了解高效的 CRC-CCITT-16 实施

Understanting an efficient CRC-CCITT-16 implementation

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

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

crc将数据+16个0的填充位除以多项式,余数就是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

如评论所述,table 查找应该更快。如果 cpu 具有快速无进位乘法,例如 X86 pclmulqdq,则可以使用更快的汇编程序,但它超过 500 行长("fold" 一次并行使用 xmm 128 字节寄存器)。下面的汇编代码没有记录常量(rk ...);它们是用于 "folding" 的多项式的 2 模数的幂,除了 rk7 = "(2^n)/polynomial" 和 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、非反射(非反向)和反射)。

这有点晚了,我很感激。这是我在 2002 年开发的原始代码。我已经关闭了该网站,但 Internet Archive 有一个副本。这里有一些关于它为什么以及如何工作的细节:

https://web.archive.org/web/20160408050435/http://www.digitalnemesis.com/info/codesamples/embeddedcrc16/

这最初是一个 4 位 table,是为只有几百字节 RAM 的 8 位 PIC 微控制器开发的。

link 包含原始描述,table 生成器程序源以及 PIC 的 C 和 ASM 实现。

当然,如果您尝试在现代 PC 上执行此操作,那么这是糟糕的代码。与替代方案相比,它 'efficient' 计算它位但在目标设备上位。