structured-zstd 0.2.2

//! Binary-tree match finder used by `BtOpt` / `BtUltra` / `BtUltra2`.
//!
//! Hosts the BT-side per-frame state: the upstream zstd `optStatePtr_t` cost
//! model (`opt_state`), the optimal-parser scratch buffers
//! (`opt_*_scratch` / `opt_*_generation` / `opt_*_stamp`), and the
//! LDM long-distance match buffer (`ldm_sequences`). Method bodies
//! (BT walk, `bt_insert_range`, `bt_update_tree_until`,
//! `build_optimal_plan*`, `collect_optimal_candidates*`,
//! `emit_optimal_plan`, …) still live on `HcMatchGenerator` and will
//! move onto `impl BtMatcher` once Stage 3b threads
//! `&mut MatchTable` through them — this stage establishes the
//! ownership boundary mirror to Stage 1 (`MatchTable`) and Stage 2
//! (`HcMatcher`).
//!
//! Upstream zstd parity reference: `lib/compress/zstd_opt.c`,
//! `ZSTD_compressBlock_opt_generic` and friends.

#![allow(dead_code)]

use alloc::boxed::Box;
use alloc::vec::Vec;
use core::mem::MaybeUninit;

use super::cost_model::{HC_MAX_LIT, HcOptState, HcOptimalCostProfile};
use super::opt::ldm::{HcOptLdmState, HcRawSeq, HcRawSeqStore};
use super::opt::types::{HcOptimalNode, HcOptimalPlanBuffers, HcOptimalSequence, MatchCandidate};

/// Maximum offset reachable by the HC3 short-match probe. Upstream zstd
/// parity: keeps the 3-byte side table from emitting offsets that
/// the main BT/HC paths would address more efficiently. Used inside
/// the `hash3_candidate_body!` macro that the kernel-specific
/// variants below expand.
pub(crate) const HC3_MAX_OFFSET: usize = 1 << 18;

/// Binary-tree matcher state used by the `BtOpt` / `BtUltra` /
/// `BtUltra2` parse modes. Owns the cost model and the per-frame
/// scratch arenas; the actual BT pointer-pair table lives on the
/// shared [`super::match_table::storage::MatchTable`].
#[derive(Clone)]
pub(crate) struct BtMatcher {
    /// Upstream zstd `optStatePtr_t` — Huffman / FSE-derived literal and
    /// sequence-symbol cost tables that drive the optimal parser.
    pub(crate) opt_state: HcOptState,
    /// Per-frame scratch for the optimal-parse node stream: `HC_OPT_NODE_LEN`
    /// cells allocated once and never filled, like upstream zstd's
    /// workspace-carved `opt[ZSTD_OPT_NUM]`. The DP never reads a cell it has
    /// not written in the same call (see [`HcOptimalPlanBuffers::nodes`]).
    pub(crate) opt_nodes_scratch: Box<[MaybeUninit<HcOptimalNode>]>,
    /// SoA companion to `opt_nodes_scratch`: the running DP price for each
    /// node, split out of `HcOptimalNode` into its own contiguous `u32`
    /// array so the optimal-parser inner price-set loop can SIMD-compare a
    /// run of consecutive node prices with a single vector load (the 28-byte
    /// AoS node stride would otherwise force a strided gather). Same length
    /// as `opt_nodes_scratch`; index `i` is the price of node `i`.
    pub(crate) opt_node_prices_scratch: Box<[MaybeUninit<u32>]>,
    /// Per-frame scratch for collected match candidates.
    pub(crate) opt_candidates_scratch: Vec<MatchCandidate>,
    /// Per-frame scratch for the final emitted node stream.
    pub(crate) opt_store_scratch: Vec<HcOptimalNode>,
    /// Per-segment plan buffer (parse → encode hand-off).
    pub(crate) opt_segment_plan_scratch: Vec<HcOptimalSequence>,
    /// `btultra2` seed-pass plan buffer.
    pub(crate) opt_seed_plan_scratch: Vec<HcOptimalSequence>,
    /// Single backing allocation for the LL/ML price caches as `[price,
    /// generation]` pairs (see [`HcOptimalPlanBuffers::price_arena`]).
    /// Replaces four separate `Vec<u32>` with one boxed slice of two
    /// fixed-stride pair regions: one base pointer + offsets, like upstream
    /// zstd's single opt workspace. `stamp` counters are the per-pass
    /// generation tags that let the parser skip re-zeroing the price cells.
    pub(crate) opt_price_arena: alloc::boxed::Box<[[u32; 2]]>,
    pub(crate) opt_ll_price_stamp: u32,
    /// Cached literal-symbol cost lookup (per-symbol fixed array).
    pub(crate) opt_lit_price_scratch: [u32; HC_MAX_LIT + 1],
    pub(crate) opt_lit_price_generation: [u32; HC_MAX_LIT + 1],
    pub(crate) opt_lit_price_stamp: u32,
    pub(crate) opt_ml_price_stamp: u32,
    /// Long-distance match (LDM) candidates seeded into the optimal
    /// parser: the driver's long-distance matcher fills them for each block
    /// before the parse, which drains them as it advances. Empty while the
    /// frame runs without it.
    pub(crate) ldm_sequences: Vec<HcRawSeq>,
}

impl BtMatcher {
    /// BT/HC hash MLS (minimum-length-segment) parameter. Upstream zstd
    /// parity: even when `minMatch == 3` (btultra2), the main BT/HC
    /// hash still goes through `ZSTD_hashPtr(…, mls)` which falls
    /// back to the default `case 4` in
    /// `zstd_compress_internal.h`. The 3-byte path is a separate HC3
    /// side table only.
    pub(crate) const HASH_MLS: usize = 4;

    /// Steady-state workspace budget for one boxed matcher: the inline
    /// payload (`HcOptState` cost tables, lit-price arrays) plus the
    /// retained scratch arenas at their growth bounds — node frontier and
    /// emitted store (`HC_OPT_NODE_LEN` nodes each, including the `+2`
    /// lookahead slack), the SoA node-price companion (`HC_OPT_NODE_LEN`
    /// `u32`s), the consolidated price arena (`HC_OPT_PRICE_ARENA_LEN`
    /// `[price, generation]` pairs, LL and ML regions), the per-segment plan
    /// buffers, and the candidate ladder (`MAX_HC_SEARCH_DEPTH`). LDM is
    /// opt-in and excluded (`ldm_sequences` stays empty on every level
    /// preset). Kept next to the struct so the estimator and the real
    /// retained layout evolve together.
    pub(crate) fn estimated_workspace_bytes() -> usize {
        use super::cost_model::{HC_OPT_NODE_LEN, HC_OPT_NUM, HC_OPT_PRICE_ARENA_LEN};
        use super::hc::MAX_HC_SEARCH_DEPTH;
        let frontier = HC_OPT_NUM + 1;
        core::mem::size_of::<Self>()
            + 2 * HC_OPT_NODE_LEN * core::mem::size_of::<HcOptimalNode>()
            + HC_OPT_NODE_LEN * core::mem::size_of::<u32>()
            + HC_OPT_PRICE_ARENA_LEN * core::mem::size_of::<[u32; 2]>()
            + 2 * frontier * core::mem::size_of::<HcOptimalSequence>()
            + MAX_HC_SEARCH_DEPTH * core::mem::size_of::<MatchCandidate>()
    }

    /// Append `candidate` to `out` if it's strictly longer than the
    /// best length seen so far (and at least `min_match_len`). Maintains
    /// `best_len_for_skip` so subsequent calls only keep strictly
    /// improving candidates. Pure associated function — no BtMatcher
    /// state needed, just the candidate ladder bookkeeping.
    pub(crate) fn push_candidate_ladder(
        out: &mut Vec<MatchCandidate>,
        best_len_for_skip: &mut usize,
        candidate: MatchCandidate,
        min_match_len: usize,
    ) -> bool {
        if candidate.match_len < min_match_len {
            return false;
        }
        if candidate.match_len > *best_len_for_skip {
            out.push(candidate);
            *best_len_for_skip = candidate.match_len;
            return true;
        }
        false
    }

