PNG CRC是如何准确计算的？

Question

在过去的4个小时里，我一直在研究CRC算法。我相信我已经掌握了它。

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

我的程序已经能够获得与教程上相同的CRC结果，例如在维基百科上:

使用与示例中相同的多项式和消息，在这两种情况下我都能够产生相同的结果。我还可以为其他几个示例做到这一点。

然而，我似乎无法正确地计算png文件的CRC。我通过在画图中创建一个空的、一个像素大小的.png文件，并使用它的CRC作为比较来测试这一点。我复制了png的IDAT块中的数据（从中计算CRC），并使用png规范中提供的多项式计算了它的CRC。

在png规范中提供的多项式如下：

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

我不确定如何修复这个问题，但我的猜测是我正错误地处理了从规范中得到的这个部分：

在PNG中，32位CRC被初始化为全1，然后从最低有效位（1）到最高有效位（128）处理每个字节的数据。处理完所有的数据字节后，将反转CRC（取其反码）。该值被传输（存储在数据流中）以MSB优先的方式。为了分离成字节和排序，32位CRC的最低有效位被定义为x31项的系数。

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

此外，这是我用于获取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规范呢？

- MythicManiac

---

我知道这不是一个获取我的代码审查的地方，但是我认为如果我包含代码，可能会有助于回答我的问题。我还没有使用单个操作处理多个位，因为我想在开始优化代码以使其更快之前先让基础部分工作。我想要理解代码，而不仅仅是从互联网上某个地方复制粘贴它。此外，我认为我已经很清楚地表明了我的代码正在工作，或者至少在我找到的指南示例中正在工作，你提供的教程就是其中之一。 - MythicManiac

我要问的问题基本上是这个预处理和后处理到底是什么？要么我没有读完教程（因为我的实现不起作用），要么它在那里没有解释清楚。 - MythicManiac

我理解这意味着我需要按照以下规范进行操作：1：将CRC初始化为全1。2：使用多项式的LSB版本处理CRC。3：翻转得到的CRC以使其成为MSB优先。如果此操作不正确，则应查看为什么无法正确获取结果。虽然如此，我非常感谢你们的帮助。 - MythicManiac

@MarcusJ “反转 CRC 的每一位” 意味着反转 CRC 的每一位。CRC 是计算的结果，不是数据，也不是多项式。 - Mark Adler

这里的 MSB 是最高有效位。CRC 总是关于位的。它们对字节的存在是不可知的。 - Mark Adler

Answer 1

您可以在这个公共领域代码中找到完整的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/

这是一个关于使用C语言编写PNG图像编码器的技术文章，可以通过上面的链接访问。

- EricLaw

---

可以使用IEND块进行测试，它应该始终生成字节0xae 0x42 0x60 0x82，因为它从不更改其名称，也从不具有任何有效负载。查看您现有的文件：它们应该都以这些字节结尾。 - AmigoJack