structured_zstd/encoding/levels/

config.rs

//! Per-level compression tuning: the matcher config structs, the level
//! parameter table, and the level → params resolution chain.
//!
//! Moved verbatim from `match_generator.rs` (no behaviour change): the
//! `HcConfig` / `RowConfig` / `DfastConfig` / `FastConfig` knobs, `LevelParams`
//! and `LEVEL_TABLE`, the public-parameter overrides, the source-size tiering,
//! and the workspace estimators. `match_generator` imports this resolution API
//! instead of carrying it inline. Encoding-level paths are written absolute
//! (`crate::encoding::…`) so the module can live under `levels/` unchanged.

use crate::encoding::CompressionLevel;
use crate::encoding::match_generator::{HC_SEARCH_DEPTH, HC_TARGET_LEN, ROW_MIN_MATCH_LEN};
#[cfg(test)]
use crate::encoding::match_generator::{ROW_HASH_BITS, ROW_LOG, ROW_SEARCH_DEPTH, ROW_TARGET_LEN};
#[cfg(test)]
use crate::encoding::match_table::storage::{HC_CHAIN_LOG, HC_HASH_LOG};
/// Bundled tuning knobs for the hash-chain matcher. Using a typed config
/// instead of positional `usize` args eliminates parameter-order hazards.
#[derive(Copy, Clone, PartialEq, Eq)]
pub(crate) struct HcConfig {
    pub(crate) hash_log: usize,
    pub(crate) chain_log: usize,
    pub(crate) search_depth: usize,
    pub(crate) target_len: usize,
    /// Binary-tree finder hash width. Upstream uses `mls = BOUNDED(3, minMatch, 6)`
    /// (`ZSTD_selectBtGetAllMatches`, zstd_opt.c:896) — i.e. mls=3 on the
    /// btultra/btultra2 levels (L18-22, minMatch=3) — and surfaces 3-byte matches
    /// through a fallback-only HC3 finder (zstd_opt.c:691-720: distance < 256 KiB,
    /// taken only when no longer/repcode match exists). Our optimal parser does
    /// NOT yet replicate that 3-byte handling — it emits short matches C prices
    /// out, breaking level-22 sequence parity — so the BT hash width is clamped UP
    /// to 4 (`cp.min_match.clamp(4, 6)`) to keep the finder from surfacing those
    /// 3-byte matches and so match C's output. This is a deliberate workaround,
    /// NOT C's finder width; drop the clamp once the optimal parser is C-faithful
    /// at minMatch 3 (tracked in #337). Carried explicitly per level so a
    /// `target_length` override can't silently change the finder's hashing width.
    /// Only the BT body reads it; HC / lazy levels keep it at 4.
    pub(crate) search_mls: usize,
}

#[derive(Copy, Clone, PartialEq, Eq)]
pub(crate) struct RowConfig {
    pub(crate) hash_bits: usize,
    pub(crate) row_log: usize,
    pub(crate) search_depth: usize,
    pub(crate) target_len: usize,
    /// Upstream zstd `cParams.minMatch` for the row matcher: the regular-search
    /// acceptance floor (a row candidate must extend to >= `mls` bytes).
    /// The C-like advanced API surfaces this as the row min-match knob.
    /// `ROW_MIN_MATCH_LEN` (5) is the default; the row hash key width stays
    /// 4 bytes (an internal detail), so this only tunes the acceptance
    /// floor, not the candidate hash distribution.
    pub(crate) mls: usize,
    /// Upstream `cParams.chainLog`: the hash-chain table the greedy/lazy
    /// parse searches instead of rows when the window is 2^14 or smaller
    /// (upstream `ZSTD_resolveRowMatchFinderMode`), or the binary tree
    /// (`2^(chainLog-1)` nodes) of a btlazy2 level.
    pub(crate) chain_log: usize,
    /// Upstream `ZSTD_btlazy2`: the lazy parse searches the lazily-sorted
    /// binary tree (`ZSTD_BtFindBestMatch`) instead of rows / the chain.
    pub(crate) bt: bool,
}

// Only used as the default HashChain config when the test-only parse×search
// override pairs a level with a backend its native row doesn't populate.
#[cfg(test)]
pub(crate) const HC_CONFIG: HcConfig = HcConfig {
    hash_log: HC_HASH_LOG,
    chain_log: HC_CHAIN_LOG,
    search_depth: HC_SEARCH_DEPTH,
    target_len: HC_TARGET_LEN,
    search_mls: 4,
};

/// Base HashChain config synthesized when a public-parameter strategy
/// override ([`crate::encoding::parameters`]) routes a level to the HC / BT
/// backend whose native level row didn't populate `hc` (e.g. forcing
/// `Strategy::Lazy2` onto a level the table resolves to Fast). Mirrors
/// the mid-band lazy defaults; the per-knob overrides then refine it.
pub(crate) const HC_OVERRIDE_DEFAULT: HcConfig = HcConfig {
    hash_log: crate::encoding::match_table::storage::HC_HASH_LOG,
    chain_log: crate::encoding::match_table::storage::HC_CHAIN_LOG,
    search_depth: HC_SEARCH_DEPTH,
    target_len: HC_TARGET_LEN,
    search_mls: 4,
};

// Default Row config: only used by tests and the test-only parse×search
// override (production greedy L5 carries its own `ROW_L5`).
#[cfg(test)]
pub(crate) const ROW_CONFIG: RowConfig = RowConfig {
    hash_bits: ROW_HASH_BITS,
    row_log: ROW_LOG,
    search_depth: ROW_SEARCH_DEPTH,
    target_len: ROW_TARGET_LEN,
    mls: ROW_MIN_MATCH_LEN,
    chain_log: ROW_HASH_BITS,
    bt: false,
};

// Level-5 greedy is the ONLY strategy routed to the Row backend
// (`StrategyTag::backend`: greedy -> Row; lazy / btopt / btultra* ->
// HashChain), so it is the only level whose `row:` field is read. The upstream zstd
// `clevels.h` default row (srcSize > 256 KB) for level 5 is searchLog=3,
// targetLength=2, from which the row matcher derives:
//   rowLog       = clamp(searchLog, 4, 6) = 4
//   search_depth = 1 << min(searchLog, rowLog) = 8   (= nbAttempts)
//   target_len   = targetLength = 2                  (nice-match early-out)
// The shared `ROW_CONFIG` (row_log=5, search_depth=16, target_len=48) ran a
// level-12-grade search here: 16 slots per row, never early-exiting until a
// 48-byte match. That exhaustive walk was the dominant cost in greedy L5's
// encode-speed regression vs FFI. `hash_bits` matches upstream zstd's
// `ZSTD_getCParams(5, .., 0).hashLog` = 19 (verified via
// `cparams_check 5`), so the row table is the same width as upstream's
// (2^19 slots); the previous `ROW_HASH_BITS` (20) doubled both row tables vs
// upstream, the dominant peak-memory excess on the greedy band.
pub(crate) const ROW_L5: RowConfig = RowConfig {
    hash_bits: 19,
    row_log: 4,
    search_depth: 8,
    target_len: 2,
    mls: ROW_MIN_MATCH_LEN,
    chain_log: 18,
    bt: false,
};

/// Per-level Double-Fast hash sizing, mirroring the upstream zstd `clevels.h` columns
/// (config-driven, not a hardcoded constant): `long_hash_log` =
/// `cParams.hashLog` (the long 8-byte hash table), `short_hash_log` =
/// `cParams.chainLog` (the short hash table dfast repurposes as its
/// secondary index). Only the Dfast backend reads it, so non-dfast level
/// rows carry `dfast: None`. `minMatch` stays the upstream zstd-fixed `5`
/// (`DFAST_MIN_MATCH_LEN`, used in const contexts).
#[derive(Copy, Clone, PartialEq, Eq)]
pub(crate) struct DfastConfig {
    pub(crate) long_hash_log: u8,
    pub(crate) short_hash_log: u8,
}

// Upstream zstd clevels.h default row (srcSize > 256 KB): L3 {hashLog 17, chainLog 16}.
pub(crate) const DFAST_L3: DfastConfig = DfastConfig {
    long_hash_log: 17,
    short_hash_log: 16,
};

/// Per-level Fast-strategy tuning, only consumed by the `FastKernelMatcher`
/// (Simple backend): `hash_log` = upstream zstd `cParams.hashLog`, `mls` = upstream zstd
/// `cParams.minMatch` (4..=8), `step_size` = upstream zstd `stepSize`. Carried as
/// `LevelParams.fast` (`Some` only on Fast level rows; `None` elsewhere).
#[derive(Copy, Clone, PartialEq, Eq)]
pub(crate) struct FastConfig {
    pub(crate) hash_log: u32,
    pub(crate) mls: u32,
    pub(crate) step_size: usize,
}

