Best way to generate CRC8 / 16 when entering an odd number of BITS (not bytes)? C or Python

Question

So, I'm stuck in a protocol that adds CRC8 / CRC16 over an odd number of bits. (i.e. it is not divisible by 8) What is the best way to generate CRC for it in software?

There are many CRC algorithms that use a table, but they look for every byte. Of course, there "fault tolerant" does it one bit at a time. But is there a better approach? Perhaps this is done mainly by searching the table and then completing it a little bit?

I am currently using bitarray in python for this. But a solution in C will also work. Thank!

EDIT: Please note that I am interacting with existing equipment that calculates CRC from an odd number of bits. (This is easy for HW, as they just use LFSR - 1 bit at a time!) Thus, while populating with a known pattern will work for integrity checking, it will break hw compatibility.

Answer 1

Filling with zeros in the front should not change the result. Calculation of CRC is essentially a binary long division. Unfortunately, this is due to the splitting of each byte. It is easy with shift operators and bitwise 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

,

                      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 CRC-CCITT FFFF. , 0x0FFF CRC-CCIT 0, 0x0ECE, CRC-CCIT 0xFFFF 0x0000, 0x1D0F, xor 0x0ECE xor 0x1D0F = 0x13C1.

CRC 0 , ( , ), , .

, . 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.

, CRC-CCIT 0xFFFF 0 0xF7EF. x ^ (- 1) mod CRC , * x ^ (- k) mod CRC . GF (2) . NTL , , , , . 32- crcs exhjaustive search, , , .

, , . , , , , 0 , 8, 16 32 , , , -, LFSR , . , galois, : LFSR .

, CRC-CCITT (0xFFFF) 11 11 11101110111, 5 0, 00000111 01110111, LFSR , 0xF060. ( , ). , LSFR ( ) IV 0xF060 0x0fff, , LFSR IV 0xFFFF 11 .