Быстрое подсчет количества установленных битов в регистре __m128i

Question

Я должен подсчитать количество битов набора из регистра __m128i. В частности, я должен написать две функции, которые могут подсчитывать количество бит регистра, используя следующие способы.

1. Общее количество заданных бит регистра.
2. Число заданных бит для каждого байта регистра.

Существуют ли внутренние функции, которые могут выполнять, полностью или частично, вышеуказанные операции?

Answer 1

Вот несколько кодов, которые я использовал в старом проекте(). Функция popcnt8 ниже вычисляет количество бит, установленных в каждом байте.

SSE2-единственная версия (на основе алгоритма 3 в Hacker's Delight book):

static const __m128i popcount_mask1 = _mm_set1_epi8(0x77); 
static const __m128i popcount_mask2 = _mm_set1_epi8(0x0F); 
static inline __m128i popcnt8(__m128i x) { 
    __m128i n; 
    // Count bits in each 4-bit field. 
    n = _mm_srli_epi64(x, 1); 
    n = _mm_and_si128(popcount_mask1, n); 
    x = _mm_sub_epi8(x, n); 
    n = _mm_srli_epi64(n, 1); 
    n = _mm_and_si128(popcount_mask1, n); 
    x = _mm_sub_epi8(x, n); 
    n = _mm_srli_epi64(n, 1); 
    n = _mm_and_si128(popcount_mask1, n); 
    x = _mm_sub_epi8(x, n); 
    x = _mm_add_epi8(x, _mm_srli_epi16(x, 4)); 
    x = _mm_and_si128(popcount_mask2, x); 
    return x; 
} 

SSSE3 версии (из-за Wojciech Mula):

static const __m128i popcount_mask = _mm_set1_epi8(0x0F); 
static const __m128i popcount_table = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4); 
static inline __m128i popcnt8(__m128i n) { 
    const __m128i pcnt0 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(n, popcount_mask)); 
    const __m128i pcnt1 = _mm_shuffle_epi8(popcount_table, _mm_and_si128(_mm_srli_epi16(n, 4), popcount_mask)); 
    return _mm_add_epi8(pcnt0, pcnt1); 
} 

версия XOP (эквивалент SSSE3, но использует инструкции XOP которые работают быстрее на AMD Bulldozer)

static const __m128i popcount_mask = _mm_set1_epi8(0x0F); 
static const __m128i popcount_table = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4); 
static const __m128i popcount_shift = _mm_set1_epi8(-4); 
static inline __m128i popcount8(__m128i n) { 
    const __m128i pcnt0 = _mm_perm_epi8(popcount_table, popcount_table, _mm_and_si128(n, popcount_mask)); 
    const __m128i pcnt1 = _mm_perm_epi8(popcount_table, popcount_table, _mm_shl_epi8(n, popcount_shift)); 
    return _mm_add_epi8(pcnt0, pcnt1); 
} 

Fuctio п ниже popcnt64 подсчитывает число бит в низких и высоких 64-битовых частях SSE регистра:

SSE2 версия:

static inline __m128i popcnt64(__m128i n) { 
    const __m128i cnt8 = popcnt8(n); 
    return _mm_sad_epu8(cnt8, _mm_setzero_si128()); 
} 

XOP версия:

static inline __m128i popcnt64(__m128i n) { 
    const __m128i cnt8 = popcnt8(n); 
    return _mm_haddq_epi8(cnt8); 
} 

Наконец, функция popcnt128 ниже подсчет количества бит во всем 128-битном регистре:

static inline int popcnt128(__m128i n) { 
    const __m128i cnt64 = popcnt64(n); 
    const __m128i cnt64_hi = _mm_unpackhi_epi64(cnt64, cnt64); 
    const __m128i cnt128 = _mm_add_epi32(cnt64, cnt64_hi); 
    return _mm_cvtsi128_si32(cnt128); 
} 

Однако более эффективный способ реализации popcnt128 является использование инструкции аппаратного POPCNT (на процессорах, которые поддерживают его):

static inline int popcnt128(__m128i n) { 
    const __m128i n_hi = _mm_unpackhi_epi64(n, n); 
    #ifdef _MSC_VER 
     return __popcnt64(_mm_cvtsi128_si64(n)) + __popcnt64(_mm_cvtsi128_si64(n_hi)); 
    #else 
     return __popcntq(_mm_cvtsi128_si64(n)) + __popcntq(_mm_cvtsi128_si64(n_hi)); 
    #endif 
} 

Answer 2

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

C предоставляет несколько хороших побитовых операций.

Вот код, чтобы подсчитать количество бит в целом числе:

countBitsSet(int toCount) 
{ 
    int numBitsSet = 0; 
    while(toCount != 0) 
    { 
     count += toCount % 2; 
     toCount = toCount >> 1; 
    } 
    return numBitsSet; 
} 

Объяснение:

toCount % 2 

Возвращает последний бит в нашем целом. (Разделив на две части и проверим остаток). Мы добавляем это в наш общий счет, а затем сдвигаем бит нашего значения toCount на единицу. Эта операция должна быть продолжена до тех пор, пока не будет больше бит, установленного в toCount (когда toCount равно 0)

