二进制交错、二进制调配、交替位

Question

问题：

我有一系列索引 7 6 5 4 3 2 1 0，我想按以下方式调整它们：

7 6 5 4 3 2 1 0  =  7 6 5 4 3 2 1 0
   _____| | | |     | | | |_____
  |    ___| | |     | | |___    |  
  |   |    _| |     | |_    |   |  
  |   |   |   |     |   |   |   |  
  v   v   v   v     v   v   v   v  
_ 3 _ 2 _ 1 _ 0     7 _ 6 _ 5 _ 4 _
       |___________________|
                 |
                 v
          7 3 6 2 5 1 4 0

即我想交错一个字节的低半字节和高半字节。

天真的解决方案：

我可以使用以下方式在 C 中实现此行为：

int output = 
    ((input & (1 <<  0)) << 0) |
    ((input & (1 <<  1)) << 1) |
    ((input & (1 <<  2)) << 2) |
    ((input & (1 <<  3)) << 3) |
    ((input & (1 <<  4)) >> 3) |
    ((input & (1 <<  5)) >> 2) |
    ((input & (1 <<  6)) >> 1) |
    ((input & (1 <<  7)) >> 0);

然而，它显然很笨重。

争取更优雅的解决方案：

我想知道我是否可以做些什么来用更少的机器指令更快地实现这种行为。以 SSE 为例？

好奇的人的一些背景：

我用它来将 2d 有符号整数矢量坐标打包成 1d 值，在处理内存和缓存时保持接近度。这个想法类似于某些 GPU 在移动设备上使用的一些纹理布局优化。 (i ^ 0xAAAAAAAA) - 0xAAAAAAAA 将 1d 整数转换为 1d 有符号整数，具有我所说的两个接近度的幂。 (x + 0xAAAAAAAA) ^ 0xAAAAAAAA 只是反向操作，从 1d 有符号整数到 1d 整数，仍然具有相同的属性。为了让它成为 2d 并保持接近度属性，我想交替 x 和 y 位。

Answer 1

所以你想交错每个字节中的低半字节和高半字节？对于标量代码，256 字节查找 table (LUT) 可能是您最好的选择。

对于 x86 SIMD，SSSE3 pshufb (_mm_shuffle_epi8) 可用作 16x 半字节-> 字节并行查找的并行 LUT。使用它可以将一个半字节解压缩为一个字节。

__m128i interleave_high_low_nibbles(__m128i v) {
    const __m128i lut_unpack_bits_low = _mm_setr_epi8( 0, 1, 0b00000100, 0b00000101, 
              ...   // dcba -> 0d0c0b0a
     );
    const __m128i lut_unpack_bits_high = _mm_slli_epi32(lut_unpack_bits_low, 1);
                    // dcba -> d0c0b0a0

   // ANDing is required because pshufb uses the high bit to zero that element
   // 8-bit element shifts aren't available so also we have to mask after shifting
    __m128i lo = _mm_and_si128(v, _mm_set1_epi8(0x0f));
    __m128i hi = _mm_and_si128(_mm_srli_epi32(v, 4), _mm_set1_epi8(0x0f));

    lo = _mm_shuffle_epi8(lut_unpack_bits_low, lo);
    hi = _mm_shuffle_epi8(lut_unpack_bits_high, hi);
    return _mm_or_si128(lo, hi);
}

对于单个字节，这并不比内存 LUT 快，但是它并行执行 16 个字节。 pshufb 是近十年来在 x86 CPU 上的一条单 uop 指令。（在第一代 Core 2 和 K8 上速度较慢。）

具有单独的 lo/hi LUT 向量意味着可以将设置提升到循环之外；否则我们需要在进行 ORing 之前移动一个 LUT 结果。

二进制交错、二进制调配、交替位

Binary Interleaving, Binary Swizzling, Alternating Bits

c

binary

bit-manipulation

sse

问题：

天真的解决方案：

争取更优雅的解决方案：

好奇的人的一些背景：