2

Intel Westmere と AMD Bulldozer で導入された PCLMULQDQ 命令を使用して CRC32 を効率的に実装する方法に関する次の論文を読んでいます。

V.ゴパルら。「PCLMULQDQ 命令を使用した汎用多項式の高速 CRC 計算」。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

等々。1 つの多項式のみをサポートする必要があるため、これらの定数を使用できますが、興味があります。これらの数値はどのように計算されたのでしょうか? 算術演算は GF(2) で行わなければならないため、典型的な bignum の実装 (Python が提供する実装など) だけを使用することはできません。

4

1 に答える 1

6

減算の代わりに排他的論理和を使用することを除けば、通常の除算と同じです。したがって、被除数の最も重要な 1 から始めます。排他的または多項式による被除数。多項式の最上位の 1 を被除数のその 1 と並べてゼロにします。下位nビットより上のすべての 1 を削除するまで繰り返します。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;
}
于 2014-01-18T07:45:36.173 に答える