CRC计算简明教程¶

CRC 是一个长除法的余数。您将 CRC 添加到消息中，整个内容（消息 + CRC）是给定 CRC 多项式的倍数。要检查 CRC，您可以检查 CRC 是否与重新计算的值匹配，或者您可以检查在消息 + CRC 上计算的余数是否为 0。后一种方法被许多硬件实现使用，这也是为什么这么多协议将帧结束标志放在 CRC 之后的原因。

它实际上是您在学校学到的相同的长除法，只不过

我们正在使用二进制，因此数字只有 0 和 1，并且
在除多项式时，没有进位。我们只是异或，而不是加减。因此，我们倾向于对加法和减法之间的差异有点马虎。

像所有除法一样，余数总是小于除数。要产生 32 位 CRC，除数实际上是一个 33 位 CRC 多项式。由于它是 33 位长，所以第 32 位总是会被设置，因此通常 CRC 以十六进制写入，省略最高有效位。（如果您熟悉 IEEE 754 浮点格式，它的想法是一样的。）

请注意，CRC 是在位串上计算的，因此您必须决定每个字节中位的字节序。为了获得最佳的错误检测属性，这应该对应于它们实际发送的顺序。例如，标准 RS-232 串行是小端序；最高有效位（有时用于奇偶校验）最后发送。并且当将 CRC 字附加到消息时，您应该以正确的顺序进行，与字节序匹配。

就像普通的除法一样，您一次处理一位数字（位）。除法的每一步，您都会获取被除数的另一位数字（位）并将其附加到当前余数。然后，您找出除数的适当倍数，以将其从余数中减去，使其回到范围内。在二进制中，这很容易 - 它必须是 0 或 1，并且为了使 XOR 取消，它只是余数的第 32 位的副本。

在计算 CRC 时，我们不关心商，因此我们可以丢弃商位，但从余数中减去多项式的适当倍数，然后我们回到起点，准备处理下一位。

以这种方式编写的大端 CRC 将被编码为

for (i = 0; i < input_bits; i++) {
        multiple = remainder & 0x80000000 ? CRCPOLY : 0;
        remainder = (remainder << 1 | next_input_bit()) ^ multiple;
}

请注意，为了获得移位后的余数的第 32 位，我们查看之前移位的余数的第 31 位。

但也要注意，我们移入余数的 next_input_bit() 位实际上不会影响任何决策，直到 32 位之后。因此，这个过程的前 32 个周期非常无聊。此外，要将 CRC 添加到消息中，我们需要在末尾为其提供一个 32 位长的孔，因此我们必须在每个消息的末尾添加 32 个额外的周期来移入零。

这些细节导致了一个标准技巧：重新安排合并到 next_input_bit() 中，直到需要它的那一刻。然后可以预先计算前 32 个周期，并且可以完全跳过合并最终 32 个零位以为 CRC 腾出空间。这会将代码更改为

for (i = 0; i < input_bits; i++) {
        remainder ^= next_input_bit() << 31;
        multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
        remainder = (remainder << 1) ^ multiple;
}

通过此优化，小端代码特别简单

for (i = 0; i < input_bits; i++) {
        remainder ^= next_input_bit();
        multiple = (remainder & 1) ? CRCPOLY : 0;
        remainder = (remainder >> 1) ^ multiple;
}

余数多项式的最高有效系数存储在二进制“余数”变量的最低有效位中。字节序的其他细节已隐藏在 CRCPOLY（必须进行位反转）和 next_input_bit() 中。

只要 next_input_bit 以合理的顺序返回位，我们就不必等到最后一刻才合并其他位。我们可以一次做 8 位，而不是一次做 1 位

for (i = 0; i < input_bytes; i++) {
        remainder ^= next_input_byte() << 24;
        for (j = 0; j < 8; j++) {
                multiple = (remainder & 0x80000000) ? CRCPOLY : 0;
                remainder = (remainder << 1) ^ multiple;
        }
}

或者用小端序

for (i = 0; i < input_bytes; i++) {
        remainder ^= next_input_byte();
        for (j = 0; j < 8; j++) {
                multiple = (remainder & 1) ? CRCPOLY : 0;
                remainder = (remainder >> 1) ^ multiple;
        }
}

如果输入是 32 位的倍数，您甚至可以一次 XOR 一个 32 位字，并将内部循环计数增加到 32。

您还可以混合和匹配两种循环样式，例如一次对一个消息字节进行批量处理，并为末尾的任何非完整字节添加一次一位的处理。

为了减少条件分支的数量，软件通常使用一次一个字节的表格方法，由 Dilip V. Sarwate 推广，“通过表格查找计算循环冗余校验”，Comm. ACM v.31 no.8 (August 1998) p. 1008-1013。

在这里，我们不仅仅移位余数的一位来决定要减去的正确倍数，我们可以一次移位一个字节。这会产生一个 40 位（而不是 33 位）的中间余数，并且使用一个 256 项的查找表（由高 8 位索引）来找到要减去的多项式的正确倍数。

（表项只是给定单字节消息的 CRC-32。）

当空间更受限制时，可以使用较小的表格，例如两次 4 位移位，然后查找 16 项的表格。

使用这种技术一次处理超过 8 位是不切实际的，因为大于 256 项的表格会占用太多内存，更重要的是，会占用太多 L1 缓存。

为了获得更高的软件性能，可以使用“切片”技术。请参阅“使用 Intel Slicing-by-8 算法进行高辛烷值 CRC 生成”， ftp://download.intel.com/technology/comms/perfnet/download/slicing-by-8.pdf

这不会改变表格查找的次数，但会增加并行性。使用经典的 Sarwate 算法，必须先完成每个表格查找，然后才能计算下一个查找的索引。

“切片 2”技术将一次移位余数 16 位，从而产生一个 48 位的中间余数。而不是在 65536 项的单个表格中查找，而是在两个不同的 256 项表格中查找两个高字节。每个表格都包含取消相应字节所需的余数。这些表格是不同的，因为要取消的多项式是不同的。一个具有从 x^32 到 x^39 的非零系数，而另一个从 x^40 到 x^47。

由于现代处理器可以处理许多并行内存操作，因此这比单个表格查找花费的时间长不了多少，因此执行速度几乎是基本 Sarwate 算法的两倍。

可以使用 4 个 256 项的表格将其扩展到“切片 4”。每一步，获取 32 位数据，与 CRC 进行异或运算，并将结果分解为字节并在表格中查找。由于 32 位移位使中间余数的低位为零，因此最终 CRC 只是 4 个表格查找的异或。

但这仍然强制执行顺序执行：直到前一组的 4 个表格查找全部完成后，才能开始第二组表格查找。

为了最大限度地利用处理器，“切片 8”并行执行 8 次查找。每一步，32 位 CRC 移位 64 位，并与 64 位输入数据进行异或运算。需要注意的是，这 8 个字节中的 4 个只是输入数据的副本；它们根本不依赖于先前的 CRC。因此，这 4 个表格查找可以立即开始，而无需等待先前的循环迭代。

通过始终保持 4 个加载在飞行中，可以使现代超标量处理器保持忙碌并充分利用其 L1 缓存。

关于现实世界中 CRC 实现的另外两个细节

通常，将零位附加到已经是多项式倍数的消息会产生该多项式的更大倍数。因此，基本 CRC 将无法检测到附加的零位（或字节）。为了使 CRC 能够检测到这种情况，通常在附加 CRC 之前将其反转。这使得消息 + crc 的余数不是零，而是一些固定的非零值。（反转模式的 CRC，0xffffffff。）

同样的问题适用于附加到消息之前的零位，并且使用了类似的解决方案。不是以 0 的余数开始 CRC 计算，而是使用全 1 的初始余数。只要您以相同的方式开始解码，就不会产生任何差异。

Linux 内核

目录

本页

CRC计算简明教程¶