Как настроить расчет таблицы CRC

Question

Существует множество примеров расчета CRC. Простые реализации со сдвигом битов и более эффективные с заранее вычисленной таблицей. Но есть также много параметров CRC, кроме полинома, которые влияют на расчет. Вы можете оценить эти параметры здесь: http://zorc.breitbandkatze.de/crc.html

Эти параметры

• начальное значение CRC
• отражение входных данных
• отражение выходных данных
• окончательное значение XOR для CRC

Для некоторого "стандартного" алгоритма CRC эти параметры четко определены, например, CRC-16 (CCITT). Но есть некоторые реализации, которые используют разные параметры.

Моя реализация должна быть совместима с CRC16 с полиномом CCITT (x¹⁶ + x¹² + x⁵ + 1). Но байты данных и окончательный CRC должны быть отражены. Я реализовал эти отражения в методе расчета. Но это отнимает много времени. Для лучшей производительности он должен быть удален из расчета.

Как рассчитать параметры отражения CRC в методе инициализации?

Изменить: Как я должен сделать, чтобы контролировать каждый из параметров в отдельности? Я хотел бы понять, как Init Функция на самом деле работает и как все параметры реализованы.

typedef unsigned char uint8_t;
typedef unsigned short crc;

crc  crcTable[256];
#define WIDTH  (8 * sizeof(crc))
#define TOPBIT (1 << (WIDTH - 1))
#define POLYNOMIAL 0x1021

template<typename t>
t reflect(t v)
{
    t r = 0;

    for (int i = 0; i < (8 * sizeof v); ++i)
    {
        r <<= 1;
        r |= v&1;
        v >>= 1;
    }

    return r;
}

void Init()
{
    crc  remainder;

    for (int dividend = 0; dividend < 256; ++dividend)
    {
        remainder = dividend << (WIDTH - 8);

        for (uint8_t bit = 8; bit > 0; --bit)
        {
            if (remainder & TOPBIT)
                remainder = (remainder << 1) ^ POLYNOMIAL;
            else
                remainder = (remainder << 1);
        }

        crcTable[dividend] = remainder;
    }
}

crc Calculate(const uint8_t *message, int nBytes, crc wOldCRC)
{
    uint8_t data;
    crc remainder = wOldCRC;

    for (int byte = 0; byte < nBytes; ++byte)
    {
        data = reflect(message[byte]) ^ (remainder >> (WIDTH - 8));
        remainder = crcTable[data] ^ (remainder << 8);
    }

    return reflect(remainder);
}

int main()
{
    crc expected = 0x6f91;
    uint8_t pattern[] = "123456789";

    Init();
    crc result = Calculate(pattern, 9, 0xFFFF);

    if (result != expected)
    {
        // this output is not relevant to the question, despite C++ tag
        printf("CRC 0x%04x wrong, expected 0x%04x\n", result, expected);
    }
}

Answer 1

Вместо того чтобы отражать поступающие данные, входящий CRC и выходящий CRC, вы просто отражаете многочлен и операции. Вам нужно сделать это только один раз, когда вы пишете код. Отраженный полином 0x8408,

typedef unsigned char uint8_t;
typedef unsigned short crc;

crc  crcTable[256];
#define POLYNOMIAL 0x8408

void Init()
{
    crc  remainder;

    for (int dividend = 0; dividend < 256; ++dividend)
    {
        remainder = dividend;

        for (uint8_t bit = 8; bit > 0; --bit)
        {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ POLYNOMIAL;
            else
                remainder = (remainder >> 1);
        }

        crcTable[dividend] = remainder;
    }
}

crc Calculate(const uint8_t *message, int nBytes, crc wOldCRC)
{
    uint8_t data;
    crc remainder = wOldCRC;

    for (int byte = 0; byte < nBytes; ++byte)
    {
        data = message[byte] ^ remainder;
        remainder = crcTable[data] ^ (remainder >> 8);
    }

    return remainder;
}

int main()
{
    crc expected = 0x6f91;
    uint8_t pattern[] = "123456789";

    Init();
    crc result = Calculate(pattern, 9, 0xFFFF);

    if (result != expected)
    {
        // this output is not relevant to the question, despite C++ tag
        printf("CRC 0x%04x wrong, expected 0x%04x\n", result, expected);
    }
}

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

Почти во всех случаях отражение выходных данных совпадает с отражением входных данных. Для всех этих случаев нет необходимости использовать немного реверсную функцию. Вы оставляете результат из регистра сдвига как есть, если и вход, и выход не отражаются, или если и вход, и выход отражаются. Только в одном из 72 CRC, внесенных в каталог на сайте RevEng, отраженный результат отличается от отраженного в (CRC-12/3GPP). В этом одном случае вам нужно инвертировать выходной бит, так как вход не отражается, а вывод есть.

Начальный CRC - это просто начальное содержимое регистра сдвига. Вы устанавливаете это один раз при запуске CRC. Окончательный исключающий-или применяется к содержимому регистра сдвига в конце. Если у вас есть функция, которая вычисляет CRC по частям за раз, вам необходимо применить окончательное исключение или при входе в функцию, а также применить это окончательное исключение или к начальному значению, которое видит пользователь, так, чтобы фактическое начальное значение - это то, что заканчивается в регистре сдвига.