👼🏼 🤨 ♾ CRC16 Fiabilidad de suma de comprobación 👩🏾‍🤝‍👩🏼 🤽🏼 💎

No hace mucho tiempo, de servicio, me encontré con un problema bastante interesante.

Tenemos un dispositivo que realiza un intercambio intensivo en el bus interno RS485, el número de paquetes que pasan es de varios miles por segundo, cada paquete tiene una longitud de 7 bytes, dos de los cuales están diseñados para almacenar la suma de verificación CRC16 en su versión CMS (polinomio = 0x8005, valor inicial = 0xFFFF). La recepción se lleva a cabo en el búfer FIFO, que se desplaza hacia arriba con desplazamiento después de la recepción de cada byte posterior. Un indicador de recibir un paquete real es el hecho de que su suma de verificación coincide con el valor transmitido en el paquete mismo. Sin encabezados ni parámetros adicionales.

El problema era el siguiente: periódicamente, aproximadamente una vez cada 5 minutos, un paquete se deslizaba durante la transferencia de datos, cuyos datos daban un valor atípico para uno de los canales y, con mayor frecuencia, el valor atípico se producía con el mismo valor. Al principio miramos en la dirección de colisiones físicas, pero resultó diferente: de vez en cuando en el búfer donde se recopilaron los datos, apareció un paquete que consistía en el final del paquete anterior y el comienzo del siguiente, y la suma de comprobación de dicho paquete combinado resultó ser correcta. Es decir, hay una colisión de la suma de comprobación: el paquete no tiene sentido, pero proporciona la suma de comprobación correcta.

Naturalmente, el error ya estaba en el nivel de diseño del sistema, ya que los paquetes no tenían encabezados, la introducción de un encabezado de byte adicional redujo el número de errores a un nivel indetectable, pero esto no me pareció suficiente. Decidí comprobar cómo los diferentes tipos de sumas de comprobación de 16 bits difieren entre sí en condiciones reales. En realidad, sobre esto y el artículo.

A modo de comparación, seleccioné algunas de las sumas de comprobación de 16 bits más utilizadas con varios polinomios, valores iniciales y un mecanismo de llegada de bits. Las cantidades que he seleccionado se resumen en la siguiente tabla:

Designación	Polinomio	Init	Refinar	Refout	Xorout
CMS	0x8005	0xFFFF	falso	falso	0x0000
CCITT	0x1021	0xFFFF	falso	falso	0x0000
AGO-CCITT	0x1021	0x1D0F	falso	falso	0x0000
BYPASS	0x8005	0x0000	falso	falso	0x0000
CDMA2000	0xC867	0xFFFF	falso	falso	0x0000
DDS-110	0x8005	0x800D	falso	falso	0x0000
DECT-X	0x0589	0x0000	falso	falso	0x0000
EN-13757	0x3D65	0x0000	falso	falso	0xFFFF
Modbus	0x8005	0xFFFF	cierto	cierto	0x0000
T10-DIF	0x8BB7	0x0000	falso	falso	0x0000
TELEDISCO	0xA097	0x0000	falso	falso	0x0000
XMODEM	0x1021	0x0000	falso	falso	0x0000

En este caso:

RefIn - el orden de llegada de los bits desde el búfer de datos: falso - comenzando con el bit más significativo (MSB primero), verdadero - LSB primero;
RefOut: indicador de inversión del orden de bits en la salida: verdadero: inversión.

Al emular la corrupción de paquetes, implementé los siguientes modelos:

Reproducción aleatoria: llenar un número aleatorio de bytes en un paquete con valores aleatorios
Desplazamiento de bits: desplaza bytes aleatorios en un paquete a la izquierda
Paquete de rollo: desplazamiento de byte de anillo en el paquete a la izquierda
Desplazamiento a la derecha : desplazamiento de paquetes a la derecha en un byte, 0xFF se agrega a la izquierda (la transmisión es a través de UART)
Desplazamiento a la izquierda: desplaza el paquete a la izquierda en un byte, 0xFF se agrega a la derecha
Rellenar ceros: rellenar un número aleatorio de bytes en un paquete con 0x00 bytes (todos ceros)
Rellenar unos: llenar un número aleatorio de bytes en un paquete con 0xFF bytes (todas las unidades)
Inyección de bytes: inserte un byte aleatorio en un paquete en un lugar aleatorio, los bytes después del insertado se desplazan en la dirección de la cola
Solo bit: daño a un solo bit aleatorio

Luego, el programa generó aleatoriamente 100,000,000 paquetes, cada uno de ellos llevó a cabo las operaciones anteriores, después de lo cual se compararon las sumas de verificación de los paquetes originales y modernizados. Los paquetes que no cambiaron durante la conversión fueron descartados. Si la suma de comprobación coincide, se registra un error.

Como resultado, se obtuvo la siguiente tabla con el número de errores:

Designación	Barajar	Cambio de bit	Paquete de rollo	Desplazamiento a la derecha	Desplazamiento a la izquierda	Llenar ceros	Llenar los	Inyección de bytes	Suma
CMS	5101	3874	2937	1439	1688	3970	4010	1080	24099
CCITT	2012	1127	3320	1494	1486	1063	1096	1130	12728
AGO-CCITT	2012	1127	3320	1494	1486	1063	1096	1130	12728
BYPASS	5101	3874	2937	1439	1688	3970	4010	1080	24099
CDMA2000	1368	1025	1946	1462	1678	1043	1028	1112	10662
DDS-110	5101	3874	2937	1439	1688	3970	4010	1080	24099
DECT-X	1432	1189	5915	1779	1580	1215	1209	1093	15412
EN-13757	1281	2209	3043	1520	1528	2193	2187	1039	15,000
Modbus	5090	3888	3086	1282	1582	3947	3897	1073	23845
T10-DIF	1390	922	1424	1421	1630	994	938	1093	9812
TELEDISCO	1394	1049	5398	1451	1512	1096	1066	1065	14031
XMODEM	2012	1127	3320	1494	1486	1063	1096	1130	12728

Obviamente, el valor inicial del algoritmo no afecta el resultado de ninguna manera, lo cual es lógico, el valor inicial nos da solo un valor diferente de la suma de verificación, pero el mecanismo de cálculo en sí no cambia de ninguna manera. Por lo tanto, excluí estas sumas de verificación de mayor consideración. De la misma manera, no tiene sentido considerar los errores en bits individuales, todas las sumas de verificación lo resolvieron sin error, lo que, de hecho, se les exigió durante la creación.

Bueno, la tabla de calidad final de la suma de comprobación, ya sin tener en cuenta algoritmos duplicados:

Designación	Numero de colisiones	Lugar
CMS	24099	8
CCITT	12728	3
CDMA2000	10662	2
DECT-X	15412	6 6
EN-13757	15,000	5 5
Modbus	23845	7 7
T10-DIF	9812	1
TELEDISCO	14031	4 4

Dejo las conclusiones restantes a los lectores. Solo noto de mí mismo que el número de unidades en el polinomio de suma de verificación tiene un cierto efecto en los resultados. Pero esta es solo mi opinión subjetiva personal. Estaré encantado de escuchar otras explicaciones.

El código fuente del programa se proporciona a continuación.

Código fuente

