zexc 0.1.0

zex native lossless compressor — CLI zexc, library zexc, files *.zex
Documentation
//! Order-0 rANS entropy coder for sequence symbols.
//!
//! Used to pack lit_len / match_len / offset_code streams after they are
//! expanded into byte tokens (0..=255 runs). Smaller and simpler than full
//! Zstd FSE tables, same role: better than raw varints on skewed distributions.

use crate::{Error, Result};

/// Total frequency scale (must be power of two).
const SCALE_BITS: u32 = 12;
const SCALE: u32 = 1 << SCALE_BITS; // 4096
const RANS_BYTE_L: u32 = 1 << 23;

/// Normalized frequencies + cumulative for 256 symbols.
#[derive(Clone, Debug)]
pub struct FseTable {
    /// freq[s] — normalized, sum = SCALE
    pub freq: [u16; 256],
    /// cumul[s] = sum of freq[0..s]
    pub cumul: [u16; 257],
}

impl FseTable {
    /// Build from raw counts (zeros allowed). At least one symbol must appear.
    pub fn from_counts(counts: &[u32; 256]) -> Option<Self> {
        let total: u64 = counts.iter().map(|&c| u64::from(c)).sum();
        if total == 0 {
            return None;
        }

        // Largest-remainder method, each present symbol ≥ 1
        let mut raw: Vec<(usize, u64, u64)> = Vec::new(); // idx, floor, remainder
        let mut present = 0u32;
        for (i, &c) in counts.iter().enumerate() {
            if c == 0 {
                continue;
            }
            present += 1;
            let scaled = c as u64 * SCALE as u64;
            let floor = (scaled / total).max(1);
            let rem = scaled % total;
            raw.push((i, floor, rem));
        }
        if present == 0 || present > SCALE {
            return None;
        }

        let mut freq = [0u16; 256];
        let mut sum: u64 = 0;
        for &(i, floor, _) in &raw {
            freq[i] = floor as u16;
            sum += floor;
        }
        // If over-allocated (many min-1), scale down largest
        while sum > SCALE as u64 {
            let mut best = 0usize;
            let mut best_f = 0u16;
            for &(i, _, _) in &raw {
                if freq[i] > best_f {
                    best_f = freq[i];
                    best = i;
                }
            }
            if freq[best] <= 1 {
                break;
            }
            freq[best] -= 1;
            sum -= 1;
        }
        // Distribute remainder to highest remainders
        if sum < SCALE as u64 {
            let mut order = raw.clone();
            order.sort_by(|a, b| b.2.cmp(&a.2));
            let mut it = 0usize;
            while sum < SCALE as u64 && !order.is_empty() {
                let i = order[it % order.len()].0;
                freq[i] = freq[i].saturating_add(1);
                sum += 1;
                it += 1;
            }
        }

        let mut cumul = [0u16; 257];
        let mut acc = 0u32;
        for i in 0..256 {
            cumul[i] = acc as u16;
            acc += u32::from(freq[i]);
        }
        cumul[256] = SCALE as u16;
        if acc != SCALE {
            return None;
        }
        Some(Self { freq, cumul })
    }

    /// Serialize: 256 × u16 LE frequencies.
    pub fn write_to(&self, out: &mut Vec<u8>) {
        for &f in &self.freq {
            out.extend_from_slice(&f.to_le_bytes());
        }
    }

    /// Deserialize 512 bytes.
    pub fn read_from(data: &[u8]) -> Result<Self> {
        if data.len() < 512 {
            return Err(Error::Decompression("fse table truncated".into()));
        }
        let mut freq = [0u16; 256];
        let mut sum = 0u32;
        for i in 0..256 {
            freq[i] = u16::from_le_bytes([data[i * 2], data[i * 2 + 1]]);
            sum += freq[i] as u32;
        }
        if sum != SCALE {
            return Err(Error::Decompression(format!(
                "fse freq sum {sum} != {SCALE}"
            )));
        }
        let mut cumul = [0u16; 257];
        let mut acc = 0u32;
        for i in 0..256 {
            cumul[i] = acc as u16;
            acc += freq[i] as u32;
        }
        cumul[256] = SCALE as u16;
        Ok(Self { freq, cumul })
    }