    /// Append the long-distance candidate after the search when it is at
    /// least `min_match_len` and longer than every candidate the search found
    /// (upstream zstd `ZSTD_optLdm_maybeAddMatch`, zstd_opt.c). The search
    /// ladder keeps `out` sorted by strictly increasing length, so its last
    /// entry is the bar.
    #[inline(always)]
    pub(crate) fn push_ldm_candidate(
        out: &mut Vec<MatchCandidate>,
        ldm: MatchCandidate,
        min_match_len: usize,
    ) {
        let mut best_len = out.last().map_or(0, |c| c.match_len);
        let _ = Self::push_candidate_ladder(out, &mut best_len, ldm, min_match_len);
    }

    pub(crate) fn new() -> Self {
        Self {
            opt_state: HcOptState::new(),
            // Empty boxed slices: no allocation until the optimal parser
            // first runs (non-BT strategies never touch these), matching
            // the prior lazy `Vec::new()` + grow behaviour.
            opt_nodes_scratch: Box::default(),
            opt_node_prices_scratch: Box::default(),
            opt_candidates_scratch: Vec::new(),
            opt_store_scratch: Vec::new(),
            opt_segment_plan_scratch: Vec::new(),
            opt_seed_plan_scratch: Vec::new(),
            opt_price_arena: alloc::boxed::Box::default(),
            opt_ll_price_stamp: 0,
            opt_lit_price_scratch: [0; HC_MAX_LIT + 1],
            opt_lit_price_generation: [0; HC_MAX_LIT + 1],
            opt_lit_price_stamp: 0,
            opt_ml_price_stamp: 0,
            ldm_sequences: Vec::new(),
        }
    }

    /// Heap bytes the optimal-parser scratch buffers hold. The fixed-size
    /// price arrays and `opt_state` are inline (counted by the owner's
    /// `size_of`), so only the `Vec` fields contribute.
    pub(crate) fn heap_size(&self) -> usize {
        self.opt_nodes_scratch.len() * core::mem::size_of::<HcOptimalNode>()
            + self.opt_node_prices_scratch.len() * core::mem::size_of::<u32>()
            + self.opt_candidates_scratch.capacity() * core::mem::size_of::<MatchCandidate>()
            + self.opt_store_scratch.capacity() * core::mem::size_of::<HcOptimalNode>()
            + (self.opt_segment_plan_scratch.capacity() + self.opt_seed_plan_scratch.capacity())
                * core::mem::size_of::<HcOptimalSequence>()
            + self.opt_price_arena.len() * core::mem::size_of::<[u32; 2]>()
            + self.ldm_sequences.capacity() * core::mem::size_of::<HcRawSeq>()
    }

    /// Per-frame reset — clears scratch buffers, resets cost model,
    /// drops cached price stamps.
    pub(crate) fn reset(&mut self) {
        self.opt_state.reset();
        // The `opt_nodes_scratch` / `opt_node_prices_scratch` /
        // `opt_price_arena` boxed slices persist across resets (no realloc
        // churn). Per-block correctness comes from the DP reading only DP
        // cells it wrote in the same call and from the generation stamps marking stale price
        // cells. The LL/ML stamps stay MONOTONIC across resets (never
        // zeroed): stale generation cells in the persistent arena carry
        // older, smaller stamps and so can never falsely match the next
        // pass — zeroing the stamp would risk a stale cell aliasing the
        // fresh value `1`. The inline lit price/generation arrays are
        // small and stay zeroed (self-consistent stamp reset).
        self.opt_candidates_scratch.clear();
        self.opt_store_scratch.clear();
        self.opt_segment_plan_scratch.clear();
        self.opt_seed_plan_scratch.clear();
        self.opt_lit_price_scratch = [0; HC_MAX_LIT + 1];
        self.opt_lit_price_generation = [0; HC_MAX_LIT + 1];
        self.opt_lit_price_stamp = 0;
        self.ldm_sequences.clear();
    }

    /// Upstream zstd parity: `ZSTD_optLdm_skipRawSeqStoreBytes`. Fast-forward the
    /// raw LDM seq store cursor by `nb_bytes`, consuming whole stored
    /// sequences and leaving a partial-sequence offset in `pos_in_sequence`.
    pub(crate) fn ldm_skip_raw_seq_store_bytes(
        &self,
        seq_store: &mut HcRawSeqStore,
        nb_bytes: usize,
    ) {
        let mut curr_pos = seq_store.pos_in_sequence.saturating_add(nb_bytes);
        while curr_pos > 0 && seq_store.pos < seq_store.size {
            let curr_seq = self.ldm_sequences[seq_store.pos];
            let seq_len = curr_seq.lit_length.saturating_add(curr_seq.match_length);
            if curr_pos >= seq_len {
                curr_pos -= seq_len;
                seq_store.pos += 1;
            } else {
                seq_store.pos_in_sequence = curr_pos;
                break;
            }
        }
        if curr_pos == 0 || seq_store.pos == seq_store.size {
            seq_store.pos_in_sequence = 0;
        }
    }

    /// Upstream zstd parity: `ZSTD_optLdm_maybeAddMatch` / its preamble in
    /// `ZSTD_optLdm_getNextMatch`. Advance the per-block LDM window
    /// markers to the next raw LDM sequence and skip its literals.
    pub(crate) fn ldm_get_next_match_and_update_seq_store(
        &self,
        opt_ldm: &mut HcOptLdmState,
        curr_pos_in_block: usize,
        block_bytes_remaining: usize,
    ) {
        if opt_ldm.seq_store.size == 0 || opt_ldm.seq_store.pos >= opt_ldm.seq_store.size {
            opt_ldm.start_pos_in_block = usize::MAX;
            opt_ldm.end_pos_in_block = usize::MAX;
            return;
        }
        let curr_seq = self.ldm_sequences[opt_ldm.seq_store.pos];
        let curr_block_end_pos = curr_pos_in_block.saturating_add(block_bytes_remaining);
        let literals_bytes_remaining = curr_seq
            .lit_length
            .saturating_sub(opt_ldm.seq_store.pos_in_sequence);
        let match_bytes_remaining = if literals_bytes_remaining == 0 {
            curr_seq.match_length.saturating_sub(
                opt_ldm
                    .seq_store
                    .pos_in_sequence
                    .saturating_sub(curr_seq.lit_length),
            )
        } else {
            curr_seq.match_length
        };
        if literals_bytes_remaining >= block_bytes_remaining {
            opt_ldm.start_pos_in_block = usize::MAX;
            opt_ldm.end_pos_in_block = usize::MAX;
            self.ldm_skip_raw_seq_store_bytes(&mut opt_ldm.seq_store, block_bytes_remaining);
            return;
        }
        opt_ldm.start_pos_in_block = curr_pos_in_block.saturating_add(literals_bytes_remaining);
        opt_ldm.end_pos_in_block = opt_ldm
            .start_pos_in_block
            .saturating_add(match_bytes_remaining);
        opt_ldm.offset = curr_seq.offset;
        if opt_ldm.end_pos_in_block > curr_block_end_pos {
            opt_ldm.end_pos_in_block = curr_block_end_pos;
            self.ldm_skip_raw_seq_store_bytes(
                &mut opt_ldm.seq_store,
                curr_block_end_pos.saturating_sub(curr_pos_in_block),
            );
        } else {
            self.ldm_skip_raw_seq_store_bytes(
                &mut opt_ldm.seq_store,
                literals_bytes_remaining.saturating_add(match_bytes_remaining),
            );
        }
    }

    /// Upstream zstd parity: `ZSTD_optLdm_maybeAddMatch`. Convert the active LDM
    /// window (open/close cursors set by
    /// [`Self::ldm_get_next_match_and_update_seq_store`]) into a usable
    /// `MatchCandidate` when the current position falls inside it.
    pub(crate) fn ldm_maybe_add_match(
        &self,
        opt_ldm: &HcOptLdmState,
        curr_pos_in_block: usize,
        min_match: usize,
    ) -> Option<MatchCandidate> {
        let _ = self;
        let pos_diff = curr_pos_in_block.saturating_sub(opt_ldm.start_pos_in_block);
        let candidate_match_length = opt_ldm
            .end_pos_in_block
            .saturating_sub(opt_ldm.start_pos_in_block)
            .saturating_sub(pos_diff);
        if curr_pos_in_block < opt_ldm.start_pos_in_block
            || curr_pos_in_block >= opt_ldm.end_pos_in_block
            || candidate_match_length < min_match
        {
            return None;
        }
        Some(MatchCandidate {
            start: curr_pos_in_block,
            offset: opt_ldm.offset,
            match_len: candidate_match_length,
        })
    }

