Geekly articles weekly

Keandalan CRC16 Checksum

Belum lama ini, saat bertugas, saya mengalami masalah yang agak menarik.

Kami memiliki perangkat yang bertukar secara intensif melalui bus RS485 internal, jumlah paket yang lewat sekitar beberapa ribu per detik, masing-masing paket panjangnya 7 byte, dua di antaranya dirancang untuk menyimpan CRC16 checksum dalam versi CMS-nya (polinomial = 0x8005, nilai awal = 0xFFFF). Penerimaan dilakukan dalam buffer FIFO, yang bergeser ke atas dengan crowding out setelah penerimaan setiap byte berikutnya. Indikator menerima paket nyata adalah kenyataan bahwa checksumnya cocok dengan nilai yang dikirimkan dalam paket itu sendiri. Tidak ada tajuk atau parameter tambahan.

Masalahnya adalah sebagai berikut - secara berkala, sekitar sekali setiap 5 menit, ketika mentransmisikan data, sebuah paket menyelinap, data yang memberikan pencilan data untuk salah satu saluran, dan paling sering pencilan terjadi pada nilai yang sama. Pada awalnya, kami melihat ke arah tabrakan fisik, tetapi ternyata berbeda - dari waktu ke waktu di buffer di mana data dikumpulkan, muncul paket yang terdiri dari akhir paket sebelumnya dan awal berikutnya, dan checksum dari paket gabungan tersebut ternyata benar. Artinya, ada tabrakan checksum: paket tidak masuk akal, tetapi memberikan checksum yang benar.

Tentu saja, kesalahan sudah ada pada level desain sistem, karena paket-paket tidak memiliki header, pengenalan header byte tambahan mengurangi jumlah kesalahan ke level yang tidak terdeteksi, tetapi bagi saya ini tampaknya tidak cukup. Saya memutuskan untuk memeriksa bagaimana perbedaan jenis checksum 16-bit berbeda satu sama lain dalam kondisi nyata. Sebenarnya, tentang ini dan artikelnya.

Sebagai perbandingan, saya memilih beberapa checksum 16-bit yang paling umum digunakan dengan berbagai polinomial, nilai awal, dan mekanisme untuk menerima bit. Jumlah yang saya pilih dirangkum dalam tabel berikut:
PenunjukanPolinomialInitSempurnakanRefoutXorout
CMS0x80050xFFFFsalahsalah0x0000
CCITT0x10210xFFFFsalahsalah0x0000
AGUSTUS-CCITT0x10210x1D0Fsalahsalah0x0000
BYPASS0x80050x0000salahsalah0x0000
CDMA20000xC8670xFFFFsalahsalah0x0000
DDS-1100x80050x800Dsalahsalah0x0000
DECT-X0x05890x0000salahsalah0x0000
ID-137570x3D650x0000salahsalah0xFFFF
Modbus0x80050xFFFFbenarbenar0x0000
T10-DIF0x8BB70x0000salahsalah0x0000
TELEDISK0xA0970x0000salahsalah0x0000
XMODEM0x10210x0000salahsalah0x0000

Dalam hal ini:

  • RefIn - urutan kedatangan bit dari buffer data: false - dimulai dengan bit paling signifikan (MSB pertama), true - LSB pertama;
  • RefOut - flag untuk membalik urutan bit pada output: true - invert.

Ketika meniru korupsi paket, saya menerapkan model berikut:

  • Acak: mengisi jumlah byte acak dalam suatu paket dengan nilai acak
  • Bit shift: menggeser byte acak dalam sebuah paket ke kiri
  • Paket roll: menggeser byte cincin dalam paket ke kiri
  • Pergeseran kanan: pergeseran paket ke kanan dengan satu byte, 0xFF ditambahkan ke kiri (transmisi melalui UART)
  • Shift kiri: menggeser paket ke kiri sebanyak satu byte, 0xFF ditambahkan ke kanan
  • Isi nol: mengisi jumlah byte acak dalam suatu paket dengan 0x00 byte (semua nol)
  • Isi yang: mengisi jumlah byte acak dalam suatu paket dengan 0xFF byte (semua unit)
  • Injeksi byte: memasukkan byte acak ke dalam paket di tempat acak, byte setelah dimasukkan digeser ke arah ekor
  • Bit tunggal: kerusakan pada bit acak tunggal

Kemudian, program secara acak menghasilkan 100.000.000 paket, masing-masing dari mereka melakukan operasi di atas, setelah itu checksum dari paket asli dan modern dibandingkan. Paket yang tidak berubah selama konversi dibuang. Jika checksum cocok, kesalahan dicatat.

Hasilnya, tabel berikut ini diperoleh dengan jumlah kesalahan:
PenunjukanAcakPergeseran sedikitGulung paketPergeseran kananPergeseran ke kiriIsi nolIsi yangInjeksi byteJumlah
CMS5101387429371439168839704010108024099
CCITT2012112733201494148610631096113012728
AGUSTUS-CCITT2012112733201494148610631096113012728
BYPASS5101387429371439168839704010108024099
CDMA20001368102519461462167810431028111210662
DDS-1105101387429371439168839704010108024099
DECT-X1432118959151779158012151209109315412
ID-137571281220930431520152821932187103915.000
Modbus5090388830861282158239473897107323845
T10-DIF139092214241421163099493810939812
TELEDISK1394104953981451151210961066106514031
XMODEM2012112733201494148610631096113012728

Jelas, nilai awal dari algoritma tidak mempengaruhi hasil dengan cara apa pun, yang logis, nilai awal hanya memberi kita nilai yang berbeda dari checksum, tetapi mekanisme perhitungan itu sendiri tidak berubah dengan cara apa pun. Karena itu, saya mengecualikan checksum ini dari pertimbangan lebih lanjut. Dengan cara yang sama, tidak masuk akal untuk mempertimbangkan kesalahan dalam bit tunggal, semua checksum mengatasi ini tanpa kesalahan, yang, pada kenyataannya, dituntut dari mereka selama pembuatan.

Nah, tabel kualitas final checksum, sudah tanpa memperhitungkan algoritma duplikat akun:
PenunjukanJumlah tabrakanTempat
CMS240998
CCITT127283
CDMA2000106622
DECT-X154126
ID-1375715.0005
Modbus238457
T10-DIF98121
TELEDISK140314

Saya menyerahkan kesimpulan yang tersisa kepada pembaca. Saya hanya mencatat dari diri saya sendiri bahwa jumlah unit dalam polinomial checksum memiliki efek tertentu pada hasilnya. Tapi ini hanya pendapat subjektif pribadi saya. Saya akan senang mendengar penjelasan lain.

Kode sumber program diberikan di bawah ini.

Kode sumber
#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; }


Akibatnya, dalam versi produk berikutnya untuk bus internal, CCITT checksum dipilih, untuk tingkat yang lebih besar karena implementasinya tersedia dalam perangkat keras mikrokontroler yang digunakan.

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

More articles:


All Articles