Оптимальное uint8_t растровый в 8 х 32-битный SIMD «BOOL» вектор

Question

В рамках алгоритма сжатия, я искал оптимальный путь для достижения следующего:

У меня есть простой растровое изображение в uint8_t. Например 01010011

То, что я хочу, это __m256i в виде: (0, MaxInt, 0, MaxInt, 0, 0, MaxInt, MaxInt)

Одним из способов достижения этой цели является перетасовки вектор 8 x maxint в вектор нулей. Но для этого сначала требуется, чтобы я расширил свой uint8_t до нужного растрового изображения в случайном порядке.

Мне интересно, есть ли лучший способ?

Answer 1

Вот решение (PaulR улучшило мое решение, см. Конец моего ответа или его ответ) на основе вариации этого вопроса fastest-way-to-broadcast-32-bits-in-32-bytes.

__m256i t1 = _mm256_set1_epi8(x); 
__m256i t2 = _mm256_and_si256(t1, mask); 
__m256i t4 = _mm256_cmpeq_epi32(t2, _mm256_setzero_si256()); 
t4 = _mm256_xor_si256(t4, _mm256_set1_epi32(-1)); 

Я не AVX2 оборудование, чтобы проверить это прямо сейчас, но вот версия SSE2 показывает, что он работает, который также показывает, как определить маску.

#include <x86intrin.h> 
#include <stdint.h> 
#include <stdio.h> 

int main(void) { 
    char mask[32] = { 
     0x01, 0x00, 0x00, 0x00, 
     0x02, 0x00, 0x00, 0x00, 
     0x04, 0x00, 0x00, 0x00, 
     0x08, 0x00, 0x00, 0x00, 
     0x10, 0x00, 0x00, 0x00, 
     0x20, 0x00, 0x00, 0x00, 
     0x40, 0x00, 0x00, 0x00, 
     0x80, 0x00, 0x00, 0x00, 
    }; 
    __m128i mask1 = _mm_loadu_si128((__m128i*)&mask[ 0]); 
    __m128i mask2 = _mm_loadu_si128((__m128i*)&mask[16]); 

    uint8_t x = 0x53; //0101 0011 
    __m128i t1 = _mm_set1_epi8(x); 
    __m128i t2 = _mm_and_si128(t1, mask1); 
    __m128i t3 = _mm_and_si128(t1, mask2); 
    __m128i t4 = _mm_cmpeq_epi32(t2,_mm_setzero_si128()); 
    __m128i t5 = _mm_cmpeq_epi32(t3,_mm_setzero_si128()); 
    t4 = _mm_xor_si128(t4, _mm_set1_epi32(-1)); 
    t5 = _mm_xor_si128(t5, _mm_set1_epi32(-1)); 

    int o1[4], o2[4]; 
    _mm_store_si128((__m128i*)o1, t4); 
    _mm_store_si128((__m128i*)o2, t5); 
    for(int i=0; i<4; i++) printf("%d \n", o1[i]); 
    for(int i=0; i<4; i++) printf("%d \n", o2[i]); 

} 

Edit:

PaulR улучшил мое решение

__m256i v = _mm256_set1_epi8(u); 
v = _mm256_and_si256(v, mask); 
v = _mm256_xor_si256(v, mask); 
return _mm256_cmpeq_epi32(v, _mm256_setzero_si256()); 

с маской определяется как

int mask[8] = { 
    0x01010101, 0x02020202, 0x04040404, 0x08080808, 
    0x10101010, 0x20202020, 0x40404040, 0x80808080, 
}; 

См свой ответ с тестирования производительности для получения более подробной информации.

Answer 2

Я думаю, что я бы, вероятно, пойти на подходе "грубой силы и невежества" изначально, может быть что-то вроде этого:

uint8_t u = 0x53; // 01010011 

const union { 
    uint32_t a[4]; 
    __m128i v; 
} kLUT[16] = { { { 0, 0, 0, 0 } }, 
       { { -1, 0, 0, 0 } }, 
       { { 0, -1, 0, 0 } }, 
       { { -1, -1, 0, 0 } }, 
       { { 0, 0, -1, 0 } }, 
       { { -1, 0, -1, 0 } }, 
       { { 0, -1, -1, 0 } }, 
       { { -1, -1, -1, 0 } }, 
       { { 0, 0, 0, -1 } }, 
       { { -1, 0, 0, -1 } }, 
       { { 0, -1, 0, -1 } }, 
       { { -1, -1, 0, -1 } }, 
       { { 0, 0, -1, -1 } }, 
       { { -1, 0, -1, -1 } }, 
       { { 0, -1, -1, -1 } }, 
       { { -1, -1, -1, -1 } } }; 
