zexc 1.2.1

zex native lossless compressor — CLI zexc, library zexc, files *.zex
Documentation
//! SIMD / wide-load helpers for the native codec.
//!
//! Stable Rust (no nightly `std::simd`). Paths:
//! - **x86_64 + `simd` feature**: runtime-dispatched AVX2 (32B) / SSE2 (16B)
//!   via `core::arch::x86_64` intrinsics, detected once with
//!   `is_x86_feature_detected!` (cheap: a cached atomic check).
//! - **aarch64 + `simd` feature**: NEON 16-byte compares via
//!   `core::arch::aarch64` (NEON is baseline on aarch64, no detection needed).
//! - **Portable fallback**: 16-byte (`u128`) then 8-byte (`u64`) compares,
//!   used when `simd` is off or on other architectures.
//!
//! Callers only see safe functions; all `unsafe` (intrinsics, raw prefetch)
//! is contained in this module.

use alloc::vec::Vec;

/// Count matching prefix bytes of `a` and `b`, at most `max`.
#[inline]
pub fn match_len(a: &[u8], b: &[u8], max: usize) -> usize {
    let n = a.len().min(b.len()).min(max);
    if n == 0 {
        return 0;
    }
    match_len_inner(a, b, n)
}

#[inline]
fn match_len_inner(a: &[u8], b: &[u8], n: usize) -> usize {
    // AVX2 needs the OS to have opted the process into saving/restoring the
    // wider YMM register state (XCR0) — `is_x86_feature_detected!` confirms
    // that, but it's a `std`-only macro (the check itself needs the OS'
    // cooperation, not just the CPU's). On bare-metal/no_std targets we
    // can't safely assume that state is set up, so AVX2 stays std-only.
    #[cfg(all(target_arch = "x86_64", feature = "simd", feature = "std"))]
    {
        if std::is_x86_feature_detected!("avx2") {
            // SAFETY: feature checked above; slices cover `n` bytes (caller-verified).
            return unsafe { arch_x86::match_len_avx2(a, b, n) };
        }
    }
    #[cfg(all(target_arch = "x86_64", feature = "simd"))]
    {
        // SAFETY: SSE2 is mandated by the x86_64 ABI — always present, no
        // runtime detection (or OS XSAVE opt-in) required, unlike AVX2.
        return unsafe { arch_x86::match_len_sse2(a, b, n) };
    }
    #[cfg(all(target_arch = "aarch64", feature = "simd"))]
    {
        // SAFETY: NEON is mandatory on aarch64 — no runtime check needed.
        return unsafe { arch_aarch64::match_len_neon(a, b, n) };
    }
    #[allow(unreachable_code)]
    match_len_portable(a, b, n)
}

/// Portable 16-then-8-byte wide compare. Also the tail/fallback for the
/// SIMD paths once fewer than a full vector width remains.
#[inline]
fn match_len_portable(a: &[u8], b: &[u8], n: usize) -> usize {
    let mut i = 0usize;

    while i + 16 <= n {
        let x = read_u128(a, i);
        let y = read_u128(b, i);
        if x != y {
            return i + first_diff_byte_u128(x, y);
        }
        i += 16;
    }

    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
}

#[cfg(all(target_arch = "x86_64", feature = "simd"))]
mod arch_x86 {
    use super::match_len_portable;
    use core::arch::x86_64::*;

    /// AVX2: compare 32 bytes at a time with `vpcmpeqb` + `vpmovmskb`.
    ///
    /// Only reachable with `std` (see the `std`-gated caller in
    /// `match_len_inner` — detection needs OS-confirmed XSAVE state).
    ///
    /// # Safety
    /// Caller must have verified AVX2 support (`is_x86_feature_detected!`).
    #[cfg(feature = "std")]
    #[target_feature(enable = "avx2")]
    pub unsafe fn match_len_avx2(a: &[u8], b: &[u8], n: usize) -> usize {
        let mut i = 0usize;
        while i + 32 <= n {
            // SAFETY: bounds checked by the loop condition (i + 32 <= n <= a/b.len()).
            let x = unsafe { _mm256_loadu_si256(a.as_ptr().add(i).cast()) };
            let y = unsafe { _mm256_loadu_si256(b.as_ptr().add(i).cast()) };
            // Safe: target_feature = "avx2" on this fn covers these intrinsics.
            let eq = _mm256_cmpeq_epi8(x, y);
            let mask = _mm256_movemask_epi8(eq) as u32;
            if mask != u32::MAX {
                return i + (!mask).trailing_zeros() as usize;
            }
            i += 32;
        }
        i + match_len_portable(&a[i..], &b[i..], n - i)
    }

