zexc 1.2.1

zex native lossless compressor — CLI zexc, library zexc, files *.zex
Documentation
//! Long-distance matching (LDM) for large files.
//!
//! When the main match finder's window is exhausted, LDM provides a coarse
//! hash table sampled every N bytes that can find matches at offsets up to
//! [`MAX_OFFSET`] (8 MiB). Minimum match length for LDM is 64 bytes —
//! shorter matches don't justify the offset encoding cost.
//!
//! Design (same approach as Zstd LDM):
//! - Hash on 8-byte windows for collision resistance
//! - Sparse sampling (every [`SAMPLE_STEP`] bytes) to keep the table small
//! - **Multi-slot buckets** so hash collisions do not erase earlier candidates
//!   (a classic single-slot table fails on high-entropy gaps — verified)
//! - Activated only for levels ≥ 5 and blocks > 256 KB
//!
//! **Important:** only index positions that are *history* relative to the
//! current encode cursor. Prefer [`LdmTable::seed`] on dictionary / past bytes
//! and [`LdmTable::insert`] / [`LdmTable::maybe_insert`] as the cursor advances.
//!
//! Matches are standard (offset, match_len) pairs — no wire format change.

use alloc::vec::Vec;

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

/// Minimum match length for long-distance matches.
pub const LDM_MIN_MATCH: usize = 64;

/// Sampling step: index every N-th byte position.
pub const SAMPLE_STEP: usize = 512;

/// Hash table log (bucket count = 2^LOG).
const LDM_HASH_LOG: u32 = 14;
const LDM_HASH_SIZE: usize = 1 << LDM_HASH_LOG;

/// Candidates kept per hash bucket (MRU order, slot 0 = newest).
const BUCKET_DEPTH: usize = 8;

/// Minimum block size to enable LDM (256 KiB).
pub const LDM_MIN_BLOCK: usize = 256 * 1024;

/// Minimum compression level to enable LDM.
pub const LDM_MIN_LEVEL: u8 = 5;

/// Long-distance match table with multi-slot hash buckets.
pub struct LdmTable {
    /// Each bucket holds up to [`BUCKET_DEPTH`] positions (+1 encoding, 0 = empty).
    buckets: Vec<[u32; BUCKET_DEPTH]>,
}

impl Default for LdmTable {
    fn default() -> Self {
        Self::new()
    }
}

impl LdmTable {
    /// Create a new empty LDM table.
    pub fn new() -> Self {
        Self {
            buckets: vec![[0u32; BUCKET_DEPTH]; LDM_HASH_SIZE],
        }
    }

