Zac*_*Zac 4 assembly crc32 sse crc
我正在尝试编写PCLMULQDQ 优化的 CRC-32实现。特定的 CRC-32 变体适用于我不拥有的变体，但我试图以库形式提供支持。在crcany模型形式中，它具有以下参数：
\nwidth=32 poly=0xaf init=0xffffffff refin=false refout=false xorout=0x00000000 check=0xa5fd3138\n（省略了我认为是0x00000000但老实说不知道它是什么的残留物）
该算法的基本非基于表/按位实现（由 生成crcany）是：
uint32_t crc32byond_bit(uint32_t crc, void const *mem, size_t len) {\n unsigned char const *data = mem;\n if (data == NULL)\n return 0xffffffff;\n for (size_t i = 0; i < len; i++) {\n crc ^= (uint32_t)data[i] << 24;\n for (unsigned k = 0; k < 8; k++) {\n crc = crc & 0x80000000 ? (crc << 1) ^ 0xaf : crc << 1;\n }\n }\n return crc;\n}\n首先，我从根本上不理解描述该算法的论文。我不知道类似的东西是什么K1 = [x^(512+64) mod P(x)]意思。（x是什么？它从哪里来？我不知道。）我是专业软件工程师；不是学者。坦率地说，我根本不理解这些符号，维基百科的文章对我也没有多大帮助。也许是我在线性代数方面的弱点再次困扰着我。
我知道一些我希望利用的公共实现：
\n\n但：
\n我在soft-crc中找到了一个 Intel 实现，但它似乎没有使用相同的常量（K4-K6？\xce\xbc？）
\n/**\n * PCLMULQDQ CRC computation context structure\n */\nstruct crc_pclmulqdq_ctx {\n /**\n * K1 = reminder X^128 / P(X) : 0-63\n * K2 = reminder X^192 / P(X) : 64-127\n */\n uint64_t k1;\n uint64_t k2;\n\n /**\n * K3 = reminder X^64 / P(X) : 0-63\n * q = quotient X^64 / P(X) : 64-127\n */\n uint64_t k3;\n uint64_t q;\n\n /**\n * p = polynomial / P(X) : 0-63\n * res = reserved : 64-127\n */\n uint64_t p;\n uint64_t res;\n};\n我相信我需要的 Poly 常数0xAF是：
Px = 0x1_0000_00AF\nk1 = 0x0_5B5A_E0C7\nk2 = 0x0_1BD8_1099\nk3 = 0x0_1157_936A\nk4 = 0x0_1010_1111\nk5 = 0x0_0029_5F23\nk6 = 0x0_0000_4455\n\xce\xbc = 0x1_0000_00AF\n（来源：print-crc32-x86-sse42-magic-numbers.go与const px = "100000000000000000000000010101111", 或0xaf | (1 << 32)）
我希望在这两方面得到帮助
\n我这里有6套16、32、64位crc的代码，非反射和反射。该代码是为 Visual Studio 设置的。注释已添加到英特尔 github 站点上缺少的常量中。
https://github.com/jeffareid/crc
32位非反射在这里：
https://github.com/jeffareid/crc/tree/master/crc32f
您需要更改 crc32fg.cpp 中生成常数的多项式。你想要的多项式实际上是：
0x00000001000000afull
我对 crc32fg.cpp 进行了此更改，以在本答案末尾生成 rk.. 常量。
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 以创建高级字节 1024+64 位的 128 位乘积（需要 +64，因为该乘积基于 128 位的高 64 位）数据）。两个 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，它只是转换数据以推进数据。处理完所有数据后，8 个 XMM 寄存器将使用常量 rk09、rk10、...、rk19、rk20、rk01、rk02 折叠为一个 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 位. 结果是 XMM7 中的 64 位值左移 32 位。
64位数除以33位多项式的商只需要64位数的高32位，因此左移的64位值具有高32位，可以方便计算商。除法实际上是乘以 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。由于多项式及其逆为 33 位，因此它们无法左移 32 位，因此代码在每次乘法后将乘积左移 4 个字节。CRC 最终位于 XMM7 的第 32 至 63 位中，pextrd eax,xmm7,1用于获取这 32 位。
我修改了 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
| 归档时间： |
|
| 查看次数： |
559 次 |
| 最近记录： |