Bit I/O & Universal Codes

• Compression is bit-precise, not byte-precise
• MSB-first bit order throughout this pack
• Universal codes show integer coding costs

Bit order (MSB-first)

• First bit -> highest bit of byte
• WriteBits uses lowest n bits of value
• Padding with zeros at end

Common bit I/O bugs

• Off-by-one on partial bytes
• Reversed bit order
• Missing or wrong padding

Elias gamma

• k zeros where k = floor(log2 n)
• Then binary of n (k+1 bits)
• Prefix-free

Elias delta

• Gamma-code the bit-length L
• Append lower L-1 bits of n
• Better for large n

Why universal codes

• No model required
• Length grows ~ log2 n
• Not optimal when model known

What you will build

• Bitstream I/O
• Elias gamma/delta