当我们在CRC32中使用CLMUL时，位反映常数是如何计算的？
How the bit-reflect constant is calculated when we use CLMUL in CRC32?
最近在学习CRC32算法。算法有很多种，我最感兴趣的是2009年intel发表的论文：Fast CRC Computation Using PCLMULQDQ Instruction。我检查了内核中的实现。
我做过一些数学运算，我完全可以理解在没有位反射的情况下如何计算常量。但我仍然感到困惑：
算法中bit-reflect常数是怎么计算的？ （本文中的位反射部分）。
在kernel's implementation中，我认为我们应该使用k5'(0x163cd6124)来计算从128折叠到96 位（第 207 行），但它似乎使用 k4'(0x0ccaa009e)
迷茫了好久，找不到哪里错了。 :(
- how bit-reflected constants are generated?
我创建了程序来生成常量。这些的其他示例可能存在，但在我编写自己的程序来生成常量时找不到任何示例。我生成常量就像没有反映一样，然后将它们反转。我的程序为 32 bit-reflected CRC 生成常量以与 Visual Studio 一起使用 | MASM (ML64) 在这里（注意代码生成的常量比您 linked 到的示例更多）：
https://github.com/jeffareid/crc/blob/master/crc32r/crc32rg.cpp
- 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) 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)
我在使用你的 link 时遇到一个找不到文件的错误。我想我在这里找到了另一个副本。应该是相同的代码。
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 寄存器的。
最近在学习CRC32算法。算法有很多种，我最感兴趣的是2009年intel发表的论文：Fast CRC Computation Using PCLMULQDQ Instruction。我检查了内核中的实现。
我做过一些数学运算，我完全可以理解在没有位反射的情况下如何计算常量。但我仍然感到困惑：
算法中bit-reflect常数是怎么计算的？ （本文中的位反射部分）。
在kernel's implementation中，我认为我们应该使用k5'(0x163cd6124)来计算从128折叠到96 位（第 207 行），但它似乎使用 k4'(0x0ccaa009e)
迷茫了好久，找不到哪里错了。 :(
- how bit-reflected constants are generated?
我创建了程序来生成常量。这些的其他示例可能存在，但在我编写自己的程序来生成常量时找不到任何示例。我生成常量就像没有反映一样，然后将它们反转。我的程序为 32 bit-reflected CRC 生成常量以与 Visual Studio 一起使用 | MASM (ML64) 在这里（注意代码生成的常量比您 linked 到的示例更多）：
https://github.com/jeffareid/crc/blob/master/crc32r/crc32rg.cpp
- 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) 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)
我在使用你的 link 时遇到一个找不到文件的错误。我想我在这里找到了另一个副本。应该是相同的代码。
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 寄存器的。