Introduction

Every file you compress is a string of symbols — letters, bytes, pixel values — each appearing with some frequency. Information theory says the shortest possible encoding assigns each symbol a code of length −log⁡2(p)\log_{2}(p) bits, where p is its probability. That limit is called Shannon entropy, and reaching it has always been the holy grail of lossless compression.

For decades the two ways to approach the limit were Huffman coding (fast but stuck to integer bit lengths, losing a little per symbol) and arithmetic coding (near-perfect but painfully slow on real hardware). In 2009 Jarek Duda published a radically different idea: instead of assigning bit patterns, fold every symbol directly into one giant integer called the state. The technique is Asymmetric Numeral Systems (ANS).

ANS encodes an entire message as a single number, then decodes that number back into the original symbols — in reverse order, like unwinding a stack. The encoder grows the state with each symbol; the decoder shrinks it. The key insight is that the state grows at a rate that precisely mirrors the symbol's probability, so the total bits used per symbol converges to the Shannon entropy without any of the bookkeeping overhead that makes arithmetic coding slow.

Two practical variants dominate modern software:

  • rANS (range ANS) — arithmetically exact, works in streaming blocks, used inside zstd's entropy kernel.
  • tANS (table ANS) — precomputes every transition into two lookup tables; a single table read encodes or decodes one symbol, making it exceptionally fast on CPUs.

Today ANS is the entropy coder inside zstd (Facebook/Meta), LZFSE (Apple), Brotli's entropy layer, and many GPU-accelerated codecs. It compresses at speeds previously associated only with simple byte-copy operations, while achieving ratios that once required heavy arithmetic coding.

Try It: Watch the State Grow

The demo below runs a simplified rANS encoder on a small alphabet. Type a message using the symbols A, B, and C, then press Encode to watch the state integer absorb each symbol. Each step shows how the state changes and how many bits it costs. Press Decode to unwind the state and recover the original message.

<div class="controls">
  <label>Message (use A, B, C only):
    <input id="msg" type="text" value="AABAC" maxlength="12" spellcheck="false" autocomplete="off">
  </label>
  <div class="btns">
    <button id="encBtn" type="button">Encode</button>
    <button id="decBtn" type="button" disabled>Decode</button>
    <button id="resetBtn" type="button" class="ghost">Reset</button>
  </div>
</div>
<div id="freqBox" class="freq-box"></div>
<div id="log" class="log"></div>
<div id="summary" class="summary"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
label { display: block; font-weight: 600; margin-bottom: .4rem; }
input { font: 600 15px ui-monospace, monospace; padding: .35rem .6rem; border: 1px solid #adb1b8;
        border-radius: 7px; width: 200px; letter-spacing: .08em; text-transform: uppercase; }
