Archivo adjunto con las rutinas al final del post, para lenguajes C y ASM
Debido a la cantidad de gente que ha estado consultandome por privado y al mail cómo realizar un CRC para diversos dispositivos(como los iButtons) me decidí a realizar las rutinas para calcular los 3 CRC más comunes: 8,16 y 32.
Entiendo que muchos hayan encontrado difícil entender o lograr conseguir un algoritmo que funcione según sus necesidades, ya que en la web el CRC no está muchas veces debidamente explicado. Tampoco es mi idea aclarar ésto. Si bien podría explicar básicamente de qué se trata sólo estaría hablando más de lo mísmo. Googlen para eso. No voy a explicar el por qué éstos algoritmos que publico a continuación funcionan.
La explicación no es sencilla si no se poseen conocimientos avanzados de sistema binario, instrucciones de uC PIC y cálculo matemático. Si me parece pertinente y necesario en el futuro lo explicaré con gusto.Sin embargo, sí voy a explicar algo que trastorna a muchos que es cómo obtener el polinomio que se utiliza en el algorítmo basandose en el polinomio dado.
¿Listos? ¡Vamos!
Para realizar el cálculo del CRC de una determinada cantidad de bytes, primero hay ciertas convenciones que debemos averiguar(en caso que estemos trabajando con un CRC impuesto) o debemos establecer(en caso que nosotros realicemos nuestro CRC propio y personal).
el algoritmo de un CRC tiene 4 variables básicas de entrada que necesitamos para determinar su correcto cálculo:
un dato de entrada(value), que es el byte(en mis ejemplos son siempre de 8 bits de longitud. Para más bits hay que modificar mis algoritmos) del cual vamos a calcular su CRC;
un polinomio: que es el divisor de "value", y requiere de ciertos conocimientos para ser elegido adecuadamente. Exísten varios polinomios populares que son los más utilizados;
un valor entrada: es un valor(de 8, 16 o 32 bits) con el cual se realiza una XOR entre el mísmo y "value" apenas comienza el cálculo del CRC;
un valor salida: es un valor(de 8, 16 o 32 bits) con el cual se realiza una XOR entre el mísmo y "value" al final del cálculo del CRC;
El dato obviamente es el djavascript:ChangeEditor(5)ividendo y es necesario, el polinomio también lo es. Los valores de entrada y salida pueden ser usados como puede que no.Eso depende del método empleado.
Si no utilizan valor de salida y/o valor de entrada, recuerden poner su/s byte/s a cero antes de realizar el cálculo del CRC.Caso contrario el CRC les va a dar...MAL(99% probable)
Por ejemplo: MAXIM en su DOW CRC (http://pdfserv.maxim-ic.com/en/an/AN27.pdf) utiliza un valor de entrada, pero no de salida. Averigüen bien lo siguiente:
¿Qué polinomio utiliza?
¿Se utiliza una variable de entrada?
¿Se utiliza una variable de salida?
Una vez averiguados esos datos, procederemos a ver cúal es el CRC que debemos usar. A este dato nos los da el Polinomio. el CRC que deberemos usar será el grado del polinomio -1.
Ejemplo:
P(x) = x^{16} + x^{15} + x^2 + 1
El grado del polinomio es 16. Por lo que el CRC deberá ser de GRADO(P(x)) = 16. Usaremos el algoritmo de CRC16.
Acá viene una parte misteriosa del asunto. No he encontrado web alguna que hable realmente de cómo calcular el valor de la variable polinomio partiendo de su función polinómica.
Muchos me han consultado cómo hago para calcularlo. Si comprenden bien el funcionamiento binario del cálculo del CRC, podrán apreciar que se calcula de la siguiente manera:
Utilicemos el polinomio de más arriba:
P(x) = x^{16} + x^{15} + x^2 + 1
Pasos:
1)Transformar cada término del polinomio en su equivalente binario. Realizando ésto nos queda:
b11000000000000101
Para llegar a este valor, lo que hice sencillamente ha sido:
P(2) = 2^{16} + 2^{15} + 2^2 + 1=98309= b11000000000000101
El número 2 es el utilizado para el valor de x, porque estamos utilizando sistema binario(2 elementos).
2) Eliminar el bit de mayor peso,quedandonos ahora:
b1000000000000101
3) Espejar el valor binario, quedandonos:
b1010000000000001
Listo, tenemos nuestro valor polinómico para usar en el algoritmo. Lo pasamos a Hexadecimal si queremos, para que sea más legible:
b1010000000000001=10100000 00000001=1010 0000 0000 0001=A001=0xA001
Entonces, utilizaremos el valor 0xA001 en nuestra variable polinomio
Hagamos un ejemplo con un CRC8 popular, el DOW CRC8 usado por MAXIM en los IButtons:
Revisando la AN27 de Maxim, veremos que su polinomio es:
P(x) =x^8 + x^5 + x^4+ 1
Respetando los pasos que comenté haremos entonces:
1) Calcular el valor del polinimo con x=2 y pasar el resultado a binario:
P(2)=2^8 + 2^5 + 2^4 + 1=305= b100110001
2)Quitarle el bit de mayor peso:
b00110001
3)Espejarlo:
b10001100=1000 1100=0x8C
Listo. Tenemos nuestro polinomio. Ahora si leemos en la AN27, veremos que este CRC en particular utiliza un valor de entrada pero no de salida.
El valor de entrada para el primer byte del cálculo de una cadena de bytes es 0x00. Los posteriores valores corresponden al valor del CRC calculado para el byte previo.
A ver si puedo ilustrar bien esto. Supongamos que quiero calcular el CRC de la siguiente cadena de bytes: 0x55,0x34,0x24,0x11,0x01
Para calcularlo debería ir sometiendo byte per byte al CRC,pero teniendo en cuenta que la variable de entrada de un byte es el CRC calculado previo.
paso por paso:
CRC1 = calcular CRC8 con: value =0x55 poly =0x8C enter_value=0x00 y exit_value=0x00
CRC2 = calcular CRC8 con: value =0x34 poly =0x8C enter_value=CRC1 y exit_value=0x00
CRC3 = calcular CRC8 con: value =0x24 poly =0x8C enter_value=CRC2 y exit_value=0x00
CRC4 = calcular CRC8 con: value =0x11 poly =0x8C enter_value=CRC3 y exit_value=0x00
CRCF = calcular CRC8 con: value =0x01 poly =0x8C enter_value=CRC4 y exit_value=0x00
El CRC Final(CRCF) será el CRC buscado. Como verán, en este CRC se realiza una XOR al inicio del cálculo entre el CRC previo y el dato actual. Esto es debido a que mejora la diversificación de distintos CRC.
Espero que les haya servido la explicación. A continuación adjunto los archivos con los algorítmos correspondientes. Éxitos en su comprobación de datos.
BrunoF.
Actualización:
Corregí errores con el grado del polinomio de la explicación. Perdón por el error.
Agrego al archivo adjunto las rutinas para el cálculo de CRC5 para CCS y assmebly, así también como la de CRC24 para lenguaje assembly(gracias MigSantiago por mencionar la CRC5 del USB la cual había olvidado);
Menciono los CRC más comunes que pueden toparse al trabajar con uCs(posteen si saben de otros y los vamos agregando!):
CRC5:
USB: polinomio: x^5+x^2+1
(0x14)
CRC7:
MMC-SD: polinomio: x^7+x^3+1
(0x48)
CRC8:
iButton: polinomio: x^8+x^5+x^4+1
(0x8C)
CRC16:
USB: polinomio: x^{16}+x^{15}+x^2+1
(0xA001)
iButton: polinomio: x^{16}+x^{15}+x^2+1
(0xA001)
Actualización:
Agregado CRC7...
Saludos.
Buenas! Estoy tratando de entender como calcular el CRC del protocolo DNP3 y me está ganando :8} Paso a explicar como se calcula así me dan una mano de como aplicar el código desarrollado por Bruno si es aplicable :?
El polinomio que se utiliza es:
p(x)=x^16+x^13+x^12+x^11+x^10+x^8+x^6+x^5+x^2+1
y esto equivale a 10011110101100101. Aplicando lo descripto por Bruno en el primer post se llega a que poly=0xA6BC.
Según las especificaciones del protocolo para calcular el CRC debo multiplicar el bloque de datos (de 8 a 128 bits) por 0x10000 (216), el resultado dividirlo en modulo 2 por el polinomio, y el CRC resulta de invertir el resto. Como aplicaría el algoritmo que desarrolla Bruno en este caso :?:
Saludos!