Static Arithmetic Coding

hard · compression, arithmetic-coding, entropy

Static Arithmetic Coding

Build an interoperable encoder and decoder using a supplied, fixed byte-frequency model. The lesson derives the interval equations and deferred-bit rule.

func BuildFrequencies(data []byte) []int
func ArithmeticEncode(data []byte, freqs []int) []byte
func ArithmeticDecode(encoded []byte, freqs []int) []byte

Model and input contract

freqs contains exactly 257 nonnegative counts: byte symbols 0–255, then EOF at index 256.
EOF and every input byte have positive frequency. Zero-frequency symbols are skipped during decoding.
Total frequency is positive and at most 1<<20; input length is at most 4096 bytes.
BuildFrequencies returns byte counts plus freqs[256]=1, including for empty input.
Encoder and decoder receive identical tables. The table need not be built from this particular message.
Do not modify data, encoded, or freqs.

Invalid models and corrupted/truncated streams are outside this exercise's contract. These functions have no error-reporting API. Decoding assumes a stream produced according to the format below, including EOF; a stream is not validated merely because decoding produces bytes.

Bitstream format

Use an inclusive interval initially [0, 2^32-1], with arithmetic widened to uint64. Define H=2^31, Q=2^30, cumulative counts C, and total T.

For each input byte, then EOF, let R=high-low+1 and base=low:

low  = base + floor(R*C[s]/T)
high = base + floor(R*C[s+1]/T) - 1

Repeatedly apply the first matching case:

high<H: emit 0.
low>=H: emit 1 and subtract H from both endpoints.
low>=Q && high<3*Q: increment pending and subtract Q from both endpoints.
Otherwise stop normalizing this symbol.

After cases 1–3, double low and set high=2*high+1. Emitting a bit also writes all pending complements and clears pending. After EOF, increment pending and emit 0 if low<Q, otherwise 1.

Write bits MSB-first, padding the last byte with zeros. The decoder initializes a 32-bit code register and supplies zero bits after physical input ends. Select a symbol using:

v = floor(((code-low+1)*T-1)/(high-low+1))
C[s] <= v < C[s+1]

Return decoded bytes before EOF; EOF itself is not output. Decoder normalization subtracts the same offset from code and shifts in a bit whenever it scales the interval.

Worked compatibility vectors

All unspecified frequencies are zero.

Model	Input	Encoded bytes (hex)
EOF:1	empty	40
A:2, B:1, EOF:1	AB	5a
A:1, B:2, EOF:1	BB	94

The third vector exercises consecutive deferred bits. Explain why those bits become zeros before relying on a round trip.

Implementation checkpoints

Use one cumulative table on each side. Keep the old interval base until both new endpoints are computed. Check values at partition boundaries, sparse frequency tables, empty input, all byte values, and a shared model whose counts differ from the input histogram.

A linear search over 257 symbols is sufficient for decoding. Extra working memory is O(257), excluding returned bytes.

package solution

// BitWriter writes bits MSB-first.
type BitWriter struct {
	buf   []byte
	cur   byte
	nbits uint8
}

func NewBitWriter() *BitWriter { return &BitWriter{} }

func (bw *BitWriter) WriteBit(bit uint8) {
	if bit&1 == 1 {
		bw.cur |= 1 << (7 - bw.nbits)
	}
	bw.nbits++
	if bw.nbits == 8 {
		bw.buf = append(bw.buf, bw.cur)
		bw.cur = 0
		bw.nbits = 0
	}
}

func (bw *BitWriter) Bytes() []byte {
	out := make([]byte, len(bw.buf))
	copy(out, bw.buf)
	if bw.nbits > 0 {
		out = append(out, bw.cur)
	}
	return out
}

// BitReader reads bits MSB-first.
type BitReader struct {
	data  []byte
	idx   int
	nbits uint8
}

func NewBitReader(data []byte) *BitReader { return &BitReader{data: data} }

func (br *BitReader) ReadBit() (uint8, bool) {
	if br.idx >= len(br.data) {
		return 0, false
	}
	b := br.data[br.idx]
	bit := (b >> (7 - br.nbits)) & 1
	br.nbits++
	if br.nbits == 8 {
		br.idx++
		br.nbits = 0
	}
	return bit, true
}

// BuildFrequencies counts bytes in data and appends EOF=1.
func BuildFrequencies(data []byte) []int {
	// TODO: implement
	return nil
}

// ArithmeticEncode encodes data + EOF using freqs.
func ArithmeticEncode(data []byte, freqs []int) []byte {
	// TODO: implement
	return nil
}

// ArithmeticDecode decodes until EOF using freqs.
func ArithmeticDecode(encoded []byte, freqs []int) []byte {
	// TODO: implement
	return nil
}