CRC32 校验和是如何计算的？
也许我只是没有看到它，但 CRC32 似乎要么不必要地复杂，要么在我可以在网络上找到的任何地方都没有得到充分的解释。
我知道它是消息值的基于非进位的算术除法除以（生成器）多项式的余数，但它的实际实现让我无法理解。
我读过 CRC 错误检测算法无痛指南，我必须说它是不是无痛的。它很好地阐述了这个理论，但作者从来没有得出一个简单的“就是这样”。他确实说明了标准 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;
}
但这似乎生成的值与我在互联网其他地方找到的值不一致。我可以使用我在网上找到的值，但我想了解它们是如何创建的。
任何帮助澄清这些令人难以置信的令人困惑的数字的帮助将非常感激。
Maybe I'm just not seeing it, but CRC32 seems either needlessly complicated, or insufficiently explained anywhere I could find on the web.
I understand that it is the remainder from a non-carry-based arithmetic division of the message value, divided by the (generator) polynomial, but the actual implementation of it escapes me.
I've read A Painless Guide To CRC Error Detection Algorithms, and I must say it was not painless. It goes over the theory rather well, but the author never gets to a simple "this is it." He does say what the parameters are for the standard CRC32 algorithm, but he neglects to lay out clearly how you get to it.
The part that gets me is when he says "this is it" and then adds on, "oh by the way, it can be reversed or started with different initial conditions," and doesn't give a clear answer of what the final way of calculating a CRC32 checksum given all of the changes he just added.
- Is there a simpler explanation of how CRC32 is calculated?
I attempted to code in C how the table is formed:
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;
}
but this seems to generate values inconsistent with values I have found elsewhere on the Internet. I could use the values I found online, but I want to understand how they were created.
Any help in clearing up these incredibly confusing numbers would be very appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
CRC32 的多项式为：
或者以十六进制和二进制表示：
最高项 (x32) 通常不会明确写入，因此可以用十六进制表示，如下所示
随意数一下 1 和 0，但您会发现它们与多项式匹配，其中
1是位 0（或第一位），x< /code> 是位 1（或第二位）。为什么是这个多项式？因为需要有一个给定多项式的标准，而该标准是由 IEEE 802.3 制定的。此外，找到有效检测不同比特错误的多项式也是极其困难的。
您可以将 CRC-32 视为一系列“无进位的二进制算术”，或者基本上是“异或和移位运算”。这在技术上称为多项式算术。
为了更好地理解它，请思考乘法：
如果我们假设 x 是以 2 为底，那么我们得到：
为什么？因为 3x^3 是 11x^11（但我们只需要 1 或 0 前位），所以我们结转：
但是数学家改变了规则，使其为 mod 2。所以基本上任何二进制多项式 mod 2 只是加法，没有进位或异或。所以我们最初的等式看起来像：
我知道这是一次信念的飞跃，但这超出了我作为线路程序员的能力。如果你是一名铁杆计算机科学学生或工程师，我挑战你要打破这一点。每个人都会从这个分析中受益。
因此，要计算出一个完整的示例：
现在我们使用 CRC 算术将增强消息除以 Poly。这与之前的除法相同：
除法产生一个商（我们将其丢弃）和一个余数（即计算出的校验和）。至此计算结束。通常，校验和会附加到消息中并传输结果。在这种情况下，传输将为：11010110111110。
仅使用 32 位数字作为除数，并使用整个流作为除数。去掉商并保留余数。将剩余部分粘贴到消息末尾，您就得到了 CRC32。
一般人评论：
（请注意，流必须可被 32 位整除，否则应进行填充。例如，必须填充 8 位 ANSI 流。此外，在流末尾，除法也会停止.)
The polynomial for CRC32 is:
Or in hex and binary:
The highest term (x32) is usually not explicitly written, so it can instead be represented in hex just as
Feel free to count the 1s and 0s, but you'll find they match up with the polynomial, where
1is bit 0 (or the first bit) andxis bit 1 (or the second bit).Why this polynomial? Because there needs to be a standard given polynomial and the standard was set by IEEE 802.3. Also it is extremely difficult to find a polynomial that detects different bit errors effectively.
You can think of the CRC-32 as a series of "Binary Arithmetic with No Carries", or basically "XOR and shift operations". This is technically called Polynomial Arithmetic.
To better understand it, think of this multiplication:
If we assume x is base 2 then we get:
Why? Because 3x^3 is 11x^11 (but we need only 1 or 0 pre digit) so we carry over:
But mathematicians changed the rules so that it is mod 2. So basically any binary polynomial mod 2 is just addition without carry or XORs. So our original equation looks like:
I know this is a leap of faith but this is beyond my capability as a line-programmer. If you are a hard-core CS-student or engineer I challenge to break this down. Everyone will benefit from this analysis.
So to work out a full example:
Now we divide the augmented Message by the Poly using CRC arithmetic. This is the same division as before:
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.
Only use a 32-bit number as your divisor and use your entire stream as your dividend. Throw out the quotient and keep the remainder. Tack the remainder on the end of your message and you have a CRC32.
Average guy review:
(Note that the stream has to be dividable by 32 bits or it should be padded. For example, an 8-bit ANSI stream would have to be padded. Also at the end of the stream, the division is halted.)
我在这里发布了有关 CRC-32 哈希的教程：
CRC-32 哈希教程 - AutoHotkey 社区
在此示例中，我演示了如何计算“ANSI”（每个字符 1 个字节）字符串“abc”的 CRC-32 哈希值：
I published a tutorial on CRC-32 hashes, here:
CRC-32 hash tutorial - AutoHotkey Community
In this example from it, I demonstrate how to calculate the CRC-32 hash for the 'ANSI' (1 byte per character) string 'abc':
对于 IEEE802.3、CRC-32。将整个消息视为串行比特流，在消息末尾附加 32 个零。接下来，您必须反转消息每个字节的位，并对前 32 位进行 1 补码。现在除以 CRC-32 多项式 0x104C11DB7。最后，您必须对该除法的 32 位余数进行 1 补码，并对余数的每个 4 字节进行位反转。这成为附加到消息末尾的 32 位 CRC。
这种奇怪过程的原因是，第一个以太网实现将一次一个字节地序列化消息，并首先传输每个字节的最低有效位。然后，串行比特流经过串行 CRC-32 移位寄存器计算，在消息完成后简单地进行补充并通过线路发送出去。对消息的前 32 位进行补码的原因是，即使消息全为零，您也不会得到全零 CRC。
For IEEE802.3, CRC-32. Think of the entire message as a serial bit stream, append 32 zeros to the end of the message. Next, you MUST reverse the bits of EVERY byte of the message and do a 1's complement the first 32 bits. Now divide by the CRC-32 polynomial, 0x104C11DB7. Finally, you must 1's complement the 32-bit remainder of this division bit-reverse each of the 4 bytes of the remainder. This becomes the 32-bit CRC that is appended to the end of the message.
The reason for this strange procedure is that the first Ethernet implementations would serialize the message one byte at a time and transmit the least significant bit of every byte first. The serial bit stream then went through a serial CRC-32 shift register computation, which was simply complemented and sent out on the wire after the message was completed. The reason for complementing the first 32 bits of the message is so that you don't get an all zero CRC even if the message was all zeros.
CRC 非常简单；您采用表示为位和数据的多项式，并将多项式除以数据（或者您将数据表示为多项式并执行相同的操作）。 0 和多项式之间的余数就是 CRC。您的代码有点难以理解，部分原因是它不完整： temp 和 testcrc 未声明，因此不清楚正在索引什么，以及有多少数据正在通过算法运行。
理解 CRC 的方法是尝试使用一小段数据（16 位左右）和一个短多项式（也许是 4 位）来计算一些 CRC。如果您以这种方式进行练习，您将真正了解如何进行编码。
如果您经常这样做，则软件中计算 CRC 的速度会相当慢。硬件计算效率更高，并且只需要几个门。
A CRC is pretty simple; you take a polynomial represented as bits and the data, and divide the polynomial into the data (or you represent the data as a polynomial and do the same thing). The remainder, which is between 0 and the polynomial is the CRC. Your code is a bit hard to understand, partly because it's incomplete: temp and testcrc are not declared, so it's unclear what's being indexed, and how much data is running through the algorithm.
The way to understand CRCs is to try to compute a few using a short piece of data (16 bits or so) with a short polynomial -- 4 bits, perhaps. If you practice this way, you'll really understand how you might go about coding it.
If you're doing it frequently, a CRC is quite slow to compute in software. Hardware computation is much more efficient, and requires just a few gates.
除了维基百科的循环冗余检查和CRC的计算文章，我发现了一篇题为逆转 CRC - 理论与实践* 是一个很好的参考。
计算 CRC 基本上有三种方法：代数方法、面向位的方法和表驱动的方法。 逆转 CRC - 理论与实践 *，这三种算法/方法中的每一种都在理论上进行了解释，并在附录中附有 C 编程语言中的 CRC32 实现。
* PDF 链接
逆转 CRC – 理论与实践。
HU 柏林公开报告
SAR-PR-2006-05
2006 年 5 月
作者：
马丁·斯蒂格、亨利克·普洛茨、沃尔夫·穆勒、延斯-彼得·雷德利希
In addition to the Wikipedia Cyclic redundancy check and Computation of CRC articles, I found a paper entitled Reversing CRC - Theory and Practice* to be a good reference.
There are essentially three approaches for computing a CRC: an algebraic approach, a bit-oriented approach, and a table-driven approach. In Reversing CRC - Theory and Practice*, each of these three algorithms/approaches is explained in theory accompanied in the APPENDIX by an implementation for the CRC32 in the C programming language.
* PDF Link
Reversing CRC – Theory and Practice.
HU Berlin Public Report
SAR-PR-2006-05
May 2006
Authors:
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich
然后总是有 Rosetta Code，它显示了用数十种计算机语言实现的 crc32。 https://rosettacode.org/wiki/CRC-32 并包含许多解释和内容的链接实施。
Then there is always Rosetta Code, which shows crc32 implemented in dozens of computer languages. https://rosettacode.org/wiki/CRC-32 and has links to many explanations and implementations.
为了减少 crc32 的提醒，您需要：
在代码中是这样的：
其中reminderIEEE是GF(2)[x]上的纯粹提醒
In order to reduce crc32 to taking the reminder you need to:
In code this is:
where reminderIEEE is the pure reminder on GF(2)[x]