PCLMULQDQ - Packed CarryLess MULtiplication Qword DoubleQword

サンプル:GCM/GMACのドット演算への応用

Intelのサンプルでは最初の255ビットの積を求めるところだけこの命令を使い、そのあと定数Rを掛けるところはビットシフトとXORで行っていますが、むしろ積極的にこの命令を使ったほうが速いようです(手元のVisiaul Studio 2017とi7-7700で確認)。

/////////////////////////////////////////////////
// GCM/GMACのドット演算
// NOTE: x、y、戻り値はリトルエンディアン

// MS Visual Studioでは
// この定数を関数の内部で定義するとなぜか実行速度が信じられないくらい遅くなる
static const __m128i R = _mm_set_epi64x(0xE100000000000000, 0);

__m128i GCM_Mul_LE(__m128i x, __m128i y)
{
    // xとyをキャリーレス乗算して255ビットの積を z:zL にセットする

    __m128i zL  = _mm_clmulepi64_si128(x, y, 0x00);
    __m128i zM  = _mm_clmulepi64_si128(x, y, 0x01);
    __m128i zM2 = _mm_clmulepi64_si128(x, y, 0x10);
    __m128i z   = _mm_clmulepi64_si128(x, y, 0x11);
    zM = _mm_xor_si128(zM, zM2);
    zL = _mm_xor_si128(zL, _mm_slli_si128(zM, 8));
    z  = _mm_xor_si128(z,  _mm_srli_si128(zM, 8));

    // z:zL の256ビット
    //  ビット255: ゼロ
    //  ビット254-127: 積の上位128ビット
    //  ビット126-0: オーバーフローしたビット

    // オーバーフローしたビットを左詰めで取り出す
    __m128i ov = _mm_slli_epi64(zL, 1);
    ov = _mm_or_si128(ov, _mm_slli_si128(_mm_srli_epi64(zL, 63), 8));

    // オーバーフロービットの下位にRをキャリーレス乗算する
    __m128i wM = _mm_clmulepi64_si128(ov, R, 0x10);
    __m128i wL = _mm_slli_si128(wM, 8);

    // wL の128ビット
    //  ビット127: R * オーバーフロービットの上位128ビットのうちの最下位ビット
    //  ビット126-121: 再オーバーフロービット
    //  ビット120-0: ゼロ

    // 再オーバーフロービットを左詰めで取り出す
    __m128i w2 = _mm_slli_epi64(wL, 1);             
    ov = _mm_xor_si128(ov, w2);

    // (オーバーフロービット ^ 再オーバーフロービット)にRをキャリーレス乗算する
    __m128i w  = _mm_clmulepi64_si128(ov, R, 0x11);
    // wMとwLの計算には再オーバーフロービットをXORしたことの影響は出ないので
    // 前に計算した値をそのまま使う
    w = _mm_xor_si128(w, _mm_srli_si128(wM, 8));

    // w:wL の256ビット
    //  ビット255: ゼロ
    //  ビット254-127: R * (オーバーフロービット ^ 再オーバーフロービット)
    //  bit 126-0: ゴミ

    // z:zL に w:wL をXORして最終結果を求める
    z  = _mm_xor_si128(z, w);
    zL = _mm_xor_si128(zL, wL);

    // z:zL の256ビット
    //  ビット255: ゼロ
    //  ビット254-127: 最終結果
    //  ビット126-0: ゴミ

    // 最終結果を取り出す
    __m128i hc = _mm_srli_epi64(z, 63);
    __m128i lc = _mm_srli_epi64(zL, 63);
    z  = _mm_slli_epi64(z, 1);
    hc = _mm_unpackhi_epi64(lc, _mm_slli_si128(hc, 8));
    z  = _mm_or_si128(z, hc);

    return z;
}

x86/x64 SIMD命令一覧表 フィードバック

ホームページ http://www.officedaytime.com/