Range Coder, in depth: byte-wise renormalization, carries with a cache and 0xFF run, LZMA's adaptive bit model and the frequency path

Two registers and one division

The encoder state is two integers. low is the bottom of the current interval and range is its width, so the interval is [low, low + range) on a number line that keeps growing to the right as bytes are shifted out. To code a symbol with cumulative frequency cum, frequency freq and model total total, the encoder computes one quotient and narrows:

r = range // total
low += cum * r
range = freq * r

The decoder mirrors this with a value code that holds the offset of the encoded number from low. It computes the same r, finds the symbol whose slot contains code // r, subtracts that slot's start and takes the same new range. Encoder and decoder therefore do identical arithmetic on range; only the encoder tracks low and only the decoder tracks code.

The integer division truncates, so the slots add up to total * r, up to total - 1 short of range. That remainder is never used, a real but small loss: with range at least 2²⁴ and total at most 2¹⁶, the wasted fraction is below 2^-8 per symbol in the worst case and usually far less. Some coders give the remainder to the last symbol; that is legal as long as the decoder does the same.

Byte-wise renormalization and the carry problem

Renormalization keeps range large. Whenever it drops below 2²⁴, the top byte of low is shifted out and both registers move left by eight bits. The trouble is that a later low += cum * r can overflow into a byte that was already shifted out. If that byte was 0x3A it becomes 0x3B; if it was 0xFF it becomes 0x00 and the carry ripples further left. There are three standard answers.

The cache approach is the one to learn, because it is exact. The low register is kept to 32 bits plus one carry bit. When a byte is ready to leave, either it is less than 0xFF, in which case nothing to its right can ever push a carry past it, or it is exactly 0xFF and must wait. A run of waiting bytes is just a count, so its length costs nothing to store. The first settled byte resolves the run: if a carry arrived, the cached byte gets plus one and the run becomes zeros; otherwise the cache and the run are written as they are.

Subbotin's carryless coder, circulated as public-domain C around 1999, instead waits for the range to fall below 2¹⁶ while the top byte is undecided, then clamps the range to the distance from low to the next 2¹⁶ boundary. It is simple and fast, but the clamp can cut the range sharply, and the model total must fit in 16 bits.

The adaptive binary coder

LZMA codes almost everything as binary decisions, each with its own adaptive probability. The probability that the next bit is zero is an 11-bit integer, initialized to 1024, which is one half. The split point of the interval is bound = (range >> 11) * p. A zero keeps the lower part; a one moves low up by bound and keeps the rest. After each bit the probability moves one thirty-second of the way toward what was seen. These constants (11 probability bits, a move shift of 5, a top value of 2²⁴) are the ones defined in the LZMA SDK's LzmaEnc.c and LzmaDec.c.

The update rule never lets the probability reach 0 or 2048. Subtracting p >> 5 stops changing anything once p is below 32, and adding (2048 - p) >> 5 stops once p is above 2016, so both halves of the split always have a non-zero width.

TOP = 1 << 24
PROB_BITS, MOVE_BITS = 11, 5

class RangeEncoder:
    def __init__(self):
        self.low, self.range = 0, 0xFFFFFFFF   # low may hold a carry in bit 32
        self.cache, self.pending = 0, 0        # settled byte + count of deferred 0xFF
        self.out = bytearray()

    def _shift_low(self):
        if self.low < 0xFF000000 or self.low >= 1 << 32:
            carry = self.low >> 32
            self.out.append((self.cache + carry) & 0xFF)
            for _ in range(self.pending):
                self.out.append((0xFF + carry) & 0xFF)
            self.pending = 0
            self.cache = (self.low >> 24) & 0xFF
        else:
            self.pending += 1          # top byte is 0xFF: a carry may still flip it
        self.low = (self.low << 8) & 0xFFFFFFFF

    def _normalize(self):
        while self.range < TOP:
            self.range <<= 8
            self._shift_low()

    def encode_bit(self, probs, i, bit):
        bound = (self.range >> PROB_BITS) * probs[i]
        if bit == 0:
            self.range = bound
            probs[i] += ((1 << PROB_BITS) - probs[i]) >> MOVE_BITS
        else:
            self.low += bound
            self.range -= bound
            probs[i] -= probs[i] >> MOVE_BITS
        self._normalize()

    def finish(self):
        for _ in range(5):            # push out cache, run and all four low bytes
            self._shift_low()
        return bytes(self.out)

