zexc 1.1.0

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
//! - ~64 KB table (16K entries × 4 bytes)
//! - Activated only for levels ≥ 5 and blocks > 256 KB
//!
//! The matches emitted are standard (offset, match_len) pairs — no wire
//! format change needed. The decoder doesn't know (or care) whether a match
//! came from LDM or the regular match finder.

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

/// Minimum match length for long-distance matches.
/// Below this, the offset encoding cost isn't worth it.
pub const LDM_MIN_MATCH: usize = 64;

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

/// Hash table size (must be power of two).
const LDM_HASH_LOG: u32 = 14;
const LDM_HASH_SIZE: usize = 1 << LDM_HASH_LOG;

/// 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.
pub struct LdmTable {
    /// Position + 1 (0 = empty slot). Indexed by hash.
    table: Vec<u32>,
}

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

    /// Hash 8 bytes at `pos` → table 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 the LDM table from the data, sampling every [`SAMPLE_STEP`] bytes.
    ///
    /// If `dict_len > 0`, positions 0..dict_len are dictionary prefix.
    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 {
            let h = Self::hash8(data, pos);
            self.table[h] = (pos as u32).wrapping_add(1);
            pos += SAMPLE_STEP;
        }
    }

    /// Insert a single position into the LDM table.
    #[inline]
    pub fn insert(&mut self, data: &[u8], pos: usize) {
        if pos + 8 <= data.len() {
            let h = Self::hash8(data, pos);
            self.table[h] = (pos as u32).wrapping_add(1);
        }
    }

    /// Try to find a long-distance match at `pos`.
    ///
    /// Returns `Some((offset, match_len))` if a match ≥ `LDM_MIN_MATCH` is found.
    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 cand = self.table[h];
        if cand == 0 {
            return None;
        }

        let cpos = (cand as usize).wrapping_sub(1);
        if cpos >= pos {
            return None;
        }

        let offset = pos - cpos;
        if offset == 0 || offset > MAX_OFFSET {
            return None;
        }

        // Verify the 8-byte hash match is a real match.
        if pos + 8 > data.len() || cpos + 8 > data.len() {
            return None;
        }
        if data[cpos..cpos + 8] != data[pos..pos + 8] {
            return None;
        }

        // Extend match length using SIMD.
        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 {
            Some((offset, ml))
        } else {
            None
        }
    }

    /// 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::*;

    #[test]
    fn ldm_finds_distant_match() {
        // Create data with a 128-byte pattern at the start and repeated far away.
        let pattern = b"LDM_LONG_DISTANCE_MATCH_TEST_PATTERN_AAABBBCCCDDDEEEFFF_1234567890ABCDEF!";
        let gap_size = 1_000_000; // 1 MB gap
        let mut data = Vec::with_capacity(gap_size + pattern.len() * 2);
        data.extend_from_slice(pattern);
        // Fill gap with pseudo-random data (won't match)
        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 mut ldm = LdmTable::new();
        ldm.seed(&data, 0, data.len());

        let repeat_pos = pattern.len() + gap_size;
        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, gap_size + pattern.len(),
            "offset should point back to pattern start"
        );
    }

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

        // Random data shouldn't produce LDM matches (extremely unlikely)
        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));
    }
}