Geekly articles weekly

Confiabilidade da soma de verificação CRC16

Há não muito tempo, em serviço, encontrei um problema bastante interessante.

Temos um dispositivo que realiza trocas intensivas no barramento interno RS485, o número de pacotes que passa é de vários milhares por segundo, cada pacote tem 7 bytes de comprimento, dois dos quais são projetados para armazenar a soma de verificação CRC16 em sua versão CMS (polinomial = 0x8005, valor inicial = 0xFFFF). A recepção é realizada no buffer FIFO, que muda para cima com a exclusão após a recepção de cada byte subsequente. Um indicador de recebimento de um pacote real é o fato de sua soma de verificação corresponder ao valor transmitido no próprio pacote. Sem cabeçalhos ou parâmetros adicionais.

O problema era o seguinte - periodicamente, uma vez a cada 5 minutos, um pacote escorregava durante a transferência de dados, cujos dados davam um valor externo a um dos canais e, na maioria das vezes, o valor externo ocorria com o mesmo valor. Inicialmente, olhamos na direção das colisões físicas, mas as coisas eram diferentes - de tempos em tempos no buffer em que os dados eram coletados, um pacote aparecia consistindo no final do pacote anterior e no início do próximo, e a soma de verificação de um pacote combinado era a correta. Ou seja, há uma colisão da soma de verificação: o pacote não faz sentido, mas fornece a soma de verificação correta.

Naturalmente, o erro já estava no nível de design do sistema, uma vez que os pacotes não tinham nenhum cabeçalho, a introdução de um cabeçalho de byte adicional reduziu o número de erros a um nível indetectável, mas isso me pareceu insuficiente. Decidi verificar como os diferentes tipos de somas de verificação de 16 bits diferem entre si em condições reais. Na verdade, sobre isso e o artigo.

Para comparação, selecionei algumas das somas de verificação de 16 bits mais usadas com vários polinômios, valores iniciais e o mecanismo para receber bits. Os valores que selecionei estão resumidos na tabela a seguir:
DesignaçãoPolinomialInitRefinRefoutXorout
CMS0x80050xFFFFfalsafalsa0x0000
CCITT0x10210xFFFFfalsafalsa0x0000
AUG-CCITT0x10210x1D0Ffalsafalsa0x0000
BYPASS0x80050x0000falsafalsa0x0000
CDMA20000xC8670xFFFFfalsafalsa0x0000
DDS-1100x80050x800Dfalsafalsa0x0000
DECT-X0x05890x0000falsafalsa0x0000
EN-137570x3D650x0000falsafalsa0xFFFF
Modbus0x80050xFFFFverdadeverdade0x0000
T10-DIF0x8BB70x0000falsafalsa0x0000
TELEDISK0xA0970x0000falsafalsa0x0000
XMODEM0x10210x0000falsafalsa0x0000

Nesse caso:

  • RefIn - a ordem de chegada dos bits do buffer de dados: false - começando com o bit mais significativo (MSB primeiro), true - LSB primeiro;
  • RefOut - flag de inverter a ordem dos bits na saída: true - invert.

Ao emular a corrupção de pacotes, implementei os seguintes modelos:

  • Aleatório: preenchimento de número aleatório de bytes em um pacote com valores aleatórios
  • Mudança de bit: muda bytes aleatórios em um pacote para a esquerda
  • Pacote de rolo: deslocamento de anel em byte no pacote para a esquerda
  • Deslocamento à direita: deslocamento de pacotes para a direita em um byte, 0xFF é adicionado à esquerda (a transmissão é via UART)
  • Deslocamento para a esquerda : desloque o pacote para a esquerda em um byte, 0xFF é adicionado à direita
  • Preencher zeros: preencher um número aleatório de bytes em um pacote com 0x00 bytes (todos os zeros)
  • Preencher os: preencher um número aleatório de bytes em um pacote com 0xFF bytes (todas as unidades)
  • Injeção de byte: insira um byte aleatório em um pacote em um local aleatório, os bytes após o inserido são deslocados na direção da cauda
  • Bit único: dano a um único bit aleatório

Em seguida, o programa gerou aleatoriamente 100.000.000 pacotes, cada um deles executando as operações acima, após o qual as somas de verificação dos pacotes originais e modernizados foram comparadas. Pacotes que não foram alterados durante a conversão foram descartados. Se a soma de verificação corresponder, um erro será registrado.

Como resultado, a tabela a seguir foi obtida com o número de erros:
DesignaçãoAleatórioMudança de bitPacote de roloDeslocamento à direitaTurno esquerdoPreencher zerosPreencha osInjeção de byteSoma
CMS5101387429371439168839704010108024099
CCITT2012112733201494148610631096113012728
AUG-CCITT2012112733201494148610631096113012728
BYPASS5101387429371439168839704010108024099
CDMA20001368102519461462167810431028111210662
DDS-1105101387429371439168839704010108024099
DECT-X1432118959151779158012151209109315412
EN-137571281220930431520152821932187103915.000
Modbus5090388830861282158239473897107323845
T10-DIF139092214241421163099493810939812
TELEDISK1394104953981451151210961066106514031
XMODEM2012112733201494148610631096113012728

Obviamente, o valor inicial do algoritmo não afeta o resultado de forma alguma, o que é lógico, o valor inicial nos fornece apenas um valor diferente da soma de verificação, mas o mecanismo de cálculo em si não muda de forma alguma. Portanto, excluí essas somas de verificação de uma análise mais aprofundada. Da mesma forma, não faz sentido considerar erros em bits únicos, todas as somas de verificação lidaram com isso sem erros, o que, de fato, era exigido deles durante a criação.

Bem, a tabela de qualidade final da soma de verificação, já sem levar em conta algoritmos duplicados:
DesignaçãoNúmero de colisõesLocal
CMS240998
CCITT127283
CDMA2000106622
DECT-X154126
EN-1375715.0005
Modbus238457
T10-DIF98121
TELEDISK140314

Deixo as conclusões restantes para os leitores. Observo apenas que o número de unidades no polinômio da soma de verificação tem um certo efeito nos resultados. Mas esta é apenas a minha opinião subjetiva pessoal. Ficarei feliz em ouvir outras explicações.

O código fonte do programa é fornecido abaixo.

Código fonte
#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; }


Como resultado, na próxima versão do produto para o barramento interno, a soma de verificação CCITT foi escolhida, em maior medida porque sua implementação estava disponível no hardware do microcontrolador usado.

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

More articles:


All Articles