    /// Upstream zstd parity: `ZSTD_optLdm_processMatchCandidate`. Wraps
    /// [`Self::ldm_maybe_add_match`] with a re-seed step when the parser has
    /// stepped past the current LDM window.
    pub(crate) fn ldm_process_match_candidate(
        &self,
        opt_ldm: &mut HcOptLdmState,
        curr_pos_in_block: usize,
        remaining_bytes: usize,
        min_match: usize,
    ) -> Option<MatchCandidate> {
        if opt_ldm.seq_store.size == 0 || opt_ldm.seq_store.pos >= opt_ldm.seq_store.size {
            return None;
        }
        if curr_pos_in_block >= opt_ldm.end_pos_in_block {
            if curr_pos_in_block > opt_ldm.end_pos_in_block {
                let pos_overshoot = curr_pos_in_block.saturating_sub(opt_ldm.end_pos_in_block);
                self.ldm_skip_raw_seq_store_bytes(&mut opt_ldm.seq_store, pos_overshoot);
            }
            self.ldm_get_next_match_and_update_seq_store(
                opt_ldm,
                curr_pos_in_block,
                remaining_bytes,
            );
        }
        self.ldm_maybe_add_match(opt_ldm, curr_pos_in_block, min_match)
    }

    /// Upstream zstd parity: restore the seven per-frame scratch buffers that
    /// `build_optimal_plan_impl!` borrowed via `core::mem::take`. The
    /// passed `result` tuple is the parser's `(offset, reps, litlen,
    /// match_len)` return value — kept untouched and returned so the
    /// macro chains the move-out in a single expression.
    pub(crate) fn finish_optimal_plan(
        &mut self,
        buffers: HcOptimalPlanBuffers,
        result: (u32, [u32; 3], usize, usize),
    ) -> (u32, [u32; 3], usize, usize) {
        let HcOptimalPlanBuffers {
            nodes,
            node_prices,
            mut candidates,
            store,
            price_arena,
            candidates_searched_at: _,
            pass: _,
        } = buffers;
        candidates.clear();
        self.opt_nodes_scratch = nodes;
        self.opt_node_prices_scratch = node_prices;
        self.opt_candidates_scratch = candidates;
        self.opt_store_scratch = store;
        self.opt_price_arena = price_arena;
        result
    }

    /// Upstream zstd parity: `ZSTD_storeSeq` — encode `actual_offset` into the
    /// upstream zstd's compact offset base (1/2/3 for rep slots, otherwise
    /// `actual_offset + 3`) and update the rolling `reps` window in
    /// lock-step. Returns `(off_base, next_reps)`. The non-rep branch
    /// uses `saturating_add` so a `u32` near `u32::MAX` (only possible
    /// via malformed external input) clamps to `u32::MAX` rather than
    /// wrapping into a small rep-code value that would silently corrupt
    /// the encoded stream.
    pub(crate) fn encode_offset_with_reps(
        actual_offset: u32,
        lit_len: usize,
        reps: [u32; 3],
    ) -> (u32, [u32; 3]) {
        let mut next_reps = reps;
        let encoded = if lit_len > 0 {
            if actual_offset == reps[0] {
                1
            } else if actual_offset == reps[1] {
                2
            } else if actual_offset == reps[2] {
                3
            } else {
                actual_offset.saturating_add(3)
            }
        } else if actual_offset == reps[1] {
            1
        } else if actual_offset == reps[2] {
            2
        } else if reps[0] > 1 && actual_offset == reps[0] - 1 {
            3
        } else {
            actual_offset.saturating_add(3)
        };

        if lit_len > 0 {
            match encoded {
                1 => {}
                2 => {
                    next_reps[1] = next_reps[0];
                    next_reps[0] = actual_offset;
                }
                _ => {
                    next_reps[2] = next_reps[1];
                    next_reps[1] = next_reps[0];
                    next_reps[0] = actual_offset;
                }
            }
        } else {
            match encoded {
                1 => {
                    next_reps[1] = next_reps[0];
                    next_reps[0] = actual_offset;
                }
                _ => {
                    next_reps[2] = next_reps[1];
                    next_reps[1] = next_reps[0];
                    next_reps[0] = actual_offset;
                }
            }
        }

        (encoded, next_reps)
    }