pub(crate) const FAST_L1: FastConfig = FastConfig {
    hash_log: 14,
    // Tier-0 (srcSize > 256 KiB) `cParams.minMatch`. Upstream zstd selects the
    // Level-1 row from a 4-way srcSize-tiered table (`ZSTD_getCParams_internal`
    // → `ZSTD_defaultCParameters[tableID][1]`), and minMatch shrinks for
    // smaller inputs: 7 (>256 KiB) / 6 (16..256 KiB) / 5 (<=16 KiB). The base
    // here is the tier-0 value; `fast_l1_mls_for_source_size` lowers it per the
    // tier in `adjust_params_for_source_size`.
    mls: 7,
    step_size: 2,
};

/// Resolved tuning parameters for a compression level and source size. The
/// [`StrategyTag`] selects the compile-time strategy consts; the runtime
/// [`BackendTag`] used by the driver dispatcher comes from the resolved
/// search method ([`Self::backend`]), so an override or a size tier that
/// changes the search changes the backend with it.
///
/// [`StrategyTag`]: crate::encoding::strategy::StrategyTag
/// [`BackendTag`]: crate::encoding::strategy::BackendTag
#[derive(Copy, Clone, PartialEq, Eq)]
pub(crate) struct LevelParams {
    pub(crate) strategy_tag: crate::encoding::strategy::StrategyTag,
    /// Decoupled search-method axis. Independent of `strategy_tag`'s
    /// parse half: a level can pair any parse (greedy / lazy depth via
    /// `lazy_depth`) with any search backend here. Defaults to the
    /// historical pairing (`strategy_tag.search()`) but is overridable
    /// per level so the parse×search matrix can be swept and tuned.
    pub(crate) search: crate::encoding::strategy::SearchMethod,
    pub(crate) window_log: u8,
    pub(crate) lazy_depth: u8,
    /// Per-strategy tuning. Exactly one is `Some` on each level row, matching
    /// `strategy_tag`'s backend, so the table self-documents which knobs a
    /// level actually consumes (the others are `None`, not dead placeholders):
    /// `fast` for the Fast/Simple backend, `dfast` for Double-Fast, `hc` for
    /// the HashChain (lazy / btopt / btultra*) backend, `row` for the Row
    /// (greedy L5) backend.
    pub(crate) fast: Option<FastConfig>,
    pub(crate) dfast: Option<DfastConfig>,
    pub(crate) hc: Option<HcConfig>,
    pub(crate) row: Option<RowConfig>,
}

impl LevelParams {
    /// Backend family (storage variant) for the driver dispatcher.
    /// Derived from the decoupled `search` axis so a level can route to
    /// a different search backend than its `strategy_tag` historically
    /// implied.
    pub(crate) fn backend(&self) -> crate::encoding::strategy::BackendTag {
        self.search.backend()
    }

    /// Parse mode derived from the decoupled `search` axis: the binary-tree
    /// search path carries `ParseMode::Optimal`; every other search backend
    /// derives greedy/lazy/lazy2 from `lazy_depth`. Reading `search` (not the
    /// strategy tag) keeps the parse×search decoupling complete even when a
    /// level whose tag is `Bt*` is overridden to a non-BT search backend.
    pub(crate) fn parse(&self) -> crate::encoding::strategy::ParseMode {
        match self.search {
            crate::encoding::strategy::SearchMethod::BinaryTree => {
                crate::encoding::strategy::ParseMode::Optimal
            }
            _ => crate::encoding::strategy::ParseMode::from_lazy_depth(self.lazy_depth),
        }
    }

    /// Cheap fingerprint pre-splitter level (the `ZSTD_splitBlock` level;
    /// `0` = from-borders heuristic, `1..=4` = byChunks with sampling tier
    /// `level - 1`, rates 43 / 11 / 5 / 1). See [`pre_split_for`].
    pub(crate) fn pre_split(&self) -> Option<u8> {
        Some(pre_split_for(self.strategy_tag, self.lazy_depth))
    }

    /// `log2` of how much of a dictionary's end the match-finder tables index
    /// when it is loaded: a longer dictionary is indexed only that far from its
    /// end, since tables this size could not keep more of it anyway (upstream
    /// `ZSTD_loadDictionaryContent`, `zstd_compress.c:4987`:
    /// `MIN(MAX(hashLog + 3, chainLog + 1), 31)`). Every byte of it stays in
    /// the window.
    pub(crate) fn dictionary_reach_log(&self) -> u32 {
        use crate::encoding::strategy::SearchMethod;
        // The active backend's config: an override may leave the level row's
        // own beside it.
        let logs = match self.search {
            SearchMethod::Fast => self.fast.map(|fast| (fast.hash_log as usize, 0)),
            SearchMethod::DoubleFast => self
                .dfast
                .map(|dfast| (dfast.long_hash_log as usize, dfast.short_hash_log as usize)),
            SearchMethod::RowHash | SearchMethod::BinaryTreeLazy => {
                self.row.map(|row| (row.hash_bits, row.chain_log))
            }
            SearchMethod::HashChain | SearchMethod::BinaryTree => {
                self.hc.map(|hc| (hc.hash_log, hc.chain_log))
            }
        };
        // The reset synthesises the active config when a row lacks it, so a
        // missing one only means a table-less level: nothing to index.
        let Some((hash_log, chain_log)) = logs else {
            return 0;
        };
        (hash_log + 3).max(chain_log + 1).min(31) as u32
    }

    /// The level's upstream `cParams.minMatch`: the shortest match its search
    /// accepts, and so the shortest piece of a long-distance match a block cut
    /// leaves worth keeping (`maybeSplitSequence`, `zstd_ldm.c:644`).
    #[cfg(feature = "ldm")]
    pub(crate) fn min_match(&self) -> usize {
        use crate::encoding::strategy::SearchMethod;
        let configured = match self.search {
            SearchMethod::Fast => self.fast.map(|fast| fast.mls as usize),
            SearchMethod::DoubleFast => Some(crate::encoding::match_generator::DFAST_MIN_MATCH_LEN),
            SearchMethod::RowHash | SearchMethod::BinaryTreeLazy => self.row.map(|row| row.mls),
            SearchMethod::HashChain => Some(crate::encoding::hc::HC_MIN_MATCH_LEN),
            SearchMethod::BinaryTree => self.hc.map(|hc| hc.search_mls),
        };
        configured.unwrap_or(crate::encoding::cost_model::HC_FORMAT_MINMATCH)
    }
}

/// The pre-splitter level for an effective strategy (the tag plus, for the
/// collapsed `Lazy` tag, its lazy depth).
///
/// Upstream's default is `splitLevels[strategy] = {0,0,1,2,2,3,3,4,4,4}`
/// (zstd_compress.c:4552, used as is; only an explicit `blockSplitterLevel`
/// is shifted down by 2). It is followed up to lazy depth 1 — the finer
/// sampling is a real ratio win on mixed data (decodecorpus at greedy/lazy:
/// the borders tier compressed 4.6-4.9 % WORSE than upstream, the upstream
/// rate-11 tier <= upstream) — but the lazy2/btlazy2 rate-5 and optimal-band
/// rate-1 tiers are DELIBERATELY kept two steps coarser: on periodic input
/// they over-split every block into tiny pieces exactly like upstream does
/// (100 MiB of repeated log lines at L8-L12: 140,625 bytes and 3.6x the
/// time upstream-tier, 9,742 bytes coarse — 14x better than upstream) while
/// on real data they buy under 0.1 % (decodecorpus L8-L12: 170 bytes of
/// 483 KiB). The drop-in contract asks for ratio <= upstream, not for
/// upstream's block boundaries.
pub(crate) fn pre_split_for(tag: crate::encoding::strategy::StrategyTag, lazy_depth: u8) -> u8 {
    use crate::encoding::strategy::StrategyTag;
    match tag {
        // Upstream tiers: borders / byChunks rate 43 / rate 11.
        StrategyTag::Fast => 0,
        StrategyTag::Dfast => 1,
        StrategyTag::Greedy => 2,
        // lazy (depth 1) = upstream rate 11; lazy2 coarsened to rate 43.
        StrategyTag::Lazy => {
            if lazy_depth >= 2 {
                1
            } else {
                2
            }
        }
        StrategyTag::Btlazy2 => 1,
        // Coarsened to byChunks rate 11 (upstream: rate 1).
        StrategyTag::BtOpt | StrategyTag::BtUltra | StrategyTag::BtUltra2 => 2,
    }
}

