Geekly articles weekly

Zuverlässigkeit der CRC16-Prüfsumme

Vor nicht allzu langer Zeit stieß ich im Dienst auf ein ziemlich interessantes Problem.

Wir haben ein Gerät, das einen intensiven Austausch auf dem internen RS485-Bus durchführt. Die Anzahl der übertragenen Pakete beträgt ungefähr mehrere Tausend pro Sekunde. Jedes Paket ist 7 Byte lang. Zwei davon dienen zum Speichern der CRC16-Prüfsumme in ihrer CMS-Version (Polynom = 0x8005, Startwert = 0xFFFF). Der Empfang erfolgt im FIFO-Puffer, der sich nach dem Empfang jedes nachfolgenden Bytes mit Verdrängung nach oben verschiebt. Ein Indikator für den Empfang eines realen Pakets ist die Tatsache, dass seine Prüfsumme mit dem im Paket selbst übertragenen Wert übereinstimmt. Keine Header oder zusätzlichen Parameter.

Das Problem war wie folgt: In regelmäßigen Abständen, etwa alle 5 Minuten, rutschte während der Datenübertragung ein Paket aus, dessen Daten einen Datenausreißer für einen der Kanäle ergaben, und meistens trat der Ausreißer mit demselben Wert auf. Zuerst haben wir in Richtung physischer Kollisionen geschaut, aber es stellte sich anders heraus - von Zeit zu Zeit erschien in dem Puffer, in dem die Daten gesammelt wurden, ein Paket, das aus dem Ende des vorherigen Pakets und dem Anfang des nächsten bestand, und die Prüfsumme eines solchen kombinierten Pakets erwies sich als korrekt. Das heißt, es gibt eine Kollision der Prüfsumme: Das Paket macht keinen Sinn, gibt aber die richtige Prüfsumme an.

Natürlich lag der Fehler bereits auf der Ebene des Systemdesigns, da die Pakete keine Header hatten. Die Einführung eines zusätzlichen Byte-Headers reduzierte die Anzahl der Fehler auf ein nicht nachweisbares Niveau, aber dies schien mir nicht genug zu sein. Ich habe mich entschlossen zu prüfen, wie sich verschiedene Arten von 16-Bit-Prüfsummen unter realen Bedingungen voneinander unterscheiden. Eigentlich darüber und über den Artikel.

Zum Vergleich habe ich einige der am häufigsten verwendeten 16-Bit-Prüfsummen mit verschiedenen Polynomen, Startwerten und dem Mechanismus zum Empfangen von Bits ausgewählt. Die von mir ausgewählten Beträge sind in der folgenden Tabelle zusammengefasst:
BezeichnungPolynomInitRefinRefoutXorout
CMS0x80050xFFFFfalschfalsch0x0000
CCITT0x10210xFFFFfalschfalsch0x0000
AUG-CCITT0x10210x1D0Ffalschfalsch0x0000
BYPASS0x80050x0000falschfalsch0x0000
CDMA20000xC8670xFFFFfalschfalsch0x0000
DDS-1100x80050x800Dfalschfalsch0x0000
DECT-X0x05890x0000falschfalsch0x0000
EN-137570x3D650x0000falschfalsch0xFFFF
Modbus0x80050xFFFFwahrwahr0x0000
T10-DIF0x8BB70x0000falschfalsch0x0000
TELEDISK0xA0970x0000falschfalsch0x0000
XMODEM0x10210x0000falschfalsch0x0000

In diesem Fall:

  • RefIn - die Reihenfolge des Eintreffens von Bits aus dem Datenpuffer: false - beginnend mit dem höchstwertigen Bit (MSB zuerst), true - LSB zuerst;
  • RefOut - Flag zum Invertieren der Bitreihenfolge am Ausgang: true - invertieren.

