En esta entrada vamos a ver algunas funciones de checksum sencillas que podemos emplear en pequeños procesadores como Arduino para comprobar la integridad de los datos.
Cuando trabajamos con sistemas de comunicación o datos almacenados, existe la posibilidad de que los datos se corrompan. Es decir, que uno o varios bytes de la secuencia cambien o incluso se pierdan por completo.
Con frecuencia necesitaremos comprobar la integridad de los datos antes de ejecutar acciones. Por ejemplo, las consecuencias de mover un robot según órdenes equivocadas recibidas por una comunicación inalámbricas podrían ser desastrosas e incluso potencialmente peligrosas.
Para eso podemos añadir un checksum, un valor de pequeño tamaño calculado a partir de un bloque de datos de tamaño mayor cuyo propósito es detectar errores introducidos en la secuencia.
En un sistema de comunicación o almacenamiento, el checksum se envía/recibe o almacena junto a los datos. Al realizar el tratamiento se calcula nuevamente el checksum y se comprueba con el checksum disponible para comprobar la integridad de los datos.
Existen múltiples funciones de checksum, con diferentes tasas de detección de fallos y requisitos de cálculo. Por otro lado, cuando más largo sea el checksum mayor es la fiabilidad del mismo, pero mayores son las necesidades de comunicación/almacenamiento adicionales para guardar el checksum.
Finalmente, ningún sistema es infalible. Aunque enviases el mismo mensaje 100 veces (lo que sería una especie de “checksum” enorme e ineficiente) no podrías garantizar que el mismo fallo haya ocurrido en las 100 tandas de transmisión. Como casi siempre, es cuestión de llegar a un compromiso entre fiabilidad, longitud, y carga de cálculo.
Vamos implementaciones de algunos de las principales funciones de checksum lo suficientemente ligeras para ejecutarse de forma ágil en un microprocesador como Arduino.
Checksum XOR
El checksum XOR, también llamado LCR (Longitudinal Redundancy Check), es ampliamente utilizado por su sencillez y rapidez de cálculo. Se calcula procesando la secuencia de datos en fragmentos de N bits, y ejecutando la operación XOR en todos los fragmentos.
Por lo general los fragmentos se escogen de forma que sean múltiplos de 8 porque los cálculos se aceleran enormemente, ya que los procesadores están pensados para ejecutar acciones sobre bloques de bytes.
Con frecuencia, el checksum se devuelve negado. El motivo es diferenciar un fallo completo de comunicación, que provoque que todos los datos recibidos sean 0, frente a un envió de datos formado por 0’s.
El siguiente código muestra un checksum XOR de 8 bits.
uint8_t XORChecksum8(const byte *data, size_t dataLength)
{
uint8_t value = 0;
for (size_t i = 0; i < dataLength; i++)
{
value ^= (uint8_t)data[i];
}
return ~value;
}El código para un checksum XOR de 16 bits es el siguiente.
uint16_t XORChecksum16(const byte *data, size_t dataLength)
{
uint16_t value = 0;
for (size_t i = 0; i < dataLength / 2; i++)
{
value ^= data[2*i] + (data[2*i+1] << 8);
}
if(dataLength%2) value ^= data[dataLength - 1];
return ~value;
}Como decimos, el checksum XOR es sencillo y rápido de ejecutar, motivos por lo cual es muy extendido. Sin embargo, la tasa de detección de errores es bastante limitada.
Debido al funcionamiento de la función XOR, en realidad el checksum XOR se comporta como un bit de paridad para cada una de las columnas (bits) del checksum. Por tanto, sólo es capaz de detectar un número impar de cambios de bits en cada una de las columnas. Como caso particular, no son capaces de detectar la recepción de dos paquetes en orden equivocado.
La tasa de fallo promedio es de 1/k, siendo K el número de bits del checksum, lo que significa una tasa de fallo promedio de 12.5% para 8bits y 6.25% para 16bits.
Checksum aditivos
Otra familia de checksum muy empleados son las familias de checksum aditivos. Los checksum aditivos también dividen los datos realizados en fragmentos de N bits, y realizan la suma acumulada de los bloques.
En función de cómo se realice la suma de los bytes recibidos tenemos distintos tipos de checksum aditivos.
El caso más sencillo es emplear la suma de complemento a 2, en el que simplemente ignoramos los acarreos y dejamos que en caso de overflow el checksum se reinicie.
Aquí tenemos un ejemplo de checksum aditivo de 8bits con complemento a 2.
uint8_t TwoComplementChecksum8(const byte *data, size_t dataLength)
{
uint8_t value = 0;
for (size_t i = 0; i < dataLength; i++)
{
value += (uint8_t)data[i];
}
return ~value;
}Y aquí un checksum aditivo de 16bits con complemento a 2.
uint16_t TwoComplementChecksum16(const byte *data, size_t dataLength)
{
uint16_t value = 0;
for (size_t i = 0; i < dataLength / 2; i++)
{
value += data[2*i] + (data[2*i+1] << 8);
}
if(dataLength%2) value += data[dataLength - 1];
return value;
}Esta implementación es sencilla, pero supone una mayor posibilidad de fallo en los bytes más significativos (MSB) porque la información de acarreo no interviene en el cálculo del checksum.
Una alternativa es emplear como función de suma el cálculo con complemento a 1. En un procesador con cálculo de complemento a 2 (la mayoría) el complemento a 1 se simula empleando un checksum de tamaño superior, y finalmente añadiendo los bits de acarreo al valor final hasta que desaparece el acarreo.
Esto mejora ligeramente la fiabilidad, a costa de suponer un pequeño aumento en el coste del cálculo.
uint8_t OneComplementChecksum8(const byte *data, size_t dataLength)
{
uint16_t value = 0;
for (size_t i = 0; i < dataLength; i++)
{
value += (uint8_t)data[i];
}
while (sum>>8)
sum = (sum & 0xF) + (sum >> 8);
return (uint8_t)~sum;
}uint16_t OneComplementChecksum16(const byte *data, size_t dataLength)
{
uint32_t value = 0;
for (size_t i = 0; i < dataLength / 2; i++)
{
value += data[2*i] + (data[2*i+1] << 8);
}
if(dataLength%2) value += data[dataLength - 1];
while (sum>>16)
sum = (sum & 0xFF) + (sum >> 16);
return sum;
}Los checksum aditivos presentan mejor comportamiento que los XOR ya que los cambios en bits tienen efectos en las otras columnas gracias a los bits de acarreo, a la vez que mantienen una alta eficiencia respecto al caso XOR (en algunos casos idéntica).
La tasa de fallo promedio para el checksum con suma con complemento a uno es la mitad (1/2K) que el XOR con el mismo número de bits. Equivalentemente, en promedio, un checksum aditivo es igual de eficiente que un XOR del doble de bits.
El motivo es que la principal causa de fallo del checksum aditivo es una modificación simultánea de dos bits en la misma columna, cuyo valor es diferente (0-1 1-0) mientras que el checksum XOR falla en la modificación simultánea de dos bits de la misma columna en todos los casos (0-0 0-1 1-0 1-1).
Es decir, la tasa de fallo promedio para un complemento a 1 es de un 6.25% para un checksum de 8bits, y de 3.125% para 1bits. En el caso de complemento a 2 es ligeramente peor, aproximadamente 7% para 8bits y 3.3 para 16bits.
Sin embargo comparten una gran debilidad, que no son capaces de detectar cuando dos bloques enteros llegan en un orden incorrecto ya la suma permanece inalterada.
Finalmente, los checksum aditivos presentan un peor comportamiento cuando la distribución de 0’s y 1’s es uniforme (lo cual lo penaliza en los benchmark con números aleatorios). El mejor comportamiento se observa con datos con una distribución mayoritaria de 0’s.
Chechsum Fletcher16
Este algoritmo de comprobación fue desarrollado por John G. Fletcher (1934–2012) en el Lawrence Livermore Labs en la década de 1970.
El checksum Fletcher requiere al menos 16 bits y está formado por la concatenación de dos sumatorios. El primer sumatorio es simplemente la suma de los bytes recibidos (con complemento a 2 o 1). El segundo sumatorio es la suma del primer sumatorio en cada uno de los pasos.
Aquí tenemos una implementación sencilla del Checksum Fletcher en 16 bits con suma en complemento a 2.
uint16_t ChecksumFletcher16(byte *data, size_t count )
{
uint8_t sum1 = 0;
uint8_t sum2 = 0;
for(size_t index = 0; index < count; ++index )
{
sum1 = sum1 + (uint8_t)data[index];
sum2 = sum2 + sum1;
}
return (sum2 << 8) | sum1;
}Y aquí una implementación con suma en complemento a 1.
uint16_t ChecksumFletcher16(byte *data, size_t count )
{
uint16_t sum1 = 0;
uint16_t sum2 = 0;
for(size_t index = 0; index < count; ++index )
{
sum1 = sum1 + (uint8_t)data[index];
while (sum1>>8)
sum1 = (sum1 & 0xF) + (sum1 >> 8);
sum2 = sum2 + sum1;
while (sum2>>8)
sum2 = (sum2 & 0xF) + (sum2 >> 8);
}
return (sum2 << 8) | sum1;
}La capacidad de detección de la función Fletcher es significativamente superior que el equivalente XOR o aditivo con el mismo número de bits (varios ordenes de magnitud) .
Además, el checksum Fletcher es capaz de detectar intercambios completos de fragmentos de código. El motivo es que el segundo sumatorio acumula cada fragmento una vez que aparece en la secuencia, hasta el final de la misma, a través del primer sumatorio.
Si un fragmento intercambia la posición en los datos, el segundo sumatorio es capaz de detectar el error, aun cuando el primero sea idéntico.
Checksum CRC
Los códigos CRC (Cyclic Redundancy Checks) son uno de los checksum más extendidos en el mundo de la informática. Su cálculo está basado en el cálculo de una serie de polinomios cuya formulación y orden dependen, entre otros, del número de bits del checksum.
Los CRC con mejores tasas de detección de los presentados aquí, pero su cálculo supone una carga superior a los demás. Aunque es posible acelerarlo con el uso de tablas precalculadas, normalmente los requisitos son excesivos para funcionar con soltura en un procesador pequeño como Arduino.
Por tanto, únicamente vamos a ver como ejemplo el CRC8, basado en las formulas distribuidas por la empresa Dallas/Maxim en los términos de licencia GNU GLP 3.0.
//CRC-8 - based on the CRC8 formulas by Dallas/Maxim
//code released under the therms of the GNU GPL 3.0 license
byte CRC8(const byte *data, size_t dataLength)
{
byte crc = 0x00;
while (dataLength--)
{
byte extract = *data++;
for (byte tempI = 8; tempI; tempI--)
{
byte sum = (crc ^ extract) & 0x01;
crc >>= 1;
if (sum)
{
crc ^= 0x8C;
}
extract >>= 1;
}
}
return crc;
}Los CRC tienen muy buenas tasas de detección. El motivo es la mayor mezcla de bits que supone la aplicación de los polinomios. En general, su comportamiento es comparable a 1/(2^k), un límite de referencia en el análisis de checksums (entendiendo comparable como que es capaz de medirse con él, no que lo alcance).
Al igual que los checksum Fletcher, los CRC detectan intercambios completos de fragmentos. En general, el comportamiento de un CRC es ligeramente superior al equivalente Fletchet con el mismo número de bits.
El mayor problema es, como hemos comentado, el mayor requisito de cálculos. Si embargo, pese a su formulación sencilla, el checksum CRC8 visto como ejemplo presenta una muy buena capacidad de detección de fallos, con un uso moderado de procesador.
Existen varias librerías para Arduino que permiten calcular el CRC16. Sin embargo, dado que la capacidad detección es superior, pero no muy superior al Fletcher16, mi consejo es que empleéis este por su mayor sencillez y rapidez de cálculo.
Descarga el código
Todo el código de esta entrada está disponible para su descarga en Github. 