ANS Coding, in depth: the state as a number, a hand trace, rANS renormalization, tANS tables and interleaving

The idea: a number that absorbs symbols

Appending a decimal digit d to x gives 10x + d: x grows by a factor of 10, log2(10) bits, because all digits are equally likely. ANS generalises this: if symbol s has probability f/M, appending it should grow x by about M/f, a cost of log2(M/f) bits, the ideal Shannon cost.

The construction: split the integers into blocks of M consecutive values and give each symbol f_s slots out of every block, at offsets c_s to c_s + f_s - 1, where c_s is the cumulative frequency of the symbols before it. Encoding s maps x to the x-th occurrence of a slot belonging to s. Because s owns only f_s of every M integers, its x-th slot sits near x times M/f_s. In closed form:

encode:  x' = (x // f[s]) * M + c[s] + (x % f[s])
decode:  slot = x % M
         s    = the symbol with c[s] <= slot < c[s] + f[s]
         x    = f[s] * (x // M) + slot - c[s]

Decoding recovers the symbol and the previous state. The message lives in one integer, and the last symbol encoded is the first decoded: ANS is a stack.

Worked example: four symbols by hand

Take M = 16 and frequencies a = 11, b = 2, c = 2, d = 1, so the cumulative starts are a = 0, b = 11, c = 13, d = 15. Encode the message a b a d. Because ANS is last-in first-out, the encoder processes it backwards, starting from x = 16:

Decoding 4552: slot 4552 % 16 = 8, which belongs to a, and x becomes 11 * 284 + 8 = 3132. Slot 12 is b, giving 391; slot 7 is a, giving 271; slot 15 is d, giving 16, the initial state. Out comes a b a d, in the right order. The state grew from 16 to 4552, which is log2(4552 / 16) = 8.15 bits, against an ideal of 8.08 bits for these four symbols at these probabilities. The small excess comes from the integer rounding in x // f, which is largest when x is small relative to M.

Streaming rANS: renormalization

An unbounded integer is no use in a real coder. Streaming rANS keeps x inside a fixed interval [L, bL) between symbols, here L = 2^23 and b = 256, so x always fits in 32 bits. Before encoding s, the encoder shifts out low bytes until encoding s will land back inside the interval. The decoder does the mirror image after each symbol, shifting bytes in while x is below L. The precise encoder bound is x_max(s) = ((L >> PROB_BITS) << 8) * f[s]; it works because L is a multiple of M, which makes the encoder's and the decoder's choices about when to move a byte agree exactly. This is the byte-wise layout popularised by Fabian Giesen's public-domain ryg_rans.

PROB_BITS = 12
M = 1 << PROB_BITS            # frequencies sum to M
L = 1 << 23                   # state lives in [L, 256 * L) between symbols

def encode(msg, freq, cum):
    x = L
    out = bytearray()
    for s in reversed(msg):                       # encode backwards ...
        f = freq[s]
        x_max = ((L >> PROB_BITS) << 8) * f
        while x >= x_max:                         # renormalize: push low bytes out
            out.append(x & 0xFF)
            x >>= 8
        x = (x // f) * M + cum[s] + (x % f)
    for _ in range(4):                            # flush the 32-bit state
        out.append(x & 0xFF)
        x >>= 8
    out.reverse()                                 # ... so the decoder reads forwards
    return bytes(out)

def decode(data, n, freq, cum):
    slot_to_sym = [None] * M
    for s, f in freq.items():
        for k in range(cum[s], cum[s] + f):
            slot_to_sym[k] = s
    pos = 0
    x = 0
    for _ in range(4):
        x = (x << 8) | data[pos]
        pos += 1
    msg = []
    for _ in range(n):
        slot = x & (M - 1)
        s = slot_to_sym[slot]
        x = freq[s] * (x >> PROB_BITS) + slot - cum[s]
        while x < L:                              # renormalize: pull bytes in
            x = (x << 8) | data[pos]
            pos += 1
        msg.append(s)
    assert pos == len(data)
    return msg

With M a power of two, the decoder's modulo and division are a mask and a shift. Production encoders replace the division by f with a reciprocal multiply.

Quantizing frequencies

The coder needs integer frequencies that sum exactly to M. Real counts do not, so they must be quantized, and every symbol that occurs must keep at least one slot or it becomes unencodable. A simple scheme scales and floors, forces a minimum of 1, and hands the rounding error to the most frequent symbol:

def quantize(counts):
    """Scale raw counts to integer frequencies summing to M, every seen symbol >= 1."""
    total = sum(counts.values())
    syms = sorted(counts)
    freq = {s: max(1, counts[s] * M // total) for s in syms}
    top = max(syms, key=lambda s: freq[s])        # hand the rounding error to the
    freq[top] += M - sum(freq.values())           # most frequent symbol
    assert freq[top] > 0
    cum, run = {}, 0
    for s in syms:
        cum[s] = run
        run += freq[s]
    return freq, cum

Quantization costs the KL divergence between true and quantized distributions on every symbol. Rare symbols suffer most: a true share of 1/100,000 still costs 12 bits at M = 4096. Larger M helps but enlarges decode tables.

Measured against entropy and Huffman

Running the code on 100,000 symbols drawn with probabilities a 0.70, b 0.15, c 0.10, d 0.05 gave quantized frequencies a 2877, b 608, c 402, d 209 out of 4096:

Both round-trips were checked symbol for symbol. The stream is 3 bytes over the 16,445-byte information content, flush included; Huffman, with code lengths 1, 2, 3, 3, spends 10% more. On the binary source Huffman cannot go below one bit per symbol, while rANS spends 0.14. The live Huffman coding article explains where that one-bit floor comes from.

Tabled ANS and Zstandard's FSE

rANS still multiplies per symbol. Tabled ANS (tANS) precomputes the whole state machine for a state range of size L = 2^R: the state is an index into a table, and decoding one symbol is one lookup that yields the symbol, how many bits to read and a baseline to add. Zstandard's FSE is a tANS variant, and RFC 8878 specifies its decode table precisely. Each symbol gets as many cells as its normalized count, spread through the table with an odd step so symbols interleave:

def build_decode_table(norm, log):
    """norm[s] = normalized count (sum = 1 << log). Returns cells of (symbol, nb_bits, baseline)."""
    size = 1 << log
    mask, step = size - 1, (size >> 1) + (size >> 3) + 3
    sym_at = [None] * size
    pos = 0
    for s, f in enumerate(norm):          # spread: no "less than 1" symbols here
        for _ in range(f):
            sym_at[pos] = s
            pos = (pos + step) & mask
    table = [None] * size
    for s, f in enumerate(norm):
        cells = [k for k in range(size) if sym_at[k] == s]     # natural order
        nxt = 1 << (f - 1).bit_length()                         # next power of two >= f
        doubles = nxt - f                                       # lowest states get 1 more bit
        share = size // nxt
        widths = [2 * share if r < doubles else share for r in range(f)]
        base, order = 0, list(range(doubles, f)) + list(range(doubles))
        for r in order:                                         # baselines from the higher states
            nb = widths[r].bit_length() - 1
            table[cells[r]] = (s, nb, base)
            base += widths[r]
    return table

For the specification's own example, a symbol with count 5 in a 128-cell table, this produces bit counts 5, 5, 5, 4, 4 and baselines 32, 64, 96, 0, 16, exactly RFC 8878's Table 21. Decoding is then s, nb, base = table[state] followed by state = base + read_bits(nb). A frequent symbol reads 0 or 1 bits per occurrence; a symbol with one cell in 32 reads 5. Zstandard writes accuracy logs from 5 upward and caps them at 9 for literal-length and match-length tables and 8 for offsets; its predefined default tables use logs of 6, 6 and 5. Very rare symbols get a special "less than 1" probability: one cell at the end of the table that triggers a full state reset.

At 16 cells and above the step is odd, so it visits every cell once; at 8 cells it is 8 and would stall on cell 0, so toy tables need a different spread.

Interleaving and other tricks

Decoding one rANS stream is a chain of dependent operations. CPUs can run several independent chains at once, so fast codecs keep two, four or more states, assign symbols round-robin and write one shared byte stream. Giesen's 2014 paper on interleaved entropy coders showed the decoder needs no side information to know which state consumes each byte, because both sides make the same renormalization decisions in mirror order. The idea extends to SIMD lanes and GPU threads, at the cost of a few bytes per extra state flush.

ANS's stack behaviour also enables bits-back coding with latent variable models, the basis of research compressors such as BB-ANS.

Failure modes

• Encoding forwards. If the encoder walks the message forwards, the decoder emits it reversed. Buffer the block, encode backwards, and output the bytes reversed, exactly as in the code above. This is why ANS is block-based and why adaptive models are awkward: the decoder's model sees symbols in the opposite order the encoder visited them.
• A zero frequency for a present symbol. x // 0 crashes the encoder, or with a clamped table, the symbol silently decodes as a neighbour. Enforce frequency at least 1 for every symbol that occurs.
• Mismatched renormalization constants. Encoder and decoder must use the same L, byte width and PROB_BITS; L must be a multiple of M. One wrong constant gives garbage, not an error.
• Overflow. Between symbols x stays below 256 L = 2^31, so the layout above fits a 32-bit unsigned state. Change L, the byte width or M and you must redo that bound. Python integers never overflow, which hides this bug until the coder is ported to C.
• No integrity check. A flipped bit corrupts everything after it within the block. Frame blocks independently and checksum them; Zstandard frames can carry a content checksum.

Trade-offs

Use ANS when the model is static per block and decode speed matters. Use arithmetic coding, covered in the live arithmetic coding article, when probabilities change every symbol, as in context mixing or language-model compressors. To see FSE in a full pipeline, read the live Zstandard article.

What to do next

1. Run the M = 16 trace above by hand once; then run the rANS code and confirm a round-trip on your own data.
2. Measure entropy, rANS output and Huffman output side by side before choosing a coder.
3. Pick M (PROB_BITS 12 as here is a reasonable start) and measure the quantization loss on your real symbol distribution at a few sizes, especially for rare symbols.
4. Always encode in reverse and frame data in independent blocks with checksums.
5. Add two or four interleaved states once correctness is proven, and benchmark decode throughput, not just ratio.
6. Before writing your own, try a vetted library: Zstandard for general data, or the FSE and ryg_rans reference code if you need a raw entropy stage.
7. Fuzz the decoder with truncated and corrupted inputs; it must fail cleanly, never read past the buffer.