La suma de comprobación de Fletcher es un algoritmo para calcular una suma de comprobación dependiente de la posición ideado por John G. Fletcher (1934–2012) en Lawrence Livermore Labs a fines de la década de 1970. [1] El objetivo de la suma de comprobación de Fletcher era proporcionar propiedades de detección de errores que se aproximaran a las de una verificación de redundancia cíclica pero con el menor esfuerzo computacional asociado con las técnicas de suma.
Al igual que con los algoritmos de suma de comprobación más simples, la suma de comprobación de Fletcher implica dividir la palabra de datos binarios que se va a proteger de errores en "bloques" cortos de bits y calcular la suma modular de esos bloques. (Tenga en cuenta que la terminología utilizada en este dominio puede ser confusa. Los datos que se van a proteger, en su totalidad, se denominan "palabra", y las partes en las que se dividen se denominan "bloques").
Como ejemplo, los datos pueden ser un mensaje a transmitir que consta de 136 caracteres, cada uno almacenado como un byte de 8 bits , lo que forma una palabra de datos de 1088 bits en total. Un tamaño de bloque conveniente sería 8 bits, aunque esto no es obligatorio. De manera similar, un módulo conveniente sería 255, aunque, nuevamente, se podrían elegir otros. Por lo tanto, la suma de comprobación simple se calcula sumando todos los bytes de 8 bits del mensaje, dividiendo por 255 y conservando solo el resto. (En la práctica, la operación de módulo se realiza durante la suma para controlar el tamaño del resultado). El valor de la suma de comprobación se transmite con el mensaje, lo que aumenta su longitud a 137 bytes, o 1096 bits. El receptor del mensaje puede volver a calcular la suma de comprobación y compararla con el valor recibido para determinar si el mensaje ha sido alterado por el proceso de transmisión.
La primera debilidad de la suma de comprobación simple es que no es sensible al orden de los bloques (bytes) en la palabra de datos (mensaje). Si se cambia el orden, el valor de la suma de comprobación será el mismo y no se detectará el cambio. La segunda debilidad es que el universo de valores de la suma de comprobación es pequeño, siendo igual al módulo elegido. En nuestro ejemplo, solo hay 255 valores de suma de comprobación posibles, por lo que es fácil ver que incluso los datos aleatorios tienen una probabilidad de alrededor del 0,4 % de tener la misma suma de comprobación que nuestro mensaje.
Fletcher soluciona ambas debilidades calculando un segundo valor junto con la suma de comprobación simple. Esta es la suma modular de los valores que toma la suma de comprobación simple a medida que se le añade cada bloque de la palabra de datos. El módulo utilizado es el mismo. Por lo tanto, para cada bloque de la palabra de datos, tomado en secuencia, el valor del bloque se suma a la primera suma y, a continuación, el nuevo valor de la primera suma se suma a la segunda suma. Ambas sumas comienzan con el valor cero (o algún otro valor conocido). Al final de la palabra de datos, se aplica el operador de módulo y los dos valores se combinan para formar el valor de la suma de comprobación de Fletcher.
Se introduce la sensibilidad al orden de los bloques porque, una vez que se añade un bloque a la primera suma, se añade repetidamente a la segunda suma junto con todos los bloques siguientes. Si, por ejemplo, se intercambian dos bloques adyacentes, el que originalmente era el primero se añadirá a la segunda suma una vez menos y el que originalmente era el segundo se añadirá a la segunda suma una vez más. El valor final de la primera suma será el mismo, pero la segunda suma será diferente, lo que detectará el cambio en el mensaje.
El universo de posibles valores de suma de comprobación es ahora el cuadrado del valor de la suma de comprobación simple. En nuestro ejemplo, las dos sumas, cada una con 255 valores posibles, dan como resultado 65025 valores posibles para la suma de comprobación combinada.
Si bien hay una infinidad de parámetros, el artículo original solo estudia el caso K=8 (longitud de palabra) con módulo 255 y 256.
Las versiones de 16 y 32 bits (Fletcher-32 y -64) se derivaron del caso original y se estudiaron en especificaciones o artículos posteriores.
Cuando la palabra de datos se divide en bloques de 8 bits, como en el ejemplo anterior, se obtienen dos sumas de 8 bits que se combinan en una suma de comprobación Fletcher de 16 bits. Normalmente, la segunda suma se multiplica por 256 y se añade a la suma de comprobación simple, apilando de forma efectiva las sumas una al lado de la otra en una palabra de 16 bits con la suma de comprobación simple en el extremo menos significativo. Este algoritmo se denomina entonces suma de comprobación Fletcher-16. El uso del módulo 2 8 − 1 = 255 también suele estar implícito.
Cuando la palabra de datos se divide en bloques de 16 bits, se obtienen dos sumas de 16 bits que se combinan en una suma de comprobación Fletcher de 32 bits. Normalmente, la segunda suma se multiplica por 2 16 y se añade a la suma de comprobación simple, apilando efectivamente las sumas una al lado de la otra en una palabra de 32 bits con la suma de comprobación simple en el extremo menos significativo. Este algoritmo se denomina entonces suma de comprobación Fletcher-32. El uso del módulo 2 16 − 1 = 65.535 también suele estar implícito. La lógica de esta elección es la misma que para Fletcher-16.
Cuando la palabra de datos se divide en bloques de 32 bits, se obtienen dos sumas de 32 bits que se combinan en una suma de comprobación Fletcher de 64 bits. Normalmente, la segunda suma se multiplica por 2 32 y se añade a la suma de comprobación simple, apilando de forma efectiva las sumas una al lado de la otra en una palabra de 64 bits con la suma de comprobación simple en el extremo menos significativo. Este algoritmo se denomina entonces suma de comprobación Fletcher-64. El uso del módulo 2 32 − 1 = 4.294.967.295 también suele estar implícito. La lógica de esta elección es la misma que para Fletcher-16 y Fletcher-32.
La suma de comprobación Adler-32 es una especialización de la suma de comprobación Fletcher-32 ideada por Mark Adler . El módulo seleccionado (para ambas sumas) es el número primo 65.521 (65.535 es divisible por 3, 5, 17 y 257). La primera suma también comienza con el valor 1. La selección de un módulo primo da como resultado una "mezcla" mejorada (los patrones de error se detectan con una probabilidad más uniforme, lo que mejora la probabilidad de que se detecten los patrones menos detectables, lo que tiende a dominar el rendimiento general). Sin embargo, la reducción en el tamaño del universo de posibles valores de suma de comprobación actúa en contra de esto y reduce ligeramente el rendimiento. Un estudio mostró que Fletcher-32 supera a Adler-32 tanto en rendimiento como en su capacidad para detectar errores. Como la suma módulo-65.535 es considerablemente más simple y rápida de implementar que la suma módulo-65.521, la suma de comprobación Fletcher-32 es generalmente un algoritmo más rápido. [2]
Arriba y en los ejemplos siguientes se utiliza un módulo de 255 para Fletcher-16, sin embargo algunas implementaciones del mundo real utilizan 256. La suma de comprobación alternativa del protocolo TCP tiene Fletcher-16 con un módulo de 256, [3] al igual que las sumas de comprobación de los mensajes UBX-* de un GPS U-blox . [4] El módulo que se utiliza depende de la implementación.
A modo de ejemplo, se calculará y verificará una suma de comprobación Fletcher-16 para un flujo de bytes de 0x01 0x02.
Por lo tanto, la suma de comprobación es 0x0403. Podría transmitirse con el flujo de bytes y verificarse como tal en el extremo receptor. Otra opción es calcular en un segundo paso un par de bytes de comprobación, que se pueden agregar al flujo de bytes para que el flujo resultante tenga un valor de suma de comprobación Fletcher-16 global de 0.
Los valores de los checkbytes se calculan de la siguiente manera:
donde C0 y C1 son el resultado del último paso del cálculo de Fletcher-16.
En nuestro caso, los bytes de suma de comprobación son CB0 = 0xF8 y CB1 = 0x04. El flujo de bytes transmitido es 0x01 0x02 0xF8 0x04. El receptor ejecuta la suma de comprobación en los cuatro bytes y calcula una suma de comprobación de paso de 0x00 0x00, como se ilustra a continuación:
La suma de comprobación de Fletcher no puede distinguir entre bloques de todos los bits 0 y bloques de todos los bits 1. Por ejemplo, si un bloque de 16 bits en la palabra de datos cambia de 0x0000 a 0xFFFF, la suma de comprobación de Fletcher-32 permanece igual. Esto también significa que una secuencia de todos los bytes 00 tiene la misma suma de comprobación que una secuencia (del mismo tamaño) de todos los bytes FF.
Estos ejemplos suponen aritmética de complemento a dos , ya que el algoritmo de Fletcher será incorrecto en máquinas de complemento a uno .
A continuación se explica cómo calcular la suma de comprobación, incluidos los bytes de comprobación; es decir, el resultado final debe ser igual a 0, dados los bytes de comprobación calculados correctamente. Sin embargo, el código por sí solo no calculará los bytes de comprobación.
A continuación se muestra una implementación ineficiente pero sencilla de una función en lenguaje C para calcular la suma de comprobación Fletcher-16 de una matriz de elementos de datos de 8 bits:
uint16_t Fletcher16 ( uint8_t * datos , int recuento ) { uint16_t suma1 = 0 ; uint16_t suma2 = 0 ; int índice ; para ( índice = 0 ; índice < conteo ; ++ índice ) { suma1 = ( suma1 + datos [ índice ]) % 255 ; suma2 = ( suma2 + suma1 ) % 255 ; } devolver ( suma2 << 8 ) | suma1 ; }En las líneas 3 y 4, las sumas son variables de 16 bits, de modo que las sumas en las líneas 9 y 10 no se desbordarán . La operación de módulo se aplica a la primera suma en la línea 9 y a la segunda suma en la línea 10. Aquí, esto se hace después de cada suma, de modo que al final del bucle for las sumas siempre se reducen a 8 bits. Al final de los datos de entrada, las dos sumas se combinan en el valor de suma de comprobación de Fletcher de 16 bits y lo devuelve la función en la línea 13.
Cada suma se calcula en módulo 255 y, por lo tanto, permanece menor que 0xFF en todo momento. Por lo tanto, esta implementación nunca producirá los resultados de suma de comprobación 0x??FF, 0xFF?? o 0xFFFF (es decir, 511 de los 65536 valores de 16 bits posibles nunca se utilizan). Puede producir el resultado de suma de comprobación 0x0000, lo que puede no ser deseable en algunas circunstancias (por ejemplo, cuando este valor se ha reservado para significar "no se ha calculado ninguna suma de comprobación").
El código fuente de ejemplo para calcular los bytes de control, utilizando la función anterior, es el siguiente. Los bytes de control se pueden agregar al final del flujo de datos, con c0 antes de c1.
uint16_t suma de suma ; uint16_t c0 , c1 , f0 , f1 ; csum = Fletcher16 ( datos , longitud ); f0 = csum & 0xff ; f1 = ( csum >> 8 ) & 0xff ; c0 = 0xff - (( f0 + f1 ) % 0xff ); c1 = 0xff - (( f0 + c0 ) % 0xff ); En un artículo de 1988, Anastase Nakassis analizó y comparó diferentes formas de optimizar el algoritmo. La optimización más importante consiste en utilizar acumuladores más grandes y retrasar la operación de módulo, relativamente costosa, hasta que se pueda demostrar que no se producirá un desbordamiento. Se pueden obtener más beneficios al reemplazar el operador de módulo con una función equivalente adaptada a este caso específico, por ejemplo, una simple comparación y resta, ya que el cociente nunca supera 1. [5]
A continuación se muestra una implementación en C que aplica la primera optimización pero no la segunda:
#include <stdlib.h> /* para tamaño_t */ #include <stdint.h> /* para uint8_t, uint16_t y uint32_t */ uint16_t fletcher16 ( const uint8_t * datos , tamaño_t len ) { uint32_t c0 , c1 ; /* Se obtiene al resolver el desbordamiento de c1: */ /* n > 0 y n * (n+1) / 2 * (2^8-1) < (2^32-1). */ for ( c0 = c1 = 0 ; len > 0 ; ) { size_t blocklen = len ; if ( blocklen > 5802 ) { blocklen = 5802 ; } len -= blocklen ; do { c0 = c0 + * data ++ ; c1 = c1 + c0 ; } while ( -- blocklen ); c0 = c0 % 255 ; c1 = c1 % 255 ; } return ( c1 << 8 | c0 ); } uint32_t fletcher32 ( const uint16_t * data , size_t len ) { uint32_t c0 , c1 ; len = ( len + 1 ) & ~ 1 ; /* Redondea len a palabras */ /* De manera similar, resolvemos para n > 0 y n * (n+1) / 2 * (2^16-1) < (2^32-1) aquí. */ /* En computadoras modernas, usar un c0/c1 de 64 bits podría permitir un tamaño de grupo de 23726746. */ for ( c0 = c1 = 0 ; len > 0 ; ) { size_t blocklen = len ; if ( blocklen > 360 * 2 ) { blocklen = 360 * 2 ; } len -= blocklen ; do { c0 = c0 + * data ++ ; c1 = c1 + c0 ; } while (( blocklen -= 2 )); c0 = c0 % 65535 ; c1 = c1 % 65535 ; } return ( c1 << 16 | c0 ); } // Se podría escribir una rutina similar para fletcher64. El tamaño del grupo sería 92681.La segunda optimización no se utiliza porque el supuesto de que "nunca supera 1" sólo se aplica cuando el módulo se calcula de forma ingenua; aplicar la primera optimización lo rompería. Por otro lado, los números de Mersenne de módulo como 255 y 65535 son de todos modos una operación rápida en las computadoras, ya que hay trucos disponibles para realizarlos sin la costosa operación de división. [6]
Implementación de 8 bits (suma de comprobación de 16 bits)
"abcde" -> 51440 (0xC8F0)"abcdef" -> 8279 (0x2057)"abcdefgh" -> 1575 (0x0627)
Implementación de 16 bits (suma de comprobación de 32 bits), con valores ASCII de 8 bits de la palabra de entrada ensamblados en bloques de 16 bits en orden little-endian , la palabra rellenada con ceros según sea necesario hasta el siguiente bloque completo, utilizando el módulo 65535 y con el resultado presentado como la suma de sumas desplazada a la izquierda por 16 bits (multiplicada por 65536) más la suma simple
"abcde" -> 4031760169 (0xF04FC729)"abcdef" -> 1448095018 (0x56502D2A)"abcdefgh" -> 3957429649 (0xEBE19591)
Implementación de 32 bits (suma de comprobación de 64 bits)
"abcde" -> 14467467625952928454 (0xC8C6C527646362C6)"abcdef" -> 14467579776138987718 (0xC8C72B276463C8C6)"abcdefgh" -> 3543817411021686982 (0x312E2B28CCCAC8C6)
Al igual que con cualquier cálculo que divide una palabra de datos binarios en bloques cortos y trata los bloques como números, dos sistemas que esperen obtener el mismo resultado deben conservar el orden de los bits en la palabra de datos. En este sentido, la suma de comprobación de Fletcher no es diferente de otros algoritmos de suma de comprobación y CRC y no necesita una explicación especial.
Un problema de ordenación que es fácil de imaginar ocurre cuando la palabra de datos se transfiere byte a byte entre un sistema big-endian y un sistema little-endian y se calcula la suma de comprobación Fletcher-32. Si se extraen bloques de la palabra de datos en la memoria mediante una simple lectura de un entero sin signo de 16 bits, entonces los valores de los bloques serán diferentes en los dos sistemas, debido a la inversión del orden de bytes de los elementos de datos de 16 bits en la memoria, y el resultado de la suma de comprobación será diferente como consecuencia. Los ejemplos de implementación, anteriores, no abordan problemas de ordenación para no oscurecer el algoritmo de suma de comprobación. Debido a que la suma de comprobación Fletcher-16 utiliza bloques de 8 bits, no se ve afectada por el orden de bytes .
{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )