algorithm - 当我们在CRC32中使用CLMUL时，位反射(reflect)常数是如何计算的？

Question

最近在学习CRC32算法。算法有很多种，我最感兴趣的是2009年intel发表的论文:Fast CRC Computation Using PCLMULQDQ Instruction .我已经检查了内核中的实现。

我做过一些数学运算，我完全可以理解在没有位反射的情况下如何计算常量。但我仍然感到困惑:

1. bit-reflect常数在算法中是如何计算的？ (本文中的位反射部分)。

2. 在kernel's implementation ，我认为当我们从 128 位折叠到 96 位时(第 207 行)，我们应该使用 k5'(0x163cd6124) 来计算结果，但它似乎使用了 k4'( 0x0ccaa009e)

迷茫了半天，找不到哪里错了。 :(

Answer 1

1. how bit-reflected constants are generated?

我创建了程序来生成常量。这些的其他示例可能存在，但在我编写自己的程序来生成常量时找不到任何示例。我生成常量就像没有反射(reflect)一样，然后将它们反转。我的程序为 32 位反射(reflect)的 CRC 生成常量以与 Visual Studio 一起使用 | MASM (ML64) 在这里(注意代码生成的常量比您链接到的示例更多):

https://github.com/jeffareid/crc/blob/master/crc32r/crc32rg.cpp

2. uses 0x0ccaa009e

常数是右对齐的，有效地将它们乘以 2^32，因此从指数中减去 32。由于 PCLMULQDQ 将反射值乘以 2，因此常量左移 1 位，相当于除以 2。(对于 64 位反射 CRC，指数减 1，因为 64 位常量不能移位)。 128 位值必须拆分为高 64 位值和低 64 位值。要将这些 64 位值向前折叠 T+64 和 T+0 位，并使用 ()' 表示反射值，常数为 (x^(T+32) mod P(x))' << 1 和 (x ^(T-32) mod P(x))' << 1 .

在标签less_64:处，将4个xmm寄存器中的512位折叠成一个128位的值，一次折叠128位，使用R3 = x^(128+32) mod P (x) 和 R4 = x^(128-32) mod P(x)。

在标签 fold_64: 第一个缩减步骤将 64 位向前折叠 96 位并“还添加了 32 个零”，因此 32 没有从指数中减去，它使用 R4 = x^(96 ) 模 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 位而不是最右边的 64 位结束xmm注册。