在输入为奇数位（非字节）时生成CRC8/16的最佳方法？C或Python

Question

我现在遇到一个问题，就是有一个协议需要对奇数位的二进制数据计算CRC8或CRC16校验码。也就是说，这些位数不能被8整除。我想知道在软件中生成这个CRC的最佳方法是什么？

有很多CRC算法是使用查找表的，但它们通常是按字节查找的。当然，也可以选择逐位计算，这种方法比较保险。但是有没有更好的办法呢？也许可以大部分使用查找表，然后最后再逐位处理？

目前我在用Python的位数组来处理这个问题。不过，如果有C语言的解决方案也可以。谢谢！

补充说明：我是在和现有的硬件进行交互，这些硬件是对奇数位的数据计算CRC的。（对硬件来说，这很简单，因为它们只需使用LFSR——逐位处理！）所以虽然用已知的模式进行填充可以保证完整性检查，但这样会影响与硬件的兼容性。

Answer 1

在前面加零填充不应该改变结果。计算CRC（循环冗余校验）本质上就像二进制的长除法。不幸的是，这涉及到将每个字节拆分开来。用位移操作符和按位或运算来处理这个问题是比较简单的。

在后面加零填充就简单多了，具体做法取决于你计算CRC的目的，这样做是完全合理的。例如，如果你是为了检查数据的完整性而使用CRC。

编辑 以我评论中的例子为例。如果你有11位的二进制数11101110111，想要计算CRC，可以填充成00000111 01110111 = 0x777，但不要填充成0x7770，因为这样会得到不同的CRC。

之所以这样做是因为CRC本质上就是二进制的长除法。

                    1 0 1 = 5
            -------------
1 0 0 1 1 / 1 1 0 1 1 0 1
            1 0 0 1 1 | |
            --------- | |
              1 0 0 0 0 |
              0 0 0 0 0 |
              --------- |
              1 0 0 0 0 1
                1 0 0 1 1
                ---------
                  1 1 1 0 = 14 = remainder

和下面这个结果完全一样：

                      1 0 1 = 5
            ---------------
1 0 0 1 1 / 0 1 1 0 1 1 0 1
              1 0 0 1 1 | |
              --------- | |
                1 0 0 0 0 |
                0 0 0 0 0 |
                --------- |
                1 0 0 0 0 1
                  1 0 0 1 1
                  ---------
                    1 1 1 0 = 14 = remainder

对于任何数量的前导零也是如此。

注意 在这一点上，除非你是个心理医生想找工作，或者想成为心理医生，或者秘密希望自己需要看心理医生，否则跳到超级双重秘密试用编辑可能更值得。

由于问题变化的进一步编辑

如果你有一个非平凡的初始向量，可以这样做。假设我们想计算上面字符串的CRC-CCITT，初始值为FFFF。我们填充字符串得到0x0FFF，计算CRC-CCITT，初始值为0，得到0x0ECE，然后用初始值0xFFFF计算0x0000的CRC-CCITT，得到0x1D0F，最后将它们异或，0x0ECE异或0x1D0F = 0x13C1。

对于任意的0字符串和非零初始值，如果多项式是原始的（我想它们都是），可以快速计算CRC，但这会变得复杂，我没有足够的时间来详细说明。

这个技术的本质是我们可以把移位寄存器的状态看作一个多项式。如果我们用n个1来初始化，这就相当于把初始多项式看作p(x) = x^(n - 1) + x^(n - 2) ... + x + 1。计算一串k个零的CRC相当于找到p(x) x^k对CRC取模。x^k对CRC取模可以通过重复平方和约简轻松找到。任何支持GF(2)的多项式运算库都能做到这一点。

进一步编辑 在非零初始值的情况下，可能更合理的是用零填充，并将初始值改为一个值，这样在读取|pad|个零后，移位寄存器就会包含FFFF（或你想要的值）。这些可以预先计算，你只需要存储16或32个（或者根据你的CRC多项式的位数）。

例如，对于CRC-CCITT，初始值为0xFFFF，填充一个0位，我们希望使用的初始值是0xF7EF。这些可以通过使用扩展欧几里得算法找到x^(-1)对CRC取模，然后计算初始值 * x^(-k)对CRC取模来得到不同的填充长度。再次强调，任何GF(2)的多项式库都应该能轻松实现。我过去使用过NTL，觉得它相当灵活，但在这里可能有点过于复杂。即使对于32位的CRC，穷举搜索可能比你写代码的速度更快找到初始值。

超级双重秘密试用编辑

好的，事情其实比我想的要简单得多。上面的总体思路是正确的，我们想在前面加0来填充，使大小扩展到8、16或32的倍数，这取决于我们的软件实现需求，并且我们想改变初始向量，使得在读取填充的零后，LFSR（线性反馈移位寄存器）会设置为我们想要的初始向量。我们当然可以使用伽罗华域算术来做到这一点，但有更简单的方法：直接反向运行LFSR。

例如，如果我们想计算11位二进制数11101110111的CRC-CCITT（0xFFFF），我们在后面加5个0，得到00000111 01110111，然后将LFSR向后移动五位，得到初始向量0xF060。（我已经手动计算过，所以要小心）。所以如果你用初始值0xF060启动LFSR（或软件实现），然后在0x0FFF上运行，你应该得到和用初始值0xFFFF在原始11位上运行相同的结果。