Lesson 02 · Writing a fixed-width code - Build a Compression Tool

Writing a fixed-width code

Writing bits one at a time is tedious; codes come in fixed widths. Today you add a helper that writes the low N bits of a value in one call, still most significant bit first, so a Huffman or length code is a single operation later.

The goal

Add WriteBits(value, width) that writes the low width bits of value, most significant first.

Start here - the target

TO DO

Scenario: A three-bit code packs high first

Givena new bit writer

WhenWriteBits(6, 3) is called (6 is binary 110) and the writer is flushed

Thenthe output is a single byte 0xC0 (binary 11000000)

Andthe bits appear in order 1, 1, 0 from the top of the byte

Background

A code is a value plus a width: the Huffman code for a symbol might be the value 6 written in 3 bits, 110. Writing it bit by bit works but reads badly, so wrap it once. WriteBits(value, width) emits the low width bits of value, most significant first - the same order as WriteBit, so the two compose cleanly.

The direction matters. To write high bit first you loop from bit width-1 down to bit 0, shifting each into place and calling WriteBit. WriteBits(6, 3) sends 1, then 1, then 0, giving 11000000 once flushed, which is 0xC0. Only the low width bits are used; any higher bits of value are ignored, so a 3-bit code and a value like 6 fit exactly.

Make it work

// walk the chosen bits from the highest down to bit 0
func (w *BitWriter) WriteBits(value uint, width uint) {
  for i := int(width) - 1; i >= 0; i-- {
    w.WriteBit((value >> uint(i)) & 1)
  }
}
// WriteBits(6, 3): i=2 -> bit1, i=1 -> bit1, i=0 -> bit0  => 1,1,0

CheckpointDONE

You can write a whole fixed-width code in one call. Commit and stop here.