ANS / Asymmetric Numeral Systems Overview

Why ANS / Asymmetric Numeral Systems Overview Matters

Suppose a data source emits independent symbols: A three quarters of the time and B one quarter of the time. A binary Huffman code still needs one bit for each symbol, averaging one bit per input. The source entropy is $$ H=-\tfrac34\log_2\tfrac34-\tfrac14\log_2\tfrac14\approx0.8113 $$ bits per symbol. An entropy coder can approach that fractional average by coding symbols together rather than assigning each occurrence its own complete, whole-bit codeword.

Asymmetric numeral systems (ANS) are a family of lossless entropy coders that represent a sequence through one evolving integer state and a stream of renormalization bits or bytes. Frequent symbols use a larger share of the state space, so they tend to add less information to the representation. ANS is an entropy-coding stage: a model supplies symbol probabilities, and the coder turns those probabilities into a reversible representation.

This overview develops range ANS (rANS) because its quotient-and-remainder formulas make the inverse visible. You will trace a complete small codec, understand its stack-like order, run identical Python, C++, and Java programs, and distinguish it from tabled ANS and production formats. The code includes byte renormalization and a concrete packet layout; it is more than an unbounded-integer demonstration.

Bit operations and integer division are the main prerequisites. The model and decoder here use small arrays, so hashing is not needed. For the broader idea and its variants, see Jarek Duda's ANS paper. Compression quality depends on model fit, state precision, block size, and framing; no entropy coder guarantees that every short input becomes smaller.

Core Concepts and Terminology

Symbols and a shared model. Let the alphabet be integer symbol IDs $0,\ldots,K-1$. Each symbol $s$ has positive integer frequency $f_s$; define total $M=\sum_s f_s$ and cumulative start $$ c_s=\sum_{t\lt s}f_t. $$ Symbol $s$ owns the residue slots $c_s,\ldots,c_s+f_s-1$ in $[0,M)$. The modeled probability is $q_s=f_s/M$. Encoder and decoder must agree on symbol ordering and every frequency, not merely the total.

The worked model assigns IDs $0,1,2,3$ to A, B, C, D and uses $$ f=(4,2,1,1),\quad c=(0,4,6,7),\quad M=8. $$ Slots $0$ through $3$ identify A; $4,5$ identify B; slot $6$ identifies C; slot $7$ identifies D.

The rANS state map. Ignoring bounded-state renormalization for a moment, push symbol $s$ into a nonnegative integer $x$ using $$ C_s(x)=M\left\lfloor\frac{x}{f_s}\right\rfloor+c_s+(x\bmod f_s). $$ To pop a symbol from encoded state $z$, compute $r=z\bmod M$, find the unique symbol with $c_s\le r\lt c_s+f_s$, and recover $$ D_s(z)=f_s\left\lfloor\frac{z}{M}\right\rfloor+(r-c_s). $$ Thus a residue identifies the symbol while the quotient and remaining residue reconstruct the prior state. When every symbol has frequency one, this reduces to ordinary base-$M$ push and pop: $C_s(x)=Mx+c_s$.

Why “asymmetric.” Ordinary positional notation allocates one equal-size digit slot per symbol. ANS allocates different numbers of slots according to the model. Roughly, pushing symbol $s$ multiplies the state by $M/f_s$, so the information increase is about $\log_2(M/f_s)=-\log_2q_s$. This is an information-rate explanation, not a fixed byte codeword assigned to each symbol.

Bounded state and byte stream. The programs use lower bound $L=16$ and radix $b=256$, maintaining normalized states in $[L,bL)=[16,4096)$. Valid model totals are powers of two no greater than $16$, so $M$ divides $L$. A renormalization step moves one low byte out of the encoder state or refills it in the decoder. Here at most one byte is moved per symbol.

Packet contract. The custom teaching packet contains a four-byte little-endian symbol count, a two-byte little-endian final encoder state, then refill bytes in decoder-consumption order. The frequency vector is supplied separately. A packet is one complete block; an outer container must supply its byte extent when several blocks share a file. This layout is not a Zstandard, FSE, or other established file format.

ANS has stack behavior: the last symbol encoded is the first decoded. To decode the original input left to right, the encoder visits it right to left. The final encoder state is the decoder's initial state; the seed $L$ is recovered after the final decoded symbol.

How ANS / Asymmetric Numeral Systems Overview Works, Step by Step

Build the model once per call. Validate the frequency vector, compute cumulative starts, and build a residue-to-symbol array of length $M$. Fill each symbol's $f_s$ slots with its ID. This makes symbol selection a single lookup. The small implementation uses positive frequencies only; zero-frequency and escape symbols require a separate format policy.

