Sti*_*ers 4 algorithm crc32 crc
最近在学习CRC32算法。算法有很多种，我最感兴趣的是intel在2009年发表的论文：Fast CRC ComputationUsingPCLMULQDQInstruction。我已经检查了内核中的实现。
我做了一些数学，我可以完全理解在没有位反射的情况下常数是如何计算的。但我仍然感到困惑：
算法中的位反射常数是如何计算的？（本文中的位反射部分）。
在内核的实现中，我认为当我们从128位折叠到96位（第207行）时，我们应该使用k5'（0x163cd6124）来计算结果，但它似乎使用k4'（0x0ccaa009e）
我困惑了很久，也找不到自己错在哪里。:(
- 位反射常量是如何生成的？
我创建了程序来生成常量。可能存在其他示例，但在我编写自己的程序来生成常量时找不到任何示例。我生成常量，就好像没有反映一样，然后对它们进行位反转。我的程序生成用于 Visual Studio 的 32 位反射 CRC 常量 | MASM (ML64) 在这里（请注意，代码生成的常量比您链接到的示例更多）：
https://github.com/jeffareid/crc/blob/master/crc32r/crc32rg.cpp
- 使用 0x0ccaa009e
常数是右对齐的，有效地将它们乘以 2^32，因此从指数中减去 32。由于 PCLMULQDQ 将反射值乘以 2，因此常数左移 1 位，相当于除以 2。（对于 64 位反射 CRC，指数减 1，因为 64 位常数无法移位）。128 位值必须分为高位和低位 64 位值。为了将这些 64 位值向前折叠 T+64 和 T+0 位，并使用 ()' 表示反射值，常数为 (x^(T+32) mod P(x))' << 1 和 (x ^(T-32) mod P(x))' << 1 。
在 label 处less_64:，4 个 xmm 寄存器中的 512 位被折叠为单个 128 位值，一次折叠 128 位，使用 R3 = x^(128+32) mod P(x) 和 R4 = x^(128-32 ) 模 P(x)。
在标签处，fold_64:第一个归约步骤将 64 位向前折叠 96 位，并“还添加 32 个零”，因此不会从指数中减去 32，并且它使用 R4 = x^(96) mod P(x)。第二个归约步骤将 32 位向前折叠 64 位，并添加另外 32 个零，因此，不会从指数中减去 32，而是使用 R5 = x^(64) mod P(x)。生成的 64 位值将位于 xmm 寄存器的最右边 64 位中。
一旦折叠减少到 64 位值，32 位 CRC 计算如下：
quotient = 64 bit value / P(x)
product = quotient * P(x)
CRC = lower 32 bits of (64 bit value XOR product)
商不是使用无借除法，而是使用无进位乘法生成：
quotient = (upper 32 bits of 64 bit value) * (x^64 / P(x))
(x^64 / P(x)) is the "inverse" of P(x)
我使用您的链接收到文件未找到错误。我想我在这里找到了另一份副本。应该是同一个代码。
https://github.com/torvalds/linux/blob/master/arch/x86/crypto/crc32-pclmul_asm.S
Intel 在其 github 存储库中有一组 CRC 示例：
https://github.com/intel/isa-l/tree/master/crc
我将其中 6 个转换为可与 Visual Studio 一起使用 | MASM (ML64)，为一些常量添加了一些缺失的注释，并且还添加了用于生成常量的程序：
https://github.com/jeffareid/crc
代码类似，只不过它使用 8 个 xmm 寄存器一次折叠 1024 位（而不是 512 位），并且生成的 64 位值将最终位于中间 64 位，而不是 xmm 寄存器最右边的 64 位。