Counting zero b-bit subsequences in a byte array

Question

I am looking for the fastest way of counting the number of b-bit subsequences (non-overlapping) that are zero in an uint8_t array of arbitrary size S (S is usually small though).

Constraints:

• b is always a power of two, valid values are actually only: 1, 2, 4, 8, 16 and 32
• it is assumed that the number of bits in an uint8_t is 8 and that S * 8 is divisible by b

Examples:

• b = 4, array = 0xA0 0x39 0x04 0x30- correct answer is 3
• b = 1, array = 0xFF 0x1F 0xF8 - correct answer is 6
• b = 16, array = 0x05 0x16 0x32 0x00 - correct answer is 0

What i'm currently doing is I "unpack" the bits into bytes and then memcmp the subsequences with a zero buffer, but it seems to me there should be a faster way of doing this.

Answer 1

You can use bit-twiddling similar to the well-known method for detecting a null byte in a string. For example for b=4, you can read a 32-bit word x and do

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

Here, x - 0x11111111 produces a value where the high bit of each 4-bit group is 1 if the 4-bit group is zero or it was already set; the second part discards those where it was already set, and then you just count the bits remaining.

Answer 2

For the additional constraint of only considering sequences starting at b bit offsets there's a very simple solution (also endianness is not an issue here, since you're only considering whole chunks of zeroes):

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