    fn symbol_of_cumul(&self, c: u16) -> u8 {
        // Linear search is fine for 256; binary would be faster
        let mut lo = 0usize;
        let mut hi = 256usize;
        while lo + 1 < hi {
            let mid = (lo + hi) / 2;
            if self.cumul[mid] <= c {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        lo as u8
    }
}

/// rANS encode symbols (processed in reverse).
/// Layout: `state:u32 LE` || renorm bytes (forward order for decoder).
pub fn rans_encode(symbols: &[u8], table: &FseTable) -> Vec<u8> {
    if symbols.is_empty() {
        return Vec::new();
    }
    let mut state = RANS_BYTE_L;
    let mut renorm = Vec::with_capacity(symbols.len() + 8);

    for &sym in symbols.iter().rev() {
        let freq = table.freq[sym as usize] as u32;
        let start = table.cumul[sym as usize] as u32;
        debug_assert!(freq > 0, "missing freq for symbol {sym}");
        // Renormalize so state stays bounded
        let x_max = ((RANS_BYTE_L >> SCALE_BITS) << 8) * freq;
        while state >= x_max {
            renorm.push((state & 0xFF) as u8);
            state >>= 8;
        }
        state = ((state / freq) << SCALE_BITS) + (state % freq) + start;
    }

    let mut out = Vec::with_capacity(4 + renorm.len());
    out.extend_from_slice(&state.to_le_bytes());
    // renorm was pushed last-first; reverse for forward read
    for &b in renorm.iter().rev() {
        out.push(b);
    }
    out
}

/// rANS decode `n` symbols.
pub fn rans_decode(data: &[u8], n: usize, table: &FseTable) -> Result<Vec<u8>> {
    if n == 0 {
        return Ok(Vec::new());
    }
    if data.len() < 4 {
        return Err(Error::Decompression("rans stream too short".into()));
    }
    let mut ip = 0usize;
    let mut state = u32::from_le_bytes(data[ip..ip + 4].try_into().unwrap());
    ip += 4;

    let mut out = Vec::with_capacity(n);
    let mask = SCALE - 1;

    for _ in 0..n {
        let slot = (state & mask) as u16;
        let sym = table.symbol_of_cumul(slot);
        let freq = table.freq[sym as usize] as u32;
        let start = table.cumul[sym as usize] as u32;
        if freq == 0 {
            return Err(Error::Decompression("rans bad symbol freq 0".into()));
        }
        state = freq * (state >> SCALE_BITS) + (state & mask) - start;
        out.push(sym);
        while state < RANS_BYTE_L {
            if ip >= data.len() {
                return Err(Error::Decompression("rans truncated".into()));
            }
            state = (state << 8) | u32::from(data[ip]);
            ip += 1;
        }
    }
    Ok(out)
}

/// Expand u32 values to byte tokens: runs of 255 + remainder (like LZ4 extra).
pub fn u32s_to_tokens(vals: &[u32]) -> Vec<u8> {
    let mut t = Vec::with_capacity(vals.len() * 2);
    for &v0 in vals {
        let mut v = v0;
        while v >= 255 {
            t.push(255);
            v -= 255;
        }
        t.push(v as u8);
    }
    t
}

/// Inverse of [`u32s_to_tokens`] for `count` values.
pub fn tokens_to_u32s(tokens: &[u8], count: usize) -> Result<Vec<u32>> {
    let mut out = Vec::with_capacity(count);
    let mut i = 0usize;
    for _ in 0..count {
        let mut v = 0u32;
        loop {
            if i >= tokens.len() {
                return Err(Error::Decompression("token stream short".into()));
            }
            let b = tokens[i];
            i += 1;
            if b == 255 {
                v = v.saturating_add(255);
            } else {
                v = v.saturating_add(b as u32);
                break;
            }
        }
        out.push(v);
    }
    Ok(out)
}

/// Encode a u32 array: table + rans bitstream (len prefixed).
pub fn encode_u32_array(vals: &[u32]) -> Result<Vec<u8>> {
    let tokens = u32s_to_tokens(vals);
    let mut counts = [0u32; 256];
    for &t in &tokens {
        counts[t as usize] += 1;
    }
    let table = FseTable::from_counts(&counts)
        .ok_or_else(|| Error::Compression("empty fse counts".into()))?;
    let stream = rans_encode(&tokens, &table);
    let mut out = Vec::with_capacity(512 + 4 + stream.len());
    table.write_to(&mut out);
    out.extend_from_slice(&(tokens.len() as u32).to_le_bytes());
    out.extend_from_slice(&(stream.len() as u32).to_le_bytes());
    out.extend_from_slice(&stream);
    Ok(out)
}

/// Decode a u32 array previously written by [`encode_u32_array`].
pub fn decode_u32_array(data: &[u8], ip: &mut usize, count: usize) -> Result<Vec<u32>> {
    if *ip + 512 + 8 > data.len() {
        return Err(Error::Decompression("fse array header truncated".into()));
    }
    let table = FseTable::read_from(&data[*ip..*ip + 512])?;
    *ip += 512;
    let ntok = u32::from_le_bytes(data[*ip..*ip + 4].try_into().unwrap()) as usize;
    *ip += 4;
    let nstream = u32::from_le_bytes(data[*ip..*ip + 4].try_into().unwrap()) as usize;
    *ip += 4;
    if *ip + nstream > data.len() {
        return Err(Error::Decompression("fse stream truncated".into()));
    }
    let tokens = rans_decode(&data[*ip..*ip + nstream], ntok, &table)?;
    *ip += nstream;
    tokens_to_u32s(&tokens, count)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn rans_roundtrip() {
        let mut syms = Vec::new();
        for _ in 0..100 {
            syms.extend_from_slice(&[1u8, 1, 1, 2, 2, 3, 0, 0, 0, 0]);
        }
        let mut counts = [0u32; 256];
        for &s in &syms {
            counts[s as usize] += 1;
        }
        let table = FseTable::from_counts(&counts).unwrap();
        let enc = rans_encode(&syms, &table);
        let dec = rans_decode(&enc, syms.len(), &table).unwrap();
        assert_eq!(dec, syms);
    }

    #[test]
    fn u32_array_roundtrip() {
        let vals: Vec<u32> = (0..50).map(|i| i * 3 + 1).collect();
        let blob = encode_u32_array(&vals).unwrap();
        let mut ip = 0;
        let out = decode_u32_array(&blob, &mut ip, vals.len()).unwrap();
        assert_eq!(out, vals);
        assert_eq!(ip, blob.len());
    }
}