x86 - QWORD 将连续的 7 位洗牌到字节对齐与 SIMD SSE...AVX

Question

我想知道在任何 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;
}

Answer 1

是的，可以使用 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;
}

掩码 提取交替的 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 有点复杂。

我不认为可以为 t1 使用不同的掩码和乘数来避免移位，因为 t1 的元素将跨越 16 位边界，这将阻止 pmullw 工作。但是，仍然有可能以某种方式进行优化。

我没有对此进行基准测试，但我怀疑它比您的标量版本快得多。如果您对其进行基准测试，请发布结果。我很想看看他们。

总而言之，该算法是 2 次移位、2 次 OR、2 次与和两次乘法(以及一些移动)以生成 8 字节。