Asymmetric numeral systems (ANS)

Deep dive

How it works

In: symbols with a frequency table (f_s, c_s; M = 2^R) · Out: a byte stream, decoded in the opposite order from encoding · State: one integer x (several when interleaved) · Cost: O(1) per symbol

rANS with M = 2^R total frequency, symbol s has frequency f_s and cumulative start c_s:

1. Encode (symbols in reverse): renormalize first, pushing low bytes while x ≥ x_max(s), so the result stays in range. Then x = (x / f_s)·M + (x mod f_s) + c_s.
2. Decode: slot = x mod M; the symbol s is the one with c_s ≤ slot < c_s + f_s (table lookup); x = f_s·(x / M) + slot − c_s; then pull bytes while x < L.
3. Invariant: x ∈ [L, 256·L) with L = 2^23 for byte-wise I/O and a 32-bit state.
4. The encoder's final state is written first; the decoder starts from it.

encode a b c  (reverse: c, b, a) ──► x_final ──► decoder pops a, b, c
x grows by log2(M/f) bits per symbol; bytes leave from the bottom

tANS precomputes, for each of 2^R states, the decoded symbol, how many bits to read, and the next-state base. The spread of symbols over states (FSE uses a step of (5/8)·size + 3) sets the effective probabilities.

Code