class RangeDecoder:
    def __init__(self, data):
        if len(data) < 5 or data[0] != 0:
            raise ValueError("corrupt stream: bad header")
        self.data, self.pos = data, 5
        self.range = 0xFFFFFFFF
        self.code = int.from_bytes(data[1:5], "big")

    def _normalize(self):
        while self.range < TOP:
            self.range <<= 8
            b = self.data[self.pos] if self.pos < len(self.data) else 0
            self.pos += 1
            self.code = ((self.code << 8) | b) & 0xFFFFFFFF

    def decode_bit(self, probs, i):
        bound = (self.range >> PROB_BITS) * probs[i]
        if self.code < bound:
            self.range = bound
            probs[i] += ((1 << PROB_BITS) - probs[i]) >> MOVE_BITS
            bit = 0
        else:
            self.code -= bound
            self.range -= bound
            probs[i] -= probs[i] >> MOVE_BITS
            bit = 1
        self._normalize()
        return bit

The first byte of every stream is the initial cache, which is always zero, so the decoder can check it as a cheap corruption test. Five bytes at the start mirror the five _shift_low calls at the end; LZMA's decoder likewise consumes five bytes when it initializes (RC_INIT_SIZE is 5).

Worked trace: four bits

Here are the first four steps of coding the bits 0, 0, 1, 0 with one adaptive probability, as printed by the code above (hexadecimal registers, probability out of 2048).

Each zero keeps the bottom p / 2048 of the range and nudges p up; the one jumps low past the zero region and nudges p down. The range is still above 2²⁴, so no byte has left yet.

Bytes, bit trees and the frequency path

To code whole bytes with binary decisions, LZMA walks a bit tree: 255 probabilities indexed by the bits seen so far, most significant first. The node index starts at 1 and doubles plus the bit at each step, so the eight decisions for a byte use eight different contexts. This captures an order-0 byte distribution without any division.

def encode_bytes_bitwise(data):
    enc, probs = RangeEncoder(), [1 << (PROB_BITS - 1)] * 256
    for byte in data:
        node = 1
        for k in range(7, -1, -1):
            bit = (byte >> k) & 1
            enc.encode_bit(probs, node, bit)
            node = (node << 1) | bit
    return enc.finish()

# Multi-symbol path: frequencies with a total of at most 2**16.
import bisect
def encode_freq(enc, cum, freq, total):
    r = enc.range // total
    enc.low += cum * r
    enc.range = freq * r
    enc._normalize()

def decode_freq(dec, cum_table, total):       # cum_table has len(symbols) + 1 entries
    r = dec.range // total
    v = min(dec.code // r, total - 1)         # clamp: the remainder region maps to the last slot
    s = bisect.bisect_right(cum_table, v) - 1
    dec.code -= cum_table[s] * r
    dec.range = (cum_table[s + 1] - cum_table[s]) * r
    dec._normalize()
    return s

The frequency path costs a division per symbol plus the decoder's slot search, one reason binary models dominate LZMA-style coders. The cap on total matters: with range at least 2²⁴ after normalization and total at most 2¹⁶, r is at least 256, so no symbol with a non-zero frequency can collapse to an empty slot.

Tested and measured

The implementation round-tripped 300 inputs of up to 400 bytes, half random and half drawn from 00 00 00 FF FE 01 to provoke runs and carries, through both paths. Sizes on three inputs:

The static coder lands within six bytes of its model's entropy: the coder is not the bottleneck, the model is. The adaptive bit tree pays about 0.9 percent for learning its statistics as it goes, but it ships no table. On the skewed binary source the single adaptive probability costs 3.4 percent over entropy. That is the price of a shift of 5: the estimate tracks roughly the last few dozen bits, so it jitters around 0.05 instead of settling. A shift of 5 trades steady-state accuracy for fast adaptation; a larger shift wastes less on stationary data.

Failure modes

• Model desynchronization. The decoder must update every probability and frequency exactly as the encoder did, in the same order, after the same symbol. An update placed before the coding call in one side and after it in the other produces garbage from the first differing symbol, with no error raised.
• Dropped carry. Writing the top byte directly instead of through the cache works on most inputs and fails on a few; the round-trip test must include low-entropy data that produces runs of 0xFF, as above.
• Running past the end. A decoder fed a truncated stream keeps producing symbols from zero padding. Store the uncompressed length or an end marker, and verify a checksum, as xz does.
• Zero-frequency symbols. A symbol with frequency zero has an empty slot and cannot be coded at all. Adaptive models need a floor of one or an escape symbol.

Trade-offs

Where each fits in real codecs is surveyed in Entropy Coding, in depth, and Zstd Compression, in depth shows the ANS-based alternative in production.

What to do next

1. Implement the encoder and decoder above, then round-trip random bytes and a low-entropy stream full of 0xFF runs before trusting it.
2. Add a carry counter and confirm your test inputs actually exercise the carry branch.
3. Code a file with the bit tree and compare the output size with its order-0 entropy.
4. Change the move shift from 5 to 4 and 6 on stationary and drifting data, and record the size change.
5. Add a length header and a CRC32, then feed the decoder truncated and bit-flipped streams.
6. Replace the order-0 tree with an order-1 context (previous byte selects the tree) and measure the gain.
7. Port the hot loop to C with a 64-bit low and compare throughput with an rANS implementation.