zexc 1.1.0

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
//! - Early **incompressible** detection → store raw (caller may choose Raw block)
//! - SIMD-wide match length only
//!
//! Trade-off: ratio is secondary to speed.

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

const HASH_LOG: u32 = 12;
const HASH_SIZE: usize = 1 << HASH_LOG;
const ACCEL: u32 = 6;

#[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())
}

/// 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)) & 0xFF) as usize;
        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 prefix history.
pub fn compress_into(src: &[u8], out: &mut Vec<u8>, dict: Option<&[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(());
    }

    // Fast reject: let outer layer use Raw if we signal expansion
    let dict = dict.unwrap_or(&[]);
    let dict = if dict.len() > MAX_OFFSET {
        &dict[dict.len() - MAX_OFFSET..]
    } else {
        dict
    };
    let dlen = dict.len();

    let mut combined = Vec::with_capacity(dlen + src.len());
    combined.extend_from_slice(dict);
    combined.extend_from_slice(src);
    let base = dlen;
    let end = combined.len();

    let mut table = [0u32; HASH_SIZE];
    // Seed dict sparsely
    if dlen >= MIN_MATCH {
        let step = if dlen > 8192 { 4 } else { 1 };
        let mut p = 0usize;
        while p + 4 <= dlen {
            table[hash4(read_u32(&combined, p))] = (p as u32).wrapping_add(1);
            p += step;
        }
    }

    let mut literals = Vec::with_capacity(src.len() / 2);
    let mut seqs: Vec<(u32, u32, u32)> = Vec::new(); // ll, ml, off

    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(&combined, ip);
        let h = hash4(v);
        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(&combined, cpos) == v {
                    let max_ml = (end - ip).min(MAX_MATCH_LEN);
                    let ml = MIN_MATCH
                        + simd::match_len(
                            &combined[cpos + MIN_MATCH..],
                            &combined[ip + MIN_MATCH..],
                            max_ml.saturating_sub(MIN_MATCH),
                        );
                    if ml >= MIN_MATCH && ip + ml <= end {
                        let lit_len = (ip - anchor) as u32;
                        literals.extend_from_slice(&combined[anchor..ip]);
                        seqs.push((lit_len, ml as u32, off as u32));
                        // sparse insert through match
                        let mut p = ip + 2;
                        let mend = ip + ml;
                        while p < mend && p + 4 <= end {
                            table[hash4(read_u32(&combined, p))] = (p as u32).wrapping_add(1);
                            p += 2;
                        }
                        ip = mend;
                        anchor = mend;
                        miss = 0;
                        matched = true;
                    }
                }
            }
        }

        if !matched {
            miss = miss.saturating_add(1);
            let step = if miss > 16 {
                (1 + ((miss as usize - 16) >> ACCEL as usize)).min(64)
            } else {
                1
            };
            ip += step;
        }
    }

    if anchor < end {
        literals.extend_from_slice(&combined[anchor..end]);
        seqs.push(((end - anchor) as u32, 0, 0));
    } else if seqs.is_empty() {
        literals.extend_from_slice(src);
        seqs.push((src.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 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());
    }
}