Вычисление константы для CRC32 с помощью PCLMULQDQ

Question

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

В. Гопал и др. «Быстрое вычисление 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 = х^(4 * 128 + 64) по модулю Р (х) = 0x8833794C
• K4 = х^128 мод Р (х) = 0xE8A45605
• му = х^64 DIV Р (х) = 0x104D101DF

и так далее. Я могу просто использовать эти константы, так как мне нужно только поддерживать один полином, но мне интересно: как они вычислили эти числа? Я не могу просто использовать типичную реализацию бигнама (например, предоставленную Python), потому что арифметика должна произойти в GF (2).

Answer 1

Это как обычное подразделение, кроме вас, исключительного или вместо вычитания. Поэтому начните с наиболее значительного 1 в дивиденде. Исключительный - или дивиденд от полинома, выстраивающий наиболее значительный 1 многочлена с тем, что 1 в дивиденде превращает его в нуль. Повторяйте до тех пор, пока не удалите все из них выше нижнего n бит, где n - это порядок многочлена. В результате получается остаток.

Убедитесь, что полином имеет высокий срок в п + 1^й бит. I.e., используйте 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; 
}