    /// SSE2: compare 16 bytes at a time with `pcmpeqb` + `pmovmskb`.
    ///
    /// # Safety
    /// Caller must have verified SSE2 support (baseline on x86_64, but
    /// gated behind `is_x86_feature_detected!` for consistency).
    #[target_feature(enable = "sse2")]
    pub unsafe fn match_len_sse2(a: &[u8], b: &[u8], n: usize) -> usize {
        let mut i = 0usize;
        while i + 16 <= n {
            // SAFETY: bounds checked by the loop condition (i + 16 <= n <= a/b.len()).
            let x = unsafe { _mm_loadu_si128(a.as_ptr().add(i).cast()) };
            let y = unsafe { _mm_loadu_si128(b.as_ptr().add(i).cast()) };
            // Safe: target_feature = "sse2" on this fn covers these intrinsics.
            let eq = _mm_cmpeq_epi8(x, y);
            let mask = _mm_movemask_epi8(eq) as u32 & 0xFFFF;
            if mask != 0xFFFF {
                return i + (!mask & 0xFFFF).trailing_zeros() as usize;
            }
            i += 16;
        }
        i + match_len_portable(&a[i..], &b[i..], n - i)
    }
}

#[cfg(all(target_arch = "aarch64", feature = "simd"))]
mod arch_aarch64 {
    use super::match_len_portable;
    use core::arch::aarch64::*;

    /// NEON: compare 16 bytes at a time with `vceqq_u8`.
    ///
    /// # Safety
    /// NEON is mandatory on all aarch64 targets, so this is always sound to call.
    #[target_feature(enable = "neon")]
    pub unsafe fn match_len_neon(a: &[u8], b: &[u8], n: usize) -> usize {
        let mut i = 0usize;
        while i + 16 <= n {
            // SAFETY: bounds checked by the loop condition (i + 16 <= n <= a/b.len()).
            let x = unsafe { vld1q_u8(a.as_ptr().add(i)) };
            let y = unsafe { vld1q_u8(b.as_ptr().add(i)) };
            let eq = unsafe { vceqq_u8(x, y) };
            // Fold 16 lanes of 0x00/0xFF into a per-byte-min to find the first mismatch.
            let min = unsafe { vminvq_u8(eq) };
            if min == 0 {
                for k in 0..16 {
                    if a[i + k] != b[i + k] {
                        return i + k;
                    }
                }
                unreachable!("vminvq_u8 reported a mismatch but byte scan found none");
            }
            i += 16;
        }
        i + match_len_portable(&a[i..], &b[i..], n - i)
    }
}

/// Prefetch hint for upcoming match-finder candidates (best-effort, safe).
///
/// Used to hide hash-chain memory latency: issued for the next chain hop
/// while the current candidate's match length is still being computed.
#[inline]
pub fn prefetch_read(ptr: *const u8) {
    #[cfg(target_arch = "x86_64")]
    {
        // SAFETY: `_mm_prefetch` never faults, even on an invalid/dangling
        // pointer — it's a hint, not a dereference. SSE is baseline on x86_64.
        unsafe {
            ::core::arch::x86_64::_mm_prefetch::<{ ::core::arch::x86_64::_MM_HINT_T0 }>(
                ptr.cast::<i8>(),
            );
        }
    }
    #[cfg(target_arch = "aarch64")]
    {
        // SAFETY: `prefetch` intrinsics aren't stabilized on aarch64; the
        // pointer is never dereferenced here, so this is a true no-op.
        let _ = ptr;
    }
    #[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
    {
        let _ = ptr;
    }
}

#[inline]
fn read_u128(data: &[u8], pos: usize) -> u128 {
    u128::from_le_bytes(data[pos..pos + 16].try_into().unwrap())
}

#[inline]
fn first_diff_byte_u128(x: u128, y: u128) -> usize {
    ((x ^ y).trailing_zeros() as usize) / 8
}

/// Fast equality check of 4 bytes at `a[pos]` and `b[pos]`.
#[inline]
pub fn match4(a: &[u8], ap: usize, b: &[u8], bp: usize) -> bool {
    u32::from_le_bytes(a[ap..ap + 4].try_into().unwrap())
        == u32::from_le_bytes(b[bp..bp + 4].try_into().unwrap())
}

/// Copy `len` bytes from history into `dst` (overlap-safe RLE).
/// History is only the already-decoded output (no dictionary).
#[inline]
pub fn copy_match(dst: &mut Vec<u8>, offset: usize, len: usize) {
    copy_match_with_history(dst, offset, len, &[]);
}

/// Copy `len` bytes using virtual history `[dict | dst…]`.
///
/// `offset` is distance backward from the current end of that virtual buffer.
#[inline]
pub fn copy_match_with_history(dst: &mut Vec<u8>, offset: usize, len: usize, dict: &[u8]) {
    debug_assert!(offset > 0);
    let dlen = dict.len();
    debug_assert!(offset <= dlen + dst.len());

    // Fast path: pure RLE in output only (offset==1, fully in dst)
    if dict.is_empty() && offset == 1 && !dst.is_empty() {
        let b = dst[dst.len() - 1];
        dst.resize(dst.len() + len, b);
        return;
    }

    // Fast path: entire match lies in output, non-overlapping
    if offset <= dst.len() && offset >= len {
        let start = dst.len() - offset;
        let chunk: Vec<u8> = dst[start..start + len].to_vec();
        dst.extend_from_slice(&chunk);
        return;
    }

    // General path (dict and/or overlap)
    dst.reserve(len);
    for _ in 0..len {
        let from = dlen + dst.len() - offset;
        let b = if from < dlen {
            dict[from]
        } else {
            dst[from - dlen]
        };
        dst.push(b);
    }
}

