CRC32校验和是如何计算的？

Question

我可能只是没看到，但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;
}

但是这似乎生成的数值与我在互联网上找到的数值不一致。我可以使用我在网上找到的数值，但我想理解它们是如何创建的。

任何有助于澄清这些难以理解的数字的帮助都将非常感激。

- aquanar

---

你生成CRC32表格的代码看起来是正确的。你使用的反向最低位（lsbit-first）的CRC32多项式0xEDB88320也可以正向最高位（msbit-first）表示为0x04C11DB7。你在别处找到的表格数值是否是使用相同的CRC多项式生成的？ - jschmier

@jschmier 嗨，我感觉自己比那个问问题的人落后一步了？https://dev59.com/FLvoa4cB1Zd3GeqP2mKf - B''H Bi'ezras -- Boruch Hashem

如果其他人也想阅读上面链接的“CRC错误检测算法无痛指南”，原始URL已经失效，但是谷歌很容易找到几份副本，包括这个：https://zlib.net/crc_v3.txt。 - Stéphane

Answer 1

CRC32的多项式为:

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

• 维基百科
• CRC计算

或以十六进制和二进制表示:

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

最高位（x³²）通常不会明确写出，因此可以用十六进制表示为

0x 04 C1 1D B7

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

因为需要一个标准的多项式，而IEEE 802.3设置了这个标准，所以选择了这个多项式。此外，要找到一个有效检测不同位错误的多项式非常困难。

您可以将CRC-32视为一系列“没有进位的二进制算术”，或者基本上是“XOR和移位操作”。从技术上讲，这被称为多项式算术。 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基础知识 第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

但是数学家改变了规则，使其模2。因此，基本上任何二进制多项式模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)

我知道这需要一定的信仰，但作为一名线性编程人员，这已经超出了我的能力范围。如果你是一名硬核计算机科学学生或工程师，我挑战你来分解这个问题。每个人都将从这个分析中受益。

因此，让我们来看一个完整的例子：

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

现在，我们使用CRC算术将增强的消息除以多项式。这与之前的除法相同：

            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。

• CRC 基础知识，第7章

只使用32位数字作为除数，并将整个流用作被除数。丢弃商，保留余数。将余数添加到消息末尾，这样就得到了CRC32。

普通人的评价：

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

1. 取前32位。
2. 移位
3. 如果32位小于除数，则转到步骤2。
4. 将32位异或除数。 转到步骤2。

（请注意，流必须可被32位整除，否则应进行填充。例如，8位ANSI流必须进行填充。在流的末尾，除法停止。）

- user295190

---

最后的“普通人评论”点赞，建议将其放在最上面 - 就像是一个TL; DR（太长，没看: P） - aaronsnoswell

记住，我们在做的是多项式除法，而不仅仅是二进制数。我们无法进行“正常”减法，因为我们无法从$x^{n+1}$中“借” $x^n$；它们是不同类型的东西。此外，由于位只能是0或1，那么-1甚至是什么？实际上，我们是在以$Z/2Z$作系数的多项式环中工作，该环仅有两个元素0和1，其中$1+1=0$。通过将系数放在一个域内，多项式形成了所谓的欧几里得整环，这基本上允许我们首先就确定我们要做的事情。 - calavicci

为了澄清，实际的多项式是100000100110000010001110110110111 = 0x104C11DB7。最高位隐含，但在实现中仍应考虑到它。由于多项式需要为33位长（因此余数可以为32位长），因此最高位始终被设置，有些人会省略最高位。 - Felipe T.

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。这不是数学的工作方式。多项式的系数是 mod(2) 或 GF(2)，x 不变，结果为 x ^ 6 + x ^ 5 + x ^ 4 + x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0（因为 3 mod(2) = 1）。"在您的消息末尾添加余数" - 技术上，余数被减去附加到消息的 0 位，但由于这是 mod(2) 数学，加和减相同于异或，零位与余数异或等于余数。 - rcgldr

@MarcusJ - 你为什么要添加四个0呢？ - 软件算法有效地附加了这些0，即使它并不明显。如果使用长除法显示CRC计算，则需要附加这些0以使除法示例正确显示。 - rcgldr

Answer 2

对于IEEE802.3而言，CRC-32的计算方式如下：将整个消息视为串行比特流，在消息末尾追加32个零。接下来，必须反转消息中每个字节的比特位并对前32位进行一次1's补码运算。然后用CRC-32多项式0x104C11DB7进行除法运算。最后，必须对这个除法的32位余数进行1's补码运算，并逆序处理4个字节的余数。这个余数就是附加在消息末尾的32位CRC。

这种奇怪的过程存在的原因是，最初的以太网实现会将消息逐字节序列化并以最低有效位先传输。然后，串行比特流通过串行CRC-32移位寄存器运算，完成消息后直接进行补码运算并发送到线路上。为了避免消息全部为零时产生全零CRC，需要对消息的前32位进行补码运算。

- Pavlo Bobrek

---

到目前为止，这是最好的答案，尽管我会用“将4个字节视为一个实体进行位反转”来替换“位反转每个4个字节”，例如将“abcdefgh ijklmnop qrstuvwx yzABCDEF”转换为“FEDCBAzy xwvutsrq ponmlkji hgfedcba”。另请参阅：CRC-32哈希教程-AutoHotkey社区。 - vafylec

