zexc 1.2.1

zex native lossless compressor — CLI zexc, library zexc, files *.zex
Documentation
//! Canonical Huffman coding for the high-ratio (Zstd-style) backend.
//!
//! Codes are emitted **MSB-first** (same convention as DEFLATE / Zstd HUF).
//! The underlying [`BitWriter`] is LSB-first on the wire, so each code is
//! bit-reversed when written/read to keep a simple LE bit container.

use alloc::vec::Vec;

use crate::utils::bitstream::{BitReader, BitWriter};
use crate::{Error, Result};

const MAX_SYMBOLS: usize = 256;
const MAX_BITS: u32 = 15;

/// Huffman encode table.
#[derive(Clone, Debug)]
pub struct HuffEncoder {
    /// Bit-reversed codes ready for LSB-first [`BitWriter`].
    codes: [u32; MAX_SYMBOLS],
    lens: [u8; MAX_SYMBOLS],
    max_bits: u32,
}

impl Default for HuffEncoder {
    fn default() -> Self {
        Self {
            codes: [0; MAX_SYMBOLS],
            lens: [0; MAX_SYMBOLS],
            max_bits: 0,
        }
    }
}

/// Huffman decode table (lookup on next `max_bits`, MSB-first semantics).
#[derive(Clone, Debug)]
pub struct HuffDecoder {
    /// table[peek] = (symbol, bit_length)
    table: Vec<(u8, u8)>,
    max_bits: u32,
}

/// Reverse the low `len` bits of `code`.
#[inline]
fn reverse_bits(mut code: u32, len: u32) -> u32 {
    let mut r = 0u32;
    for _ in 0..len {
        r = (r << 1) | (code & 1);
        code >>= 1;
    }
    r
}

/// Build encoder from symbol frequencies.
pub fn build_encoder(freq: &[u32; MAX_SYMBOLS]) -> Option<HuffEncoder> {
    let mut leaves: Vec<(u32, u16)> = Vec::new();
    for (sym, &f) in freq.iter().enumerate() {
        if f > 0 {
            leaves.push((f, sym as u16));
        }
    }
    if leaves.is_empty() {
        return None;
    }
    if leaves.len() == 1 {
        let mut enc = HuffEncoder::default();
        let s = leaves[0].1 as usize;
        // 1-bit code 0, reversed is still 0
        enc.codes[s] = 0;
        enc.lens[s] = 1;
        enc.max_bits = 1;
        return Some(enc);
    }

    // --- Huffman tree via binary heap (min-freq) ---
    #[derive(Clone, Copy)]
    struct Node {
        freq: u32,
        /// >=0 child index; <0 => leaf with symbol = !left
        left: i32,
        right: i32,
    }

    let mut nodes: Vec<Node> = Vec::new();
    // heap of node indices sorted by (freq, index) for stability
    let mut heap: Vec<usize> = Vec::new();

    let less = |nodes: &[Node], a: usize, b: usize| -> bool {
        nodes[a].freq < nodes[b].freq || (nodes[a].freq == nodes[b].freq && a < b)
    };

    let heap_push = |heap: &mut Vec<usize>, nodes: &[Node], idx: usize| {
        heap.push(idx);
        let mut i = heap.len() - 1;
        while i > 0 {
            let p = (i - 1) / 2;
            if !less(nodes, heap[i], heap[p]) {
                break;
            }
            heap.swap(p, i);
            i = p;
        }
    };

    let heap_pop = |heap: &mut Vec<usize>, nodes: &[Node]| -> Option<usize> {
        if heap.is_empty() {
            return None;
        }
        let res = heap[0];
        let last = heap.pop().unwrap();
        if !heap.is_empty() {
            heap[0] = last;
            let mut i = 0;
            loop {
                let l = 2 * i + 1;
                let r = 2 * i + 2;
                let mut s = i;
                if l < heap.len() && less(nodes, heap[l], heap[s]) {
                    s = l;
                }
                if r < heap.len() && less(nodes, heap[r], heap[s]) {
                    s = r;
                }
                if s == i {
                    break;
                }
                heap.swap(i, s);
                i = s;
            }
        }
        Some(res)
    };

    for &(f, s) in &leaves {
        let idx = nodes.len();
        nodes.push(Node {
            freq: f,
            left: !(s as i32),
            right: -1,
        });
        heap_push(&mut heap, &nodes, idx);
    }

    while heap.len() > 1 {
        let a = heap_pop(&mut heap, &nodes).unwrap();
        let b = heap_pop(&mut heap, &nodes).unwrap();
        let idx = nodes.len();
        nodes.push(Node {
            freq: nodes[a].freq.saturating_add(nodes[b].freq),
            left: a as i32,
            right: b as i32,
        });
        heap_push(&mut heap, &nodes, idx);
    }

    let root = heap[0];
    let mut lens = [0u8; MAX_SYMBOLS];

    fn walk(nodes: &[Node], idx: usize, depth: u8, lens: &mut [u8; MAX_SYMBOLS]) {
        let n = nodes[idx];
        if n.left < 0 {
            let sym = (!n.left) as usize;
            // Cap depth; rare path for pathological trees
            lens[sym] = depth.max(1).min(MAX_BITS as u8);
            return;
        }
        let d = depth.saturating_add(1).min(MAX_BITS as u8 + 1);
        walk(nodes, n.left as usize, d, lens);
        if n.right >= 0 {
            walk(nodes, n.right as usize, d, lens);
        }
    }
    walk(&nodes, root, 0, &mut lens);

    // If any length hit the cap, rebuild lengths with a simple package-style
    // renormalize: sort by freq and assign balanced lengths (fallback).
    if lens.contains(&(MAX_BITS as u8)) {
        // Verify kraft; if over-subscribed, force equalish lengths
        let mut kraft = 0u32;
        for &l in &lens {
            if l > 0 {
                kraft += 1u32 << (MAX_BITS - l as u32);
            }
        }
        if kraft > (1u32 << MAX_BITS) {
            // Fallback: fixed length ceil(log2(n_symbols))
            let nsym = leaves.len().next_power_of_two().trailing_zeros().max(1) as u8;
            let nsym = nsym.min(MAX_BITS as u8);
            lens = [0u8; MAX_SYMBOLS];
            for &(_, s) in &leaves {
                lens[s as usize] = nsym;
            }
        }
    }

    let mut enc = HuffEncoder {
        codes: [0; MAX_SYMBOLS],
        lens,
        max_bits: 0,
    };
    assign_canonical_codes(&mut enc);
    Some(enc)
}

