Функция для вычисления контрольной суммы CRC16

Я работаю над библиотекой, чтобы обеспечить простую надежную связь через соединение RS232 или RS485. Часть этого кода включает использование контрольной суммы CRC16 для данных, чтобы обнаружить повреждение от линейного шума. Я создал функцию для вычисления контрольной суммы CRC16, но, похоже, она не выводит правильные значения.

Соответствующий код, который я написал, можно найти здесь.

Я проверяю свой результат на этот онлайн-калькулятор CRC.

Я пришел к выводу, что либо мое понимание того, как вычислять CRC16, является неправильным, либо онлайн-калькулятор ошибочным (первое кажется более вероятным). Может ли кто-нибудь сказать мне, где я могу ошибиться?

Ответы

Ответ 1

Есть несколько деталей, которые вам нужно "совместить" для конкретной реализации CRC. Даже при использовании одного и того же полинома могут быть разные результаты из-за незначительных различий в том, как обрабатываются биты данных, используя определенное начальное значение для CRC (иногда это ноль, иногда 0xffff) и/или инвертирование бит CRC. Например, иногда одна реализация будет работать из младших бит байтов данных, тогда как иногда они будут работать с битами верхнего порядка вниз (как это делается в настоящее время).

Кроме того, вам нужно "вытолкнуть" последние бит CRC после запуска всех бит данных.

Имейте в виду, что алгоритмы CRC были разработаны для аппаратного обеспечения, поэтому некоторые из способов обработки битового заказа могут не иметь особого смысла с точки зрения программного обеспечения.

Если вы хотите сопоставить CRC16 с полиномом 0x8005, как показано на странице калькулятора CRM lammertbies.nl, вам необходимо внести следующие изменения в функцию CRC:

  • a) запускать биты данных через цикл CRC, начиная с младшего значащего бита, а не из самого значащего бита
  • b) вытащите последние 16 бит CRC из регистра CRC после того, как вы закончили с входными данными.
  • c) отменить бит CRC (я предполагаю, что этот бит переносится с аппаратных реализаций)

Итак, ваша функция может выглядеть так:

#define CRC16 0x8005

uint16_t gen_crc16(const uint8_t *data, uint16_t size)
{
    uint16_t out = 0;
    int bits_read = 0, bit_flag;

    /* Sanity check: */
    if(data == NULL)
        return 0;

    while(size > 0)
    {
        bit_flag = out >> 15;

        /* Get next bit: */
        out <<= 1;
        out |= (*data >> bits_read) & 1; // item a) work from the least significant bits

        /* Increment bit counter: */
        bits_read++;
        if(bits_read > 7)
        {
            bits_read = 0;
            data++;
            size--;
        }

        /* Cycle check: */
        if(bit_flag)
            out ^= CRC16;

    }

    // item b) "push out" the last 16 bits
    int i;
    for (i = 0; i < 16; ++i) {
        bit_flag = out >> 15;
        out <<= 1;
        if(bit_flag)
            out ^= CRC16;
    }

    // item c) reverse the bits
    uint16_t crc = 0;
    i = 0x8000;
    int j = 0x0001;
    for (; i != 0; i >>=1, j <<= 1) {
        if (i & out) crc |= j;
    }

    return crc;
}

Эта функция возвращает 0xbb3d для меня, когда я передаю "123456789".

Ответ 2

Здесь следует рабочий код для вычисления crc16 CCITT. Я тестировал его, и результаты соответствовали результатам, предоставленным http://www.lammertbies.nl/comm/info/crc-calculation.html.

unsigned short crc16(const unsigned char* data_p, unsigned char length){
    unsigned char x;
    unsigned short crc = 0xFFFF;

    while (length--){
        x = crc >> 8 ^ *data_p++;
        x ^= x>>4;
        crc = (crc << 8) ^ ((unsigned short)(x << 12)) ^ ((unsigned short)(x <<5)) ^ ((unsigned short)x);
    }
    return crc;
}

Ответ 3

Существует несколько различных вариантов CRC-16. Смотрите страницу wiki.

Каждый из них будет возвращать разные результаты с одного и того же ввода.

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

Ответ 4

for (pos = 0; pos < len; pos++) {
    crc ^= (uint16_t)buf[pos];     // XOR byte into least sig. byte of crc

    for (i = 8; i != 0; i--) {     // Loop over each bit
        if ((crc & 0x0001) != 0) { // If the LSB is set
            crc >>= 1;             // Shift right and XOR 0xA001
            crc ^= CRC16;
        } else {                   // Else LSB is not set
            crc >>= 1;             // Just shift right
        }
     }
}

return crc;