Arithmetic coding

Deep dive

How it works

In: a bit and its model probability P(bit = 0) · Out: a byte stream · State: low, range, the pending-carry cache, and the model's probabilities · Cost: O(1) per binary decision

1. Model gives P(bit = 0) as a 11-bit integer p (units of 1/2048).
2. bound = (range >> 11) * p. Bit 0 keeps [low, low+bound); bit 1 keeps [low+bound, low+range).
3. Normalize: while range < 2^24, shift the top byte of low out and range <<= 8. Range stays in [2^24, 2^32).
4. Carry: adding bound to low can overflow into bytes already "emitted". LZMA keeps the last byte plus a count of pending 0xFF bytes in a cache, and releases them once the carry is known.
5. Decoder mirrors it: holds code − low and compares against bound.

range 1.0: [-------------- bit0 p=0.8 ------------|-- bit1 --)
after 0:   [--- 0 ---|-1-)          interval width multiplies by p
bits ≈ Σ -log2(p_i)

Multi-symbol alphabets: either a binary tree of bit models (LZMA codes a byte as 8 binary decisions, context = bits so far), or cumulative frequency tables (AV1 uses CDFs of up to 16 symbols).

Code

LZMA-style adaptive binary range coder plus an order-1 byte model (context = previous byte).

const PROB_BITS: u32 = 11; // probabilities are P(bit = 0) in units of 1/2048
const ONE: u16 = 1 << PROB_BITS;
const MOVE_BITS: u32 = 5; // adaptation rate 1/32
const TOP: u32 = 1 << 24;

pub struct Encoder { low: u64, range: u32, cache: u8, cache_size: u64, out: Vec<u8> }

impl Encoder {
    pub fn new() -> Self { Encoder { low: 0, range: u32::MAX, cache: 0, cache_size: 1, out: Vec::new() } }
    pub fn bit(&mut self, p: &mut u16, bit: u32) {
        let bound = (self.range >> PROB_BITS) * *p as u32;
        if bit == 0 { self.range = bound; *p += (ONE - *p) >> MOVE_BITS; }
        else { self.low += bound as u64; self.range -= bound; *p -= *p >> MOVE_BITS; }
        while self.range < TOP { self.range <<= 8; self.shift_low(); }
    }
    fn shift_low(&mut self) {
        // Emit the top byte unless it is 0xFF (a later carry could still change it).
        if (self.low as u32) < 0xFF00_0000 || (self.low >> 32) != 0 {
            let carry = (self.low >> 32) as u8;
            let mut temp = self.cache;
            loop {
                self.out.push(temp.wrapping_add(carry)); // carry turns pending 0xFF into 0x00
                temp = 0xFF;
                self.cache_size -= 1;
                if self.cache_size == 0 { break; }
            }
            self.cache = (self.low >> 24) as u8;
        }
        self.cache_size += 1;
        self.low = (self.low & 0x00FF_FFFF) << 8;
    }
    pub fn finish(mut self) -> Vec<u8> { for _ in 0..5 { self.shift_low(); } self.out }
}

pub struct Decoder<'a> { code: u32, range: u32, input: &'a [u8], pos: usize }

impl<'a> Decoder<'a> {
    pub fn new(input: &'a [u8]) -> Self {
        let mut d = Decoder { code: 0, range: u32::MAX, input, pos: 0 };
        for _ in 0..5 { d.code = (d.code << 8) | d.next() as u32; } // first byte is always 0
        d
    }
    fn next(&mut self) -> u8 { let b = *self.input.get(self.pos).unwrap_or(&0); self.pos += 1; b }
    pub fn bit(&mut self, p: &mut u16) -> u32 {
        let bound = (self.range >> PROB_BITS) * *p as u32;
        let bit = if self.code < bound {
            self.range = bound; *p += (ONE - *p) >> MOVE_BITS; 0
        } else {
            self.code -= bound; self.range -= bound; *p -= *p >> MOVE_BITS; 1
        };
        while self.range < TOP { self.range <<= 8; self.code = (self.code << 8) | self.next() as u32; }
        bit
    }
}

/// Order-1 model: 256 bit-trees (one per previous byte), 255 nodes each.
pub fn compress(data: &[u8]) -> Vec<u8> {
    let mut probs = vec![ONE / 2; 256 * 256];
    let (mut enc, mut prev) = (Encoder::new(), 0usize);
    for &b in data {
        let tree = &mut probs[prev * 256..][..256];
        let mut node = 1;
        for i in (0..8).rev() {
            let bit = (b >> i) as u32 & 1;
            enc.bit(&mut tree[node], bit);
            node = node * 2 + bit as usize;
        }
        prev = b as usize;
    }
    enc.finish()
}

pub fn decompress(input: &[u8], n: usize) -> Vec<u8> {
    let mut probs = vec![ONE / 2; 256 * 256];
    let (mut dec, mut prev, mut out) = (Decoder::new(input), 0usize, Vec::with_capacity(n));
    for _ in 0..n {
        let tree = &mut probs[prev * 256..][..256];
        let mut node = 1;
        while node < 256 { node = node * 2 + dec.bit(&mut tree[node]) as usize; }
        let b = (node - 256) as u8;
        out.push(b);
        prev = b as usize;
    }
    out
}