/// Apply the public-parameter per-knob overrides onto the
/// level-resolved [`LevelParams`], in place. Runs in
/// [`Matcher::reset`](crate::encoding::Matcher::reset)
/// after the level params are computed and before backend selection, so
/// a strategy override re-routes the backend uniformly. An all-`None`
/// override is a no-op the caller skips via
/// [`crate::encoding::parameters::ParamOverrides::is_empty`], keeping the default
/// level geometry byte-identical.
pub(crate) fn apply_param_overrides(
    params: &mut LevelParams,
    ov: &crate::encoding::parameters::ParamOverrides,
) {
    use crate::encoding::strategy::SearchMethod;

    // 1. Strategy override re-derives tag / search / lazy depth.
    if let Some(strategy) = ov.strategy {
        let tag = strategy.tag();
        params.strategy_tag = tag;
        params.search = tag.search();
        params.lazy_depth = strategy.lazy_depth();
    }

    // 2. Ensure the active backend's config row exists (synthesize a
    //    default when a strategy override moved off the native row).
    match params.search {
        SearchMethod::Fast => {
            params.fast.get_or_insert(FAST_L1);
        }
        SearchMethod::DoubleFast => {
            params.dfast.get_or_insert(DFAST_L3);
        }
        SearchMethod::RowHash | SearchMethod::BinaryTreeLazy => {
            // `ROW_L5` already carries `mls = ROW_MIN_MATCH_LEN = 5`, the
            // upstream `minMatch` of the whole greedy..btlazy2 band at the
            // >256 KiB tier, so a synthesized btlazy2 override hashes at the
            // same width as a native btlazy2 row.
            let row = params.row.get_or_insert(ROW_L5);
            row.bt = matches!(params.search, SearchMethod::BinaryTreeLazy);
        }
        SearchMethod::HashChain | SearchMethod::BinaryTree => {
            params.hc.get_or_insert(HC_OVERRIDE_DEFAULT);
        }
    }

    // 3. window_log (bounds-checked at <= 30 by the builder).
    if let Some(window_log) = ov.window_log {
        params.window_log = window_log;
    }

    // 4. Per-backend numeric knobs map into the active config, mirroring
    //    the upstream zstd `cParams` -> matcher translation documented on each
    //    config struct.
    match params.search {
        SearchMethod::Fast => {
            if let Some(fast) = params.fast.as_mut() {
                if let Some(hash_log) = ov.hash_log {
                    fast.hash_log = hash_log;
                }
                if let Some(min_match) = ov.min_match {
                    fast.mls = fast_key_len(min_match);
                }
                // targetLength is the Fast strategy's step, as it is on the
                // level's own row: upstream zstd_fast.c `stepSize =
                // targetLength + !targetLength + 1`.
                if let Some(target_length) = ov.target_length {
                    fast.step_size = (target_length as usize).max(1) + 1;
                }
            }
        }
        SearchMethod::DoubleFast => {
            if let Some(dfast) = params.dfast.as_mut() {
                // hashLog -> long table, chainLog -> short table (the
                // dfast secondary index). Both bounds-checked <= 30, so
                // the `u8` casts are lossless.
                if let Some(hash_log) = ov.hash_log {
                    dfast.long_hash_log = hash_log as u8;
                }
                if let Some(chain_log) = ov.chain_log {
                    dfast.short_hash_log = chain_log as u8;
                }
            }
        }
        SearchMethod::RowHash | SearchMethod::BinaryTreeLazy => {
            if let Some(row) = params.row.as_mut() {
                // Row hash-table width override (mirrors dfast `long_hash_log`
                // / hc `hash_log`); `chain_log` sizes the hash chain the same
                // backend searches on a <= 2^14 window, or its binary tree.
                if let Some(hash_log) = ov.hash_log {
                    row.hash_bits = hash_log as usize;
                }
                if let Some(chain_log) = ov.chain_log {
                    row.chain_log = chain_log as usize;
                }
                if let Some(search_log) = ov.search_log {
                    // Upstream zstd: rowLog = clamp(searchLog, 4, 6); the
                    // compare budget stays the FULL `1 << searchLog`
                    // (`nbAttempts`) — the chain walk and the tree walk
                    // consume it directly, and the row probe bounds its own
                    // budget by the row size at the search site.
                    row.row_log = (search_log as usize).clamp(4, 6);
                    row.search_depth = 1usize << search_log;
                }
                if let Some(target_length) = ov.target_length {
                    row.target_len = target_length as usize;
                }
                if let Some(min_match) = ov.min_match {
                    row.mls = min_match as usize;
                }
            }
        }
        SearchMethod::HashChain | SearchMethod::BinaryTree => {
            if let Some(hc) = params.hc.as_mut() {
                if let Some(hash_log) = ov.hash_log {
                    hc.hash_log = hash_log as usize;
                }
                if let Some(chain_log) = ov.chain_log {
                    hc.chain_log = chain_log as usize;
                }
                if let Some(search_log) = ov.search_log {
                    hc.search_depth = 1usize << search_log;
                }
                if let Some(target_length) = ov.target_length {
                    hc.target_len = target_length as usize;
                }
                if let Some(min_match) = ov.min_match {
                    // BT finder hash width, derived from cParams.minMatch exactly
                    // as upstream zstd: `mls = BOUNDED(3, cParams.minMatch, 6)`
                    // (zstd_opt.c:896 ZSTD_selectBtGetAllMatches). minMatch=3
                    // tiers hash on 3 bytes (btultra/btultra2 path). Only the BT
                    // body reads `search_mls`; HC/lazy hash on 4 bytes regardless.
                    hc.search_mls = (min_match as usize).clamp(3, 6);
                }
            }
        }
    }
}

/// The key width the fast strategy hashes for a `minMatch`: upstream's fast
/// block compressor takes 3 as 4 (zstd_fast.c, `ZSTD_compressBlock_fast`:
/// `default: /* includes case 3 */`). A 3 reaches the fast strategy from the
/// knob, or from an optimal level's CDict row a strategy knob moved onto it.
fn fast_key_len(min_match: u32) -> u32 {
    min_match.max(4)
}

/// Map the resolved runtime strategy to the upstream zstd LDM strategy ordinal
/// (1..=9) that [`crate::encoding::ldm::params::LdmParams::adjust_for`] expects.
/// The collapsed `Lazy` tag splits on `lazy_depth` (lazy = 4, lazy2 = 5).
#[cfg(feature = "ldm")]
pub(crate) fn ldm_strategy_ordinal(
    tag: crate::encoding::strategy::StrategyTag,
    lazy_depth: u8,
) -> u32 {
    use crate::encoding::strategy::StrategyTag;
    match tag {
        StrategyTag::Fast => 1,
        StrategyTag::Dfast => 2,
        StrategyTag::Greedy => 3,
        StrategyTag::Lazy => {
            if lazy_depth >= 2 {
                5
            } else {
                4
            }
        }
        // Upstream zstd `ZSTD_btlazy2` ordinal.
        StrategyTag::Btlazy2 => 6,
        StrategyTag::BtOpt => 7,
        StrategyTag::BtUltra => 8,
        StrategyTag::BtUltra2 => 9,
    }
}

/// `ceil(log2(size))` of a source-size hint, with a zero hint floored to
/// [`MIN_WINDOW_LOG`]. This is the single quantization every hint-dependent
/// matcher parameter is derived from: the window-log cap, the HC / Fast hash
/// and chain widths, the Dfast / Row table widths, the L22 config buckets, and
/// the Fast attach-vs-copy cutoff. Two hints sharing this value resolve to the
/// identical matcher shape, which is why it (not the raw byte count) keys the
/// primed-dictionary snapshot — see `match_generator::PrimedKey`. Operates on the full `u64`
/// so callers comparing a hint against a cutoff get the same bucketed decision
/// here and at the driver, with no `as usize` truncation on 32-bit targets.
pub(crate) fn source_size_ceil_log(size: u64) -> u8 {
    if size == 0 {
        MIN_WINDOW_LOG
    } else {
        (64 - (size - 1).leading_zeros()) as u8
    }
}