Bei der Emulation von Paketbeschädigungen habe ich die folgenden Modelle implementiert:

  • Mischen: Füllen einer zufälligen Anzahl von Bytes in einem Paket mit zufälligen Werten
  • Bitverschiebung: Verschieben Sie zufällige Bytes in einem Paket nach links
  • Paket rollen: Ringbyte-Verschiebung im Paket nach links
  • Rechtsverschiebung: Paketverschiebung um ein Byte nach rechts, 0xFF wird nach links hinzugefügt (Übertragung erfolgt über UART)
  • Linksverschiebung : Verschieben Sie das Paket um ein Byte nach links. 0xFF wird nach rechts hinzugefügt
  • Nullen füllen : Füllen einer zufälligen Anzahl von Bytes in einem Paket mit 0x00 Bytes (alle Nullen)
  • Füllen Sie eine: Füllen Sie eine zufällige Anzahl von Bytes in einem Paket mit 0xFF-Bytes (alle Einheiten).
  • Byte-Injection: Fügen Sie ein zufälliges Byte an einer zufälligen Stelle in ein Paket ein. Die Bytes nach dem Einfügen werden in Schwanzrichtung verschoben
  • Einzelbit: Schaden an einem einzelnen Zufallsbit

Dann erzeugte das Programm zufällig 100.000.000 Pakete, von denen jedes die obigen Operationen ausführte, wonach die Prüfsummen der ursprünglichen und aktualisierten Pakete verglichen wurden. Pakete, die sich während der Konvertierung nicht geändert haben, wurden verworfen. Wenn die Prüfsumme übereinstimmt, wird ein Fehler protokolliert.

Als Ergebnis wurde die folgende Tabelle mit der Anzahl der Fehler erhalten:
BezeichnungMischeBitverschiebungRollenpaketRechtsverschiebungLinksverschiebungFüllen Sie NullenFülle diejenigenByte-InjektionSumme
CMS5101387429371439168839704010108024099
CCITT2012112733201494148610631096113012728
AUG-CCITT2012112733201494148610631096113012728
BYPASS5101387429371439168839704010108024099
CDMA20001368102519461462167810431028111210662
DDS-1105101387429371439168839704010108024099
DECT-X1432118959151779158012151209109315412
EN-137571281220930431520152821932187103915.000
Modbus5090388830861282158239473897107323845
T10-DIF139092214241421163099493810939812
TELEDISK1394104953981451151210961066106514031
XMODEM2012112733201494148610631096113012728

Offensichtlich beeinflusst der Startwert des Algorithmus das Ergebnis in keiner Weise, was logisch ist. Der Startwert gibt uns nur einen anderen Wert der Prüfsumme, aber der Berechnungsmechanismus selbst ändert sich in keiner Weise. Daher habe ich diese Prüfsummen von weiteren Überlegungen ausgeschlossen. Ebenso macht es keinen Sinn, Fehler in einzelnen Bits zu betrachten, wobei alle Prüfsummen fehlerfrei damit fertig wurden, was tatsächlich bei der Erstellung von ihnen verlangt wurde.

Nun, die endgültige Qualitätstabelle der Prüfsumme, bereits ohne Berücksichtigung doppelter Algorithmen:
BezeichnungAnzahl der KollisionenPlatzieren
CMS240998
CCITT127283
CDMA2000106622
DECT-X154126
EN-1375715.0005
Modbus238457
T10-DIF98121
TELEDISK140314

Die restlichen Schlussfolgerungen überlasse ich den Lesern. Ich stelle nur von mir selbst fest, dass die Anzahl der Einheiten im Prüfsummenpolynom einen gewissen Einfluss auf die Ergebnisse hat. Dies ist jedoch nur meine persönliche subjektive Meinung. Ich werde mich über weitere Erklärungen freuen.

Der Quellcode des Programms ist unten angegeben.

Quellcode
#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; }


Infolgedessen wurde in der nächsten Version des Produkts für den internen Bus die CCITT-Prüfsumme in größerem Umfang gewählt, da ihre Implementierung in der Hardware des verwendeten Mikrocontrollers verfügbar war.

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

More articles:


All Articles