Encode from the last input symbol toward the first. Initialize $x=L$ and an empty emission list. For each symbol $s$, use threshold $$ T_s=b\frac{L}{M}f_s. $$ While $x\ge T_s$, append $x\bmod256$ to the emission list and replace $x$ by $\lfloor x/256\rfloor$. Then apply $x\leftarrow C_s(x)$. In our worked model the thresholds for A, B, C, D are $2048,1024,512,512$ respectively.

After all symbols, serialize the input count and final state, then append the emission list in reverse order. A decoder must undo the most recent state transition first, including consuming the most recently spilled byte first. Reversing this byte list changes byte order only, not the bit order inside a byte. A production encoder often achieves this by writing backward into a buffer; the teaching code uses an explicit list.

Decode from the first symbol toward the last. Read and validate the count and initial state. For each of the specified number of symbols, compute $r=x\bmod M$, select $s$ using the slot table, and assign $x\leftarrow D_s(x)$. While $x\lt L$, read the next payload byte $a$ and assign $x\leftarrow256x+a$. Record $s$. Running out of bytes when a refill is required is an error.

After exactly the declared count, require $x=L$ and require every payload byte to have been consumed. The first condition checks return to the seed; the second rejects trailing bytes. No end-of-message symbol is needed because the packet count is explicit. With zero input symbols, the count is zero, the state is $16$, and the packet is exactly six bytes.

One complete spill and inverse. For C, $f_C=1$, $c_C=6$, and $T_C=512$. Suppose the old encoder state is $601$. Since $601\ge512$, emit $601\bmod256=89$, hex 59, and reduce to $y=\lfloor601/256\rfloor=2$. Then $$ C_C(2)=8\cdot2+6=22. $$ The decoder sees residue $22\bmod8=6$, identifies C, and computes $$ D_C(22)=1\cdot\lfloor22/8\rfloor+(6-6)=2. $$ Since $2\lt16$, refill using the saved byte: $256\cdot2+89=601$. Both the old state and the symbol have been recovered exactly.

These are the standard arithmetic ingredients of byte-renormalized rANS; Fabian Giesen's reference implementation shows the same threshold-based structure with larger implementation parameters. The tiny state here is chosen for inspection, not for production compression speed or precision.

flowchart TD
    A["Validate shared frequency model"] --> B["Read count and final encoder state"]
    B --> C{"Header valid and state normalized?"}
    C -->|"No"| R["Reject packet"]
    C -->|"Yes"| D{"Decoded declared count?"}
    D -->|"No"| E["Use residue slot to identify symbol"]
    E --> F["Apply inverse rANS state map"]
    F --> G{"State below lower bound?"}
    G -->|"Yes"| H{"Refill byte available?"}
    H -->|"No"| R
    H -->|"Yes"| I["Refill: state = 256 state + byte"]
    I --> G
    G -->|"No"| J["Append decoded symbol"]
    J --> D
    D -->|"Yes"| K{"Seed recovered and payload exhausted?"}
    K -->|"No"| R
    K -->|"Yes"| Z["Return original symbol sequence"]

Worked Example with a Full Trace

Use text ABACABADABACABDA with model $f=(4,2,1,1)$ and seed $16$. There are sixteen symbols: eight A, four B, two C, two D. The model exactly matches these empirical proportions. Its entropy is $$ H=\tfrac12\cdot1+\tfrac14\cdot2+\tfrac18\cdot3+\tfrac18\cdot3 =\tfrac74 $$ bits per symbol, so the model information for this block is $16H=28$ bits before finite-state and framing costs. These probabilities are dyadic, so an appropriate Huffman code also has average $7/4$ bits here. This sample is selected for a readable trace, not to show an ANS advantage over Huffman.

The entire encoder run is in the next diagram. Index $i$ is the original zero-based input position. Rows are in processing order $15,14,\ldots,0$. Each row records the incoming state $x$, threshold $T$, emitted byte if any, reduced state $y$, quotient $q=\lfloor y/f_s\rfloor$, remainder $r=y\bmod f_s$, and resulting state $Mq+c_s+r$. Emitted bytes are hexadecimal; every other number is decimal.

The initial tail of the message illustrates growth without spilling: encoding A at index $15$ changes $16$ to $32$; D at $14$ changes $32$ to $263$; B at $13$ changes $263$ to $1053$; A at $12$ changes $1053$ to $2105$. At C, index $11$, threshold $512$ is exceeded: spill low byte $57$, hex 39, reduce to $8$, then map to $70$.

Two later spills occur at indices $7$ and $3$. At index $7$, old state $1112$ spills byte $88$, hex 58, reduces to $4$, and maps D to $39$. At index $3$, old state $601$ spills byte $89$, hex 59, reduces to $2$, and maps C to $22$. The remaining transitions end at final state $344$.