/// Assign canonical codes, store **bit-reversed** form for LSB-first writer.
fn assign_canonical_codes(enc: &mut HuffEncoder) {
    let mut bl_count = [0u32; (MAX_BITS as usize) + 1];
    let mut max_bits = 0u32;
    for &l in &enc.lens {
        if l > 0 {
            bl_count[l as usize] += 1;
            max_bits = max_bits.max(l as u32);
        }
    }
    enc.max_bits = max_bits;

    // next_code[len] = canonical code (MSB-first numeric value)
    let mut next_code = [0u32; (MAX_BITS as usize) + 1];
    let mut code = 0u32;
    for bits in 1..=max_bits as usize {
        code = (code + bl_count[bits - 1]) << 1;
        next_code[bits] = code;
    }

    for sym in 0..MAX_SYMBOLS {
        let len = enc.lens[sym] as u32;
        if len > 0 {
            let canonical = next_code[len as usize];
            next_code[len as usize] += 1;
            // Reverse so LSB-first write emits MSB of canonical first
            enc.codes[sym] = reverse_bits(canonical, len);
        }
    }
}

impl HuffEncoder {
    /// Write Huffman code for `symbol` (MSB-first logical order).
    #[inline]
    pub fn encode(&self, w: &mut BitWriter, symbol: u8) {
        let len = self.lens[symbol as usize] as u32;
        debug_assert!(len > 0, "encoding unused symbol {symbol}");
        w.write_bits(self.codes[symbol as usize], len);
    }

    /// Serialize length table (256 bytes).
    pub fn write_table(&self, out: &mut Vec<u8>) {
        out.extend_from_slice(&self.lens);
    }

    /// Length table.
    pub fn lengths(&self) -> &[u8; MAX_SYMBOLS] {
        &self.lens
    }
}

