首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >如何计算CRC32校验和?

如何计算CRC32校验和?
EN

Stack Overflow用户
提问于 2010-04-07 03:44:51
回答 5查看 257.6K关注 0票数 122

也许我只是没有意识到这一点,但CRC32似乎要么不必要地复杂,要么在网上任何地方都没有得到充分的解释。

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

我读过A Painless Guide To CRC Error Detection Algorithms,我必须说它并不是没有痛苦的。它在理论上进行得相当好,但是作者从来没有得到一个简单的“就是这样”。他确实说了标准CRC32算法的参数是什么,但他忽略了清楚地列出如何实现它。

当他说“就是这样”,然后补充说,“哦,顺便说一下,它可以用不同的初始条件反转或开始”,但没有给出计算CRC32校验和的最终方法的明确答案,考虑到他刚刚添加的所有更改。

  • 关于CRC32的计算方式有没有更简单的解释?

我尝试用C语言编写表格是如何形成的:

代码语言:javascript
复制
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可以使用我在网上找到的值,但我想了解它们是如何创建的。

任何帮助澄清这些令人难以置信的令人困惑的数字的人都会非常感谢。

EN

回答 5

Stack Overflow用户

发布于 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。

票数 13
EN

Stack Overflow用户

发布于 2010-04-07 03:56:05

CRC非常简单;您可以将多项式表示为位和数据,然后将多项式划分为数据(或者将数据表示为多项式,然后执行相同的操作)。在0和多项式之间的余数是CRC。你的代码有点难以理解,部分原因是它是不完整的: temp和testcrc没有声明,所以不清楚索引的是什么,以及算法中运行了多少数据。

理解CRC的方法是尝试使用一小段数据(16位左右)和一个短多项式--也许是4位--来计算几个CRC。如果你以这种方式练习,你就会真正理解如何去编码它。

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

票数 11
EN

Stack Overflow用户

发布于 2017-08-10 07:39:45

我在这里发布了一篇关于CRC-32散列的教程:CRC-32 hash tutorial - AutoHotkey Community

在这个示例中,我演示了如何计算'ANSI‘(每个字符1字节)字符串’abc‘的CRC-32散列:

代码语言:javascript
复制
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
票数 11
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/2587766

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档