/// Attach-vs-copy cutoff for the Fast strategy, as a ceil-log bucket: a hint at
/// or below `2^this` (or unknown, `None`) ATTACHES the dictionary (a separate
/// immutable table scanned in place via the borrowed dual-base kernel); a larger
/// hint would COPY it into the live table.
///
/// `13` is upstream zstd's Fast cutoff (`attachDictSizeCutoffs[ZSTD_fast]` is
/// 8 KB, zstd_compress.c:2296; `ZSTD_shouldAttachDict`, :2309). Above it the
/// dictionary is COPIED, and the copy is what makes the dictionary pay on a
/// larger source: the scan then runs over a table already holding the
/// dictionary's positions, so ordinary NEAR matches improve everywhere. Attach
/// mode starts with an empty table and reaches the dictionary only through the
/// separate exact table, at the positions the step happens to land on.
///
/// This was `31` (attach every source up to 2 GiB) on a speed argument alone,
/// and the missing byte column is where it went wrong. Per frame, `z000033`
/// (1,022,035 B) and its leading 10 KiB, with a 16 KiB dictionary trained over
/// its 10 KiB chunks, on the i9: two prebuilt binaries and libzstd alternated
/// in one session, `perf stat -r 3`, three rounds, ranges non-overlapping.
///
/// | case | bytes attach | bytes copy | reference | cycles attach | cycles copy | insn attach | insn copy |
/// |---|---|---|---|---|---|---|---|
/// | 10 KiB, L1 | 6,976 | 7,122 | 7,122 | 236,355 (1.95x) | 169,116 (1.39x) | 633,127 (1.78x) | 478,066 (1.34x) |
/// | 10 KiB, L-5 | 9,660 | 9,124 | 9,130 | 51,678 (1.22x) | 56,444 (1.33x) | 152,281 (1.14x) | 153,369 (1.15x) |
/// | 1 MiB, L1 | 550,810 | 551,584 | 570,765 | 19.84M (1.76x) | 16.21M (1.44x) | 54.01M (1.91x) | 39.60M (1.40x) |
/// | 1 MiB, L-5 | 689,127 | 647,735 | 669,826 | 8.80M (1.46x) | 10.67M (1.77x) | 21.62M (1.54x) | 22.81M (1.63x) |
///
/// Copy is the better arm on both axes at the positive levels: it takes 18-28%
/// fewer cycles and 22-27% fewer instructions, and its bytes are the
/// reference's exactly on the small frame and 3.4% under the reference on the
/// large one. At the ultra-fast levels it buys ratio with time: 21% more cycles
/// on the 1 MiB frame for 6.0% fewer bytes, 9% more on the small one for 5.5%
/// fewer. That trade is what the cutoff is for. Attach put us 2.9% ABOVE the
/// reference on the 1 MiB ultra-fast frame — the dictionary made our frame
/// bigger than our own no-dict frame there, while it made the reference's
/// smaller — because it found 21,897 sequences where the reference finds
/// 27,546. Copy puts us 3.3% under it.
///
/// The remaining gap is now a same-mode one: the reference does this copy in
/// 1.0x where we take 1.3-1.8x, which is a target with an apples-to-apples
/// reference rather than a mode the reference never runs.
///
/// The borrowed attach kernel stores virtual positions as `u32`
/// (`cur_abs as u32`), so it could not attach past bucket `31` regardless; that
/// ceiling is now far above the cutoff and no longer the binding constraint.
/// Shared by `reset` (records the mode in the primed-snapshot key) and
/// `prime_with_dictionary` (acts on it).
pub(crate) const FAST_ATTACH_DICT_CUTOFF_LOG: u8 = 13;

/// Whether a dictionary frame in size bucket `size_log` reuses the captured
/// primed snapshot rather than re-priming: only a known size above the
/// strategy's attach cutoff `cutoff_log`, the upstream zstd copy regime
/// (`ZSTD_shouldAttachDict`). The frame compressor restores on this and the
/// Fast reset keeps its table only on it, so the two cannot disagree.
pub(crate) fn restores_primed_snapshot(size_log: Option<u8>, cutoff_log: u8) -> bool {
    size_log.is_some_and(|log| log > cutoff_log)
}

/// Largest dictionary region (bytes) the Fast attach path can index. The tagged
/// dict table packs each position into `32 - DICT_TAG_BITS` (= 24) bits, so a
/// region past `2^24` (16 MiB) would overflow the packed position. Dictionaries
/// this large fall back to COPY mode, whose live table stores full `u32`
/// positions and handles them. The size hint set on dict load equals the actual
/// dict content length, so the attach-vs-copy decision (and the matching
/// snapshot-key / epoch bits) can gate on it consistently at reset time.
pub(crate) const MAX_FAST_ATTACH_DICT_REGION: usize = 1 << 24;

/// Dfast counterpart of [`FAST_ATTACH_DICT_CUTOFF_LOG`]: upstream zstd
/// `ZSTD_dictMatchState` attach cutoff for the double-fast strategy is 16 KiB
/// (`2^14`), so small / unknown-size inputs ATTACH (separate immutable dict
/// long+short tables + dual-probe in `start_matching_fast_loop`) and larger
/// known-size inputs COPY (re-prime the dict into the live tables, where the
/// dense scan matches it as window history). The attach build also self-gates
/// on `use_fast_loop` inside `skip_matching_for_dict_attach` — only the
/// fast-loop levels (L3 / Default / L0) carry the dual-probe.
pub(crate) const DFAST_ATTACH_DICT_CUTOFF_LOG: u8 = 14;

/// 32 KiB (`2^15`, upstream zstd `attachDictSizeCutoffs[ZSTD_lazy2]`): small /
/// unknown-size inputs ATTACH the dict as a separate hash-chain dms (the dual
/// search in `find_best_match` walks the live input chain + the dms), larger
/// known-size inputs dense-COPY (merge the dict into the live chain and search
/// the one combined chain).
pub(crate) const HC_ATTACH_DICT_CUTOFF_LOG: u8 = 15;

/// BT/optimal attach cutoff for `btlazy2` + `btopt`: 32 KiB (`2^15`, upstream
/// zstd `attachDictSizeCutoffs[ZSTD_btlazy2]` == `[ZSTD_btopt]`). Small /
/// unknown-size inputs ATTACH the dict as a separate DUBT dms; larger known-size
/// inputs COPY the dict into the LIVE binary tree (upstream zstd
/// `ZSTD_resetCCtx_byCopyingCDict`).
pub(crate) const BT_OPT_ATTACH_DICT_CUTOFF_LOG: u8 = 15;

/// BT/optimal attach cutoff for `btultra` + `btultra2`: 8 KiB (`2^13`, upstream
/// zstd `attachDictSizeCutoffs[ZSTD_btultra]` == `[ZSTD_btultra2]`). The deepest
/// parses copy the dict into the live tree past a much smaller source than the
/// `btopt` tier, matching upstream's per-strategy cutoff table.
pub(crate) const BT_ULTRA_ATTACH_DICT_CUTOFF_LOG: u8 = 13;

// Source-size cap for the dfast hash bits when a size hint is present: a tiny
// input needs no larger hash than its window. The upstream zstd `cParams.hashLog` /
// `chainLog` (from `DfastConfig`) caps it from above at the call site.
pub(crate) fn dfast_hash_bits_for_window(max_window_size: usize) -> usize {
    let window_log = (usize::BITS - 1 - max_window_size.leading_zeros()) as usize;
    window_log.max(MIN_WINDOW_LOG as usize)
}

pub(crate) fn row_hash_bits_for_window(max_window_size: usize) -> usize {
    // Upstream zstd `ZSTD_adjustCParams_internal` cap: `hashLog <= windowLog + 1`.
    // The `+ 1` is load-bearing for L12, whose upstream zstd hashLog (23) exceeds
    // its windowLog (22) — a plain `windowLog` cap would shrink the L12
    // table on EVERY hinted reset and split primed snapshots between
    // hinted and unhinted frames that resolve to the identical geometry.
    // No constant upper clamp: the old `ROW_HASH_BITS` (20) ceiling
    // predates the lazy band moving onto Row (L9-12 carry upstream zstd hashLog
    // 21-23).
    let window_log = (usize::BITS - 1 - max_window_size.leading_zeros()) as usize;
    (window_log + 1).max(MIN_WINDOW_LOG as usize)
}

/// `floor(log2(window))` for the HashChain table-log cap (upstream zstd
/// `ZSTD_adjustCParams_internal`). The caller clamps the level's `hash_log` /
/// `chain_log` from above with this so a small hinted input doesn't allocate the
/// full level's tables.
pub(crate) fn hc_hash_bits_for_window(max_window_size: usize) -> usize {
    let window_log = (usize::BITS - 1 - max_window_size.leading_zeros()) as usize;
    window_log.max(MIN_WINDOW_LOG as usize)
}

/// Smallest window_log the encoder will use regardless of source size.
pub(crate) const MIN_WINDOW_LOG: u8 = 10;

/// Largest window_log the public parameter API accepts
/// ([`CParameter::WindowLog`](crate::encoding::CParameter)'s upper bound), and
/// so the largest a workspace estimate can be asked to describe. The estimate
/// answers for whatever it is given, and shifting by more than the width of a
/// `usize` is undefined, so a request beyond this is answered with this.
pub(crate) const MAX_ESTIMATED_WINDOW_LOG: u8 = 30;

