Codice veloce per la ricerca di array di bit per set contigui/chiari bit?

Question

Esiste un codice ragionevolmente veloce che può aiutarmi a cercare rapidamente una bitmap di grandi dimensioni (alcuni megabyte) per le esecuzioni di zero contigui o di un bit?

Con "ragionevolmente veloce" intendo qualcosa che può sfruttare la dimensione della parola della macchina e confrontare intere parole contemporaneamente, invece di fare analisi bit per bit che è orribilmente lenta (come si fa con vector<bool>).

È molto utile per es. ricerca nella bitmap di un volume per lo spazio libero (per la deframmentazione, ecc.).

Answer 1

Windows ha una struttura dati RTL_BITMAP che è possibile utilizzare insieme alle relative API.

Ma avevo bisogno il codice per questo qualche tempo fa, e così l'ho scritto qui (attenzione, è un po 'brutto):
https://gist.github.com/3206128

ho solo parzialmente provato, quindi potrebbe ancora avere bug (specialmente su reverse). Ma una versione recente (solo leggermente diversa da questa) sembrava essere utilizzabile per me, quindi vale la pena provare.

L'operazione fondamentale per l'intera cosa è essere in grado di - rapidamente - trovare la lunghezza di una corsa di bit:

long long GetRunLength(
    const void *const pBitmap, unsigned long long nBitmapBits, 
    long long startInclusive, long long endExclusive, 
    const bool reverse, /*out*/ bool *pBit); 

Tutto il resto dovrebbe essere facile da costruire su questo, data la sua versatilità.

Ho cercato di includere del codice SSE, ma non ha migliorato sensibilmente le prestazioni. Tuttavia, in generale, il codice è molte volte più veloce dell'analisi bit-by-bit, quindi penso che potrebbe essere utile.

Dovrebbe essere facile verificare se è possibile ottenere il buffer vector<bool> in qualche modo - e se si è su Visual C++, quindi c'è una funzione che ho incluso che fa questo per voi. Se trovi bug, sentiti libero di farmelo sapere.

Answer 2

Non riesco a capire come fare bene direttamente sulle parole di memoria, quindi ho inventato una soluzione rapida che sta lavorando su byte; per comodità, analizziamo l'algoritmo per il conteggio di quelli contigui:

Costruisci due tabelle di dimensione 256 in cui scriverai per ogni numero compreso tra 0 e 255, il numero di titoli finali 1 all'inizio e alla fine del byte. Ad esempio, per il numero 167 (10100111 in binario), inserire 1 nella prima tabella e 3 nella seconda tabella. Chiamiamo il primo tavolo BBeg e il secondo tavolo BEnd. Quindi, per ogni byte b, due casi: se è 255, aggiungi 8 alla tua attuale somma del tuo attuale insieme contiguo, e sei in una regione di uno. Altrimenti, si termina una regione con bit BBeg [b] e ne inizia una nuova con BEnd [b] bit. A seconda delle informazioni che si desidera, è possibile adattare questo algoritmo (questo è un motivo per cui non inserisco qui alcun codice, non so quale output si desidera).

Un difetto è che non conta (piccolo) insieme contiguo di quelli all'interno di un byte ...

Accanto a questo algoritmo, un amico mi dice che, se è per la compressione del disco, basta guardare per i byte differenti da 0 (area disco vuota) e 255 (area disco intera). È un'euristica rapida per creare una mappa dei blocchi che devi comprimere. Forse è oltre lo scopo di questo argomento ...

Answer 3

Suona come questo potrebbe essere utile:

http://www.aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count%29 e http://www.aggregate.org/MAGIC/#Leading%20Zero%20Count

Non si dice se si voleva fare una sorta di RLE o per contare semplicemente in-byte di zeri e uno bit (come 0b1001 dovrebbe restituire 1x1 2x0 1x1).

Una tabella di ricerca più algoritmo SWAR per il controllo rapido potrebbe fornire facilmente tali informazioni. Un po 'come questo:

byte lut[0x10000] = { /* see below */ }; 
for (uint * word = words; word < words + bitmapSize; word++) { 
    if (word == 0 || word == (uint)-1) // Fast bailout 
    { 
     // Do what you want if all 0 or all 1 
    } 
    byte hiVal = lut[*word >> 16], loVal = lut[*word & 0xFFFF]; 
    // Do what you want with hiVal and loVal 

La LUT dovrà essere costruito a seconda del vostro algoritmo previsto. Se si desidera contare il numero di contigui 0 e 1 nella parola, si costruito in questo modo:

for (int i = 0; i < sizeof(lut); i++) 
    lut[i] = countContiguousZero(i); // Or countContiguousOne(i) 
    // The implementation of countContiguousZero can be slow, you don't care 
    // The result of the function should return the largest number of contiguous zero (0 to 15, using the 4 low bits of the byte, and might return the position of the run in the 4 high bits of the byte 
    // Since you've already dismissed word = 0, you don't need the 16 contiguous zero case.