Szybki kod do wyszukiwania bitowych tablic dla ciągłych bitów set/clear?

Question

Czy jest jakiś rozsądny szybki kod, który może mi pomóc szybko przeszukać dużą bitmapę (kilka megabajtów) dla przebiegów przyległych zera lub jednego bitu?

Przez "rozsądnie szybki" rozumiem coś, co może wykorzystać rozmiar słowa maszynowego i porównać całe słowa na raz, zamiast robić analizę bit-by-bit, która jest przerażająco powolna (tak jak ma to miejsce z vector<bool>).

Jest to bardzo przydatne dla np. przeszukiwanie mapy bitowej woluminu dla wolnego miejsca (do defragmentacji itp.).

Answer 1

System Windows ma strukturę danych RTL_BITMAP, której można używać wraz z jej interfejsami API.

Ale potrzebny kod do tego jakiś czas temu, a więc napisałem go tutaj (uwaga, to trochę brzydki):
https://gist.github.com/3206128

mam tylko częściowo go testowane, więc może jeszcze błędy (zwłaszcza na reverse). Ale ostatnia wersja (tylko trochę inna od tej) wydawała mi się użyteczna, więc warto spróbować.

Fundamentalna praca na cały rzeczą jest możliwość - szybko - znajdź długość przebiegu bitów:

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

Wszystko inne powinno być łatwe do zbudowania na tym, ze względu na jego uniwersalność.

Próbowałem dołączyć kod SSE, ale nie poprawił on znacząco wydajności. Jednak generalnie kod jest wielokrotnie szybszy niż analiza bit-by-bit, więc myślę, że może się przydać.

Powinno być łatwo przetestować, czy można jakoś uchwycić bufor vector<bool> - a jeśli korzystasz z Visual C++, to jest funkcja, którą zawarłem, która robi to za ciebie. Jeśli znajdziesz błędy, daj mi znać.

Answer 2

Nie mogę sobie wyobrazić, jak dobrze radzić sobie bezpośrednio ze słowami pamięci, więc stworzyłem szybkie rozwiązanie, które działa na bajtach; dla wygody opiszmy algorytm zliczania sąsiadujących:

Skonstruuj dwie tabele o rozmiarze 256, w których będziesz pisać dla każdej liczby od 0 do 255, liczbę końcowych 1 na początku i na końcu bajtu. Na przykład dla liczby 167 (10100111 w systemie binarnym), umieść 1 w pierwszej tabeli i 3 w drugiej tabeli. Nazwijmy pierwszą tabelę BBeg i drugą tabelę BEnd. Następnie, dla każdego bajtu b, dwie sprawy: jeśli jest 255, dodaj 8 do aktualnej sumy bieżącego, ciągłego zbioru tych i jesteś w regionie jednego. W przeciwnym razie kończysz region z BBeg [b] bitami i zaczynasz nowy z BEnd [b] bitami. W zależności od tego, jakie informacje chcesz, możesz dostosować ten algorytm (to jest powód, dla którego nie umieszczam tutaj żadnego kodu, nie wiem, jakiego wyniku chcesz).

Wada jest to, że nie liczy (mały) zwarty zbiór tych wewnątrz jednego bajta ...

Oprócz tego algorytmu, przyjaciel powiedział mi, że jeśli to jest do kompresji dysku, wystarczy spojrzeć na różnych bajtów od 0 (pusty obszar dysku) i 255 (pełny obszar dysku). Szybka heurystyka tworzy mapę bloków, które trzeba kompresować. Może to wykracza poza zakres tego tematu ...

Answer 3

Brzmi to może być przydatne:

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

Nie mów, jeśli chciał zrobić jakąś RLE lub po prostu liczyć na bajtów zer i jeden bitów (jak 0b1001 powinien powrócić 1x1 2x0 1x1).

Tablica przeglądowa plus algorytm SWAR do szybkiego sprawdzania może łatwo dostarczyć te informacje. Trochę tak:

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 

LUT muszą być skonstruowane w zależności od zamierzonego algorytmu. Jeśli chcesz policzyć liczbę sąsiednich 0 i 1 w słowie, zbudujesz to tak:

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.