你好，你具体是通过什么“消息”进行反转的？https://dev59.com/FLvoa4cB1Zd3GeqP2mKf - B''H Bi'ezras -- Boruch Hashem

Answer 3

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

CRC-32哈希教程 - AutoHotkey社区

在这个示例中，我展示了如何计算“ANSI”字符串“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

- vafylec

---

如果你想要更快的速度，可以使用英特尔工程师在2006年开发出的一种方法，通常同时使用机器数据总线宽度的4或8个字节。学术论文：https://static.aminer.org/pdf/PDF/000/432/446/a_systematic_approach_to_building_high_performance_software_based_crc.pdf Sourceforge项目：http://sourceforge.net/projects/slicing-by-8/普通crc页面：https://create.stephan-brumme.com/crc32/ - Alan Corey

嗨，谢谢，看起来很不错，但是你是如何得到多项式值的呢？X具体代表什么？当它说x^32时，是指32次方，还是按位运算符^？https://dev59.com/FLvoa4cB1Zd3GeqP2mKf - B''H Bi'ezras -- Boruch Hashem

Answer 4

CRC非常简单；你将表示为位的多项式和数据相除（或者将数据表示为多项式并执行相同操作）。余数，介于0和多项式之间，就是CRC。由于temp和testcrc未声明，因此很难理解你的代码，部分原因是它不完整，无法确定正在索引什么以及算法运行了多少数据。

理解CRC的方法是使用短数据（大约16位）和短多项式（例如4位）尝试计算几个。通过这种方式练习，您将真正了解如何编写代码。

如果您经常这样做，CRC在软件中计算速度非常慢。 硬件计算效率更高，仅需要几个门。

- WhirlWind

---

对于CRC32或CRC32b，我们是否会得到哈希冲突的意思，即两个不同的字符串是否会得到相同的CRC？ - indianwebdevil

你好，我有点困惑你所说的“将多项式分成数据”的意思是什么？在这个链接（https://dev59.com/FLvoa4cB1Zd3GeqP2mKf）中，多项式表示中的X代表什么？我应该使用块中的其他字节吗？ - B''H Bi'ezras -- Boruch Hashem

Answer 5

除了维基百科的循环冗余校验和CRC计算文章外，我还发现一篇名为反向CRC——理论与实践^*的论文是一个很好的参考资料。

计算CRC有三种方法：代数方法、比特导向方法和表驱动方法。在反向CRC——理论与实践^*中，这三种算法/方法在理论上都有解释，并在附录中用C编程语言实现了CRC32。

^{* PDF链接
逆向CRC - 理论与实践。
HU柏林公共报告
SAR-PR-2006-05
2006年5月
作者:
Martin Stigge，Henryk Plötz，Wolf Müller，Jens-Peter Redlich}

- jschmier

---

你好，能否详细说明一下？ - B''H Bi'ezras -- Boruch Hashem

Answer 6

还有一种方法是使用Rosetta Code，它展示了crc32在许多计算机语言中的实现。 https://rosettacode.org/wiki/CRC-32 ，并提供了许多解释和实现的链接。

- don bright

---

你能详细解释一下吗？https://dev59.com/FLvoa4cB1Zd3GeqP2mKf - B''H Bi'ezras -- Boruch Hashem

Answer 7

为了将crc32缩小到取余数，您需要执行以下操作：

1. 反转每个字节上的位
2. 将前四个字节与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
}

其中reminderIEEE是GF(2)[x]上的纯余数

- Gabriel Furstenheim

---

我有一点（位运算）难以理解这个问题？https://dev59.com/FLvoa4cB1Zd3GeqP2mKf - B''H Bi'ezras -- Boruch Hashem

嘿@bluejayke，看看这个库https://github.com/furstenheim/sparse_crc32/blob/master/main.go，它实现了稀疏文件的crc32，你可以在那里看到计算的细节。它没有被优化，所以比普通实现更容易理解。可能你不理解的是GF(2)[x]部分。基本上x^3 + x表示1010，x ^4 + x + 1表示10011。然后你需要进行除法，例如x^3 + x是x * (x^2 + 1)。所以x^3 + x对于x的余数是0，但对于x ^2来说，余数将是x ^ 2 * x + x，也就是余数是x。 - Gabriel Furstenheim

@bluejayke和reminderIEEE意味着提醒一个众所周知的多项式，即IEEE多项式。 - Gabriel Furstenheim

再次问候，感谢您的回复。 我只是想理解（为了JavaScript）多项式中的“x”代表什么。 “x”是某种代码词吗？这里有很多让我困惑的术语，我以前从未听说过CRC32，并且即使进行搜索，我也找不到它的详细解释。例如对于PNG，它说我需要获取“每个块的CRC”，这是指“块中所有数据”吗？ 但是我该如何将其“插入”到多项式中呢？ “x”代表什么？此外，当它说x^32时，是否像Math.pow（x，32）或位运算符^一样？ - B''H Bi'ezras -- Boruch Hashem

嗨@bluejayke，x是一个抽象概念，使计算变得容易。不希望用任何东西替代它。我指的是x * x，作为正式乘法。在这里http://chrisballance.com/wp-content/uploads/2015/10/CRC-Primer.html，您可以找到有关该除法的详细解释。我的回答尝试填补该链接中除法和实际计算之间的差距。 - Gabriel Furstenheim