Geekly articles weekly

CRC16校验和可靠性

不久前，当值时，我遇到了一个相当有趣的问题。

我们有一台在内部RS485总线上进行密集交换的设备，每秒传递的数据包数量约为数千，每个数据包长7个字节，其中两个旨在将CRC16校验和存储在其CMS版本中（多项式= 0x8005，起始值= 0xFFFF）。 接收在FIFO缓冲区中进行，FIFO缓冲区在接收到每个后续字节后向上移位并排满。 接收到实际数据包的一个指标是它的校验和与数据包本身中发送的值匹配。 没有标题或其他参数。

问题如下-周期性地（大约每5分钟一次），在数据传输过程中数据包丢失了，该数据包的数据给出了其中一个通道的数据异常值，并且异常值经常出现在相同的值上。 最初，我们着眼于物理冲突的方向，但结果却有所不同-有时会在收集数据的缓冲区中出现一个数据包，该数据包由上一个数据包的末尾和下一个数据包的开始组成，并且这样组合的数据包的校验和被证明是正确的。 也就是说，校验和存在冲突：包没有意义，但是给出了正确的校验和。

自然地，错误已经在系统设计级别，因为软件包没有任何标头，所以引入额外的字节标头将错误数量减少到无法检测的水平，但是在我看来这还不够。 我决定检查不同类型的16位校验和在实际情况下如何彼此不同。 其实，关于这个和这篇文章。

为了进行比较，我选择了一些最常用的16位校验和，其中包含各种多项式，初始值和位到达机制。 下表中汇总了我选择的金额：
代号多项式初始化精炼反驳Xorout
内容管理系统0x80050xFFFF错误的错误的0x0000
贸促会0x10210xFFFF错误的错误的0x0000
奥古斯特0x10210x1D0F错误的错误的0x0000
旁路0x80050x0000错误的错误的0x0000
CDMA20000xC8670xFFFF错误的错误的0x0000
DDS-1100x80050x800D错误的错误的0x0000
DECT-X0x05890x0000错误的错误的0x0000
EN-137570x3D650x0000错误的错误的0xFFFF
Modbus0x80050xFFFF是真的是真的0x0000
T10-DIF0x8BB70x0000错误的错误的0x0000
泰力迪斯克0xA0970x0000错误的错误的0x0000
XMODEM0x10210x0000错误的错误的0x0000

在这种情况下：

  • RefIn-来自数据缓冲区的位到达顺序：false-从最高有效位开始（MSB在先），true-LSB在先；
  • RefOut-反转输出位顺序的标志：true-反转。

模拟数据包损坏时，我实现了以下模型：

  • 随机播放：使用随机值填充数据包中的随机字节数
  • 位移：将数据包中的随机字节向左移动
  • 滚动分组：分组中的环形字节向左移动
  • 右移：数据包向右移动一个字节，向左添加0xFF（通过UART传输）
  • 左移：将数据包向左移动一个字节，向右添加0xFF
  • 填充零：使用0x00字节（全零）填充数据包中的随机字节数
  • 填充1：用0xFF字节（所有单位）填充数据包中的随机字节数
  • 字节注入：将随机字节随机插入到数据包中，插入后的字节向尾移动
  • 一位：损坏一个随机位

然后，该程序随机生成1亿个数据包，每个数据包均执行上述操作，然后对原始和升级包的校验和进行比较。 转换期间未更改的数据包将被丢弃。 如果校验和匹配，则会记录错误。

结果，获得具有错误数量的下表：
代号随机播放位移卷包右移左移填零填一个字节注入求和
内容管理系统5101387429371439168839704010108024099
贸促会2012年112733201494148610631096113012728
奥古斯特2012年112733201494148610631096113012728
旁路5101387429371439168839704010108024099
CDMA2000136810251946年1462167810431028111210662
DDS-1105101387429371439168839704010108024099
DECT-X1432118959151779158012151209109315412
EN-137571281220930431520152821932187103915,000
Modbus5090388830861282158239473897107323845
T10-DIF139092214241421163099493810939812
泰力迪斯克1394104953981451151210961066106514031
XMODEM2012年112733201494148610631096113012728

显然，该算法的起始值不会以任何方式影响结果，这是合乎逻辑的，该起始值仅给我们提供了不同的校验和值，但是计算机制本身却没有任何变化。 因此，我不再考虑这些校验和。 同样，以单个位考虑错误是没有意义的，所有校验和均无误地对此进行了应对，实际上，这是在创建过程中对它们的要求。

好吧，校验和的最终质量表已经不考虑重复算法了：
代号碰撞次数地点
内容管理系统240998
贸促会127283
CDMA2000106622
DECT-X154126
EN-1375715,0005
Modbus238457
T10-DIF98121个
泰力迪斯克140314

我将其余结论留给读者。 我仅从自己身上注意到，校验和多项式中的单位数对结果有一定影响。 但这只是我个人的主观意见。 我很高兴听到其他解释。

该程序的源代码如下。

源代码
#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校验和，因为它的实现可在所用微控制器的硬件中找到。

Source: https://habr.com/ru/post/zh-CN428746/

More articles:


All Articles