Поддержка эффективного внедрения CRC-CCITT-16 - PullRequest
Новая
       126

Поддержка эффективного внедрения CRC-CCITT-16

2 голосов
/ 11 ноября 2019

Я столкнулся с якобы очень эффективной и элегантной реализацией CRC, и я пытаюсь действительно понять все шаги. Я понимаю реализации CRC-CCITT 0x1021, которые повторяются для каждого бита, но я изо всех сил пытаюсь получить это. Это код. 

/*
* Original Code by Ashley Roll 
*/

uint16_t crc16(uint8_t* data, uint16_t length){

  uint8_t x;
  uint16_t crc = 0xFFFF;

  while (length--){
      x = crc >> 8 ^ *data++;
      x ^= x>>4;
      crc = (crc << 8) ^ ((uint16_t)(x << 12)) ^ ((uint16_t)(x <<5)) ^ ((uint16_t)x);
  }

  return crc;
}

Может кто-нибудь объяснить мне немного глубже, что происходит с переменной x? Это то, что я мог понять до сих пор 

x = crc >> 8 ^ *data++; // Here, we take the high byte of the register
                        // and we XOR it with the next 8 bits of data. Why?
x ^= x>>4;              // Then, we XOR it with its last four bits?
                        // And we always remain with 4 possible non-zero bits, right?
                        // Why do we do this?
crc = (crc << 8) ^ ((uint16_t)(x << 12)) ^ ((uint16_t)(x <<5)) ^ ((uint16_t)x);
                        // Finally, we drop the oldest (highest) byte from the register
                        // And XOR it with rotations of x, according to the polynomial
                        // 0x1021, which is x^16 + x^12 + x^5 + 1
                        // Is (16-12) = 4 the reason why x has 4 possible non-zero bits?

Я предполагаю, что этот алгоритм является просто эквивалентом 8 циклов побитового алгоритма, но я был бы признателен за некоторые пояснения. Спасибо за ваше время.

1 Ответ

3 голосов
/ 11 ноября 2019

Было бы полезно, если бы код содержал комментарий о том, что x является частным, который будет использоваться для обработки 8 битов одновременно с использованием двоичного деления без заимствования.

CRC делит данные + 16 битов заполненияноль за полином, а остаток - это CRC. 

poly = x^16 + x^12 + x^5 + 1 = 0x11021 = 10001000000100001 (binary)

Для обработки 8 битов за раз, каждый шаг делит биты aaaabbbb0000000000000000 на 10001000000100001, где aaaabbbb - это старшие 8 битов crc xor'edсо следующим байтом данных. Это можно сделать за один шаг деления, отметив частное = x = (aaaabbbb) ^ (aaaabbbb >> 4) = aaaacccc, где c = a ^ b, поэтому a ^ c = b и a ^ b ^ c =0: 

                                    aaaacccc
                  --------------------------
10001000000100001 | aaaabbbb0000000000000000
                                    aaaacccc
                               aaaacccc
                        aaaacccc
                    aaaacccc
                            ----------------
                            cccbaaacbbbacccc

В коде вопросов биты выше x ^ 16 не генерируются, поскольку известно, что они будут аннулировать биты с x ^ 16 по x ^ 23. Сдвиг влево на 12 сдвигает верхние 4 бита, соответствующие битам от x ^ 16 до x ^ 19, и нет сдвига влево, равного 16. 

example: data = 0x31 0x32 = 00110001 00110010

crc = 1111111111111111
x = (crc>>8)^00110001 = 11001110
q = (x)^(x>>4) = 11000010

                                   11000010
                  -------------------------
10001000000100001 |110011100000000000000000
                                   11000010
                              11000010
                       11000010
                   11000010
                           ----------------
                           0011100010000010

crc = (crc<<8)^0011100010000010 = 1100011110000010
x = (crc>>8) ^ 00110010 = 11110101
q = (x)^(x>>4) = 11111010

                                   11111010
                  -------------------------
10001000000100001 |111101010000000000000000
                                   11111010
                              11111010
                       11111010
                   11111010
                           ----------------
                           1011111110111010

crc = (crc<<8)^1011111110111010 = 0011110110111010 = 0x3dba

Как прокомментировано,поиск таблицы должен быть быстрее. Если процессор имеет быстрое умножение без переноса, такое как X86 pclmulqdq, то можно использовать более быструю программу сборки неподвижных изображений, но она имеет длину более 500 строк (чтобы «свернуть» 128 байтов за раз параллельно, используя регистры xmm). Код ассемблера ниже не документирует константы (rk ...);они являются степенями 2 по модулю многочлена, используемого для «сворачивания», за исключением rk7 = «(2 ^ n) / полином» и rk8 = полином.

https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf

https://github.com/intel/isa-l/blob/master/crc/crc16_t10dif_01.asm

Я преобразовал код в Visual Studio ML64.EXE (MASM) и Windows и имею исходный код для crc16, crc32, crc64, неотраженный (не обращенный) и отраженный).

...