Расчет констант для CRC32 с использованием PCLMULQDQ

Question

Я читаю следующую статью о том, как эффективно реализовать CRC32 с помощью инструкции PCLMULQDQ, представленной в Intel Westmere и AMD Bulldozer:

V. Gopal и соавт. "Быстрые вычисления CRC для общих полиномов с использованием инструкции PCLMULQDQ". 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) mod 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 в дивиденде, чтобы превратить его в ноль. Повторяйте до тех пор, пока вы не удалите все 1 выше младших n битов, где n - порядок многочлена. Результатом является остаток.

Убедитесь, что ваш полином имеет старший член в n+1-^м бите. Т.е. использовать 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;
}