Suma de comprobación de Fletcher

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 finales 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 similares a las de una comprobación de redundancia cíclica, pero con el menor esfuerzo computacional asociado con las técnicas de suma.

El algoritmo

Revisión de sumas de verificación simples

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 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 resultar confusa. Los datos que se protegerán, 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 hace una palabra de datos de 1088 bits en total. Un tamaño de bloque conveniente sería de 8 bits, aunque no es necesario. De manera similar, un módulo conveniente sería 255, aunque, nuevamente, se podrían elegir otros. Entonces, la suma de verificación simple se calcula sumando todos los bytes de 8 bits del mensaje, dividiéndolos por 255 y manteniendo solo el resto. (En la práctica, la operación módulose realiza durante la suma para controlar el tamaño del resultado.) El valor de la suma de comprobación se transmite con el mensaje, aumentando 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.

Debilidades de las sumas de verificación simples

La primera debilidad de la suma de comprobación simple es que es insensible 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 suma de control es pequeño, siendo igual al módulo elegido. En nuestro ejemplo, solo hay 255 valores de suma de verificación posibles, por lo que es fácil ver que incluso los datos aleatorios tienen aproximadamente un 0,4% de probabilidad de tener la misma suma de verificación que nuestro mensaje.

La suma de comprobación de Fletcher

Fletcher aborda estas dos debilidades calculando un segundo valor junto con la suma de comprobación simple. Esta es la suma modular de los valores tomados por la suma de comprobación simple a medida que se le agrega cada bloque de la palabra de datos. El módulo utilizado es el mismo. Entonces, para cada bloque de la palabra de datos, tomado en secuencia, el valor del bloque se agrega a la primera suma y el nuevo valor de la primera suma luego se agrega 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 suma de comprobación de Fletcher.

Se introduce sensibilidad al orden de los bloques porque una vez que se agrega un bloque a la primera suma, luego se agrega repetidamente a la segunda suma junto con todos los bloques posteriores. Si, por ejemplo, se intercambian dos bloques adyacentes, el que originalmente era el primero se agregará a la segunda suma una vez menos y el que originalmente era el segundo se agregará a la segunda suma una vez más. El valor final de la primera suma será el mismo, pero la segunda suma será diferente, detectando 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.

Resumen de los diferentes parámetros del algoritmo

Si bien existe 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 han derivado del caso original y se han estudiado en especificaciones o documentos posteriores.

Fletcher-16

Cuando la palabra de datos se divide en bloques de 8 bits, como en el ejemplo anterior, resultan dos sumas de 8 bits y se combinan en una suma de comprobación Fletcher de 16 bits. Por lo general, la segunda suma se multiplicará por 256 y se agregará a la suma de verificación simple, apilando efectivamente las sumas una al lado de la otra en una palabra de 16 bits con la suma de verificación simple en el extremo menos significativo. Este algoritmo se denomina entonces suma de comprobación de Fletcher-16. El uso del módulo 2 ⁸  -  1  =  255 también está generalmente implícito.

Fletcher-32

Cuando la palabra de datos se divide en bloques de 16 bits, resultan dos sumas de 16 bits y se combinan en una suma de comprobación Fletcher de 32 bits. Por lo general, la segunda suma se multiplicará por 2 ¹⁶ y se agregará a la suma de verificación simple, apilando efectivamente las sumas una al lado de la otra en una palabra de 32 bits con la suma de verificación simple en el extremo menos significativo. Este algoritmo se denomina suma de comprobación Fletcher-32. El uso del módulo 2 ¹⁶  -  1  =  65.535 también está implícito en general. El fundamento de esta elección es el mismo que el de Fletcher-16.

Fletcher-64

Cuando la palabra de datos se divide en bloques de 32 bits, resultan dos sumas de 32 bits y se combinan en una suma de comprobación Fletcher de 64 bits. Por lo general, la segunda suma se multiplicará por 2 ³² y se agregará a la suma de verificación simple, apilando efectivamente las sumas una al lado de la otra en una palabra de 64 bits con la suma de verificación simple en el extremo menos significativo. Este algoritmo se denomina suma de comprobación Fletcher-64. El uso del módulo 2 ³²  -  1  =  4.294.967.295 también está implícito en general. El fundamento de esta elección es el mismo que para Fletcher-16 y Fletcher-32.