Чтобы подсчитать количество бит в определенном байте, вы захотите использовать маску. Вот пример:

countBitsInByte(int toCount, int byteNumber) 
{ 
    int mask = 0x000F << byteNumber * 8 
    return countBitsSet(toCount & mask) 
} 

Допустим, что в нашей системе, мы считаем байт 0 младший байт в небольшой системе с обратным порядком байтов. Мы хотим создать новый toCount, чтобы перейти к нашей более ранней функции countBitsSet, замаскировав биты, которые установлены в 0. Мы делаем это, переставляя байт, полный единиц (обозначенных буквой F), на нужную позицию (byteNumber * 8 для 8 бит в байте) и выполнения побитовой операции И с нашей переменной toCount.

Answer 3

Как сказал в первом комментарии, GCC 3.4+ предлагает легкий доступ к (надеюсь оптимальный) встроенный через

int __builtin_popcount (unsigned int x) /* Returns the number of 1-bits in x. */ 

Как указано здесь: http://gcc.gnu.org/onlinedocs/gcc-3.4.3/gcc/Other-Builtins.html#Other%20Builtins

ли точно не ответить на вопрос, для 128бит, но дать хороший ответ на вопрос, который я имел, когда я л здесь :) операция AND

Answer 4

Вот версия базы на Bit Twiddling Hacks - Counting Set Bits in Parallel с именования похож на другие встроенные функции, а также некоторые дополнительные функции для 16 32 и 64-битных векторов

#include "immintrin.h" 

/* bit masks: 0x55 = 01010101, 0x33 = 00110011, 0x0f = 00001111 */ 
static const __m128i m1 = {0x5555555555555555ULL,0x5555555555555555ULL}; 
static const __m128i m2 = {0x3333333333333333ULL,0x3333333333333333ULL}; 
static const __m128i m3 = {0x0f0f0f0f0f0f0f0fULL,0x0f0f0f0f0f0f0f0fULL}; 
static const __m128i m4 = {0x001f001f001f001fULL,0x001f001f001f001fULL}; 
static const __m128i m5 = {0x0000003f0000003fULL,0x0000003f0000003fULL}; 

__m128i _mm_popcnt_epi8(__m128i x) { 
    /* Note: if we returned x here it would be like _mm_popcnt_epi1(x) */ 
    __m128i y; 
    /* add even and odd bits*/ 
    y = _mm_srli_epi64(x,1); //put even bits in odd place 
    y = _mm_and_si128(y,m1); //mask out the even bits (0x55) 
    x = _mm_subs_epu8(x,y); //shortcut to mask even bits and add 
    /* if we just returned x here it would be like _mm_popcnt_epi2(x) */ 
    /* now add the half nibbles */ 
    y = _mm_srli_epi64 (x,2); //move half nibbles in place to add 
    y = _mm_and_si128(y,m2); //mask off the extra half nibbles (0x0f) 
    x = _mm_and_si128(x,m2); //ditto 
    x = _mm_adds_epu8(x,y); //totals are a maximum of 5 bits (0x1f) 
    /* if we just returned x here it would be like _mm_popcnt_epi4(x) */ 
    /* now add the nibbles */ 
    y = _mm_srli_epi64(x,4); //move nibbles in place to add 
    x = _mm_adds_epu8(x,y); //totals are a maximum of 6 bits (0x3f) 
    x = _mm_and_si128(x,m3); //mask off the extra bits 
    return x; 
} 

__m128i _mm_popcnt_epi16(__m128i x) { 
    __m128i y; 
    x = _mm_popcnt_epi8(x); //get byte popcount 
    y = _mm_srli_si128(x,1); //copy even bytes for adding 
    x = _mm_add_epi16(x,y); //add even bytes into the odd bytes 
    return _mm_and_si128(x,m4);//mask off the even byte and return 
} 

__m128i _mm_popcnt_epi32(__m128i x) { 
    __m128i y; 
    x = _mm_popcnt_epi16(x); //get word popcount 
    y = _mm_srli_si128(x,2); //copy even words for adding 
    x = _mm_add_epi32(x,y); //add even words into odd words 
    return _mm_and_si128(x,m5);//mask off the even words and return 
} 

__m128i _mm_popcnt_epi64(__m128i x){ 
    /* _mm_sad_epu8() is weird 
     It takes the absolute difference of bytes between 2 __m128i 
     then horizontal adds the lower and upper 8 differences 
     and stores the sums in the lower and upper 64 bits 
    */ 
    return _mm_sad_epu8(_mm_popcnt_epi8(x),(__m128i){0}); 
} 

int _mm_popcnt_si128(__m128i x){ 
    x = _mm_popcnt_epi64(x); 
    __m128i y = _mm_srli_si128(x,8); 
    return _mm_add_epi64(x,y)[0]; 
    //alternative: __builtin_popcntll(x[0])+__builtin_popcntll(x[1]); 
}