zexc 1.2.1

zex native lossless compressor — CLI zexc, library zexc, files *.zex
Documentation
//! Turbo compression path — maximum throughput, minimal analysis.
//!
//! Used for levels 1–2 (and Turbo profile). Design goals:
//! - Single-slot hash table (no chain)
//! - Aggressive adaptive skip on misses (LZ4-style acceleration)
//! - Early **incompressible** detection → store raw (caller may choose Raw block)
//! - SIMD-wide match length only
//! - **Zero-copy** when no dictionary (no combined buffer)
//!
//! Trade-off: ratio is secondary to speed. Level 2 uses a larger hash and
//! denser post-match inserts for a slightly better ratio at small cost.

use alloc::vec::Vec;

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

/// Level-1 defaults: tiny hash, aggressive skip.
const HASH_LOG_L1: u32 = 12;
/// Level-2: larger hash → fewer collisions → better ratio.
const HASH_LOG_L2: u32 = 14;

#[inline]
fn hash4(v: u32, hash_log: 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())
}

/// Sample-based incompressible heuristic.
///
/// Returns `true` if a sparse sample of `src` looks high-entropy (few 4-byte
/// repeats). Caller should store as raw to avoid wasted work.
pub fn looks_incompressible(src: &[u8]) -> bool {
    if src.len() < 4096 {
        return false;
    }
    // Sample ~256 positions across the block
    let step = (src.len() / 256).max(16);
    let mut table = [0u32; 256]; // tiny direct-map of high hash bits
    let mut hits = 0u32;
    let mut samples = 0u32;
    let mut pos = 0usize;
    while pos + 4 <= src.len() && samples < 256 {
        let h = hash4(read_u32(src, pos), 12) & 0xFF;
        let tag = read_u32(src, pos);
        if table[h] == tag.wrapping_add(1) {
            hits += 1;
        } else {
            table[h] = tag.wrapping_add(1);
        }
        samples += 1;
        pos += step;
    }
    // Very few hash collisions → likely random / already compressed
    samples > 64 && hits * 20 < samples
}

/// Compress with turbo algorithm into the **same** native sequence wire format
/// as the main codec (FLAG_REP, no FSE/Huffman) for decoder compatibility.
///
/// Returns compressed payload bytes (not including outer ZEX frame).
pub fn compress(src: &[u8]) -> Result<Vec<u8>> {
    let mut out = Vec::with_capacity(src.len() / 2 + 64);
    compress_into(src, &mut out, None)?;
    Ok(out)
}

/// Turbo compress with optional dictionary (defaults to level-1 params).
pub fn compress_into(src: &[u8], out: &mut Vec<u8>, dict: Option<&[u8]>) -> Result<()> {
    compress_into_level(src, out, dict, 1)
}

/// Turbo compress with level-tuned hash/skip (1 = fastest, 2 = denser hash).
pub fn compress_into_level(
    src: &[u8],
    out: &mut Vec<u8>,
    dict: Option<&[u8]>,
    level: u8,
) -> Result<()> {
    if src.is_empty() {
        out.push(0);
        out.extend_from_slice(&0u32.to_le_bytes());
        out.extend_from_slice(&0u32.to_le_bytes());
        return Ok(());
    }

    let level = level.clamp(1, 2);
    let hash_log = if level >= 2 { HASH_LOG_L2 } else { HASH_LOG_L1 };
    let hash_size = 1usize << hash_log;
    // Acceleration: higher → skip grows faster on misses (level 1 more aggressive).
    let accel: u32 = if level >= 2 { 4 } else { 6 };
    let max_skip: usize = if level >= 2 { 32 } else { 64 };
    // After a match, fill hash every `fill_step` bytes (1 = denser).
    let fill_step: usize = if level >= 2 { 1 } else { 2 };

    let dict = dict.unwrap_or(&[]);
    let dict = if dict.len() > MAX_OFFSET {
        &dict[dict.len() - MAX_OFFSET..]
    } else {
        dict
    };
    let dlen = dict.len();

    let cfg = TurboCfg {
        hash_log,
        hash_size,
        accel,
        max_skip,
        fill_step,
    };

    // Zero-copy path when no dictionary: search directly in `src`.
    if dlen == 0 {
        return compress_body(src, 0, src, out, &cfg);
    }

    let mut combined = Vec::with_capacity(dlen + src.len());
    combined.extend_from_slice(dict);
    combined.extend_from_slice(src);
    compress_body(&combined, dlen, src, out, &cfg)
}

struct TurboCfg {
    hash_log: u32,
    hash_size: usize,
    accel: u32,
    max_skip: usize,
    fill_step: usize,
}