Comparación con la suma de comprobación de Adler

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 principal 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 control 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 capacidad para detectar errores. Como la adición módulo-65,535 es considerablemente más simple y más rápida de implementar que la adición módulo-65,521, la suma de comprobación de Fletcher-32 es generalmente un algoritmo más rápido. ^[2]

Ejemplo de cálculo de la suma de comprobación de Fletcher-16

Por ejemplo, se calculará y verificará una suma de comprobación de Fletcher-16 para un flujo de bytes de 0x01 0x02.

• C0_inicial = 0
• C1_inicial = 0

Byte (B)	C0 = (C0 anterior + B) mod 255	C1 = (C1 anterior + C0) mod 255	Descripción
0x01	0x01	0x01	Primer byte introducido
0x02	0x03	0x04	Segundo byte introducido

Por 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 verificación, que se pueden agregar al flujo de bytes para que el flujo resultante tenga un valor global de suma de verificación Fletcher-16 de 0.

Los valores de los bytes de verificación se calculan de la siguiente manera:

• CB0 = 255 - ((C0 + C1) mod 255),
• CB1 = 255 - ((C0 + CB0) mod 255),

donde C0 y C1 son el resultado del último paso en el 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 verificación en los cuatro bytes y calcula una suma de verificación aprobatoria de 0x00 0x00, como se ilustra a continuación:

Byte (B)	C0 = (C0 anterior + B) mod 255	C1 = (C1 anterior + C0) mod 255	Descripción
0x01	0x01	0x01	Primer byte introducido
0x02	0x03	0x04	Segundo byte introducido
CB0 = 0xF8	(0x03 + 0xF8)% 0xFF = 0xFB	(0x04 + 0xFB)% 0xFF = 0x00	Cálculo de suma de comprobación - byte 1
CB1 = 0x04	(0xFB + 0x04)% 0xFF = 0x00	(0x00 + 0x00)% 0xFF = 0x00	Cálculo de suma de comprobación - byte 2

Debilidades

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 los 00 bytes tiene la misma suma de control que una secuencia (del mismo tamaño) de todos los bytes FF.

Implementación

Estos ejemplos asumen la aritmética del complemento a dos , ya que el algoritmo de Fletcher será incorrecto en las máquinas del complemento a uno .

Simple

A continuación se muestra un tratamiento sobre 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 control calculados correctamente. Sin embargo, el código por sí solo no calculará los bytes de verificació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 , recuento de int )      { uint16_t sum1 = 0 ;    uint16_t sum2 = 0 ;    int index ;  para ( índice = 0 ; índice < recuento ; ++ índice )          { suma1 = ( suma1 + datos [ índice ]) % 255 ;       suma2 = ( suma2 + suma1 ) % 255 ;       } return ( suma2 << 8 ) | sum1 ;     }

En las líneas 3 y 4, las sumas son variables de 16 bits para que las sumas en las líneas 9 y 10 no se desborden . 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 adición, de modo que al final del ciclo 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 la función en la línea 13 las devuelve.

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 la suma de comprobación 0x ?? FF, 0xFF ?? o 0xFFFF (es decir, 511 del total de 65536 valores posibles de 16 bits nunca se utilizan). Puede producir el resultado de suma de comprobación 0x0000, 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").

Comprobar bytes

El código fuente de ejemplo para calcular los bytes de verificación, utilizando la función anterior, es el siguiente. Los bytes de verificación se pueden agregar al final del flujo de datos, con el c0 antes del c1.

uint16_t csum ; 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 );        

Optimizaciones

