2

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

五、戈帕尔等人。“使用 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 模 P(x) = 0xE8A45605
  • mu = x^64 格 P(x) = 0x104D101DF

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

4

1 回答 1

6

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

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

如果您想要商（您写为“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;
}
于 2014-01-18T07:45:36.173 回答