    /// Hash 8 bytes at `pos` → bucket index.
    #[inline]
    fn hash8(data: &[u8], pos: usize) -> usize {
        if pos + 8 > data.len() {
            return 0;
        }
        let lo = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap());
        let hi = u32::from_le_bytes(data[pos + 4..pos + 8].try_into().unwrap());
        let h = lo.wrapping_mul(0x9E37_79B1) ^ hi.wrapping_mul(0x85EB_CA77);
        (h >> (32 - LDM_HASH_LOG)) as usize
    }

    /// Seed from history `[start, end)`, sampling every [`SAMPLE_STEP`] bytes.
    ///
    /// `end` must be the exclusive end of **already-known** history. Do not pass
    /// the full block end while the encode cursor is still at the start.
    pub fn seed(&mut self, data: &[u8], start: usize, end: usize) {
        let end = end.min(data.len().saturating_sub(8));
        let mut pos = start;
        while pos < end {
            self.insert(data, pos);
            pos += SAMPLE_STEP;
        }
        // Index the last sample-aligned history edge for short tails.
        if end > start {
            let last = end.saturating_sub(1);
            let aligned = last.saturating_sub(last % SAMPLE_STEP);
            if aligned >= start && aligned + 8 <= data.len() {
                self.insert(data, aligned);
            }
        }
    }

    /// Insert `pos` at the front of its hash bucket (MRU).
    #[inline]
    pub fn insert(&mut self, data: &[u8], pos: usize) {
        if pos + 8 > data.len() {
            return;
        }
        let h = Self::hash8(data, pos);
        let bucket = &mut self.buckets[h];
        let tag = (pos as u32).wrapping_add(1);

        // Already newest — nothing to do.
        if bucket[0] == tag {
            return;
        }
        // Push front; keep older unique candidates; drop overflow from the tail.
        let mut tmp = [0u32; BUCKET_DEPTH];
        tmp[0] = tag;
        let mut o = 1usize;
        for &c in bucket.iter() {
            if c == 0 || c == tag {
                continue;
            }
            if o < BUCKET_DEPTH {
                tmp[o] = c;
                o += 1;
            }
        }
        *bucket = tmp;
    }

    /// Insert only on sample boundaries (as the encode cursor advances).
    #[inline]
    pub fn maybe_insert(&mut self, data: &[u8], pos: usize) {
        if pos % SAMPLE_STEP == 0 {
            self.insert(data, pos);
        }
    }

    /// Find a long-distance match at `pos`.
    ///
    /// Probes all candidates in the hash bucket so collisions do not hide the
    /// real match. Returns `Some((offset, match_len))` if ≥ [`LDM_MIN_MATCH`].
    pub fn find(&self, data: &[u8], pos: usize, max_len: usize) -> Option<(usize, usize)> {
        if pos + 8 > data.len() || max_len < LDM_MIN_MATCH {
            return None;
        }

        let h = Self::hash8(data, pos);
        let bucket = &self.buckets[h];
        let mut best: Option<(usize, usize)> = None;

        for &cand in bucket {
            if cand == 0 {
                break; // trailing empties after compact insert
            }
            let cpos = (cand as usize).wrapping_sub(1);
            if cpos >= pos || cpos + 8 > data.len() {
                continue;
            }
            let offset = pos - cpos;
            if offset == 0 || offset > MAX_OFFSET {
                continue;
            }
            // Reject pure hash collisions quickly.
            if data[cpos..cpos + 8] != data[pos..pos + 8] {
                continue;
            }

            let max_ml = max_len.min(MAX_MATCH_LEN);
            let ml = 8 + simd::match_len(
                &data[cpos + 8..],
                &data[pos + 8..],
                max_ml.saturating_sub(8),
            );

            if ml >= LDM_MIN_MATCH {
                let better = match best {
                    None => true,
                    Some((bo, bm)) => ml > bm || (ml == bm && offset < bo),
                };
                if better {
                    best = Some((offset, ml));
                    if ml >= 256 {
                        break;
                    }
                }
            }
        }

        best
    }

    /// Whether LDM should be active for this level + block size.
    pub fn should_use(level: u8, block_len: usize) -> bool {
        level >= LDM_MIN_LEVEL && block_len >= LDM_MIN_BLOCK
    }
}

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

    fn make_distant_pattern_data(gap_size: usize) -> (Vec<u8>, usize, usize) {
        let pattern = b"LDM_LONG_DISTANCE_MATCH_TEST_PATTERN_AAABBBCCCDDDEEEFFF_1234567890ABCDEF!";
        assert!(pattern.len() >= LDM_MIN_MATCH);
        let mut data = Vec::with_capacity(gap_size + pattern.len() * 2);
        data.extend_from_slice(pattern);
        let mut x = 0xDEAD_BEEFu32;
        for _ in 0..gap_size {
            x = x.wrapping_mul(1664525).wrapping_add(1013904223);
            data.push((x >> 24) as u8);
        }
        data.extend_from_slice(pattern);
        let repeat_pos = pattern.len() + gap_size;
        (data, pattern.len(), repeat_pos)
    }

    #[test]
    fn ldm_finds_distant_match() {
        let (data, _plen, repeat_pos) = make_distant_pattern_data(1_000_000);
        let mut ldm = LdmTable::new();
        // Correct usage: only seed *history* before the search position.
        ldm.seed(&data, 0, repeat_pos);

        let remain = data.len() - repeat_pos;
        let result = ldm.find(&data, repeat_pos, remain);
        assert!(
            result.is_some(),
            "LDM should find the distant pattern match"
        );
        let (offset, ml) = result.unwrap();
        assert!(
            ml >= LDM_MIN_MATCH,
            "match length {ml} should be >= {LDM_MIN_MATCH}"
        );
        assert_eq!(
            offset, repeat_pos,
            "offset should point back to pattern start"
        );
        assert_eq!(
            &data[repeat_pos - offset..repeat_pos - offset + ml],
            &data[repeat_pos..repeat_pos + ml]
        );
    }

    #[test]
    fn ldm_survives_hash_collisions_in_full_seed() {
        // Full-buffer seed fills the bucket with random-gap collisions.
        // Multi-slot buckets must still keep the real match at position 0.
        let (data, _plen, repeat_pos) = make_distant_pattern_data(1_000_000);
        let mut ldm = LdmTable::new();
        ldm.seed(&data, 0, data.len());

        let result = ldm.find(&data, repeat_pos, data.len() - repeat_pos);
        assert!(
            result.is_some(),
            "bucket must recover match past hash collisions"
        );
        let (offset, ml) = result.unwrap();
        assert!(ml >= LDM_MIN_MATCH);
        assert_eq!(offset, repeat_pos);
    }

    #[test]
    fn ldm_progressive_insert_finds_match() {
        let pattern = b"PROG_LDM_PATTERN_XXXXXXXXYYYYYYYYZZZZZZZZ_0123456789ABCDEF_END_PAD!!";
        assert!(pattern.len() >= LDM_MIN_MATCH);
        let gap = 300_000usize;
        let mut data = Vec::new();
        data.extend_from_slice(pattern);
        for i in 0..gap {
            data.push((i.wrapping_mul(31) & 0xFF) as u8);
        }
        data.extend_from_slice(pattern);

        let mut ldm = LdmTable::new();
        let search_at = pattern.len() + gap;
        let mut pos = 0usize;
        while pos < search_at {
            ldm.maybe_insert(&data, pos);
            pos += 1;
        }
        ldm.insert(&data, 0);

        let r = ldm.find(&data, search_at, pattern.len());
        assert!(r.is_some());
        let (off, ml) = r.unwrap();
        assert!(ml >= LDM_MIN_MATCH);
        assert_eq!(off, search_at);
    }

    #[test]
    fn ldm_no_match_random() {
        let mut data = Vec::with_capacity(100_000);
        let mut x = 0xC0FFEEu32;
        for _ in 0..100_000 {
            x = x.wrapping_mul(1664525).wrapping_add(1013904223);
            data.push((x >> 24) as u8);
        }
        let mut ldm = LdmTable::new();
        ldm.seed(&data, 0, data.len());

        let mut found = 0;
        for pos in (50_000..90_000).step_by(512) {
            if ldm.find(&data, pos, data.len() - pos).is_some() {
                found += 1;
            }
        }
        assert!(
            found < 3,
            "random data should have very few LDM matches, got {found}"
        );
    }

    #[test]
    fn ldm_activation_check() {
        assert!(!LdmTable::should_use(4, 1_000_000));
        assert!(!LdmTable::should_use(5, 100_000));
        assert!(LdmTable::should_use(5, 300_000));
        assert!(LdmTable::should_use(9, 1_000_000));
    }
}