124

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

我知道它是消息值的非基于进位的算术除法除以（生成器）多项式的余数，但它的实际实现使我无法理解。

我读过A Painless Guide To CRC Error Detection Algorithms，我必须说它不是无痛的。它很好地解释了理论，但作者从来没有得到一个简单的“就是这样”。他确实说明了标准 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;
}

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

在清理这些令人难以置信的令人困惑的数字方面的任何帮助将不胜感激。

4

7 回答 7

142

CRC32 的多项式是：

x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1

或十六进制和二进制：

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

最高项 (x 32 ) 通常没有明确写出，因此它可以用十六进制表示，就像

0x 04 C1 1D B7

随意计算 1 和 0，但您会发现它们与多项式相匹配，1即位 0（或第一位）和x位 1（或第二位）。

为什么是这个多项式？因为需要有一个给定多项式的标准，并且该标准是由 IEEE 802.3 制定的。此外，要找到有效检测不同误码的多项式也非常困难。

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

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

(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

为什么？因为 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 都只是没有进位或 XOR 的加法。所以我们的原始方程看起来像：

=( 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。

仅使用 32 位数字作为除数，并使用整个流作为除数。扔掉商并保留余数。在邮件末尾添加其余部分，您将获得 CRC32。

普通人评论：

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER
  1. 取前 32 位。
  2. 移位位
  3. 如果 32 位小于 DIVISOR，则转到步骤 2。
  4. 通过 DIVISOR 异或 32 位。转到第 2 步。

（请注意，流必须可被 32 位整除，否则应进行填充。例如，必须填充 8 位 ANSI 流。同样在流结束时，停止除法。）

于 2011-01-27T00:21:32.073 回答
13

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

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

于 2017-06-28T14:26:04.643 回答
11

CRC 非常简单。您将多项式表示为位和数据，然后将多项式划分为数据（或者您将数据表示为多项式并执行相同的操作）。余数（介于 0 和多项式之间）是 CRC。您的代码有点难以理解，部分原因是它不完整： temp 和 testcrc 未声明，因此不清楚索引的内容以及通过算法运行的数据量。

理解 CRC 的方法是尝试使用带有短多项式（可能是 4 位）的一小段数据（16 位左右）来计算一些 CRC。如果您以这种方式练习，您将真正了解如何进行编码。

如果您经常这样做，那么在软件中计算 CRC 会很慢。硬件计算效率更高，并且只需要几个门。

于 2010-04-06T19:56:05.203 回答
11

我在这里发布了一篇关于 CRC-32 哈希的教程： CRC-32 哈希教程 - AutoHotkey 社区

在此示例中，我演示了如何计算 '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
于 2017-08-09T23:39:45.457 回答
8

除了 Wikipedia Cyclicredundancy check and Computation of CRC文章之外，我发现一篇题为Reversing CRC - Theory and Practice *的论文是一个很好的参考。

计算 CRC 基本上有三种方法：代数方法、面向位的方法和表驱动方法。在Reversing CRC - Theory and Practice *中，这三种算法/方法中的每一种都在理论上进行了解释，附录中附有 C 编程语言中 CRC32 的实现。

* PDF Link
Reversing CRC – 理论与实践。
HU Berlin Public Report
SAR-PR- 2006-05
May 2006
作者：
Martin Stigge、Henryk Plötz、Wolf Müller、Jens-Peter Redlich

于 2011-01-27T03:55:43.337 回答
2

然后总是有 Rosetta Code，它显示了用几十种计算机语言实现的 crc32。https://rosettacode.org/wiki/CRC-32并链接到许多解释和实现。

于 2020-04-15T00:46:55.713 回答
1

为了减少 crc32 以接收提醒，您需要：

  1. 反转每个字节上的位
  2. xor 前四个字节与 0xFF（这是为了避免前导 0 上的错误）
  3. 在末尾添加填充（这是为了使最后 4 个字节参与散列）
  4. 计算提醒
  5. 再次反转位
  6. 再次异或结果。

在代码中是：


func CRC32 (file []byte) uint32 {
    for i , v := range(file) {
        file[i] = bits.Reverse8(v)
    }
    for i := 0; i < 4; i++ {
        file[i] ^= 0xFF
    }

    // Add padding
    file = append(file, []byte{0, 0, 0, 0}...)
    newReminder := bits.Reverse32(reminderIEEE(file))

    return newReminder ^ 0xFFFFFFFF
}

其中，remindIEEE 是 GF(2)[x] 上的纯提醒

于 2020-05-05T16:19:06.413 回答