Надежность контрольной суммы CRC16

Не так давно по долгу службы столкнулся с довольно интересной проблемой.

У нас имеется устройство, которое осуществляет интенсивный обмен по внутренней шине RS485, число проходящих пакетов составляет порядка нескольких тысяч в секунду, каждый пакет имеет длину в 7 байт, два из которых предназначены для хранения контрольной суммы CRC16 в ее CMS варианте (полином = 0x8005, стартовое значение = 0xFFFF). Прием осуществляется в FIFO-буфер, который сдвигается вверх с вытеснением после приема каждого последующего байта. Индикатором получения реального пакета является факт совпадения его контрольной суммы со значением, переданным в самом пакете. Никаких заголовков или дополнительных параметров.

Проблема заключалась в следующем – периодически, примерно раз в 5 минут, при передаче данных проскакивал пакет, данные которого давали выброс данных для одного из каналов, причем чаще всего выброс происходил до одного и того же значения. Сначала мы смотрели в сторону физических коллизий, но дело оказалось в другом – время от времени в буфере, где собирались полученные данные, оказывался пакет, состоящий из конца предыдущего пакета и начала следующего, причем контрольная сумма у такого комбинированного пакета оказывалась верной. То есть, налицо коллизия контрольной суммы: пакет не имеет смысла, но дает верную контрольную сумму.

Естественно, ошибка была уже на уровне проектирования системы, так как у пакетов не было никаких заголовков, введение дополнительного байта-заголовка свело количество ошибок до недетектируемого уровня, но этого мне показалось мало. Я решил проверить, насколько различные виды 16-битных контрольных сумм отличаются друг от друга в реальных условиях. Собственно, об этом и статья.

Для сравнения я выбрал несколько наиболее часто используемых 16-битных контрольных сумм с различными полиномами, стартовыми значениями и механизмом поступления битов. Выбранные мной суммы сведены в следующую таблицу:

Обозначение Polynomial Init RefIn RefOut XorOut
CMS 0x8005 0xFFFF false false 0x0000
CCITT 0x1021 0xFFFF false false 0x0000
AUG-CCITT 0x1021 0x1D0F false false 0x0000
BYPASS 0x8005 0x0000 false false 0x0000
CDMA2000 0xC867 0xFFFF false false 0x0000
DDS-110 0x8005 0x800D false false 0x0000
DECT-X 0x0589 0x0000 false false 0x0000
EN-13757 0x3D65 0x0000 false false 0xFFFF
Modbus 0x8005 0xFFFF true true 0x0000
T10-DIF 0x8BB7 0x0000 false false 0x0000
TELEDISK 0xA097 0x0000 false false 0x0000
XMODEM 0x1021 0x0000 false false 0x0000

В данном случае:

  • RefIn — порядок поступления битов из буфера данных: false — начиная со старшего значащего бита (MSB first), true – LSB first;
  • RefOut – признак инвертирования порядка битов на выходе: true – инвертировать.

При эмуляции повреждения пакетов я реализовал следующие модели:

  • Shuffle: заполнение случайного количества байт в пакете случайными значениями
  • Bit shift: сдвиг случайных байт в пакете влево
  • Roll packet: кольцевой сдвиг байт в пакете влево
  • Right shift: сдвиг пакета вправо на один байт, слева дописывается 0xFF (передача идет посредством UART)
  • Left shift: сдвиг пакета влево на один байт, справа дописывается 0xFF
  • Fill zeros: заполнение случайного количества байт в пакете байтами 0x00 (все нули)
  • Fill ones: заполнение случайного количества байт в пакете байтами 0xFF (все единицы)
  • Byte injection: вставка в пакет случайного байта в случайном месте, байты за вставленным сдвигаются в направлении хвоста
  • Single bit: повреждение единственного случайного бита

Затем программой были сгенерированы случайным образом 100.000.000 пакетов, над каждым из них была проведена указанные выше операции, после чего сравнивались контрольные суммы исходного и модернизированного пакета. Пакеты, которые не изменились при преобразовании, отбрасывались. Если контрольная сумма совпадала, то регистрировалась ошибка.

В итоге была получена следующая таблица с количеством ошибок:

Обозначение Shuffle Bit shift Roll packet Right shift Left shift Fill zeros Fill ones Byte injection Sum
CMS 5101 3874 2937 1439 1688 3970 4010 1080 24099
CCITT 2012 1127 3320 1494 1486 1063 1096 1130 12728
AUG-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 15000
Modbus 5090 3888 3086 1282 1582 3947 3897 1073 23845
T10-DIF 1390 922 1424 1421 1630 994 938 1093 9812
TELEDISK 1394 1049 5398 1451 1512 1096 1066 1065 14031
XMODEM 2012 1127 3320 1494 1486 1063 1096 1130 12728

Очевидно, что стартовое значение алгоритма никак не влияет на полученный результат, что логично, стартовое значение дает нам лишь иное значение контрольной суммы, но сам механизм расчета никак не меняется. Поэтому эти контрольные суммы я исключил из дальнейшего рассмотрения. Точно так же не имеет смысла рассматривать ошибки в одиночных битах, все контрольные суммы справились с этим безошибочно, что, собственно, от них и требовалось при создании.

Ну и итоговая таблица качества контрольной суммы, уже без учета дублирующих алгоритмов:

Обозначение Number of collisions Place
CMS 24099 8
CCITT 12728 3
CDMA2000 10662 2
DECT-X 15412 6
EN-13757 15000 5
Modbus 23845 7
T10-DIF 9812 1
TELEDISK 14031 4

Остальные выводы оставляю читателям. От себя замечу лишь, что определенное влияние на результаты оказывает число единиц в полиноме контрольной суммы. Но это всего лишь мое личное субъективное мнение. Буду рад выслушать иные объяснения.

Исходный код программы приведен ниже.

Исходный код

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

В итоге в следующей версии изделия для внутренней шины была выбрана контрольная сумма CCITT, в большей степени потому, что ее реализация была доступна в аппаратной части используемого микроконтроллера.

FavoriteLoadingДобавить в избранное
Posted in Без рубрики

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *