Бинарное чередование, бинарное чередование, переменные биты - PullRequest
Новая
       72

Бинарное чередование, бинарное чередование, переменные биты

2 голосов
/ 02 апреля 2020

Проблема:

У меня есть последовательность битов индексов 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, например?

Некоторый контекст для любопытных:

Я использую это для упаковки 2-х целочисленных векторных координат со знаком в 1-е значение, которое сохраняет близость при работе с памятью и кэшированием. Идея аналогична оптимизации некоторых текстурных макетов, используемых некоторыми графическими процессорами на мобильных устройствах. (i ^ 0xAAAAAAAA) - 0xAAAAAAAA преобразует из 1d целого числа в 1d целое число со знаком с этой степенью близости, о которой я говорил. (x + 0xAAAAAAAA) ^ 0xAAAAAAAA - это просто обратная операция, переходящая от 1-го целого числа со знаком к 1-му целому числу, но с теми же свойствами. Чтобы он стал 2d и сохранял свойство близости, я хочу чередовать биты x и y.

1 Ответ

3 голосов
/ 02 апреля 2020

То есть вы хотите чередовать биты нижнего и верхнего полубайтов в каждом байте? Для скалярного кода лучше всего подойдет 256-байтовая таблица поиска (LUT).

Для x86 SIMD SSSE3 pshufb (_mm_shuffle_epi8) может использоваться в качестве параллельной LUT из 16x nibble-> 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);
}

Это не быстрее, чем LUT памяти для одного байта, но он делает 16 байтов параллельно . pshufb - это инструкция с одним мопом для процессоров x86, созданная в последнее десятилетие. (Медленно на Core 2 и K8 первого поколения.)

Наличие отдельных векторов LUT lo / hi означает, что установка может быть выведена из цикла; в противном случае нам нужно было бы сдвинуть один результат LUT перед выполнением ORing вместе.

...