Byte-wise rANS with a static 12-bit model (after Giesen's ryg_rans).

const SCALE_BITS: u32 = 12; // frequencies sum to M = 4096
const M: u32 = 1 << SCALE_BITS;
const L: u32 = 1 << 23; // state stays in [L, 256 * L)

pub struct Model { freq: [u32; 256], cum: [u32; 256], slot: Vec<u8> } // slot: M entries -> symbol

impl Model {
    pub fn new(counts: &[u64; 256]) -> Model {
        let total: u64 = counts.iter().sum::<u64>().max(1);
        let mut freq = [0u32; 256];
        for s in 0..256 {
            if counts[s] > 0 { freq[s] = ((counts[s] * M as u64 / total) as u32).max(1); }
        }
        let mut sum: u32 = freq.iter().sum();
        while sum != M && sum > 0 { // fix rounding drift on the most frequent symbol
            let s = (0..256).max_by_key(|&s| freq[s]).unwrap();
            if sum > M { freq[s] -= 1; sum -= 1; } else { freq[s] += 1; sum += 1; }
        }
        let (mut cum, mut slot, mut c) = ([0u32; 256], vec![0u8; M as usize], 0u32);
        for s in 0..256 {
            cum[s] = c;
            slot[c as usize..(c + freq[s]) as usize].fill(s as u8);
            c += freq[s];
        }
        Model { freq, cum, slot }
    }
}

pub fn encode(data: &[u8], m: &Model) -> Vec<u8> {
    let mut out = Vec::with_capacity(data.len() + 4);
    let mut x = L;
    for &s in data.iter().rev() { // LIFO: encode backwards so decoding runs forwards
        let (f, c) = (m.freq[s as usize], m.cum[s as usize]);
        let x_max = ((L >> SCALE_BITS) << 8) * f;
        while x >= x_max { out.push(x as u8); x >>= 8; }
        x = ((x / f) << SCALE_BITS) + (x % f) + c;
    }
    for i in (0..4).rev() { out.push((x >> (8 * i)) as u8); }
    out.reverse(); // final state first (little-endian), then spilled bytes in pop order
    out
}

pub fn decode(input: &[u8], n: usize, m: &Model) -> Vec<u8> {
    let mut x = u32::from_le_bytes(input[..4].try_into().unwrap());
    let mut pos = 4;
    (0..n).map(|_| {
        let low = x & (M - 1);
        let s = m.slot[low as usize];
        x = m.freq[s as usize] * (x >> SCALE_BITS) + low - m.cum[s as usize];
        while x < L { x = (x << 8) | input[pos] as u32; pos += 1; } // validate pos on untrusted input
        s
    }).collect()
}

Complexity and constants

• Decode per symbol: 1 table load (4 KB slot table fits L1), 1 multiply, 0-2 byte reads. The dependency chain through x is order of 5-10 cycles, so throughput comes from interleaving.
• Encode needs a division by f; replace it with a precomputed reciprocal multiply-shift (ryg_rans RansEncSymbol) for order of 2x faster encoding.
• Precision: probabilities are quantized to 1/M. With M = 4096 the loss is typically well under 1 %; rare symbols forced to f = 1 pay the most.
• tANS table: 2^R entries of ~4 bytes. zstd uses accuracy logs of at most 9 (literal and match lengths) and 8 (offset codes): 1-2 KB tables, cheap to rebuild per block.

Efficiency

• Cost: per symbol one table load (4 KB slot table, fits L1), one multiply and 0-2 byte reads. The dependency chain through x is order of 5-10 cycles, so speed comes from interleaving: scalar decode order of 0.5-1 GB/s, interleaved SIMD states several GB/s. Encode needs a division by f. Memory: 1-2 KB of tables per block in zstd. Bound: latency of the single-state dependency chain, then compute.
• Levers:
  • interleave 2 states — roughly 2x scalar decode (Giesen, arXiv:1402.3392) — any rANS decoder
  • 4-32 interleaved states in SIMD lanes — several GB/s — large blocks
  • reciprocal multiply-shift instead of division — order of 2x faster encode (ryg_rans) — encoder
  • 64-bit state, 32-bit renormalization — at most one read per symbol, no inner loop — rANS
  • alias method — 2-entry bucket instead of an M-entry slot table — large alphabets
• Naive → standard → state of the art:
  • Huffman · 1-3 % larger on typical literals, multi-symbol table decode
  • scalar rANS or tANS (FSE) · order of 0.5-1 GB/s decode
  • interleaved SIMD rANS · several GB/s decode

Implementation notes

• Interleave states: 2 states alternating symbols (even/odd) roughly doubles scalar decode speed; 4-32 states map to SIMD lanes (Giesen, Interleaved entropy coders). All states share one byte stream if renormalization order is preserved.
• Bigger I/O units: 64-bit state with 32-bit renormalization (L = 2^31) does at most one read per symbol, removing the inner loop branch.
• Alias method lets the decoder find the symbol with a 2-entry bucket instead of an M-entry slot table, good for large alphabets.
• Encoder buffering: you must know the whole block before encoding (reverse order); zstd encodes sequences backward over a 128 KB block.
• Header: transmit normalized frequencies (FSE header uses a compact variable-bit scheme), or use predefined tables for small blocks.

Pitfalls

• Frequencies not summing to exactly M, or a present symbol with f = 0: silent corruption or division by zero.
• Off-by-one in renormalization bounds: x must satisfy L ≤ x < 256·L at every step; check with random tests at the extremes (a symbol with f = 1, one with f = M − 1).
• Forgetting the LIFO order and emitting symbols forward: decode comes out reversed.
• Reading past the input end on corrupt data; bounds-check pos in production decoders.
• Adaptive models: the encoder must replay the model backwards; usually you buffer probabilities forward, then encode in reverse.

Variants and alternatives

In production

Storage and OS: zstd (FSE for literal-length, match-length and offset codes; RFC 8878), Apple LZFSE, Linux kernel via zstd. Images and 3D: JPEG XL, Google Draco mesh compression. Genomics: CRAM 3.x (rANS 4x8 and 4x16 in htslib).

Implementations

Sources

• J. Duda, Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, arXiv:1311.2540, 2013. paper
• F. Giesen, Interleaved entropy coders, arXiv:1402.3392, 2014. paper · code
• Y. Collet, M. Kucherawy, RFC 8878: Zstandard Compression and the 'application/zstd' Media Type, 2021. RFC
• CRAM codecs specification (CRAM 3.1: rANS 4x8, rANS Nx16), GA4GH/samtools hts-specs. spec
• Y. Collet, Finite State Entropy (FSE reference implementation). code