structured-zstd 0.0.54

//! Shared helpers and constants consumed by every match finder (Simple
//! / Dfast / Row / Hc). Extracted from `match_generator.rs` as part of
//! #111 Phase 1b so later commits can move each matcher into its own
//! module without duplicating these primitives.
//!
//! Phase 1c additionally hosts `common_prefix_len` and the shared
//! match-finder constants (`MIN_MATCH_LEN`, `FAST_HASH_FILL_STEP`,
//! `INCOMPRESSIBLE_SKIP_STEP`) here so the per-matcher modules
//! (`simple`, `dfast`, `row`) depend on this shared infra rather than on
//! each other — breaking the `match_generator` ↔ `simple` reverse
//! dependency the original Phase 1c split introduced.
//!
//! Mechanical move — names, signatures, and bodies are byte-for-byte
//! identical to the pre-extraction monolith; the only intentional API
//! change is `pub(crate)` visibility on the moved items.

use super::super::opt::types::MatchCandidate;
use crate::encoding::fastpath::FastpathKernel;

/// Minimum match length emitted by the Simple / level-1 matcher (and the
/// upstream zstd `ZSTD_fast.c` baseline). Lives here so every matcher and the
/// `match_generator` driver can reference the shared minimum without
/// importing one matcher module from another.
pub(crate) const MIN_MATCH_LEN: usize = 5;
/// Hash-fill stride used by the Simple / level-1 fast pass when
/// backfilling the suffix store. Upstream zstd parity: matches
/// `ZSTD_FAST_HASH_FILL_STEP` in `zstd_fast.c`.
pub(crate) const FAST_HASH_FILL_STEP: usize = 3;
/// Stride the lazy / row matchers index a block they wrote off unsearched at.
///
/// Same question, same answer as the fast path's [`RAW_SKIP_INDEX_STEP`], which
/// this defers to: the block is not searched, so the only reason to index it is
/// a LATER block duplicating it, that duplicate is recognised on the seen-content
/// grid and then searched, and the search sweeps positions — so an entry every
/// stride bytes is met within a stride of scanning, immaterial against a
/// block-sized match. The two paths had drifted to different answers (8 here,
/// 512 there) and it was the whole cost of a skip: an entry per eight bytes is
/// 131,000 stores per mebibyte of input nothing will search.
///
/// Measured on the i9, three arms in one session (before, after, and the C
/// reference through `ffi_encode_loop_z000033`), `perf stat -r 3`, three rounds
/// each. Per run, cycles / instructions / wall clock:
///
/// Incompressible 1 MiB at level 5, 300 frames:
///
/// | arm | cycles | instructions | wall |
/// |---|---|---|---|
/// | before | 1.653-1.670 G | 1.9287 G | 0.402-0.408 s |
/// | after | 0.337-0.347 G | 0.3028 G | 0.087-0.089 s |
/// | reference | 1.007-1.068 G | 0.8330 G | 0.247-0.267 s |
///
/// A 1 MiB block repeated verbatim at level 19, 30 frames — the case the wider
/// stride costs bytes on:
///
/// | arm | cycles | instructions | wall | bytes |
/// |---|---|---|---|---|
/// | before | 0.807-0.839 G | 0.6231 G | 0.206-0.213 s | 524,365 |
/// | after | 0.082-0.084 G | 0.0776 G | 0.029-0.030 s | 524,871 |
/// | reference | 12.20-13.08 G | 5.5298 G | 2.95-3.16 s | 524,361 |
///
/// So the stride takes us from 1.58x of the reference to 0.33x on the first,
/// and the second costs 510 bytes in 524,871 (0.1%) against the reference while
/// running 150 times faster than it. Output is unchanged on 65 of 66
/// fixture-and-level rows; that level-19 row is the only one that moves.
pub(crate) const INCOMPRESSIBLE_SKIP_STEP: usize =
    crate::encoding::incompressible::RAW_SKIP_INDEX_STEP;

