ans

Asymmetric Numeral Systems (rANS) entropy coding primitives.

Small, pure-Rust, no_std-capable rANS with both batch and streaming APIs.

Batch API

use ans::{decode, encode, FrequencyTable};

let counts = [10u32, 20, 70]; // A, B, C
let table = FrequencyTable::from_counts(&counts, 14)?;
let message = [0u32, 2, 1, 2, 2, 0];

let bytes = encode(&message, &table)?;
let back = decode(&bytes, &table, message.len())?;
assert_eq!(back, message);

# Ok::<(), ans::AnsError>(())

Streaming API

Symbol-at-a-time encoding/decoding. Required for bits-back coding (BB-ANS, ROC).

use ans::{RansEncoder, RansDecoder, FrequencyTable};

let table = FrequencyTable::from_counts(&[3, 7], 12)?;
let message = [0u32, 1, 1, 0, 1];

// Encode in reverse order (rANS requirement).
let mut enc = RansEncoder::new();
for &sym in message.iter().rev() {
    enc.put(sym, &table)?;
}
let bytes = enc.finish();

// Decode in forward order.
let mut dec = RansDecoder::new(&bytes)?;
let mut decoded = Vec::new();
for _ in 0..message.len() {
    decoded.push(dec.get(&table)?);
}
assert_eq!(decoded, message);

# Ok::<(), ans::AnsError>(())

Bits-back primitives

RansDecoder::peek and RansDecoder::advance allow inspecting the decoded slot before advancing state, which is the key operation for bits-back coding:

# use ans::{RansEncoder, RansDecoder, FrequencyTable};
# let table = FrequencyTable::from_counts(&[3, 7], 12)?;
# let bytes = ans::encode(&[0u32, 1], &table)?;
let mut dec = RansDecoder::new(&bytes)?;
let sym = dec.peek(&table);       // look at slot without advancing
dec.advance(sym, &table)?;        // advance after external logic
# Ok::<(), ans::AnsError>(())

no_std

This crate is no_std by default (requires alloc). The std feature is enabled by default for convenience but can be disabled:

[dependencies]
ans = { version = "0.1.0", default-features = false }

Notes

• Encoding returns a byte vector in a stack format: decoding consumes bytes from the end.
• This crate is focused on correctness and integration simplicity (not maximum throughput).

Choosing precision_bits

FrequencyTable::from_counts(counts, precision_bits) builds a model with total mass (T = 2^{precision_bits}). Practical guidance:

• Larger precision_bits approximates the empirical distribution more closely (less quantization), but increases memory and can slow decoding.
• Typical ranges are ~12–16 for small alphabets.

Memory footprint

The table stores sym_by_slot of length (T), mapping each slot to a symbol. This dominates:

• Approx size (\approx 4 \cdot 2^{precision_bits}) bytes (u32 per slot), plus cdf/freqs.
• Example: precision_bits = 14 → (2^{14} = 16384) slots → ~64 KiB for sym_by_slot.

Security / robustness

This is an entropy coder, not encryption. Do not treat it as a cryptographic primitive.

License

MIT OR Apache-2.0