Range Coding and rANS as Practical Entropy Coders

Arithmetic coding as usually described manipulates a pair of endpoints and emits bits only when the interval commits to one half. It reaches the entropy bound and it is slow: every symbol requires a multiply, a divide, and a comparison chain, and the bit-at-a-time output prevents the coder from working in machine words. Two reformulations keep the rate and remove most of the cost. The range coder reorganizes the same arithmetic around bytes and defers carry propagation; the asymmetric numeral system replaces the interval with a single integer and inverts the coding direction, which turns out to make the state splittable.

The range coder’s reformulation

A range coder keeps one number, the current range, plus a low value and a count of pending bytes for carry propagation. Encoding a symbol with frequency $f$, cumulative start $c$, and total $M$ narrows the range:

$$r’ = \left\lfloor \frac{r}{M} \right\rfloor \cdot f, \qquad low’ = low + \left\lfloor \frac{r}{M} \right\rfloor \cdot c$$

The range is normalized to a fixed width, typically 24 or 32 bits, by shifting out the top byte whenever it becomes small. The critical difference from bit-oriented arithmetic coding is that the carry from low cannot be resolved immediately: adding to low may overflow into bytes already emitted. The standard solution is to keep a cache byte and a run count, and to propagate the carry only when the next byte is flushed. This is the “carryless” range coder design, and it exists precisely because deferring the carry is cheaper than resolving it eagerly.

The cost per symbol is one division by $M$ when $M$ is not a power of two, or a shift when it is. That is why range coders in practice use a total frequency that is a power of two, often $2^{11}$ or $2^{12}$ for binary adaptive models, so that the division becomes a shift and the multiply becomes a shift-and-add. The precision loss from rounding frequencies to a power-of-two total is small, since the model’s probabilities are quantized and the rate penalty is second order in the quantization step, but it is not zero, and it interacts with the model’s own adaptation.

LZMA and its descendants use exactly this structure with binary contexts: each decision is coded with a probability estimated from a small state machine, and the encoder keeps less than a full machine word of precision for the range. Binary coding sidesteps the general $M$-ary case entirely, at the cost of requiring the model to decompose each symbol into a sequence of binary decisions. The decomposition is where the modelling quality lives, and it is why a format built on binary range coding can still outperform a general arithmetic coder with a worse model.

The asymmetric numeral system

The rANS formulation inverts the usual direction. Instead of maintaining an interval and narrowing it, the encoder maintains a single integer $x$ that represents the entire message so far, and maps it through the symbol’s frequency interval:

$$x’ = \left( x \gg s \right) \cdot 2^{s} + f + \left( x \bmod 2^{s} \right)$$

The decoder inverts it: the slot is $x’ \bmod 2^{s}$, the symbol is whichever table entry covers that slot with cumulative start $c$ and frequency $f$, and the previous state is recovered as

$$x = 2^{s} \cdot \left\lfloor x’ / 2^{s} \right\rfloor - c + \left( x’ \bmod 2^{s} \right)$$

where the symbol is identified by finding the one whose interval $[c, c+f)$ contains the slot. The transformation is bijective on the appropriate domain, which is the property that makes the scheme lossless: every integer in the image corresponds to exactly one predecessor, so decoding recovers the exact state and hence the exact symbol.

The name comes from the fact that the decoding map is not the encoder map run backwards: the encoder folds the symbol’s slot into the low bits below the state’s integer quotient, so the state grows by a factor of about $2^{s}/f$ per symbol on average, and each symbol’s low bits carry its frequency interval. The decoder reverses the arithmetic exactly, reading the symbol’s slot out of the low bits and shrinking the state by the same factor. The result is a numeral system in base $2^{s}$ whose digit probabilities are the model’s frequencies rather than equal weights, which is precisely the generalization that ordinary base-2 notation lacks.

Because $x$ grows without bound during encoding, renormalization is required. The encoder flushes the low byte whenever $x$ reaches a threshold that depends on $f$ and on the table’s scale bits $s$ (with $M = 2^s$); the decoder pulls bytes back whenever $x$ falls below a lower bound $L$. With 32-bit renorm and a lower bound of $L = 2^{23}$, the standard arrangement keeps $x \in [L, 256L)$ for a 32-bit encoder, flushing while $x \ge ((L \gg s) \ll 8) \cdot f$. The threshold depends on the symbol’s frequency, which is why the renormalization condition must be checked per symbol rather than once per iteration.

# rANS, 32-bit state, byte renormalization, M = 1 << scale_bits.
L = 1 << 23
MASK = 0xFF

def encode(symbols, freq, start, scale_bits, state=L):
    """Returns the renormalization bytes in the order the decoder consumes them."""
    M = 1 << scale_bits
    out = bytearray()
    for s in reversed(symbols):          # rANS encodes in reverse order
        f, c = freq[s], start[s]
        x_max = ((L >> scale_bits) << 8) * f
        while state >= x_max:
            out.append(state & MASK)     # decoder reads these back in this order
            state >>= 8
        state = (state // f) * M + (state % f) + c
    for _ in range(4):                   # final state occupies the first four bytes
        out.append(state & MASK)
        state >>= 8
    return bytes(out)

def decode(data, table, freq, start, scale_bits, n):
    M = 1 << scale_bits
    state = int.from_bytes(data[:4], 'little')
    pos = 4
    out = []
    for _ in range(n):                   # symbol count is in the header
        slot = state % M
        s = table[slot]                  # table maps slot -> symbol
        out.append(s)
        state = freq[s] * (state // M) + slot - start[s]
        while state < L and pos < len(data):
            state = (state << 8) | data[pos]
            pos += 1
    return out

Two details are load-bearing. The encoder processes symbols in reverse, because the state represents the message with the most recently encoded symbol at the top of the stack; decoding then recovers symbols in forward order. The flush appends the full state as four little-endian bytes after the renormalization bytes, so the state occupies the first four bytes of the output and the decoder starts from the exact final value rather than from a truncated one. And the decoder needs the symbol count from the header, since a byte-oriented renormalization stream has no in-band end marker: any attempt to infer the end from the state alone is ambiguous when the final symbols are frequent.

Interleaving and why it matters

The rANS state is a single integer, and consecutive symbols update it serially. That looks like a serial dependency as bad as arithmetic coding’s. The trick that makes rANS fast is interleaving: run $k$ independent states, assign symbols to them round-robin, and encode each state’s subsequence independently. Decoding runs the same states in the same order, so the dependency chain per state is $1/k$ as long as the stream.

With $k = 2$ the two states can be updated in the same instruction window; with $k = 4$ or $k = 8$ the coder saturates a superscalar core’s integer units. This is the structural difference from a range coder: the range coder’s carry propagation couples every output byte to all previous ones, so it cannot be split without encoding separate streams and paying a header per stream.

The price of interleaving is a small rate loss from having $k$ states initialized and flushed, each costing a few bytes of state. For a large block the loss is negligible; for a small block it is not, which is why formats choose the interleave factor per block size and why tiny blocks are often stored uncompressed.

Choosing between a range coder and rANS

The choice is not about compression ratio. Both reach the same rate for the same model, up to rounding, because both implement the same ideal length. The differences are in implementation and in what the surrounding format needs.

Property	Range coder	rANS
Output granularity	Byte, with deferred carry	Byte, per-state
Symbol order	Forward	Reverse (encoder)
Parallel states	Not without separate streams	Yes, interleaved
Typical use	Streaming formats with binary contexts	Block formats with static tables
Renormalization	Per range width	Per symbol, frequency-dependent

The reverse-order requirement of rANS is a genuine constraint. An encoder that produces symbols incrementally, such as a streaming parser that cannot buffer the whole block, must either buffer the symbol sequence or use a range coder. A block-oriented encoder that knows the whole token sequence in advance has no problem reversing it, which is why rANS fits block compressors and range coding fits streaming ones.

A second constraint is that rANS with a static frequency table needs the table transmitted or derived. If the table is derived from the data, the encoder must make two passes: one to count, one to encode. Range coders with adaptive binary models need one pass and no table, which is a decisive advantage for small blocks and for streaming.

Failure modes in the integer coders

State underflow and overflow. Both coders rely on invariants that are easy to violate by one bit. An rANS encoder that checks the renormalization threshold against the wrong lower bound produces a stream that decodes to different symbols rather than failing loudly. The invariant to test is that the decoder’s state after every step matches the encoder’s state before the corresponding step, for random symbol sequences and for the extreme frequencies in the table.

Zero frequencies. A symbol with frequency zero cannot be encoded: the division by $f$ is undefined, and the interval has no width. Adaptive models must never let a count reach zero, which is why rescaling rounds up. A static table built from counts must add one to every symbol, which costs a small rate penalty proportional to the alphabet size over the total.

Quantization of skewed distributions. With a 12-bit total, the smallest representable probability is $2^{-12}$. A symbol whose true probability is $2^{-20}$ is coded as $2^{-12}$, costing eight extra bits per occurrence. Highly skewed sources therefore need a larger total or a different decomposition, often a binary context tree that represents the skew as a path of decisions rather than as one flat frequency.

Carry bugs in range coders. The deferred carry is the single most error-prone part of a range coder. A byte that should have been incremented is emitted before the carry arrives, and the result decodes correctly for most inputs and fails for a specific pattern of low values. The standard test is exhaustive over short inputs with a model that produces many near-boundary ranges, not random testing over long ones.

Interleave factor mismatch. An rANS decoder that assumes a different interleave factor than the encoder produces garbage from the first symbol. The factor is part of the format, not a free parameter of the implementation, and formats that allow it to vary must record it in the header.

The larger point is that these coders are interchangeable in rate and not in structure. The model, meaning which contexts exist, how probabilities are estimated, and how symbols are decomposed into binary decisions, determines the compression; the coder determines how fast the model’s probabilities can be turned into bytes. That division of labour is what Arithmetic Coding by Interval Subdivision establishes in the abstract and what the integer formulations here make practical.