/// Length of the common prefix of two byte slices, capped at
/// `min(a.len(), b.len())`. Hot path on every match finder; dispatches to
/// the per-CPU `common_prefix_len_ptr` kernel (NEON / SSE4.2 / AVX2+BMI2 /
/// scalar) so the SIMD/CRC heavy lifting lives in one place. See
/// [`crate::encoding::fastpath`] for the per-CPU implementations.
#[inline(always)]
pub(crate) fn common_prefix_len(a: &[u8], b: &[u8]) -> usize {
    let max = a.len().min(b.len());
    // SAFETY: slice `a` / `b` guarantee at least their `len()` initialized
    // bytes; `max` is the minimum so both pointers are valid for `max`
    // bytes.
    unsafe {
        crate::encoding::fastpath::dispatch_common_prefix_len_ptr(a.as_ptr(), b.as_ptr(), max)
    }
}

/// As [`common_prefix_len`] but against an already-resolved [`FastpathKernel`].
/// Hot match-finder loops resolve the kernel once per block and pass it in,
/// so each byte-compare skips the per-call `select_kernel()` `OnceLock` atomic.
#[inline(always)]
pub(crate) fn common_prefix_len_with_kernel(kernel: FastpathKernel, a: &[u8], b: &[u8]) -> usize {
    let max = a.len().min(b.len());
    // SAFETY: as `common_prefix_len` — both pointers are valid for `max` bytes.
    unsafe {
        crate::encoding::fastpath::dispatch_common_prefix_len_ptr_with_kernel(
            kernel,
            a.as_ptr(),
            b.as_ptr(),
            max,
        )
    }
}

/// Pick the better of two candidate matches: longer wins, ties go to
/// the smaller offset (cheaper to encode and better for decompression
/// throughput).
pub(crate) fn best_len_offset_candidate(
    lhs: Option<MatchCandidate>,
    rhs: Option<MatchCandidate>,
) -> Option<MatchCandidate> {
    match (lhs, rhs) {
        (None, other) | (other, None) => other,
        (Some(lhs), Some(rhs)) => {
            if rhs.match_len > lhs.match_len
                || (rhs.match_len == lhs.match_len && rhs.offset < lhs.offset)
            {
                Some(rhs)
            } else {
                Some(lhs)
            }
        }
    }
}

/// Walk a candidate match backwards over the literal run so the matcher
/// can absorb literal bytes that happen to match the byte preceding the
/// candidate. Upstream zstd parity: equivalent to the back-extend done inside
/// every match finder before committing a sequence.
#[inline]
pub(crate) fn extend_backwards_shared(
    concat: &[u8],
    history_abs_start: usize,
    mut candidate_pos: usize,
    mut abs_pos: usize,
    mut match_len: usize,
    lit_len: usize,
) -> MatchCandidate {
    let min_abs_pos = abs_pos - lit_len;
    let concat_ptr = concat.as_ptr();
    let concat_len = concat.len();
    // SAFETY: loop guard `candidate_pos > history_abs_start` and
    // `abs_pos > min_abs_pos` keep both `candidate_pos - history_abs_start - 1`
    // and `abs_pos - history_abs_start - 1` strictly positive (no underflow).
    // Their upper bound is `concat.len() - 1` because both `candidate_pos` and
    // `abs_pos` point at currently-live history. Asserted in debug builds.
    while abs_pos > min_abs_pos && candidate_pos > history_abs_start {
        let cand_off = candidate_pos - history_abs_start - 1;
        let cur_off = abs_pos - history_abs_start - 1;
        debug_assert!(cand_off < concat_len && cur_off < concat_len);
        let cand_byte = unsafe { *concat_ptr.add(cand_off) };
        let cur_byte = unsafe { *concat_ptr.add(cur_off) };
        if cand_byte != cur_byte {
            break;
        }
        candidate_pos -= 1;
        abs_pos -= 1;
        match_len += 1;
    }
    MatchCandidate {
        start: abs_pos,
        offset: abs_pos - candidate_pos,
        match_len,
    }
}

