Bitstream reader

Question

I have a program which reads and analyses MPEG-TS files. I've been using gperftools to identify hotspots and optimize them, and 45% of all samples at this point are in my main bitstream reader function.

I've already:

Reduced the number of overflow checks to one per call (not shown here, since the overflow check occurs before this function is called).
Optimized for byte-aligned reads.

Update: Based on answers here and some profiling, I also did..

Make one call to get us aligned, read as many aligned bytes as we can, and then do one more unaligned read to finish.
Split up read_bits function and skip complex logic for whole-byte reads.

See previous edits for original code.

static uint64_t bitreader_read_bytes_aligned_unchecked(bitreader_t* b, uint8_t bytes)
{
    uint64_t result = b->data[b->bytes_read];
    for (size_t i = 1; i < bytes; ++i) {
        result <<= 8;
        result += b->data[b->bytes_read + i];
    }
    b->bytes_read += bytes;
    return result;
}

static uint64_t bitreader_read_bits_unaligned_unchecked(bitreader_t* b, uint8_t bits)
{
    uint8_t result = b->data[b->bytes_read];
    result >>= 8 - bits - b->bits_read;
    result &= (1 << bits) - 1;
    bitreader_skip_bits_unchecked(b, bits);
    return result;
}

static uint64_t bitreader_read_bits_unchecked(bitreader_t* b, uint8_t bits)
{
    uint64_t result = 0;
    /* Try to turn this into an aligned read */
    if (b->bits_read && bits >= 8) {
        size_t to_read = 8 - b->bits_read;
        result = bitreader_read_bits_unaligned_unchecked(b, to_read);
        bits -= to_read;
    }

    /* Do aligned reads if we can */
    while (!b->bits_read && bits >= 8) {
        result <<= 8;
        result += b->data[b->bytes_read];
        ++b->bytes_read;
        bits -= 8;
    }

    /* Handle leftovers */
    while (bits > 0) {
        size_t to_read = MIN(bits, 8 - b->bits_read);
        result <<= to_read;
        result += bitreader_read_bits_unaligned_unchecked(b, to_read);
        bits -= to_read;
    }
    return result;
}

And here's a full program that demonstrates typical behavior in my application. gperftools confirms that it spends 99% of its time in bitreader_read_bits_unchecked().

#include <assert.h>
#include <inttypes.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN(a, b)  (((a) < (b)) ? (a) : (b))

typedef struct {
    const uint8_t* data;
    size_t len;
    size_t bytes_read;
    uint8_t bits_read;
} bitreader_t;

void bitreader_init(bitreader_t* b, const uint8_t* data, size_t len)
{
    b->data = data;
    b->len = len;
    b->bytes_read = 0;
    b->bits_read = 0;
}

void bitreader_skip_bits_unchecked(bitreader_t* b, size_t bits)
{
    size_t bits_read = b->bits_read + bits;
    b->bytes_read += bits_read / 8;
    b->bits_read = bits_read % 8;
}

uint8_t bitreader_read_bit_unchecked(bitreader_t* b)
{
    uint8_t result = b->data[b->bytes_read];
    result &= 128 >> b->bits_read;
    bitreader_skip_bits_unchecked(b, 1);
    return result;
}

static uint64_t bitreader_read_bytes_aligned_unchecked(bitreader_t* b, uint8_t bytes)
{
    uint64_t result = b->data[b->bytes_read];
    for (size_t i = 1; i < bytes; ++i) {
        result <<= 8;
        result += b->data[b->bytes_read + i];
    }
    b->bytes_read += bytes;
    return result;
}

static uint64_t bitreader_read_bits_unaligned_unchecked(bitreader_t* b, uint8_t bits)
{
    uint8_t result = b->data[b->bytes_read];
    result >>= 8 - bits - b->bits_read;
    result &= (1 << bits) - 1;
    bitreader_skip_bits_unchecked(b, bits);
    return result;
}

static uint64_t bitreader_read_bits_unchecked(bitreader_t* b, uint8_t bits)
{
    uint64_t result = 0;
    /* Try to turn this into an aligned read */
    if (b->bits_read && bits >= 8) {
        size_t to_read = 8 - b->bits_read;
        result = bitreader_read_bits_unaligned_unchecked(b, to_read);
        bits -= to_read;
    }

    /* Do aligned reads if we can */
    while (!b->bits_read && bits >= 8) {
        result <<= 8;
        result += b->data[b->bytes_read];
        ++b->bytes_read;
        bits -= 8;
    }

    /* Handle leftovers */
    while (bits > 0) {
        size_t to_read = MIN(bits, 8 - b->bits_read);
        result <<= to_read;
        result += bitreader_read_bits_unaligned_unchecked(b, to_read);
        bits -= to_read;
    }
    return result;
}