/// Translate a verbatim upstream `ZSTD_defaultCParameters[tier][level]` row
/// (`cparams::CParams`) into our resolved [`LevelParams`], reproducing
/// upstream's cParams -> matcher-config derivation so the encoder follows C's
/// source-size-tiered STRATEGY + table widths rather than a single hand-tuned
/// `LEVEL_TABLE`. Derivation (verified against L6/L16/L22 vs clevels.h):
/// `search_depth = 1 << searchLog`; row `row_log = clamp(searchLog, 4, 6)`; the
/// per-strategy sub-config carries the verbatim `hashLog` / `chainLog` /
/// `targetLength` / `minMatch`. Strategy numbers are upstream `ZSTD_strategy`
/// (fast=1, dfast=2, greedy=3, lazy=4, lazy2=5, btlazy2=6, btopt=7, btultra=8,
/// btultra2=9).
fn level_params_from_cparams(cp: crate::encoding::cparams::CParams) -> LevelParams {
    use crate::encoding::strategy::{SearchMethod, StrategyTag};
    let window_log = cp.window_log as u8;
    let search_depth = 1usize << cp.search_log;
    let target_len = cp.target_length as usize;
    let hc = HcConfig {
        hash_log: cp.hash_log as usize,
        chain_log: cp.chain_log as usize,
        search_depth,
        target_len,
        // Clamp UP to 4: C's BT finder uses mls=3 on L18-22, but our optimal
        // parser diverges on the resulting 3-byte matches (breaks level-22
        // sequence parity), so we keep the finder at >=4 as a workaround until
        // the parser is C-faithful at minMatch 3. See `HcConfig::search_mls` (#337).
        search_mls: cp.min_match.clamp(4, 6) as usize,
    };
    let row = RowConfig {
        hash_bits: cp.hash_log as usize,
        row_log: cp.search_log.clamp(4, 6) as usize,
        search_depth,
        target_len,
        mls: cp.min_match as usize,
        chain_log: cp.chain_log as usize,
        // Upstream `ZSTD_btlazy2` (strategy 6).
        bt: cp.strategy == 6,
    };
    let bt = |tag| LevelParams {
        strategy_tag: tag,
        search: SearchMethod::BinaryTree,
        window_log,
        lazy_depth: 2,
        fast: None,
        dfast: None,
        hc: Some(hc),
        row: None,
    };
    let row_lvl = |tag, search, lazy_depth| LevelParams {
        strategy_tag: tag,
        search,
        window_log,
        lazy_depth,
        fast: None,
        dfast: None,
        hc: None,
        row: Some(row),
    };
    match cp.strategy {
        1 => LevelParams {
            strategy_tag: StrategyTag::Fast,
            search: SearchMethod::Fast,
            window_log,
            lazy_depth: 0,
            // Upstream fast `stepSize`: `targetLength + 1` (0 -> 1, so step 2).
            fast: Some(FastConfig {
                hash_log: cp.hash_log,
                mls: fast_key_len(cp.min_match),
                step_size: target_len.max(1) + 1,
            }),
            dfast: None,
            hc: None,
            row: None,
        },
        2 => LevelParams {
            strategy_tag: StrategyTag::Dfast,
            search: SearchMethod::DoubleFast,
            window_log,
            lazy_depth: 1,
            fast: None,
            dfast: Some(DfastConfig {
                long_hash_log: cp.hash_log as u8,
                short_hash_log: cp.chain_log as u8,
            }),
            hc: None,
            row: None,
        },
        3 => row_lvl(StrategyTag::Greedy, SearchMethod::RowHash, 0),
        4 => row_lvl(StrategyTag::Lazy, SearchMethod::RowHash, 1),
        5 => row_lvl(StrategyTag::Lazy, SearchMethod::RowHash, 2),
        // btlazy2: the same lazy2 parse over the lazily-sorted binary tree.
        6 => row_lvl(StrategyTag::Btlazy2, SearchMethod::BinaryTreeLazy, 2),
        7 => bt(StrategyTag::BtOpt),
        8 => bt(StrategyTag::BtUltra),
        _ => bt(StrategyTag::BtUltra2),
    }
}

/// Down-size a synthesized backend's window / hash / chain logs for a known
/// source size by routing through the single C-faithful adjuster
/// [`adjust_cparams`](crate::encoding::cparams::adjust_cparams)
/// (`ZSTD_adjustCParams_internal`).
///
/// Used only on the param-override re-cap path: [`apply_param_overrides`]
/// synthesizes a backend's full-size default config when a strategy override
/// moves off the native level row, and this re-applies the source-size cap
/// C-faithfully — the SAME adjuster the `get_cparams` main path uses, so the
/// override path and the level path now down-size identically (no extra hinted
/// 16 KiB window floor, no per-backend headroom that diverged from C). The
/// Dfast backend self-sizes its tables in `reset`, so only its window is capped.
pub(crate) fn adjust_params_for_source_size(mut params: LevelParams, src_size: u64) -> LevelParams {
    use crate::encoding::cparams::{CParams, adjust_cparams};
    use crate::encoding::strategy::{BackendTag, StrategyTag};

    let backend = params.backend();
    // Lift the active backend's source-cappable logs into a flat CParams. Dfast
    // contributes none (window-only); its table widths self-size in `reset`.
    let (hash_log, chain_log): (u32, u32) = match backend {
        BackendTag::Simple => (params.fast.as_ref().map_or(0, |f| f.hash_log), 0),
        BackendTag::HashChain => params
            .hc
            .as_ref()
            .map_or((0, 0), |h| (h.hash_log as u32, h.chain_log as u32)),
        BackendTag::Row => params
            .row
            .as_ref()
            .map_or((0, 0), |r| (r.hash_bits as u32, r.chain_log as u32)),
        BackendTag::Dfast => (0, 0),
    };
    // `adjust_cparams` reads the strategy for the chain cap (`ZSTD_cycleLog`,
    // btlazy2 and up) and for the row-hash cap (greedy to lazy2, with the
    // search log as the row log), so it gets the real class and search log;
    // `Lazy` stands for lazy and lazy2, which both caps treat alike.
    let strategy = match params.strategy_tag {
        StrategyTag::Fast => 1,
        StrategyTag::Dfast => 2,
        StrategyTag::Greedy => 3,
        StrategyTag::Lazy => 4,
        StrategyTag::Btlazy2 => 6,
        StrategyTag::BtOpt => 7,
        StrategyTag::BtUltra => 8,
        StrategyTag::BtUltra2 => 9,
    };
    // `search_depth` is `1 << searchLog` on both backends that search.
    let search_log = match backend {
        BackendTag::HashChain => params
            .hc
            .as_ref()
            .map_or(1, |h| h.search_depth.trailing_zeros()),
        BackendTag::Row => params
            .row
            .as_ref()
            .map_or(1, |r| r.search_depth.trailing_zeros()),
        BackendTag::Simple | BackendTag::Dfast => 1,
    };
    let adj = adjust_cparams(
        CParams {
            window_log: u32::from(params.window_log),
            chain_log,
            hash_log,
            search_log,
            min_match: 4,
            target_length: 0,
            strategy,
        },
        src_size,
        0,
        false,
    );
    params.window_log = adj.window_log as u8;
    match backend {
        BackendTag::Simple => {
            if let Some(f) = params.fast.as_mut() {
                f.hash_log = adj.hash_log;
            }
        }
        BackendTag::HashChain => {
            if let Some(h) = params.hc.as_mut() {
                h.hash_log = adj.hash_log as usize;
                h.chain_log = adj.chain_log as usize;
            }
        }
        BackendTag::Row => {
            if let Some(r) = params.row.as_mut() {
                r.hash_bits = adj.hash_log as usize;
                r.chain_log = adj.chain_log as usize;
            }
        }
        BackendTag::Dfast => {}
    }
    params
}

/// Apply the caller's parameter overrides to the level params a frame
/// resolved to: the step the matcher's reset takes after the level (and a
/// dictionary's CDict tier) is resolved, kept in one place so the workspace
/// estimate builds exactly what the encoder does. An all-`None` set leaves the
/// params untouched, which keeps plain level-based geometry byte-identical.
pub(crate) fn apply_frame_overrides(
    params: &mut LevelParams,
    ov: &crate::encoding::parameters::ParamOverrides,
    dictionary_frame: bool,
    hint: Option<u64>,
) {
    if ov.is_empty() {
        return;
    }
    if dictionary_frame {
        // A dictionary frame runs the CDict's cParams (upstream
        // `ZSTD_resetCCtx_byAttachingCDict` / `byCopyingCDict`), and the
        // search knobs are already part of them
        // (`resolve_level_params_with_dict`); the frame's own knob is the
        // window.
        //
        // The window still answers to the source, as it does for every
        // other frame: `ZSTD_adjustCParams_internal` caps it by the source
        // and dictionary extent, and a window neither can fill only makes
        // decoders reserve memory the frame never uses. Capped here rather
        // than through the full adjuster, which would reshape the search.
        if let Some(window_log) = ov.window_log {
            params.window_log = match hint {
                // The source caps the window even here, and even with an
                // explicit request: the reference command declares 2 KiB
                // for `--ultra -22 --long=27 -D dict` on a 2 KiB file, and
                // a window the content cannot fill only makes every decoder
                // reserve memory the frame never uses. The floor that
                // travels with the cap in `adjust_cparams` applies too, or
                // a hint of a few dozen bytes asks for a window smaller
                // than the format's smallest.
                //
                // The dictionary's own size is NOT part of that cap: the
                // reference declares the same 2 KiB whether the dictionary
                // is 4 KiB or 256 KiB, because a small window does not put
                // the dictionary out of reach: sequences may reference it
                // at offsets beyond the window while the output so far is
                // within it (RFC 8878, Dictionary_Content). Counting it
                // made our frames ask decoders for up to 256x what the
                // reference asks.
                Some(src) => {
                    (crate::encoding::cparams::adjusted_window_log(u32::from(window_log), src, 0)
                        as u8)
                        .max(MIN_WINDOW_LOG)
                }
                None => window_log,
            };
        }
    } else {
        apply_param_overrides(params, ov);
        // The level's own resolution applied the source-size cap for the
        // LEVEL's native backend. If a strategy override moved the frame
        // onto a different backend, `apply_param_overrides` synthesized that
        // backend's DEFAULT config (FAST_L1 / HC_OVERRIDE_DEFAULT) with
        // full-size table logs AFTER that cap ran. Re-apply the hint cap so a
        // tiny hinted frame doesn't allocate the new backend's full-size
        // tables.
        //
        // The cap covers an explicit `window_log` too, as
        // `ZSTD_adjustCParams_internal` does upstream: the window is a
        // promise about the memory decoding will need, and a source that
        // cannot fill it makes that promise for nothing: every decoder
        // opening the frame would reserve the whole declared window to read
        // a few bytes. The override still raises the window as far as the
        // source can use.
        if let Some(hint_size) = hint {
            *params = adjust_params_for_source_size(*params, hint_size);
        }
    }
}

