当输入的比特数为奇数（而不是字节）时，生成CRC8 / 16的最佳方法？ C或Python [英] Best way to generate CRC8/16 when input is odd number of BITS (not byte)? C or Python

问题描述

因此，我坚持使用一种协议，该协议会在奇数位上添加CRC8 / CRC16。 （即不能被8整除）在软件中为其生成CRC的最佳方法是什么？

So I'm stuck with a protocol that adds a CRC8/CRC16 over odd number of bits. (ie. it's not divisible by 8) What's the best method to generate the CRC for it in software?

有很多使用表的CRC算法，但它们每字节查找。当然，一次只做一次是自动防故障的。但是有更好的方法吗？也许主要是通过查表来完成它，然后一次完成它呢？

There are plenty of CRC algorithm that uses table, but they are lookup per byte. Of course, there's the "fail-safe" of doing it one bit at a time. But is there a better approach? Perhaps doing it mostly by table lookup and then finish it doing a bit at a time?

我目前在python中使用位数组来处理此问题。但是用C解决方案也可以。谢谢！

I'm currently using a bitarray in python to handle this. But solution in C would also work. Thanks!

编辑：请注意，我正在与现有的硬件接口，这些硬件在奇数位数上计算CRC。 （对于硬件而言，这很容易，因为它们一次只使用LFSR--1位！）因此，尽管使用已知模式进行填充可以进行完整性检查，但会破坏硬件兼容性。

Note that I'm interfacing with existing hardware that calc the CRC over the odd number of bits. (It's easy for the HW, since they just use a LFSR--1 bit at a time!) So while padding with known pattern would work for sake of integrity checking, it would break the hw compatibility.

推荐答案

填充为零的填充不应更改结果。计算CRC本质上是二进制长除法。不幸的是，这涉及拆分每个字节。

Padding with zeros at the front should not change the result. Computing the CRC is essentially binary long division. Unfortunately this involves splitting each byte. This is easy to with shift operators and bitwise or.

最后的零填充要容易得多，并且根据您计算CRC的原因，这是完全合理的事情去做。例如，如果您正在使用CRC进行完整性检查。

Zero padding at the end is, much easier, and depending on your reason for computing the CRC, a completely reasonable thing to do. For example, if you are using CRC for an integrity check.

编辑以我的示例为我的评论。如果您有11位11101110111并要计算CRC，请填充它们以获得00000111 01110111 = 0x777，请勿填充它们以获得0x7770，因为这将具有不同的CRC。

Edit Taking my example from my comment. If you have 11 bits 11101110111 and want to compute the CRC, pad them to get 00000111 01110111 = 0x777, do not pad them to get 0x7770 as this will have a different CRC.

之所以起作用，是因为CRC本质上是二进制长除法

The reason that this works is that CRC is essentially binary long division

                    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

以及类似的任意数量的前导零。

and similarly for any number of leading zeros.

请注意，除非您是一位精神科医生，希望从事野外工作，想成为一名，或者暗中想要见一眼，否则可能值得您跳到超级双重秘密试用期编辑

Note at this point, unless you are a psychiatrist looking for field work, want to become one, or secretly desire to need to see one, it may be worth your while to skip to the Super double secret probationary edit

进一步编辑由于问题更改

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

If you have a nontrivial initial vector, you can do the following. Say we want to compute the CRC-CCITT CRC of the above string with an initializer of FFFF. We pad the string to get 0x0FFF compute the CRC-CCIT with initializer 0 to get 0x0ECE, then compute the CRC-CCIT with initializer 0xFFFF of 0x0000 to get 0x1D0F, and xor them 0x0ECE xor 0x1D0F = 0x13C1.

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

The CRC of an arbitrary string of 0's and a nonzero initializer can be computed quickly if the polynomial is primitive (I think they all are), but it gets complicated and I do not have nearly enough time.

