PCLMULQDQ fast-crc 的位反射常数

Question

我对白皮书“Fast CRC Computation for Generic Polynomials Using PCLMULQDQ Instruction”中的如何计算位反射常数感到困惑。

在帖子Fast CRC with PCLMULQDQNOTreflected和How the bit-reflect constant is calculated when we use CLMUL in CRC32，@rcgldr提到“...被调整以补偿移位，所以它不是 x^(a) mod poly，而是 (x^(a-32) mod poly)<<32...”，但我不明白这是什么意思。

例如常数k1=(x^(4*128+64)%P(x))=0x8833794c（第16页）v.s. k1'=(x^(4*128+64-32)%P(x)<<32)'=(0x154442db4>>1)（第22页），我看不出这两个数字有任何反射关系（10001000_00110011_01111001_01001100 v.s 10101010_00100010_00010110_11011010）。

我想我的问题是为什么指数需要减去32来补偿左移的32位？以及为什么 k1 和 (k1)' 没有反映出来？

你能帮忙解释一下吗？谢谢

我在网上仔细搜索了这个问题的答案，特别是在StackOverflow，我试图理解相关的帖子，但需要一些专家来解释更多。

Answer 1

我修改了最初的一些英特尔示例以使用 Visual Studio | Windows，未反映和反映 16、32 和 64 位 CRC，在此 github 存储库中。

https://github.com/jeffareid/crc

我添加了一些缺失的注释，还添加了一个程序来为 6 种情况中的每一种生成汇编代码中使用的常量。

不是 x^(a) mod poly，而是 (x^(a-32) mod poly)

<<32

这是针对非反射 CRC 完成的。 CRC 保留在高 32 位，以及常数，因此 PCLMULQDQ 的结果在高 64 位结束，然后右移。将常量左移 32 位与乘以 2^32 或使用多项式表示法 x^32 相同。

对于反射 CRC，CRC 保存在低 32 位中，逻辑上是反射数的高 32 位。问题是 PCLMULQDQ 将乘积乘以 2，将乘积右移 1 位，将位 127 == 0 和位 126 中的 127 位乘积保留为 0。为了对此进行补偿，常量是 (x^(a) mod聚）

<< 1 (left shift for reflected number is == divide by 2).

github 站点上的示例代码包括 crc32rg.cpp，它是生成 crc32ra.asm 使用的常量的程序。

---

做 64 位 CRC 时会出现另一个问题。对于非反射 CRC，有时常量是 65 位（例如，如果除数是 7），但只存储低 64 位，而 2^64 位则用更多的指令处理。对于反射的 64 位 CRC，由于常量不能左移，因此使用 (x^(a-1) mod poly) 代替。

Answer 2

@rcgldr 我想我没明白你的意思……可能我没有把我的问题说清楚……

如果我对代码的理解（反向CRC32）是正确的，以最简单的场景为例，1-fold 32byte block的过程如下

。我不明白为什么常数中使用的指数分别不是128和192（=128+64）