c# - PNG CRC 是如何精确计算的？

Question

在过去的 4 个小时里，我一直在研究 CRC 算法。我很确定我已经掌握了窍门。

我正在尝试编写一个 png 编码器，我不希望将外部库用于 CRC 计算，也不希望用于 png 编码本身。

我的程序已经能够获得与教程示例相同的 CRC。喜欢 Wikipedia :

使用与示例中相同的多项式和消息，我能够在两种情况下产生相同的结果。我也能够为其他几个示例执行此操作。

但是，我似乎无法正确计算 png 文件的 CRC。我通过在 Paint 中创建一个空白的、一个像素大的 .png 文件并使用它的 CRC 作为比较来测试它。我从 png ( which the CRC is calculated from ) 的 IDAT block 中复制数据(和 block 名称)，并使用 png 规范中提供的多项式计算它的 CRC。

png specification 中提供的多项式是以下内容:

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

应该翻译成:

1 00000100 11000001 00011101 10110111

使用该多项式，我尝试获取以下数据的 CRC:

01001001 01000100 01000001 01010100
00011000 01010111 01100011 11101000
11101100 11101100 00000100 00000000
00000011 00111010 00000001 10011100

这是我得到的:

01011111 11000101 01100001 01101000 (MSB First)
10111011 00010011 00101010 11001100 (LSB First)

这是实际的 CRC:

11111010 00010110 10110110 11110111

我不确定如何解决这个问题，但我猜我正在做这部分 from the specification错误:

In PNG, the 32-bit CRC is initialized to all 1's, and then the data from each byte is processed from the least significant bit (1) to the most significant bit (128). After all the data bytes are processed, the CRC is inverted (its ones complement is taken). This value is transmitted (stored in the datastream) MSB first. For the purpose of separating into bytes and ordering, the least significant bit of the 32-bit CRC is defined to be the coefficient of the x31 term.

我不完全确定我能理解所有这些。

此外，这是我用来获取 CRC 的代码:

 public BitArray GetCRC(BitArray data)
    {
        // Prepare the divident; Append the proper amount of zeros to the end
        BitArray divident = new BitArray(data.Length + polynom.Length - 1);
        for (int i = 0; i < divident.Length; i++)
        {
            if (i < data.Length)
            {
                divident[i] = data[i];
            }
            else
            {
                divident[i] = false;
            }
        }

        // Calculate CRC
        for (int i = 0; i < divident.Length - polynom.Length + 1; i++)
        {
            if (divident[i] && polynom[0])
            {
                for (int j = 0; j < polynom.Length; j++)
                {
                    if ((divident[i + j] && polynom[j]) || (!divident[i + j] && !polynom[j]))
                    {
                        divident[i + j] = false;
                    }
                    else
                    {
                        divident[i + j] = true;
                    }
                }
            }
        }

        // Strip the CRC off the divident
        BitArray crc = new BitArray(polynom.Length - 1);
        for (int i = data.Length, j = 0; i < divident.Length; i++, j++)
        {
            crc[j] = divident[i];
        }
        return crc;
    }

那么，我该如何解决这个问题以匹配 PNG 规范？

Answer 1

您可以在此 public domain code 中找到 CRC 计算(和一般的 PNG 编码)的完整实现。 :

static uint[] crcTable;

// Stores a running CRC (initialized with the CRC of "IDAT" string). When
// you write this to the PNG, write as a big-endian value
static uint idatCrc = Crc32(new byte[] { (byte)'I', (byte)'D', (byte)'A', (byte)'T' }, 0, 4, 0);

// Call this function with the compressed image bytes, 
// passing in idatCrc as the last parameter
private static uint Crc32(byte[] stream, int offset, int length, uint crc)
{
    uint c;
    if(crcTable==null){
        crcTable=new uint[256];
        for(uint n=0;n<=255;n++){
            c = n;
            for(var k=0;k<=7;k++){
                if((c & 1) == 1)
                    c = 0xEDB88320^((c>>1)&0x7FFFFFFF);
                else
                    c = ((c>>1)&0x7FFFFFFF);
            }
            crcTable[n] = c;
        }
    }
    c = crc^0xffffffff;
    var endOffset=offset+length;
    for(var i=offset;i<endOffset;i++){
        c = crcTable[(c^stream[i]) & 255]^((c>>8)&0xFFFFFF);
    }
    return c^0xffffffff;
}

1 https://web.archive.org/web/20150825201508/http://upokecenter.dreamhosters.com/articles/png-image-encoder-in-c/