Conteggio veloce del numero di bit impostati nel registro __m128i

Question

Dovrei contare il numero di bit impostati di un registro __m128i. In particolare, dovrei scrivere due funzioni che sono in grado di contare il numero di bit del registro, usando i seguenti modi.

1. Il numero totale di bit impostati del registro.
2. Il numero di bit impostati per ciascun byte del registro.

Esistono funzioni intrinseche che possono eseguire, in tutto o in parte, le suddette operazioni?

Answer 1

Ecco alcuni codici utilizzati in un vecchio progetto (there is a research paper about it). La funzione popcnt8 di seguito calcola il numero di bit impostato in ciascun byte.

versione SSE2-only (basata su algoritmo 3 in 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; 
} 

versione SSSE3 (a causa di 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); 
} 

versione XOP (equivalente a SSSE3, ma utilizza istruzioni XOP che sono più veloci su 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); 
} 

Funct ion popcnt64 sotto conta il numero di bit nelle parti basse ed alte 64 bit del SSE registro: versione

SSE2:

versione

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

Infine, la funzione popcnt128 sotto contare il numero di bit per intero registro 128 bit:

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

Tuttavia, un modo più efficace per attuare popcnt128 è di usare istruzioni hardware POPCNT (su processori che supporta):

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

Modifica: Credo di non aver capito cosa stava cercando l'OP, ma sto mantenendo la mia risposta nel caso in cui sia utile a qualcun altro inciampare in questo.

C fornisce alcune operazioni bit a bit piacevoli.

Ecco il codice per contare il numero di bit impostati in un numero intero:

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

Spiegazione:

toCount % 2 

Restituisce l'ultimo bit nel nostro intero. (Dividendo per due e controllando il resto). Aggiungiamo questo al nostro conteggio totale e quindi spostiamo i bit del nostro valore toCount di uno. Questa operazione deve essere continuata finché non ci sono più bit impostati in toCount (quando toCount è uguale a 0)

Per contare il numero di bit in un byte specifico, si desidera utilizzare una maschera. Ecco un esempio:

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

Diciamo che nel nostro sistema, consideriamo byte 0 il byte meno significativo in un sistema endian poco. Vogliamo creare un nuovo toCount per passare alla precedente funzione countBitsSet nascondendo i bit impostati su 0. Lo facciamo spostando un byte pieno di uno (indicato dalla lettera F) nella posizione desiderata (byteNumber * 8 per 8 bit in un byte) ed eseguendo un'operazione AND bit a bit con la nostra variabile toCount.

Answer 3

Come detto nel primo commento, 3.4+ gcc offre un facile accesso a una (si spera ottimale) built-in via

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

come indicato qui: http://gcc.gnu.org/onlinedocs/gcc-3.4.3/gcc/Other-Builtins.html#Other%20Builtins

non esattamente rispondere alla domanda per 128bits, ma dare una bella risposta alla domanda che ho avuto quando sono atterrato qui :)

Answer 4

Ecco una versione base su Bit Twiddling Hacks - Counting Set Bits in Parallel con denominazione simile ad altre funzioni intrinseche, nonché alcune funzioni extra per 16 32 e 64 vettori di bit

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