/// Build decoder from 256 length bytes.
pub fn decoder_from_lengths(lens: &[u8; MAX_SYMBOLS]) -> Result<HuffDecoder> {
    let mut max_bits = 0u32;
    for &l in lens {
        if l as u32 > MAX_BITS {
            return Err(Error::Decompression(format!(
                "huffman length {l} > {MAX_BITS}"
            )));
        }
        if l > 0 {
            max_bits = max_bits.max(l as u32);
        }
    }
    if max_bits == 0 {
        return Err(Error::Decompression("empty huffman table".into()));
    }

    // Rebuild canonical (non-reversed) codes for table
    let mut bl_count = [0u32; (MAX_BITS as usize) + 1];
    for &l in lens {
        if l > 0 {
            bl_count[l as usize] += 1;
        }
    }
    let mut next_code = [0u32; (MAX_BITS as usize) + 1];
    let mut code = 0u32;
    for bits in 1..=max_bits as usize {
        code = (code + bl_count[bits - 1]) << 1;
        next_code[bits] = code;
    }

    // Table indexed by MSB-first bit window: code in the high `len` bits.
    // Our BitReader is LSB-first, so after reading we reverse the peek window.
    let size = 1usize << max_bits;
    let mut table = vec![(0u8, 0u8); size];

    for (sym, &len_u8) in lens.iter().enumerate().take(MAX_SYMBOLS) {
        let len = len_u8 as u32;
        if len == 0 {
            continue;
        }
        let canonical = next_code[len as usize];
        next_code[len as usize] += 1;

        // For LSB-first stream with bit-reversed codes on the wire, the next
        // `max_bits` from the reader (low bits = first bits) equal
        // reverse(canonical_window). Fill table using reversed index.
        let rev = reverse_bits(canonical, len);
        let free = max_bits - len;
        let count = 1usize << free;
        for i in 0..count {
            // free bits are the later (high) bits in LSB-first peek
            let idx = (rev as usize) | (i << len as usize);
            // Prefer longer codes on collision (shouldn't happen if kraft OK)
            if table[idx].1 < len as u8 {
                table[idx] = (sym as u8, len as u8);
            }
        }
    }

    Ok(HuffDecoder { table, max_bits })
}

impl HuffDecoder {
    /// Decode one symbol.
    #[inline]
    pub fn decode(&self, r: &mut BitReader<'_>) -> Result<u8> {
        r.ensure_bits();
        let peek = r
            .peek_bits_padded(self.max_bits)
            .ok_or_else(|| Error::Decompression("truncated huffman bitstream".into()))?;
        let (sym, len) = self.table[peek as usize];
        if len == 0 {
            return Err(Error::Decompression("invalid huffman code".into()));
        }
        let _ = r
            .read_bits(len as u32)
            .ok_or_else(|| Error::Decompression("truncated huffman code bits".into()))?;
        Ok(sym)
    }
}

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

    #[test]
    fn huff_roundtrip() {
        let mut freq = [0u32; 256];
        for b in b"aaabbc" {
            freq[*b as usize] += 1;
        }
        let enc = build_encoder(&freq).unwrap();
        let mut w = BitWriter::new();
        for &b in b"aaabbc" {
            enc.encode(&mut w, b);
        }
        let bytes = w.finish();
        let dec = decoder_from_lengths(enc.lengths()).unwrap();
        let mut r = BitReader::new(&bytes);
        let mut out = Vec::new();
        for _ in 0..6 {
            out.push(dec.decode(&mut r).unwrap());
        }
        assert_eq!(out, b"aaabbc");
    }

    #[test]
    fn huff_large_alphabet() {
        let mut freq = [0u32; 256];
        for i in 0..36u8 {
            let c = if i < 26 { b'A' + i } else { b'0' + (i - 26) };
            freq[c as usize] = 200;
        }
        let enc = build_encoder(&freq).unwrap();
        let mut data = Vec::new();
        for _ in 0..200 {
            data.extend_from_slice(b"ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789");
        }
        let mut w = BitWriter::new();
        for &b in &data {
            enc.encode(&mut w, b);
        }
        let bytes = w.finish();
        let dec = decoder_from_lengths(enc.lengths()).unwrap();
        let mut r = BitReader::new(&bytes);
        let mut out = Vec::with_capacity(data.len());
        for i in 0..data.len() {
            match dec.decode(&mut r) {
                Ok(s) => out.push(s),
                Err(e) => panic!("at {i}: {e}"),
            }
        }
        assert_eq!(out, data);
    }
}