了解有效的 CRC-CCITT-16 实现

Question

我遇到了一个据称非常高效和优雅的 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 个循环，但我希望得到一些澄清。谢谢你的时间。

Answer 1

如果代码包含一条注释，即 x 是用于使用二进制无借位除法一次处理 8 位的商，那将会有所帮助。

crc将数据+16个零的填充位除以多项式，余数就是CRC。

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

为了一次处理 8 位，每一步都将位 aaaabbbb0000000000000000 除以 10001000000100001，其中 aaaabbbb 是与下一个数据字节异或的 crc 的高 8 位。这可以通过注意到商 = 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

正如评论的那样，查表应该更快。如果 cpu 具有快速的无进位乘法，例如 X86 pclmulqdq，则可以使用速度更快的汇编程序，但它的长度超过 500 行（使用 xmm 寄存器并行“折叠”128 个字节）。下面的汇编代码没有记录常量（rk ...）；它们是用于“折叠”的多项式的 2 次幂，除了 rk7 =“(2^n)/polynomial”和 rk8 = polynomial。

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、非反射（非反向）和反射的源代码。