Thus the emission list is 39 58 59, while the serialized payload is 59 58 39. Count $16$ becomes 10 00 00 00. State $344=256+88$ becomes 58 01. The full packet is 10 00 00 00 58 01 59 58 39.

Every decoder step. In the following list, “inverse” is the state immediately after $D_s$ and “next” is the normalized state after any refill. Residue slots identify the symbols without guessing them.

1. Index $0$: state $344$, slot $0$ selects A; inverse $172$; no refill, next $172$.
2. Index $1$: state $172$, slot $4$ selects B; inverse $42$; no refill, next $42$.
3. Index $2$: state $42$, slot $2$ selects A; inverse $22$; no refill, next $22$.
4. Index $3$: state $22$, slot $6$ selects C; inverse $2$; read hex 59 ($89$), so next $2\cdot256+89=601$.
5. Index $4$: state $601$, slot $1$ selects A; inverse $301$; no refill, next $301$.
6. Index $5$: state $301$, slot $5$ selects B; inverse $75$; no refill, next $75$.
7. Index $6$: state $75$, slot $3$ selects A; inverse $39$; no refill, next $39$.
8. Index $7$: state $39$, slot $7$ selects D; inverse $4$; read hex 58 ($88$), so next $4\cdot256+88=1112$.
9. Index $8$: state $1112$, slot $0$ selects A; inverse $556$; no refill, next $556$.
10. Index $9$: state $556$, slot $4$ selects B; inverse $138$; no refill, next $138$.
11. Index $10$: state $138$, slot $2$ selects A; inverse $70$; no refill, next $70$.
12. Index $11$: state $70$, slot $6$ selects C; inverse $8$; read hex 39 ($57$), so next $8\cdot256+57=2105$.
13. Index $12$: state $2105$, slot $1$ selects A; inverse $1053$; no refill, next $1053$.
14. Index $13$: state $1053$, slot $5$ selects B; inverse $263$; no refill, next $263$.
15. Index $14$: state $263$, slot $7$ selects D; inverse $32$; no refill, next $32$.
16. Index $15$: state $32$, slot $0$ selects A; inverse $16$; no refill, next $16$.

The decoder has consumed all three payload bytes and returned to seed $16$. It reconstructs ABACABADABACABDA exactly. The two-byte state plus three refill bytes occupy five bytes; adding the four-byte count makes a nine-byte packet, versus sixteen ASCII bytes. That comparison excludes the separately shared model. A fixed two-bit packing of this four-symbol alphabet needs only four payload bytes, and a dyadic Huffman code uses $28$ payload bits before its own framing. The small custom packet's fixed header and state storage dominate such a short block; do not confuse its nine-byte result with the entropy limit.

Implementation in Python, C++, and Java

Each panel is a complete deterministic program. Use Python 3, C++17, or Java 8+; save the Java panel as Main.java. The sample uses the same model, symbol sequence, packet, round-trip checks, and malformed-packet checks in every language.

Supported model. The frequency vector has $1$ through $16$ entries, every entry is a positive integer at most $16$, and its total is one of $1,2,4,8,16$. Symbol IDs are integers from $0$ through $K-1$, and the message count is at most $100000$. A symbol with zero modeled frequency is unsupported. Frequency normalization from real-valued estimates is the caller's responsibility; these functions validate an already normalized model.

Public API. encode(symbols, frequencies) returns the custom packet; decode(packet, frequencies) returns the symbol IDs. make_model constructs cumulative starts and the slot table. Both calls validate the model first. Inputs are not mutated. Python accepts lists or tuples for symbols and frequencies, plus lists, tuples, bytes, or bytearray for packets; it rejects Boolean and floating-point elements. Java rejects null arrays; C++ uses integer vectors through its static types.

Exact packet layout. Offsets $0$ through $3$ contain the unsigned count in little-endian order. Offsets $4,5$ contain the final encoder state in little-endian order. Offset $6$ onward contains the reversed spill list. A decoder expects one complete packet, not concatenated packets. The frequency model is not stored inside it, so the caller must supply precisely the same frequency vector and symbol ordering. There is no universal ANS wire format that makes these details interchangeable.

The decoder limits the packet to $100006$ bytes and the count to $100000$. Under these model/state parameters, at most one payload byte is needed per symbol, so this global size limit covers every encoder result. Count parsing uses 64-bit arithmetic in C++ and Java before checking the supported limit. Normalized states and state arithmetic fit signed 32-bit integers; the header may represent a larger unsigned count, which is rejected before any decode loop or output allocation proportional to that count.

The routines return integer containers with byte values $0$ through $255$ for clarity. C++ vector<int> and Java int[] do not occupy one byte per element; the printed packet length is its logical wire-byte count. Use bytes(packet) in Python or write each validated element as one octet when producing packed storage. Java or C++ code reading signed byte types must convert them to nonnegative octets first.

Errors raise ValueError, invalid_argument, or IllegalArgumentException with matching labels: MODEL for an invalid frequency vector; SYMBOL for invalid symbol input; COUNT for an unsupported message length or header count; SIZE for an oversized packet; BYTE for invalid packet elements; TRUNCATED for a short header or missing refill; STATE for an initial state outside $[16,4096)$; FINAL_STATE for failure to return to seed $16$; and TRAILING for leftover bytes after decoding. Checks report the first detected error in the order shown.

An exception returns no partially decoded list from these APIs. The terminal checks reject many malformed packets, but a damaged packet or wrong model can still decode to a different valid message. These checks are not an integrity guarantee. Python and C++ use assertions for the sample round trip; Java uses explicit checks so its verification runs even with language assertions disabled.

L = 16
RADIX = 256
MAX_SYMBOLS = 100000


def make_model(frequencies):
    if (not isinstance(frequencies, (list, tuple))
            or not 1 <= len(frequencies) <= 16
            or any(type(f) is not int or not 1 <= f <= 16 for f in frequencies)):
        raise ValueError("MODEL")
    total = sum(frequencies)
    if total > 16 or total & (total - 1):
        raise ValueError("MODEL")
    cumulative, lookup, start = [], [], 0
    for s, frequency in enumerate(frequencies):
        cumulative.append(start)
        lookup.extend([s] * frequency)
        start += frequency
    return list(frequencies), cumulative, lookup, total