/// The long-distance matcher's parameters for a frame: the caller-pinned knobs
/// seeded first, then the upstream derivation fills the rest so the set stays
/// consistent (`hash_rate_log = window_log - hash_log`, and so on); clobbering
/// after the derivation would hand the producer an inconsistent set. Shared by
/// the matcher's reset and the workspace estimate.
#[cfg(feature = "ldm")]
pub(crate) fn frame_ldm_params(
    params: &LevelParams,
    ldm: &crate::encoding::parameters::LdmOverride,
) -> crate::encoding::ldm::params::LdmParams {
    let seed = crate::encoding::ldm::params::LdmParams {
        window_log: params.window_log as u32,
        hash_log: ldm.hash_log.unwrap_or(0),
        hash_rate_log: ldm.hash_rate_log.unwrap_or(0),
        min_match_length: ldm.min_match.unwrap_or(0),
        bucket_size_log: ldm.bucket_size_log.unwrap_or(0),
    };
    seed.derive(ldm_strategy_ordinal(params.strategy_tag, params.lazy_depth))
}

/// Estimated steady-state heap footprint of a one-shot compression context
/// at `level` (window history + match-finder tables + block staging), in
/// bytes. Computed from the same per-level tuning table the encoder
/// resolves at frame start, so the estimate tracks the real allocations;
/// it is an upper-bound style budget figure, not an exact accounting.
pub fn estimated_compression_workspace_bytes(level: CompressionLevel) -> usize {
    estimated_compression_workspace_bytes_for_source(level, None)
}

/// The same estimate for a source whose size is known.
///
/// The window and the match-finder tables are capped by the source, so a level
/// that would reserve hundreds of MiB for an arbitrary stream reserves a
/// fraction of that for a small one — and a caller budgeting memory for a
/// compression it is about to run knows which. `None` is the arbitrary-stream
/// figure that [`estimated_compression_workspace_bytes`] reports.
pub fn estimated_compression_workspace_bytes_for_source(
    level: CompressionLevel,
    src_size_hint: Option<u64>,
) -> usize {
    estimated_compression_workspace_bytes_for_run(level, src_size_hint, None, false, None)
}

/// The same estimate for a run whose window, long-distance matching and
/// dictionary are what the caller has actually asked for.
///
/// A `window_log` override enlarges the history the frame keeps, and
/// long-distance matching adds a hash table of its own on top — neither of them
/// visible in the level's own preset. A dictionary goes further than adding to
/// the figure: it *decides* it. The frame runs the dictionary's own compression
/// parameters, so a small source compressed against a large dictionary builds
/// tables sized for the dictionary, which at the higher levels is the
/// difference between tens of KiB and hundreds of MiB. `None`, `false` and
/// `None` give the preset, which is what
/// [`estimated_compression_workspace_bytes_for_source`] reports.
///
/// `dictionary` is what a caller weighing a run before it parses the blob can
/// answer with [`DictionarySizes::raw_content`] on the blob's own length: the
/// content of a trained dictionary is smaller than the blob it came in, and
/// overstating it can only move the estimate toward the copy-mode geometry,
/// which is the larger of the two.
///
/// [`DictionarySizes::raw_content`]: crate::encoding::DictionarySizes::raw_content
pub fn estimated_compression_workspace_bytes_for_run(
    level: CompressionLevel,
    src_size_hint: Option<u64>,
    window_log: Option<u8>,
    long_distance_matching: bool,
    dictionary: Option<crate::encoding::DictionarySizes>,
) -> usize {
    let mut params = match dictionary.filter(|sizes| sizes.content != 0) {
        Some(sizes) => {
            resolve_level_params_with_dict(
                level,
                src_size_hint,
                sizes,
                &crate::encoding::parameters::ParamOverrides::default(),
            )
            .0
        }
        None => resolve_level_params(level, src_size_hint),
    };
    // The override is what the frame will keep, but never below the floor the
    // format sets or above what the source can fill — the same two bounds the
    // encoder applies to it.
    if let Some(requested) = window_log {
        // Bounded to what the encoder itself accepts before anything shifts by
        // it. This answers for whatever it is asked, and a shift past the width
        // of the type is undefined rather than merely large: the largest window
        // there is, is the honest answer to a request beyond it.
        let requested = requested.min(MAX_ESTIMATED_WINDOW_LOG);
        let capped = match src_size_hint {
            Some(src) => {
                crate::encoding::cparams::adjusted_window_log(u32::from(requested), src, 0) as u8
            }
            None => requested,
        };
        params.window_log = capped.clamp(MIN_WINDOW_LOG, MAX_ESTIMATED_WINDOW_LOG);
    }
    // The long-distance matcher's own table, sized from the window it searches
    // (upstream `ZSTD_ldm_adjustParameters`). Only the `ldm` build has one.
    #[cfg(feature = "ldm")]
    let ldm = if long_distance_matching {
        let strategy = ldm_strategy_ordinal(params.strategy_tag, params.lazy_depth);
        crate::encoding::ldm::estimated_workspace_bytes(
            &crate::encoding::ldm::params::LdmParams::adjust_for(
                u32::from(params.window_log),
                strategy,
            ),
        )
    } else {
        0
    };
    #[cfg(not(feature = "ldm"))]
    let ldm = {
        let _ = long_distance_matching;
        0
    };
    workspace_bytes(&params, ldm)
}

/// The level params a frame resolves to under `parameters`, for a source of
/// `src_size_hint` bytes and an optional dictionary: the level (or the
/// dictionary's tier), then the caller's overrides, as the matcher's reset
/// resolves them.
pub(crate) fn frame_level_params(
    parameters: &crate::encoding::CompressionParameters,
    src_size_hint: Option<u64>,
    dictionary: Option<crate::encoding::DictionarySizes>,
) -> LevelParams {
    let level = parameters.level();
    let overrides = parameters.overrides();
    let dictionary = dictionary.filter(|sizes| sizes.content != 0);
    let mut params = match dictionary {
        Some(sizes) => resolve_level_params_with_dict(level, src_size_hint, sizes, &overrides).0,
        None => resolve_level_params(level, src_size_hint),
    };
    apply_frame_overrides(&mut params, &overrides, dictionary.is_some(), src_size_hint);
    params
}

/// The workspace estimate for a frame run under `parameters`: the level, every
/// knob that overrides it, the source size and the dictionary, resolved the way
/// the encoder resolves them at frame start.
///
/// [`estimated_compression_workspace_bytes_for_run`] answers for a level with a
/// window and long-distance matching on top; a caller that also sets `hashLog`,
/// `chainLog`, a strategy or the long-distance matcher's own table sizes needs
/// this one, since each of those resizes what the frame allocates. A dictionary
/// frame runs the geometry the dictionary is prepared with, the knobs included,
/// as the encoder does.
///
/// # Examples
///
/// ```
/// use structured_zstd::encoding::{
///     estimated_compression_workspace_bytes_for_parameters, CompressionLevel,
///     CompressionParameters,
/// };
///
/// let level = CompressionParameters::builder(CompressionLevel::Level(3)).build().unwrap();
/// let wide = CompressionParameters::builder(CompressionLevel::Level(3))
///     .window_log(27)
///     .hash_log(24)
///     .build()
///     .unwrap();
/// let source = Some(512 << 20);
/// assert!(
///     estimated_compression_workspace_bytes_for_parameters(&wide, source, None)
///         > estimated_compression_workspace_bytes_for_parameters(&level, source, None)
/// );
/// ```
pub fn estimated_compression_workspace_bytes_for_parameters(
    parameters: &crate::encoding::CompressionParameters,
    src_size_hint: Option<u64>,
    dictionary: Option<crate::encoding::DictionarySizes>,
) -> usize {
    let params = frame_level_params(parameters, src_size_hint, dictionary);
    #[cfg(feature = "ldm")]
    let ldm = parameters.overrides().ldm.map_or(0, |ldm| {
        crate::encoding::ldm::estimated_workspace_bytes(&frame_ldm_params(&params, &ldm))
    });
    #[cfg(not(feature = "ldm"))]
    let ldm = 0;
    workspace_bytes(&params, ldm)
}

