Binary Interleaving, Binary Swizzling, Alternating Bits

user_12421768 0
Viewed 638

Problem:

I have a sequence of bits of indices 7 6 5 4 3 2 1 0 and I want to swizzle them the following way :

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

i.e. I want to interleave the bits of the low and high nibbles from a byte.

Naive solution:

I can achieve this behavior in C using the following way :

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

However it's obviously very clunky.

Striving for a more elegant solution:

I was wondering if there where something I could do to achieve this behavior faster in less machine instructions. Using SSE for example?

Some context for curious people :

I use this for packing 2d signed integer vector coordinates into a 1d value that conserves proximity when dealing with memory and caching. The idea is similar to some texture layouts optimization used by some GPUs on mobile devices. (i ^ 0xAAAAAAAA) - 0xAAAAAAAA converts from 1d integer to 1d signed integer with this power of two proximity I was talking about. (x + 0xAAAAAAAA) ^ 0xAAAAAAAA is just the reverse operation, going from 1d signed integer to a 1d integer, still with the same properties. To have it become 2d and keep the proximity property, I want to alternate the x and y bits.

bit-manipulation sse binary c
1 Answers

So you want to interleave the bits of the low and high nibbles in each byte? For scalar code a 256-byte lookup table (LUT) is probably your best bet.

For x86 SIMD, SSSE3 pshufb (_mm_shuffle_epi8) can be used as a parallel LUT of 16x nibble->byte lookups in parallel. Use this to unpack a nibble to a byte.

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

This is not faster than a memory LUT for a single byte, but it does 16 bytes in parallel. pshufb is a single-uop instruction on x86 CPUs made in the last decade. (Slow on first-gen Core 2 and K8.)

Having separate lo/hi LUT vectors means that setup can be hoisted out of a loop; otherwise we'd need to shift one LUT result before ORing together.

user_2241320
Related