En un artículo de 1988, Anastase Nakassis discutió y comparó diferentes formas de optimizar el algoritmo. La optimización más importante consiste en utilizar acumuladores más grandes y retrasar el relativamente costoso funcionamiento del módulo mientras se pueda demostrar que no se producirá un desbordamiento. Se puede obtener un beneficio adicional 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 excede 1. ^[3]

Aquí hay una implementación de C que aplica la primera pero no la segunda optimización:

#include <stdlib.h> / * para size_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 ;  / * Encontrado resolviendo el desbordamiento de c1: * // * n> 0 y n * (n + 1) / 2 * (2 ^ 8-1) <(2 ^ 32-1). * /para ( c0 = c1 = 0 ; len > 0 ; ) {          size_t blocklen = len ;   si ( blocklen > 5002 ) {    blocklen = 5002 ;  }len - = blocklen ;  hacer { c0 = c0 + * datos ++ ;    c1 = c1 + c0 ;    } while ( - blocklen );  c0 = c0 % 255 ;    c1 = c1 % 255 ;     } return ( c1 << 8 | c0 );     }uint32_t fletcher32 ( const uint16_t * datos , tamaño_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, el uso de un c0 / c1 de 64 bits podría permitir un tamaño de grupo de 23726746. * /para ( c0 = c1 = 0 ; len > 0 ; ) {          size_t blocklen = len ;   si ( blocklen > 360 * 2 ) {    blocklen = 360 * 2 ;  }len - = blocklen ;  hacer { c0 = c0 + * datos ++ ;    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 la suposición "nunca excede 1" sólo se aplica cuando el módulo se calcula ingenuamente; aplicar la primera optimización lo rompería. Por otro lado, los números de módulo Mersenne como 255 y 65535 son una operación rápida en computadoras de todos modos, ya que hay trucos disponibles para hacerlos sin la costosa operación de división. ^[4]

Vectores de prueba

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 para 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 (multiplicado 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)

Orden de bits y bytes ( endianness / orden de red)

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 cualesquiera que esperen obtener el mismo resultado deben conservar el orden de los bits en la palabra de datos. A este respecto, la suma de control de Fletcher no es diferente de otros algoritmos de suma de control 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 de Fletcher-32. Si los bloques se extraen de la palabra de datos en la memoria mediante una simple lectura de un entero sin signo de 16 bits, 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 de Fletcher-16 utiliza bloques de 8 bits, no se ve afectada por el byte endianness .

Referencias

1. Fletcher, JG (enero de 1982). "Una suma de comprobación aritmética para transmisiones en serie". Transacciones IEEE sobre comunicaciones . COM-30 (1): 247–252. doi : 10.1109 / tcom.1982.1095369 .
2. Theresa C. Maxino, Philip J. Koopman (enero de 2009). "La eficacia de las sumas de comprobación para redes de control integradas" (PDF) . Transacciones IEEE sobre computación segura y confiable.
3. Anastase Nakassis (octubre de 1988). "Algoritmo de detección de errores de Fletcher: cómo implementarlo de manera eficiente y cómo evitar las trampas más comunes". Newsletter ACM SIGCOMM Computer Communication Review Inicio Archivo . 18 (5): 63–88. doi : 10.1145 / 53644.53648 .
4. Jones, Douglas W. "Módulo sin división, un tutorial" . LA UNIVERSIDAD DE IOWA Departamento de Ciencias de la Computación . Consultado el 9 de septiembre de 2019 .

enlaces externos

• RFC  905 - Especificación del protocolo de transporte ISO describe el algoritmo de suma de comprobación de Fletcher sumando cero (en el Apéndice B).
• RFC  1146 - Opciones de suma de comprobación alternativas de TCP describe el algoritmo de suma de comprobación de Fletcher para su uso con TCP.
• Jonathan Stone, Michael Greenwald, Craig Partridge, Jim Hughes: Rendimiento de sumas de comprobación y CRC sobre datos reales (transacciones IEEE / ACM en redes).
• John Kodis : cuando se trata de verificación de datos de alta velocidad, el algoritmo de suma de comprobación de Fletcher puede hacer el trabajo.