/// `entry` bytes for each of `1 << log` slots, pinned at `usize::MAX` where
/// the table is more than a `usize` counts: the estimate is a budget, and a
/// figure that wrapped would call an impossible table affordable.
fn table_bytes(entry: usize, log: usize) -> usize {
    u32::try_from(log)
        .ok()
        .and_then(|log| 1usize.checked_shl(log))
        .and_then(|slots| slots.checked_mul(entry))
        .unwrap_or(usize::MAX)
}

/// Everything a compressor keeps for a frame resolved to `params`, plus `ldm`
/// bytes of long-distance table: the workspace (history, match-finder tables
/// and block buffers, laid out by the same functions the reset uses), and
/// what lives beside it (optimal-parser scratch, entropy tables, the block
/// splitter's state, the window's block deque).
fn workspace_bytes(params: &LevelParams, ldm: usize) -> usize {
    use crate::encoding::strategy::{SearchMethod, StrategyTag};
    use crate::encoding::workspace::{ALIGN, region_bytes};
    // A 30-bit window is a gibibyte, which a 32-bit `usize` cannot count: the
    // widest window is more memory than such a machine has, so the figure is
    // pinned rather than wrapped.
    let window = 1usize
        .checked_shl(u32::from(params.window_log))
        .unwrap_or(usize::MAX);
    let block = (crate::common::MAX_BLOCK_SIZE as usize).min(window);
    let backend = params.backend();
    let history = crate::encoding::match_generator::history_ceiling(backend, window, 0, block);
    // Mirror `configure()`: the HC3 short-match side table exists only on
    // the btultra/btultra2 tags (minMatch 3), capped by the window log; the
    // BT pointer-pair layout fits inside the `4 << chain_log` chain term
    // (pairs over `chain_log - 1` nodes).
    let wants_hash3 = matches!(
        params.strategy_tag,
        StrategyTag::BtUltra | StrategyTag::BtUltra2
    );
    let uses_bt = matches!(
        params.strategy_tag,
        StrategyTag::BtOpt | StrategyTag::BtUltra | StrategyTag::BtUltra2
    );
    // Only the backend `params.search` selects is built: `reset` swaps in one
    // matcher storage per frame. A strategy override leaves the level's own
    // row in place beside the one it synthesized, so summing every populated
    // config would charge a frame for tables it never allocates.
    // Every term goes through `table_bytes` and every sum saturates: an
    // override can ask for a table past what a 32-bit `usize` counts, and a
    // shift that dropped its high bits would report that table as free.
    let tables = match params.search {
        SearchMethod::Fast => params
            .fast
            .map_or(0, |f| table_bytes(4, f.hash_log as usize)),
        SearchMethod::DoubleFast => params.dfast.map_or(0, |d| {
            table_bytes(4, usize::from(d.long_hash_log))
                .saturating_add(table_bytes(4, usize::from(d.short_hash_log)))
        }),
        // The lazy backend's chain / tree finders (window <= 2^14, or a
        // btlazy2 level) use a plain hash table (`4 << hash_bits`) plus the
        // chain / tree table (`4 << chain_log`) instead of the row tables.
        SearchMethod::RowHash | SearchMethod::BinaryTreeLazy => params.row.map_or(0, |r| {
            if r.bt || params.window_log <= 14 {
                table_bytes(4, r.hash_bits).saturating_add(table_bytes(4, r.chain_log))
            } else {
                table_bytes(4, r.hash_bits).saturating_add(table_bytes(2, r.hash_bits))
            }
        }),
        SearchMethod::HashChain | SearchMethod::BinaryTree => params.hc.map_or(0, |h| {
            let hash3 = if wants_hash3 {
                table_bytes(
                    4,
                    crate::encoding::match_table::storage::HC3_HASH_LOG
                        .min(params.window_log as usize),
                )
            } else {
                0
            };
            table_bytes(4, h.hash_log)
                .saturating_add(table_bytes(4, h.chain_log))
                .saturating_add(hash3)
        }),
    };
    // BT modes box a `BtMatcher`; its retained scratch layout is budgeted
    // next to the struct so estimator and allocator evolve together.
    let bt = if uses_bt {
        crate::encoding::bt::BtMatcher::estimated_workspace_bytes()
    } else {
        0
    };
    // One allocation: each table region and the history rounded to `ALIGN`,
    // the block buffers behind them, and the padding that aligns its start.
    let laid_out = tables
        .saturating_add(3 * ALIGN)
        .saturating_add(region_bytes::<u8>(history))
        .saturating_add(crate::encoding::blocks::CompressedBlockScratch::workspace_bytes(block))
        .saturating_add(ALIGN - 1);
    // The backends that slide their window by blocks keep one length per
    // block in it, in a deque that grows by doubling. Plain arithmetic here
    // and in `beside`: `history / block` is at most the window over the
    // smallest block plus a few, and every term of `beside` is a constant or
    // bounded by the 128 KiB block, so neither comes near `usize::MAX`.
    let block_deque = if matches!(backend, crate::encoding::strategy::BackendTag::Simple) {
        0
    } else {
        2 * (history / block + 2) * core::mem::size_of::<usize>()
    };
    let splits =
        crate::encoding::levels::fastest::post_split_enabled(params.strategy_tag, window as u64);
    let beside = crate::encoding::frame_compressor::FseTables::max_heap_size()
        + crate::encoding::blocks::CompressedBlockScratch::max_retained_heap_size(block, splits)
        + 2 * crate::huff0::huff0_encoder::HuffmanTable::max_heap_size()
        + crate::huff0::huff0_encoder::WeightScratch::max_heap_size();
    // Saturating: the parts are each bounded, but their sum at the widest
    // window is more than a 32-bit `usize` counts, and a total that wrapped
    // would report a run as fitting a limit it cannot.
    laid_out
        .saturating_add(bt)
        .saturating_add(block_deque)
        .saturating_add(beside)
        .saturating_add(ldm)
}

/// Extra steady-state workspace the optimal strategies (ordinals 7..=9,
/// btopt..btultra2) retain beyond the hash/chain tables: the boxed matcher
/// plus its scratch arenas, and the HC3 short-match side table for
/// btultra/btultra2 (capped by the window log). 0 for the other ordinals
/// (btlazy2's tree lives in the lazy backend's chain table).
pub fn estimated_bt_strategy_extra_bytes(strategy_ordinal: u32, window_log: u32) -> usize {
    if !(7..=9).contains(&strategy_ordinal) {
        return 0;
    }
    let hash3 = if matches!(strategy_ordinal, 8 | 9) {
        4usize << crate::encoding::match_table::storage::HC3_HASH_LOG.min(window_log as usize)
    } else {
        0
    };
    crate::encoding::bt::BtMatcher::estimated_workspace_bytes() + hash3
}

