Bit Reader / Writer (C)
Topics: bit manipulation, serialization, codecs
Problem
Implement a bitstream reader and writer over a byte buffer (no allocation): pack
and unpack fields of 1 to 32 bits that do not have to land on byte boundaries.
void br_init(BitReader *r, const unsigned char *buf, size_t nbytes);
uint32_t br_read(BitReader *r, int n, bool *ok); // n bits, MSB-first, *ok on success
void bw_init(BitWriter *w, unsigned char *buf, size_t nbytes);
bool bw_write(BitWriter *w, uint32_t value, int n); // low n bits, MSB-first
size_t bw_bits(const BitWriter *w);
Use the MSB-first convention: the high bit of each value is written first, and
bits fill each byte from bit 7 down to bit 0. Reading the bits back in the same order
must reproduce the exact values written.
Key concepts
- Track a bit position, not a byte position. The writer and reader each hold a
running bit offset. The byte is
pos >> 3 and the bit within it is pos & 7. Since
you fill MSB-first, the shift for bit pos is 7 - (pos & 7).
- Fields straddle bytes. A 9-bit field starting at bit 6 spills across two bytes.
Because you operate one bit at a time against the running offset, this just works,
no special casing.
- Bounds matter. A read past the end sets
*ok = false; a write past the end
returns false. A real codec relies on these to detect truncated input.
Sub-byte packing is everywhere bytes are too coarse: Huffman codes, PNG/JPEG, video
codecs, protocol headers with bit flags, and anything that squeezes structure into
the smallest space.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/bitio && /tmp/bitio
Sign in to submit your solution.