了解高效的 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://github.com/intel/isa-l/blob/master/crc/crc16_t10dif_01.asm
我将代码转换为 Visual Studio ML64.EXE (MASM) 和 Windows,并且有 crc16、crc32、crc64、非反射(非反向)和反射)。
这有点晚了,我很感激。这是我在 2002 年开发的原始代码。我已经关闭了该网站,但 Internet Archive 有一个副本。这里有一些关于它为什么以及如何工作的细节:
这最初是一个 4 位 table,是为只有几百字节 RAM 的 8 位 PIC 微控制器开发的。
link 包含原始描述,table 生成器程序源以及 PIC 的 C 和 ASM 实现。
当然,如果您尝试在现代 PC 上执行此操作,那么这是糟糕的代码。与替代方案相比,它 'efficient' 计算它位但在目标设备上位。
我遇到了一个据称非常高效和优雅的 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://github.com/intel/isa-l/blob/master/crc/crc16_t10dif_01.asm
我将代码转换为 Visual Studio ML64.EXE (MASM) 和 Windows,并且有 crc16、crc32、crc64、非反射(非反向)和反射)。
这有点晚了,我很感激。这是我在 2002 年开发的原始代码。我已经关闭了该网站,但 Internet Archive 有一个副本。这里有一些关于它为什么以及如何工作的细节:
这最初是一个 4 位 table,是为只有几百字节 RAM 的 8 位 PIC 微控制器开发的。
link 包含原始描述,table 生成器程序源以及 PIC 的 C 和 ASM 实现。
当然,如果您尝试在现代 PC 上执行此操作,那么这是糟糕的代码。与替代方案相比,它 'efficient' 计算它位但在目标设备上位。