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 位的倍数，您甚至可以一次异或一个 32 位字，并将内部循环计数增加到 32。

您还可以混合和匹配两种循环样式，例如，一次处理消息的大部分，并为末尾的任何小数部分添加一次处理一位的处理。

为了减少条件分支的数量，软件通常使用 Dilip V. Sarwate 推广的逐字节表方法，“通过表查找计算循环冗余校验”，Comm. ACM v.31 no.8（1998 年 8 月）第 1008-1013 页。

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

（表条目只是给定的一字节消息的 CRC-32。）

当空间更受限制时，可以使用较小的表，例如，两个 4 位移位，然后在 16 条目的表中查找。

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

为了获得更高的软件性能，可以使用“切片”技术。请参阅“使用 Intel 切片-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 的余数不是零，而是一些固定的非零值。（反转模式 0xffffffff 的 CRC。）

同样的问题适用于附加到消息的零位，并使用类似的解决方案。不是以 0 的余数开始 CRC 计算，而是使用全 1 的初始余数。只要您在解码时以相同的方式开始，就不会有什么区别。

Linux 内核

目录

本页

CRC 计算简明教程¶