代码之家 › 专栏 › 技术社区 › fseto

当输入为奇数位(非字节)时生成CRC8/16的最佳方法?C或Python

algorithm c python

fseto · 技术社区 · 14 年前

所以我坚持使用一个在奇数位上添加CRC8/CRC16的协议。(即,它不能被8整除)在软件中为它生成CRC的最佳方法是什么?

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

我目前正在使用Python中的位数组来处理这个问题。但C语言的解决方案也会起作用。谢谢!

编辑:请注意,我正在与现有的硬件接口,这些硬件通过奇数位计算CRC。(对于硬件来说很容易,因为他们只使用LFSR——一次1位!)因此,虽然使用已知模式填充可以工作以进行完整性检查,但它会破坏硬件兼容性。

1 回复 | 直到 14 年前

deinst 14 年前

前面用零填充不应更改结果。计算CRC本质上是二进制长除法。不幸的是,这涉及到拆分每个字节。这很容易使用移位运算符和按位或。

末尾的零填充更加容易,并且根据计算CRC的原因,这是一个完全合理的操作。例如,如果您使用CRC进行完整性检查。

编辑以我的评论为例。如果您有11个位1110110111,并且想要计算CRC,请将其填充以获得00000111 0110111=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

同样地,对于任何前导零的数目。

注释在这一点上,除非你是一个正在寻找实地工作的精神病学家,想要成为一个,或者暗地里想要去看一个,否则你可能值得一段时间跳到 超级双秘密试用编辑

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

如果有一个非平凡的初始向量,可以执行以下操作。假设我们想用ffff的初始值计算上面字符串的crc-ccitt crc。我们填充字符串得到0x0fff,用初始值为0的crc-ccit计算得到0x0ece,然后用初始值为0x0000的0xffff计算crc-ccit,得到0x1d0f,然后xor它们0x0ece xor 0x1d0f=0x13c1。

如果多项式是基元的(我认为它们都是基元的),则可以快速计算任意0和非零初始值设定项字符串的CRC,但它会变得复杂,而且我没有足够的时间。

这种技术的本质是我们可以把移位寄存器的状态看作一个多项式。如果我们用n个来初始化它,这与考虑初始多项式 p(x)=x^(n-1)+x^(n-2)……+x+ 1 . 计算字符串的CRC K 零等于求 P(x)x^ k MOD CRC X^ K mod crc很容易通过反复的平方和约简找到。对于gf(2)上的多项式算术,任何库都应该这样做。

更进一步的编辑 在非零初始值设定项的情况下,用零填充并将初始值设定项更改为一个值,这样在读取pad零个数后,移位寄存器包含ffff(或您想要的值)。这些可以预先计算,您只需要存储其中的16或32位(或者CRC多项式中有多少位)。

例如,对于初始值为0xffff的CRC-CCIT和单个位0填充,我们将希望使用初始值为0xf7ef。这些可以通过使用扩展欧几里得算法找到x^(-1)mod crc,然后计算不同填充长度的初始值设定项*x^(-k)mod crc来计算。同样,任何gf(2)聚诺麦包装都应该使这变得容易。我已经用过 NTL 在过去,发现它很灵活,但在这里可能是多余的。即使对于32位的CRC,鼓励性搜索也可能比您编写代码更快地找到初始值设定项。

超级双秘密试用编辑

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

例如,如果我们要计算11位11位1110110111的crc-ccitt(0xffff),我们用5 0填充它们以得到00000111 0110111,然后将lfsr备份到5个空格以得到初始向量0xf060。(我已经手工计算过了,所以要小心)。因此,如果使用iv为0xf060启动lsfr(或软件实现),并在0x0fff上运行它,那么应该得到与在原始11位上使用iv 0xffff运行lfsr相同的结果。