Complexity and constants

• Per binary decision: 1 multiply, 1 compare, 1 data-dependent branch (often mispredicted at ~50/50 bits, about 15-20 cycles each), occasional renormalization.
• Precision: with 11-bit probabilities and shift 5, p saturates in [31, 2017]/2048, so a near-certain bit still costs at least −log2(2017/2048) ≈ 0.022 bits. Use 12-16-bit probabilities (or two-rate mixing) for very predictable data.
• 32-bit range with 24-bit normalization threshold: coding loss is negligible (order of 0.01 % or less).
• Memory is all in the model: the order-1 model above is 64 K × 2 bytes = 128 KB; LZMA's literal coder uses 0x300 probs per context.

Efficiency

• Cost: per binary decision one multiply, one compare, one data-dependent branch (about 15-20 cycles when mispredicted on 50/50 bits) and rare renormalization. LZMA decodes at order of 50-150 MB/s per core; context mixing (cmix, PAQ) runs at order of 1-100 KB/s. Model memory: 128 KB for the order-1 model below. Bound: branch misprediction and the serial dependency between bits, not memory bandwidth.
• Levers:
  • multi-symbol CDF coder (AV1, Daala) — fewer coder calls per symbol, alphabets up to 16 — non-binary syntax elements
  • branch-free bit update (mask = 0 - bit) — removes the mispredict penalty — unpredictable 50/50 bits only
  • table instead of multiply (CABAC: 64 x 4 table) — no multiplier needed — hardware and low-power decoders
  • split input into independent blocks — more cores, resets the model and costs some ratio — large inputs
  • ANS instead of the arithmetic coder — faster, SIMD-friendly decode — static per-block statistics
• Naive → standard → state of the art:
  • whole-bit Huffman codes · at least 1 bit per symbol (a p = 0.99 symbol costs 1 bit instead of 0.015)
  • adaptive binary range coder with an 11-bit model (LZMA, CABAC) · one multiply and one branch per bit, order of 50-150 MB/s decode
  • context mixing for ratio (cmix, PAQ), ANS where speed matters · order of 1-100 KB/s (cmix); ANS decodes faster

Implementation notes

• Branch-free update: compute mask = 0 - bit and select with &/|; helps on 50/50 bits, hurts on predictable ones (where the branch predicts well).
• Adaptation rate: shift 4 adapts fast, shift 7 is precise for stationary data. Many modern coders mix two rates: p = (p_fast + p_slow) / 2.
• Multiplication-free variants (CABAC) replace range * p by a 64 × 4 lookup table on quantized range and a 6-bit probability state.
• Context mixing (PAQ, cmix): several models predict, a small online neural net mixes them in the logistic domain, then the range coder codes the bit. Best ratios known, at order of 1-100 KB/s.
• End of stream: store the symbol count or reserve an EOF symbol; the decoder reads up to 4 bytes past the real end (pad or bounds-check).

Pitfalls

• Forgetting carry propagation: output is wrong only when a run of 0xFF bytes meets a carry, so tests on small inputs pass.
• Encoder and decoder updating the model in different order (or the decoder updating with stale context): instant desync, garbage from that point on.
• Probabilities reaching 0 or ONE: bound becomes 0 or range, and the interval collapses. Clamp.
• Decoding is serial; to use more cores, split the input into independent blocks (resets the model, costs some ratio).

Variants and alternatives

In production

Archives: LZMA/xz/7-Zip, PAQ/cmix context-mixing compressors. Video and images: H.264/HEVC/VVC CABAC, AV1 (multi-symbol coder from Daala), JPEG arithmetic mode, JBIG2, and Dropbox Lepton, which recompresses JPEGs losslessly with an adaptive arithmetic coder to cut file-storage volume (NSDI 2017). Genomics: the CRAM 3.1 specification defines range/arithmetic-coded codecs for streams such as read names and quality values.

Implementations

Sources

• J. Rissanen, Generalized Kraft Inequality and Arithmetic Coding, IBM J. Research and Development, 1976. paper
• G. N. N. Martin, Range encoding: an algorithm for removing redundancy from a digitised message, Video & Data Recording Conference, 1979.
• I. H. Witten, R. M. Neal, J. G. Cleary, Arithmetic Coding for Data Compression, CACM, 1987. paper
• A. Moffat, R. M. Neal, I. H. Witten, Arithmetic Coding Revisited, ACM TOIS, 1998. paper
• D. Marpe, H. Schwarz, T. Wiegand, Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard, IEEE TCSVT, 2003. paper
• CRAM codecs specification (CRAM 3.1), GA4GH/samtools hts-specs. spec
• Horn et al., The Design, Implementation, and Deployment of a System to Transparently Compress Hundreds of Petabytes of Image Files for a File-Storage Service, NSDI 2017. paper