void usage(const char* name)
{
    printf("usage: %s [-v] [some file]\n", name);
}

int main(int argc, char** argv)
{
    int verbose = 0;
    const char* filename = NULL;
    size_t i;
    for (i = 1; i < (unsigned)argc; ++i) {
        if (!strcmp(argv[i], "-v")) {
            verbose = 1;
        } else if (filename) {
            usage(argv[0]);
            return 1;
        } else {
            filename = argv[i];
        }
    }
    if (filename == NULL) {
        usage(argv[0]);
        return 1;
    }

    FILE* f = fopen(argv[1], "rb");
    if (!f) {
        printf("Failed to open file %s\n", argv[1]);
        return 1;
    }

    fseek(f, 0, SEEK_END);
    long fsize = ftell(f);
    fseek(f, 0, SEEK_SET);

    uint8_t* fbytes = malloc(fsize);
    if (!fbytes) {
        printf("Failed to allocate %ld bytes when reading file %s\n",
            fsize, argv[1]);
        return 1;
    }
    fread(fbytes, fsize, 1, f);
    fclose(f);

    bitreader_t b;
    bitreader_init(&b, fbytes, fsize);
    printf("%zu\n", fsize);

    uint8_t NUM_BITS[] = {1, 1, 22, 19, 61, 24, 16, 16, 16, 32, 64};
    size_t NUM_BYTES_SUM = 0;
    for (i = 0; i < sizeof(NUM_BITS); ++i) {
        NUM_BYTES_SUM += NUM_BITS[i];
    }
    assert(NUM_BYTES_SUM % 8 == 0);
    NUM_BYTES_SUM = NUM_BYTES_SUM / 8;

    size_t loops = b.len / NUM_BYTES_SUM;
    size_t l;
    for (l = 0; l < loops; ++l) {
        for (i = 0; i < sizeof(NUM_BITS); ++i) {
            size_t num_bits = NUM_BITS[i];
            uint64_t bits;
            if (num_bits == 1) {
                bits = bitreader_read_bit_unchecked(&b);
            } else if (num_bits % 8 == 0) {
                bits = bitreader_read_bytes_aligned_unchecked(&b, num_bits / 8);
            } else {
                bits = bitreader_read_bits_unchecked(&b, num_bits);
            }
            if (verbose) {
                printf("Read %zu bits and got %"PRIu64"\n", num_bits, bits);
            }
        }
    }

    free(fbytes);
    return 0;
}

Compile with:

gcc -o bitreader bitreader.c -O3

Run with:

./bitreader /path/to/a/big/file

Well, as a micro optimization, you could try one of those branchless min functions: coranac.com/documents/bittrick — glampert, Apr 16 '15 at 18:43
In your actual program, do you seek around in the file? Or do you change the NUM_BITS array? Because if your program only does exactly what the sample program does, it might be possible to do it completely differently. — JS1, Apr 16 '15 at 20:23
@JS1 The NUM_BITS array is just an example of typical calls made to the bitreader. The actual usage is more like uint16_t table_id = bitreader_read_bits(b, 16); bool indicator = bitreader_read_bit(b);, etc. I never seek in the file though. There is one case where I rewind the bitreader, but I could do it differently (I read forward to find the end of NULL-terminated strings and then rewind). — Brendan Long, Apr 16 '15 at 21:20

Loki Astari · Answer 1 · 2015-04-16 21:01:38Z

up vote 3 down vote

I think you can optimize itreader_read_bits_unchecked() by unrolling the first and last loop. These two iterations are the only ones with special conditions about the number of bits being read. The main body of the loop will always read 8 bits per iteration. By doing this you remove a conditional branch from the loop allowing it to run optimally.

    uint64_t result = 0;

    // Pre-Loop
    // To make things lign up nicely before we enter the loop.
    size_t to_read = MIN(bits, 8 - b->bits_read);
    if (bits >= 8 && to_read != 8)
    {
        result <<= to_read;

        uint8_t byte = b->data[b->bytes_read];
        byte >>= 8 - to_read - b->bits_read;
        byte &= (1 << to_read) - 1;
        result += byte;

        b->bits_read = 0;
        b->bytes_read++;
        bits -= to_read;
    }

    // Everything aligns up to 8 bit boundaries so no need to test.
    // Loop can now run without branching.
    while (bits >= 8)
    {
        size_t to_read = 8;
        result <<= to_read;
        result += b->data[b->bytes_read];

        ++b->bytes_read;
        bits -= to_read;
    }

    // Post-Loop
    // If there is any remainder then read it and adjust.
    if (bits > 0)
    {
        size_t to_read = bits;
        result <<= to_read;
        uint8_t byte = b->data[b->bytes_read];
        byte >>= 8 - to_read - b->bits_read;
        byte &= (1 << to_read) - 1;
        result += byte;

        bitreader_skip_bits_unchecked()
    }

    return result;

