如何生成奇数个比特（而不是字节）的CRC8/16，使用C或Python的最佳方法？

Question

所以我一直坚持在奇数位上加一个CRC8/CRC16的协议。（即它不能被8整除）在软件中为它生成CRC的最佳方法是什么？在

有很多CRC算法使用表，但它们是按字节查找的。当然，一次只做一点是有“故障保险”的。但是有更好的方法吗？也许主要是通过查表来完成，然后一次完成一点？在

我目前正在python中使用bitarray来处理这个问题。但C语言中的解决方案也是可行的。谢谢！在

编辑：请注意，我正在与现有的硬件接口，它计算奇数位的CRC。（这对硬件来说很简单，因为他们只使用LFSR——一次1位！）因此，虽然使用已知模式填充可以进行完整性检查，但它会破坏硬件兼容性。在

Answer 1

在前面填充0不应该改变结果。计算CRC本质上是二进制长除法。不幸的是，这涉及到分割每个字节。使用移位运算符和按位or很容易实现。在

结尾处的零填充要容易得多，并且取决于计算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

结果与

^{pr2}$

对于任何数量的前导零也是类似的。在

注意在这一点上，除非你是一名正在寻找实地工作的精神病医生，想要成为一名医生，或是暗地里想去看一名医生，否则跳到超级双秘密试用编辑

由于问题更改而进一步编辑

如果有一个非平凡的初始向量，可以执行以下操作。假设我们要用FFFF的初始值设定项计算上述字符串的CRC-CCITT CRC。我们填充字符串得到0x0FFF用初始化器0计算CRC-CCIT得到0x0ECE，然后用初始化器0xFFFF为0x0000计算CRC-CCIT得到0x1D0F，并对它们进行异或0x0ECE xor 0x1D0F=0x13C1。在

如果多项式是原始的（我认为它们都是原始的），那么任意0字符串和非零初始值设定项的CRC可以很快计算出来，但是它变得很复杂，而且我几乎没有足够的时间。在

该技术的实质是我们可以把移位寄存器的状态看作一个多项式。如果我们用n个一初始化它，这与把初始多项式看作p（x）=x^（n-1）+x^（n-2）。。。+x+1。计算一个包含k零的字符串的CRC相当于找到p（x）x^kmod CRC。x^kmod CRC很容易通过重复的平方和约化找到。任何GF（2）上多项式运算的库都应该这样做。在

甚至进一步编辑对于非零初始值设定项，用零填充并将初始值设定项更改为一个值，以便在读取| pad |个零之后，移位寄存器包含FFFF（或您想要的任何值）。这些可以预先计算，你只需要存储其中的16或32个（或者不管你的crc多项式中有多少位）。在

例如，对于带有初始值设定项0xFFFF和单个位0填充的CRC-CCIT，我们希望使用0xF7EF的初始值设定项。这些可以通过使用扩展的欧几里德算法找到x^（-1）mod CRC，然后计算不同填充长度的初始值*x^（-k）mod CRC来计算。再次任何GF（2）多项式包应该使这容易。我以前用过NTL，发现它相当灵活，但在这里可能有点过头了。即使是对于32位的crcs exhjaustive搜索也可能会比编写代码更快地找到初始化器。在

超级双密试用编辑

好吧，事情其实比我想象的要简单得多。上面的基本思想是正确的，我们希望在字符串的前面加上0，以根据我们的软件实现的需要将大小扩展到8、16或32的倍数，我们想改变我们的初始向量来设置我们的状态，在读取填充零之后，LFSR将被设置为我们想要的初始向量。我们当然可以使用galois field算法来实现这一点，但有一种更简单的方法：只需反向运行LFSR。在

例如，如果我们要计算11位11位111011011111的CRC-CCITT（0xFFFF），我们用5 0填充它们，得到0000011101110111，然后将LFSR向上返回五个空格，以获得0xF060的初始向量。（我是手工计算的，小心点）。 因此，如果您使用0xF060的IV启动LSFR（或软件实现），并在0x0fff上运行它，那么您将获得与在原始11位上运行IV 0xFFFF的LFSR相同的结果。在