/// Resolve a [`CompressionLevel`] (+ optional source-size hint) to the
/// concrete [`LevelParams`] the matcher runs: strategy tag, search method
/// (match-finder), window log, and per-backend config.
///
/// ## CRITICAL: input size changes the match-finder (and can change strategy)
///
/// The resolved geometry is a function of the SOURCE SIZE, not the level
/// alone. This is the easy-to-miss part (so read this before assuming a level
/// maps to one fixed match-finder). Every level except `Uncompressed` goes
/// through [`get_cparams`](crate::encoding::cparams::get_cparams), the port of
/// upstream zstd `ZSTD_getCParams_internal`, which runs its two stages:
///
/// 1. the `clevels.h` row for the (level, source-size tier) pair. The tier
///    changes the STRATEGY as well as the table widths: level 11 is lazy2 on
///    a large source and btopt on one of 16 KiB or less;
/// 2. `ZSTD_adjustCParams_internal`, which caps `window_log` to
///    ~`ceil_log2(source_size)` and shrinks the hash and chain logs to match.
///
/// THEN, inside the Row backend, the greedy/lazy band searches a hash chain
/// instead of rows when the resolved `window_log <= 14`
/// (`RowMatchGenerator::finder`) — exactly upstream's
/// `ZSTD_resolveRowMatchFinderMode` (the Row match-finder is used for
/// greedy/lazy/lazy2 ONLY when `windowLog > 14`) — and a btlazy2 level
/// searches the lazily-sorted binary tree; the parse itself is the same
/// `lazy_generic` body in all three cases. Net effect for the SAME level:
///
/// * small input (e.g. a 10 KiB fixture → `window_log` 14) → hash chain
///   (`ZSTD_HcFindBestMatch`, scalar chain walk);
/// * large input (e.g. 1 MiB → `window_log` 20) → rows (the SIMD-tag
///   row match-finder).
///
/// A dictionary frame resolves through [`resolve_level_params_with_dict`]
/// instead: the CDict's cParams (its own size tier) with the frame's
/// source-derived `window_log`. When comparing against C on a fixture,
/// resolve the match-finder from the fixture's size (and dictionary) first,
/// or you may optimise/benchmark a path C does not even take for that input.
pub(crate) fn resolve_level_params(
    level: CompressionLevel,
    source_size: Option<u64>,
) -> LevelParams {
    // Uncompressed = raw blocks, no match-finder. Not a cParams level, so it is
    // the one row resolved by hand rather than through `get_cparams`.
    if matches!(level, CompressionLevel::Uncompressed) {
        return LevelParams {
            strategy_tag: crate::encoding::strategy::StrategyTag::Fast,
            search: crate::encoding::strategy::SearchMethod::Fast,
            // Raw frames emit literal blocks and never reference history;
            // advertising a wider window only inflates the decoder-side buffer
            // reservation, so clamp to 17 (128 KiB) regardless of input size.
            window_log: 17,
            lazy_depth: 0,
            // Beyond-upstream: hash_log=14 (vs upstream's row-0 13) for ~2× fewer
            // collisions on structured corpora; mls=6 / step_size=2 mirror the
            // upstream "base for negative" row (targetLength=1 -> step 2).
            fast: Some(FastConfig {
                hash_log: 14,
                mls: 6,
                step_size: 2,
            }),
            dfast: None,
            hc: None,
            row: None,
        };
    }
    // Every other level resolves through the SINGLE C-faithful cParams source,
    // `cparams::get_cparams` (the port of `ZSTD_getCParams`). One place selects
    // strategy + table widths + the negative-level acceleration per
    // (level, srcSize) + the source-size window/hash down-clamp, so the encoder
    // never re-derives parameters from a parallel hand-tuned path. Named presets
    // map to their numeric level; the cParams source clamps out-of-range levels
    // (>22 to 22, negatives to MIN_CLEVEL) itself.
    let numeric = numeric_level(level);
    let src = source_size.unwrap_or(crate::encoding::cparams::CONTENTSIZE_UNKNOWN);
    level_params_from_cparams(crate::encoding::cparams::get_cparams(numeric, src, 0))
}

/// The upstream numeric level a preset maps to.
pub(crate) fn numeric_level(level: CompressionLevel) -> i32 {
    match level {
        CompressionLevel::Uncompressed => unreachable!("raw frames resolve no cParams"),
        // Fastest = upstream level 1 (fast strategy, smallest real-compression
        // tables).
        CompressionLevel::Fastest => 1,
        // Default = upstream level 3 (the libzstd default).
        CompressionLevel::Default => CompressionLevel::DEFAULT_LEVEL,
        // Better = level 7: the lazy2 band — clearly above the fast/dfast levels
        // on ratio while still well under the binary-tree cost cliff.
        CompressionLevel::Better => 7,
        // Best = level 13: the first point of the deep binary-tree band that
        // strictly dominates every level below it on ratio (lower levels can tie
        // on window-bound corpora), so the alias sits on a config that always
        // wins rather than on a hair-thin margin.
        CompressionLevel::Best => 13,
        CompressionLevel::Level(n) => n,
    }
}

/// How a greedy / lazy frame compressed with a dictionary takes its
/// match-finder from the dictionary's own cParams (upstream
/// `ZSTD_resetCCtx_usingCDict`).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct RowDictPlan {
    /// `ZSTD_shouldAttachDict`: the dictionary tables are searched in place
    /// (`dictMatchState`) instead of being copied into the frame's tables.
    pub(crate) attach: bool,
    /// The CDict's `useRowMatchFinder`, inherited by the frame.
    pub(crate) use_row: bool,
    /// The CDict's cParams: the geometry (`hash_log`, `chain_log`,
    /// `search_log` → row width) and key width its tables were built with.
    pub(crate) cdict: crate::encoding::cparams::CParams,
}

/// [`resolve_level_params`] for a frame that compresses with a dictionary of
/// `dict_size` bytes. Upstream builds the CDict with
/// `ZSTD_getCParams(level, UNKNOWN, dictSize, createCDict)` and the frame
/// then runs the CDict's strategy / widths / search depth / match-finder:
/// re-adjusted to the source when the dictionary is attached
/// (`ZSTD_resetCCtx_byAttachingCDict`), verbatim when it is copied
/// (`ZSTD_resetCCtx_byCopyingCDict`); only the frame's own `windowLog` is
/// kept. The CDict's strategy is taken whatever backend family the plain
/// level resolved to; a lazy-band CDict (greedy..btlazy2) also carries the
/// lazy backend's [`RowDictPlan`]. The caller's `overrides` are part of the
/// CDict's cParams, as they are for a dictionary upstream loads into a context
/// that carries them.
pub(crate) fn resolve_level_params_with_dict(
    level: CompressionLevel,
    source_size: Option<u64>,
    sizes: crate::encoding::DictionarySizes,
    overrides: &crate::encoding::parameters::ParamOverrides,
) -> (LevelParams, Option<RowDictPlan>) {
    use crate::encoding::cparams::{
        CONTENTSIZE_UNKNOWN, attach_cparams, copy_cparams, get_cdict_cparams, should_attach_dict,
        uses_row_match_finder,
    };
    let base = resolve_level_params(level, source_size);
    // A raw frame searches nothing, so a dictionary has no tier to give it.
    if sizes.content == 0 || matches!(level, CompressionLevel::Uncompressed) {
        return (base, None);
    }
    // The CDict's cParams decide the frame's strategy REGARDLESS of the
    // backend family the plain level resolved to for this source size
    // (upstream takes them unconditionally): L13 on a 4 KiB source is
    // btopt, but a 300 KiB CDict is btlazy2 and the frame runs btlazy2; L4
    // on a 1 MiB source is dfast, but a 4 KiB CDict is greedy. Only the
    // frame's own `windowLog` is kept.
    let cdict = get_cdict_cparams(numeric_level(level), sizes.serialized, overrides);
    // `ZSTD_shouldAttachDict`, bounded by the backend's attach representability:
    // the Fast / Dfast attached tables pack the dict position next to a tag, so
    // they index at most 2^24 content bytes. A larger dictionary is primed in
    // COPY mode, and the frame must then run the CDict's verbatim table
    // geometry (`byCopyingCDict`) — copying it into source-capped attach-mode
    // tables would collide away its matches.
    let attach_fits = match cdict.strategy {
        1 => sizes.content <= MAX_FAST_ATTACH_DICT_REGION,
        2 => sizes.content <= crate::encoding::dfast::DFAST_ATTACH_DICT_MAX_LEN,
        _ => true,
    };
    let attach = should_attach_dict(&cdict, source_size) && attach_fits;
    let window_log = u32::from(base.window_log);
    let frame = if attach {
        attach_cparams(
            cdict,
            source_size.unwrap_or(CONTENTSIZE_UNKNOWN),
            window_log,
        )
    } else {
        copy_cparams(cdict, window_log)
    };
    let params = level_params_from_cparams(frame);
    if !(3..=6).contains(&cdict.strategy) {
        // Fast / dfast / optimal strategies: their backends prime the
        // dictionary themselves; no lazy-backend plan.
        return (params, None);
    }
    (
        params,
        Some(RowDictPlan {
            attach,
            use_row: uses_row_match_finder(&cdict),
            cdict,
        }),
    )
}

/// The cheap fingerprint pre-splitter level for a compression level (the
/// C-like `blockSplitterLevel`), resolved through the same per-level
/// `LevelParams` table as every other tuning knob. `None` keeps the whole
/// 128 KiB block. The frame loop reads this instead of hardcoding the
/// level→split mapping at the call site.
pub(crate) fn level_pre_split(level: CompressionLevel) -> Option<usize> {
    // Resolve through `resolve_level_params` directly — NOT via the legacy
    // `numeric_level()` alias — so named presets read the SAME table row as
    // every other tuning knob (`Best` maps to its own row there, which is
    // not the row its numeric alias points at). `Uncompressed` (raw
    // blocks) never splits.
    if matches!(level, CompressionLevel::Uncompressed) {
        return None;
    }
    resolve_level_params(level, None)
        .pre_split()
        .map(usize::from)
}

#[cfg(test)]
mod tests;