Szybkie zliczanie liczby bitów setu w rejestrze __m128i

Question

Powinienem policzyć liczbę bitów setu rejestru __m128i. W szczególności powinienem napisać dwie funkcje, które są w stanie policzyć liczbę bitów rejestru, korzystając z następujących sposobów.

1. Łączna liczba ustawionych bitów rejestru.
2. Liczba ustawionych bitów dla każdego bajtu rejestru.

Czy istnieją wewnętrzne funkcje, które mogą wykonywać, w całości lub w części, powyższe operacje?

Answer 1

Oto niektóre kody użyte w starym projekcie (there is a research paper about it). Poniższa funkcja popcnt8 oblicza liczbę bitów ustawionych w każdym bajcie.

wersja SSE2 tylko (w oparciu o algorytm 3 w 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; 
} 

wersja ssse3 (ze względu na 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); 
} 

wersja XOP (odpowiednik ssse3, ale używa instrukcji xop które są szybsze w buldożerach AMD)

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

Funkcja jon popcnt64 poniżej oblicza liczbę bitów w niskich i wysokich elementów 64-bitowych GSS zarejestrować: Wersja

SSE2:

wersji

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

Na koniec, funkcja popcnt128 poniżej policz liczbę bitów w całym 128-bitowym rejestrze:

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

Jednakże bardziej efektywny sposób realizować popcnt128 jest użycie instrukcji sprzętu POPCNT (procesory, która go obsługuje):

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

Edycja: Myślę, że nie rozumiałem, czego szukał OP, ale zachowuję moją odpowiedź na wypadek, gdyby była przydatna dla każdego, kto się o to potyka.

C dostarcza kilka ładnych operacji bitowych.

Oto kod policzyć liczbę bitów zawartych w integer:

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

Objaśnienie:

toCount % 2 

Zwraca ostatni bit w naszej całkowitej. (Dzieląc przez dwa i sprawdzając pozostałą część). Dodajemy to do naszej całkowitej liczby, a następnie przesuwamy bity naszej wartości toCount o jeden. Ta operacja powinna być kontynuowana do momentu, gdy nie zostanie ustawionych więcej bitów w toCount (gdy toCount jest równe 0).

Aby zliczyć liczbę bitów określonego bajtu, należy użyć maski. Oto przykład:

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

Powiedzmy, że w naszym systemie, uważamy bajt 0 bajt najmniej znaczący w małym systemie endian. Chcemy stworzyć nowy toCount, który przejdzie do naszej wcześniejszej funkcji countBitsSet poprzez zamaskowanie bitów, które są ustawione na 0. Robimy to przesuwając bajt pełen tych (oznaczonych literą F) do pozycji, którą chcemy (byteNumber * 8 dla 8 bitów w bajcie) i wykonanie bitowej operacji AND z naszą zmienną toCount.

Answer 3

Jak powiedział w pierwszym komentarzu, gcc 3.4+ oferuje łatwy dostęp do (miejmy nadzieję, że optymalna) wbudowany poprzez

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

Jak stwierdzono tutaj: http://gcc.gnu.org/onlinedocs/gcc-3.4.3/gcc/Other-Builtins.html#Other%20Builtins

nie dokładnie odpowiedzieć na pytanie 128bitowe, ale dają ładne odpowiedź na pytanie miałem kiedy wylądowałem tutaj :)

Answer 4

Oto bazowa wersja na Bit Twiddling Hacks - Counting Set Bits in Parallel z nazewnictwa podobna do innych swoistych funkcji, jak również kilka dodatkowych funkcji dla 16 32 i 64-bitowych wektorów

#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]); 
}