Range Coder

Algorithms & Numeric

A binary arithmetic (range) coder — the compression primitive behind LZMA and video codecs. Each bit narrows a 32-bit interval by a probability: bound = (range >> PBITS) * prob (a 32-bit multiply), and when the range gets too small a byte-wise renormalization loop shifts a byte out and scales back up. An adaptive probability drifts with the coded bits. Compiler stress-test #86.

loading core…

Self-running — top bar = current range; below = emitted-byte waterfall.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

The teal bar across the top is the coder's current range — the width of the live interval. As bits are encoded it shrinks; when it drops below 2²⁴ the renormalization loop fires, emitting a byte (shown in the waterfall below) and scaling the interval back up. The white tick marks the adaptive probability as it drifts with the incoming bit stream.

// Binary range coder — the interval split is a 32-bit multiply, renorm is a shift loop.
void encode_bit(uint8_t bit, uint16_t prob) {   // prob/4096 = P(bit==0)
  uint32_t bound = (range >> PBITS) * prob;      // __mulsi3 (32-bit mul) + G_LSHR
  if (bit == 0) range = bound;
  else        { low += bound; range -= bound; }
  while (range < (1u<<24)) {                     // byte-wise renormalization
    emit(low >> 24); low <<= 8; range <<= 8;     // 32-bit G_SHL / G_LSHR carry loop
  }
}

The 65816 has neither a 32-bit multiply nor a barrel shifter, so both the interval split and the renormalization compile to library calls / shift loops — a realistic stress of the backend's 32-bit arithmetic in a tight feedback loop.

Compiler stress-test

Item	What it exercises
multiply-driven interval	Arithmetic coding narrows a numeric interval by the symbol probability each step. The split point bound = (range >> PBITS) * prob is a 32-bit multiply (__mulsi3) preceded by a logical shift (G_LSHR) — the 65816 has no 32-bit multiply instruction, so this is a library call in a hot loop.
renormalization carry loop	When the range shrinks below 2²⁴, the coder shifts a byte out of the top and scales range and low up by 256. That while-loop is a data-dependent count of 32-bit shifts (G_SHL/G_LSHR) with a carry into the emitted byte — the second codegen corner.
adaptive probability	The probability is nudged toward each observed bit (prob += (4096−prob)>>5 on a 0, prob −= prob>>5 on a 1), so the interval geometry keeps changing — exactly the feedback shape a real adaptive coder (LZMA, CABAC) uses.
distinct from #67 / #49	#67 huffman assigns fixed bit-length codes from a table (no multiply-interval). #49 lzdec copies match/literal runs (no arithmetic coding). This is the only battery demo doing multiply-driven range coding.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg and MAME. Hit Verify fidelity to reproduce the build gate's WRAM assert (range-coder CRC 0x6D21 — a fold of the emitted bytes + final state) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean.