3

SIMD ファミリーの命令のいずれかで以下が可能かどうかを知りたいです。

有効ビット数が 63 の qword 入力があります (決して負ではありません)。LSB から始まる一連の 7 ビットはそれぞれ、バイトにシャッフル整列され、左パディングは 1 です (ゼロ以外の最上位バイトを除く)。説明のために、わかりやすくするために文字を使用します。

結果は、バイト配列に変換される 0 から 9 のサイズの有効なバイトのみです。

In:         0|kjihgfe|dcbaZYX|WVUTSRQ|PONMLKJ|IHGFEDC|BAzyxwv|utsrqpo|nmlkjih|gfedcba
Out: 0kjihgfe|1dcbaZYX|1WVUTSRQ|1PONMLKJ|1IHGFEDC|1BAzyxwv|1utsrqpo|1nmlkjih|1gfedcba

サイズ = 9

In:  00|nmlkjih|gfedcba
Out: |0nmlkjih|1gfedcba

サイズ = 2

パディングが別であることは理解しています。シャッフル調整は私の質問です。これは可能ですか？

編集2

これが私の更新されたコードです。シングル スレッド Core 2 Duo 2 GHz、64 ビットでランダムな長さの入力に対して持続的な 46 M/秒を取得します。

private static int DecodeIS8(long j, ref byte[] result)
{
    if (j <= 0)
    {
        return 0;
    }

    int size;

    // neater code: gives something to break out of
    while (true)
    {
        result[0] = (byte)((j & 0x7F) | 0x80);
        size = 0;
        j >>= 7;

        if (j == 0) break;

        result[1] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[2] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[3] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[4] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[5] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[6] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[7] = (byte)((j & 0x7F) | 0x80);
        size++;
        j >>= 7;

        if (j == 0) break;

        result[8] = (byte)j;

        return 9;
    }

    result[size] ^= 0x80;

    return size + 1;
}
4

1 に答える 1

6

はい、MMX/SSE のpmullw命令 (組み込み関数: _mm_mullo_pi16) を使用して、要素ごとのシフトを行うことができます。

基本的な考え方は、AND 命令で交互の 7 ビット要素を抽出しpmullw、要素を所定の位置にシフトするために を実行することです。これで要素の半分のタスクが完了するため、このプロセスを数回追加で繰り返す必要があります。

#include <stdio.h>
#include <stdint.h>
#include <mmintrin.h>

__m64 f(__m64 input) {
    static const __m64 mask = (__m64) 0xfe03f80fe03f80UL;
    static const __m64 multiplier = (__m64) 0x0080002000080002UL;

    __m64 t0 = _mm_and_si64 (input, mask);
    __m64 t1 = _mm_and_si64 (_mm_srli_si64 (input, 7), mask);

    t0 = _mm_mullo_pi16 (t0, multiplier);
    t1 = _mm_mullo_pi16 (t1, multiplier);

    __m64 res =  _mm_or_si64 (t0, _mm_slli_si64 (t1, 8));
    /* set most significant bits, except for in most significant byte */
    return _mm_or_si64 (res, (__m64) 0x0080808080808080UL);
}

int main(int argc, char *argv[])
{
    int i;
    typedef union {
            __m64 m64;
            unsigned char _8x8[8];
    } type_t;

    /* 0x7f7e7c7870608080 = {127, 63, 31, 15, 7, 3, 2, 1, 0} */
    type_t res0 = { .m64 = f((__m64) 0x7f7e7c7870608080UL) };

    for (i = 0; i < 8; i++) {
            printf("%3u ", res0._8x8[i]);
    }
    puts("");

    return 0;
}

はmask交互の 7 ビット要素を抽出します。はmultiplier、要素ごとのシフトを指定できる定数です。これは、マスクされた入力を見ることから派生しています。

00000000|dcbaZYX0|000000PO|NMLKJ000|0000BAzy|xwv00000|00nmlkji|h0000000

そしてそれに気づく

00000000|dcbaZYX0 needs to be shifted by 7 (or multiplied by 2^7, 128, 0x0080)
000000PO|NMLKJ000 needs to be shifted by 5 (or multiplied by 2^5,  32, 0x0020)
0000BAzy|xwv00000 needs to be shifted by 3 (or multiplied by 2^3,   8, 0x0008)
00nmlkji|h0000000 needs to be shifted by 1 (or multiplied by 2^1,   2, 0x0002)

この関数は一度に 8 バイトを書き込むため (9 つの 7 ビット要素がアンパックされる 9 バイトではなく)、各反復後にソース ポインターを 7 バイトだけ進める必要があります。このため、SSE2 への変換はもう少し複雑です。

の要素が 16 ビットの境界を越えて動作しなくなるt1ため、シフトを回避するために別のマスクと乗数を使用することはできないと思います。しかし、何らかの方法で最適化することはまだ可能かもしれません。t1pmullw

これをベンチマークしたことはありませんが、スカラー バージョンよりも大幅に高速であると思われます。ベンチマークしたら、結果を投稿してください。私はそれらを見ることに非常に興味があります。

全体として、アルゴリズムは 2 つのシフト、2 つの or、2 つの and、2 つの乗算 (およびいくつかの移動) で 8 バイトを生成します。

于 2012-06-11T04:49:06.360 に答える