Zählung Null b-Bit-Untersequenzen in einem Byte-Array

Question

I auf den schnellsten Weg suchen, die Anzahl der b -Bit Subsequenzen des Zählens (nicht überlappend), die Null in einer uint8_t Array von beliebiger Größe S sind (S ist normalerweise jedoch klein).

Constraints:

• b ist immer eine Potenz von zwei ist, sind die gültigen Werte tatsächlich nur: 1, 2, 4, 8, 16 und 32
• es, dass die Anzahl von Bits angenommen wird, in einem uint8_t ist 8 und die S * 8 teilbar durch b

Beispiele:

• b = 4, array = 0xA0 0x39 0x04 0x30 - richtige Antwort 3
• b = 1, array = 0xFF 0x1F 0xF8 - richtige Antwort 6
• b = 16, array = 0x05 0x16 0x32 0x00 - richtige Antwort ist 0

Was ich gerade mache ist, dass ich die Bits in Bytes "entpacke" und dann die Untersequenzen mit einem Nullpuffer memcmp, aber es scheint mir, dass es einen schnelleren Weg dafür geben sollte.

Answer 1

Sie können Bit-Twiddling ähnlich der bekannten Methode zum Erkennen eines Nullbytes in einer Zeichenfolge verwenden. Zum Beispiel für b = 4, Sie x ein 32-Bit-Wort lesen und

__builtin_popcount((x - 0x11111111) & (~x & 0x88888888)) 

Hier tun, erzeugt x - 0x11111111 einen Wert, bei dem die hohe Bit jeder 4-Bit-Gruppe 1 ist, wenn die 4-Bit-Gruppe ist Null oder es war bereits eingestellt; Der zweite Teil verwirft die bereits gesetzten Teile und zählt dann die verbleibenden Bits.

Answer 2

Für die zusätzliche Einschränkung von nur Sequenzen unter Berücksichtigung bei b Bit Start-Offsets eine sehr einfache Lösung gibt es (auch hier kein Problem endianness, da Sie nur ganze Stücke von Nullen bedenkt):

size_t countZeroChunks(const uint8_t* bytes, size_t nbytes, uint8_t b) { 
    assert(b == 2 || b == 4 || b == 8 || b == 16 || b == 32); 
    size_t count = 0; 
    if(b <= 8) { 
     // chunks fit inside a byte 
     for(size_t i = 0; i < nbytes; ++i) { 
      uint8_t byte = *bytes++; 
      for(uint8_t offset = 0; offset < 8; offset += b) { 
       // collect bits in chunk 
       // e.g. for b=2 at offset=2 
       // yyyyxxyy >> 2 -> 00yyyyxx 
       // 00yyyyxx << 6 -> xx000000 
       uint8_t chunk = (byte >> offset) << ((8 - offset) % 8); 
       if(chunk == 0) 
        ++count; 
      } 
     } 
    } else { 
     // chunks span multiple bytes 
     size_t nchunks = nbytes * 8/b; 
     for(size_t i = 0; i < nchunks; ++i) { 
      // collect chunk from bytes 
      uint32_t chunk = 0; 
      for(size_t k = 0, bytesPerChunk = b/8; k < bytesPerChunk; ++k) 
       chunk |= (uint32_t)(*bytes++) << (k * 8); 
      if(chunk == 0) 
       ++count; 
     } 
    } 
    return count; 
}