¿La mejor manera de generar CRC8 / 16 cuando la entrada es un número impar de BITS (no byte)? C o Python

Así que me quedo con un protocolo que agrega un CRC8 / CRC16 en un número impar de bits. (es decir, no es divisible entre 8) ¿Cuál es el mejor método para generar el CRC para él en el software?

Hay muchos algoritmos CRC que usan tablas, pero son de búsqueda por byte. Por supuesto, está el “seguro a prueba de fallos” de hacerlo poco a poco. ¿Pero hay un mejor enfoque? ¿Quizás hacerlo principalmente por búsqueda en la mesa y luego terminarlo haciendo poco a poco?

Actualmente estoy usando un bitarray en python para manejar esto. Pero la solución en C también funcionaría. ¡Gracias!

EDITAR: tenga en cuenta que estoy interactuando con el hardware existente que calcula el CRC sobre el número impar de bits. (Es fácil para el HW, ya que solo usan un LFSR – ¡1 bit a la vez!) Por lo tanto, si bien el relleno con un patrón conocido funcionaría para verificar la integridad, rompería la compatibilidad de hw.

El relleno con ceros en la parte delantera no debe cambiar el resultado. Calcular la CRC es esencialmente una división larga binaria. Desafortunadamente esto implica dividir cada byte. Esto es fácil con los operadores de cambio y en modo bit o.

El relleno cero al final es, mucho más fácil, y dependiendo de su razón para calcular el CRC, es algo completamente razonable. Por ejemplo, si está utilizando CRC para una verificación de integridad.

Editar Tomando mi ejemplo de mi comentario. Si tiene 11 bits 11101110111 y desea calcular el CRC, rellénelos para obtener 00000111 01110111 = 0x777, no los rellene para obtener 0x7770 ya que esto tendrá un CRC diferente.

La razón por la que esto funciona es que CRC es esencialmente una división larga binaria

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 

Tiene exactamente el mismo resultado que

  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 

y de manera similar para cualquier número de ceros iniciales.

Tenga en cuenta que en este punto, a menos que sea un psiquiatra que esté buscando trabajo de campo, quiera convertirse en uno o desee secretamente querer verlo, puede valer la pena pasar por alto la edición probatoria de doble secreto.

Edición adicional debido a cambio de pregunta

Si tiene un vector inicial no trivial, puede hacer lo siguiente. Digamos que queremos calcular el CRC CRC-CCITT de la cadena anterior con un inicializador de FFFF. Rellenamos la cadena para obtener 0x0FFF calcular el CRC-CCIT con el inicializador 0 para obtener 0x0ECE, luego calcular el CRC-CCIT con el inicializador 0xFFFF de 0x0000 para obtener 0x1D0F, y xor ellos 0x0ECE xor 0x1D0F = 0x13C1.

El CRC de una cadena arbitraria de 0 y un inicializador distinto de cero se puede calcular rápidamente si el polinomio es primitivo (creo que todos lo son), pero se complica y no tengo el tiempo suficiente.

La esencia de la técnica es que podemos considerar el estado del registro de desplazamiento como un polinomio. Si lo inicializamos con n unos, es lo mismo que considerar el polinomio inicial como p (x) = x ^ (n – 1) + x ^ (n – 2) … + x + 1 . Calcular el CRC de una cadena de k ceros es equivalente a encontrar p (x) x ^ k mod CRC. x ^ k mod CRC se encuentra fácilmente mediante escuadrado y reducción repetidos. Cualquier biblioteca para la aritmética polinómica sobre GF (2) debe hacer esto.

Incluso más adelante Editar Es probable que tenga más sentido en el caso de inicializadores distintos de cero a rellenar con ceros y cambiar el inicializador a un valor tal que después de leer | pad | número de ceros el registro de desplazamiento contiene FFFF (o cualquiera que sea el valor que deseaba. Pueden precomputarse, y solo necesita almacenar 16 o 32 de ellos (o sin embargo, cuántos bits están en su polinomio CRC).

Por ejemplo, con CRC-CCIT con inicializador 0xFFFF y un solo relleno de bit 0, desearemos utilizar un inicializador de 0xF7EF. Se pueden calcular encontrando x ^ (- 1) mod CRC usando el algoritmo euclidiano extendido y luego calculando el inicializador * x ^ (- k) mod CRC para las diversas longitudes de relleno. De nuevo, cualquier paquete GF (2) polynomail debería hacer esto fácil. He usado NTL en el pasado y lo encontré bastante flexible, pero es probable que sea excesivo aquí. Incluso para las búsquedas de 32 bits en el navegador, los iniciadores probablemente encontrarán los inicializadores más rápido de lo que puede escribir el código.

Súper secreto doble edición de prueba

Ok, las cosas son en realidad considerablemente más simples de lo que pensaba. La idea general anterior es correcta, queremos rellenar la cadena con 0 en la parte delantera para extender el tamaño a un múltiplo de 8, 16 o 32, dependiendo de lo que quiera nuestra implementación de software, y queremos cambiar nuestro vector inicial para establecer nuestra Indique a algo que después de leer los ceros de relleno, el LFSR se establecerá en el vector inicial que queríamos. Ciertamente podríamos usar la aritmética de campo galois para hacer esto, pero hay una manera más fácil: simplemente ejecute el LFSR hacia atrás.

Por ejemplo, si queremos calcular el CRC-CCITT (0xFFFF) de los 11 bits 11 bits 11101110111 los rellenamos con 5 0 para obtener 00000111 01110111 y luego retroceder el LFSR cinco espacios para obtener un vector inicial de 0xF060. (He hecho el cálculo a mano, así que ten cuidado). Entonces, si inicia un LSFR (o una implementación de software) con IV de 0xF060 y lo ejecuta en 0x0fff, debería obtener el mismo resultado que ejecutando un LFSR con IV 0xFFFF en los 11 bits originales.