Geekly articles weekly

Fiabilité du total de contrôle CRC16

Il n'y a pas si longtemps, en service, je suis tombé sur un problème assez intéressant.

Nous avons un appareil qui échange intensivement via le bus RS485 interne, le nombre de paquets passant est d'environ plusieurs milliers par seconde, chaque paquet fait 7 octets de long, dont deux sont conçus pour stocker la somme de contrôle CRC16 dans sa version CMS (polynôme = 0x8005, valeur de départ = 0xFFFF). La réception est effectuée dans le tampon FIFO, qui se déplace vers le haut avec éviction après réception de chaque octet suivant. Un indicateur de la réception d'un vrai paquet est le fait que sa somme de contrôle correspond à la valeur transmise dans le paquet lui-même. Pas d'en-têtes ou de paramètres supplémentaires.

Le problème était le suivant - périodiquement, environ une fois toutes les 5 minutes, lors de la transmission de données, un paquet a glissé, dont les données ont donné une valeur aberrante pour l'un des canaux, et le plus souvent, la valeur aberrante s'est produite à la même valeur. Au début, nous avons regardé dans le sens des collisions physiques, mais cela s'est avéré différent - de temps en temps dans le tampon où les données ont été collectées, il est apparu un paquet composé de la fin du paquet précédent et du début du suivant, et la somme de contrôle d'un tel paquet combiné s'est avérée correcte. Autrement dit, il y a une collision de la somme de contrôle: le package n'a pas de sens, mais donne la somme de contrôle correcte.

Naturellement, l'erreur était déjà au niveau de la conception du système, car les packages n'avaient pas d'en-tête, l'introduction d'un en-tête d'octet supplémentaire a réduit le nombre d'erreurs à un niveau indétectable, mais cela ne m'a pas semblé suffisant. J'ai décidé de vérifier en quoi les différents types de sommes de contrôle 16 bits diffèrent les uns des autres dans des conditions réelles. En fait, à ce sujet et l'article.

À titre de comparaison, j'ai sélectionné certaines des sommes de contrôle 16 bits les plus couramment utilisées avec divers polynômes, valeurs de départ et le mécanisme de réception des bits. Les montants que j'ai sélectionnés sont résumés dans le tableau suivant:
DésignationPolynômeInitRaffinerRefoutXorout
CMS0x80050xFFFFfauxfaux0x0000
CCITT0x10210xFFFFfauxfaux0x0000
AUG-CCITT0x10210x1D0Ffauxfaux0x0000
BYPASS0x80050x0000fauxfaux0x0000
CDMA20000xC8670xFFFFfauxfaux0x0000
DDS-1100x80050x800Dfauxfaux0x0000
DECT-X0x05890x0000fauxfaux0x0000
EN-137570x3D650x0000fauxfaux0xFFFF
Modbus0x80050xFFFFvraivrai0x0000
T10-DIF0x8BB70x0000fauxfaux0x0000
TELEDISK0xA0970x0000fauxfaux0x0000
XMODEM0x10210x0000fauxfaux0x0000

Dans ce cas:

  • RefIn - l'ordre d'arrivée des bits du tampon de données: faux - en commençant par le bit le plus significatif (MSB en premier), vrai - LSB en premier;
  • RefOut - drapeau d'inversion de l'ordre des bits en sortie: true - invert.

Lors de l'émulation de la corruption de paquets, j'ai implémenté les modèles suivants:

  • Shuffle: remplir un nombre aléatoire d'octets dans un paquet avec des valeurs aléatoires
  • Décalage de bits: décaler les octets aléatoires dans un paquet vers la gauche
  • Roll packet: décalage de l'octet en anneau dans le paquet vers la gauche
  • Décalage à droite: décalage des paquets vers la droite d'un octet, 0xFF est ajouté à gauche (la transmission se fait via UART)
  • Décalage à gauche: décale le paquet vers la gauche d'un octet, 0xFF est ajouté à droite
  • Remplir les zéros: remplir un nombre aléatoire d'octets dans un paquet avec 0x00 octets (tous les zéros)
  • Fill ones: remplir un nombre aléatoire d'octets dans un paquet avec 0xFF octets (toutes les unités)
  • Injection d'octets: insérez un octet aléatoire dans un paquet dans un endroit aléatoire, les octets après l'inséré sont décalés dans la direction de la queue
  • Bit unique: endommagement d'un seul bit aléatoire

Ensuite, le programme a généré au hasard 100 000 000 de paquets, chacun d'eux a effectué les opérations ci-dessus, après quoi les sommes de contrôle des packages d'origine et mis à niveau ont été comparées. Les paquets qui n'ont pas changé pendant la conversion ont été jetés. Si la somme de contrôle correspond, une erreur est enregistrée.

Par conséquent, le tableau suivant a été obtenu avec le nombre d'erreurs:
DésignationShuffleDécalage de bitsPaquet de rouleauxDécalage à droiteDécalage à gaucheRemplir les zérosRemplissez ceuxInjection d'octetsSomme
CMS5101387429371439168839704010108024099
CCITT2012112733201494148610631096113012728
AUG-CCITT2012112733201494148610631096113012728
BYPASS5101387429371439168839704010108024099
CDMA20001368102519461462167810431028111210662
DDS-1105101387429371439168839704010108024099
DECT-X1432118959151779158012151209109315412
EN-137571281220930431520152821932187103915 000
Modbus5090388830861282158239473897107323845
T10-DIF139092214241421163099493810939812
TELEDISK1394104953981451151210961066106514031
XMODEM2012112733201494148610631096113012728

Évidemment, la valeur de départ de l'algorithme n'affecte en rien le résultat, ce qui est logique, la valeur de départ ne nous donne qu'une valeur différente de la somme de contrôle, mais le mécanisme de calcul lui-même ne change en aucune façon. Par conséquent, j'ai exclu ces sommes de contrôle de tout examen ultérieur. De la même manière, cela n'a aucun sens de considérer les erreurs en bits simples, toutes les sommes de contrôle y ont fait face sans erreur, ce qui, en fait, leur était demandé lors de la création.

Eh bien, la table de qualité finale de la somme de contrôle, déjà sans tenir compte des algorithmes en double:
DésignationNombre de collisionsLieu
CMS240998
CCITT127283
CDMA2000106622
DECT-X154126
EN-1375715 0005
Modbus238457
T10-DIF98121
TELEDISK140314

Je laisse les conclusions restantes aux lecteurs. Je note seulement de moi-même que le nombre d'unités dans le polynôme de somme de contrôle a un certain effet sur les résultats. Mais ce n'est que mon opinion subjective personnelle. Je serai heureux d'entendre d'autres explications.

Le code source du programme est donné ci-dessous.

Code source
#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; }


En conséquence, dans la prochaine version du produit pour le bus interne, la somme de contrôle CCITT a été choisie, dans une plus large mesure parce que son implémentation était disponible dans le matériel du microcontrôleur utilisé.

Source: https://habr.com/ru/post/fr428746/

More articles:


All Articles