具有 PCLMULQDQ 的快速 CRC *未反映*

我正在尝试写一个PCLMULQDQ 优化的 CRC-32 https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf执行。特定的 CRC-32 变体适用于我不拥有的变体，但我试图以库形式提供支持。在令人惊奇的模型 https://github.com/madler/crcany/blob/master/allcrcs.txt形式，它有以下参数：

width=32 poly=0xaf init=0xffffffff refin=false refout=false xorout=0x00000000 check=0xa5fd3138（省略了我认为是的残留物0x00000000但说实话我不知道那是什么）

该算法的基本非基于表/按位实现（由crcany) is:

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是什么？它从哪里来？我不知道。）我是一名专业的软件工程师；我是一名软件工程师。不是学者。坦白说，我根本看不懂这个符号，而且维基百科文章 https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks没有为我做太多事情。也许是我在线性代数方面的弱点再次困扰着我。

我知道一些我希望利用的公共实现：

• wuffs https://github.com/google/wuffs/blob/main/std/crc32/common_up_x86_sse42.wuffs
• folly https://github.com/facebook/folly/blob/main/folly/hash/detail/ChecksumDetail.cpp
• CRC32快速 https://github.com/srijs/rust-crc32fast/blob/master/src/specialized/pclmulqdq.rs

But:

• 他们使用位反射算法，我不确定如何创建非反射变体。
• 他们好像不看报纸？例如，wuffs和crc32fast特别指出他们不使用K6，但论文却让K6显得必要。

我发现了一个英特尔实施soft-crc https://github.com/intel/soft-crc/blob/34a84bfd8278ff48e6aa67f0746618242266c8a2/crc.h#L377 but it 似乎没有使用相同的常量 https://github.com/intel/soft-crc/blob/34a84bfd8278ff48e6aa67f0746618242266c8a2/crc.h#L51-L72（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;
};

I believe我需要的聚常数0xAF are:

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

（来源：打印 crc32-x86-sse42-magic-numbers.go https://github.com/google/wuffs/blob/a55e0a02a2befbd110dd2b76300b4f1caf3d3840/script/print-crc32-x86-sse42-magic-numbers.go with const px = "100000000000000000000000010101111", or 0xaf | (1 << 32))

我希望得到帮助

1. 了解文章中使用的符号和公式（以及为什么实现似乎与文章有所不同？），
2. 将现有实现转换为非反射变体，或者也许
3. 一些伪代码？

我这里有6套16、32、64位crc的代码，非反射和反射。该代码是为 Visual Studio 设置的。注释已添加到英特尔 github 站点上缺少的常量中。

https://github.com/jeffareid/crc https://github.com/jeffareid/crc

32位非反射在这里：

https://github.com/jeffareid/crc/tree/master/crc32f 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 聚)

折叠过程不会产生 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