/// Probe the 3 rep-code offsets (with the upstream zstd `ll0` ↦ `rep[0] - 1`
/// fallback) and return the best match found, if any. Hot path:
/// invoked once per encoded byte on lazy / Dfast / Row matchers
/// (~10% exclusive on the default-level profile).
#[inline(always)]
pub(crate) fn repcode_candidate_shared(
    kernel: FastpathKernel,
    concat: &[u8],
    history_abs_start: usize,
    offset_hist: [u32; 3],
    abs_pos: usize,
    lit_len: usize,
    min_match_len: usize,
) -> Option<MatchCandidate> {
    let current_idx = abs_pos - history_abs_start;
    if current_idx + min_match_len > concat.len() {
        return None;
    }
    // The 4-byte gate below relies on a first-4-byte mismatch implying the
    // match can never reach the acceptance floor.
    debug_assert!(min_match_len >= 4, "repcode gate requires min_match >= 4");

    // Called once per input byte (10% exclusive on default-level profile).
    // The previous form built an `[Option<usize>; 3]` and walked it via
    // `into_iter().flatten()`, which the compiler couldn't always unroll
    // through the conditional `then_some` on the last slot. Unroll the
    // 3-rep probe by hand: each branch is a couple of compares + one
    // `common_prefix_len` (already SIMD).
    let mut best: Option<MatchCandidate> = None;

    let (rep0, rep1, rep2_opt) = if lit_len == 0 {
        let r2 = if offset_hist[0] > 1 {
            Some(offset_hist[0] as usize - 1)
        } else {
            None
        };
        (offset_hist[1] as usize, offset_hist[2] as usize, r2)
    } else {
        (
            offset_hist[0] as usize,
            offset_hist[1] as usize,
            Some(offset_hist[2] as usize),
        )
    };

    macro_rules! probe {
        ($rep:expr) => {{
            let rep = $rep;
            if rep != 0 && rep <= abs_pos {
                let candidate_pos = abs_pos - rep;
                // Upstream zstd `MEM_read32` rep gate (`zstd_lazy.c` lazy loop): a
                // first-4-byte mismatch can never reach the
                // `>= min_match_len` floor (asserted >= 4 above), so reject
                // on one scalar compare instead of paying the SIMD count
                // call on every non-matching rep. In-bounds: `current_idx +
                // 4 <= concat.len()` from the entry guard, and
                // `candidate_idx < current_idx`.
                if candidate_pos >= history_abs_start {
                    let candidate_idx = candidate_pos - history_abs_start;
                    // Upstream zstd `MEM_read32` gate: one unaligned u32 compare. The
                    // slice-range form paid two bounds checks per rep probe
                    // (per input byte on the greedy/lazy levels).
                    // SAFETY: the entry guard established `current_idx +
                    // min_match_len <= concat.len()` with `min_match_len >= 4`
                    // (debug-asserted above), and `candidate_idx <
                    // current_idx`, so both 4-byte reads are in bounds.
                    let gate = unsafe {
                        let base = concat.as_ptr();
                        core::ptr::read_unaligned(base.add(candidate_idx).cast::<u32>())
                            == core::ptr::read_unaligned(base.add(current_idx).cast::<u32>())
                    };
                    if gate {
                        let match_len = common_prefix_len_with_kernel(
                            kernel,
                            &concat[candidate_idx..],
                            &concat[current_idx..],
                        );
                        if match_len >= min_match_len {
                            let candidate = extend_backwards_shared(
                                concat,
                                history_abs_start,
                                candidate_pos,
                                abs_pos,
                                match_len,
                                lit_len,
                            );
                            best = best_len_offset_candidate(best, Some(candidate));
                        }
                    }
                }
            }
        }};
    }

    probe!(rep0);
    probe!(rep1);
    if let Some(rep2) = rep2_opt {
        probe!(rep2);
    }
    best
}