    /// `encode_offset_with_reps` minus the rep-history update — used in
    /// the optimal parser's per-candidate price probe where the rep
    /// window hasn't been committed yet.
    #[inline(always)]
    pub(crate) fn encode_offset_base_with_reps(
        actual_offset: u32,
        lit_len: usize,
        reps: [u32; 3],
    ) -> u32 {
        if lit_len > 0 {
            if actual_offset == reps[0] {
                1
            } else if actual_offset == reps[1] {
                2
            } else if actual_offset == reps[2] {
                3
            } else {
                actual_offset.saturating_add(3)
            }
        } else if actual_offset == reps[1] {
            1
        } else if actual_offset == reps[2] {
            2
        } else if reps[0] > 1 && actual_offset == reps[0] - 1 {
            3
        } else {
            actual_offset.saturating_add(3)
        }
    }

    /// Upstream zstd parity: `ZSTD_updateStats` for one sequence the parser
    /// has just settled, called from its traceback so the next segment prices
    /// against counts that include it. `literals_start` is the block offset
    /// the previous sequence ended at and `reps` the history before this one;
    /// both advance. The caller refreshes the base prices once the segment's
    /// sequences are in.
    #[inline]
    pub(crate) fn record_sequence_stats(
        block: &[u8],
        sequence: HcOptimalSequence,
        literals_start: &mut usize,
        reps: &mut [u32; 3],
        opt_state: &mut HcOptState,
    ) {
        let lit_len = sequence.lit_len as usize;
        let match_len = sequence.match_len as usize;
        // `checked_add` on both edges so a malformed sequence can't overflow
        // `usize` arithmetic before the bounds guard fires. `saturating_add`
        // would have masked overflow as "clamp to usize::MAX" which then
        // bypasses the `> block.len()` check.
        let Some(start) = literals_start.checked_add(lit_len) else {
            return;
        };
        let Some(end) = start.checked_add(match_len) else {
            return;
        };
        if end > block.len() {
            return;
        }
        let literals = &block[*literals_start..start];
        let (off_base, next_reps) =
            Self::encode_offset_with_reps(sequence.offset, literals.len(), *reps);
        opt_state.update_stats(literals.len(), literals, off_base, match_len);
        *reps = next_reps;
        *literals_start = end;
    }

    /// Brings cells `start..=end` into the frontier as unreached: price `MAX`.
    /// Their nodes are left untouched, possibly uninitialised: the DP reads a
    /// node only once its price is finite, and every transition that makes a
    /// price finite writes the whole node with it.
    ///
    /// # Safety
    ///
    /// `node_prices` points into an arena longer than `end`.
    #[inline(always)]
    pub(crate) unsafe fn reset_opt_node_prices(node_prices: *mut u32, start: usize, end: usize) {
        for i in start..=end {
            // SAFETY: `i <= end`, in bounds by the caller's contract.
            unsafe { node_prices.add(i).write(u32::MAX) };
        }
    }

    #[inline(always)]
    pub(crate) fn add_price_delta(price: u32, add: u32, delta: i32) -> u32 {
        #[cfg(debug_assertions)]
        {
            let sum = price as i64 + add as i64 + delta as i64;
            debug_assert!((0..=u32::MAX as i64).contains(&sum));
        }
        price.wrapping_add(add).wrapping_add_signed(delta)
    }

    #[inline(always)]
    pub(crate) fn add_prices(lhs: u32, rhs: u32) -> u32 {
        let sum = lhs + rhs;
        debug_assert!(sum >= lhs);
        sum
    }

