sse - 使用 PCLMULQDQ 计算 CRC32 的常量

Question

我正在阅读以下关于如何使用 Intel Westmere 和 AMD Bulldozer 中引入的 PCLMULQDQ 指令有效地实现 CRC32 的论文:

V.戈帕尔等。 “使用 PCLMULQDQ 指令对一般多项式进行快速 CRC 计算。” 2009. http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf

我了解该算法，但我不确定的一件事是如何计算常量 $k_i$。例如，它们为 IEEE 802.3 多项式提供常数值:

• k1 = x^(4*128+64) 模 P(x) = 0x8833794C
• k4 = x^128 mod P(x) = 0xE8A45605
• mu = x^64 div P(x) = 0x104D101DF

等等。我可以只使用这些常量，因为我只需要支持一个多项式，但我很感兴趣:他们是如何计算这些数字的？我不能只使用典型的 bignum 实现(例如 Python 提供的实现)，因为算术必须在 GF(2) 中进行。

Answer 1

这就像常规除法，除了你用异或代替减法。因此，从股息中最重要的 1 开始。异或多项式的股息，将多项式的最重要的 1 与股息中的 1 对齐，将其变为零。重复，直到您消除了低 n 位上方的所有 1，其中 n 是多项式的阶数。结果是余数。

确保您的多项式在 n+1^th 位中具有高项。即，使用 0x104C11DB7，而不是 0x4C11DB7。

如果您想要商(您将其写为“div”)，请跟踪您消除的 1 的位置。该集合向下移动 n，就是商。

方法如下:

/* Placed in the public domain by Mark Adler, Jan 18, 2014. */

#include <stdio.h>
#include <inttypes.h>

/* Polynomial type -- must be an unsigned integer type. */
typedef uintmax_t poly_t;
#define PPOLY PRIxMAX

/* Return x^n mod p(x) over GF(2).  x^deg is the highest power of x in p(x).
   The positions of the bits set in poly represent the remaining powers of x in
   p(x).  In addition, returned in *div are as many of the least significant
   quotient bits as will fit in a poly_t. */
static poly_t xnmodp(unsigned n, poly_t poly, unsigned deg, poly_t *div)
{
    poly_t mod, mask, high;

    if (n < deg) {
        *div = 0;
        return poly;
    }
    mask = ((poly_t)1 << deg) - 1;
    poly &= mask;
    mod = poly;
    *div = 1;
    deg--;
    while (--n > deg) {
        high = (mod >> deg) & 1;
        *div = (*div << 1) | high;  /* quotient bits may be lost off the top */
        mod <<= 1;
        if (high)
            mod ^= poly;
    }
    return mod & mask;
}

/* Compute and show x^n modulo the IEEE 802.3 CRC-32 polynomial.  If d is true,
   also show the low bits of the quotient. */
static void show(unsigned n, int showdiv)
{
    poly_t div;

    printf("x^%u mod p(x) = %#" PPOLY "\n", n, xnmodp(n, 0x4C11DB7, 32, &div));
    if (showdiv)
        printf("x^%u div p(x) = %#" PPOLY "\n", n, div);
}

/* Compute the constants required to use PCLMULQDQ to compute the IEEE 802.3
   32-bit CRC.  These results appear on page 16 of the Intel paper "Fast CRC
   Computation Using PCLMULQDQ Instruction". */
int main(void)
{
    show(4*128+64, 0);
    show(4*128, 0);
    show(128+64, 0);
    show(128, 0);
    show(96, 0);
    show(64, 1);
    return 0;
}