c - 了解高效的 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个pad bits的零除以多项式，余数就是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)/多项式”和 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、非反射(非反向)和反射的源代码。