数据填充对CRC计算的影响
Impact of data padding on CRC calculation
我在硬件的每个周期（每个周期 64B）计算大量数据的 CRC。为了并行计算CRC，我想对小数据块计算CRC，然后并行异或。
方法：
- 我们把数据分成小块（64B数据分成8块
每个 8B）。
- 然后我们计算所有块的CRC
单独（8B 块并行 8 个 CRC）。
- 最后计算
填充数据的 CRC。 This answer 指出 CRC
填充数据是通过将旧的 CRC 乘以 x^n 获得的。
因此，我正在为一小块数据计算 CRC，然后将其与移位 'i' 次的 0x1 CRC 相乘，如下所示。
简而言之，我正在努力完成以下工作：
例如：CRC-8 on this site:
Input Data=(0x05 0x07) CRC=0x54
Step-1: Data=0x5 CRC=0x1B
Step-2: Data=0x7 CRC=0x15
Step-3: Data=(0x1 0x0) CRC=0x15
Step-4: Multiply step-1 CRC and step-3 CRC with primitive polynomial 0x7. So, I calculate (0x1B).(0x15) = (0x1 0xC7) mod 0x7.
Step-5: Calculate CRC Data=(0x1 0xC7) CRC=0x4E (I assume this is same as (0x1 0xC7) mod 0x7)
Step-6: XOR the result to get the final CRC. 0x4E^0x15=0x5B
正如我们所见，第 6 步的结果不是正确的结果。
有人可以帮我计算填充数据的CRC吗？或者我在上面的例子中哪里出错了？
如你的图所示，需要计算0x05 0x00,(A,0)的CRC，和0x00 0x07,(0,B)的CRC，然后互斥-或那些在一起。在您链接的网站上计算，您分别得到 0x41 和 0x15。异或那些一起，瞧，你得到 0x54，0x05 0x07 的 CRC。
(0,B) 有一个捷径，因为对于这个 CRC，一串零的 CRC 为零。您可以计算 0x07 的 CRC，并得到与 0x00 0x07 相同的结果，即 0x15.
请参阅 crcany 了解如何组合 CRC。 crcany 将生成 C 代码来计算任何指定的 CRC，包括组合 CRC 的代码。它采用一种技术，将 n 零应用于 O(log(n)) 时间而不是 O(n )时间。
不是计算然后调整多个 CRC，而是可以将数据字节无进位相乘以形成一组 16 位“折叠”乘积，然后对其进行异或运算，并对异或运算执行单个模运算“折叠”产品。优化的模运算使用两个无进位倍数，因此在生成所有折叠产品并将其异或在一起之前可以避免这种情况。无进位乘法使用 XOR 而不是 ADD，无借位除法使用 XOR 而不是 SUB。 Intel 有一个关于这个的 pdf 文件，使用 XMM 指令 PCLMULQDQ（无进位乘法），其中一次读取 16 个字节，分成两个 8 字节的组，每个组折叠成一个 16 字节的产品，两个 16 字节的产品是异或形成一个 16 字节的产品。使用8个XMM寄存器存放折叠产品，一次处理128个字节。 （对于 AVX512 和 ZMM 寄存器，每次 256 个字节）。
假设您的硬件可以实现无进位乘法，它采用两个 8 位操作数并产生 16 位（技术上是 15 位）乘积。
设message = M = 31 32 33 34 35 36 37 38。在这种情况下CRC(M) = C7
pre-calculated constants (all values shown in hex):
2^38%107 = DF cycles forwards 0x38 bits
2^30%107 = 29 cycles forwards 0x30 bits
2^28%107 = 62 cycles forwards 0x28 bits
2^20%107 = 16 cycles forwards 0x20 bits
2^18%107 = 6B cycles forwards 0x18 bits
2^10%107 = 15 cycles forwards 0x10 bits
2^08%107 = 07 cycles forwards 0x08 bits
2^00%107 = 01 cycles forwards 0x00 bits
16 bit folded (cycled forward) products (can be calculated in parallel):
31·DF = 16CF
32·29 = 07E2
33·62 = 0AC6
34·16 = 03F8
35·6B = 0A17
36·15 = 038E
37·07 = 0085
38·01 = 0038
----
V = 1137 the xor of the 8 folded products
CRC(V) = 113700 % 107 = C7
为避免模运算必须使用无借位除法，可以使用无进位乘法计算 CRC(V)。例如
V = FFFE
CRC(V) = FFFE00 % 107 = 23.
实现，同样是十六进制的所有值（十六进制 10 = 十进制 16），⊕ 是 XOR。
input:
V = FFFE
constants:
P = 107 polynomial
I = 2^10 / 107 = 107 "inverse" of polynomial
by coincidence, it's the same value
2^10 % 107 = 15 for folding right 16 bits
fold the upper 8 bits of FFFE00 16 bits to the right:
U = FF·15 ⊕ FE00 = 0CF3 ⊕ FE00 = F2F3 (check: F2F3%107 = 23 = CRC)
Q = ((U>>8)·I)>>8 = (F2·107)>>8 = ...
to avoid a 9 bit operand, split up 107 = 100 ⊕ 7
Q = ((F2·100) ⊕ (F2·07))>>8 = ((F2<<8) ⊕ (F2·07))>>8 = (F200 ⊕ 02DE)>>8 = F0DE>>8 = F0
X = Q·P = F0·107 = F0·100 ⊕ F0·07 = F0<<8 ⊕ F0·07 = F000 ⊕ 02D0 = F2D0
CRC = U ⊕ X = F2F3 ⊕ F2D0 = 23
由于CRC是8位，所以最后两步不需要高8位，但对整体计算帮助不大。
X = (Q·(P&FF))&FF = (F0·07)&FF = D0
CRC = (U&FF) ⊕ X = F3 ⊕ D0 = 23
生成 2^0x10 / 0x107 和 2 % 0x107 的幂的示例程序：
#include <stdio.h>
typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
#define poly 0x107
uint16_t geninv(void) /* generate 2^16 / 9 bit poly */
{
uint16_t q = 0x0000u; /* quotient */
uint16_t d = 0x0001u; /* initial dividend = 2^0 */
for(int i = 0; i < 16; i++){
d <<= 1;
q <<= 1;
if(d&0x0100){ /* if bit 8 set */
q |= 1; /* q |= 1 */
d ^= poly; /* d ^= poly */
}
}
return q; /* return inverse */
}
uint8_t powmodpoly(int n) /* generate 2^n % 9 bit poly */
{
uint16_t d = 0x0001u; /* initial dividend = 2^0 */
for(int i = 0; i < n; i++){
d <<= 1; /* shift dvnd left */
if(d&0x0100){ /* if bit 8 set */
d ^= poly; /* d ^= poly */
}
}
return (uint8_t)d; /* return remainder */
}
int main()
{
printf("%04x\n", geninv());
printf("%02x %02x %02x %02x %02x %02x %02x %02x %02x %02x\n",
powmodpoly(0x00), powmodpoly(0x08), powmodpoly(0x10), powmodpoly(0x18),
powmodpoly(0x20), powmodpoly(0x28), powmodpoly(0x30), powmodpoly(0x38),
powmodpoly(0x40), powmodpoly(0x48));
printf("%02x\n", powmodpoly(0x77)); /* 0xd9, cycles crc backwards 8 bits */
return 0;
}
2^0x10 / 0x107 的长手示例。
100000111 quotient
-------------------
divisor 100000111 | 10000000000000000 dividend
100000111
---------
111000000
100000111
---------
110001110
100000111
---------
100010010
100000111
---------
10101 remainder
我不知道您的硬件设计中可以有多少个寄存器，但假设有五个 16 位寄存器用于保存折叠值，以及两个或八个 8 位寄存器（取决于折叠的并行程度已经完成了）。然后按照 Intel 论文，折叠所有 64 个字节的值，一次折叠 8 个字节，并且只需要一个模运算。寄存器大小，fold# = 16 位，reg# = 8 位。请注意，2 模多边形的幂是预先计算的常数。
foldv = prior buffer's folding value, equivalent to folded msg[-2 -1]
reg0 = foldv>>8
reg1 = foldv&0xFF
foldv = reg0·((2^0x18)%poly) advance by 3 bytes
foldv ^= reg1·((2^0x10)%poly) advance by 2 bytes
fold0 = msg[0 1] ^ foldv handling 2 bytes at a time
fold1 = msg[2 3]
fold2 = msg[4 5]
fold3 = msg[6 7]
for(i = 8; i < 56; i += 8){
reg0 = fold0>>8
reg1 = fold0&ff
fold0 = reg0·((2^0x48)%poly) advance by 9 bytes
fold0 ^= reg1·((2^0x40)%poly) advance by 8 bytes
fold0 ^= msg[i+0 i+1]
reg2 = fold1>>8 if not parallel, reg0
reg3 = fold1&ff and reg1
fold1 = reg2·((2^0x48)%poly) advance by 9 bytes
fold1 ^= reg3·((2^0x40)%poly) advance by 8 bytes
fold1 ^= msg[i+2 i+3]
...
fold3 ^= msg[i+6 i+7]
}
reg0 = fold0>>8
reg1 = fold0&ff
fold0 = reg0·((2^0x38)%poly) advance by 7 bytes
fold0 ^= reg1·((2^0x30)%poly) advance by 6 bytes
reg2 = fold1>>8 if not parallel, reg0
reg3 = fold1&ff and reg1
fold1 = reg2·((2^0x28)%poly) advance by 5 bytes
fold1 ^= reg3·((2^0x20)%poly) advance by 4 bytes
fold2 ... advance by 3 2 bytes
fold3 ... advance by 1 0 bytes
foldv = fold0^fold1^fold2^fold3
假设最终缓冲区有 5 个字节：
foldv = prior folding value, equivalent to folded msg[-2 -1]
reg0 = foldv>>8
reg1 = foldv&0xFF
foldv = reg0·((2^0x30)%poly) advance by 6 bytes
foldv ^= reg1·((2^0x28)%poly) advance by 5 bytes
fold0 = msg[0 1] ^ foldv
reg0 = fold0>>8
reg1 = fold0&ff
fold0 = reg0·((2^0x20)%poly) advance by 4 bytes
fold0 ^= reg1·((2^0x18)%poly) advance by 3 bytes
fold1 = msg[2 3]
reg2 = fold1>>8
reg3 = fold1&ff
fold1 = reg0·((2^0x10)%poly) advance by 2 bytes
fold1 ^= reg1·((2^0x08)%poly) advance by 1 bytes
fold2 = msg[4] just one byte loaded
fold3 = 0
foldv = fold0^fold1^fold2^fold3
now use the method above to calculate CRC(foldv)
我在硬件的每个周期（每个周期 64B）计算大量数据的 CRC。为了并行计算CRC，我想对小数据块计算CRC，然后并行异或。
方法：
- 我们把数据分成小块（64B数据分成8块 每个 8B）。
- 然后我们计算所有块的CRC 单独（8B 块并行 8 个 CRC）。
- 最后计算 填充数据的 CRC。 This answer 指出 CRC 填充数据是通过将旧的 CRC 乘以 x^n 获得的。
因此，我正在为一小块数据计算 CRC，然后将其与移位 'i' 次的 0x1 CRC 相乘，如下所示。
简而言之，我正在努力完成以下工作：
例如：CRC-8 on this site:
Input Data=(0x05 0x07) CRC=0x54
Step-1: Data=0x5 CRC=0x1B
Step-2: Data=0x7 CRC=0x15
Step-3: Data=(0x1 0x0) CRC=0x15
Step-4: Multiply step-1 CRC and step-3 CRC with primitive polynomial 0x7. So, I calculate (0x1B).(0x15) = (0x1 0xC7) mod 0x7.
Step-5: Calculate CRC Data=(0x1 0xC7) CRC=0x4E (I assume this is same as (0x1 0xC7) mod 0x7)
Step-6: XOR the result to get the final CRC. 0x4E^0x15=0x5B
正如我们所见，第 6 步的结果不是正确的结果。
有人可以帮我计算填充数据的CRC吗？或者我在上面的例子中哪里出错了？
如你的图所示，需要计算0x05 0x00,(A,0)的CRC，和0x00 0x07,(0,B)的CRC，然后互斥-或那些在一起。在您链接的网站上计算，您分别得到 0x41 和 0x15。异或那些一起，瞧，你得到 0x54，0x05 0x07 的 CRC。
(0,B) 有一个捷径，因为对于这个 CRC，一串零的 CRC 为零。您可以计算 0x07 的 CRC，并得到与 0x00 0x07 相同的结果，即 0x15.
请参阅 crcany 了解如何组合 CRC。 crcany 将生成 C 代码来计算任何指定的 CRC，包括组合 CRC 的代码。它采用一种技术，将 n 零应用于 O(log(n)) 时间而不是 O(n )时间。
不是计算然后调整多个 CRC，而是可以将数据字节无进位相乘以形成一组 16 位“折叠”乘积，然后对其进行异或运算，并对异或运算执行单个模运算“折叠”产品。优化的模运算使用两个无进位倍数，因此在生成所有折叠产品并将其异或在一起之前可以避免这种情况。无进位乘法使用 XOR 而不是 ADD，无借位除法使用 XOR 而不是 SUB。 Intel 有一个关于这个的 pdf 文件，使用 XMM 指令 PCLMULQDQ（无进位乘法），其中一次读取 16 个字节，分成两个 8 字节的组，每个组折叠成一个 16 字节的产品，两个 16 字节的产品是异或形成一个 16 字节的产品。使用8个XMM寄存器存放折叠产品，一次处理128个字节。 （对于 AVX512 和 ZMM 寄存器，每次 256 个字节）。
假设您的硬件可以实现无进位乘法，它采用两个 8 位操作数并产生 16 位（技术上是 15 位）乘积。
设message = M = 31 32 33 34 35 36 37 38。在这种情况下CRC(M) = C7
pre-calculated constants (all values shown in hex):
2^38%107 = DF cycles forwards 0x38 bits
2^30%107 = 29 cycles forwards 0x30 bits
2^28%107 = 62 cycles forwards 0x28 bits
2^20%107 = 16 cycles forwards 0x20 bits
2^18%107 = 6B cycles forwards 0x18 bits
2^10%107 = 15 cycles forwards 0x10 bits
2^08%107 = 07 cycles forwards 0x08 bits
2^00%107 = 01 cycles forwards 0x00 bits
16 bit folded (cycled forward) products (can be calculated in parallel):
31·DF = 16CF
32·29 = 07E2
33·62 = 0AC6
34·16 = 03F8
35·6B = 0A17
36·15 = 038E
37·07 = 0085
38·01 = 0038
----
V = 1137 the xor of the 8 folded products
CRC(V) = 113700 % 107 = C7
为避免模运算必须使用无借位除法，可以使用无进位乘法计算 CRC(V)。例如
V = FFFE
CRC(V) = FFFE00 % 107 = 23.
实现，同样是十六进制的所有值（十六进制 10 = 十进制 16），⊕ 是 XOR。
input:
V = FFFE
constants:
P = 107 polynomial
I = 2^10 / 107 = 107 "inverse" of polynomial
by coincidence, it's the same value
2^10 % 107 = 15 for folding right 16 bits
fold the upper 8 bits of FFFE00 16 bits to the right:
U = FF·15 ⊕ FE00 = 0CF3 ⊕ FE00 = F2F3 (check: F2F3%107 = 23 = CRC)
Q = ((U>>8)·I)>>8 = (F2·107)>>8 = ...
to avoid a 9 bit operand, split up 107 = 100 ⊕ 7
Q = ((F2·100) ⊕ (F2·07))>>8 = ((F2<<8) ⊕ (F2·07))>>8 = (F200 ⊕ 02DE)>>8 = F0DE>>8 = F0
X = Q·P = F0·107 = F0·100 ⊕ F0·07 = F0<<8 ⊕ F0·07 = F000 ⊕ 02D0 = F2D0
CRC = U ⊕ X = F2F3 ⊕ F2D0 = 23
由于CRC是8位，所以最后两步不需要高8位，但对整体计算帮助不大。
X = (Q·(P&FF))&FF = (F0·07)&FF = D0
CRC = (U&FF) ⊕ X = F3 ⊕ D0 = 23
生成 2^0x10 / 0x107 和 2 % 0x107 的幂的示例程序：
#include <stdio.h>
typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
#define poly 0x107
uint16_t geninv(void) /* generate 2^16 / 9 bit poly */
{
uint16_t q = 0x0000u; /* quotient */
uint16_t d = 0x0001u; /* initial dividend = 2^0 */
for(int i = 0; i < 16; i++){
d <<= 1;
q <<= 1;
if(d&0x0100){ /* if bit 8 set */
q |= 1; /* q |= 1 */
d ^= poly; /* d ^= poly */
}
}
return q; /* return inverse */
}
uint8_t powmodpoly(int n) /* generate 2^n % 9 bit poly */
{
uint16_t d = 0x0001u; /* initial dividend = 2^0 */
for(int i = 0; i < n; i++){
d <<= 1; /* shift dvnd left */
if(d&0x0100){ /* if bit 8 set */
d ^= poly; /* d ^= poly */
}
}
return (uint8_t)d; /* return remainder */
}
int main()
{
printf("%04x\n", geninv());
printf("%02x %02x %02x %02x %02x %02x %02x %02x %02x %02x\n",
powmodpoly(0x00), powmodpoly(0x08), powmodpoly(0x10), powmodpoly(0x18),
powmodpoly(0x20), powmodpoly(0x28), powmodpoly(0x30), powmodpoly(0x38),
powmodpoly(0x40), powmodpoly(0x48));
printf("%02x\n", powmodpoly(0x77)); /* 0xd9, cycles crc backwards 8 bits */
return 0;
}
2^0x10 / 0x107 的长手示例。
100000111 quotient
-------------------
divisor 100000111 | 10000000000000000 dividend
100000111
---------
111000000
100000111
---------
110001110
100000111
---------
100010010
100000111
---------
10101 remainder
我不知道您的硬件设计中可以有多少个寄存器，但假设有五个 16 位寄存器用于保存折叠值，以及两个或八个 8 位寄存器（取决于折叠的并行程度已经完成了）。然后按照 Intel 论文，折叠所有 64 个字节的值，一次折叠 8 个字节，并且只需要一个模运算。寄存器大小，fold# = 16 位，reg# = 8 位。请注意，2 模多边形的幂是预先计算的常数。
foldv = prior buffer's folding value, equivalent to folded msg[-2 -1]
reg0 = foldv>>8
reg1 = foldv&0xFF
foldv = reg0·((2^0x18)%poly) advance by 3 bytes
foldv ^= reg1·((2^0x10)%poly) advance by 2 bytes
fold0 = msg[0 1] ^ foldv handling 2 bytes at a time
fold1 = msg[2 3]
fold2 = msg[4 5]
fold3 = msg[6 7]
for(i = 8; i < 56; i += 8){
reg0 = fold0>>8
reg1 = fold0&ff
fold0 = reg0·((2^0x48)%poly) advance by 9 bytes
fold0 ^= reg1·((2^0x40)%poly) advance by 8 bytes
fold0 ^= msg[i+0 i+1]
reg2 = fold1>>8 if not parallel, reg0
reg3 = fold1&ff and reg1
fold1 = reg2·((2^0x48)%poly) advance by 9 bytes
fold1 ^= reg3·((2^0x40)%poly) advance by 8 bytes
fold1 ^= msg[i+2 i+3]
...
fold3 ^= msg[i+6 i+7]
}
reg0 = fold0>>8
reg1 = fold0&ff
fold0 = reg0·((2^0x38)%poly) advance by 7 bytes
fold0 ^= reg1·((2^0x30)%poly) advance by 6 bytes
reg2 = fold1>>8 if not parallel, reg0
reg3 = fold1&ff and reg1
fold1 = reg2·((2^0x28)%poly) advance by 5 bytes
fold1 ^= reg3·((2^0x20)%poly) advance by 4 bytes
fold2 ... advance by 3 2 bytes
fold3 ... advance by 1 0 bytes
foldv = fold0^fold1^fold2^fold3
假设最终缓冲区有 5 个字节：
foldv = prior folding value, equivalent to folded msg[-2 -1]
reg0 = foldv>>8
reg1 = foldv&0xFF
foldv = reg0·((2^0x30)%poly) advance by 6 bytes
foldv ^= reg1·((2^0x28)%poly) advance by 5 bytes
fold0 = msg[0 1] ^ foldv
reg0 = fold0>>8
reg1 = fold0&ff
fold0 = reg0·((2^0x20)%poly) advance by 4 bytes
fold0 ^= reg1·((2^0x18)%poly) advance by 3 bytes
fold1 = msg[2 3]
reg2 = fold1>>8
reg3 = fold1&ff
fold1 = reg0·((2^0x10)%poly) advance by 2 bytes
fold1 ^= reg1·((2^0x08)%poly) advance by 1 bytes
fold2 = msg[4] just one byte loaded
fold3 = 0
foldv = fold0^fold1^fold2^fold3
now use the method above to calculate CRC(foldv)