CRC32 校验和是如何计算的？

也许我只是没有看到它，但 CRC32 似乎要么不必要地复杂，要么在我可以在网络上找到的任何地方都没有得到充分的解释。

我知道它是消息值的基于非进位的算术除法除以（生成器）多项式的余数，但它的实际实现让我无法理解。

我读了CRC 错误检测算法的轻松指南 http://www.ross.net/crc/crcpaper.html，我必须说这并不是无痛的。它很好地阐述了这个理论，但作者从来没有得出一个简单的“就是这样”。他确实说明了标准 CRC32 算法的参数是什么，但他忽略了清楚地说明如何获得它。

让我困惑的是，他说“就是这样”，然后补充道，“哦，顺便说一句，它可以逆转或以不同的初始条件开始”，并且没有给出最终方式的明确答案考虑到他刚刚添加的所有更改，计算 CRC32 校验和。

• 有没有更简单的解释一下CRC32是如何计算的？

我尝试用 C 语言编写表格的形成方式：

for (i = 0; i < 256; i++)
{
    temp = i;

    for (j = 0; j < 8; j++)
    {
        if (temp & 1)
        {
            temp >>= 1;
            temp ^= 0xEDB88320;
        }
        else {temp >>= 1;}
    }
    testcrc[i] = temp;
}

但这似乎生成的值与我在互联网其他地方找到的值不一致。我could使用我在网上找到的值，但我想了解它们是如何创建的。

任何有助于澄清这些令人难以置信的令人困惑的数字的帮助都是very赞赏。

CRC32 的多项式为：

x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

• 维基百科 http://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRCs_and_data_integrity
• CRC计算 http://www.lammertbies.nl/comm/info/crc-calculation.html

或者以十六进制和二进制表示：

0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111

The highest term (x³²) is usually not explicitly written, so it can instead be represented in hex just as

0x 04 C1 1D B7

随意数一下 1 和 0，但您会发现它们与多项式匹配，其中1是位 0（或第一位）并且x是位 1（或第二位）。

为什么是这个多项式？因为需要有一个给定多项式的标准，而该标准是由 IEEE 802.3 制定的。此外，找到有效检测不同比特错误的多项式也是极其困难的。

您可以将 CRC-32 视为一系列“无进位的二进制算术”，或者基本上是“异或和移位运算”。这在技术上称为多项式算术。

• CRC 入门，第 5 章 http://chrisballance.com/wp-content/uploads/2015/10/CRC-Primer.html

为了更好地理解它，请考虑这个乘法：

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

如果我们假设 x 以 2 为底，那么我们得到：

x^7 + x^3 + x^2 + x^1 + x^0

• CRC 引物 Chp.5 http://chrisballance.com/wp-content/uploads/2015/10/CRC-Primer.html

为什么？因为 3x^3 是 11x^11（但我们只需要 1 或 0 个前位），所以我们结转：

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

但数学家改变了规则，使其为 mod 2。所以基本上任何二进制多项式 mod 2 都只是加法，没有进位或异或。所以我们的原始方程如下：

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

我知道这是一次信念的飞跃，但这超出了我作为线路程序员的能力。如果你是一名铁杆计算机科学学生或工程师，我挑战你要打破这一点。每个人都会从这个分析中受益。

因此，要制定一个完整的示例：

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

现在我们使用 CRC 算术将增强消息除以 Poly。这与之前的划分相同：

            1100001010 = Quotient (nobody cares about the quotient)
       _______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder = THE CHECKSUM!!!!

除法产生一个商（我们将其丢弃）和一个余数（即计算出的校验和）。至此计算结束。通常，校验和会附加到消息中并传输结果。在这种情况下，传输将为：11010110111110。

• CRC 入门，第 7 章 http://chrisballance.com/wp-content/uploads/2015/10/CRC-Primer.html

仅使用 32 位数字作为除数，并使用整个流作为除数。去掉商并保留余数。将剩余部分粘贴到消息末尾，您就得到了 CRC32。

一般人评价：

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER

1. 取前 32 位。
2. 移位位
3. 如果 32 位小于 DIVISOR，则转至步骤 2。
4. 通过除法器对 32 位进行异或。转到步骤 2。

（请注意，流必须可被 32 位整除，否则应进行填充。例如，必须填充 8 位 ANSI 流。此外，在流末尾，除法也会停止。）