edited Apr 16 '15 at 21:01

answered Apr 16 '15 at 20:07

Loki Astari

52k257169

I tried your code but it doesn't have the same behavior as the original. In particular, after reading 1 bit, b->bits_read should be 1 but with your code it is 0. – JS1 Apr 16 '15 at 20:34

@JS1: I did not test. But the principle remains sound. If you find the bug I will update the code appropriately. – Loki Astari Apr 16 '15 at 20:35

@JS1: If the bits to read is 1. It should not enter the first section (Pre-Loop). It should only enter the last section (Post-Loop). The first section (Pre-Loop) should read the number of bits required to reach an 8 bit boundry. Thus by definition at the end of this section b->bits_read = 0 – Loki Astari Apr 16 '15 at 20:38

@JS1: Thats my bug then. Hold on. – Loki Astari Apr 16 '15 at 20:40

@JS1: Fixed. Try that. – Loki Astari Apr 16 '15 at 20:42

| show 3 more comments

JS1 · Answer 2 · 2015-04-17 06:09:50Z

Minor problems with the test program

I got a compiler warning on this:
```
 printf("%zu\n", fsize);
```
Since fsize is a long, it should be %ld. Or change fsize to a size_t.
Here you set filename to one of the command line arguments:
```
filename = argv[i];
```
But later you ignore filename and just use argv[1]:
```
FILE* f = fopen(argv[1], "rb");
```

Speeding up the bitreading function

Given the sample program, the reading can be split into two cases:

Reading less than 8 bits.
Reading 8 bits in an aligned fashion.

I split the bitreading function into two separate functions to handle the two cases separately:

static uint64_t bitreader_read_bits(bitreader_t* b, int bits)
{
    uint64_t result = b->data[b->bytes_read];

    result = (result >> (8 - bits - b->bits_read)) & ((1 << bits) - 1);
    b->bits_read  += bits;
    b->bytes_read += (b->bits_read >> 3);
    b->bits_read  &= 0x7;
    return result;
}

static uint64_t bitreader_read_bytes(bitreader_t* b, int num_bytes)
{
    uint64_t result = b->data[b->bytes_read++];

    while (--num_bytes > 0) {
        result <<= 8;
        result |= b->data[b->bytes_read++];
    }
    return result;
}

Then in the main loop, I can do the following:

while (b.bytes_read + NUM_BYTES_SUM < b.len) {
    for (i = 0; i < sizeof(NUM_BITS); ++i) {
        int num_bits = NUM_BITS[i];
        uint64_t bits = 0;
        int leftover_bits = num_bits & 0x7;
        if (leftover_bits == 0) {
            bits = bitreader_read_bytes(&b, num_bits >> 3);
        } else {
            bits = bitreader_read_bits(&b, leftover_bits);
            if (num_bits >= 8) {
                bits <<= (num_bits - leftover_bits);
                bits |= bitreader_read_bytes(&b, num_bits >> 3);
            }
        }
        if (verbose) {
            printf("%d + %d\n", (int) b.bytes_read, (int) b.bits_read);
            printf("Read %zu bits and got %llx\n", num_bits, bits);
        }
    }
}

With these changes, the program became 65% faster than the original.

Letting the compiler inline/unroll special cases

It can become even faster if you let the compiler inline/unroll some special cases like this:

while (b.bytes_read + NUM_BYTES_SUM < b.len) {
    for (i = 0; i < sizeof(NUM_BITS); ++i) {
        int num_bits = NUM_BITS[i];
        uint64_t bits = 0;
        switch (num_bits) {
            case  1: bits = bitreader_read_bits (&b, 1); break;
            case  8: bits = bitreader_read_bytes(&b, 1); break;
            case 16: bits = bitreader_read_bytes(&b, 2); break;
            case 32: bits = bitreader_read_bytes(&b, 4); break;
            case 64: bits = bitreader_read_bytes(&b, 8); break;
            default:
            {
                int leftover_bits = num_bits & 0x7;
                if (leftover_bits == 0) {
                    bits = bitreader_read_bytes(&b, num_bits >> 3);
                } else {
                    bits = bitreader_read_bits(&b, leftover_bits);
                    if (num_bits >= 8) {
                        bits <<= (num_bits - leftover_bits);
                        bits |= bitreader_read_bytes(&b, num_bits >> 3);
                    }
                }
            }
        }
        if (verbose) {
            printf("%d + %d\n", (int) b.bytes_read, (int) b.bits_read);
            printf("Read %zu bits and got %llx\n", num_bits, bits);
        }
    }
}