该技术的本质是我们可以将移位寄存器的状态视为多项式。如果我们用n个值对其进行初始化，则与将初始多项式视为 p（x）= x ^（n-1）+ x ^（n-2）... + x + 1 。计算 k 零字符串的CRC等效于找到 p（x）x ^ k mod CRC。通过反复平方和归约，很容易发现 x ^ k mod CRC。任何通过GF（2）进行多项式运算的库都应执行此操作。

The essence of the technique is that we can consider the state of the shift register as a polynomial. If we initialize it with n ones this is the same as considering the initial polynomial as p(x) = x^(n - 1) + x^(n - 2) ... + x + 1. Computing the CRC of a string of k zeros is equivalent to finding p(x) x^k mod CRC. x^k mod CRC is easily found by repeated squaring and reduction. Any library for polynomial arithmetic over GF(2) should do this.

甚至进一步编辑对于非零初始值设定项，这可能更有意义填充零，然后将初始化器更改为一个值，使得在读取| pad |之后移位寄存器包含FFFF的零（或您想要的值。可以预先计算），而您只需要存储16或32（即crc多项式中有多少位。

Even further Edit It probably makes more sense in the case of nonzero initializers to pad with zeros and change the initializer to a value such that after reading |pad| number of zeros the shift register contains FFFF (or whatever the value you wanted was. These can be precomputed, and you only need to store 16 or 32 of them (or howver many bits are in your crc polynomial.

例如，对于带有初始化程序0xFFFF和单个位0填充的CRC-CCIT，我们将要使用0xF7EF的初始化程序。可以通过使用以下公式找到x ^（-1）mod CRC来计算这些值：扩展的欧几里得算法，然后针对各种填充长度计算初始化程序* x ^（-k）mod CRC。再次，任何GF（2）polynomail软件包都应该使此操作变得容易。我使用了 NTL 过去，发现它非常灵活，但是在这里可能会显得过分杀人。即使对于32位crcs，令人难以置信的搜索也可能会发现初始化程序比您编写的速度更快

For example with CRC-CCIT with initializer 0xFFFF and a single bit 0 padding we will want to use an initializer of 0xF7EF. These can be computed by finding x^(-1) mod CRC using the extended euclidean algorithm and then computing initializer * x^(-k) mod CRC for the various padding lengths. Again any GF(2) polynomail package should make this easy. I have used NTL in the past and found it quite flexible, but it is probably overkill here. Even for 32 bit crcs exhjaustive search will probably find the initializers faster than you can write the code.

超级双重秘密试用编辑

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

Ok, Things are actually considerably simpler than I thought they were. The general idea above is correct, we want to pad the string with 0's at the front to extend the size to a multiple of 8, 16 or 32 depending on what our software implementation wants, and we want to change our initial vector to set our state to something that after reading the padding zeros will the LFSR will be set to the initial vector that we wanted. We certainly could use galois field arithmetic to do this, but there is an easier way: just run the LFSR backwards.

例如，如果我们要计算11位11位11101110111的CRC-CCITT（0xFFFF），则用5 0填充以得到00000111 01110111，然后返回LFSR向上扩展五个空格，以获得初始向量0xF060。 （我已经手工完成了计算，所以要小心）。
因此，如果以0xF060的IV启动LSFR（或软件实现）并在0x0fff上运行，则结果应与在原始11位上以IV 0xFFFF运行LFSR的结果相同。

For example if we want to compute the CRC-CCITT (0xFFFF) of the 11 bits 11 bits 11101110111 we pad them with 5 0's to get 00000111 01110111 and then back the LFSR up five spaces to get an initial vector of 0xF060. (I've done the computation by hand, so beware). So if you start an LSFR (or a software implementation) with IV of 0xF060 and run it on 0x0fff, you should get the same result as running an LFSR with IV 0xFFFF on the original 11 bits.

这篇关于当输入的比特数为奇数（而不是字节）时，生成CRC8 / 16的最佳方法？ C或Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！