    #[inline(always)]
    pub(crate) fn cached_literal_price<const ACCURATE: bool>(
        profile: HcOptimalCostProfile,
        stats: &HcOptState,
        byte: u8,
        prices: &mut [u32; HC_MAX_LIT + 1],
        generations: &mut [u32; HC_MAX_LIT + 1],
        stamp: u32,
    ) -> u32 {
        // The integer weight is one bit scan on a frequency, no dearer than the
        // probe that would stand in for it, so it is computed in place, as
        // upstream does at `optLevel` 0. Only the fractional weight is cached.
        if !ACCURATE {
            return profile.literal_price::<false>(stats, byte);
        }
        // SAFETY: `byte as usize` is `0..256` and the fixed-size arrays are
        // `[u32; HC_MAX_LIT + 1 = 257]`, so the index is statically in bounds.
        // Each cached_*_price call sits inside the optimal parser per-byte
        // hot loop where these bounds checks are pure overhead.
        let idx = byte as usize;
        unsafe {
            if *generations.get_unchecked(idx) == stamp {
                return *prices.get_unchecked(idx);
            }
            let price = profile.literal_price::<ACCURATE>(stats, byte);
            *prices.get_unchecked_mut(idx) = price;
            *generations.get_unchecked_mut(idx) = stamp;
            price
        }
    }

    #[inline(always)]
    pub(crate) fn cached_lit_length_price<const ACCURATE: bool>(
        profile: HcOptimalCostProfile,
        stats: &HcOptState,
        lit_len: usize,
        cache: &mut [[u32; 2]],
        stamp: u32,
    ) -> u32 {
        // Computed in place under the integer weight; see `cached_literal_price`.
        if !ACCURATE || lit_len >= cache.len() {
            return profile.lit_length_price::<ACCURATE>(stats, lit_len);
        }
        // SAFETY: the early-return above proves `lit_len < cache.len()`.
        // Each cell pairs `[price, generation]`, so the stamp check and the
        // price read/write hit ONE cache line instead of two separate
        // strided regions 16 KiB apart.
        unsafe {
            let cell = cache.get_unchecked_mut(lit_len);
            if cell[1] == stamp {
                return cell[0];
            }
            let price = profile.lit_length_price::<ACCURATE>(stats, lit_len);
            cell[0] = price;
            cell[1] = stamp;
            price
        }
    }

    #[inline(always)]
    pub(crate) fn cached_lit_length_delta_price<const ACCURATE: bool>(
        profile: HcOptimalCostProfile,
        stats: &HcOptState,
        lit_len: usize,
        cache: &mut [[u32; 2]],
        stamp: u32,
    ) -> i32 {
        if lit_len == 0 {
            // The `lit_len == 0` branch is the rare case where computing
            // `lit_len - 1` would underflow; we feed `0` to both
            // `lit_length_price` calls so the delta is 0 by construction.
            // No need to compute `0_usize - 1`.
            return 0;
        }
        let price =
            Self::cached_lit_length_price::<ACCURATE>(profile, stats, lit_len, cache, stamp);
        let previous =
            Self::cached_lit_length_price::<ACCURATE>(profile, stats, lit_len - 1, cache, stamp);
        price as i32 - previous as i32
    }

    #[inline(always)]
    pub(crate) fn cached_match_length_price<const ACCURATE: bool>(
        profile: HcOptimalCostProfile,
        stats: &HcOptState,
        match_len: usize,
        cache: &mut [[u32; 2]],
        stamp: u32,
    ) -> u32 {
        // Computed in place under the integer weight; see `cached_literal_price`.
        if !ACCURATE || match_len >= cache.len() {
            return profile.match_length_price::<ACCURATE>(stats, match_len);
        }
        // SAFETY: see `cached_lit_length_price` — paired `[price, generation]`
        // cells, one cache line per probe; early return proves
        // `match_len < cache.len()`.
        unsafe {
            let cell = cache.get_unchecked_mut(match_len);
            if cell[1] == stamp {
                return cell[0];
            }
            let price = profile.match_length_price::<ACCURATE>(stats, match_len);
            cell[0] = price;
            cell[1] = stamp;
            price
        }
    }
}

#[cfg(test)]
mod ldm_helper_tests;
#[cfg(test)]
mod tests;