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

Question

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

Этих параметров

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

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

Моя реализация должна быть совместима с CRC16 с CCITT полинома (х + х + х + 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

Вместо отражения данных, поступающие в и C поступают, и 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 CRCs catalogued at the RevEng site отражается отличие от отражения в (CRC-12/3GPP). В этом случае вам нужно битовать обратный вывод, поскольку вход не отражен, но выход.

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