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 / sec 的随机长度输入。

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;
}

提取交替的mask7 位元素。这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 次或、2 次与，以及两次乘法（和几次移动）以生成 8 字节。

于 2012-06-11T04:49:06.360 回答