Conteo rápido del número de bits establecidos en el registro __m128i

9 minutos de lectura

avatar de usuario
enzom83

Debo contar el número de bits establecidos de un registro __m128i. En particular, debo escribir dos funciones que puedan contar el número de bits del registro, utilizando las siguientes formas.

  1. El número total de bits establecidos del registro.
  2. El número de bits establecidos para cada byte del registro.

¿Existen funciones intrínsecas que puedan realizar, total o parcialmente, las operaciones anteriores?

  • Las CPU recientes tienen un POPCNT instrucción (recuento de población); GCC lo expone a través de la __builtin_popcount incorporado.

    – KerrekSB

    27 de junio de 2013 a las 23:42

  • Ver graphics.stanford.edu/~seander/bithacks.html por esto y mucho más.

    –Jim Balter

    27 de junio de 2013 a las 23:44

  • MS también tiene funciones popcount… ver stackoverflow.com/questions/11114017/… … Tenga en cuenta que estos no son necesariamente más rápidos que los bithacks; y si cuenta bits en matrices, algunas de las funciones de bithack son algo más rápidas.

    –Jim Balter

    27/06/2013 a las 23:50

avatar de usuario
marat dukhan

Aquí hay algunos códigos que usé en un proyecto anterior (hay un trabajo de investigacion al respecto). La función popcnt8 a continuación calcula el número de bits establecidos en cada byte.

Versión solo SSE2 (basada en el Algoritmo 3 en Libro El placer del hacker):

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

Versión SSSE3 (debido a 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);
}

Versión XOP (equivalente a SSSE3, pero usa instrucciones XOP que son más rápidas en 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);
}

Función popcnt64 a continuación cuenta el número de bits en las partes alta y baja de 64 bits del registro SSE:

Versión SSE2:

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

Versión XOP:

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

Finalmente, la función popcnt128 a continuación cuente el número de bits en el registro completo de 128 bits:

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

Sin embargo, una forma más eficiente de implementar popcnt128 es usar la instrucción POPCNT de hardware (en los procesadores que lo admiten):

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
}

  • Parece que usted es uno de los coautores del trabajo de investigación mencionado 🙂 Buen resumen también para el equipo de cortar y pegar. Sus soluciones están actualizadas. Los trucos de Hakem ya no están actualizados. ¡Felicitaciones, amigo!

    – Nils Pipenbrinck

    5 de julio de 2013 a las 20:57

  • Oh que mal. Publicaste tu artículo en la ACM, así que lamentablemente no puedo leerlo sin pagar $15 🙁

    – Nils Pipenbrinck

    5 de julio de 2013 a las 21:02

  • @NilsPipenbrinck, el documento está disponible gratuitamente en el sitio web de la conferencia: conferences.computer.org/sc/2012/papers/1000a033.pdf

    – Marat Dukhan

    26 de julio de 2013 a las 3:28


  • Aparentemente, su versión SSE2 suele ser más rápida que su versión SSSE3. No importa que SSSE3 tenga menos instrucciones. Aquí hay un punto de referencia: github.com/Const-me/LookupTables

    – Pronto

    28/10/2016 a las 23:05

  • @Soonts Podría ser, pero los resultados del compilador de Microsoft por sí solos no son convincentes.

    – Marat Dukhan

    31/10/2016 a las 21:36

Aquí hay una versión basada en Bit Twiddler Hacks – Contando Set Bits en Paralelo con nombres similares a otras funciones intrínsecas, así como algunas funciones adicionales para vectores de 16, 32 y 64 bits

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

  • ¿Por qué necesitas saturar adds en lugar de regular add para los pasos después del primero? (Aunque según las tablas de instrucciones de Agner Fog, paddusb tiene el mismo rendimiento que paddb en todo, por lo que no hay motivo de rendimiento para evitar saturar el complemento. Es simplemente sorprendente.)

    – Peter Cordes

    2 de febrero de 2018 a las 2:25

Como se dijo en el primer comentario, gcc 3.4+ ofrece un fácil acceso a un (con suerte óptimo) incorporado a través de

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

Como se indica aquí:
http://gcc.gnu.org/onlinedocs/gcc-3.4.3/gcc/Other-Builtins.html#Other%20Builtins

No responde exactamente a la pregunta de 128 bits, pero da una buena respuesta a la pregunta que tenía cuando llegué aquí 🙂

avatar de usuario
tommy perfecto

Editar: Supongo que no entendí lo que estaba buscando el OP, pero mantengo mi respuesta en caso de que sea útil para cualquier otra persona que se encuentre con esto.

C proporciona algunas buenas operaciones bit a bit.

Aquí hay un código para contar el número de bits establecidos en un número entero:

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

Explicación:

toCount % 2

Devuelve el último bit de nuestro entero. (Dividiendo por dos y comprobando el resto). Agregamos esto a nuestro conteo total y luego cambiamos los bits de nuestro valor toCount en uno. Esta operación debe continuar hasta que no haya más bits configurados en toCount (cuando toCount es igual a 0)

Para contar la cantidad de bits en un byte específico, querrá usar una máscara. Aquí hay un ejemplo:

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

Digamos que en nuestro sistema, consideramos el byte 0 como el byte menos significativo en un sistema little endian. Queremos crear un nuevo toCount para pasar a nuestra función anterior countBitsSet enmascarando los bits que están establecidos en 0. Hacemos esto cambiando un byte lleno de unos (indicado por la letra F) a la posición que queremos (byteNumber * 8 para 8 bits en un byte) y realizando una operación AND bit a bit con nuestra variable toCount.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad