c - 如何计算 CRC32 校验和？

Question

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

我知道它是消息值的非基于进位的算术除法除以(生成器)多项式的余数，但我不知道它的实际实现。

我读过 A Painless Guide To CRC Error Detection Algorithms ，我必须说这并非没有痛苦。它很好地阐述了这个理论，但作者从来没有说出一个简单的“就是这样”。他确实说明了标准 CRC32 算法的参数是什么，但他忽略了清楚地说明如何实现它。

让我理解的部分是当他说“就是这样”然后补充说“哦顺便说一下，它可以被逆转或从不同的初始条件开始”并且没有给出明确的答案考虑到他刚刚添加的所有更改，计算 CRC32 校验和的 final方法。

• 对于 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;
}

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

任何帮助清理这些令人难以置信的困惑数字的人都将非常感激。

Answer 1

CRC32 的多项式是:

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

• Wikipedia
• CRC calculation

或者十六进制和二进制:

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

最高项 (x³²) 通常没有显式写入，因此可以用十六进制表示，就像

0x 04 C1 1D B7

随意计算 1 和 0，但您会发现它们与多项式匹配，其中 1 是位 0(或第一位)和 x 是第 1 位(或第二位)。

为什么这个多项式？因为给定多项式需要有一个标准，而这个标准是由 IEEE 802.3 制定的。也很难找到有效检测不同位错误的多项式。

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

• CRC primer, Chapter 5

为了更好地理解它，想想这个乘法:

(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 primer Chp.5

为什么？因为 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)

我知道这是一种信仰的飞跃，但这超出了我作为一名程序员的能力。如果您是 CS 的硬核学生或工程师，我挑战将其分解。每个人都会从这个分析中受益。

所以要制定一个完整的例子:

   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 primer, Chapter 7

仅使用 32 位数字作为除数，并将整个流用作除数。去掉商，保留余数。将消息末尾的其余部分添加到 CRC32 中。

平均评价:

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

1. 取前 32 位。
2. 移位位
3. 如果 32 位小于 DIVISOR，转到第 2 步。
4. 用 DIVISOR 异或 32 位。转到第 2 步。

(请注意，流必须可以除以 32 位，否则应该被填充。例如，必须填充 8 位 ANSI 流。同样在流的末尾，除法停止。)