如何计算CRC32校验和？

也许我只是没有看到它，但CRC32似乎不必要的复杂，或没有足够的解释，我可以在网上find任何地方。

我理解它的要点就在于它是由消息值的非进位的算术除法的余数除以多项式，但是它的实际执行却逃脱了我。

我已经阅读了CRC错误检测algorithm的无痛指南 ，我必须说这不是无痛的。 它理论上相当好，但作者从来没有得到一个简单的“这就是它”。 他确实说了标准的CRC32algorithm的参数是什么，但是他忽略了清楚地说明如何实现它。

得到我的部分是当他说“这就是它”，然后加上“哦，顺便说一下，它可以颠倒或从不同的初始条件开始”，并没有给出明确的答案，最终的方式是什么计算一个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; } 

但是这似乎产生了与我在互联网上其他地方find的值不一致的值。 我可以用我发现的价值观，但我想了解他们是如何抵达他们的。

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

Answer 1

CRC32的多项式是：

0x04C11DB7

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

• 维基百科
• CRC计算

哪些工作是二进制的：

100110000010001110110110111

可以自由计数1和0，但是您会发现它们与1是位0（或第一位）和x是位1（或第二位）的多项式匹配。

为什么这个多项式？ 因为需要一个标准给定多项式，标准由IEEE 802.3设置。 另外find一个有效工作的多项式也是非常困难的。

您可以将CRC-32看作是一系列“不进行二进制算术运算”或基本上是异或运算。 这在技术上被称为多项式算术（Polynomial Arithmetic）。

– CRC引物，第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引物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 

但math家改变了规则，使它是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 Poly : 10011 Message after appending W zeros : 11010110110000 Now we simply divide the augmented message by the poly using CRC arithmetic. This is the same division as before: 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!!!! The division yields a quotient, which we throw away, and a remainder, which is the calculated checksum. This ends the calculation. Usually, the checksum is then appended to the message and the result transmitted. In this case the transmission would be: 11010110111110. 

– CRC引物，第7章

只能使用32位数字作为除数，并使用整个stream作为您的分红。 抛出商并保留余数。 把剩下的部分放在信息的末尾，你有一个CRC32。

平均家伙评论：

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

1. 以前32位。
2. 移位
3. 如果32位小于DIVISOR，则转到步骤2。
4. 由DIVISOR异或32位。 转到第2步。

（请注意，数据stream必须可以被32位分割，或者应该被填充，例如，一个8位的ANSI数据stream将被填充，同样在数据stream的末尾，分隔也会被暂停）。

Answer 2

CRC很简单， 你把一个多项式表示成比特和数据，然后把多项式分成数据（或者你把数据表示成一个多项式并且做同样的事情）。 0和多项式之间的余数是CRC。 你的代码有点难以理解，部分是因为它是不完整的：temp和testcrc没有被声明，所以不清楚索引什么，以及algorithm中运行了多less数据。

理解CRC的方法是尝试使用短多项式（16位左右）和短多项式（4位）来计算一些数据。 如果你这样练习，你就会真正理解你如何编码它。

如果你经常这样做，一个CRC在软件中计算是相当慢的。 硬件计算效率更高，只需要几个门。

Answer 3

除了维基百科的循环冗余校验和CRC文章的计算之外 ，我还发现了一篇名为Reversing CRC – Theory and Practice ^*的论文 ，作为一个很好的参考。

基本上有三种计算CRC的方法：代数方法，位方法和表驱动方法。 在逆向CRC-理论和实践 ^*中 ，这三种algorithm/方法中的每一种都在理论上伴随着在附录中通过在C编程语言中的CRC32的实现来解释。

^{* PDF链接
逆向CRC – 理论与实践。
胡柏林公众报告
SAR-PR-2006-05
2006年5月
作者：
Martin Stigge，HenrykPlötz，WolfMüller，Jens-Peter Redlich}

Answer 4

对于IEEE802.3，CRC-32。 将整个消息视为一个串行比特stream，在消息的末尾附加32个零。 接下来，你必须反转消息的每个字节的位，并对前32位进行1的补码。 现在除以CRC-32多项式，0x104C11DB7。 最后，你必须对这个除法的32位余数进行补码 – 反转余数的4个字节中的每一个。 这将成为消息结尾附加的32位CRC。

这个奇怪的过程的原因是，第一个以太网实现将一次一个字节地串行化消息并且首先传输每个字节的最低有效位。 然后串行比特stream经过一个串行的CRC-32移位寄存器计算，在消息完成之后，串行比特stream被简单地补充并发送出去。 补充消息的前32位的原因是，即使消息全部为零，也不会获得全零CRC。

Answer 5

我花了一段时间试图揭开这个问题的答案，并且我终于今天发布了关于CRC-32的教程： CRC-32哈希教程 – AutoHotkey社区

在这个例子中，我演示了如何计算ASCIIstring'abc'的CRC-32哈希值：

 calculate the CRC-32 hash for the ASCII string 'abc': inputs: dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263 polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7 011000010110001001100011 reverse bits in each byte: 100001100100011011000110 append 32 0 bits: 10000110010001101100011000000000000000000000000000000000 XOR the first 4 bytes with 0xFFFFFFFF: 01111001101110010011100111111111000000000000000000000000 'CRC division': 01111001101110010011100111111111000000000000000000000000 100000100110000010001110110110111 --------------------------------- 111000100010010111111010010010110 100000100110000010001110110110111 --------------------------------- 110000001000101011101001001000010 100000100110000010001110110110111 --------------------------------- 100001011101010011001111111101010 100000100110000010001110110110111 --------------------------------- 111101101000100000100101110100000 100000100110000010001110110110111 --------------------------------- 111010011101000101010110000101110 100000100110000010001110110110111 --------------------------------- 110101110110001110110001100110010 100000100110000010001110110110111 --------------------------------- 101010100000011001111110100001010 100000100110000010001110110110111 --------------------------------- 101000011001101111000001011110100 100000100110000010001110110110111 --------------------------------- 100011111110110100111110100001100 100000100110000010001110110110111 --------------------------------- 110110001101101100000101110110000 100000100110000010001110110110111 --------------------------------- 101101010111011100010110000001110 100000100110000010001110110110111 --------------------------------- 110111000101111001100011011100100 100000100110000010001110110110111 --------------------------------- 10111100011111011101101101010011 remainder: 0b10111100011111011101101101010011 = 0xBC7DDB53 XOR the remainder with 0xFFFFFFFF: 0b01000011100000100010010010101100 = 0x438224AC reverse bits: 0b00110101001001000100000111000010 = 0x352441C2 thus the CRC-32 hash for the ASCII string 'abc' is 0x352441C2