#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <stdbool.h> #include <string.h> #include <time.h> #define PACKET_LEN (7) #define NUM_OF_CYCLES (100000) static unsigned char reverse_table[16] = { 0x0, 0x8, 0x4, 0xC, 0x2, 0xA, 0x6, 0xE, 0x1, 0x9, 0x5, 0xD, 0x3, 0xB, 0x7, 0xF }; uint8_t reverse_bits(uint8_t byte) { // Reverse the top and bottom nibble then swap them. return (reverse_table[byte & 0b1111] << 4) | reverse_table[byte >> 4]; } uint16_t reverse_word(uint16_t word) { return ((reverse_bits(word & 0xFF) << 8) | reverse_bits(word >> 8)); } uint16_t crc16_common(uint8_t *data, uint8_t len, uint16_t poly, uint16_t init, uint16_t doXor, bool refIn, bool refOut) { uint8_t y; uint16_t crc; crc = init; while (len--) { if (refIn) crc = ((uint16_t)reverse_bits(*data++) << 8) ^ crc; else crc = ((uint16_t)*data++ << 8) ^ crc; for (y = 0; y < 8; y++) { if (crc & 0x8000) crc = (crc << 1) ^ poly; else crc = crc << 1; } } if (refOut) crc = reverse_word(crc); return (crc ^ doXor); } uint16_t crc16_ccitt(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x1021, 0xFFFF, 0x0000, false, false); } uint16_t crc16_bypass(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x8005, 0x0000, 0x0000, false, false); } uint16_t crc16_xmodem(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x1021, 0x0000, 0x0000, false, false); } uint16_t crc16_teledisk(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0xA097, 0x0000, 0x0000, false, false); } uint16_t crc16_augccitt(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x1021, 0x1d0f, 0x0000, false, false); } uint16_t crc16_cdma2000(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0xc867, 0xffff, 0x0000, false, false); } uint16_t crc16_dds110(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x8005, 0x800d, 0x0000, false, false); } uint16_t crc16_dect(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x0589, 0x0000, 0x0000, false, false); } uint16_t crc16_en13757(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x3d65, 0x0000, 0xffff, false, false); } uint16_t crc16_t10dif(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x8bb7, 0x0000, 0x0000, false, false); } uint16_t crc16_cms(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x8005, 0xFFFF, 0x0000, false, false); } uint16_t crc16_modbus(uint8_t *data, uint8_t len) { return crc16_common(data, len, 0x8005, 0xFFFF, 0x0000, true, true); } bool compare_buf(uint8_t *buf1, uint8_t *buf2) { uint8_t x; for (x = 0; x < PACKET_LEN; x++) { if (buf1[x] != buf2[x]) return true; } return false; } bool method_shuffle(uint8_t *buf) { uint8_t i, j; uint16_t rnd; uint8_t copy[PACKET_LEN]; memcpy(copy, buf, PACKET_LEN); for (i = 0; i < PACKET_LEN; i++) { for (j = 0; j < 10; j++) { rnd = (uint16_t)rand(); if (rnd % 7 == 0) buf[i] ^= (1 << (rnd % 8)); } } return compare_buf(buf, copy); } bool method_bitshift(uint8_t *buf) { uint8_t x, i, j; uint8_t copy[PACKET_LEN]; memcpy(copy, buf, PACKET_LEN); x = (uint8_t)(rand() % PACKET_LEN) + 1; for (j = 0; j < x; j++) { i = (uint8_t)(rand() % PACKET_LEN); if (buf[i] == 0) buf[i] = 0x01; else buf[i] <<= 1; } return compare_buf(buf, copy); } bool method_packetroll(uint8_t *buf) { uint8_t x, i, j; uint8_t temp; uint8_t copy[PACKET_LEN]; memcpy(copy, buf, PACKET_LEN); x = (uint8_t)(rand() % (PACKET_LEN - 1)) + 1; for (j = 0; j < x; j++) { temp = buf[0]; for (i = 0; i < PACKET_LEN - 1; i++) buf[i] = buf[i + 1]; buf[PACKET_LEN - 1] = temp; } return compare_buf(buf, copy); } bool method_shiftright(uint8_t *buf) { uint8_t i; uint8_t copy[PACKET_LEN]; memcpy(copy, buf, PACKET_LEN); for (i = 0; i < PACKET_LEN - 1; i++) buf[i + 1] = buf[i]; buf[0] = 0xff; return compare_buf(buf, copy); } bool method_shiftleft(uint8_t *buf) { uint8_t i; uint8_t copy[PACKET_LEN]; memcpy(copy, buf, PACKET_LEN); for (i = 0; i < PACKET_LEN - 1; i++) buf[i] = buf[i + 1]; buf[PACKET_LEN - 1] = 0xff; return compare_buf(buf, copy); } bool method_zero(uint8_t *buf) { uint8_t x, i, j; uint8_t copy[PACKET_LEN]; memcpy(copy, buf, PACKET_LEN); x = (uint8_t)(rand() % PACKET_LEN) + 1; for (j = 0; j < x; j++) { i = (uint8_t)(rand() % PACKET_LEN); if (buf[i] != 0x00) buf[i] = 0x00; else buf[i] = 0xFF; } return compare_buf(buf, copy); } bool method_one(uint8_t *buf) { uint8_t x, i, j; uint8_t copy[PACKET_LEN]; memcpy(copy, buf, PACKET_LEN); x = (uint8_t)(rand() % PACKET_LEN) + 1; for (j = 0; j < x; j++) { i = (uint8_t)(rand() % PACKET_LEN); if (buf[i] != 0xFF) buf[i] = 0xFF; else buf[i] = 0x00; } return compare_buf(buf, copy); } bool method_injection(uint8_t *buf) { uint8_t x, i; uint8_t copy[PACKET_LEN]; memcpy(copy, buf, PACKET_LEN); x = (uint8_t)(rand() % PACKET_LEN); for (i = PACKET_LEN - 1; i > x; i--) { buf[i] = buf[i - 1]; } buf[x] = (uint8_t)rand(); return compare_buf(buf, copy); } bool method_single(uint8_t *buf) { uint8_t x; x = (uint8_t)(rand() % (PACKET_LEN * 8)); buf[(uint8_t)(x / 8)] ^= (1 << (x % 8)); return true; } typedef struct { uint16_t crc1; uint16_t crc2; uint32_t errors; uint16_t (*fn)(uint8_t *data, uint8_t len); char name[32]; } tCRC; typedef struct { bool (*fn)(uint8_t *buf); char name[32]; } tMethod; static tMethod methods[] = { {method_shuffle, "Shuffle"}, {method_bitshift, "Bit shift"}, {method_packetroll, "Roll packet"}, {method_shiftright, "Right shift"}, {method_shiftleft, "Left shift"}, {method_zero, "Fill zeros"}, {method_one, "Fill ones"}, {method_injection, "Byte injection"}, {method_single, "Single bit"} }; static tCRC crcs[] = { {0, 0, 0, crc16_cms, "CMS"}, {0, 0, 0, crc16_ccitt, "CCITT"}, {0, 0, 0, crc16_augccitt, "AUG-CCITT"}, {0, 0, 0, crc16_bypass, "BYPASS"}, {0, 0, 0, crc16_cdma2000, "CDMA2000"}, {0, 0, 0, crc16_dds110, "DDS-110"}, {0, 0, 0, crc16_dect, "DECT-X"}, {0, 0, 0, crc16_en13757, "EN-13757"}, {0, 0, 0, crc16_modbus, "Modbus"}, {0, 0, 0, crc16_t10dif, "T10-DIF"}, {0, 0, 0, crc16_teledisk, "TELEDISK"}, {0, 0, 0, crc16_xmodem, "XMODEM"} }; int main(int argc, char * argv[]) { uint32_t num_of_cycle; uint32_t num_of_sums; uint8_t packet[PACKET_LEN]; uint8_t i; uint8_t m; //uint8_t buf[8] = {0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17}; srand(time(NULL)); printf("------------------------- CRC16 comparison -------------------------\n"); num_of_sums = sizeof(crcs) / sizeof(tCRC); for (m = 0; m < sizeof(methods) / sizeof(tMethod); m++) { printf("\r%s:\n", methods[m].name); for (i = 0; i < num_of_sums; i++) { crcs[i].errors = 0; } for (num_of_cycle = 0; num_of_cycle < NUM_OF_CYCLES; num_of_cycle++) { for (i = 0; i < PACKET_LEN; i++) packet[i] = (uint8_t)rand(); for (i = 0; i < num_of_sums; i++) crcs[i].crc1 = crcs[i].fn(packet, PACKET_LEN); if (!methods[m].fn(packet)) continue; for (i = 0; i < num_of_sums; i++) { crcs[i].crc2 = crcs[i].fn(packet, PACKET_LEN); if (crcs[i].crc1 == crcs[i].crc2) crcs[i].errors++; } if (num_of_cycle % 1000 == 0) printf("\r%.2f%%", (float)num_of_cycle / NUM_OF_CYCLES * 100); } for (i = 0; i < num_of_sums; i++) printf("\r %20s: %10d\n", crcs[i].name, crcs[i].errors); } return 0; }

Como resultado, en la próxima versión del producto para el bus interno, se eligió la suma de verificación CCITT, en mayor medida porque su implementación estaba disponible en el hardware del microcontrolador utilizado.

CRC16 Fiabilidad de suma de comprobación

More articles: