也许我只是没有意识到这一点,但CRC32似乎要么不必要地复杂,要么在网上任何地方都没有得到充分的解释。
我知道它是消息值的非进位算术除法除以(生成器)多项式的余数,但我搞不懂它的实际实现。
我读过A Painless Guide To CRC Error Detection Algorithms,我必须说它并不是没有痛苦的。它在理论上进行得相当好,但是作者从来没有得到一个简单的“就是这样”。他确实说了标准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;
}
但这似乎产生了与我在互联网上其他地方找到的值不一致的值。I可以使用我在网上找到的值,但我想了解它们是如何创建的。
任何帮助澄清这些令人难以置信的令人困惑的数字的人都会非常感谢。
发布于 2017-06-28 22:26:05
对于IEEE802.3、CRC-32。将整个消息视为串行比特流,在消息的末尾附加32个零。接下来,您必须反转消息的每个字节的位,并对前32位进行1的补码。现在除以CRC-32多项式0x104C11DB7。最后,您必须对该除法位的32位余数进行1的补码-反转余数的4个字节中的每一个字节。这将成为附加到消息末尾的32位CRC。
这个奇怪的过程的原因是,第一个以太网实现会一次序列化一个字节的消息,并首先传输每个字节的最低有效位。然后,串行位流经过串行CRC-32移位寄存器计算,该计算被简单地补充,并在消息完成后在线路上发送。补充消息的前32位的原因是,即使消息全为零,也不会得到全零的CRC。
发布于 2010-04-07 03:56:05
CRC非常简单;您可以将多项式表示为位和数据,然后将多项式划分为数据(或者将数据表示为多项式,然后执行相同的操作)。在0和多项式之间的余数是CRC。你的代码有点难以理解,部分原因是它是不完整的: temp和testcrc没有声明,所以不清楚索引的是什么,以及算法中运行了多少数据。
理解CRC的方法是尝试使用一小段数据(16位左右)和一个短多项式--也许是4位--来计算几个CRC。如果你以这种方式练习,你就会真正理解如何去编码它。
如果你经常这样做,CRC在软件中的计算速度是相当慢的。硬件计算效率更高,只需要几个门。
发布于 2017-08-10 07:39:45
我在这里发布了一篇关于CRC-32散列的教程:CRC-32 hash tutorial - AutoHotkey Community
在这个示例中,我演示了如何计算'ANSI‘(每个字符1字节)字符串’abc‘的CRC-32散列:
calculate the CRC-32 hash for the 'ANSI' string 'abc':
inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7
start with the 3 bytes 'abc':
61 62 63 (as hex)
01100001 01100010 01100011 (as bin)
reverse the bits in each byte:
10000110 01000110 11000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR (exclusive or) the first 4 bytes with 0xFFFFFFFF:
(i.e. flip the first 32 bits:)
01111001101110010011100111111111000000000000000000000000
next we will perform 'CRC division':
a simple description of 'CRC division':
we put a 33-bit box around the start of a binary number,
start of process:
if the first bit is 1, we XOR the number with the polynomial,
if the first bit is 0, we do nothing,
we then move the 33-bit box right by 1 bit,
if we have reached the end of the number,
then the 33-bit box contains the 'remainder',
otherwise we go back to 'start of process'
note: every time we perform a XOR, the number begins with a 1 bit,
and the polynomial always begins with a 1 bit,
1 XORed with 1 gives 0, so the resulting number will always begin with a 0 bit
'CRC division':
'divide' by the polynomial 0x104C11DB7:
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
we obtain the 32-bit remainder:
0b10111100011111011101101101010011 = 0xBC7DDB53
note: the remainder is a 32-bit number, it may start with a 1 bit or a 0 bit
XOR the remainder with 0xFFFFFFFF:
(i.e. flip the 32 bits:)
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
bit-reverse the 4 bytes (32 bits), treating them as one entity:
(e.g. 'abcdefgh ijklmnop qrstuvwx yzABCDEF'
to 'FEDCBAzy xwvutsrq ponmlkji hgfedcba':)
0b00110101001001000100000111000010 = 0x352441C2
thus the CRC-32 hash for the 'ANSI' string 'abc' is: 0x352441C2
https://stackoverflow.com/questions/2587766
复制相似问题