__m256i v = _mm256_set_m128i(kLUT[u >> 4].v, kLUT[u & 15].v); 

Использование clang -O3 это компилируется:

movl %ebx, %eax    ;; eax = ebx = u 
andl $15, %eax     ;; get low offset = (u & 15) * 16 
shlq $4, %rax 
leaq _main.kLUT(%rip), %rcx ;; rcx = kLUT 
vmovaps (%rax,%rcx), %xmm0  ;; load low half of ymm0 from kLUT 
andl $240, %ebx    ;; get high offset = (u >> 4) * 16 
vinsertf128 $1, (%rbx,%rcx), %ymm0, %ymm0 
            ;; load high half of ymm0 from kLUT 

---

FWIW я бросил вместе простой тест проводов для трех реализаций: (я) простой скаляр код эталонной реализации, (б) выше код, (III) реализация на основе @ ответ Zboson, в (я v) несколько улучшенная версия (iii) и (v) дальнейшее улучшение на (iv) с использованием предложения от @MarcGlisse. Я получил следующие результаты с 2.6GHz Haswell CPU (скомпилирован с clang -O3):

scalar code:         7.55336 ns/vector 
Paul R:          1.36016 ns/vector 
Z boson:          1.24863 ns/vector 
Z boson (improved):       1.07590 ns/vector 
Z boson (improved + @MarcGlisse suggestion): 1.08195 ns/vector 

Так @ решения Zboson (ов) выигрыш, примерно 10% - 20%, по-видимому, потому что они нужны только 1 нагрузку, по сравнению 2 для моего.

Если мы получим какие-либо другие реализации, я добавлю их на тестовый жгут и обновить результаты.

---

Немного улучшенная версия @ реализации Zboson в:

__m256i v = _mm256_set1_epi8(u); 
v = _mm256_and_si256(v, mask); 
v = _mm256_xor_si256(v, mask); 
return _mm256_cmpeq_epi32(v, _mm256_setzero_si256()); 

---

Далее улучшенный вариант @ реализации, включающего предложения Zboson в от @MarcGlisse:

__m256i v = _mm256_set1_epi8(u); 
v = _mm256_and_si256(v, mask); 
return _mm256_cmpeq_epi32(v, mask); 

(Обратите внимание, что mask должен содержать реплицируются 8 бит значения в каждом 32-битном элементе, то есть 0x01010101, 0x02020202, ..., 0x80808080)

---

Answer 3

Основываясь на всех ответах, я взломал решение, используя превосходную библиотеку Agner Fog (которая обрабатывает как решения AVX2, AVX, так и SSE с общей абстракцией). Я хотел бы рассказать об этом в качестве альтернативного ответа:

// Used to generate 32 bit vector bitmasks from 8 bit ints 
static const Vec8ui VecBitMask8(
     0x01010101 
    , 0x02020202 
    , 0x04040404 
    , 0x08080808 
    , 0x10101010 
    , 0x20202020 
    , 0x40404040 
    , 0x80808080); 

// As above, but for 64 bit vectors and 4 bit ints 
static const Vec4uq VecBitMask4(
     0x0101010101010101 
    , 0x0202020202020202 
    , 0x0404040404040404 
    , 0x0808080808080808); 

template <typename V> 
inline static Vec32c getBitmapMask(); 

template <> inline Vec32c getBitmapMask<Vec8ui>() {return VecBitMask8;}; 
template <> inline Vec32c getBitmapMask<Vec8i>() {return VecBitMask8;}; 
template <> inline Vec32c getBitmapMask<Vec4uq>() {return VecBitMask4;}; 
template <> inline Vec32c getBitmapMask<Vec4q>() {return VecBitMask4;}; 

// Returns a bool vector representing the bitmask passed. 
template <typename V> 
static inline V getBitmap(const uint8_t bitMask) { 
    Vec32c mask = getBitmapMask<V>(); 
    Vec32c v1(bitMask); 
    v1 = v1 & mask; 
    return ((V)v1 == (V)mask); 
}