use std::{
sync::Arc,
time::{Duration, Instant},
};
use crate::{
entropy::mem::highbit32,
error::{Error, Result},
sequence::{
RepeatOffsets, SequenceCommand, estimate_sequence_bit_cost, literal_length_code_unchecked,
ll_bits, match_length_code_unchecked, ml_bits, offset_code_unchecked,
},
};
mod binary_tree;
mod dict;
mod double_fast;
mod fast;
mod internal;
mod lazy;
mod ldm;
mod opt;
#[cfg(test)]
mod tests;
pub(crate) use self::binary_tree::*;
pub(crate) use self::dict::*;
pub(crate) use self::double_fast::*;
pub(crate) use self::fast::*;
pub(crate) use self::internal::*;
pub(crate) use self::lazy::*;
pub(crate) use self::ldm::*;
pub use self::ldm::LdmMode;
pub(crate) use self::opt::*;
#[derive(Debug, Clone)]
pub(crate) struct ContiguousBlockMatchState {
inner: ContiguousBlockMatchStateInner,
fast_table_next_to_update: usize,
built_with: MatchFinderParameters,
wide_entries: bool,
}
#[derive(Debug, Clone)]
enum ContiguousBlockMatchStateInner {
Chain(MatchFinder),
Fast(FastFinder),
WideFast(WideFastFinder),
DoubleFast(DoubleFastFinder),
WideDoubleFast(WideDoubleFastFinder),
Row(RowHashFinder),
BinaryTree(BinaryTreeFinder),
}
#[derive(Debug, Clone)]
pub(crate) struct PrefixedBlockMatchState {
inner: PrefixedBlockMatchStateInner,
fast_table_next_to_update: usize,
}
#[derive(Debug, Clone)]
enum PrefixedBlockMatchStateInner {
Chain {
prefix_finder: Arc<MatchFinder>,
src_finder: MatchFinder,
mode: PrefixMatchMode,
prefix_len: usize,
},
Fast {
prefix_finder: Option<Arc<FastFinder>>,
src_finder: FastFinder,
mode: PrefixMatchMode,
prepared: Option<Arc<PreparedFastDictionaryTables>>,
},
WideFast {
prefix_finder: Option<Arc<WideFastFinder>>,
src_finder: WideFastFinder,
mode: PrefixMatchMode,
prepared: Option<Arc<PreparedFastDictionaryTables>>,
},
DoubleFast {
prefix_finder: Option<Arc<DoubleFastFinder>>,
src_finder: DoubleFastFinder,
mode: PrefixMatchMode,
prepared: Option<Arc<PreparedDoubleFastDictionaryTables>>,
},
WideDoubleFast {
prefix_finder: Option<Arc<WideDoubleFastFinder>>,
src_finder: WideDoubleFastFinder,
mode: PrefixMatchMode,
prepared: Option<Arc<PreparedDoubleFastDictionaryTables>>,
},
Row {
prefix_finder: Arc<RowHashFinder>,
src_finder: RowHashFinder,
mode: PrefixMatchMode,
},
BinaryTree {
prefix_finder: Arc<BinaryTreeFinder>,
src_finder: BinaryTreeFinder,
mode: PrefixMatchMode,
},
}
fn new_prefixed_fast_finders<E: TaggedEntry>(
prefix: &[u8],
params: MatchFinderParameters,
mode: PrefixMatchMode,
) -> (Option<Arc<FastFinderImpl<E>>>, FastFinderImpl<E>) {
let prefix_finder = (mode == PrefixMatchMode::ExtDict).then(|| {
let mut finder = FastFinderImpl::new(params.dictionary_hash_bits(), params.min_match);
finder.insert_prefix_for_cdict(prefix);
Arc::new(finder)
});
let src_finder = FastFinderImpl::new(params.hash_bits, params.min_match);
(prefix_finder, src_finder)
}
fn new_prefixed_double_fast_finders<E: TaggedEntry>(
prefix: &[u8],
params: MatchFinderParameters,
mode: PrefixMatchMode,
) -> (
Option<Arc<DoubleFastFinderImpl<E>>>,
DoubleFastFinderImpl<E>,
) {
let prefix_finder = (mode == PrefixMatchMode::ExtDict).then(|| {
let mut finder = DoubleFastFinderImpl::new(
params.dictionary_hash_bits(),
params.dictionary_chain_log(),
params.min_match,
);
finder.insert_prefix_ext_dict(prefix);
Arc::new(finder)
});
let src_finder = DoubleFastFinderImpl::new(
params.hash_bits,
params.secondary_hash_bits,
params.min_match,
);
(prefix_finder, src_finder)
}
fn needs_wide_entries(params: MatchFinderParameters, position_limit: usize) -> bool {
matches!(
params.parser_strategy,
ParserStrategy::Fast | ParserStrategy::DoubleFast
) && position_limit > PACKED_TAGGED_POSITION_LIMIT
}
impl ContiguousBlockMatchState {
pub(crate) fn new(src_len: usize, params: MatchFinderParameters) -> Self {
Self::new_with_position_limit(src_len, src_len, params)
}
pub(crate) fn new_with_position_limit(
src_len: usize,
position_limit: usize,
params: MatchFinderParameters,
) -> Self {
let wide_entries = needs_wide_entries(params, position_limit);
let inner = match params.parser_strategy {
ParserStrategy::Fast if wide_entries => ContiguousBlockMatchStateInner::WideFast(
WideFastFinder::new(params.hash_bits, params.min_match),
),
ParserStrategy::Fast => ContiguousBlockMatchStateInner::Fast(FastFinder::new(
params.hash_bits,
params.min_match,
)),
ParserStrategy::DoubleFast if wide_entries => {
ContiguousBlockMatchStateInner::WideDoubleFast(WideDoubleFastFinder::new(
params.hash_bits,
params.secondary_hash_bits,
params.min_match,
))
}
ParserStrategy::DoubleFast => {
ContiguousBlockMatchStateInner::DoubleFast(DoubleFastFinder::new(
params.hash_bits,
params.secondary_hash_bits,
params.min_match,
))
}
strategy if strategy.is_row_hash() => ContiguousBlockMatchStateInner::Row(
RowHashFinder::new(params.hash_bits, params.search_log, params.min_match),
),
strategy if strategy.is_hash_chain() => {
ContiguousBlockMatchStateInner::Chain(MatchFinder::with_chain_log(
src_len,
params.hash_bits,
params.chain_log,
params.min_match,
))
}
strategy if strategy.is_binary_tree() => ContiguousBlockMatchStateInner::BinaryTree(
BinaryTreeFinder::new(params.hash_bits, params.chain_log, params.min_match)
.with_window_log(params.window_log)
.with_search_depth(params.search_depth),
),
_ => unreachable!(),
};
Self {
inner,
fast_table_next_to_update: 0,
built_with: params,
wide_entries,
}
}
pub(crate) fn reset(&mut self) {
match &mut self.inner {
ContiguousBlockMatchStateInner::Fast(finder) => finder.reset(),
ContiguousBlockMatchStateInner::WideFast(finder) => finder.reset(),
ContiguousBlockMatchStateInner::DoubleFast(finder) => finder.reset(),
ContiguousBlockMatchStateInner::WideDoubleFast(finder) => finder.reset(),
ContiguousBlockMatchStateInner::Row(finder) => finder.reset(),
ContiguousBlockMatchStateInner::Chain(finder) => finder.reset(),
ContiguousBlockMatchStateInner::BinaryTree(finder) => finder.reset(),
}
self.fast_table_next_to_update = 0;
}
pub(crate) fn reset_if_compatible(
&mut self,
params: MatchFinderParameters,
position_limit: usize,
) -> bool {
if self.built_with != params
|| self.wide_entries != needs_wide_entries(params, position_limit)
{
return false;
}
self.reset();
true
}
pub(crate) fn rebase_period(&self) -> usize {
match &self.inner {
ContiguousBlockMatchStateInner::Fast(_)
| ContiguousBlockMatchStateInner::WideFast(_)
| ContiguousBlockMatchStateInner::DoubleFast(_)
| ContiguousBlockMatchStateInner::WideDoubleFast(_)
| ContiguousBlockMatchStateInner::Row(_) => 1,
ContiguousBlockMatchStateInner::Chain(finder) => finder.rebase_period(),
ContiguousBlockMatchStateInner::BinaryTree(finder) => finder.rebase_period(),
}
}
pub(crate) fn shift_positions(&mut self, delta: usize, live_end: usize) -> bool {
let period = self.rebase_period();
let by_slot = live_end <= period;
if !by_slot && !delta.is_multiple_of(period) {
return false;
}
self.fast_table_next_to_update = self.fast_table_next_to_update.saturating_sub(delta);
match &mut self.inner {
ContiguousBlockMatchStateInner::Fast(finder) => finder.shift_positions(delta),
ContiguousBlockMatchStateInner::WideFast(finder) => finder.shift_positions(delta),
ContiguousBlockMatchStateInner::DoubleFast(finder) => finder.shift_positions(delta),
ContiguousBlockMatchStateInner::WideDoubleFast(finder) => finder.shift_positions(delta),
ContiguousBlockMatchStateInner::Row(finder) => finder.shift_positions(delta),
ContiguousBlockMatchStateInner::Chain(finder) if by_slot => {
finder.shift_positions_by_slot(delta, live_end);
}
ContiguousBlockMatchStateInner::Chain(finder) => finder.shift_positions(delta),
ContiguousBlockMatchStateInner::BinaryTree(finder) if by_slot => {
finder.shift_positions_by_slot(delta, live_end);
}
ContiguousBlockMatchStateInner::BinaryTree(finder) => finder.shift_positions(delta),
}
true
}
pub(crate) fn insert_range(&mut self, src: &[u8], start: usize, end: usize) {
match &mut self.inner {
ContiguousBlockMatchStateInner::Chain(finder) => finder.insert_range(src, start, end),
ContiguousBlockMatchStateInner::Fast(finder) => finder.insert_range(src, start, end),
ContiguousBlockMatchStateInner::WideFast(finder) => {
finder.insert_range(src, start, end)
}
ContiguousBlockMatchStateInner::DoubleFast(finder) => {
finder.insert_range(src, start, end)
}
ContiguousBlockMatchStateInner::WideDoubleFast(finder) => {
finder.insert_range(src, start, end)
}
ContiguousBlockMatchStateInner::Row(finder) => finder.insert_range(src, start, end),
ContiguousBlockMatchStateInner::BinaryTree(finder) => {
let depth = finder.default_search_depth;
finder.insert_range(src, start, end, depth)
}
}
}
fn bypassed_insert_start(&self, block_start: usize) -> usize {
match &self.inner {
ContiguousBlockMatchStateInner::Chain(finder) => finder.next_to_update.min(block_start),
ContiguousBlockMatchStateInner::Row(finder) => finder.next_to_update.min(block_start),
ContiguousBlockMatchStateInner::BinaryTree(finder) => {
finder.next_to_update.min(block_start)
}
ContiguousBlockMatchStateInner::Fast(_)
| ContiguousBlockMatchStateInner::WideFast(_)
| ContiguousBlockMatchStateInner::DoubleFast(_)
| ContiguousBlockMatchStateInner::WideDoubleFast(_) => block_start,
}
}
pub(crate) fn insert_rle_block(&mut self, src: &[u8], start: usize, end: usize) {
if end <= start {
return;
}
self.limit_update_after_long_match(start);
let start = self.bypassed_insert_start(start);
self.insert_range(src, start, end);
}
pub(crate) fn insert_range_for_uncompressed_block(
&mut self,
src: &[u8],
start: usize,
end: usize,
) {
if end <= start {
return;
}
if matches!(&self.inner, ContiguousBlockMatchStateInner::BinaryTree(_)) {
return;
}
let start = self.bypassed_insert_start(start);
self.insert_range(src, start, end);
}
fn limit_update_after_long_match(&mut self, block_start: usize) {
self.fast_table_next_to_update =
limited_update_after_long_match(self.fast_table_next_to_update, block_start);
match &mut self.inner {
ContiguousBlockMatchStateInner::Chain(finder) => {
finder.next_to_update =
limited_update_after_long_match(finder.next_to_update, block_start);
}
ContiguousBlockMatchStateInner::Row(finder) => {
finder.next_to_update =
limited_update_after_long_match(finder.next_to_update, block_start);
}
ContiguousBlockMatchStateInner::BinaryTree(finder) => {
finder.next_to_update =
limited_update_after_long_match(finder.next_to_update, block_start);
}
ContiguousBlockMatchStateInner::Fast(_)
| ContiguousBlockMatchStateInner::WideFast(_)
| ContiguousBlockMatchStateInner::DoubleFast(_)
| ContiguousBlockMatchStateInner::WideDoubleFast(_) => {}
}
}
fn limit_update_after_ldm_match(&mut self, segment_start: usize) {
let clamp = |cursor: usize| {
if segment_start <= cursor + LDM_LIMITED_UPDATE_LAG {
return cursor;
}
segment_start
- LDM_LIMITED_UPDATE_SPAN.min(segment_start - cursor - LDM_LIMITED_UPDATE_LAG)
};
self.fast_table_next_to_update = clamp(self.fast_table_next_to_update);
match &mut self.inner {
ContiguousBlockMatchStateInner::Chain(finder) => {
finder.next_to_update = clamp(finder.next_to_update);
}
ContiguousBlockMatchStateInner::Row(finder) => {
finder.next_to_update = clamp(finder.next_to_update);
}
ContiguousBlockMatchStateInner::BinaryTree(finder) => {
finder.next_to_update = clamp(finder.next_to_update);
}
ContiguousBlockMatchStateInner::Fast(_)
| ContiguousBlockMatchStateInner::WideFast(_)
| ContiguousBlockMatchStateInner::DoubleFast(_)
| ContiguousBlockMatchStateInner::WideDoubleFast(_) => {}
}
}
fn fill_fast_tables(&mut self, src: &[u8], end: usize) {
if !matches!(
&self.inner,
ContiguousBlockMatchStateInner::Fast(_)
| ContiguousBlockMatchStateInner::WideFast(_)
| ContiguousBlockMatchStateInner::DoubleFast(_)
| ContiguousBlockMatchStateInner::WideDoubleFast(_)
) {
return;
}
let Some(limit) = end.checked_sub(FAST_FILL_HASH_READ_SIZE + FAST_FILL_STEP - 2) else {
return;
};
let mut pos = self.fast_table_next_to_update;
macro_rules! fill {
($finder:expr) => {
while pos < limit {
$finder.insert_src_position(src, pos);
pos += FAST_FILL_STEP;
}
};
}
match &mut self.inner {
ContiguousBlockMatchStateInner::Fast(finder) => fill!(finder),
ContiguousBlockMatchStateInner::WideFast(finder) => fill!(finder),
ContiguousBlockMatchStateInner::DoubleFast(finder) => fill!(finder),
ContiguousBlockMatchStateInner::WideDoubleFast(finder) => fill!(finder),
_ => unreachable!("the strategy was checked above"),
}
}
}
impl PrefixedBlockMatchState {
#[allow(dead_code)]
pub(crate) fn new(prefix: &[u8], src_len: usize, params: MatchFinderParameters) -> Self {
Self::new_with_mode(prefix, src_len, params, PrefixMatchMode::ExtDict)
}
pub(crate) fn new_with_mode(
prefix: &[u8],
src_len: usize,
params: MatchFinderParameters,
mode: PrefixMatchMode,
) -> Self {
Self::new_with_prepared_match_state(prefix, src_len, params, mode, None)
}
pub(crate) fn new_with_prepared_match_state(
prefix: &[u8],
src_len: usize,
params: MatchFinderParameters,
mode: PrefixMatchMode,
prepared_match_state: Option<&PreparedDictionaryMatchState>,
) -> Self {
Self::new_with_prepared_match_state_and_position_limit(
prefix,
src_len,
src_len,
params,
mode,
prepared_match_state,
)
}
pub(crate) fn new_with_prepared_match_state_and_position_limit(
prefix: &[u8],
src_len: usize,
position_limit: usize,
params: MatchFinderParameters,
mode: PrefixMatchMode,
prepared_match_state: Option<&PreparedDictionaryMatchState>,
) -> Self {
let inner = match params.parser_strategy {
strategy if strategy.is_row_hash() => {
let prefix_finder = if let Some(PreparedDictionaryMatchState::Row(prefix_finder)) =
prepared_match_state
{
prefix_finder.prefix_finder()
} else {
let mut prefix_finder = RowHashFinder::new(
params.dictionary_hash_bits(),
params.search_log,
params.min_match,
);
prefix_finder.insert_prefix(prefix);
Arc::new(prefix_finder)
};
let mut src_finder =
RowHashFinder::new(params.hash_bits, params.search_log, params.min_match);
src_finder.hash_salt = prefix_finder.hash_salt;
PrefixedBlockMatchStateInner::Row {
prefix_finder,
src_finder,
mode,
}
}
strategy if strategy.is_hash_chain() => {
let prefix_finder =
if let Some(PreparedDictionaryMatchState::Chain(prefix_finder)) =
prepared_match_state
{
prefix_finder.prefix_finder()
} else {
let mut prefix_finder = MatchFinder::with_chain_log(
prefix.len(),
params.dictionary_hash_bits(),
params.dictionary_chain_log(),
params.min_match,
);
let prefix_refs = [prefix];
let prefix_chain = PrefixChain::new(&prefix_refs)
.expect("single prefix must not overflow")
.expect("single non-empty prefix expected");
prefix_finder.insert_prefix_chain(prefix_chain, &[]);
Arc::new(prefix_finder)
};
let src_finder = if mode == PrefixMatchMode::ExtDict {
prefix_finder.as_ref().clone()
} else {
MatchFinder::with_chain_log(
src_len,
params.hash_bits,
params.chain_log,
params.min_match,
)
};
PrefixedBlockMatchStateInner::Chain {
prefix_finder,
src_finder,
mode,
prefix_len: prefix.len(),
}
}
ParserStrategy::Fast => {
let prepared = match prepared_match_state {
Some(PreparedDictionaryMatchState::Fast(prepared)) => Some(prepared.clone()),
_ if mode == PrefixMatchMode::DictMatchState => {
Some(Arc::new(PreparedFastDictionaryTables::build(
prefix,
params.dictionary_hash_bits(),
params.min_match,
)))
}
_ => None,
};
if prefix.len().saturating_add(position_limit) > PACKED_TAGGED_POSITION_LIMIT {
let (prefix_finder, src_finder) =
new_prefixed_fast_finders::<u64>(prefix, params, mode);
PrefixedBlockMatchStateInner::WideFast {
prefix_finder,
src_finder,
mode,
prepared,
}
} else {
let (prefix_finder, src_finder) =
new_prefixed_fast_finders::<u32>(prefix, params, mode);
PrefixedBlockMatchStateInner::Fast {
prefix_finder,
src_finder,
mode,
prepared,
}
}
}
ParserStrategy::DoubleFast => {
let prepared = match prepared_match_state {
Some(PreparedDictionaryMatchState::DoubleFast(prepared)) => {
Some(prepared.clone())
}
_ if mode == PrefixMatchMode::DictMatchState => {
Some(Arc::new(PreparedDoubleFastDictionaryTables::build(
prefix,
params.dictionary_hash_bits(),
params.dictionary_chain_log(),
params.min_match,
)))
}
_ => None,
};
if prefix.len().saturating_add(position_limit) > PACKED_TAGGED_POSITION_LIMIT {
let (prefix_finder, src_finder) =
new_prefixed_double_fast_finders::<u64>(prefix, params, mode);
PrefixedBlockMatchStateInner::WideDoubleFast {
prefix_finder,
src_finder,
mode,
prepared,
}
} else {
let (prefix_finder, src_finder) =
new_prefixed_double_fast_finders::<u32>(prefix, params, mode);
PrefixedBlockMatchStateInner::DoubleFast {
prefix_finder,
src_finder,
mode,
prepared,
}
}
}
strategy if strategy.is_binary_tree() => {
let prefix_finder =
if let Some(PreparedDictionaryMatchState::BinaryTree(prefix_finder)) =
prepared_match_state
{
prefix_finder.prefix_finder()
} else {
let mut prefix_finder = BinaryTreeFinder::new(
params.dictionary_hash_bits(),
params.dictionary_chain_log(),
params.min_match,
)
.with_window_log(params.dictionary_window_log());
let prefix_refs = [prefix];
let prefix_chain = PrefixChain::new(&prefix_refs)
.expect("single prefix must not overflow")
.expect("single non-empty prefix expected");
prefix_finder.insert_prefix_chain(prefix_chain, &[], params.search_depth);
Arc::new(prefix_finder)
};
let mut src_finder =
BinaryTreeFinder::new(params.hash_bits, params.chain_log, params.min_match)
.with_window_log(params.window_log)
.with_search_depth(params.search_depth);
if mode == PrefixMatchMode::ExtDict {
let prefix_refs = [prefix];
if let Some(prefix_chain) = PrefixChain::new(&prefix_refs).ok().flatten() {
src_finder.insert_prefix_into_unified(
prefix_chain,
params.search_depth,
params.window_log,
);
src_finder.prefix_len = prefix_chain.len();
src_finder.next_to_update = prefix_chain.len();
}
}
PrefixedBlockMatchStateInner::BinaryTree {
prefix_finder,
src_finder,
mode,
}
}
_ => unreachable!(),
};
Self {
inner,
fast_table_next_to_update: 0,
}
}
pub(crate) fn insert_range(&mut self, src: &[u8], start: usize, end: usize) {
match &mut self.inner {
PrefixedBlockMatchStateInner::Chain {
src_finder,
mode,
prefix_len,
..
} => match mode {
PrefixMatchMode::DictMatchState => src_finder.insert_range(src, start, end),
PrefixMatchMode::ExtDict => {
src_finder.insert_ext_dict_range(*prefix_len, src, start, end)
}
},
PrefixedBlockMatchStateInner::Fast { src_finder, .. } => {
src_finder.insert_range(src, start, end)
}
PrefixedBlockMatchStateInner::WideFast { src_finder, .. } => {
src_finder.insert_range(src, start, end)
}
PrefixedBlockMatchStateInner::DoubleFast { src_finder, .. } => {
src_finder.insert_range(src, start, end)
}
PrefixedBlockMatchStateInner::WideDoubleFast { src_finder, .. } => {
src_finder.insert_range(src, start, end)
}
PrefixedBlockMatchStateInner::Row { src_finder, .. } => {
src_finder.insert_range(src, start, end)
}
PrefixedBlockMatchStateInner::BinaryTree { src_finder, .. } => {
if src_finder.prefix_len > 0 {
src_finder.dubt_insert_range_virtual(
src,
src_finder.next_to_update,
src_finder.prefix_len + end,
);
} else {
let depth = src_finder.default_search_depth;
src_finder.insert_range(src, start, end, depth)
}
}
}
}
fn limit_update_after_long_match(&mut self, block_start: usize) {
if let PrefixedBlockMatchStateInner::BinaryTree { src_finder, .. } = &mut self.inner {
src_finder.next_to_update = limited_update_after_long_match(
src_finder.next_to_update,
src_finder.prefix_len + block_start,
);
}
}
fn limit_update_after_ldm_match(&mut self, segment_start: usize) {
let clamp = |cursor: usize, segment_start: usize| {
if segment_start <= cursor + LDM_LIMITED_UPDATE_LAG {
return cursor;
}
segment_start
- LDM_LIMITED_UPDATE_SPAN.min(segment_start - cursor - LDM_LIMITED_UPDATE_LAG)
};
self.fast_table_next_to_update = clamp(self.fast_table_next_to_update, segment_start);
match &mut self.inner {
PrefixedBlockMatchStateInner::Chain {
src_finder,
mode,
prefix_len,
..
} => {
let segment_start = match mode {
PrefixMatchMode::DictMatchState => segment_start,
PrefixMatchMode::ExtDict => *prefix_len + segment_start,
};
src_finder.next_to_update = clamp(src_finder.next_to_update, segment_start);
}
PrefixedBlockMatchStateInner::Row { src_finder, .. } => {
src_finder.next_to_update = clamp(src_finder.next_to_update, segment_start);
}
PrefixedBlockMatchStateInner::BinaryTree { src_finder, .. } => {
src_finder.next_to_update = clamp(
src_finder.next_to_update,
src_finder.prefix_len + segment_start,
);
}
PrefixedBlockMatchStateInner::Fast { .. }
| PrefixedBlockMatchStateInner::WideFast { .. }
| PrefixedBlockMatchStateInner::DoubleFast { .. }
| PrefixedBlockMatchStateInner::WideDoubleFast { .. } => {}
}
}
fn fill_fast_tables(&mut self, src: &[u8], end: usize) {
if !matches!(
&self.inner,
PrefixedBlockMatchStateInner::Fast { .. }
| PrefixedBlockMatchStateInner::WideFast { .. }
| PrefixedBlockMatchStateInner::DoubleFast { .. }
| PrefixedBlockMatchStateInner::WideDoubleFast { .. }
) {
return;
}
let Some(limit) = end.checked_sub(FAST_FILL_HASH_READ_SIZE + FAST_FILL_STEP - 2) else {
return;
};
let mut pos = self.fast_table_next_to_update;
macro_rules! fill {
($finder:expr) => {
while pos < limit {
$finder.insert_src_position(src, pos);
pos += FAST_FILL_STEP;
}
};
}
match &mut self.inner {
PrefixedBlockMatchStateInner::Fast { src_finder, .. } => fill!(src_finder),
PrefixedBlockMatchStateInner::WideFast { src_finder, .. } => fill!(src_finder),
PrefixedBlockMatchStateInner::DoubleFast { src_finder, .. } => fill!(src_finder),
PrefixedBlockMatchStateInner::WideDoubleFast { src_finder, .. } => fill!(src_finder),
_ => unreachable!("the strategy was checked above"),
}
}
fn insert_block_tail(&mut self, src: &[u8], block_start: usize, block_end: usize) {
match &mut self.inner {
PrefixedBlockMatchStateInner::Fast { .. }
| PrefixedBlockMatchStateInner::WideFast { .. }
| PrefixedBlockMatchStateInner::DoubleFast { .. }
| PrefixedBlockMatchStateInner::WideDoubleFast { .. } => {}
_ => self.insert_range(src, block_start, block_end),
}
}
pub(crate) fn insert_range_for_uncompressed_block(
&mut self,
src: &[u8],
start: usize,
end: usize,
) {
if end <= start {
return;
}
if matches!(&self.inner, PrefixedBlockMatchStateInner::BinaryTree { .. }) {
return;
}
self.insert_range(src, start, end);
}
}
fn limited_update_after_long_match(next_to_update: usize, block_start: usize) -> usize {
if block_start <= next_to_update + LIMITED_UPDATE_LAG {
return next_to_update;
}
block_start - LIMITED_UPDATE_SPAN.min(block_start - next_to_update - LIMITED_UPDATE_LAG)
}
#[allow(dead_code)]
pub(crate) fn plan_sequences(src: &[u8], repeat_offsets: RepeatOffsets) -> Result<SequencePlan> {
plan_sequences_with_params(src, repeat_offsets, MatchFinderParameters::default())
}
#[allow(dead_code)]
pub(crate) fn plan_sequences_with_params(
src: &[u8],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<SequencePlan> {
let mut plan = SequencePlan::default();
plan_sequences_with_params_into(&mut plan, src, repeat_offsets, params)?;
Ok(plan)
}
#[allow(dead_code)]
pub(crate) fn plan_sequences_with_params_and_prefix(
src: &[u8],
prefix: &[u8],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<SequencePlan> {
let prefixes = [prefix];
plan_sequences_with_params_and_prefixes(src, &prefixes, repeat_offsets, params)
}
fn plan_sequences_with_params_into(
plan: &mut SequencePlan,
src: &[u8],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<()> {
plan_sequences_without_prefix_into(plan, src, repeat_offsets, params)
}
pub(crate) fn plan_sequences_with_params_and_prefixes(
src: &[u8],
prefixes: &[&[u8]],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<SequencePlan> {
let mut plan = SequencePlan::default();
plan_sequences_with_params_and_prefixes_into(&mut plan, src, prefixes, repeat_offsets, params)?;
Ok(plan)
}
fn plan_sequences_with_params_and_prefixes_into(
plan: &mut SequencePlan,
src: &[u8],
prefixes: &[&[u8]],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<()> {
let Some(prefix_chain) = PrefixChain::new(prefixes)? else {
return plan_sequences_without_prefix_into(plan, src, repeat_offsets, params);
};
plan_sequences_with_prefix_chain_into(plan, src, prefix_chain, repeat_offsets, params)
}
#[cfg_attr(not(test), allow(dead_code))]
pub(crate) fn plan_sequences_for_block(
src: &[u8],
prefixes: &[&[u8]],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<SequencePlan> {
let mut plan = SequencePlan::default();
plan_sequences_for_block_into(&mut plan, src, prefixes, repeat_offsets, params)?;
Ok(plan)
}
pub(crate) fn plan_sequences_for_block_into(
plan: &mut SequencePlan,
src: &[u8],
prefixes: &[&[u8]],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<()> {
match params.parser_strategy {
strategy if strategy.is_row_hash() => {
if prefixes.iter().all(|prefix| prefix.is_empty()) {
plan_sequences_row_without_prefix_into(plan, src, repeat_offsets, params)
} else {
plan_sequences_row_with_prefixes_into(plan, src, prefixes, repeat_offsets, params)
}
}
strategy if strategy.is_hash_chain() => {
if prefixes.iter().all(|prefix| prefix.is_empty()) {
plan_sequences_with_params_into(plan, src, repeat_offsets, params)
} else {
plan_sequences_with_params_and_prefixes_into(
plan,
src,
prefixes,
repeat_offsets,
params,
)
}
}
ParserStrategy::Fast => match single_non_empty_prefix(prefixes) {
Ok(Some(prefix)) => {
plan_sequences_fast_with_prefix_into(plan, src, prefix, repeat_offsets, params)
}
Ok(None) => plan_sequences_fast_without_prefix_into(plan, src, repeat_offsets, params),
Err(()) => plan_sequences_with_params_and_prefixes_into(
plan,
src,
prefixes,
repeat_offsets,
params,
),
},
ParserStrategy::DoubleFast => match single_non_empty_prefix(prefixes) {
Ok(Some(prefix)) => plan_sequences_double_fast_with_prefix_into(
plan,
src,
prefix,
repeat_offsets,
params,
),
Ok(None) => {
plan_sequences_double_fast_without_prefix_into(plan, src, repeat_offsets, params)
}
Err(()) => plan_sequences_with_params_and_prefixes_into(
plan,
src,
prefixes,
repeat_offsets,
params,
),
},
strategy if strategy.is_binary_tree() => match single_non_empty_prefix(prefixes) {
Ok(Some(prefix)) => plan_sequences_binary_tree_with_prefix_into(
plan,
src,
prefix,
repeat_offsets,
params,
),
Ok(None) => {
plan_sequences_binary_tree_without_prefix_into(plan, src, repeat_offsets, params)
}
Err(()) => plan_sequences_binary_tree_with_prefixes_into(
plan,
src,
prefixes,
repeat_offsets,
params,
),
},
_ => unreachable!(),
}
}
#[cfg_attr(not(test), allow(dead_code))]
pub(crate) fn plan_sequences_for_contiguous_block(
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut ContiguousBlockMatchState,
) -> Result<SequencePlan> {
let mut plan = SequencePlan::default();
plan_sequences_for_contiguous_block_into(
&mut plan,
src,
block_start,
repeat_offsets,
params,
max_history_bytes,
state,
)?;
Ok(plan)
}
pub(crate) fn plan_sequences_for_contiguous_block_into(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut ContiguousBlockMatchState,
) -> Result<()> {
plan_sequences_for_contiguous_block_into_with_candidates(
plan,
src,
block_start,
repeat_offsets,
params,
max_history_bytes,
state,
None,
)
}
#[allow(clippy::too_many_arguments)]
fn plan_sequences_for_contiguous_block_into_with_candidates(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut ContiguousBlockMatchState,
ldm: Option<&[RawSequence]>,
) -> Result<()> {
state.limit_update_after_long_match(block_start);
plan_sequences_for_contiguous_segment_into(
plan,
src,
block_start,
block_start.saturating_sub(max_history_bytes),
repeat_offsets,
params,
max_history_bytes,
state,
ldm,
)
}
#[allow(clippy::too_many_arguments)]
fn plan_sequences_for_contiguous_segment_into(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
rep_window_low: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut ContiguousBlockMatchState,
ldm: Option<&[RawSequence]>,
) -> Result<()> {
debug_assert!(
ldm.is_none() || matches!(state.inner, ContiguousBlockMatchStateInner::BinaryTree(_)),
"only the binary tree carries a parser that prices long-distance matches"
);
let window_low = src.len().saturating_sub(max_history_bytes).min(block_start);
let match_floor = MatchFloor::reaching(rep_window_low, max_history_bytes);
match &mut state.inner {
ContiguousBlockMatchStateInner::Row(finder) => plan_sequences_row_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
match_floor,
finder,
),
ContiguousBlockMatchStateInner::Chain(finder) => plan_sequences_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
match_floor,
finder,
),
ContiguousBlockMatchStateInner::Fast(finder) => {
plan_sequences_fast_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
window_low,
rep_window_low,
finder,
)
}
ContiguousBlockMatchStateInner::WideFast(finder) => {
plan_sequences_fast_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
window_low,
rep_window_low,
finder,
)
}
ContiguousBlockMatchStateInner::DoubleFast(finder) => {
plan_sequences_double_fast_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
window_low,
rep_window_low,
finder,
)
}
ContiguousBlockMatchStateInner::WideDoubleFast(finder) => {
plan_sequences_double_fast_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
window_low,
rep_window_low,
finder,
)
}
ContiguousBlockMatchStateInner::BinaryTree(finder) => {
plan_sequences_binary_tree_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
match_floor,
finder,
ldm,
)
}
}?;
Ok(())
}
#[derive(Debug, Clone)]
pub(crate) struct LdmFrameState {
matcher: LdmState,
max_distance: usize,
sequences: Vec<RawSequence>,
generated_for: Option<(usize, usize)>,
segment: SequencePlan,
}
impl LdmFrameState {
pub(crate) fn new(params: LdmParameters, max_distance: usize) -> Self {
Self {
matcher: LdmState::new(params),
max_distance,
sequences: Vec::new(),
generated_for: None,
segment: SequencePlan::default(),
}
}
pub(crate) fn shift_positions(&mut self, dropped: usize) {
self.matcher.shift_positions(dropped);
self.generated_for = self
.generated_for
.map(|(start, end)| (start.saturating_sub(dropped), end.saturating_sub(dropped)));
}
pub(crate) fn sequences_for_block(
&mut self,
dictionary: &[u8],
src: &[u8],
block_start: usize,
) -> &[RawSequence] {
let block = (block_start, src.len());
if self.generated_for == Some(block) {
return &self.sequences;
}
debug_assert!(
match self.generated_for {
Some((_, end)) => end == block_start,
None => true,
},
"a block the long-distance table has already passed cannot be generated for again"
);
let dictionary_len = dictionary.len();
self.sequences.clear();
self.matcher.generate_sequences(
LdmSource::with_dictionary(dictionary, src),
block_start + dictionary_len,
src.len() + dictionary_len,
self.max_distance,
&mut self.sequences,
);
self.generated_for = Some(block);
&self.sequences
}
pub(crate) fn load_dictionary(&mut self, dictionary: &[u8]) {
self.matcher.fill_from_dictionary(dictionary);
}
}
pub(crate) fn plan_sequences_for_contiguous_block_with_ldm_into(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut ContiguousBlockMatchState,
ldm: &mut LdmFrameState,
) -> Result<()> {
if params.parser_strategy.prices_long_distance_matches() {
let sequences = ldm.sequences_for_block(&[], src, block_start);
return plan_sequences_for_contiguous_block_into_with_candidates(
plan,
src,
block_start,
repeat_offsets,
params,
max_history_bytes,
state,
Some(sequences),
);
}
lay_down_long_distance_matches_into(
plan,
src,
block_start,
repeat_offsets,
params,
max_history_bytes,
state,
ldm,
)
}
#[allow(clippy::too_many_arguments)]
fn lay_down_long_distance_matches_into(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut ContiguousBlockMatchState,
ldm: &mut LdmFrameState,
) -> Result<()> {
let block_end = src.len();
ldm.sequences_for_block(&[], src, block_start);
let LdmFrameState {
sequences: ldm_sequences,
segment,
..
} = ldm;
state.limit_update_after_long_match(block_start);
let rep_window_low = block_start.saturating_sub(max_history_bytes);
plan.reset_for_block(block_end - block_start);
plan.repeat_offsets = repeat_offsets;
let mut literals_claimed = 0usize;
let mut position = block_start;
for index in 0..ldm_sequences.len() {
let raw = ldm_sequences[index];
let literal_length = raw.literal_length as usize;
let match_length = raw.match_length as usize;
debug_assert!(
position + literal_length + match_length <= block_end,
"a long-distance sequence ran past the block it was generated for"
);
state.limit_update_after_ldm_match(position);
state.fill_fast_tables(src, position);
plan_sequences_for_contiguous_segment_into(
segment,
&src[..position + literal_length],
position,
rep_window_low,
plan.repeat_offsets,
params,
max_history_bytes,
state,
None,
)?;
literals_claimed += append_segment_plan(plan, segment);
position += literal_length;
let off_base = plan.repeat_offsets.update_explicit_offset(raw.offset);
let trailing_literals = plan.literals.len() - literals_claimed;
plan.push_stored_sequence(SequenceCommand {
literal_length: trailing_literals as u32,
offset_value: off_base,
match_length: raw.match_length,
});
literals_claimed = plan.literals.len();
position += match_length;
}
state.limit_update_after_ldm_match(position);
state.fill_fast_tables(src, position);
plan_sequences_for_contiguous_segment_into(
segment,
src,
position,
rep_window_low,
plan.repeat_offsets,
params,
max_history_bytes,
state,
None,
)?;
append_segment_plan(plan, segment);
Ok(())
}
fn append_segment_plan(plan: &mut SequencePlan, segment: &SequencePlan) -> usize {
plan.literals.extend_from_slice(&segment.literals);
plan.sequences.extend_from_slice(&segment.sequences);
plan.literal_codes.extend_from_slice(&segment.literal_codes);
plan.offset_codes.extend_from_slice(&segment.offset_codes);
plan.match_codes.extend_from_slice(&segment.match_codes);
if plan.trace_enabled {
plan.trace_match_sources
.extend_from_slice(&segment.trace_match_sources);
plan.trace_emissions
.extend_from_slice(&segment.trace_emissions);
plan.trace_row_searches
.extend_from_slice(&segment.trace_row_searches);
plan.trace_row_lazy_probes
.extend_from_slice(&segment.trace_row_lazy_probes);
#[cfg(test)]
plan.trace_chain_searches
.extend_from_slice(&segment.trace_chain_searches);
}
plan.repeat_offsets = segment.repeat_offsets;
segment
.sequences
.iter()
.map(|sequence| sequence.literal_length as usize)
.sum()
}
#[cfg_attr(not(test), allow(dead_code))]
pub(crate) fn plan_sequences_for_prefixed_contiguous_block(
prefix: &[u8],
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut PrefixedBlockMatchState,
) -> Result<SequencePlan> {
let mut plan = SequencePlan::default();
plan_sequences_for_prefixed_contiguous_block_into(
&mut plan,
prefix,
src,
block_start,
repeat_offsets,
params,
max_history_bytes,
state,
)?;
Ok(plan)
}
pub(crate) fn plan_sequences_for_prefixed_contiguous_block_into(
plan: &mut SequencePlan,
prefix: &[u8],
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut PrefixedBlockMatchState,
) -> Result<()> {
state.limit_update_after_long_match(block_start);
let floors = prefixed_block_floors(
prefix,
block_start,
src.len(),
max_history_bytes,
params.prefix_low_limit,
);
plan_sequences_for_prefixed_contiguous_segment_into(
plan,
prefix,
src,
block_start,
floors,
repeat_offsets,
params,
state,
None,
)?;
state.insert_block_tail(src, block_start, src.len());
Ok(())
}
#[derive(Debug, Clone, Copy)]
struct PrefixedBlockFloors {
match_floor: PrefixedMatchFloor,
prefix_low: usize,
source_low: usize,
rep_window_low: usize,
prefix_retired: bool,
}
fn prefixed_block_floors(
prefix: &[u8],
block_start: usize,
block_end: usize,
max_history_bytes: usize,
prefix_low_limit: usize,
) -> PrefixedBlockFloors {
let (prefix_low, source_low) = prefixed_window_lows(
prefix.len(),
block_start,
block_end,
max_history_bytes,
prefix_low_limit,
);
let prefix_retired = prefix_low >= prefix.len();
let match_floor = if prefix_retired {
PrefixedMatchFloor::reaching(
prefix.len(),
MatchFloor::reaching(
prefix
.len()
.saturating_add(block_start.saturating_sub(max_history_bytes)),
max_history_bytes,
),
)
} else {
PrefixedMatchFloor::fixed(prefix_low, source_low)
};
PrefixedBlockFloors {
match_floor,
prefix_low,
source_low,
rep_window_low: block_start.saturating_sub(max_history_bytes),
prefix_retired,
}
}
#[allow(clippy::too_many_arguments)]
fn plan_sequences_for_prefixed_contiguous_segment_into(
plan: &mut SequencePlan,
prefix: &[u8],
src: &[u8],
block_start: usize,
floors: PrefixedBlockFloors,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
state: &mut PrefixedBlockMatchState,
ldm: Option<&[RawSequence]>,
) -> Result<()> {
debug_assert!(
ldm.is_none() || matches!(state.inner, PrefixedBlockMatchStateInner::BinaryTree { .. }),
"only the binary tree carries a parser that prices long-distance matches"
);
let PrefixedBlockFloors {
match_floor,
prefix_low,
source_low,
rep_window_low,
prefix_retired,
} = floors;
let (repeat_offsets, saved1, saved2) = if prefix_retired {
let (clamped, _, _, saved1, saved2) = invalidate_no_dict_repeat_offsets(
repeat_offsets,
block_start,
match_floor.at(block_start).1,
);
(clamped, saved1, saved2)
} else {
(repeat_offsets, 0, 0)
};
let restore = |plan: &mut SequencePlan| {
if prefix_retired {
plan.repeat_offsets =
restore_invalidated_repeat_offsets(plan.repeat_offsets, saved1, saved2);
}
};
let result = match &mut state.inner {
PrefixedBlockMatchStateInner::Row {
prefix_finder,
src_finder,
mode,
} => match mode {
PrefixMatchMode::ExtDict => {
let prefix_refs = [prefix];
let prefix_chain = PrefixChain::new(&prefix_refs)?
.expect("prefixed contiguous planning requires a non-empty prefix");
plan_sequences_row_ext_dict_from_into(
plan,
src,
block_start,
prefix_chain,
repeat_offsets,
params,
match_floor,
prefix_finder.as_ref(),
src_finder,
)
}
PrefixMatchMode::DictMatchState => plan_sequences_row_dict_match_state_from_into(
plan,
src,
block_start,
prefix,
repeat_offsets,
params,
match_floor,
prefix_finder.as_ref(),
src_finder,
),
},
PrefixedBlockMatchStateInner::Chain {
prefix_finder,
src_finder,
mode,
..
} => {
let prefix_refs = [prefix];
let prefix_chain = PrefixChain::new(&prefix_refs)?
.expect("prefixed contiguous planning requires a non-empty prefix");
if *mode == PrefixMatchMode::DictMatchState {
plan_sequences_chain_dict_match_state_with_prefix_chain_from_into(
plan,
src,
block_start,
prefix_chain,
repeat_offsets,
params,
match_floor,
prefix_finder.as_ref(),
src_finder,
)
} else {
plan_sequences_chain_ext_dict_with_prefix_chain_from_into(
plan,
src,
block_start,
prefix_chain,
repeat_offsets,
params,
match_floor,
src_finder,
)
}
}
PrefixedBlockMatchStateInner::Fast {
prefix_finder,
src_finder,
mode,
prepared,
} => {
if prefix_retired {
plan_sequences_fast_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
source_low,
rep_window_low,
src_finder,
)
} else {
plan_sequences_fast_with_prefix_from_into(
plan,
src,
block_start,
prefix,
repeat_offsets,
params,
prefix_low,
source_low,
prefix_finder.as_deref(),
src_finder,
*mode,
prepared.as_deref(),
)
}
}
PrefixedBlockMatchStateInner::WideFast {
prefix_finder,
src_finder,
mode,
prepared,
} => {
if prefix_retired {
plan_sequences_fast_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
source_low,
rep_window_low,
src_finder,
)
} else {
plan_sequences_fast_with_prefix_from_into(
plan,
src,
block_start,
prefix,
repeat_offsets,
params,
prefix_low,
source_low,
prefix_finder.as_deref(),
src_finder,
*mode,
prepared.as_deref(),
)
}
}
PrefixedBlockMatchStateInner::DoubleFast {
prefix_finder,
src_finder,
mode,
prepared,
} => plan_sequences_double_fast_with_prefix_from_into(
plan,
src,
block_start,
prefix,
repeat_offsets,
params,
prefix_low,
source_low,
prefix_finder.as_deref(),
src_finder,
*mode,
prepared.as_deref(),
),
PrefixedBlockMatchStateInner::WideDoubleFast {
prefix_finder,
src_finder,
mode,
prepared,
} => plan_sequences_double_fast_with_prefix_from_into(
plan,
src,
block_start,
prefix,
repeat_offsets,
params,
prefix_low,
source_low,
prefix_finder.as_deref(),
src_finder,
*mode,
prepared.as_deref(),
),
PrefixedBlockMatchStateInner::BinaryTree {
prefix_finder,
src_finder,
mode,
} => plan_sequences_binary_tree_with_prefix_from_into(
plan,
src,
block_start,
prefix,
repeat_offsets,
params,
match_floor,
prefix_finder.as_ref(),
src_finder,
*mode,
ldm,
),
};
restore(plan);
result
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn plan_sequences_for_prefixed_contiguous_block_with_ldm_into(
plan: &mut SequencePlan,
prefix: &[u8],
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut PrefixedBlockMatchState,
ldm: &mut LdmFrameState,
) -> Result<()> {
if params.parser_strategy.prices_long_distance_matches() {
state.limit_update_after_long_match(block_start);
let floors = prefixed_block_floors(
prefix,
block_start,
src.len(),
max_history_bytes,
params.prefix_low_limit,
);
let sequences = ldm.sequences_for_block(prefix, src, block_start);
plan_sequences_for_prefixed_contiguous_segment_into(
plan,
prefix,
src,
block_start,
floors,
repeat_offsets,
params,
state,
Some(sequences),
)?;
state.insert_block_tail(src, block_start, src.len());
return Ok(());
}
lay_down_long_distance_matches_prefixed_into(
plan,
prefix,
src,
block_start,
repeat_offsets,
params,
max_history_bytes,
state,
ldm,
)
}
#[allow(clippy::too_many_arguments)]
fn lay_down_long_distance_matches_prefixed_into(
plan: &mut SequencePlan,
prefix: &[u8],
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
max_history_bytes: usize,
state: &mut PrefixedBlockMatchState,
ldm: &mut LdmFrameState,
) -> Result<()> {
let block_end = src.len();
state.limit_update_after_long_match(block_start);
let floors = prefixed_block_floors(
prefix,
block_start,
block_end,
max_history_bytes,
params.prefix_low_limit,
);
ldm.sequences_for_block(prefix, src, block_start);
let LdmFrameState {
sequences: ldm_sequences,
segment,
..
} = ldm;
plan.reset_for_block(block_end - block_start);
plan.repeat_offsets = repeat_offsets;
let mut literals_claimed = 0usize;
let mut position = block_start;
for index in 0..ldm_sequences.len() {
let raw = ldm_sequences[index];
let literal_length = raw.literal_length as usize;
let match_length = raw.match_length as usize;
debug_assert!(
position + literal_length + match_length <= block_end,
"a long-distance sequence ran past the block it was generated for"
);
state.limit_update_after_ldm_match(position);
state.fill_fast_tables(src, position);
plan_sequences_for_prefixed_contiguous_segment_into(
segment,
prefix,
&src[..position + literal_length],
position,
floors,
plan.repeat_offsets,
params,
state,
None,
)?;
literals_claimed += append_segment_plan(plan, segment);
position += literal_length;
let off_base = plan.repeat_offsets.update_explicit_offset(raw.offset);
let trailing_literals = plan.literals.len() - literals_claimed;
plan.push_stored_sequence(SequenceCommand {
literal_length: trailing_literals as u32,
offset_value: off_base,
match_length: raw.match_length,
});
literals_claimed = plan.literals.len();
position += match_length;
}
state.limit_update_after_ldm_match(position);
state.fill_fast_tables(src, position);
plan_sequences_for_prefixed_contiguous_segment_into(
segment,
prefix,
src,
position,
floors,
plan.repeat_offsets,
params,
state,
None,
)?;
append_segment_plan(plan, segment);
state.insert_block_tail(src, block_start, block_end);
Ok(())
}
fn prefixed_window_lows(
prefix_len: usize,
block_start: usize,
block_end: usize,
history_limit: usize,
prefix_low_limit: usize,
) -> (usize, usize) {
let trim = prefix_len
.saturating_add(block_end)
.saturating_sub(history_limit);
if trim > prefix_len {
(prefix_len, (trim - prefix_len).min(block_start))
} else {
(prefix_low_limit.min(prefix_len), 0)
}
}
fn single_non_empty_prefix<'a>(
prefixes: &'a [&'a [u8]],
) -> core::result::Result<Option<&'a [u8]>, ()> {
let mut single = None;
for prefix in prefixes.iter().copied().filter(|prefix| !prefix.is_empty()) {
if single.replace(prefix).is_some() {
return Err(());
}
}
Ok(single)
}