With this new code, the speed is now 104% faster than the original (2.04x faster).

Limitations

It should be noted that this method is not as general as the one by @LokiAstari. This solution depends on the fact that all byte sized reads are aligned (which is true of the given example). If in the real program, you will need to do byte sized reads that are not aligned, then the answer from @LokiAstari will be required.

Further Tinkering

I thought about it some more, and I came up with a 64-bit "cache" solution which reads ahead 64 bits at a time. Here are the relevant portions:

#include <endian.h>

typedef struct {
    const uint8_t* data;
    size_t len;
    size_t bytes_read;
    uint64_t cachedVal;
    uint32_t validBits;
} bitreader_t;

static void bitreader_load_cache(bitreader_t *b)
{
    uint64_t val = *(uint64_t *) &b->data[b->bytes_read];

    b->bytes_read += 8;
    b->cachedVal = htobe64(val);
    b->validBits = 64;
}

void bitreader_init(bitreader_t* b, const uint8_t* data, size_t len)
{
    b->data = data;
    b->len = len;
    b->bytes_read = 0;
    bitreader_load_cache(b);
}

uint64_t bitreader_read_bits(bitreader_t* b, uint8_t bits)
{
    uint32_t validBits = b->validBits;
    uint64_t result = 0;

    if (bits >= validBits) {
        bits -= validBits;
        result = (b->cachedVal & ((1ull << validBits) - 1)) << bits;
        bitreader_load_cache(b);
        validBits = 64;
    }
    validBits -= bits;
    result |= (b->cachedVal >> validBits) & ((1ull << bits) - 1);
    b->validBits = validBits;
    return result;
}

In main():

    // Allocate 8 extra zeroed bytes here because we read ahead 64 bits.
    uint8_t* fbytes = calloc(fsize+8, sizeof(char));

    // ...

    // Don't use b.bytes_read because it is always up to 8 bytes ahead
    // of where we have actually read.
    size_t total_bytes_to_read = b.len - NUM_BYTES_SUM;
    size_t bytes_read = 0;

    while (bytes_read < total_bytes_to_read) {
        for (i = 0; i < sizeof(NUM_BITS); ++i) {
            size_t num_bits = NUM_BITS[i];
            uint64_t bits = bitreader_read_bits(&b, num_bits);
            if (verbose) {
                printf("Read %zu bits and got %llx\n", num_bits, bits);
            }
        }
        bytes_read += NUM_BYTES_SUM;
    }

This program ran 2.37x faster than the original program, and it properly handles unaligned bytes. On a non-x86 machine, you may have to align the start of the data buffer at a 64-bit boundary, but malloc may already do that for you.

I found that I could do even better with a mixture of this and LokiAstari's version. It looks like gcc is giving me a lot of things for free with -O3 (like loop unrolling, and converting / and % into bitwise operators. Splitting out aligned byte reading and special-casing it made a huge difference in my test program, and a pretty noticable difference in my real program (in my real program I have functions like bitreader_read_uint8, and I'm having them check alignedness and calling directly into bitreader_read_bytes_aligned_unchecked). — Brendan Long, Apr 17 '15 at 1:29

vnp · Answer 3 · 2015-04-16 21:05:46Z

up vote 0 down vote

gperftools confirms that it spends 99% of its time in bitreader_read_bits_unchecked()

I am not surprised. The application doesn't have anything else to spend time in.

Regarding optimization, LokiAstari advise is very sound indeed. In the old days a variation of Duff's device would be recommended.

answered Apr 16 '15 at 21:05

vnp

24.3k1262

I considered Duff's device, but I think -O3 already does that. – Brendan Long Apr 16 '15 at 21:21

add a comment |

asked	1 year ago
viewed	149 times
active	1 year ago

current community

your communities

more stack exchange communities

Bitstream reader

3 Answers 3

Minor problems with the test program

Speeding up the bitreading function

Letting the compiler inline/unroll special cases

Limitations

Further Tinkering

Your Answer

Not the answer you're looking for? Browse other questions tagged performance c bitwise or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Bitstream reader

3 Answers 3

Minor problems with the test program

Speeding up the bitreading function

Letting the compiler inline/unroll special cases

Limitations

Further Tinkering

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged performance c bitwise or ask your own question.

Related

Hot Network Questions