时间戳

首页 > 解决方案 > 二进制交错、二进制混合、交替位

c - 二进制交错、二进制混合、交替位

问题描述

问题：

我有一系列索引位，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只是相反的操作，从一维有符号整数到一维整数，仍然具有相同的属性。为了让它变成 2d 并保持邻近属性，我想交替 x 和 y 位。

标签： cbinarybit-manipulationsse

解决方案

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

对于 x86 SIMD，SSSE3 pshufb( _mm_shuffle_epi8) 可用作 16x nibble->byte 并行查找的并行 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 上的单微指令。（第一代 Core 2 和 K8 速度较慢。）

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

推荐阅读