zexc 1.2.1

zex native lossless compressor — CLI zexc, library zexc, files *.zex
Documentation
//! Optimal-ish parsing for high compression levels (≥ 15).
//!
//! Dynamic programming over positions with a simple bit-cost model.
//! Emits the same sequence model as the main codec: (lit_len, match_len, offset).

use alloc::vec::Vec;

use crate::utils::security::{MAX_MATCH_LEN, MAX_OFFSET, MIN_MATCH};
use crate::utils::simd;

const HASH_LOG: u32 = 17;
const HASH_SIZE: usize = 1 << HASH_LOG;
const CHAIN_LOG: u32 = 15;
const SEARCHES: usize = 64;

#[inline]
fn lit_cost(n: u32) -> u32 {
    n.saturating_mul(8).saturating_add(2)
}

#[inline]
fn match_cost(ml: u32, offset: u32) -> u32 {
    let ml_bits = if ml < 16 {
        4
    } else if ml < 256 {
        12
    } else {
        20
    };
    let off_bits = if offset < 128 {
        8
    } else if offset < 16384 {
        16
    } else {
        24
    };
    8 + ml_bits + off_bits
}

#[inline]
fn hash4(v: u32) -> usize {
    (v.wrapping_mul(0x9E37_79B1) >> (32 - HASH_LOG)) as usize
}

#[inline]
fn read_u32(data: &[u8], pos: usize) -> u32 {
    u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap())
}

/// (literal_len, match_len, offset); match_len 0 = trailing lits only.
pub type OptSeq = (u32, u32, u32);

/// Optimal parse → (literals blob, sequences).
pub fn parse(src: &[u8]) -> (Vec<u8>, Vec<OptSeq>) {
    let n = src.len();
    if n == 0 {
        return (Vec::new(), Vec::new());
    }
    if n < MIN_MATCH + 1 {
        return (src.to_vec(), vec![(n as u32, 0, 0)]);
    }

    let mut hash = vec![0u32; HASH_SIZE];
    let mut chain = vec![0u32; 1 << CHAIN_LOG];
    let chain_mask = (1u32 << CHAIN_LOG) - 1;
    let window = MAX_OFFSET.min(n);

    let mut cost = vec![u32::MAX / 4; n + 1];
    let mut prev = vec![0usize; n + 1];
    let mut arr_ml = vec![0u32; n + 1];
    let mut arr_off = vec![0u32; n + 1];
    cost[0] = 0;

    for i in 0..n {
        if cost[i] >= u32::MAX / 8 {
            // still fill hash so later positions work
            if i + 4 <= n {
                let h = hash4(read_u32(src, i));
                let old = hash[h];
                hash[h] = (i as u32).wrapping_add(1);
                chain[(i as u32 & chain_mask) as usize] = old;
            }
            continue;
        }

        // Literal
        let cl = cost[i].saturating_add(lit_cost(1));
        if cl < cost[i + 1] {
            cost[i + 1] = cl;
            prev[i + 1] = i;
            arr_ml[i + 1] = 0;
            arr_off[i + 1] = 0;
        }

        if i + MIN_MATCH <= n {
            let v = read_u32(src, i);
            let h = hash4(v);
            let mut cand = hash[h];
            let mut probes = 0usize;
            while cand != 0 && probes < SEARCHES {
                probes += 1;
                let cpos = (cand as usize).wrapping_sub(1);
                if cpos >= i {
                    break;
                }
                let off = i - cpos;
                if off == 0 || off > window {
                    break;
                }
                // Kick off the next chain hop's load now, hidden behind the
                // match_len work below (chain walks are effectively random
                // access, so this is a real cache-miss-latency win).
                simd::prefetch_read(
                    chain
                        .as_ptr()
                        .wrapping_add((cpos as u32 & chain_mask) as usize)
                        .cast::<u8>(),
                );
                if read_u32(src, cpos) == v {
                    let max_ml = (n - i).min(MAX_MATCH_LEN);
                    let ml = MIN_MATCH
                        + simd::match_len(
                            &src[cpos + MIN_MATCH..],
                            &src[i + MIN_MATCH..],
                            max_ml.saturating_sub(MIN_MATCH),
                        );
                    if ml >= MIN_MATCH {
                        let j = i + ml;
                        let cm = cost[i].saturating_add(match_cost(ml as u32, off as u32));
                        if cm < cost[j] {
                            cost[j] = cm;
                            prev[j] = i;
                            arr_ml[j] = ml as u32;
                            arr_off[j] = off as u32;
                        }
                    }
                }
                cand = chain[(cpos as u32 & chain_mask) as usize];
            }
            let old = hash[h];
            hash[h] = (i as u32).wrapping_add(1);
            chain[(i as u32 & chain_mask) as usize] = old;
        } else if i + 4 <= n {
            let h = hash4(read_u32(src, i));
            let old = hash[h];
            hash[h] = (i as u32).wrapping_add(1);
            chain[(i as u32 & chain_mask) as usize] = old;
        }
    }

    // Path edges from 0 → n
    let mut nodes = Vec::new();
    let mut i = n;
    while i > 0 {
        let p = prev[i];
        nodes.push((p, i, arr_ml[i], arr_off[i]));
        i = p;
    }
    nodes.reverse();

    let mut literals = Vec::new();
    let mut seqs: Vec<OptSeq> = Vec::new();
    let mut pending_lits = 0u32;

    for &(start, end, ml, off) in &nodes {
        if ml == 0 {
            pending_lits += (end - start) as u32;
            literals.extend_from_slice(&src[start..end]);
        } else {
            // Match starts at `start`; any pending_lits are immediately before it
            seqs.push((pending_lits, ml, off));
            pending_lits = 0;
            // Match body is not stored in literals
            debug_assert_eq!(end - start, ml as usize);
        }
    }
    if pending_lits > 0 || seqs.is_empty() {
        seqs.push((pending_lits, 0, 0));
    }

    (literals, seqs)
}

/// Use optimal parse for this level?
pub fn should_use(level: u8) -> bool {
    level >= 15
}

/// Rebuild bytes from parse output (test helper).
pub fn execute(lits: &[u8], seqs: &[OptSeq]) -> Vec<u8> {
    let mut out = Vec::new();
    let mut li = 0usize;
    for &(ll, ml, off) in seqs {
        out.extend_from_slice(&lits[li..li + ll as usize]);
        li += ll as usize;
        if ml > 0 {
            let start = out.len() - off as usize;
            for k in 0..ml as usize {
                let b = out[start + k];
                out.push(b);
            }
        }
    }
    out
}

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

    #[test]
    fn opt_rebuilds_source() {
        let src = b"OPTIMAL PARSE TEST DATA OPTIMAL PARSE ".repeat(100);
        let (lits, seqs) = parse(&src);
        let sum_ll: usize = seqs.iter().map(|s| s.0 as usize).sum();
        assert_eq!(sum_ll, lits.len());
        assert_eq!(execute(&lits, &seqs), src.as_slice());
    }

    #[test]
    fn opt_beats_all_literals_on_rep() {
        let src = b"ABCDEFGH".repeat(200);
        let (lits, seqs) = parse(&src);
        let has_match = seqs.iter().any(|s| s.1 >= MIN_MATCH as u32);
        assert!(has_match, "expected matches on repetitive data");
        assert!(lits.len() < src.len());
        assert_eq!(execute(&lits, &seqs), src.as_slice());
    }
}