CRC 计算简明教程¶
CRC 是一个长除法余数。你将 CRC 添加到消息中，整个对象（消息+CRC）是给定 CRC 多项式的倍数。要检查 CRC，你可以检查 CRC 是否与重新计算的值匹配，或者你可以检查对消息+CRC 计算出的余数是否为 0。后一种方法被许多硬件实现所采用，这也是为什么许多协议将帧结束标志放在 CRC 之后的原因。
这其实和你上学时学的长除法是一样的，只不过
我们使用的是二进制，所以数字只有 0 和 1，并且
当除多项式时，没有进位。我们不用做加减法，只需进行异或运算。因此，我们往往会对加法和减法之间的区别表现得比较模糊。
和所有除法一样，余数总是小于除数。为了生成 32 位 CRC，除数实际上是一个 33 位的 CRC 多项式。由于它长达 33 位，第 32 位始终为 1，因此通常在写成十六进制时会省略最高位。（如果你熟悉 IEEE 754 浮点数格式，这是同一个道理。）
请注意，CRC 是在一串比特（bit）上计算的，因此你必须确定每个字节内比特的大小端。为了获得最佳的检错特性，这应该与它们实际发送的顺序相对应。例如，标准 RS-232 串口是小端的；最高位（sometimes used for parity，有时用于奇偶校验）最后发送。并且在向消息追加 CRC 字时，你也应该以正确的顺序进行，以匹配大小端。
就像普通除法一样，你每次处理一个数字（比特）。在除法的每一步中，你从被除数中多取一个数字（比特）并将其追加到当前余数后面。然后你找出除数的适当倍数来减去，以使余数回到范围内。在二进制中，这很简单——它只能是 0 或 1，为了让异或抵消，它刚好是余数第 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;
}
余数多项式的最高次系数存储在二进制“remainder”（余数）变量的最低有效位中。大小端的其他细节已被隐藏在 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 推广，参见其论文：“Computation of Cyclic Redundancy Checks via Table Look-Up”, Comm. ACM v.31 no.8 (August 1988) p. 1008-1013。
在这里，我们不是只移位余数的一个比特来决定要减去的正确倍数，而是可以一次移位一个字节。这会产生一个 40 位（而不是 33 位）的中间余数，并且通过由高 8 位进行索引的 256 项查找表来找到要减去的多项式的正确倍数。
（表项就是给定单字节消息的 CRC-32。）
当空间受限时，可以使用更小的表，例如两次 4 位移位，接着在一个 16 项的表中进行查找。
使用这种技术一次处理远多于 8 位的数据是不切实际的，因为大于 256 项的表会占用太多内存，更重要的是，会占用太多 L1 缓存。
为了获得更高的软件性能，可以使用“切片”（slicing）技术。参见“High Octane CRC Generation with the Intel Slicing-by-8 Algorithm”, ftp://download.intel.com/technology/comms/perfnet/download/slicing-by-8.pdf
这并没有改变查表的次数，但增加了并行性。在经典的 Sarwate 算法中，必须先完成当前查表，然后才能计算下一个查表的索引。
“按 2 切片”（slicing by 2）技术会一次移位余数 16 位，产生一个 48 位的中间余数。与其在一个 65536 项的表中进行单次查找，不如在两个不同的 256 项表中分别查找两个高字节。每个表包含抵消相应字节所需的余数。这些表之所以不同，是因为要抵消的多项式不同。其中一个具有从 x^32 到 x^39 的非零系数，而另一个从 x^40 到 x^47。
由于现代处理器可以处理许多并行的内存操作，这几乎不比单次查表花更多时间，因此其性能几乎是基本 Sarwate 算法的两倍。
这可以扩展为使用 4 个 256 项表的“按 4 切片”（slicing by 4）。在每一步中，获取 32 位数据，与 CRC 进行异或，然后将结果拆分为字节并在表中进行查找。因为 32 位移位使得中间余数的低阶位为零，所以最终的 CRC 只是这 4 次查表结果的异或值。
但这仍然强制执行顺序执行：在上一组的 4 次查表全部完成之前，第二组的查表无法开始。因此，处理器的加载/存储单元有时会处于空闲状态。
为了最大程度地利用处理器，“按 8 切片”（slicing by 8）并行执行 8 次查表。在每一步中，32 位 CRC 被移位 64 位并与 64 位输入数据进行异或。需要注意的是，这 8 个字节中的 4 个字节只是输入数据的副本；它们根本不依赖于先前的 CRC。因此，这 4 次查表可以立即开始，而不必等待上一次循环迭代完成。
通过始终保持 4 个加载操作处于运行（并行）状态，现代超标量处理器可以保持忙碌状态并充分利用其 L1 缓存。
关于现实世界中 CRC 实现的另外两个细节
通常，向已经是多项式倍数的消息追加零比特会产生该多项式的一个更大的倍数。因此，基本的 CRC 无法检测追加的零比特（或字节）。为了使 CRC 能够检测到这种情况，通常在追加 CRC 之前对其进行按位取反。这使得“消息+crc”的余数不再是零，而是一个固定的非零值。（即取反模式的 CRC，0xffffffff。）
同样的问题也适用于在消息前预置（prepend）零比特的情况，并且使用了类似的解决方案。我们不以 0 作为余数开始 CRC 计算，而是使用全 1 作为初始余数。只要你在解码时以相同的方式开始，结果就不会有影响。