def encode(symbols, frequencies):
    f, c, _, total = make_model(frequencies)
    if not isinstance(symbols, (list, tuple)):
        raise ValueError("SYMBOL")
    if len(symbols) > MAX_SYMBOLS:
        raise ValueError("COUNT")
    if any(type(s) is not int or not 0 <= s < len(f) for s in symbols):
        raise ValueError("SYMBOL")
    state, emitted = L, []
    for s in reversed(symbols):
        threshold = RADIX * (L // total) * f[s]
        while state >= threshold:
            emitted.append(state & 255)
            state >>= 8
        state = (state // f[s]) * total + c[s] + state % f[s]
    count = len(symbols)
    packet = [(count >> (8 * j)) & 255 for j in range(4)]
    packet.extend((state & 255, state >> 8))
    packet.extend(reversed(emitted))
    return packet


def decode(packet, frequencies):
    f, c, lookup, total = make_model(frequencies)
    if not isinstance(packet, (list, tuple, bytes, bytearray)):
        raise ValueError("BYTE")
    if len(packet) > MAX_SYMBOLS + 6:
        raise ValueError("SIZE")
    if any(type(b) is not int or not 0 <= b <= 255 for b in packet):
        raise ValueError("BYTE")
    if len(packet) < 6:
        raise ValueError("TRUNCATED")
    count = sum(packet[j] << (8 * j) for j in range(4))
    if count > MAX_SYMBOLS:
        raise ValueError("COUNT")
    state = packet[4] + 256 * packet[5]
    if not L <= state < RADIX * L:
        raise ValueError("STATE")
    position, symbols = 6, []
    for _ in range(count):
        slot = state % total
        s = lookup[slot]
        state = f[s] * (state // total) + slot - c[s]
        while state < L:
            if position == len(packet):
                raise ValueError("TRUNCATED")
            state = RADIX * state + packet[position]
            position += 1
        symbols.append(s)
    if state != L:
        raise ValueError("FINAL_STATE")
    if position != len(packet):
        raise ValueError("TRAILING")
    return symbols


if __name__ == "__main__":
    text = "ABACABADABACABDA"
    frequencies = [4, 2, 1, 1]
    original = [ord(ch) - ord("A") for ch in text]
    packet = encode(original, frequencies)
    decoded = decode(packet, frequencies)
    assert decoded == original
    assert encode(decoded, frequencies) == packet
    print("model=[4,2,1,1]")
    print("text=" + text)
    print("packet=" + " ".join(f"{b:02X}" for b in packet))
    print("decoded=" + "".join(chr(ord("A") + s) for s in decoded))
    print(f"bytes={len(packet)} raw={len(original)}")
    bad = [
        ("truncated", packet[:-1]),
        ("trailing", packet + [0]),
        ("bad-state", packet[:4] + [0, 0] + packet[6:]),
    ]
    for label, data in bad:
        try:
            decode(data, frequencies)
        except ValueError as error:
            print(label + "=" + str(error))
        else:
            raise AssertionError("malformed packet accepted")

#include <cassert>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
using namespace std;

constexpr int L = 16, RADIX = 256, MAX_SYMBOLS = 100000;
struct Model {
    vector<int> f, c, lookup;
    int total;
};
Model make_model(const vector<int>& frequencies) {
    if (frequencies.empty() || frequencies.size() > 16)
        throw invalid_argument("MODEL");
    int total = 0;
    for (int f : frequencies) {
        if (f < 1 || f > 16) throw invalid_argument("MODEL");
        total += f;
    }
    if (total > 16 || (total & (total - 1))) throw invalid_argument("MODEL");
    Model m; m.f = frequencies; m.total = total;
    int start = 0;
    for (int s = 0; s < int(frequencies.size()); ++s) {
        m.c.push_back(start);
        for (int j = 0; j < frequencies[s]; ++j) m.lookup.push_back(s);
        start += frequencies[s];
    }
    return m;
}
vector<int> encode(const vector<int>& symbols, const vector<int>& frequencies) {
    Model m = make_model(frequencies);
    if (symbols.size() > MAX_SYMBOLS) throw invalid_argument("COUNT");
    for (int s : symbols)
        if (s < 0 || s >= int(m.f.size())) throw invalid_argument("SYMBOL");
    int state = L;
    vector<int> emitted;
    for (size_t i = symbols.size(); i > 0; --i) {
        int s = symbols[i - 1];
        int threshold = RADIX * (L / m.total) * m.f[s];
        while (state >= threshold) {
            emitted.push_back(state & 255); state >>= 8;
        }
        state = (state / m.f[s]) * m.total + m.c[s] + state % m.f[s];
    }
    int count = int(symbols.size());
    vector<int> packet;
    for (int j = 0; j < 4; ++j) packet.push_back((count >> (8 * j)) & 255);
    packet.push_back(state & 255); packet.push_back(state >> 8);
    packet.insert(packet.end(), emitted.rbegin(), emitted.rend());
    return packet;
}
vector<int> decode(const vector<int>& packet, const vector<int>& frequencies) {
    Model m = make_model(frequencies);
    if (packet.size() > MAX_SYMBOLS + 6) throw invalid_argument("SIZE");
    for (int b : packet) if (b < 0 || b > 255) throw invalid_argument("BYTE");
    if (packet.size() < 6) throw invalid_argument("TRUNCATED");
    int64_t count = 0;
    for (int j = 0; j < 4; ++j) count += int64_t(packet[j]) << (8 * j);
    if (count > MAX_SYMBOLS) throw invalid_argument("COUNT");
    int state = packet[4] + 256 * packet[5];
    if (state < L || state >= RADIX * L) throw invalid_argument("STATE");
    size_t position = 6;
    vector<int> symbols;
    for (int64_t i = 0; i < count; ++i) {
        int slot = state % m.total, s = m.lookup[slot];
        state = m.f[s] * (state / m.total) + slot - m.c[s];
        while (state < L) {
            if (position == packet.size()) throw invalid_argument("TRUNCATED");
            state = RADIX * state + packet[position++];
        }
        symbols.push_back(s);
    }
    if (state != L) throw invalid_argument("FINAL_STATE");
    if (position != packet.size()) throw invalid_argument("TRAILING");
    return symbols;
}
int main() {
    string text = "ABACABADABACABDA";
    vector<int> frequencies = {4, 2, 1, 1}, original;
    for (char ch : text) original.push_back(ch - 'A');
    auto packet = encode(original, frequencies);
    auto decoded = decode(packet, frequencies);
    assert(decoded == original);
    assert(encode(decoded, frequencies) == packet);
    cout << "model=[4,2,1,1]\ntext=" << text << "\npacket=";
    for (size_t i = 0; i < packet.size(); ++i) {
        if (i) cout << ' ';
        cout << uppercase << hex << setw(2) << setfill('0') << packet[i];
    }
    cout << dec << "\ndecoded=";
    for (int s : decoded) cout << char('A' + s);
    cout << "\nbytes=" << packet.size() << " raw=" << original.size() << '\n';
    vector<pair<string, vector<int>>> bad;
    auto truncated = packet; truncated.pop_back();
    bad.emplace_back("truncated", truncated);
    auto trailing = packet; trailing.push_back(0);
    bad.emplace_back("trailing", trailing);
    auto bad_state = packet; bad_state[4] = bad_state[5] = 0;
    bad.emplace_back("bad-state", bad_state);
    for (const auto& test : bad) {
        try { decode(test.second, frequencies); throw logic_error("malformed packet accepted"); }
        catch (const invalid_argument& error) {
            cout << test.first << '=' << error.what() << '\n';
        }
    }
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final int L = 16, RADIX = 256, MAX_SYMBOLS = 100000;
    static class Model {
        int[] f, c, lookup;
        int total;
    }
    static Model make_model(int[] frequencies) {
        if (frequencies == null || frequencies.length < 1 || frequencies.length > 16)
            throw new IllegalArgumentException("MODEL");
        int total = 0;
        for (int f : frequencies) {
            if (f < 1 || f > 16) throw new IllegalArgumentException("MODEL");
            total += f;
        }
        if (total > 16 || (total & (total - 1)) != 0)
            throw new IllegalArgumentException("MODEL");
        Model m = new Model();
        m.f = frequencies.clone(); m.total = total;
        m.c = new int[frequencies.length]; m.lookup = new int[total];
        int start = 0;
        for (int s = 0; s < frequencies.length; ++s) {
            m.c[s] = start;
            for (int j = 0; j < frequencies[s]; ++j) m.lookup[start + j] = s;
            start += frequencies[s];
        }
        return m;
    }
    static int[] integers(List<Integer> values) {
        int[] a = new int[values.size()];
        for (int i = 0; i < a.length; ++i) a[i] = values.get(i);
        return a;
    }
    static int[] encode(int[] symbols, int[] frequencies) {
        Model m = make_model(frequencies);
        if (symbols == null) throw new IllegalArgumentException("SYMBOL");
        if (symbols.length > MAX_SYMBOLS) throw new IllegalArgumentException("COUNT");
        for (int s : symbols)
            if (s < 0 || s >= m.f.length) throw new IllegalArgumentException("SYMBOL");
        int state = L;
        List<Integer> emitted = new ArrayList<>();
        for (int i = symbols.length - 1; i >= 0; --i) {
            int s = symbols[i];
            int threshold = RADIX * (L / m.total) * m.f[s];
            while (state >= threshold) {
                emitted.add(state & 255); state >>= 8;
            }
            state = (state / m.f[s]) * m.total + m.c[s] + state % m.f[s];
        }
        List<Integer> packet = new ArrayList<>();
        for (int j = 0; j < 4; ++j) packet.add((symbols.length >>> (8 * j)) & 255);
        packet.add(state & 255); packet.add(state >> 8);
        for (int j = emitted.size() - 1; j >= 0; --j) packet.add(emitted.get(j));
        return integers(packet);
    }
    static int[] decode(int[] packet, int[] frequencies) {
        Model m = make_model(frequencies);
        if (packet == null) throw new IllegalArgumentException("BYTE");
        if (packet.length > MAX_SYMBOLS + 6) throw new IllegalArgumentException("SIZE");
        for (int b : packet)
            if (b < 0 || b > 255) throw new IllegalArgumentException("BYTE");
        if (packet.length < 6) throw new IllegalArgumentException("TRUNCATED");
        long count = 0;
        for (int j = 0; j < 4; ++j) count += (long)packet[j] << (8 * j);
        if (count > MAX_SYMBOLS) throw new IllegalArgumentException("COUNT");
        int state = packet[4] + 256 * packet[5];
        if (state < L || state >= RADIX * L) throw new IllegalArgumentException("STATE");
        int position = 6;
        List<Integer> symbols = new ArrayList<>();
        for (int i = 0; i < count; ++i) {
            int slot = state % m.total, s = m.lookup[slot];
            state = m.f[s] * (state / m.total) + slot - m.c[s];
            while (state < L) {
                if (position == packet.length) throw new IllegalArgumentException("TRUNCATED");
                state = RADIX * state + packet[position++];
            }
            symbols.add(s);
        }
        if (state != L) throw new IllegalArgumentException("FINAL_STATE");
        if (position != packet.length) throw new IllegalArgumentException("TRAILING");
        return integers(symbols);
    }
    public static void main(String[] args) {
        String text = "ABACABADABACABDA";
        int[] frequencies = {4, 2, 1, 1}, original = new int[text.length()];
        for (int i = 0; i < text.length(); ++i) original[i] = text.charAt(i) - 'A';
        int[] packet = encode(original, frequencies);
        int[] decoded = decode(packet, frequencies);
        if (!Arrays.equals(decoded, original) || !Arrays.equals(encode(decoded, frequencies), packet))
            throw new AssertionError("round trip failed");
        System.out.println("model=[4,2,1,1]");
        System.out.println("text=" + text);
        StringBuilder hex = new StringBuilder(), restored = new StringBuilder();
        for (int b : packet) {
            if (hex.length() != 0) hex.append(' ');
            hex.append("0123456789ABCDEF".charAt(b >>> 4));
            hex.append("0123456789ABCDEF".charAt(b & 15));
        }
        for (int s : decoded) restored.append((char)('A' + s));
        System.out.println("packet=" + hex);
        System.out.println("decoded=" + restored);
        System.out.println("bytes=" + packet.length + " raw=" + original.length);
        String[] labels = {"truncated", "trailing", "bad-state"};
        int[][] bad = new int[3][];
        bad[0] = Arrays.copyOf(packet, packet.length - 1);
        bad[1] = Arrays.copyOf(packet, packet.length + 1);
        bad[2] = packet.clone(); bad[2][4] = bad[2][5] = 0;
        for (int i = 0; i < bad.length; ++i) {
            try {
                decode(bad[i], frequencies);
                throw new AssertionError("malformed packet accepted");
            } catch (IllegalArgumentException error) {
                System.out.println(labels[i] + "=" + error.getMessage());
            }
        }
    }
}

Expected standard output, identical in all three languages:

• model=[4,2,1,1]
• text=ABACABADABACABDA
• packet=10 00 00 00 58 01 59 58 39
• decoded=ABACABADABACABDA
• bytes=9 raw=16
• truncated=TRUNCATED
• trailing=TRAILING
• bad-state=STATE

Complexity, Correctness, and Invariants

Let $K$ be the alphabet size, $M$ the normalized frequency total, $n$ the number of symbols, and $P$ the packet length. Building cumulative starts and the slot table costs $O(K+M)$ time and space. Direct slot lookup gives $O(1)$ symbol selection. A binary search over cumulative intervals could avoid the $M$-entry table at the cost of $O(\log K)$ per decoded symbol.

For this implementation $K,M\le16$, the state remains below $4096$, and renormalization moves at most one byte per symbol. Encoding therefore takes $\Theta(K+M+n)$ time and produces $6\le P\le n+6$ logical bytes. Decoding validates all $P$ byte elements and then performs $n$ symbol steps, taking $\Theta(K+M+P+n)$ time on valid packets. Under the fixed model limits this is $\Theta(P+n+1)$; valid packets also satisfy $P\le n+6$, so it is linear in the message length plus constant setup. A one-symbol model can have no payload bytes even for a long message, but reconstruction still writes $n$ symbols.

Best, average, and worst valid-input work are linear under these fixed bounds; compression ratio has no distribution-free average guarantee. Increasing alphabet size, total frequency precision, state width, or output radix changes setup costs, arithmetic costs, and normalization behavior. These bounds do not imply identical speed across rANS, Huffman, or arithmetic implementations.

The encoder stores a spill list and then a packet, using $O(K+M+P)$ extra space including output. The decoder stores the model and reconstructed symbols, using $O(K+M+n)$ including output, in addition to the input packet. A decoder can stream output with $O(K+M)$ working state if its API allows earlier results; the current API buffers the complete result. Reverse-order encoding means a forward-only source needs block buffering, another representation, or a deliberately designed scheduling method.

The state maps are inverse. Write a pre-map state as $y=f_s q+t$ with $0\le t\lt f_s$. Then $$ C_s(y)=Mq+c_s+t. $$ Since $0\le c_s+t\lt M$, division by $M$ yields quotient $q$ and residue $c_s+t$, which uniquely identifies $s$. The decoder gives $$ D_s(C_s(y))=f_s q+(c_s+t-c_s)=y. $$ The frequency intervals cover every residue exactly once, so symbol selection is unambiguous.

Normalization preserves the interval. Let $k=L/M$, an integer. Immediately before applying $C_s$, the reduced state satisfies $$ kf_s\le y\lt bkf_s. $$ If no byte was spilled, the old normalized state is at least $L\ge kf_s$ and the threshold check supplies the upper bound. If one was spilled, the old state was at least $bkf_s$, so division by $b$ leaves at least $kf_s$; the old state was below $bL$, so the quotient is below $L$. Since thresholds are at least $256$ while that quotient is below $16$, no second spill is needed.

Now $\lfloor y/f_s\rfloor$ lies in $[k,bk)$, and $0\le c_s+(y\bmod f_s)\lt M$. Consequently $$ L\le C_s(y)\lt bL. $$ This proves the normalized-state invariant and also bounds the integer arithmetic. The general threshold derivation depends on $M$ dividing $L$; changing model totals without revisiting it breaks the proof.

A byte spill is reversible. A saved old state has form $x=256y+a$, $0\le a\lt256$. The inverse state map recovers $y$. Exactly when the encoder spilled, $y\lt L$; without a spill it equals the old normalized state and is at least $L$. Thus the decoder's lower-bound check chooses precisely when to read $a$ and reconstruct $x$. Here the inverse state is positive, so one refill from a value below $16$ returns to $[16,4096)$.

The block invariant. Decoder steps undo encoder steps in reverse processing order. Because the encoder visited input indices backward, the popped symbols arrive in original order. Refill bytes must be popped in the same last-in, first-out order as the spills. Induction over all $n$ steps returns the state to its seed and consumes exactly the emitted payload. Therefore decoding an encoded supported message returns the original message. With the model fixed, the terminal and exhaustion checks also make accepted packets reproduce exactly when re-encoded.

For modeled probabilities $q_s$, the ideal information of a message is $\sum_i-\log_2q_{s_i}$. A finite-state coder adds state/rounding and framing costs. If the true distribution is $p$ but the model is $q$, the ideal average model cost is $H(p)+D_{\mathrm{KL}}(p\Vert q)$, assuming every used symbol has positive modeled probability. The divergence is $D_{\mathrm{KL}}(p\Vert q)=\sum_s p_s\log_2(p_s/q_s)$, measured in bits here. Better coding arithmetic cannot compensate for an inaccurate model.

Variants, Pitfalls, and Optimizations

rANS and tabled ANS. rANS uses arithmetic quotient/remainder maps and may use a small residue-to-symbol table as these programs do. That lookup alone does not make it tabled ANS. tANS arranges symbols over a finite state set and precomputes transitions, often replacing arithmetic maps by table lookups and selected bits. FSE is an ANS-based entropy coder using such state tables. RFC 8878's entropy-encoding section specifies FSE and Huffman within Zstandard; this custom rANS packet cannot be substituted for those format components.

State size and frequency normalization. Larger totals represent probabilities more finely but cost table space, while larger normalized states can reduce finite-state redundancy at the cost of wider arithmetic. The teaching limits $M\le16$ and $L=16$ make every step small enough to inspect. Production choices must prove that thresholds, multiplication, and final-state serialization fit their integer widths. Normalize estimated probabilities so the integer frequencies sum exactly to the agreed total. If a used symbol receives zero frequency, add an escape mechanism or change the model before encoding it.

Static, contextual, and adaptive models. A static model is constant for the block, as here. Context models select different distributions based on surrounding data. Their encoder must use exactly the contexts the forward decoder will have; reverse coding does not automatically provide the same context state. Adaptive models that update in forward order likewise require a deliberate reversible or buffered schedule. Training a model on each block also means accounting for how its description reaches the decoder.

Interleaving for speed. Several ANS states can be interleaved to expose independent arithmetic work to a CPU or SIMD lanes. The number of states, symbol-to-state schedule, flush order, and refill order must be specified identically at both ends. Interleaving is a separate implementation design, not permission to reorder the symbols arbitrarily.

Order and off-by-one bugs. Encode the input backward for forward output. Serialize the last spill first. Compare encoder state with the exclusive upper threshold using >=, and compare decoder state with the lower bound using <. The state seed and final state are different roles: the encoder begins at $16$, but the decoder begins at the encoder's final state. Resetting to $16$ at decoder startup loses the encoded information.

Framing and validation. Validate counts before allocating or looping, and check every requested refill. Empty input still has a six-byte header/state packet. A wrong count, wrong model, or changed payload can sometimes produce a different accepted message, so final-state checks do not replace a checksum or other integrity mechanism. Store or identify the frequency model, alphabet order, state parameters, and byte extent in an enclosing format. The current decoder rejects concatenated packets as trailing data; a container must frame and decode them separately.

When to choose another method. A short block may be dominated by model and packet overhead; fixed-bit packing or an existing simple code may be smaller. A forward-only workflow may prefer a range coder or a block strategy. A production compression requirement is usually best served by an established format and implementation. Use this reference to understand and test ANS mechanics, then measure total size, model overhead, decode speed, memory, and access requirements on representative data.

The original ANS paper and Jeremy Gibbons's derivation of ANS coding provide deeper treatments of the mathematical structure and variants. Performance depends on the actual implementation and workload; this overview makes no benchmark ranking.

Practice Problems and Real-World Use

Start with a one-symbol model, then two symbols, then the four-symbol trace. Verify the algebraic inverse independently before optimizing. In addition to round trips, check that every normalized symbol transition stays in range and that the decoder reads a byte exactly when its matching encoder step spilled one.

The accompanying test oracle enumerates each normalized encoded state, determines its symbol and predecessor using the model intervals, and builds an inverse transition dictionary. Its encoder finds valid states by that dictionary rather than copying the implementation's threshold/formula loop. This checks the arithmetic codec from an independently constructed representation.

Across $139$ positive frequency models with totals $1,2,4,8$, all $2448000$ normalized state/symbol transitions were checked for exact inversion and correct byte restoration. The shared program suite has $7830$ encode/decode operation inputs: $7249$ accepted and $581$ rejected. It includes all four-symbol messages through length five under the worked model, all binary messages through length seven under five models, varied total-$16$ models, randomized blocks, packet mutations, empty messages, and $100000$-symbol limits. Python, C++, and Java agree on every complete result and diagnostic label; C++ was also run with address and undefined-behavior sanitizers. Additional Python-only tests reject invalid container and element types.

For application experiments, compare the sample's nine-byte packet with raw ASCII, two-bit packing, and a Huffman payload using the same alphabet. Include whichever headers and model descriptions each real format requires. To study model mismatch, encode a D-heavy message with the A-heavy worked model, then construct and communicate a more suitable model; measure both payload change and model cost rather than just one of them.