zexc 1.1.0

zex native lossless compressor — CLI zexc, library zexc, files *.zex
Documentation
//! Pure-Rust LZ4 block compressor / decompressor.
//!
//! Implements the [LZ4 Block Format](https://github.com/lz4/lz4/blob/dev/doc/lz4_Block_format.md)
//! as documented in LZ4 1.10.0 — no dependency on liblz4 or `lz4_flex`.
//!
//! Design notes (from LZ4 source philosophy):
//! - Hash-table match finder, 4-byte min match, 64 KiB window (16-bit offsets)
//! - Last 5 bytes always literals; last match ≥ 12 bytes from end
//! - Extremely fast encode & decode paths

use crate::format::block::BlockType;
use crate::{Error, Result};

const MIN_MATCH: usize = 4;
const LAST_LITERALS: usize = 5;
const MATCH_SAFEGUARD: usize = 12;
const HASH_LOG: usize = 12; // 4K entries — good speed/ratio for Fast mode
const HASH_SIZE: usize = 1 << HASH_LOG;
const MAX_DISTANCE: usize = 65535;

#[inline]
fn hash4(data: &[u8], pos: usize) -> usize {
    let v = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap());
    // Multiplicative hash (same family as LZ4_hash4)
    ((v.wrapping_mul(2654435761)) >> (32 - HASH_LOG)) as usize
}

#[inline]
fn common_prefix_len(a: &[u8], b: &[u8]) -> usize {
    let n = a.len().min(b.len());
    let mut i = 0;
    // Word-wise compare
    while i + 8 <= n {
        let x = u64::from_le_bytes(a[i..i + 8].try_into().unwrap());
        let y = u64::from_le_bytes(b[i..i + 8].try_into().unwrap());
        if x != y {
            return i + ((x ^ y).trailing_zeros() as usize / 8);
        }
        i += 8;
    }
    while i < n && a[i] == b[i] {
        i += 1;
    }
    i
}

/// Write LZ4 variable-length size extension (for lit/match lengths ≥ 15).
fn write_var_len(out: &mut Vec<u8>, mut len: usize) {
    while len >= 255 {
        out.push(255);
        len -= 255;
    }
    out.push(len as u8);
}

/// Compress `src` into LZ4 block format. Returns compressed bytes.
pub fn compress(src: &[u8], _level: u8) -> Result<Vec<u8>> {
    let mut out = Vec::with_capacity(src.len() + src.len() / 255 + 16);
    compress_into(src, &mut out, _level)?;
    Ok(out)
}

/// Compress into an existing buffer (appended).
pub fn compress_into(src: &[u8], out: &mut Vec<u8>, _level: u8) -> Result<()> {
    let n = src.len();
    if n == 0 {
        // Empty block: single zero token (no literals, no match)
        out.push(0);
        return Ok(());
    }

    // Tiny inputs: store as all-literals
    if n < MATCH_SAFEGUARD {
        emit_last_literals(out, src);
        return Ok(());
    }

    let mut hash_table = [0u32; HASH_SIZE];
    let mut anchor = 0usize;
    let iend = n;
    let mflimit = iend.saturating_sub(MATCH_SAFEGUARD);
    let match_limit = iend - LAST_LITERALS;

    // Skip first byte (need history for matches)
    let mut ip = 1usize;

    while ip <= mflimit {
        // Find match
        let h = hash4(src, ip);
        let ref_pos = hash_table[h] as usize;
        hash_table[h] = ip as u32;

        let distance = ip.wrapping_sub(ref_pos);
        if ref_pos == 0
            || distance == 0
            || distance > MAX_DISTANCE
            || ref_pos >= ip
            || ip + MIN_MATCH > match_limit
            || src[ref_pos..ref_pos + MIN_MATCH] != src[ip..ip + MIN_MATCH]
        {
            ip += 1;
            continue;
        }

        // Extend match forward
        let mut match_len = MIN_MATCH
            + common_prefix_len(
                &src[ref_pos + MIN_MATCH..match_limit],
                &src[ip + MIN_MATCH..match_limit],
            );

        // Also try to extend match backward into literals (LZ4 style optional)
        let mut match_pos = ref_pos;
        let mut lit_start = ip;
        while lit_start > anchor && match_pos > 0 && src[lit_start - 1] == src[match_pos - 1] {
            lit_start -= 1;
            match_pos -= 1;
            match_len += 1;
        }

        let lit_len = lit_start - anchor;
        // After backward extend, match starts at (lit_start / match_pos) with same distance.
        let offset = (lit_start - match_pos) as u16;

        // Token
        let mut token = 0u8;
        let token_lit = if lit_len >= 15 { 15 } else { lit_len };
        let ml_stored = match_len - MIN_MATCH;
        let token_ml = if ml_stored >= 15 { 15 } else { ml_stored };
        token |= (token_lit as u8) << 4;
        token |= token_ml as u8;
        out.push(token);

        if lit_len >= 15 {
            write_var_len(out, lit_len - 15);
        }
        out.extend_from_slice(&src[anchor..lit_start]);

        out.push((offset & 0xFF) as u8);
        out.push((offset >> 8) as u8);

        if ml_stored >= 15 {
            write_var_len(out, ml_stored - 15);
        }

        // Advance
        ip = lit_start + match_len;
        anchor = ip;

        // Fill hash for skipped positions (step=1 for better ratio on Fast)
        let fill_end = ip.min(mflimit + 1);
        let mut p = lit_start + 1;
        while p < fill_end {
            hash_table[hash4(src, p)] = p as u32;
            p += 1;
        }
    }

    // Last literals
    emit_last_literals(out, &src[anchor..]);
    Ok(())
}

fn emit_last_literals(out: &mut Vec<u8>, lits: &[u8]) {
    let lit_len = lits.len();
    let token_lit = if lit_len >= 15 { 15 } else { lit_len };
    out.push((token_lit as u8) << 4); // ml = 0
    if lit_len >= 15 {
        write_var_len(out, lit_len - 15);
    }
    out.extend_from_slice(lits);
}

/// Decompress an LZ4 block into a buffer of exact `uncompressed_size`.
pub fn decompress(src: &[u8], uncompressed_size: usize) -> Result<Vec<u8>> {
    let mut out = Vec::with_capacity(uncompressed_size);
    decompress_into(src, &mut out, uncompressed_size)?;
    Ok(out)
}

/// Decompress into `dst` (cleared first).
pub fn decompress_into(src: &[u8], dst: &mut Vec<u8>, uncompressed_size: usize) -> Result<()> {
    dst.clear();
    dst.reserve(uncompressed_size);

    let mut ip = 0usize;
    let src_end = src.len();

    while ip < src_end {
        let token = src[ip];
        ip += 1;

        // Literals
        let mut lit_len = (token >> 4) as usize;
        if lit_len == 15 {
            loop {
                if ip >= src_end {
                    return Err(Error::Decompression("lz4: truncated lit length".into()));
                }
                let b = src[ip];
                ip += 1;
                lit_len += b as usize;
                if b != 255 {
                    break;
                }
            }
        }

        if lit_len > 0 {
            if ip + lit_len > src_end {
                return Err(Error::Decompression("lz4: truncated literals".into()));
            }
            if dst.len() + lit_len > uncompressed_size {
                return Err(Error::Decompression("lz4: output overflow (literals)".into()));
            }
            dst.extend_from_slice(&src[ip..ip + lit_len]);
            ip += lit_len;
        }

        // End of block if no more input (last sequence is literals-only)
        if ip >= src_end {
            break;
        }

        // Offset
        if ip + 2 > src_end {
            return Err(Error::Decompression("lz4: truncated offset".into()));
        }
        let offset = u16::from_le_bytes([src[ip], src[ip + 1]]) as usize;
        ip += 2;
        if offset == 0 {
            return Err(Error::Decompression("lz4: invalid offset 0".into()));
        }
        if offset > dst.len() {
            return Err(Error::Decompression(format!(
                "lz4: offset {offset} > decoded {}",
                dst.len()
            )));
        }

        // Match length
        let mut match_len = (token & 0x0F) as usize + MIN_MATCH;
        if (token & 0x0F) == 15 {
            loop {
                if ip >= src_end {
                    return Err(Error::Decompression("lz4: truncated match length".into()));
                }
                let b = src[ip];
                ip += 1;
                match_len += b as usize;
                if b != 255 {
                    break;
                }
            }
        }

        if dst.len() + match_len > uncompressed_size {
            return Err(Error::Decompression("lz4: output overflow (match)".into()));
        }

        // Copy match (may overlap — handle RLE-style carefully)
        let match_start = dst.len() - offset;
        for i in 0..match_len {
            let b = dst[match_start + i];
            dst.push(b);
        }
    }

    if dst.len() != uncompressed_size {
        return Err(Error::SizeMismatch {
            expected: uncompressed_size as u64,
            actual: dst.len() as u64,
        });
    }
    Ok(())
}

/// [`BlockCompressor`] for LZ4.
pub struct Lz4Compressor;

impl crate::algorithms::BlockCompressor for Lz4Compressor {
    fn compress_block(&self, src: &[u8], dst: &mut Vec<u8>, level: u8) -> Result<BlockType> {
        dst.clear();
        compress_into(src, dst, level)?;
        // If expansion, fall back to raw is handled by encoder
        Ok(BlockType::Lz4)
    }
}

/// [`BlockDecompressor`] for LZ4.
pub struct Lz4Decompressor;

impl crate::algorithms::BlockDecompressor for Lz4Decompressor {
    fn decompress_block(
        &self,
        src: &[u8],
        dst: &mut Vec<u8>,
        uncompressed_size: usize,
    ) -> Result<()> {
        decompress_into(src, dst, uncompressed_size)
    }
}

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

    #[test]
    fn roundtrip_text() {
        let src = b"Hello Hello Hello Hello LZ4 pure Rust block format test!!!!";
        let c = compress(src, 1).unwrap();
        let d = decompress(&c, src.len()).unwrap();
        assert_eq!(d, src);
    }

    #[test]
    fn roundtrip_zeros() {
        let src = vec![0u8; 4096];
        let c = compress(&src, 1).unwrap();
        assert!(c.len() < src.len());
        let d = decompress(&c, src.len()).unwrap();
        assert_eq!(d, src);
    }

    #[test]
    fn roundtrip_randomish() {
        let mut src = Vec::new();
        for i in 0..5000u32 {
            src.extend_from_slice(&(i.wrapping_mul(2654435761)).to_le_bytes());
        }
        let c = compress(&src, 1).unwrap();
        let d = decompress(&c, src.len()).unwrap();
        assert_eq!(d, src);
    }

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