使用PCLMULQDQ

Question

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

K1= x^（4*128+64）mod p（x）= 0x8833794c

K4= x^128 mod p（x）= 0xe8a45605

mu= x^64 div p（x）= 0x104d101df

等。我只需使用这些常数，因为我只需要支持一个多项式，但是我很感兴趣：它们如何计算这些数字？我不能只使用典型的Bignum实现（例如Python提供的实现），因为算术必须发生在GF（2）中。
• 它就像常规部门一样，除非您独家或减去。 因此，从股息中最重要的1开始。 独家或多项式的股息，将多项式最有意义的1与股息中的1套在一起，以将其变成零。 重复直到您消除了低
n

位上方的所有1，其中

n

是多项式的阶。 结果是其余部分。

Answer 1

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;
}

I转换了以后的Intel汇编代码的版本，因此我可以使用Visual Studio构建它。我向所有常数添加了注释，并包括一个程序，用于在此GitHub文件夹中的源文件中生成这些常数：

https：//github.com/jeffareid/crc/tree/master/crc32f

为了利用PCLMULQDQ用于CRC32，将大多数常数移动32位，指数减少了32位。这是针对常数PCLMULQDQ友好对准常数的，因此产品最终在XMM寄存器的上部64位。 RK07中有两个33位常数，RK08中的多项式，X^64 /多项式。
大多数代码都是使用RK03和RK04“折叠”数据。代码从加载128字节| 1024位进入XMM0-> XMM7。然后将成对的XMM寄存器向前折叠。每个XMM寄存器都有128位数据，上部有64位，下部有64位。上部64位向前“折叠”向前的1122（1024+64）位，下部64位向前折叠1024位（1024+64），因此，后来，128位变成了64位等效的1024位。数据的“折叠”一直持续，直到接近缓冲区的末端，那里完成了较小的褶皱。在最后一步，您有128位折叠数据。这被视为128位数据，然后是32位零，以160位值。下部64位左右移动64位，XOR'ED转移到上部64位为逻辑位96，然后在逻辑位索引0处折叠，产生96位结果。96位的上部32位折叠的上部32位用于折叠最终的64位在逻辑位0上折叠数据。然后计算CRC：商=数据 / CRC多项式。产品=商 * CRC多项式。 CRC =数据XOR产品。 32位结果在EAX中返回。
    

Answer 2