Bit Reader

Most data sent over the wire, is formated in bits, but given as bytes.

Implementing the bit stream boils down to four simple statements:

• You keep a buffer, no smaller than 32 bits
• When filling the buffer, you write to the left
• When filling the buffer, you fill byte by byte.
• When consuming from the buffer, you read from the right.

Pseudo Code

def fill
    while offset < N
        buffer |= next() << offset
        offset += 8
        
def consume
    if offset < N then fill
    
    mask = (2 ^ N) - 1
    value = buffer & mask
    buffer >>= N
    offset -= N
    
    return value
    

Optimisations

Precompute, (hopefully with constant expressions and compile-time optimization) the masks for consuming.

Reading bytes can be improved by checking if the reader is currently "byte aligned".

• This can be done by checking if your offset is zero, e.g. no stored bits. (offset == 0)
• The benefit of which, is skipping the cost of filling then draining the buffer every time.