¿Alguna forma más inteligente de extraer de un conjunto de bits?

Question

Tengo áreas de memoria que podrían considerarse "conjunto de bits". Son equivalentes a

unsigned char arr[256]; 

, pero sería mejor como

bit arr[2048]; 

estoy acceder a trozos separados de ella con

#define GETBIT(x,in) ((in)[ ((x)/8) ] & 1<<(7-((x)%8))) 

pero lo hago mucho en muchos lugares del código, a menudo en secciones de rendimiento crítico y me pregunto si hay algún método más inteligente y más óptimo para hacerlo.

información adicional: Arquitectura: ARM9 (32 bit); gcc/Linux. La representación de datos físicos no puede modificarse: se proporciona o se asigna de forma externa para uso externo.

Answer 1

Para acceder aleatoriamente a bits individuales, la macro que ha sugerido es tan buena como la que obtendrá (siempre que active las optimizaciones en su compilador).

Si hay algún patrón en los bits a los que está accediendo, entonces es posible que pueda hacerlo mejor. Por ejemplo, si accede con frecuencia a pares de bits, puede ver algunas mejoras al proporcionar un método para obtener dos bits en lugar de uno, incluso si no siempre termina utilizando ambos bits.

Al igual que con cualquier problema de optimización, deberá familiarizarse con el comportamiento de su código, en particular sus patrones de acceso en su matriz de bits, para lograr una mejora significativa en el rendimiento.

Actualización: Dado que accede a rangos de bits, probablemente pueda obtener más rendimiento de sus macros. Por ejemplo, si necesita acceder a cuatro bits es posible que tenga macros como este:

#define GETBITS_0_4(x,in) (((in)[(x)/8] & 0x0f)) 
#define GETBITS_1_4(x,in) (((in)[(x)/8] & 0x1e) >> 1) 
#define GETBITS_2_4(x,in) (((in)[(x)/8] & 0x3c) >> 2) 
#define GETBITS_3_4(x,in) (((in)[(x)/8] & 0x78) >> 3) 
#define GETBITS_4_4(x,in) (((in)[(x)/8] & 0xf0) >> 4) 
#define GETBITS_5_4(x,in) ((((in)[(x)/8] & 0xe0) >> 5) | (((in)[(x)/8+1] & 0x01)) << 3) 
#define GETBITS_6_4(x,in) ((((in)[(x)/8] & 0xc0) >> 6) | (((in)[(x)/8+1] & 0x03)) << 2) 
#define GETBITS_7_4(x,in) ((((in)[(x)/8] & 0x80) >> 7) | (((in)[(x)/8+1] & 0x07)) << 1) 
// ...etc 

Estas macros se recortar cuatro bits de cada posición de bit 0, 1, 2, etc. (Para reducir la proliferación de paréntesis, sin sentido, es posible que desee utilizar las funciones en línea de los anteriores) Entonces, tal vez definir una función en línea como:.

inline int GETBITS_4(int x, unsigned char *in) { 
    switch (x % 8) { 
     case 0: return GETBITS_0_4(x,in); 
     case 1: return GETBITS_1_4(x,in); 
     case 2: return GETBITS_2_4(x,in); 
     // ...etc 
    } 
} 

como se trata de una gran cantidad de código repetitivo tedioso, especialmente si usted tiene múltiples anchuras diferentes , es posible que desee escribir un programa para generar todas las funciones de acceso GETBIT_*.

(Noto que los bits en los bytes se almacenan en el orden inverso de lo que he escrito anteriormente. Aplicar una transformación adecuada para que coincida con su estructura si es necesario.)

Answer 2

Si invierte el orden de los bits en 'arr', entonces puede eliminar la sustracción de la macro. Es lo mejor que puedo decir, sin conocimiento del contexto del problema (cómo se usan los bits).

Answer 3

¿Por qué no crear su propia clase de contenedor?

Puede agregar bits a la "matriz" utilizando un operador como + y recuperar los bits individuales con el operador [].

Su macro podría mejorarse usando & 7 en vez de% 8 pero es probable que el compilador haga esa optimización para usted de todos modos.

Recientemente hice exactamente lo que está haciendo y mi transmisión podría constar de cualquier cantidad de bits.

así que tengo algo como lo siguiente:

BitStream<1> oneBitBitStream; 
BitStream<2> twoBitBitStream; 

oneBitBitStream += Bit_One; 
oneBitBitStream += Bit_Zero; 

twoBitBitStream += Bit_Three; 
twoBitBitStream += Bit_One; 

y así sucesivamente. Es un buen código legible y puedes proporcionarle una interfaz similar a STL para ayudar a la similitud :)

Answer 4

No lo creo. De hecho, muchas arquitecturas de CPU no accederán a los bits de forma individual.

En C++ tiene std::bitset<N>. pero puede no tener el más alto rendimiento según la implementación y optimización de su compilador.

Por cierto, puede ser mejor para agrupar los bits de matriz como uint32_t[32] (o uint64_t[16]) para desreferenciar Alineados (que bitset lo hace por usted ya).

Answer 5

Dado que se etiqueta la pregunta con C++, ¿hay alguna razón por la que no pueda simplemente usar el estándar bitset?

Answer 6

#define GETBIT(x,in) ((in)[ ((x)/8) ] & 1<<(7-((x)%8))) 

se puede optimizar.

1) Use el estándar int que normalmente es el tipo de datos entero de acceso más rápido. Si no necesita ser portátil, puede averiguar el tamaño de una int con sizeof y adaptar el siguiente código.

2)

#define GETBIT(x,in) ((in)[ ((x) >>> 3) ] & 1<<((x) & 7)) 

El operador mod% es más lento que ANDing. Y no necesita restar, simplemente ajuste su rutina SETBIT.

Answer 7

Tomando solución de Greg como base:

template<unsigned int n, unsigned int m> 
inline unsigned long getbits(unsigned long[] bits) { 
    const unsigned bitsPerLong = sizeof(unsigned long) * CHAR_BIT 
    const unsigned int bitsToGet = m - n; 
    BOOST_STATIC_ASSERT(bitsToGet < bitsPerLong); 
    const unsigned mask = (1UL << bitsToGet) - 1; 
    const size_t index0 = n/bitsPerLong; 
    const size_t index1 = m/bitsPerLong; 
    // Do the bits to extract straddle a boundary? 
    if (index0 == index1) { 
    return (bits[index0] >> (n % bitsPerLong)) & mask; 
    } else { 
    return ((bits[index0] >> (n % bitsPerLong)) + (bits[index1] << (bitsPerLong - (m % bitsPerLong)))) & mask; 
    } 
} 

puede obtener al menos 32 bits, incluso si no están alineados. Tenga en cuenta que es intencionalmente inline ya que no desea tener toneladas de estas funciones.

Answer 8

En lugar de la matriz de caracteres unsigned y las macros personalizadas, puede usar std::vector<bool>. La plantilla de clase vectorial tiene una especialización especial de plantilla para el tipo bool. Esta especialización se proporciona para optimizar la asignación de espacio: en esta especialización de plantilla, cada elemento ocupa solo un bit (que es ocho veces menor que el tipo más pequeño en C++: char).