/// Report whether the build enabled the `simd` feature (for `zex info` / debug).
pub fn simd_enabled() -> bool {
    cfg!(feature = "simd")
}

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

    #[test]
    fn match_len_basic() {
        let a = b"HelloHelloXXXX";
        let b = b"HelloHelloYYYY";
        assert_eq!(match_len(a, b, 100), 10);
    }

    #[test]
    fn match_len_long() {
        let a = vec![0xABu8; 1000];
        let mut b = vec![0xABu8; 1000];
        b[777] = 0x00;
        assert_eq!(match_len(&a, &b, 1000), 777);
    }

    /// Exercise the AVX2/SSE2/NEON vector-width boundaries (32 and 16 bytes)
    /// plus the scalar tail, since a single mismatched lane anywhere in a
    /// vector must still resolve to the exact first-differing byte index.
    #[test]
    fn match_len_vector_width_boundaries() {
        for total in [0usize, 1, 7, 8, 15, 16, 17, 31, 32, 33, 63, 64, 65, 100] {
            for diff_at in 0..total {
                let a = vec![0x5Au8; total];
                let mut b = a.clone();
                b[diff_at] = 0xA5;
                assert_eq!(
                    match_len(&a, &b, total),
                    diff_at,
                    "total={total} diff_at={diff_at}"
                );
            }
            // No mismatch at all within `total`.
            let a = vec![0x5Au8; total];
            let b = a.clone();
            assert_eq!(match_len(&a, &b, total), total, "total={total} no diff");
        }
    }

    #[test]
    fn match_len_respects_max_cap() {
        let a = vec![0x11u8; 100];
        let b = vec![0x11u8; 100];
        assert_eq!(match_len(&a, &b, 40), 40);
    }

    /// Call each x86 intrinsic path directly so CI hosts without AVX2 still
    /// verify the AVX2 code (and vice versa) — `match_len`'s runtime
    /// dispatch would otherwise silently skip whichever path the host CPU
    /// doesn't support.
    #[test]
    #[cfg(all(target_arch = "x86_64", feature = "simd", feature = "std"))]
    fn match_len_x86_paths_agree_with_portable() {
        for total in [0usize, 1, 15, 16, 17, 31, 32, 33, 65, 100] {
            for diff_at in 0..total {
                let a = vec![0x5Au8; total];
                let mut b = a.clone();
                b[diff_at] = 0xA5;
                let expected = match_len_portable(&a, &b, total);
                assert_eq!(expected, diff_at);

                if std::is_x86_feature_detected!("avx2") {
                    // SAFETY: feature checked above.
                    let got = unsafe { arch_x86::match_len_avx2(&a, &b, total) };
                    assert_eq!(got, expected, "avx2 total={total} diff_at={diff_at}");
                }
                if std::is_x86_feature_detected!("sse2") {
                    // SAFETY: feature checked above.
                    let got = unsafe { arch_x86::match_len_sse2(&a, &b, total) };
                    assert_eq!(got, expected, "sse2 total={total} diff_at={diff_at}");
                }
            }
        }
    }

    /// `no_std`-safe twin of the test above: SSE2 needs no OS-confirmed
    /// detection (it's x86_64 ABI baseline), so this runs under any config.
    #[test]
    #[cfg(all(target_arch = "x86_64", feature = "simd"))]
    fn match_len_sse2_agrees_with_portable_no_std() {
        for total in [0usize, 1, 15, 16, 17, 31, 32, 33, 65, 100] {
            for diff_at in 0..total {
                let a = vec![0x5Au8; total];
                let mut b = a.clone();
                b[diff_at] = 0xA5;
                let expected = match_len_portable(&a, &b, total);
                // SAFETY: SSE2 is mandatory on x86_64.
                let got = unsafe { arch_x86::match_len_sse2(&a, &b, total) };
                assert_eq!(got, expected, "sse2 total={total} diff_at={diff_at}");
            }
        }
    }

    #[test]
    fn copy_match_rle() {
        let mut d = vec![0x41u8];
        copy_match(&mut d, 1, 10);
        assert_eq!(d, vec![0x41u8; 11]);
    }

    #[test]
    fn copy_match_overlap() {
        let mut d = vec![1, 2, 3, 4];
        copy_match(&mut d, 3, 6); // from [2,3,4,...]
        assert_eq!(&d[..4], &[1, 2, 3, 4]);
        assert_eq!(d.len(), 10);
    }
}