具有 PCLMULQDQ 的快速 CRC *未*反映
Fast CRC with PCLMULQDQ *NOT* reflected
我正在尝试编写一个 PCLMULQDQ-optimized CRC-32 implementation. The specific CRC-32 variant is for one that I don't own, but am trying to support in library form. In crcany model 表单，它具有以下参数：
width=32 poly=0xaf init=0xffffffff refin=false refout=false xorout=0x00000000 check=0xa5fd3138
（我认为遗漏的残留物是 0x00000000 但老实说不知道它是什么）
算法的基本 non-table-based/bitwise 实现（由 crcany 生成）是：
uint32_t crc32byond_bit(uint32_t crc, void const *mem, size_t len) {
unsigned char const *data = mem;
if (data == NULL)
return 0xffffffff;
for (size_t i = 0; i < len; i++) {
crc ^= (uint32_t)data[i] << 24;
for (unsigned k = 0; k < 8; k++) {
crc = crc & 0x80000000 ? (crc << 1) ^ 0xaf : crc << 1;
}
}
return crc;
}
首先，我从根本上不理解描述该算法的论文。我不知道 K1 = [x^(512+64) mod P(x)] 这样的东西是什么意思。 （什么是x？从哪里来的？我不知道。）我是一名专业的软件工程师；不是学者。坦率地说，我根本不理解这个符号，Wikipedia article 对我没有多大帮助。也许是我在线性代数方面的弱点又来困扰我了。
我知道一些 public 实现我希望吸取：
但是：
- 他们使用位反射算法，我不确定如何创建非反射变体。
- 他们好像不看论文？比如wuffs和crc32fast特别喊出不用K6，但是论文却让K6显得很有必要
我在 soft-crc but it doesn't appear to use the same constants (K4-K6?μ?)
中找到了一个英特尔实现
/**
* PCLMULQDQ CRC computation context structure
*/
struct crc_pclmulqdq_ctx {
/**
* K1 = reminder X^128 / P(X) : 0-63
* K2 = reminder X^192 / P(X) : 64-127
*/
uint64_t k1;
uint64_t k2;
/**
* K3 = reminder X^64 / P(X) : 0-63
* q = quotient X^64 / P(X) : 64-127
*/
uint64_t k3;
uint64_t q;
/**
* p = polynomial / P(X) : 0-63
* res = reserved : 64-127
*/
uint64_t p;
uint64_t res;
};
我相信 我需要的 poly 0xAF 常数是：
Px = 0x1_0000_00AF
k1 = 0x0_5B5A_E0C7
k2 = 0x0_1BD8_1099
k3 = 0x0_1157_936A
k4 = 0x0_1010_1111
k5 = 0x0_0029_5F23
k6 = 0x0_0000_4455
μ = 0x1_0000_00AF
（来源：print-crc32-x86-sse42-magic-numbers.go 和 const px = "100000000000000000000000010101111"，或 0xaf | (1 << 32)）
我希望在这两个方面得到帮助
- 理解文章中使用的符号和公式（以及为什么实现似乎与文章不同？），
- 为非反射变体转换现有实现，或者可能
- 一些伪代码？
我有16、32、64位crc的6组代码，non-reflected反映在这里。该代码是为 Visual Studio 设置的。注释已添加到英特尔 github 站点中缺失的常量。
https://github.com/jeffareid/crc
32 位 non-relfected 在这里：
https://github.com/jeffareid/crc/tree/master/crc32f
您需要更改 crc32fg.cpp 中的多项式，它会生成常量。你要的多项式其实是：
0x00000001000000afull
我对 crc32fg.cpp 进行了此更改，以在该答案的末尾生成 rk.. 常量。
what is x?
CRC 使用具有 1 位系数的多项式。例如 0x0B 实际上是 x^3 + x + 1.
XMM寄存器可以读|写16字节|一次 128 位，但 PCLMULQDQ 只能将两个 64 位操作数进行无进位乘法以产生 128 位乘积。所以 128 位被拆分成两个 64 位操作数，然后每个操作数乘以一个常数以“折叠”它向前。由于 XMM 寄存器可以并行操作，因此使用 8 个 XMM 寄存器来读取 |写入 128 个字节 |一次 1024 位。每个折叠步骤“前进” 16 个字节 | 128 位数据转发 128 个字节 | 1024 位，乘以常数。较低的 64 位乘以 x^(1024) mod poly 以创建一个“高级”1024 位的 128 位乘积。高64位乘以x^(1024+64) mod poly得到一个128位乘积，即高级字节1024+64位（需要+64，因为乘积是基于高64位的128 位数据）。两个 128 位产品被异或在一起，然后与数据 128 字节进行异或运算 |缓冲区中的 1024 位之后。
注意Intel文档中的例子使用了4个XMM寄存器来推进数据64字节|一次 512 位，但我看到的 github 示例和我在 github 存储库中使用的示例使用 8 个 XMM 寄存器并前进 128 个字节 |一次 1024 位。对于数量相对较少的支持 AVX512 的处理器 | ZMM寄存器，有前进256字节的例子 |一次 2048 位。我没有带 AVX512 的电脑，所以我没有任何代码。
由于 XMM 读|写是小端，PSHUFB 用于在每次读取后反转字节。
该代码主要基于使用 65 位多项式的 64 位 CRC，但对于 32 位 CRC，这可以通过将低 32 位设置为零来处理。对于 32 位 CRC，大多数常量只有 32 位，并向左移动 32 位以简化 PCLMULQDQ 的使用，并进行调整以补偿移位，因此不是 x^(a) mod poly，它是(x^(a-32) mod 聚)<<32。实际 33 位多项式及其“逆”x^64 / 多项式的常数是 33 位并且没有左移，而使用这些常数创建实际 CRC 的 64 位值被左移 32 位。
折叠过程不产生 CRC，它只是转换数据以推进它。处理完所有数据后，使用常量 rk09、rk10、...、rk19、rk20、rk01、rk02，将 8 个 XMM 寄存器折叠成一个 128 位值。此时（标签 _128_done:) 有 128 位数据，并且由于代码基于 64 位 CRC 逻辑，逻辑上附加了 64 位零，因此实际上它是一个 192 位值，其中虚数低 64 位全部为零。高 64 位向前折叠 128 位，导致 XMM7 中的 128 位值准备计算 64 位 CRC，但由于这是 32 位 CRC，XMM7 将 96 位数据左移 32 位。高 32 位向前折叠 64 位（在这种情况下，96 位值和 rk06 都左移 32 位，因此 rk06 在这种情况下折叠 64 位（x^64 mod poly）并移位左移 32 位。结果是一个 64 位值在 XMM7 中左移 32 位。
64位数除以33位多项式的商只需要64位数的高32位，所以左移64位的值有高32位，方便计算a商。除法实际上是乘以 x^64 / 多项式，PCLMULQDQ 将仅指定使用 XMM7 的高 64 位部分来使用左移 64 位数字的高 32 位。实际的CRC计算是基于这样的逻辑：
quotient = upper 32 bits of 64 bit value / polynomial
product = quotient * polynomial
CRC = 64 bit value XOR product
除法是通过乘以倒数来完成的：x^64 / poly。由于 poly 和它的逆是 33 位，它们不能左移 32 位，所以代码在每次乘法后将乘积左移 4 个字节。 CRC 以 XMM7 的第 32 位到第 63 位结束，pextrd eax,xmm7,1 用于获取这 32 位。
我 mod 使 crc32fg.cpp 使用 CRC 多项式 0x1000000af，这就是我得到的结果。对于这个多项式，rk07 == rk08，但对于其他多项式，它们将不同。
rk01 dq 000295f2300000000h ; x^(32* 3) mod P(x) << 32
rk02 dq 0fafa517900000000h ; x^(32* 5) mod P(x) << 32
rk03 dq 05cd86bb500000000h ; x^(32*31) mod P(x) << 32
rk04 dq 0af6f37a300000000h ; x^(32*33) mod P(x) << 32
rk05 dq 000295f2300000000h ; x^(32* 3) mod P(x) << 32
rk06 dq 00000445500000000h ; x^(32* 2) mod P(x) << 32
rk07 dq 000000001000000afh ; floor(2^64/P(x))
rk08 dq 000000001000000afh ; P(x)
rk09 dq 09bd57b5d00000000h ; x^(32*27) mod P(x) << 32
rk10 dq 0b7a4d76400000000h ; x^(32*29) mod P(x) << 32
rk11 dq 01ae0004200000000h ; x^(32*23) mod P(x) << 32
rk12 dq 0e7720be600000000h ; x^(32*25) mod P(x) << 32
rk13 dq 09c7fc8fe00000000h ; x^(32*19) mod P(x) << 32
rk14 dq 03885faf800000000h ; x^(32*21) mod P(x) << 32
rk15 dq 0b477ad7100000000h ; x^(32*15) mod P(x) << 32
rk16 dq 00ac2ae3d00000000h ; x^(32*17) mod P(x) << 32
rk17 dq 05eae9dbe00000000h ; x^(32*11) mod P(x) << 32
rk18 dq 0784a483800000000h ; x^(32*13) mod P(x) << 32
rk19 dq 07d21bf2000000000h ; x^(32* 7) mod P(x) << 32
rk20 dq 0faebd3d300000000h ; x^(32* 9) mod P(x) << 32
我正在尝试编写一个 PCLMULQDQ-optimized CRC-32 implementation. The specific CRC-32 variant is for one that I don't own, but am trying to support in library form. In crcany model 表单，它具有以下参数：
width=32 poly=0xaf init=0xffffffff refin=false refout=false xorout=0x00000000 check=0xa5fd3138
（我认为遗漏的残留物是 0x00000000 但老实说不知道它是什么）
算法的基本 non-table-based/bitwise 实现（由 crcany 生成）是：
uint32_t crc32byond_bit(uint32_t crc, void const *mem, size_t len) {
unsigned char const *data = mem;
if (data == NULL)
return 0xffffffff;
for (size_t i = 0; i < len; i++) {
crc ^= (uint32_t)data[i] << 24;
for (unsigned k = 0; k < 8; k++) {
crc = crc & 0x80000000 ? (crc << 1) ^ 0xaf : crc << 1;
}
}
return crc;
}
首先，我从根本上不理解描述该算法的论文。我不知道 K1 = [x^(512+64) mod P(x)] 这样的东西是什么意思。 （什么是x？从哪里来的？我不知道。）我是一名专业的软件工程师；不是学者。坦率地说，我根本不理解这个符号，Wikipedia article 对我没有多大帮助。也许是我在线性代数方面的弱点又来困扰我了。
我知道一些 public 实现我希望吸取：
但是：
- 他们使用位反射算法，我不确定如何创建非反射变体。
- 他们好像不看论文？比如wuffs和crc32fast特别喊出不用K6，但是论文却让K6显得很有必要
我在 soft-crc but it doesn't appear to use the same constants (K4-K6?μ?)
中找到了一个英特尔实现/**
* PCLMULQDQ CRC computation context structure
*/
struct crc_pclmulqdq_ctx {
/**
* K1 = reminder X^128 / P(X) : 0-63
* K2 = reminder X^192 / P(X) : 64-127
*/
uint64_t k1;
uint64_t k2;
/**
* K3 = reminder X^64 / P(X) : 0-63
* q = quotient X^64 / P(X) : 64-127
*/
uint64_t k3;
uint64_t q;
/**
* p = polynomial / P(X) : 0-63
* res = reserved : 64-127
*/
uint64_t p;
uint64_t res;
};
我相信 我需要的 poly 0xAF 常数是：
Px = 0x1_0000_00AF
k1 = 0x0_5B5A_E0C7
k2 = 0x0_1BD8_1099
k3 = 0x0_1157_936A
k4 = 0x0_1010_1111
k5 = 0x0_0029_5F23
k6 = 0x0_0000_4455
μ = 0x1_0000_00AF
（来源：print-crc32-x86-sse42-magic-numbers.go 和 const px = "100000000000000000000000010101111"，或 0xaf | (1 << 32)）
我希望在这两个方面得到帮助
- 理解文章中使用的符号和公式（以及为什么实现似乎与文章不同？），
- 为非反射变体转换现有实现，或者可能
- 一些伪代码？
我有16、32、64位crc的6组代码，non-reflected反映在这里。该代码是为 Visual Studio 设置的。注释已添加到英特尔 github 站点中缺失的常量。
https://github.com/jeffareid/crc
32 位 non-relfected 在这里：
https://github.com/jeffareid/crc/tree/master/crc32f
您需要更改 crc32fg.cpp 中的多项式，它会生成常量。你要的多项式其实是：
0x00000001000000afull
我对 crc32fg.cpp 进行了此更改，以在该答案的末尾生成 rk.. 常量。
what is x?
CRC 使用具有 1 位系数的多项式。例如 0x0B 实际上是 x^3 + x + 1.
XMM寄存器可以读|写16字节|一次 128 位，但 PCLMULQDQ 只能将两个 64 位操作数进行无进位乘法以产生 128 位乘积。所以 128 位被拆分成两个 64 位操作数，然后每个操作数乘以一个常数以“折叠”它向前。由于 XMM 寄存器可以并行操作，因此使用 8 个 XMM 寄存器来读取 |写入 128 个字节 |一次 1024 位。每个折叠步骤“前进” 16 个字节 | 128 位数据转发 128 个字节 | 1024 位，乘以常数。较低的 64 位乘以 x^(1024) mod poly 以创建一个“高级”1024 位的 128 位乘积。高64位乘以x^(1024+64) mod poly得到一个128位乘积，即高级字节1024+64位（需要+64，因为乘积是基于高64位的128 位数据）。两个 128 位产品被异或在一起，然后与数据 128 字节进行异或运算 |缓冲区中的 1024 位之后。
注意Intel文档中的例子使用了4个XMM寄存器来推进数据64字节|一次 512 位，但我看到的 github 示例和我在 github 存储库中使用的示例使用 8 个 XMM 寄存器并前进 128 个字节 |一次 1024 位。对于数量相对较少的支持 AVX512 的处理器 | ZMM寄存器，有前进256字节的例子 |一次 2048 位。我没有带 AVX512 的电脑，所以我没有任何代码。
由于 XMM 读|写是小端，PSHUFB 用于在每次读取后反转字节。
该代码主要基于使用 65 位多项式的 64 位 CRC，但对于 32 位 CRC，这可以通过将低 32 位设置为零来处理。对于 32 位 CRC，大多数常量只有 32 位，并向左移动 32 位以简化 PCLMULQDQ 的使用，并进行调整以补偿移位，因此不是 x^(a) mod poly，它是(x^(a-32) mod 聚)<<32。实际 33 位多项式及其“逆”x^64 / 多项式的常数是 33 位并且没有左移，而使用这些常数创建实际 CRC 的 64 位值被左移 32 位。
折叠过程不产生 CRC，它只是转换数据以推进它。处理完所有数据后，使用常量 rk09、rk10、...、rk19、rk20、rk01、rk02，将 8 个 XMM 寄存器折叠成一个 128 位值。此时（标签 _128_done:) 有 128 位数据，并且由于代码基于 64 位 CRC 逻辑，逻辑上附加了 64 位零，因此实际上它是一个 192 位值，其中虚数低 64 位全部为零。高 64 位向前折叠 128 位，导致 XMM7 中的 128 位值准备计算 64 位 CRC，但由于这是 32 位 CRC，XMM7 将 96 位数据左移 32 位。高 32 位向前折叠 64 位（在这种情况下，96 位值和 rk06 都左移 32 位，因此 rk06 在这种情况下折叠 64 位（x^64 mod poly）并移位左移 32 位。结果是一个 64 位值在 XMM7 中左移 32 位。
64位数除以33位多项式的商只需要64位数的高32位，所以左移64位的值有高32位，方便计算a商。除法实际上是乘以 x^64 / 多项式，PCLMULQDQ 将仅指定使用 XMM7 的高 64 位部分来使用左移 64 位数字的高 32 位。实际的CRC计算是基于这样的逻辑：
quotient = upper 32 bits of 64 bit value / polynomial
product = quotient * polynomial
CRC = 64 bit value XOR product
除法是通过乘以倒数来完成的：x^64 / poly。由于 poly 和它的逆是 33 位，它们不能左移 32 位，所以代码在每次乘法后将乘积左移 4 个字节。 CRC 以 XMM7 的第 32 位到第 63 位结束，pextrd eax,xmm7,1 用于获取这 32 位。
我 mod 使 crc32fg.cpp 使用 CRC 多项式 0x1000000af，这就是我得到的结果。对于这个多项式，rk07 == rk08，但对于其他多项式，它们将不同。
rk01 dq 000295f2300000000h ; x^(32* 3) mod P(x) << 32
rk02 dq 0fafa517900000000h ; x^(32* 5) mod P(x) << 32
rk03 dq 05cd86bb500000000h ; x^(32*31) mod P(x) << 32
rk04 dq 0af6f37a300000000h ; x^(32*33) mod P(x) << 32
rk05 dq 000295f2300000000h ; x^(32* 3) mod P(x) << 32
rk06 dq 00000445500000000h ; x^(32* 2) mod P(x) << 32
rk07 dq 000000001000000afh ; floor(2^64/P(x))
rk08 dq 000000001000000afh ; P(x)
rk09 dq 09bd57b5d00000000h ; x^(32*27) mod P(x) << 32
rk10 dq 0b7a4d76400000000h ; x^(32*29) mod P(x) << 32
rk11 dq 01ae0004200000000h ; x^(32*23) mod P(x) << 32
rk12 dq 0e7720be600000000h ; x^(32*25) mod P(x) << 32
rk13 dq 09c7fc8fe00000000h ; x^(32*19) mod P(x) << 32
rk14 dq 03885faf800000000h ; x^(32*21) mod P(x) << 32
rk15 dq 0b477ad7100000000h ; x^(32*15) mod P(x) << 32
rk16 dq 00ac2ae3d00000000h ; x^(32*17) mod P(x) << 32
rk17 dq 05eae9dbe00000000h ; x^(32*11) mod P(x) << 32
rk18 dq 0784a483800000000h ; x^(32*13) mod P(x) << 32
rk19 dq 07d21bf2000000000h ; x^(32* 7) mod P(x) << 32
rk20 dq 0faebd3d300000000h ; x^(32* 9) mod P(x) << 32