zexc 1.2.1

zex native lossless compressor — CLI zexc, library zexc, files *.zex
Documentation
//! Simplified **COVER / fastCover**-style dictionary training.
//!
//! Inspired by Zstd `lib/dictBuilder/cover.c` / `fastcover.c`:
//! 1. Collect segment (k-mer) frequencies across samples  
//! 2. Score segments by frequency × usefulness  
//! 3. Greedily select non-overlapping high-score segments into a dict  
//!
//! This is a clean-room practical trainer — not a line-by-line port.

use crate::core::dictionary::Dictionary;
use crate::utils::crc::crc32;
use crate::{Error, Result};
use std::collections::HashMap;

/// Training parameters.
#[derive(Debug, Clone)]
pub struct CoverParams {
    /// Segment (d-mer) length for frequency counting.
    pub d: usize,
    /// Target dictionary size in bytes.
    pub dict_size: usize,
    /// Minimum times a segment must appear (across samples) to be considered.
    pub min_freq: u32,
    /// Step when scanning samples (1 = dense, >1 = faster).
    pub step: usize,
}

impl Default for CoverParams {
    fn default() -> Self {
        Self {
            d: 8,
            dict_size: 112_640,
            min_freq: 2,
            step: 1,
        }
    }
}

/// Train a dictionary with COVER-style segment selection.
pub fn train_cover(samples: &[&[u8]], params: CoverParams) -> Result<Dictionary> {
    if samples.is_empty() {
        return Err(Error::Dictionary("no samples".into()));
    }
    let d = params.d.clamp(4, 32);
    let dict_size = params.dict_size.clamp(256, 8 * 1024 * 1024);
    let step = params.step.max(1);

    // Concatenate samples with a rare separator so matches don't cross samples
    let sep = [0x00u8, 0x01, 0xFF, 0xFE];
    let mut corpus = Vec::new();
    let mut sample_ranges: Vec<(usize, usize)> = Vec::new();
    for s in samples {
        if s.is_empty() {
            continue;
        }
        let start = corpus.len();
        corpus.extend_from_slice(s);
        sample_ranges.push((start, corpus.len()));
        corpus.extend_from_slice(&sep);
    }
    if corpus.len() < d {
        return Dictionary::train_simple(samples, dict_size);
    }

    // Count d-mer frequencies (hash → count, keep one example offset)
    let mut counts: HashMap<u64, (u32, usize)> = HashMap::new();
    for &(a, b) in &sample_ranges {
        let mut i = a;
        while i + d <= b {
            let h = hash_bytes(&corpus[i..i + d]);
            counts
                .entry(h)
                .and_modify(|(c, _)| *c = c.saturating_add(1))
                .or_insert((1, i));
            i += step;
        }
    }

    // Score candidates
    let mut cands: Vec<(u32, usize, u64)> = counts
        .into_iter()
        .filter(|(_, (c, _))| *c >= params.min_freq)
        .map(|(h, (c, off))| {
            // Prefer frequent + mid-content segments
            let score = c.saturating_mul(d as u32);
            (score, off, h)
        })
        .collect();
    cands.sort_by(|a, b| b.0.cmp(&a.0).then(a.1.cmp(&b.1)));

    // Greedy select non-overlapping epochs into dict (most useful content at end)
    let mut selected: Vec<(usize, usize)> = Vec::new(); // (offset, len) in corpus
    let mut covered = vec![false; corpus.len()];
    let mut used = 0usize;

    for &(_score, off, _) in &cands {
        if used + d > dict_size {
            break;
        }
        // Skip if heavily overlapping already-selected
        let mut overlap = 0usize;
        for k in 0..d {
            if covered[off + k] {
                overlap += 1;
            }
        }
        if overlap * 2 >= d {
            continue;
        }
        for k in 0..d {
            covered[off + k] = true;
        }
        selected.push((off, d));
        used += d;
    }

    if selected.is_empty() {
        return Dictionary::train_simple(samples, dict_size);
    }

    // Build dictionary: least useful first, most useful last (Zstd convention)
    selected.reverse();
    let mut data = Vec::with_capacity(dict_size);
    for (off, len) in selected {
        if data.len() + len > dict_size {
            break;
        }
        data.extend_from_slice(&corpus[off..off + len]);
    }
    // Pad / fill remainder with sample tails if still small
    if data.len() < dict_size / 4 {
        for s in samples.iter().rev() {
            if data.len() >= dict_size {
                break;
            }
            let take = (dict_size - data.len()).min(s.len());
            data.extend_from_slice(&s[s.len() - take..]);
        }
    }

    if data.is_empty() {
        return Err(Error::Dictionary("cover produced empty dict".into()));
    }
    // Stable id
    let mut id = crc32(&data);
    if id == 0 {
        id = 1;
    }
    Ok(Dictionary { id, data })
}

#[inline]
fn hash_bytes(seg: &[u8]) -> u64 {
    // FNV-1a 64
    let mut h = 0xcbf29ce484222325u64;
    for &b in seg {
        h ^= u64::from(b);
        h = h.wrapping_mul(0x100_0000_01b3);
    }
    h
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::core::decoder::{DecompressOptions, decompress_with_options};
    use crate::core::encoder::{CompressOptions, compress};

    #[test]
    fn cover_trains_and_helps() {
        let samples: Vec<&[u8]> = vec![
            b"HTTP/1.1 200 OK\r\nContent-Type: application/json\r\n\r\n{\"a\":1}",
            b"HTTP/1.1 200 OK\r\nContent-Type: application/json\r\n\r\n{\"b\":2}",
            b"HTTP/1.1 404 Not Found\r\nContent-Type: application/json\r\n\r\n{}",
            b"HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\nhi",
            b"HTTP/1.1 500 Error\r\nContent-Type: text/plain\r\n\r\nerr",
        ];
        let dict = train_cover(
            &samples,
            CoverParams {
                d: 6,
                dict_size: 512,
                min_freq: 2,
                step: 1,
            },
        )
        .unwrap();
        assert!(!dict.data.is_empty());

        let msg = b"HTTP/1.1 200 OK\r\nContent-Type: application/json\r\n\r\n{\"x\":9}";
        let plain = compress(msg, &CompressOptions::default().level(6).threads(false)).unwrap();
        let with = compress(
            msg,
            &CompressOptions::default()
                .level(6)
                .threads(false)
                .dictionary(dict.clone()),
        )
        .unwrap();
        assert!(
            with.len() <= plain.len() + 8,
            "cover dict should not hurt: with={} plain={}",
            with.len(),
            plain.len()
        );
        let d = decompress_with_options(
            &with,
            &DecompressOptions {
                dictionary: Some(dict),
                ..Default::default()
            },
        )
        .unwrap();
        assert_eq!(d, msg);
    }
}