Un modo più intelligente per estrarre dalla matrice di bit?

Question

Ho aree di memoria che possono essere considerate "array di bit". Essi sono equivalenti a

unsigned char arr[256]; 

ma sarebbe meglio pensato come

bit arr[2048]; 

sto accedendo bit separati da esso con

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

ma lo faccio molto in molti luoghi del codice, spesso in sezioni critiche per le prestazioni e mi chiedo se ci sono metodi più intelligenti e più ottimali per farlo.

informazioni extra: Architettura: ARM9 (32 bit); gcc/Linux. La rappresentazione fisica dei dati non può essere modificata - è fornita o mappata esternamente per uso esterno.

Answer 1

Per accedere in modo casuale a singoli bit, la macro che hai suggerito è buona come quella che otterrai (a patto di attivare le ottimizzazioni nel compilatore).

Se c'è qualche modello per i bit a cui si sta accedendo, allora si potrebbe essere in grado di fare meglio. Ad esempio, se accedi spesso alle coppie di bit, potresti notare dei miglioramenti fornendo un metodo per ottenere due bit invece di uno, anche se non sempre finisci con l'utilizzare entrambi i bit.

Come per qualsiasi problema di ottimizzazione, è necessario avere molta familiarità con il comportamento del codice, in particolare i suoi schemi di accesso nel proprio array di bit, per ottenere un miglioramento significativo delle prestazioni.

Aggiornamento: Poiché si accede a intervalli di bit, è possibile probabilmente ottenere un po 'più di prestazioni dai propri macro. Ad esempio, se è necessario accedere a quattro bit si potrebbe avere le macro come questo:

#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 

Queste macro avrebbero ritagliare quattro bit da ogni posizione di bit 0, 1, 2, ecc (Per ridurre la proliferazione di parentesi inutili, si potrebbe desiderare di utilizzare funzioni inline per quanto sopra) Allora, forse, definire una funzione inline, come:.

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

Poiché si tratta di un sacco di codice boilerplate noioso, soprattutto se hai più diverse larghezze , potresti voler scrivere un programma per generare tutte le funzioni di accesso GETBIT_*.

(ho notato che i bit nei vostri byte vengono memorizzati in ordine inverso da quello che ho scritto sopra. Applicare una trasformazione appropriata per abbinare la struttura se è necessario.)

Answer 2

Se si inverte l'ordine dei bit in "arr", è possibile eliminare la sottostringa dalla macro. È il meglio che posso dire, senza conoscere il contesto del problema (come vengono usati i bit).

Answer 3

Perché non creare la propria classe wrapper?

È quindi possibile aggiungere bit all'array utilizzando un operatore come + e recuperare i singoli bit utilizzando l'operatore [].

La tua macro potrebbe essere migliorata utilizzando & 7 anziché% 8 ma è probabile che il compilatore effettui tale ottimizzazione comunque.

Recentemente ho fatto esattamente quello che stai facendo e il mio stream potrebbe contenere un numero qualsiasi di bit.

Così ho qualcosa di simile al seguente:

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

oneBitBitStream += Bit_One; 
oneBitBitStream += Bit_Zero; 

twoBitBitStream += Bit_Three; 
twoBitBitStream += Bit_One; 

e così via. Rende il codice piacevole e leggibile ed è possibile fornire un'interfaccia simile a STL per facilitare la somiglianza :)

Answer 4

Non credo. In effetti, molte architetture di CPU non accedono ai bit singolarmente.

Su C++ si dispone di std::bitset<N>. ma potrebbe non avere le massime prestazioni a seconda dell'implementazione e dell'ottimizzazione del compilatore.

proposito, può essere meglio per il vostro gruppo di bit-array come uint32_t[32] (o uint64_t[16]) per dereferenziazione Allineati (che bitset fa questo per voi già).

Answer 5

Dal momento che la questione è aggiunto con C++, c'è qualche ragione per cui non puoi semplicemente usare lo standard bitset?

Answer 6

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

può essere ottimizzato.

1) Utilizzare standard int che è normalmente il tipo di dati intero più veloce accessibile. Se non è necessario essere portatili, è possibile scoprire le dimensioni di un interno con sizeof e adattare il seguente codice.

2)

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

L'operatore mod% è più lento di ANDing. E non è necessario sottrarre, semplicemente aggiusta la tua routine SETBIT.

Answer 7

Prendendo la soluzione di Greg come 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; 
    } 
} 

Può ottenere almeno 32 bit, anche se non sono allineati. Nota che è intenzionalmente inline come non vuoi avere tonnellate di queste funzioni.

Answer 8

Invece del char array non firmato e dei macro personalizzati, è possibile utilizzare std::vector<bool>. Il modello di classe vettoriale ha una specializzazione di modello speciale per il tipo di bool. Questa specializzazione viene fornita per ottimizzare l'allocazione dello spazio: in questa specializzazione del modello, ogni elemento occupa solo un bit (che è otto volte inferiore al tipo più piccolo in C++: char).