¿Cuál es la forma (s) más rápida de hacer un ciclo a través de una gran porción de datos por bit?

Question

Estoy ejecutando un bloque de memoria de datos binarios por byte.

Actualmente estoy haciendo algo como esto:

for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    ((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
    ((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
    ((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
    ((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
    ((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
    ((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
    ((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
    ((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}

Donde están las máscaras:

for (i = 0; i < 8; i++)
{
    Masks[i] = 1 << i;
}

(De alguna manera no logré hacerlo tan rápido en un bucle o en una función en línea, así que lo escribí).

¿Alguien tiene alguna sugerencia sobre cómo mejorar este primer ciclo? Soy bastante inexperto en bajar a bits.

Esto puede parecer una cosa estúpida de hacer. Pero estoy en el proceso de implementar un algoritmo de compresión. Solo quiero que el bit acceda a la parte inferior derecha.

¡Gracias!

PS: Esto está en el compilador de Visual Studio 2008. Por lo tanto, sería bueno si las sugerencias se aplicaran a ese compilador.

PPS: Me acabo de dar cuenta de que no necesito incrementar dos cuentas. Uno sería suficiente. Luego calcula la diferencia a los bits totales al final. Pero eso sería específico solo para contar. Lo que realmente quiero hacer rápido es la extracción de bits.

EDITAR: La idea de la tabla de búsqueda que se presentó es agradable. Sin embargo, me doy cuenta de que he planteado mal la pregunta en el título. Porque al final, lo que quiero hacer no es contar los bits, sino acceder a cada bit lo más rápido posible.

OTRA EDICIÓN: ¿Es posible avanzar un puntero solo un bit en los datos?

OTRA EDICIÓN: Gracias por todas sus respuestas hasta ahora.

Lo que quiero implementar en los próximos pasos es un codificador aritmético binario no sofisticado que no analiza el contexto. Así que solo estoy interesado en bits individuales por ahora. Eventualmente se convertirá en un BAC adaptable al contexto, pero lo dejaré para más adelante.

Procesar 4 bytes en lugar de 1 byte podría ser una opción. Pero un bucle de más de 32 bits también es costoso, ¿no?

Answer 1

No entendí realmente lo que intentas hacer. Pero si solo desea obtener acceso a los bits de un mapa de bits, puede usar estas funciones (sin probar!):

#include <stddef.h>

_Bool isbitset(unsigned char * bitmap, size_t idx)
{
    return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}

void setbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] |= (1 << (idx % 8));
}

void unsetbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] &= ~(1 << (idx % 8));
}

void togglebit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] ^= (1 << (idx % 8));
}

Editar: Ok, pienso Entiendo lo que quieres hacer: iteración rápida sobre una secuencia de bits. Por lo tanto, no queremos usar las funciones de acceso aleatorio de arriba, sino leer una palabra completa de datos a la vez.

Puede usar cualquier tipo de entero sin signo que desee, pero debe elegir uno que probablemente corresponda al tamaño de palabra de su arquitectura. Iré con uint_fast32_t desde stdint.h :

uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
    uint_fast32_t mask = 1;
    uint_fast32_t current = *data;
    for(; mask; mask <<= 1)
    {
        if(current & mask)
        {
            // bit is set
        }
        else
        {
            // bit is not set
        }
    }
}

Desde el bucle interno, puede establecer el bit con

*data |= mask;

anular el bit con

*data &= ~mask;

y alternar el bit con

*data ^= mask;

Advertencia: ¡El código podría comportarse inesperadamente en las arquitecturas de big-endian!

Answer 2

Probablemente, la forma más rápida es construir una tabla de búsqueda de valores de bytes frente al número de bits establecidos en ese byte. Al menos esa fue la respuesta cuando me entrevisté en Google.

Answer 3

Consulte el siguiente enlace para ver una docena de cosas relacionadas con los bits: Hacking Twiddling Hacks

Answer 4

Use una tabla que asigne cada valor de byte (256) al número de 1 en él. (El # de 0 es solo (8 - # de 1)). Luego itere sobre los bytes y realice una única búsqueda para cada byte, en lugar de múltiples búsquedas y comparaciones. Por ejemplo:

int onesCount = 0;
for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;

Answer 5

Podría usar una tabla de búsqueda precomputada, es decir:

static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */

...

for( ... ) 
   byte = ... 
   Stats.FreqOf1 += bitcount_lookup[byte];

Answer 6

Aquí hay un método de cómo contar los 1 bits de un entero de 32 bits (basado en el método Integer.bitCount (i) de Java):

unsigned bitCount(unsigned i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

Para que pueda convertir sus datos a int y avanzar en pasos de 4 bytes.

Answer 7

Aquí hay uno simple que preparé con un solo valor de 32 bits, pero se puede ver que no sería difícil adaptarlo a cualquier número de bits ...

int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
    if((x & 0x1) == 0x1) ones++;
    x = (x >> 1);
}

printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);

Sin embargo, tenga en cuenta que modifica el valor en el proceso. Si está haciendo esto con los datos que necesita conservar, primero debe hacer una copia.

Hacer esto en __asm ??probablemente sería una forma mejor, quizás más rápida, pero es difícil decir con qué facilidad puede optimizar el compilador ...

Con cada solución que considere, cada una tendrá inconvenientes. Una tabla de búsqueda o un modificador de bits (como el mío), ambos tienen inconvenientes.

Larry

Answer 8

ttobiass: tenga en cuenta que las funciones en línea son importantes en las aplicaciones de las que habla, pero hay cosas que debe tener en cuenta. Usted PUEDE obtener el rendimiento del código en línea, solo recuerde un par de cosas.

• en línea en el modo de depuración no existe. (A menos que lo fuerce)
• el compilador en línea funcionará como le parezca. A menudo, si le dices que incorpore una función, puede que no lo haga. Incluso si usas __forceinline. Consulte MSDN para obtener más información sobre la inscripción.
• Solo ciertas funciones pueden incluso estar en línea. Por ejemplo, no puede alinear una función recursiva.

Obtendrá su mejor rendimiento de la configuración de su proyecto para el lenguaje C / C ++ y de cómo construye su código. En este punto, es importante comprender las operaciones de pila frente a pila, convenciones de llamada, alineación de memoria, etc.

Sé que esto no responde exactamente a tu pregunta, pero mencionas el rendimiento y cómo obtener el mejor rendimiento, y estas son las claves.

Answer 9

Para unirse al vagón de enlaces: bits de conteo

Answer 10

Si este no es un caso de optimización prematura y realmente necesita exprimir hasta el último femtosegundo, entonces probablemente esté mejor con una matriz estática de 256 elementos que rellena una vez con la cuenta de bits de cada valor de byte , entonces

  

Stats.FreqOf1 + = bitCountTable [byte]

y cuando el bucle haya terminado:

  

Stats.FreqOf0 = ((data- > Count * 8) - Stats.FreqOf1)

Answer 11

Hay un capítulo entero sobre las diferentes técnicas para esto en el libro Beautiful Code . Puede leerlo (la mayoría de) en los libros de Google comenzando aquí .

Answer 12

Una forma más rápida de extraer bits es usar:

bitmask= data->Data[i];

while (bitmask)
{
    bit_set_as_power_of_two= bitmask & -bitmask;
    bitmask&= bitmask - 1;
}

Si solo quiere contar los bits establecidos, una LUT en caché sería rápida, pero también puede hacerlo en tiempo constante con el método de conteo de bits intercalados en el enlace en esta respuesta .