¿Cálculo de un CRC de 8 bits con el preprocesador C?

Question

Estoy escribiendo código para un pequeño microcontrolador de 8 bits con solo unos pocos bytes de RAM. Tiene un trabajo simple que es transmitir 7 palabras de 16 bits, luego el CRC de esas palabras. Los valores de las palabras se eligen en tiempo de compilación. El CRC específicamente es "resto de la división de palabra 0 a palabra 6 como número sin signo dividido por el polinomio x^8 + x² + x + 1 (valor inicial 0xFF)".

¿Es posible calcular el CRC de esos bytes en tiempo de compilación utilizando el preprocesador C?

#define CALC_CRC(a,b,c,d,e,f,g) /* what goes here? */ 

#define W0 0x6301 
#define W1 0x12AF 
#define W2 0x7753 
#define W3 0x0007 
#define W4 0x0007 
#define W5 0x5621 
#define W6 0x5422 
#define CRC CALC_CRC(W0, W1, W2, W3, W4, W5, W6) 

Answer 1

El algoritmo de suma de control más simple es la llamada de verificación de paridad longitudinal, que rompe los datos en "palabras" con un número n fijo de bits, y luego calcula el exclusivo o de todas esas palabras. El resultado se agrega al mensaje como una palabra adicional.

Para verificar la integridad de un mensaje, el receptor calcula la exclusiva o todas sus palabras, incluida la suma de comprobación; si el resultado no es una palabra con n ceros, el receptor sabe que ocurrió un error de transmisión.

(Souce: wiki)

En su ejemplo:

#define CALC_CRC(a,b,c,d,e,f) ((a)^(b)^(c)^(d)^(e)^(f)) 

Answer 2

responsabilidad: esto no es realmente una respuesta directa, sino más bien una serie de preguntas y sugerencias que son demasiado largos para un comentario.

Primera pregunta: ¿Tiene control sobre ambos extremos del protocolo, p. ¿Puedes elegir el algoritmo de suma de comprobación por medio de ti mismo o de un compañero de trabajo que controle el código en el otro extremo?

Si SÍ a la pregunta # 1:

Es necesario evaluar qué necesita la suma de comprobación, lo que la suma de comprobación es apropiada, y las consecuencias de la recepción de un mensaje dañado con una suma de comprobación válida (que toma en tanto el que & por qué).

¿Cuál es su medio de transmisión, protocolo, tasa de bits, etc.? ¿Estás esperando/observando errores de bits? Entonces, por ejemplo, con SPI o I2C de un chip a otro en la misma placa, si tiene errores de bit, es probable que los ingenieros de HW tengan una falla o que necesite reducir la velocidad del reloj, o ambos. Una suma de comprobación no puede doler, pero realmente no debería ser necesaria. Por otro lado, con una señal de infrarrojos en un entorno ruidoso, tendrás una probabilidad de error mucho mayor.

Las consecuencias de un mensaje incorrecto siempre son la pregunta más importante aquí. Entonces, si está escribiendo el controlador para el termómetro digital de sala y enviando un mensaje para actualizar la pantalla 10 veces por segundo, un valor incorrecto cada 1000 mensajes tiene muy poco o ningún daño real. Ninguna suma de comprobación o una suma de comprobación débil debería estar bien.

Si estos 6 bytes disparan un misil, establecen la posición de un bisturí robótico, o causan la transferencia de dinero, es mejor que esté seguro de que tiene la suma de comprobación correcta, e incluso puede buscar un hash criptográfico (que puede requerir más memoria RAM de la que tiene).

Para las cosas intermedias, con notable detrimento en el rendimiento/satisfacción con el producto, pero sin daños reales, es su llamada.Por ejemplo, un televisor que ocasionalmente cambie el volumen en lugar del canal podría molestar a los clientes: más que simplemente dejar caer el comando si un buen CRC detecta un error, pero si usted está en el negocio de hacer dinero barato/Televisores imbatibles que podrían estar bien si lleva el producto al mercado más rápido.

¿Qué suma de verificación necesita?

Si uno o ambos extremos tienen compatibilidad HW para una suma de comprobación integrada en el periférico (bastante común en SPI, por ejemplo), esa podría ser una buena elección. Entonces se vuelve más o menos libre de calcular.

Un LRC, como lo sugiere la respuesta de vulkanino, es el algoritmo más simple.

Wikipedia tiene algo de información decente sobre cómo/por qué elegir un polinomio si realmente necesita un CRC: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

Si NO a la pregunta # 1:

Lo CRC algoritmo/polinomio hace el otro extremo requiere? Eso es lo que tiene que hacer, pero decirnos podría brindarle una respuesta mejor/más completa.

Reflexiones sobre la aplicación:

La mayoría de los algoritmos son bastante ligero en términos de RAM/registros, que sólo requiere un par de bytes adicionales. En general, una función dará como resultado un código mejor, más limpio, más fácil de leer y fácil de depurar.

Debería pensar en la macro solución como un truco de optimización, y como todos los trucos de optimización, saltar a ellos temprano puede ser una pérdida de tiempo de desarrollo y una causa de más problemas de lo que vale.

Usando una macro también tiene algunas implicaciones extrañas que no haya considerado todavía:
usted es consciente de que el preprocesador solo puede hacer el cálculo si todos los bytes en un mensaje se fijan en tiempo de compilación, ¿verdad? Si tiene una variable allí, el compilador debe generar código. Sin una función, ese código se insertará cada vez que se use (sí, eso podría significar mucho uso de la ROM). Si todos los bytes son variables, ese código podría ser peor que simplemente escribir la función en C. O con un buen compilador, podría ser mejor. Difícil de decir con certeza. Por otro lado, si un número diferente de bytes es variable dependiendo del mensaje que se envía, puede terminar con varias versiones del código, cada una optimizada para ese uso particular.

Answer 3

Es posible diseñar una macro que realizará un cálculo de CRC en tiempo de compilación. Algo como

 
// Choosing names to be short and hopefully unique. 
#define cZX((n),b,v) (((n) & (1 << b)) ? v : 0) 
#define cZY((n),b, w,x,y,z) (cZX((n),b,w)^CzX((n),b+1,x)^CzX((n),b+2,y)^cZX((n),b+3,z)) 
#define CRC(n) (cZY((n),0,cZ0,cZ1,cZ2,cZ3)^cZY((n),4,cZ4,cZ5,cZ6,cZ7)) 

probablemente debería funcionar, y será muy eficiente si (n) se puede evaluar como una constante de tiempo de compilación; simplemente evaluará a una constante en sí misma. Por otro lado, si n es una expresión, esa expresión terminará siendo recalculada ocho veces. Incluso si n es una variable simple, es probable que el código resultante sea significativamente más grande que el modo más rápido de escribirlo que no esté basado en tablas, y puede ser más lento que la forma más compacta de escribirlo.

Por cierto, una cosa que realmente me gustaría ver en el estándar C y C++ sería un medio de especificar sobrecargas que se usarían para funciones declaradas en línea solo si determinados parámetros pudieran evaluarse como constantes de tiempo de compilación.La semántica sería tal que no habría "garantía" de que dicha sobrecarga se usaría en todos los casos en que un compilador pudiera determinar un valor, pero habría una garantía de que (1) no se usaría dicha sobrecarga. en cualquier caso donde un parámetro "compile-time-const" tendría que ser evaluado en tiempo de ejecución, y (2) cualquier parámetro que se considere una constante en una tal sobrecarga se considerará una constante en cualquier función invocada desde él. Hay muchos casos en que una función podría escribirse para evaluar una constante en tiempo de compilación si su parámetro es constante, pero la evaluación en tiempo de ejecución sería absolutamente horrible. Por ejemplo:

 
#define bit_reverse_byte(n) ((((n) & 128)>>7)|(((n) & 64)>>5)|(((n) & 32)>>3)|(((n) & 16)>>1)| 
    (((n) & 8)<<1)|(((n) & 4)<<3)|(((n) & 2)<<5)|(((n) & 1)<<7)) 
#define bit_reverse_word(n) (bit_reverse_byte((n) >> 8) | (bit_reverse_byte(n) << 8)) 

Un simple representación de una función de bits inversa no en bucle de un solo byte en C en el PIC sería de alrededor de 17-19 instrucciones de ciclo único; una palabra bit-reverse sería 34, o aproximadamente 10 más una función byte-reverse (que se ejecutaría dos veces). El código de ensamblaje óptimo sería aproximadamente 15 instrucciones de ciclo único para byte inverso o 17 para word-reverse. Calcular bit_reverse_byte(b) para una variable de byte b tomaría muchas docenas de instrucciones por un total de muchas docenas de ciclos. La computación bit_reverse_word( w ) for some 16-bit word w` probablemente tomaría cientos de instrucciones y tardaría cientos o miles de ciclos en ejecutarse. Sería realmente agradable si se pudiera marcar una función para expandir en línea usando algo como la formulación anterior en el escenario en el que se expandiría a un total de cuatro instrucciones (básicamente solo cargando el resultado) pero usaría una llamada de función en escenarios en línea la expansión sería atroz.