.btns { display: flex; gap: .45rem; margin-top: .55rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .38rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.freq-box { display: flex; gap: .6rem; margin: .7rem 0 .5rem; flex-wrap: wrap; }
.freq-chip { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 7px;
             padding: .25rem .6rem; font: 600 13px ui-monospace, monospace; color: #1d3557; }
.log { font: 13px ui-monospace, monospace; background: #f5f7fa; border: 1px solid #d6dde3;
       border-radius: 8px; padding: .6rem .8rem; max-height: 220px; overflow-y: auto;
       display: none; line-height: 1.6; }
.log.visible { display: block; }
.log .step { color: #444; }
.log .step span { color: #1d3557; font-weight: 700; }
.log .step .sym { color: #c92f3c; }
.log .step .cost { color: #0a7d33; font-size: .92em; }
.log .sep { border: none; border-top: 1px dashed #cdd9e3; margin: .35rem 0; }
.summary { margin-top: .6rem; font-size: .92rem; font-weight: 600; min-height: 1.4em; }
.summary.ok { color: #0a7d33; }
.summary.bad { color: #c92f3c; }
.controls { margin-bottom: .3rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Simplified rANS (Range Asymmetric Numeral Systems) demo.
// Alphabet: A, B, C with frequencies 4, 2, 1 (sum M=7).
// Encoding: x' = floor(x / fs) * M + (x mod fs) + CUM[s]
// Decoding: s = symbol_at(x mod M), x = fs * floor(x/M) + (x mod M) - CUM[s]
// Renormalisation keeps x in [M, 2M-1] before each encode step
// (we flush one bit when needed so x stays manageable for the demo).

const SYMS = ['A','B','C'];
const FREQ = { A: 4, B: 2, C: 1 };
const M = 7; // total frequency
const CUM  = { A: 0, B: 4, C: 6 }; // cumulative frequencies

// Build decode table: for each remainder r in [0,M), which symbol?
// r in [CUM[s], CUM[s]+FREQ[s]) => symbol s
function symAt(r) {
  for (const s of SYMS) if (r >= CUM[s] && r < CUM[s] + FREQ[s]) return s;
  return null;
}

let encodedState = null;
let encodedBits  = [];
let originalMsg  = '';

function showFreq(msg) {
  const box = document.getElementById('freqBox');
  const counts = { A: 0, B: 0, C: 0 };
  for (const ch of msg.toUpperCase()) if (ch in counts) counts[ch]++;
  const total = Object.values(counts).reduce((a,b)=>a+b, 0) || 1;
  box.innerHTML = SYMS.map(s => {
    const p = (counts[s] / total * 100).toFixed(0);
    const ideal = counts[s] > 0 ? (Math.log2(total/counts[s])).toFixed(2) : '—';
    return fmt('<span class="freq-chip">%s%: %v%/%total% · ideal %ideal% bits</span>', { s: s, v: counts[s], total: total, ideal: ideal });
  }).join('');
}

function encode() {
  const raw = document.getElementById('msg').value.toUpperCase().replace(/[^ABC]/g,'');
  if (!raw) { setSummary('Use only A, B, C.', 'bad'); return; }
  originalMsg = raw;
  showFreq(raw);

  const log = document.getElementById('log');
  log.innerHTML = '';
  log.classList.add('visible');

  let x = M; // initial state in renorm range
  const bits = []; // flushed bits (LSB first)

  addLog(log, fmt('<div class="step">Initial state: <span>%x%</span></div>', { x: x }));
  addLog(log, `<hr class="sep">`);

  for (const sym of raw) {
    const fs = FREQ[sym];
    // Renormalise: if x >= fs*2, flush bits until x < fs*2
    while (x >= fs * 2) {
      bits.push(x & 1);
      x >>= 1;
    }
    const xBefore = x;
    // ANS encode step
    x = Math.floor(x / fs) * M + (x % fs) + CUM[sym];
    const bitsUsed = Math.log2(x / xBefore).toFixed(3);
    addLog(log, fmt('<div class="step">Encode <span class="sym">%sym%</span> (f=%fs%/7): <span>%xBefore%</span> → <span>%x%</span> <span class="cost">(~%bitsUsed% bits)</span></div>', { sym: sym, fs: fs, xBefore: xBefore, x: x, bitsUsed: bitsUsed }));
  }

  addLog(log, `<hr class="sep">`);
  addLog(log, fmt('<div class="step">Final state: <span>%x%</span>  |  Flushed bits: <span>%length%</span></div>', { x: x, length: bits.length }));

  const totalBits = Math.ceil(Math.log2(x + 1)) + bits.length;
  const idealBits = raw.split('').reduce((acc, s) => acc + Math.log2(M / FREQ[s]), 0).toFixed(2);
  addLog(log, fmt('<div class="step">Total bits ≈ <span>%totalBits%</span>  |  Ideal (entropy) ≈ <span>%idealBits%</span></div>', { totalBits: totalBits, idealBits: idealBits }));

  encodedState = x;
  encodedBits  = bits;
  setSummary(fmt('✓ Encoded ""%raw%"" → state=%x%. Press Decode to verify.', { raw: raw, x: x }), 'ok');
  document.getElementById('decBtn').disabled = false;
}

function decode() {
  if (encodedState === null) return;
  let x = encodedState;
  const bits = [...encodedBits]; // copy, we'll pop from end (it was pushed LSB-first)
  const decoded = [];

  const log = document.getElementById('log');
  log.innerHTML = '';
  log.classList.add('visible');

  addLog(log, fmt('<div class="step">Starting decode from state: <span>%x%</span></div>', { x: x }));
  addLog(log, `<hr class="sep">`);

  for (let i = 0; i < originalMsg.length; i++) {
    const r = x % M;
    const sym = symAt(r);
    const fs = FREQ[sym];
    const xBefore = x;
    // ANS decode step (inverse of encode)
    x = fs * Math.floor(x / M) + r - CUM[sym];
    addLog(log, fmt('<div class="step">Decode step %v%: r=<span>%r%</span> → <span class="sym">%sym%</span>, state <span>%xBefore%</span> → <span>%x%</span></div>', { v: i+1, r: r, sym: sym, xBefore: xBefore, x: x }));
    decoded.push(sym);
    // Renorm: restore bits that were flushed (reverse order)
    while (x < M && bits.length > 0) {
      x = (x << 1) | bits.pop();
    }
  }

  addLog(log, `<hr class="sep">`);
  const result = decoded.reverse().join('');
  addLog(log, fmt('<div class="step">Decoded (reversed): <span>%result%</span></div>', { result: result }));

  if (result === originalMsg) {
    setSummary(fmt('✓ Perfect round-trip: ""%result%"" matches the original.', { result: result }), 'ok');
    console.log('ANS round-trip OK:', result);
  } else {
    setSummary(fmt('✗ Mismatch: got ""%result%"", expected ""%originalMsg%"".', { result: result, originalMsg: originalMsg }), 'bad');
    console.error('ANS round-trip FAIL:', result, '!=', originalMsg);
  }
}

function addLog(container, html) {
  const div = document.createElement('div');
  div.innerHTML = html;
  container.appendChild(div.firstChild);
}

function setSummary(text, cls) {
  const s = document.getElementById('summary');
  s.textContent = text; s.className = 'summary ' + cls;
}

function reset() {
  encodedState = null; encodedBits = []; originalMsg = '';
  document.getElementById('log').classList.remove('visible');
  document.getElementById('log').innerHTML = '';
  document.getElementById('freqBox').innerHTML = '';
  document.getElementById('decBtn').disabled = true;
  setSummary('', '');
}

document.getElementById('encBtn').addEventListener('click', encode);
document.getElementById('decBtn').addEventListener('click', decode);
document.getElementById('resetBtn').addEventListener('click', reset);
document.getElementById('msg').addEventListener('input', function() {
  this.value = this.value.toUpperCase().replace(/[^ABC]/g,'');
});
showFreq('AABAC');
Result
Console

Notice three things. First, the state grows multiplicatively — it never just shifts bits. Second, high-frequency symbols (A is most common) cause smaller jumps than rare ones (C), matching the Shannon cost −log⁡2(p)\log_{2}(p). Third, decoding is just the inverse arithmetic, perfectly reversible with no wasted bits. This is what separates ANS from Huffman: there are no rounding gaps.

The Real Complexity

Why does ANS work so much better than Huffman, and so much faster than arithmetic coding?

Huffman's ceiling. Huffman coding must assign whole numbers of bits to each symbol. A symbol with probability 0.3 needs log⁡2(1/0.3)\log_{2}(1/0.3) ≈ 1.74 bits, but Huffman rounds to 2 bits — a 15% waste. Over millions of symbols this gap accumulates.

Arithmetic coding's floor. Arithmetic coding represents the entire message as a fraction in [0, 1), updating the interval with each symbol. It reaches the entropy limit exactly but requires multi-precision integer arithmetic and careful management of carry propagation, making it roughly 3–5× slower than table-based methods.

ANS's sweet spot. Instead of a fraction, ANS uses one positive integer x (the state). Encoding symbol s with probability p_s = f_s / M (where M is the total symbol count in a frequency table) transforms the state by:

x′=⌊xfs⌋×M+(x mod fs)+cumulative_freq(s)x' = \left\lfloor \frac{x}{f_s} \right\rfloor \times M + (x \bmod f_s) + \text{cumulative\_freq}(s)

This is asymmetric because different symbols produce different-sized jumps — hence the name. The state grows at an average rate of −log⁡2(ps)-\log_{2}(p_s) bits per symbol, which is exactly the Shannon cost. When the state's bit-length reaches a threshold, the encoder flushes one or two bits to an output buffer to keep x in a working range. This "renormalisation" step replaces the carry arithmetic of arithmetic coding with simple bit-shifts, which modern CPUs execute in a single clock cycle.

Complexity class. ANS encoding and decoding are both O(n)O(n) in the message length — strictly linear time. The compression problem itself is polynomial (we can always achieve the entropy limit in O(n)O(n) time given the symbol frequencies). What ANS solved was not a hardness barrier but an engineering one: matching the theory's bit budget on real CPUs without multi-precision arithmetic.

Where It Matters

ANS has quietly become the entropy layer of the modern internet:

  • zstd (Zstandard): Facebook/Meta's general-purpose compressor uses rANS as its entropy coder. At compression level 3 it is faster than gzip while producing smaller files. Linux kernel, Python, and Firefox all ship zstd.
  • LZFSE: Apple's in-house compressor (used on iOS and macOS backups) uses tANS. The table-lookup design is particularly friendly to mobile CPUs with limited instruction throughput.
  • Brotli: Google's web-compression format uses a hybrid: ANS-style entropy coding on top of an LZ77 back-reference scheme. It is mandatory in HTTP/2 header compression (HPACK) and widely deployed across CDNs.
  • Image and video codecs: AV1 (the royalty-free video standard), JPEG XL, and AVIF all use ANS variants in their entropy layers, enabling better-than-JPEG quality at smaller file sizes.
  • GPU and hardware codecs: The parallelism-friendly structure of tANS (each lookup is independent once the state is in range) maps well onto GPU streaming multiprocessors, enabling real-time compression of game textures and video streams.

Learn how ANS works and you understand the entropy layer beneath almost every piece of data you transfer today — related ideas appear in information-theoretic compression and the probabilistic reasoning of Bayesian inference.

Conclusion

For fifty years, compressors faced a cruel trade-off: be fast (Huffman) or be optimal (arithmetic coding). Jarek Duda's ANS dissolved the dilemma in 2009 by finding a new way to think about the state — not a fraction but an integer, grown and shrunk by multiplicative steps that mirror each symbol's probability.

The result is a coder that reaches the Shannon entropy limit while running at table-lookup speed — a combination that was considered impossible until it existed. Today virtually every byte you save to a modern device or send across the internet passes through an ANS entropy coder, usually invisibly. The state absorbs your data symbol by symbol, and the bits fall out just as theory says they must — no more, no less.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/asymmetric-numeral-systems/Content licensed under CC BY-NC 4.0.