/// Core turbo loop over `data[base..]` (source region starts at `base`).
fn compress_body(
    data: &[u8],
    base: usize,
    src_only: &[u8],
    out: &mut Vec<u8>,
    cfg: &TurboCfg,
) -> Result<()> {
    let end = data.len();
    let mut table = vec![0u32; cfg.hash_size];

    // Seed dictionary prefix sparsely (if any).
    if base >= MIN_MATCH {
        let step = if base > 8192 { 4 } else { 1 };
        let mut p = 0usize;
        while p + 4 <= base {
            table[hash4(read_u32(data, p), cfg.hash_log)] = (p as u32).wrapping_add(1);
            p += step;
        }
    }

    let mut literals = Vec::with_capacity(src_only.len() / 4 + 16);
    let mut seqs: Vec<(u32, u32, u32)> = Vec::with_capacity(src_only.len() / 32 + 4);

    let mut anchor = base;
    let mut ip = base;
    let limit = end.saturating_sub(MIN_MATCH + 1);
    let mut miss = 0u32;
    let window = (64 * 1024).min(MAX_OFFSET).min(end.max(1));

    while ip < limit {
        let v = read_u32(data, ip);
        let h = hash4(v, cfg.hash_log);
        let cand = table[h];
        table[h] = (ip as u32).wrapping_add(1);

        let mut matched = false;
        if cand != 0 {
            let cpos = (cand as usize).wrapping_sub(1);
            if cpos < ip {
                let off = ip - cpos;
                if off > 0 && off <= window && read_u32(data, cpos) == v {
                    let max_ml = (end - ip).min(MAX_MATCH_LEN);
                    let ml = MIN_MATCH
                        + simd::match_len(
                            &data[cpos + MIN_MATCH..],
                            &data[ip + MIN_MATCH..],
                            max_ml.saturating_sub(MIN_MATCH),
                        );
                    // Gain filter: min-match at huge offset is usually a loss.
                    if ml >= MIN_MATCH && ip + ml <= end && !(ml == MIN_MATCH && off > 4096) {
                        let lit_len = (ip - anchor) as u32;
                        literals.extend_from_slice(&data[anchor..ip]);
                        seqs.push((lit_len, ml as u32, off as u32));
                        // Sparse/dense insert through match
                        let mend = ip + ml;
                        let mut p = ip + cfg.fill_step;
                        while p < mend && p + 4 <= end {
                            table[hash4(read_u32(data, p), cfg.hash_log)] =
                                (p as u32).wrapping_add(1);
                            p += cfg.fill_step;
                        }
                        ip = mend;
                        anchor = mend;
                        miss = 0;
                        matched = true;
                    }
                }
            }
        }

        if !matched {
            miss = miss.saturating_add(1);
            // LZ4-style acceleration: after a streak of misses, stride grows.
            // Using >> accel makes higher accel → larger steps sooner.
            let step = if miss > 16 {
                (1 + ((miss as usize - 16) >> cfg.accel as usize)).min(cfg.max_skip)
            } else {
                1
            };
            // When skipping, still index the land position next iteration only
            // (hash insert happens at loop head). Intermediate skips stay cold —
            // that is intentional for turbo throughput.
            ip += step;
        }
    }

    if anchor < end {
        literals.extend_from_slice(&data[anchor..end]);
        seqs.push(((end - anchor) as u32, 0, 0));
    } else if seqs.is_empty() {
        literals.extend_from_slice(src_only);
        seqs.push((src_only.len() as u32, 0, 0));
    }

    // Wire: FLAG_REP only (fast, no FSE/Huffman)
    const FLAG_REP: u8 = 4;
    let mut reps = [1u32, 4u32, 8u32];
    out.push(FLAG_REP);
    out.extend_from_slice(&(literals.len() as u32).to_le_bytes());
    out.extend_from_slice(&(seqs.len() as u32).to_le_bytes());
    out.extend_from_slice(&literals);

    for &(ll, ml, off) in &seqs {
        put_varint(out, ll);
        put_varint(out, ml);
        if ml > 0 {
            let code = encode_off(off, &mut reps);
            put_varint(out, code);
        }
    }
    Ok(())
}

#[inline]
fn put_varint(out: &mut Vec<u8>, mut v: u32) {
    while v >= 0x80 {
        out.push((v as u8) | 0x80);
        v >>= 7;
    }
    out.push(v as u8);
}

#[inline]
fn encode_off(offset: u32, reps: &mut [u32; 3]) -> u32 {
    if offset == reps[0] {
        return 0;
    }
    if offset == reps[1] {
        reps[1] = reps[0];
        reps[0] = offset;
        return 1;
    }
    if offset == reps[2] {
        reps[2] = reps[1];
        reps[1] = reps[0];
        reps[0] = offset;
        return 2;
    }
    let code = offset.saturating_add(3);
    reps[2] = reps[1];
    reps[1] = reps[0];
    reps[0] = offset;
    code
}

/// Whether turbo path should be selected for this level (no dict entropy path).
pub fn should_use_turbo(level: u8) -> bool {
    level <= 2
}

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

    #[test]
    fn turbo_roundtrip() {
        let src = b"turbo turbo turbo speed path test!!!! ".repeat(100);
        let c = compress(&src).unwrap();
        let d = zex_native::decompress(&c, src.len()).unwrap();
        assert_eq!(d, src.as_slice());
    }

    #[test]
    fn turbo_level2_roundtrip() {
        let src = b"level two denser hash table turbo path ".repeat(200);
        let mut c = Vec::new();
        compress_into_level(&src, &mut c, None, 2).unwrap();
        let d = zex_native::decompress(&c, src.len()).unwrap();
        assert_eq!(d, src.as_slice());
    }

    #[test]
    fn turbo_dict_roundtrip() {
        let dict = b"SHARED-PREFIX-AAAAAAAAAAAAAAAA";
        let src = b"SHARED-PREFIX-AAAAAAAAAAAAAAAA and some tail data";
        let mut c = Vec::new();
        compress_into_level(src, &mut c, Some(dict), 2).unwrap();
        let d = zex_native::decompress_with_history(&c, src.len(), Some(dict)).unwrap();
        assert_eq!(d, src);
    }

    #[test]
    fn incompressible_heuristic_randomish() {
        let mut src = Vec::with_capacity(8192);
        let mut x = 0xDEAD_BEEFu32;
        for _ in 0..8192 {
            x = x.wrapping_mul(1664525).wrapping_add(1013904223);
            src.push((x >> 24) as u8);
        }
        assert!(looks_incompressible(&src));
        let zeros = vec![0u8; 8192];
        assert!(!looks_incompressible(&zeros));
    }

    #[test]
    fn turbo_empty() {
        let c = compress(b"").unwrap();
        let d = zex_native::decompress(&c, 0).unwrap();
        assert!(d.is_empty());
    }
}