use super::*;
const OPT_REPCODE_MIN_MATCH: usize = 3;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum OptimalPriceType {
Predefined,
Dynamic,
}
#[derive(Debug, Clone)]
pub(crate) struct OptimalPriceModel<const IS_ULTRA: bool> {
pub(crate) price_type: OptimalPriceType,
pub(crate) ll_freq: [u32; 36],
pub(crate) ml_freq: [u32; 53],
pub(crate) of_freq: [u32; 32],
pub(crate) ll_sum: u32,
pub(crate) ml_sum: u32,
pub(crate) of_sum: u32,
pub(crate) lit_freq: [u32; 256],
pub(crate) lit_sum: u32,
pub(crate) ll_sum_base_price: u32,
pub(crate) ml_sum_base_price: u32,
pub(crate) of_sum_base_price: u32,
pub(crate) lit_sum_base_price: u32,
ml_price_by_code: [u32; 53],
pub(crate) long_offset_penalty: bool,
pub(crate) compressed_literals: bool,
}
const MAX_PRICE: u32 = 1 << 30;
#[derive(Debug, Clone, Copy)]
#[repr(C)]
pub(crate) struct OptimalPathNode {
pub(crate) price: u32,
pub(crate) off: u32,
pub(crate) mlen: u32,
pub(crate) litlen: u32,
pub(crate) reps: [u32; 3],
}
impl Default for OptimalPathNode {
#[inline(always)]
fn default() -> Self {
Self {
price: MAX_PRICE,
off: 0,
mlen: 0,
litlen: 0,
reps: [0; 3],
}
}
}
impl OptimalPathNode {
pub(crate) const UNSET: Self = Self {
price: MAX_PRICE,
off: 0,
mlen: 0,
litlen: 0,
reps: [0; 3],
};
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct OptimalMatchCandidate {
pub(crate) offset_value: u32,
pub(crate) length: u32,
}
#[derive(Debug, Clone, Copy)]
struct LdmCandidateSpan {
start: u32,
end: u32,
offset: u32,
}
struct LdmCandidates<'a> {
cursor: RawSequenceCursor<'a>,
span: Option<LdmCandidateSpan>,
}
impl<'a> LdmCandidates<'a> {
fn new(sequences: &'a [RawSequence], block_len: u32) -> Self {
let mut candidates = Self {
cursor: RawSequenceCursor::new(sequences),
span: None,
};
candidates.arm_next_match(0, block_len);
candidates
}
fn arm_next_match(&mut self, position_in_block: u32, block_bytes_remaining: u32) {
let Some(current) = self.cursor.current() else {
self.span = None;
return;
};
let block_end = position_in_block + block_bytes_remaining;
let consumed = self.cursor.offset_in_sequence();
debug_assert!(consumed <= current.literal_length + current.match_length);
let literals_remaining = current.literal_length.saturating_sub(consumed);
let match_remaining = if literals_remaining == 0 {
current.match_length - (consumed - current.literal_length)
} else {
current.match_length
};
if literals_remaining >= block_bytes_remaining {
self.span = None;
self.cursor.skip_bytes(block_bytes_remaining as usize);
return;
}
let start = position_in_block + literals_remaining;
let end = start + match_remaining;
if end > block_end {
self.span = Some(LdmCandidateSpan {
start,
end: block_end,
offset: current.offset,
});
self.cursor
.skip_bytes((block_end - position_in_block) as usize);
} else {
self.span = Some(LdmCandidateSpan {
start,
end,
offset: current.offset,
});
self.cursor
.skip_bytes((literals_remaining + match_remaining) as usize);
}
}
fn offer(
&mut self,
candidates: &mut Vec<OptimalMatchCandidate>,
position_in_block: u32,
block_bytes_remaining: u32,
min_match: u32,
) {
if self.cursor.current().is_none() {
return;
}
if let Some(span) = self.span {
if position_in_block >= span.end {
let overshoot = position_in_block - span.end;
if overshoot > 0 {
self.cursor.skip_bytes(overshoot as usize);
}
self.arm_next_match(position_in_block, block_bytes_remaining);
}
}
self.add_match(candidates, position_in_block, min_match);
}
fn add_match(
&self,
candidates: &mut Vec<OptimalMatchCandidate>,
position_in_block: u32,
min_match: u32,
) {
let Some(span) = self.span else {
return;
};
if position_in_block < span.start || position_in_block >= span.end {
return;
}
let length = span.end - position_in_block;
if length < min_match {
return;
}
if candidates.len() >= OPT_NUM {
return;
}
if let Some(last) = candidates.last() {
if length <= last.length {
return;
}
}
candidates.push(OptimalMatchCandidate {
offset_value: span.offset + 3,
length,
});
}
}
pub(crate) fn plan_sequences_binary_tree_without_prefix_into(
plan: &mut SequencePlan,
src: &[u8],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<()> {
let mut finder = BinaryTreeFinder::new(params.hash_bits, params.chain_log, params.min_match)
.with_window_log(params.window_log);
plan_sequences_binary_tree_without_prefix_from_into(
plan,
src,
0,
repeat_offsets,
params,
MatchFloor::fixed(0),
&mut finder,
None,
)
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn plan_sequences_binary_tree_without_prefix_from_into(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
match_floor: MatchFloor,
finder: &mut BinaryTreeFinder,
ldm: Option<&[RawSequence]>,
) -> Result<()> {
match params.parser_strategy {
ParserStrategy::BinaryTreeOpt => plan_sequences_optimal_without_prefix_into::<false>(
plan,
src,
block_start,
repeat_offsets,
params,
match_floor,
finder,
ldm,
),
ParserStrategy::BinaryTreeUltra | ParserStrategy::BinaryTreeUltra2 => {
plan_sequences_optimal_without_prefix_into::<true>(
plan,
src,
block_start,
repeat_offsets,
params,
match_floor,
finder,
ldm,
)
}
_ => {
debug_assert!(
ldm.is_none(),
"only the optimal parsers price long-distance matches"
);
plan_sequences_without_prefix_from_into(
plan,
src,
block_start,
repeat_offsets,
params,
match_floor,
finder,
)
}
}
}
pub(crate) fn plan_sequences_binary_tree_with_prefix_into(
plan: &mut SequencePlan,
src: &[u8],
prefix: &[u8],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<()> {
let prefix_refs = [prefix];
plan_sequences_binary_tree_with_prefixes_into(plan, src, &prefix_refs, repeat_offsets, params)
}
pub(crate) fn plan_sequences_binary_tree_with_prefixes_into(
plan: &mut SequencePlan,
src: &[u8],
prefixes: &[&[u8]],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
) -> Result<()> {
let prefix_chain = PrefixChain::new(prefixes)?
.expect("binary-tree prefix planning requires a non-empty prefix");
let mut prefix_finder =
BinaryTreeFinder::new(params.hash_bits, params.chain_log, params.min_match)
.with_window_log(params.window_log);
prefix_finder.insert_prefix_chain(prefix_chain, src, params.search_depth);
let mut src_finder =
BinaryTreeFinder::new(params.hash_bits, params.chain_log, params.min_match)
.with_window_log(params.window_log);
plan_sequences_binary_tree_with_prefix_chain_from_into(
plan,
src,
0,
prefix_chain,
repeat_offsets,
params,
PrefixedMatchFloor::fixed(0, 0),
&prefix_finder,
&mut src_finder,
PrefixMatchMode::ExtDict,
None,
)
}
pub(crate) fn plan_sequences_binary_tree_with_prefix_from_into(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
prefix: &[u8],
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
match_floor: PrefixedMatchFloor,
prefix_finder: &BinaryTreeFinder,
src_finder: &mut BinaryTreeFinder,
mode: PrefixMatchMode,
ldm: Option<&[RawSequence]>,
) -> Result<()> {
let prefix_refs = [prefix];
let prefix_chain = PrefixChain::new(&prefix_refs)?
.expect("binary-tree prefix planning requires a non-empty prefix");
plan_sequences_binary_tree_with_prefix_chain_from_into(
plan,
src,
block_start,
prefix_chain,
repeat_offsets,
params,
match_floor,
prefix_finder,
src_finder,
mode,
ldm,
)
}
pub(crate) fn plan_sequences_binary_tree_with_prefix_chain_from_into(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
prefix_chain: PrefixChain<'_>,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
match_floor: PrefixedMatchFloor,
prefix_finder: &BinaryTreeFinder,
src_finder: &mut BinaryTreeFinder,
mode: PrefixMatchMode,
ldm: Option<&[RawSequence]>,
) -> Result<()> {
match params.parser_strategy {
ParserStrategy::BinaryTreeOpt
| ParserStrategy::BinaryTreeUltra
| ParserStrategy::BinaryTreeUltra2 => {
let has_source_overrides = params.dictionary_attaches;
if plan.opt_prefix_len != Some(prefix_chain.len()) {
plan.opt_source_bt = None;
plan.opt_dict_bt = None;
plan.opt_prefix_len = Some(prefix_chain.len());
}
let mut source_bt = plan.opt_source_bt.take().unwrap_or_else(|| {
let mut bt =
BinaryTreeFinder::new(params.hash_bits, params.chain_log, params.min_match);
bt.zero_tables();
if !has_source_overrides {
let dict_search_depth = params.search_depth.max(64);
bt.insert_prefix_into_unified(
prefix_chain,
dict_search_depth,
params.window_log,
);
}
bt
});
if plan.opt_dict_bt.is_none() {
let mut bt = BinaryTreeFinder::new(
params.dictionary_hash_bits(),
params.dictionary_chain_log(),
params.min_match,
)
.with_window_log(params.dictionary_window_log());
bt.zero_tables();
let dms_search_depth = params.search_depth.max(64);
bt.insert_prefix_into_unified(
prefix_chain,
dms_search_depth,
params.dictionary_window_log(),
);
plan.opt_dict_bt = Some(Arc::new(bt));
}
let dict_bt = plan.opt_dict_bt.as_ref().unwrap().clone();
let result = if matches!(
params.parser_strategy,
ParserStrategy::BinaryTreeUltra | ParserStrategy::BinaryTreeUltra2
) {
plan_sequences_optimal_with_prefix_two_phase_into::<true>(
plan,
src,
block_start,
prefix_chain,
repeat_offsets,
params,
match_floor,
&mut source_bt,
&dict_bt,
ldm,
)
} else {
plan_sequences_optimal_with_prefix_two_phase_into::<false>(
plan,
src,
block_start,
prefix_chain,
repeat_offsets,
params,
match_floor,
&mut source_bt,
&dict_bt,
ldm,
)
};
plan.opt_source_bt = Some(source_bt);
result
}
_ => {
debug_assert!(
ldm.is_none(),
"only the optimal parsers price long-distance matches"
);
plan_sequences_with_prefix_chain_from_into(
plan,
src,
block_start,
prefix_chain,
repeat_offsets,
params,
match_floor,
prefix_finder,
src_finder,
mode,
)
}
}
}
impl<const IS_ULTRA: bool> OptimalPriceModel<IS_ULTRA> {
pub(crate) fn new(
src: &[u8],
dict_seed: Option<&DictionaryPriceSeed>,
long_offset_penalty: bool,
compressed_literals: bool,
) -> Self {
if let Some(seed) = dict_seed {
let mut model = Self {
price_type: OptimalPriceType::Dynamic,
ll_freq: seed.ll_freq,
ml_freq: seed.ml_freq,
of_freq: seed.of_freq,
ll_sum: seed.ll_sum,
ml_sum: seed.ml_sum,
of_sum: seed.of_sum,
lit_freq: if compressed_literals {
seed.lit_freq
} else {
[0; 256]
},
lit_sum: if compressed_literals { seed.lit_sum } else { 0 },
ll_sum_base_price: 0,
ml_sum_base_price: 0,
of_sum_base_price: 0,
lit_sum_base_price: 0,
ml_price_by_code: [0; 53],
long_offset_penalty,
compressed_literals,
};
model.set_base_prices();
return model;
}
let mut model = Self {
price_type: if src.len() <= OPT_PREDEFINED_THRESHOLD {
OptimalPriceType::Predefined
} else {
OptimalPriceType::Dynamic
},
ll_freq: optimal_base_ll_frequencies(),
ml_freq: [1; 53],
of_freq: optimal_base_of_frequencies(),
ll_sum: 0,
ml_sum: 53,
of_sum: 0,
lit_freq: [0; 256],
lit_sum: 0,
ll_sum_base_price: 0,
ml_sum_base_price: 0,
of_sum_base_price: 0,
lit_sum_base_price: 0,
ml_price_by_code: [0; 53],
long_offset_penalty,
compressed_literals,
};
model.ll_sum = model.ll_freq.iter().sum();
model.of_sum = model.of_freq.iter().sum();
if model.compressed_literals {
for &byte in src {
model.lit_freq[byte as usize] += 1;
}
for freq in &mut model.lit_freq {
if *freq != 0 {
*freq = 1 + (*freq >> 8);
model.lit_sum += *freq;
}
}
}
model.set_base_prices();
model
}
#[inline(always)]
fn weight(&self, stat: u32) -> u32 {
if IS_ULTRA {
optimal_fractional_weight(stat)
} else {
optimal_bit_weight(stat)
}
}
pub(crate) fn set_base_prices(&mut self) {
self.ll_sum_base_price = self.weight(self.ll_sum);
self.ml_sum_base_price = self.weight(self.ml_sum);
self.of_sum_base_price = self.weight(self.of_sum);
if self.compressed_literals {
self.lit_sum_base_price = self.weight(self.lit_sum);
}
if !matches!(self.price_type, OptimalPriceType::Predefined) {
for code in 0..self.ml_price_by_code.len() {
self.ml_price_by_code[code] = ml_bits(code as u8) * OPT_PRICE_UNIT
+ self.ml_sum_base_price
- self.weight(self.ml_freq[code]);
}
}
}
fn from_persisted_state(
state: &OptimalPriceState,
long_offset_penalty: bool,
compressed_literals: bool,
) -> Self {
let mut model = Self {
price_type: OptimalPriceType::Dynamic,
ll_freq: state.ll_freq,
ml_freq: state.ml_freq,
of_freq: state.of_freq,
ll_sum: state.ll_sum,
ml_sum: state.ml_sum,
of_sum: state.of_sum,
lit_freq: state.lit_freq,
lit_sum: state.lit_sum,
ll_sum_base_price: 0,
ml_sum_base_price: 0,
of_sum_base_price: 0,
lit_sum_base_price: 0,
ml_price_by_code: [0; 53],
long_offset_penalty,
compressed_literals,
};
model.set_base_prices();
model
}
fn to_persisted_state(&self) -> OptimalPriceState {
OptimalPriceState {
lit_freq: self.lit_freq,
lit_sum: self.lit_sum,
ll_freq: self.ll_freq,
ll_sum: self.ll_sum,
ml_freq: self.ml_freq,
ml_sum: self.ml_sum,
of_freq: self.of_freq,
of_sum: self.of_sum,
}
}
#[inline(always)]
pub(crate) fn literal_byte_price(&self, byte: u8) -> u32 {
if !self.compressed_literals {
return 8 * OPT_PRICE_UNIT;
}
match self.price_type {
OptimalPriceType::Predefined => 6 * OPT_PRICE_UNIT,
OptimalPriceType::Dynamic => {
debug_assert!(
self.lit_sum_base_price >= OPT_PRICE_UNIT,
"dynamic literal pricing with lit_sum={} gives a {}-unit base",
self.lit_sum,
self.lit_sum_base_price,
);
let discount = self
.weight(self.lit_freq[byte as usize])
.min(self.lit_sum_base_price - OPT_PRICE_UNIT);
self.lit_sum_base_price - discount
}
}
}
#[inline(always)]
pub(crate) fn ll_price(&self, literal_length: u32) -> u32 {
if matches!(self.price_type, OptimalPriceType::Predefined) {
return self.weight(literal_length);
}
let ll_code = literal_length_code_unchecked(literal_length) as usize;
ll_bits(ll_code as u8) * OPT_PRICE_UNIT + self.ll_sum_base_price
- self.weight(self.ll_freq[ll_code])
}
#[inline(always)]
pub(crate) fn offset_price(&self, offset_value: u32) -> u32 {
let off_code = offset_code_unchecked(offset_value) as usize;
if matches!(self.price_type, OptimalPriceType::Predefined) {
return (16 + off_code as u32) * OPT_PRICE_UNIT;
}
let mut price = off_code as u32 * OPT_PRICE_UNIT + self.of_sum_base_price
- self.weight(self.of_freq[off_code]);
if self.long_offset_penalty && off_code >= 20 {
price += (off_code as u32 - 19) * 2 * OPT_PRICE_UNIT;
}
price + OPT_PRICE_UNIT / 5
}
#[inline(always)]
pub(crate) fn match_length_price(&self, match_length: u32) -> u32 {
if matches!(self.price_type, OptimalPriceType::Predefined) {
return self.weight(match_length.wrapping_sub(OPT_REPCODE_MIN_MATCH as u32));
}
let ml_code = match_length_code_unchecked(match_length) as usize;
debug_assert_eq!(
self.ml_price_by_code[ml_code],
ml_bits(ml_code as u8) * OPT_PRICE_UNIT + self.ml_sum_base_price
- self.weight(self.ml_freq[ml_code])
);
self.ml_price_by_code[ml_code]
}
pub(crate) fn update_stats(
&mut self,
literals: &[u8],
literal_length: u32,
offset_value: u32,
match_length: u32,
) -> Result<()> {
if self.compressed_literals {
for &byte in literals {
self.lit_freq[byte as usize] += OPT_LITERAL_FREQ_ADD;
self.lit_sum += OPT_LITERAL_FREQ_ADD;
}
}
let ll_code = literal_length_code_unchecked(literal_length) as usize;
let ml_code = match_length_code_unchecked(match_length) as usize;
let of_code = offset_code_unchecked(offset_value) as usize;
self.ll_freq[ll_code] += 1;
self.ll_sum += 1;
self.ml_freq[ml_code] += 1;
self.ml_sum += 1;
self.of_freq[of_code] += 1;
self.of_sum += 1;
self.set_base_prices();
Ok(())
}
}
pub(crate) fn optimal_base_ll_frequencies() -> [u32; 36] {
[
4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1,
]
}
pub(crate) fn optimal_base_of_frequencies() -> [u32; 32] {
[
6, 2, 1, 1, 2, 3, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1,
]
}
pub(crate) fn optimal_bit_weight(stat: u32) -> u32 {
highbit32(stat.saturating_add(1)) * OPT_PRICE_UNIT
}
pub(crate) fn optimal_fractional_weight(raw_stat: u32) -> u32 {
let stat = raw_stat.saturating_add(1);
let high_bit = highbit32(stat);
let base = high_bit * OPT_PRICE_UNIT;
let fraction = (stat << OPT_PRICE_ACCURACY_LOG) >> high_bit;
base + fraction
}
#[inline(always)]
pub(crate) fn push_optimal_candidate(
candidates: &mut Vec<OptimalMatchCandidate>,
raw_offset: usize,
length: usize,
current_reps: [u32; 3],
literal_length: usize,
) {
if raw_offset == 0 || length < OPT_REPCODE_MIN_MATCH {
return;
}
let repeat_offsets = RepeatOffsets::from_values(current_reps);
let offset_value = repeat_offsets.classify_offset(
raw_offset.min(u32::MAX as usize) as u32,
literal_length.min(u32::MAX as usize) as u32,
);
candidates.push(OptimalMatchCandidate {
offset_value,
length: length as u32,
});
}
pub(crate) fn collect_optimal_matches_without_prefix(
candidates: &mut Vec<OptimalMatchCandidate>,
tree_matches: &mut Vec<MatchCandidate>,
src: &[u8],
pos: usize,
current_reps: [u32; 3],
literal_length: usize,
params: MatchFinderParameters,
finder: &mut BinaryTreeFinder,
window_low: usize,
hash3: Option<&mut Hash3Table>,
sufficient_len: u32,
) -> usize {
match params.min_match {
3 => collect_optimal_matches_without_prefix_inner::<3>(
candidates,
tree_matches,
src,
pos,
current_reps,
literal_length,
params,
finder,
window_low,
hash3,
sufficient_len,
),
5 => collect_optimal_matches_without_prefix_inner::<5>(
candidates,
tree_matches,
src,
pos,
current_reps,
literal_length,
params,
finder,
window_low,
hash3,
sufficient_len,
),
6 => collect_optimal_matches_without_prefix_inner::<6>(
candidates,
tree_matches,
src,
pos,
current_reps,
literal_length,
params,
finder,
window_low,
hash3,
sufficient_len,
),
_ => collect_optimal_matches_without_prefix_inner::<4>(
candidates,
tree_matches,
src,
pos,
current_reps,
literal_length,
params,
finder,
window_low,
hash3,
sufficient_len,
),
}
}
#[inline(always)]
fn collect_optimal_matches_without_prefix_inner<const MLS: u32>(
candidates: &mut Vec<OptimalMatchCandidate>,
tree_matches: &mut Vec<MatchCandidate>,
src: &[u8],
pos: usize,
current_reps: [u32; 3],
literal_length: usize,
params: MatchFinderParameters,
finder: &mut BinaryTreeFinder,
window_low: usize,
hash3: Option<&mut Hash3Table>,
sufficient_len: u32,
) -> usize {
candidates.clear();
let [rep1, rep2, rep3] = current_reps;
const fn effective_min(mls: u32) -> usize {
if mls == 3 { 3 } else { 4 }
}
let mut best_length = effective_min(MLS).saturating_sub(1);
let rep_offsets: [Option<u32>; 3] = if literal_length == 0 {
[Some(rep2), Some(rep3), Some(rep1.saturating_sub(1))]
} else {
[Some(rep1), Some(rep2), Some(rep3)]
};
for raw_offset in rep_offsets.into_iter().flatten() {
let raw_offset = raw_offset as usize;
if raw_offset == 0 || raw_offset > pos {
continue;
}
let match_start = pos - raw_offset;
if match_start < window_low {
continue;
}
#[allow(unsafe_code)]
unsafe {
let base = src.as_ptr();
let l = core::ptr::read_unaligned(base.add(match_start) as *const u32);
let r = core::ptr::read_unaligned(base.add(pos) as *const u32);
if MLS == 3 {
if cfg!(target_endian = "little") {
if (l ^ r) & 0x00FF_FFFF != 0 {
continue;
}
} else if (l ^ r) & 0xFFFF_FF00 != 0 {
continue;
}
} else if l != r {
continue;
}
}
let length = count_match_length_from(src, match_start, pos, effective_min(MLS));
if length > best_length {
push_optimal_candidate(candidates, raw_offset, length, current_reps, literal_length);
best_length = length;
if length > sufficient_len as usize || pos + length >= src.len() {
return pos;
}
}
}
if MLS == 3 {
if let Some(hash3) = hash3 {
if best_length < 3 {
let match_index = hash3.insert_and_find(src, pos) as usize;
let match_low = window_low;
if match_index < pos
&& match_index >= match_low
&& pos - match_index < HASH3_MAX_DISTANCE
{
let length = count_match_length(src, match_index, pos);
if length >= 3 {
let raw_offset = pos - match_index;
push_optimal_candidate(
candidates,
raw_offset,
length,
current_reps,
literal_length,
);
best_length = length;
if length > sufficient_len as usize || pos + length >= src.len() {
return pos + 1;
}
}
}
}
}
}
let (next_to_update, _remaining) = finder.insert_and_collect_matches(
tree_matches,
src,
pos,
params.search_depth,
window_low,
best_length + 1,
);
for candidate in tree_matches.iter().copied() {
push_optimal_candidate(
candidates,
candidate.offset,
candidate.length,
current_reps,
literal_length,
);
best_length = best_length.max(candidate.length);
}
next_to_update
}
#[allow(dead_code)]
pub(crate) fn collect_optimal_matches_with_prefix(
candidates: &mut Vec<OptimalMatchCandidate>,
tree_matches: &mut Vec<MatchCandidate>,
prefix_chain: PrefixChain<'_>,
src: &[u8],
pos: usize,
current_reps: [u32; 3],
literal_length: usize,
params: MatchFinderParameters,
prefix_low: usize,
source_low: usize,
prefix_finder: &BinaryTreeFinder,
src_finder: &mut BinaryTreeFinder,
hash3: Option<&mut Hash3Table>,
sufficient_len: u32,
) -> usize {
match params.min_match {
3 => collect_optimal_matches_with_prefix_inner::<3>(
candidates,
tree_matches,
prefix_chain,
src,
pos,
current_reps,
literal_length,
params,
prefix_low,
source_low,
prefix_finder,
src_finder,
hash3,
sufficient_len,
),
5 => collect_optimal_matches_with_prefix_inner::<5>(
candidates,
tree_matches,
prefix_chain,
src,
pos,
current_reps,
literal_length,
params,
prefix_low,
source_low,
prefix_finder,
src_finder,
hash3,
sufficient_len,
),
6 => collect_optimal_matches_with_prefix_inner::<6>(
candidates,
tree_matches,
prefix_chain,
src,
pos,
current_reps,
literal_length,
params,
prefix_low,
source_low,
prefix_finder,
src_finder,
hash3,
sufficient_len,
),
_ => collect_optimal_matches_with_prefix_inner::<4>(
candidates,
tree_matches,
prefix_chain,
src,
pos,
current_reps,
literal_length,
params,
prefix_low,
source_low,
prefix_finder,
src_finder,
hash3,
sufficient_len,
),
}
}
#[inline(always)]
fn collect_optimal_matches_with_prefix_inner<const MLS: u32>(
candidates: &mut Vec<OptimalMatchCandidate>,
tree_matches: &mut Vec<MatchCandidate>,
prefix_chain: PrefixChain<'_>,
src: &[u8],
pos: usize,
current_reps: [u32; 3],
literal_length: usize,
params: MatchFinderParameters,
prefix_low: usize,
source_low: usize,
prefix_finder: &BinaryTreeFinder,
src_finder: &mut BinaryTreeFinder,
hash3: Option<&mut Hash3Table>,
sufficient_len: u32,
) -> usize {
candidates.clear();
let [rep1, rep2, rep3] = current_reps;
let current = prefix_chain.len() + pos;
const fn effective_min(mls: u32) -> usize {
if mls == 3 { 3 } else { 4 }
}
let mut best_length = effective_min(MLS).saturating_sub(1);
let rep_offsets: [Option<u32>; 3] = if literal_length == 0 {
[Some(rep2), Some(rep3), Some(rep1.saturating_sub(1))]
} else {
[Some(rep1), Some(rep2), Some(rep3)]
};
for raw_offset in rep_offsets.into_iter().flatten() {
let raw_offset = raw_offset as usize;
if raw_offset == 0 || raw_offset > current {
continue;
}
let match_start = current - raw_offset;
if !logical_match_start_is_valid(prefix_chain.len(), match_start, prefix_low, source_low) {
continue;
}
let length = count_match_length_virtual(prefix_chain, src, match_start, current);
if length > best_length {
push_optimal_candidate(candidates, raw_offset, length, current_reps, literal_length);
best_length = length;
if length > sufficient_len as usize || pos + length >= src.len() {
return pos;
}
}
}
if MLS == 3 {
if let Some(hash3) = hash3 {
if best_length < 3 {
let match_index = hash3.insert_and_find(src, pos) as usize;
let match_low = source_low;
if match_index < pos
&& match_index >= match_low
&& pos - match_index < HASH3_MAX_DISTANCE
{
let length = count_match_length(src, match_index, pos);
if length >= 3 {
let raw_offset = pos - match_index;
push_optimal_candidate(
candidates,
raw_offset,
length,
current_reps,
literal_length,
);
best_length = length;
if length > sufficient_len as usize || pos + length >= src.len() {
return pos + 1;
}
}
}
}
}
}
let tree_min = regular_match_length_threshold(literal_length, params);
if best_length < tree_min.saturating_sub(1) {
best_length = tree_min.saturating_sub(1);
}
prefix_finder.collect_prefix_chain_matches(
tree_matches,
prefix_chain,
src,
pos,
params.dictionary_search_depth,
prefix_low,
best_length + 1,
);
for candidate in tree_matches.iter().copied() {
push_optimal_candidate(
candidates,
candidate.offset,
candidate.length,
current_reps,
literal_length,
);
best_length = best_length.max(candidate.length);
}
let (next_to_update, _remaining) = src_finder.insert_and_collect_matches(
tree_matches,
src,
pos,
params.search_depth,
source_low,
best_length + 1,
);
for candidate in tree_matches.iter().copied() {
push_optimal_candidate(
candidates,
candidate.offset,
candidate.length,
current_reps,
literal_length,
);
best_length = best_length.max(candidate.length);
}
next_to_update
}
pub(crate) fn collect_optimal_matches_two_phase(
candidates: &mut Vec<OptimalMatchCandidate>,
tree_matches: &mut Vec<MatchCandidate>,
dict_matches: &mut Vec<MatchCandidate>,
virtual_buf: &[u8],
prefix_len: usize,
pos: usize,
current_reps: [u32; 3],
literal_length: usize,
params: MatchFinderParameters,
prefix_low: usize,
source_low: usize,
source_finder: &mut BinaryTreeFinder,
dict_finder: &BinaryTreeFinder,
hash3: Option<&mut Hash3Table>,
ext_dict_mode: bool,
sufficient_len: u32,
) {
match params.min_match {
3 => collect_optimal_matches_two_phase_inner::<3>(
candidates,
tree_matches,
dict_matches,
virtual_buf,
prefix_len,
pos,
current_reps,
literal_length,
params,
prefix_low,
source_low,
source_finder,
dict_finder,
hash3,
ext_dict_mode,
sufficient_len,
),
5 => collect_optimal_matches_two_phase_inner::<5>(
candidates,
tree_matches,
dict_matches,
virtual_buf,
prefix_len,
pos,
current_reps,
literal_length,
params,
prefix_low,
source_low,
source_finder,
dict_finder,
hash3,
ext_dict_mode,
sufficient_len,
),
6 => collect_optimal_matches_two_phase_inner::<6>(
candidates,
tree_matches,
dict_matches,
virtual_buf,
prefix_len,
pos,
current_reps,
literal_length,
params,
prefix_low,
source_low,
source_finder,
dict_finder,
hash3,
ext_dict_mode,
sufficient_len,
),
_ => collect_optimal_matches_two_phase_inner::<4>(
candidates,
tree_matches,
dict_matches,
virtual_buf,
prefix_len,
pos,
current_reps,
literal_length,
params,
prefix_low,
source_low,
source_finder,
dict_finder,
hash3,
ext_dict_mode,
sufficient_len,
),
}
}
#[inline(always)]
fn collect_optimal_matches_two_phase_inner<const MLS: u32>(
candidates: &mut Vec<OptimalMatchCandidate>,
tree_matches: &mut Vec<MatchCandidate>,
dict_matches: &mut Vec<MatchCandidate>,
virtual_buf: &[u8],
prefix_len: usize,
pos: usize,
current_reps: [u32; 3],
literal_length: usize,
params: MatchFinderParameters,
prefix_low: usize,
source_low: usize,
source_finder: &mut BinaryTreeFinder,
dict_finder: &BinaryTreeFinder,
hash3: Option<&mut Hash3Table>,
ext_dict_mode: bool,
sufficient_len: u32,
) {
candidates.clear();
let src = &virtual_buf[prefix_len..];
let [rep1, rep2, rep3] = current_reps;
let current = prefix_len + pos;
const fn effective_min(mls: u32) -> usize {
if mls == 3 { 3 } else { 4 }
}
let mut best_length = effective_min(MLS).saturating_sub(1);
let sufficient_len = sufficient_len as usize;
let bst_prefix_len = if ext_dict_mode { prefix_len } else { 0 };
let rep_offsets: [Option<u32>; 3] = if literal_length == 0 {
[Some(rep2), Some(rep3), Some(rep1.saturating_sub(1))]
} else {
[Some(rep1), Some(rep2), Some(rep3)]
};
for raw_offset in rep_offsets.into_iter().flatten() {
let raw_offset = raw_offset as usize;
if raw_offset == 0 || raw_offset > current {
continue;
}
let match_start = current - raw_offset;
if !logical_match_start_is_valid(prefix_len, match_start, prefix_low, source_low) {
continue;
}
if match_start < prefix_len && prefix_len.wrapping_sub(1).wrapping_sub(match_start) < 3 {
continue;
}
#[allow(unsafe_code)]
unsafe {
let base = virtual_buf.as_ptr();
let l = core::ptr::read_unaligned(base.add(match_start) as *const u32);
let r = core::ptr::read_unaligned(base.add(current) as *const u32);
if MLS == 3 {
if cfg!(target_endian = "little") {
if (l ^ r) & 0x00FF_FFFF != 0 {
continue;
}
} else if (l ^ r) & 0xFFFF_FF00 != 0 {
continue;
}
} else if l != r {
continue;
}
}
let length = count_match_length_from(virtual_buf, match_start, current, effective_min(MLS));
if length > best_length {
push_optimal_candidate(candidates, raw_offset, length, current_reps, literal_length);
best_length = length;
if best_length > sufficient_len || pos + best_length >= src.len() {
return;
}
}
}
if MLS == 3 {
if let Some(hash3) = hash3 {
if best_length < 3 {
let match_index = hash3.insert_and_find(src, pos) as usize;
let match_low = source_low;
if match_index < pos
&& match_index >= match_low
&& pos - match_index < HASH3_MAX_DISTANCE
{
let length = count_match_length(src, match_index, pos);
if length >= 3 {
let raw_offset = pos - match_index;
push_optimal_candidate(
candidates,
raw_offset,
length,
current_reps,
literal_length,
);
best_length = length;
if best_length > sufficient_len || pos + best_length >= src.len() {
source_finder.next_to_update = pos + 1;
return;
}
}
}
}
}
}
let prev_match_index = source_finder.pre_insert_hash_unified(src, bst_prefix_len, pos);
if ext_dict_mode {
let (_ntu, _remaining_compares) = source_finder.insert_and_collect_matches_unified(
tree_matches,
virtual_buf,
bst_prefix_len,
pos,
params.search_depth,
prefix_low,
source_low,
best_length + 1,
prev_match_index,
);
for candidate in tree_matches.iter().copied() {
push_optimal_candidate(
candidates,
candidate.offset,
candidate.length,
current_reps,
literal_length,
);
best_length = best_length.max(candidate.length);
}
} else {
let (_ntu, _remaining_compares) = source_finder.insert_and_collect_matches_unified(
tree_matches,
src,
0, pos,
params.search_depth,
0, source_low,
best_length + 1,
prev_match_index,
);
for candidate in tree_matches.iter().copied() {
push_optimal_candidate(
candidates,
candidate.offset,
candidate.length,
current_reps,
literal_length,
);
best_length = best_length.max(candidate.length);
}
if prefix_len > 0 {
const DICT_POS_BIAS: usize = 2;
let dms_high_limit = prefix_len + DICT_POS_BIAS;
let dms_low_limit = prefix_low + DICT_POS_BIAS;
let dms_bt_low = if dict_finder.bt_mask >= dms_high_limit - dms_low_limit {
dms_low_limit
} else {
dms_high_limit - dict_finder.bt_mask
};
BinaryTreeFinder::search_dict_bst(
dict_finder,
dict_matches,
virtual_buf,
prefix_len,
pos,
params.search_depth,
dms_low_limit,
dms_bt_low,
best_length,
);
for candidate in dict_matches.iter().copied() {
push_optimal_candidate(
candidates,
candidate.offset,
candidate.length,
current_reps,
literal_length,
);
best_length = best_length.max(candidate.length);
let mi = (prefix_len + pos) - candidate.offset;
let match_end_virtual = mi + candidate.length;
if match_end_virtual >= prefix_len {
let match_end_src = match_end_virtual - prefix_len;
let ntu_candidate = match_end_src.saturating_sub(8).max(pos + 1);
if ntu_candidate > source_finder.next_to_update {
source_finder.next_to_update = ntu_candidate;
}
}
}
}
}
}
#[allow(dead_code)]
fn collect_optimal_rep_and_prefix_matches(
candidates: &mut Vec<OptimalMatchCandidate>,
tree_matches: &mut Vec<MatchCandidate>,
prefix_chain: PrefixChain<'_>,
src: &[u8],
pos: usize,
current_reps: [u32; 3],
literal_length: usize,
params: MatchFinderParameters,
prefix_low: usize,
source_low: usize,
prefix_finder: &BinaryTreeFinder,
src_finder: &BinaryTreeFinder,
) {
candidates.clear();
let [rep1, rep2, rep3] = current_reps;
let current = prefix_chain.len() + pos;
let mut best_length = OPT_REPCODE_MIN_MATCH.saturating_sub(1);
let rep_offsets: [Option<u32>; 3] = if literal_length == 0 {
[Some(rep2), Some(rep3), Some(rep1.saturating_sub(1))]
} else {
[Some(rep1), Some(rep2), Some(rep3)]
};
for raw_offset in rep_offsets.into_iter().flatten() {
let raw_offset = raw_offset as usize;
if raw_offset == 0 || raw_offset > current {
continue;
}
let match_start = current - raw_offset;
if !logical_match_start_is_valid(prefix_chain.len(), match_start, prefix_low, source_low) {
continue;
}
let length = count_match_length_virtual(prefix_chain, src, match_start, current);
if length > best_length {
push_optimal_candidate(candidates, raw_offset, length, current_reps, literal_length);
best_length = length;
}
}
prefix_finder.collect_prefix_chain_matches(
tree_matches,
prefix_chain,
src,
pos,
params.dictionary_search_depth,
prefix_low,
best_length + 1,
);
for candidate in tree_matches.iter().copied() {
push_optimal_candidate(
candidates,
candidate.offset,
candidate.length,
current_reps,
literal_length,
);
best_length = best_length.max(candidate.length);
}
src_finder.collect_matches(tree_matches, src, pos, params, literal_length, source_low);
for candidate in tree_matches.iter().copied() {
push_optimal_candidate(
candidates,
candidate.offset,
candidate.length,
current_reps,
literal_length,
);
}
}
#[inline(always)]
#[allow(unsafe_code)]
pub(crate) fn update_optimal_literal_node<const IS_ULTRA: bool>(
nodes: &mut [OptimalPathNode],
pos: usize,
byte: u8,
price_model: &OptimalPriceModel<IS_ULTRA>,
) -> Option<OptimalPathNode> {
debug_assert!(pos > 0 && pos < nodes.len());
let previous = unsafe { *nodes.get_unchecked(pos - 1) };
let new_litlen = previous.litlen + 1;
let price =
previous.price + price_model.literal_byte_price(byte) + price_model.ll_price(new_litlen)
- price_model.ll_price(previous.litlen);
let current = unsafe { nodes.get_unchecked(pos) };
if price <= current.price {
let prev_node = *current;
unsafe {
*nodes.get_unchecked_mut(pos) = OptimalPathNode {
price,
off: 0,
mlen: 0,
litlen: new_litlen,
reps: previous.reps,
};
}
if prev_node.litlen == 0 && prev_node.price < MAX_PRICE {
return Some(prev_node);
}
}
None
}
#[inline(always)]
#[allow(unsafe_code)]
pub(crate) fn init_optimal_match_nodes<const IS_ULTRA: bool>(
nodes: &mut [OptimalPathNode],
candidates: &[OptimalMatchCandidate],
price_model: &OptimalPriceModel<IS_ULTRA>,
horizon: usize,
min_match: usize,
) -> usize {
debug_assert!(horizon < nodes.len());
let current = unsafe { *nodes.get_unchecked(0) };
if current.price >= MAX_PRICE {
return 0;
}
for p in 1..min_match {
if p > horizon {
break;
}
unsafe {
let node = nodes.get_unchecked_mut(p);
node.price = MAX_PRICE;
node.mlen = 0;
node.litlen = current.litlen + p as u32;
}
}
let base_price = current.price + price_model.ll_price(0);
let max_reach = horizon as u32;
let mut pos = min_match as u32;
for candidate in candidates {
let end = candidate.length.min(max_reach);
if pos > end {
continue;
}
let candidate_price = base_price + price_model.offset_price(candidate.offset_value);
while pos <= end {
let idx = pos as usize;
debug_assert!(idx <= horizon && idx < nodes.len());
let price = candidate_price + price_model.match_length_price(pos);
unsafe {
let node = nodes.get_unchecked_mut(idx);
node.price = price;
node.off = candidate.offset_value;
node.mlen = pos;
node.litlen = 0;
}
pos += 1;
}
}
let last_pos = pos.saturating_sub(1) as usize;
if pos as usize <= horizon {
unsafe {
nodes.get_unchecked_mut(pos as usize).price = MAX_PRICE;
}
}
last_pos
}
#[inline(always)]
#[allow(unsafe_code)]
pub(crate) fn update_optimal_match_nodes<const IS_ULTRA: bool>(
nodes: &mut [OptimalPathNode],
cur: usize,
last_pos: &mut usize,
candidates: &[OptimalMatchCandidate],
price_model: &OptimalPriceModel<IS_ULTRA>,
horizon: usize,
min_match: usize,
) {
debug_assert!(cur <= horizon && horizon < nodes.len());
let current = unsafe { *nodes.get_unchecked(cur) };
if current.price >= MAX_PRICE {
return;
}
let base_price = current.price + price_model.ll_price(0);
let max_reach = (horizon - cur) as u32;
let mut previous_length = min_match as u32 - 1;
for candidate in candidates {
let max_length = candidate.length.min(max_reach);
if max_length <= previous_length {
continue;
}
let start_ml = previous_length + 1;
let mut ml = max_length;
let candidate_price = base_price + price_model.offset_price(candidate.offset_value);
while ml >= start_ml {
let pos = cur + ml as usize;
debug_assert!(pos <= horizon && pos < nodes.len());
let price = candidate_price + price_model.match_length_price(ml);
let beyond = pos > *last_pos;
if beyond || price < unsafe { nodes.get_unchecked(pos) }.price {
while *last_pos < pos {
*last_pos += 1;
unsafe {
let gap = nodes.get_unchecked_mut(*last_pos);
gap.price = MAX_PRICE;
gap.litlen = u32::MAX; }
}
unsafe {
let node = nodes.get_unchecked_mut(pos);
node.price = price;
node.off = candidate.offset_value;
node.mlen = ml;
node.litlen = 0;
}
} else if !IS_ULTRA {
break; }
ml -= 1;
}
previous_length = max_length;
if previous_length == max_reach {
break;
}
}
}
pub(crate) fn backtrace_optimal_path(
nodes: &[OptimalPathNode],
last_pos: usize,
sequences: &mut Vec<(u32, u32, u32)>,
) -> u32 {
sequences.clear();
let tail_literals = nodes[last_pos].litlen;
let mut pos = last_pos;
while pos > 0 && nodes[pos].mlen == 0 {
pos -= 1;
}
while pos > 0 {
let node = nodes[pos];
if node.mlen == 0 {
break;
}
let prev = pos - node.mlen as usize - node.litlen as usize;
sequences.push((nodes[prev].litlen, node.off, node.mlen));
pos = prev;
while pos > 0 && nodes[pos].mlen == 0 {
pos -= 1;
}
}
sequences.reverse();
tail_literals
}
pub(crate) fn emit_optimal_sequence<const IS_ULTRA: bool>(
plan: &mut SequencePlan,
src: &[u8],
anchor: &mut usize,
repeat_offsets: &mut RepeatOffsets,
price_model: &mut OptimalPriceModel<IS_ULTRA>,
literal_length: u32,
offset_value: u32,
match_length: u32,
) -> Result<()> {
let literals_end = *anchor + literal_length as usize;
let literals = &src[*anchor..literals_end];
plan.literals.extend_from_slice(literals);
let command = SequenceCommand {
literal_length,
offset_value,
match_length,
};
plan.sequences.push(command);
price_model.update_stats(literals, literal_length, offset_value, match_length)?;
repeat_offsets.resolve(&command)?;
*anchor = literals_end + match_length as usize;
Ok(())
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn plan_sequences_optimal_without_prefix_into<const IS_ULTRA: bool>(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
match_floor: MatchFloor,
finder: &mut BinaryTreeFinder,
ldm: Option<&[RawSequence]>,
) -> Result<()> {
let block_len = src.len().saturating_sub(block_start);
plan.reset_for_block(block_len);
if block_len < MIN_MATCH {
plan.literals.extend_from_slice(&src[block_start..]);
plan.repeat_offsets = repeat_offsets;
return Ok(());
}
let mut price_model = if let Some(mut persisted) = plan.opt_price_state.take() {
persisted.rescale();
OptimalPriceModel::<IS_ULTRA>::from_persisted_state(
&persisted,
params.long_offset_penalty,
params.compressed_literals,
)
} else {
OptimalPriceModel::<IS_ULTRA>::new(
&src[block_start..],
None,
params.long_offset_penalty,
params.compressed_literals,
)
};
let mut repeat_offsets = repeat_offsets;
let mut anchor = block_start;
let mut ip = block_start;
let limit = src.len().saturating_sub(8);
let mut inserted_until = finder.next_to_update.min(block_start);
let mut nodes = core::mem::take(&mut plan.opt_nodes);
nodes.clear();
nodes.resize(OPT_NUM + 1, OptimalPathNode::UNSET);
let mut tree_matches = core::mem::take(&mut plan.opt_tree_matches);
let mut candidates = core::mem::take(&mut plan.opt_candidates);
let mut backtrace_buf = core::mem::take(&mut plan.opt_backtrace);
let mut hash3 = if params.min_match == 3 {
let mut h3 = plan
.opt_hash3
.take()
.unwrap_or_else(|| Hash3Table::new(params.window_log));
h3.next_to_update = finder.next_to_update;
Some(h3)
} else {
None
};
let sufficient_len = params.target_length.min(OPT_NUM - 1) as u32;
let min_match: usize = if params.min_match == 3 { 3 } else { 4 };
let mut ldm_candidates = ldm.map(|sequences| LdmCandidates::new(sequences, block_len as u32));
while ip < limit {
if inserted_until > ip {
candidates.clear();
} else {
if inserted_until < ip {
finder.insert_range(src, inserted_until, ip, params.search_depth);
}
inserted_until = collect_optimal_matches_without_prefix(
&mut candidates,
&mut tree_matches,
src,
ip,
repeat_offsets.values(),
ip - anchor,
params,
finder,
match_floor.at(ip),
hash3.as_mut(),
sufficient_len,
);
}
if let Some(ldm_candidates) = ldm_candidates.as_mut() {
ldm_candidates.offer(
&mut candidates,
(ip - block_start) as u32,
(src.len() - ip) as u32,
min_match as u32,
);
}
if candidates.is_empty() {
ip += 1;
continue;
}
let horizon = OPT_NUM.min(src.len() - ip);
let best = *candidates.last().expect("candidate list must be non-empty");
if best.length > sufficient_len {
let literal_length = (ip - anchor) as u32;
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
literal_length,
best.offset_value,
best.length,
)?;
ip = anchor;
continue;
}
let litlen0 = (ip - anchor) as u32;
nodes[0] = OptimalPathNode {
price: price_model.ll_price(litlen0),
off: 0,
mlen: 0,
litlen: litlen0,
reps: repeat_offsets.values(),
};
let mut last_pos = init_optimal_match_nodes(
&mut nodes[..=horizon],
&candidates,
&price_model,
horizon,
min_match,
);
let mut forced_last_stretch: Option<(u32, u32)> = None; let mut forced_last_cur = 0usize;
let mut cur = 1usize;
while cur <= last_pos {
let replaced_match = update_optimal_literal_node::<IS_ULTRA>(
&mut nodes[..=horizon],
cur,
src[ip + cur - 1],
&price_model,
);
if nodes[cur].litlen == 0 {
let prev = cur - nodes[cur].mlen as usize;
let mut reps = RepeatOffsets::from_values(nodes[prev].reps);
let _ = reps.resolve_values(nodes[prev].litlen, nodes[cur].off);
nodes[cur].reps = reps.values();
}
let inr = ip + cur;
if IS_ULTRA {
if let Some(prev_match) = replaced_match {
let ll1_inc = price_model.ll_price(1) as i32 - price_model.ll_price(0) as i32;
if ll1_inc < 0 && cur + 1 <= horizon && inr < src.len() {
let with1literal = prev_match.price as i32
+ price_model.literal_byte_price(src[inr]) as i32
+ ll1_inc;
let new_litlen = nodes[cur].litlen + 1;
let with_more_literals = nodes[cur].price as i32
+ price_model.literal_byte_price(src[inr]) as i32
+ price_model.ll_price(new_litlen) as i32
- price_model.ll_price(nodes[cur].litlen) as i32;
if with1literal < with_more_literals
&& (with1literal as u32) < nodes[cur + 1].price
{
let prev = cur - prev_match.mlen as usize;
let mut rep_offsets = RepeatOffsets::from_values(nodes[prev].reps);
let _ = rep_offsets.resolve_values(nodes[prev].litlen, prev_match.off);
nodes[cur + 1] = OptimalPathNode {
price: with1literal as u32,
off: prev_match.off,
mlen: prev_match.mlen,
litlen: 1,
reps: rep_offsets.values(),
};
if last_pos < cur + 1 {
last_pos = cur + 1;
}
}
}
}
}
if inr > limit {
cur += 1;
continue;
}
if cur == last_pos {
break;
}
if !IS_ULTRA
&& cur + 1 <= horizon
&& nodes[cur + 1].price <= nodes[cur].price + OPT_PRICE_UNIT / 2
{
cur += 1;
continue;
}
if inserted_until > inr {
candidates.clear();
} else {
if inserted_until < inr {
finder.insert_range(src, inserted_until, inr, params.search_depth);
}
inserted_until = collect_optimal_matches_without_prefix(
&mut candidates,
&mut tree_matches,
src,
inr,
nodes[cur].reps,
nodes[cur].litlen as usize,
params,
finder,
match_floor.at(inr),
hash3.as_mut(),
sufficient_len,
);
}
if let Some(ldm_candidates) = ldm_candidates.as_mut() {
ldm_candidates.offer(
&mut candidates,
(inr - block_start) as u32,
(src.len() - inr) as u32,
min_match as u32,
);
}
{
if !candidates.is_empty() {
let best_candidate = candidates.last().expect("non-empty");
let uncapped_longest = best_candidate.length;
if uncapped_longest > sufficient_len
|| cur + uncapped_longest as usize >= horizon
|| inr + uncapped_longest as usize >= src.len()
{
forced_last_stretch = Some((best_candidate.offset_value, uncapped_longest));
forced_last_cur = cur;
break;
}
update_optimal_match_nodes::<IS_ULTRA>(
&mut nodes[..=horizon],
cur,
&mut last_pos,
&candidates,
&price_model,
horizon,
min_match,
);
}
}
cur += 1;
}
if last_pos + 1 <= horizon {
nodes[last_pos + 1].price = MAX_PRICE;
}
if let Some((off, mlen)) = forced_last_stretch {
let tail_literals = backtrace_optimal_path(
&nodes[..=forced_last_cur],
forced_last_cur,
&mut backtrace_buf,
);
for &(literal_length, offset_value, match_length) in &backtrace_buf {
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
literal_length,
offset_value,
match_length,
)?;
}
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
tail_literals,
off,
mlen,
)?;
ip = anchor;
continue;
}
let tail_literals =
backtrace_optimal_path(&nodes[..=last_pos], last_pos, &mut backtrace_buf);
if backtrace_buf.is_empty() {
ip = anchor + tail_literals as usize;
continue;
}
for &(literal_length, offset_value, match_length) in &backtrace_buf {
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
literal_length,
offset_value,
match_length,
)?;
}
ip = anchor;
}
plan.literals.extend_from_slice(&src[anchor..]);
plan.repeat_offsets = repeat_offsets;
plan.opt_price_state = Some(price_model.to_persisted_state());
finder.next_to_update = inserted_until;
plan.opt_nodes = nodes;
plan.opt_tree_matches = tree_matches;
plan.opt_candidates = candidates;
plan.opt_backtrace = backtrace_buf;
plan.opt_hash3 = hash3;
Ok(())
}
#[allow(dead_code)]
pub(crate) fn plan_sequences_optimal_with_prefix_into<const IS_ULTRA: bool>(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
prefix_chain: PrefixChain<'_>,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
prefix_low: usize,
source_low: usize,
prefix_finder: &BinaryTreeFinder,
src_finder: &mut BinaryTreeFinder,
) -> Result<()> {
let block_len = src.len().saturating_sub(block_start);
plan.reset_for_block(block_len);
if block_len < MIN_MATCH {
plan.literals.extend_from_slice(&src[block_start..]);
plan.repeat_offsets = repeat_offsets;
return Ok(());
}
let mut price_model = if let Some(mut persisted) = plan.opt_price_state.take() {
persisted.rescale();
OptimalPriceModel::<IS_ULTRA>::from_persisted_state(
&persisted,
params.long_offset_penalty,
params.compressed_literals,
)
} else {
let dict_seed = plan.opt_dict_price_seed.as_ref();
OptimalPriceModel::<IS_ULTRA>::new(
&src[block_start..],
dict_seed,
params.long_offset_penalty,
params.compressed_literals,
)
};
let mut repeat_offsets = repeat_offsets;
let mut anchor = block_start;
let mut ip = block_start;
let limit = src.len().saturating_sub(8);
let mut inserted_until = block_start;
let mut nodes = core::mem::take(&mut plan.opt_nodes);
nodes.clear();
nodes.resize(OPT_NUM + 1, OptimalPathNode::UNSET);
let mut tree_matches = core::mem::take(&mut plan.opt_tree_matches);
let mut candidates = core::mem::take(&mut plan.opt_candidates);
let mut backtrace_buf = core::mem::take(&mut plan.opt_backtrace);
let mut hash3 = if params.min_match == 3 {
let mut h3 = plan
.opt_hash3
.take()
.unwrap_or_else(|| Hash3Table::new(params.window_log));
h3.next_to_update = block_start;
Some(h3)
} else {
None
};
let sufficient_len = params.target_length.min(OPT_NUM - 1) as u32;
while ip < limit {
if inserted_until > ip {
ip += 1;
continue;
}
if inserted_until < ip {
src_finder.insert_range(src, inserted_until, ip, params.search_depth);
}
inserted_until = collect_optimal_matches_with_prefix(
&mut candidates,
&mut tree_matches,
prefix_chain,
src,
ip,
repeat_offsets.values(),
ip - anchor,
params,
prefix_low,
source_low,
prefix_finder,
src_finder,
hash3.as_mut(),
sufficient_len,
);
if candidates.is_empty() {
ip += 1;
continue;
}
let horizon = OPT_NUM.min(src.len() - ip);
let best = *candidates.last().expect("candidate list must be non-empty");
if best.length > sufficient_len {
let literal_length = (ip - anchor) as u32;
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
literal_length,
best.offset_value,
best.length,
)?;
ip = anchor;
continue;
}
let litlen0 = (ip - anchor) as u32;
nodes[0] = OptimalPathNode {
price: price_model.ll_price(litlen0),
off: 0,
mlen: 0,
litlen: litlen0,
reps: repeat_offsets.values(),
};
let min_match = if params.min_match == 3 { 3 } else { 4 };
let mut last_pos = init_optimal_match_nodes(
&mut nodes[..=horizon],
&candidates,
&price_model,
horizon,
min_match,
);
let mut forced_last_stretch: Option<(u32, u32)> = None;
let mut forced_last_cur = 0usize;
let mut cur = 1usize;
while cur <= last_pos {
let replaced_match = update_optimal_literal_node::<IS_ULTRA>(
&mut nodes[..=horizon],
cur,
src[ip + cur - 1],
&price_model,
);
if nodes[cur].litlen == 0 {
let prev = cur - nodes[cur].mlen as usize;
let mut reps = RepeatOffsets::from_values(nodes[prev].reps);
let _ = reps.resolve_values(nodes[prev].litlen, nodes[cur].off);
nodes[cur].reps = reps.values();
}
let inr = ip + cur;
if IS_ULTRA {
if let Some(prev_match) = replaced_match {
let ll1_inc = price_model.ll_price(1) as i32 - price_model.ll_price(0) as i32;
if ll1_inc < 0 && cur + 1 <= horizon && inr < src.len() {
let with1literal = prev_match.price as i32
+ price_model.literal_byte_price(src[inr]) as i32
+ ll1_inc;
let new_litlen = nodes[cur].litlen + 1;
let with_more_literals = nodes[cur].price as i32
+ price_model.literal_byte_price(src[inr]) as i32
+ price_model.ll_price(new_litlen) as i32
- price_model.ll_price(nodes[cur].litlen) as i32;
if with1literal < with_more_literals
&& (with1literal as u32) < nodes[cur + 1].price
{
let prev = cur - prev_match.mlen as usize;
let mut rep_offsets = RepeatOffsets::from_values(nodes[prev].reps);
let _ = rep_offsets.resolve_values(nodes[prev].litlen, prev_match.off);
nodes[cur + 1] = OptimalPathNode {
price: with1literal as u32,
off: prev_match.off,
mlen: prev_match.mlen,
litlen: 1,
reps: rep_offsets.values(),
};
if last_pos < cur + 1 {
last_pos = cur + 1;
}
}
}
}
}
if inr > limit {
cur += 1;
continue;
}
if cur == last_pos {
break;
}
if !IS_ULTRA
&& cur + 1 <= horizon
&& nodes[cur + 1].price <= nodes[cur].price + OPT_PRICE_UNIT / 2
{
cur += 1;
continue;
}
if inserted_until > inr {
cur += 1;
continue;
}
if inserted_until < inr {
src_finder.insert_range(src, inserted_until, inr, params.search_depth);
}
inserted_until = collect_optimal_matches_with_prefix(
&mut candidates,
&mut tree_matches,
prefix_chain,
src,
inr,
nodes[cur].reps,
nodes[cur].litlen as usize,
params,
prefix_low,
source_low,
prefix_finder,
src_finder,
hash3.as_mut(),
sufficient_len,
);
{
if !candidates.is_empty() {
let best_candidate = candidates.last().expect("non-empty");
let uncapped_longest = best_candidate.length;
if uncapped_longest > sufficient_len
|| cur + uncapped_longest as usize >= horizon
|| inr + uncapped_longest as usize >= src.len()
{
forced_last_stretch = Some((best_candidate.offset_value, uncapped_longest));
forced_last_cur = cur;
break;
}
update_optimal_match_nodes::<IS_ULTRA>(
&mut nodes[..=horizon],
cur,
&mut last_pos,
&candidates,
&price_model,
horizon,
min_match,
);
}
}
cur += 1;
}
if last_pos + 1 <= horizon {
nodes[last_pos + 1].price = MAX_PRICE;
}
if let Some((off, mlen)) = forced_last_stretch {
let tail_literals = backtrace_optimal_path(
&nodes[..=forced_last_cur],
forced_last_cur,
&mut backtrace_buf,
);
for &(literal_length, offset_value, match_length) in &backtrace_buf {
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
literal_length,
offset_value,
match_length,
)?;
}
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
tail_literals,
off,
mlen,
)?;
ip = anchor;
continue;
}
let tail_literals =
backtrace_optimal_path(&nodes[..=last_pos], last_pos, &mut backtrace_buf);
if backtrace_buf.is_empty() {
ip = anchor + tail_literals as usize;
continue;
}
for &(literal_length, offset_value, match_length) in &backtrace_buf {
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
literal_length,
offset_value,
match_length,
)?;
}
ip = anchor;
}
plan.literals.extend_from_slice(&src[anchor..]);
plan.repeat_offsets = repeat_offsets;
plan.opt_price_state = Some(price_model.to_persisted_state());
plan.opt_nodes = nodes;
plan.opt_tree_matches = tree_matches;
plan.opt_candidates = candidates;
plan.opt_backtrace = backtrace_buf;
plan.opt_hash3 = hash3;
Ok(())
}
pub(crate) fn plan_sequences_optimal_with_prefix_two_phase_into<const IS_ULTRA: bool>(
plan: &mut SequencePlan,
src: &[u8],
block_start: usize,
prefix_chain: PrefixChain<'_>,
repeat_offsets: RepeatOffsets,
params: MatchFinderParameters,
match_floor: PrefixedMatchFloor,
source_finder: &mut BinaryTreeFinder,
dict_finder: &BinaryTreeFinder,
ldm: Option<&[RawSequence]>,
) -> Result<()> {
let block_len = src.len().saturating_sub(block_start);
plan.reset_for_block(block_len);
if block_len < MIN_MATCH {
plan.literals.extend_from_slice(&src[block_start..]);
plan.repeat_offsets = repeat_offsets;
return Ok(());
}
let ext_dict_mode = !params.dictionary_attaches;
const DICT_POS_BIAS: usize = 2;
let dict_len = prefix_chain.len();
let prefix_len = if ext_dict_mode {
dict_len + DICT_POS_BIAS
} else {
dict_len
};
let mut virtual_buf = Vec::with_capacity(prefix_len + src.len());
if ext_dict_mode {
virtual_buf.extend_from_slice(&[0u8; DICT_POS_BIAS]);
}
for segment in prefix_chain.segments {
virtual_buf.extend_from_slice(segment);
}
virtual_buf.extend_from_slice(src);
let floor_at = |pos: usize| {
let (prefix_low, source_low) = match_floor.at(pos);
let prefix_low = if ext_dict_mode {
prefix_low + DICT_POS_BIAS
} else {
prefix_low
};
(prefix_low, source_low)
};
let mut price_model = if let Some(mut persisted) = plan.opt_price_state.take() {
persisted.rescale();
OptimalPriceModel::<IS_ULTRA>::from_persisted_state(
&persisted,
params.long_offset_penalty,
params.compressed_literals,
)
} else {
let dict_seed = plan.opt_dict_price_seed.as_ref();
OptimalPriceModel::<IS_ULTRA>::new(
&src[block_start..],
dict_seed,
params.long_offset_penalty,
params.compressed_literals,
)
};
let mut repeat_offsets = repeat_offsets;
let mut anchor = block_start;
let mut ip = block_start;
let limit = src.len().saturating_sub(8);
let mut nodes = core::mem::take(&mut plan.opt_nodes);
nodes.clear();
nodes.resize(OPT_NUM + 1, OptimalPathNode::UNSET);
let mut tree_matches = core::mem::take(&mut plan.opt_tree_matches);
let mut dict_match_buf = core::mem::take(&mut plan.opt_dict_matches);
let mut ldm_candidates = ldm.map(|sequences| LdmCandidates::new(sequences, block_len as u32));
let mut candidates = core::mem::take(&mut plan.opt_candidates);
let mut backtrace_buf = core::mem::take(&mut plan.opt_backtrace);
let mut hash3 = if params.min_match == 3 {
let mut h3 = plan
.opt_hash3
.take()
.unwrap_or_else(|| Hash3Table::new(params.window_log));
h3.next_to_update = block_start;
Some(h3)
} else {
None
};
let sufficient_len = params.target_length.min(OPT_NUM - 1) as u32;
if ip == 0 {
ip = 1;
}
while ip < limit {
let (prefix_low, source_low) = floor_at(ip);
if ip < source_finder.next_to_update {
ip += 1;
continue;
}
if ext_dict_mode {
source_finder.update_tree_unified(&virtual_buf, prefix_len, ip, params.search_depth);
} else {
source_finder.update_tree_unified(src, 0, ip, params.search_depth);
}
collect_optimal_matches_two_phase(
&mut candidates,
&mut tree_matches,
&mut dict_match_buf,
&virtual_buf,
prefix_len,
ip,
repeat_offsets.values(),
ip - anchor,
params,
prefix_low,
source_low,
source_finder,
dict_finder,
hash3.as_mut(),
ext_dict_mode,
sufficient_len,
);
if let Some(ldm_candidates) = ldm_candidates.as_mut() {
ldm_candidates.offer(
&mut candidates,
(ip - block_start) as u32,
(src.len() - ip) as u32,
params.min_match,
);
}
if candidates.is_empty() {
ip += 1;
continue;
}
let horizon = OPT_NUM.min(src.len() - ip);
let best = *candidates.last().expect("candidate list must be non-empty");
if best.length > sufficient_len {
let literal_length = (ip - anchor) as u32;
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
literal_length,
best.offset_value,
best.length,
)?;
ip = anchor;
continue;
}
let litlen0 = (ip - anchor) as u32;
nodes[0] = OptimalPathNode {
price: price_model.ll_price(litlen0),
off: 0,
mlen: 0,
litlen: litlen0,
reps: repeat_offsets.values(),
};
let min_match = if params.min_match == 3 { 3 } else { 4 };
let mut last_pos = init_optimal_match_nodes(
&mut nodes[..=horizon],
&candidates,
&price_model,
horizon,
min_match,
);
let mut forced_last_stretch: Option<(u32, u32)> = None; let mut forced_last_cur = 0usize;
let mut cur = 1usize;
while cur <= last_pos {
let replaced_match = update_optimal_literal_node::<IS_ULTRA>(
&mut nodes[..=horizon],
cur,
src[ip + cur - 1],
&price_model,
);
if nodes[cur].litlen == 0 {
let prev = cur - nodes[cur].mlen as usize;
let mut reps = RepeatOffsets::from_values(nodes[prev].reps);
let _ = reps.resolve_values(nodes[prev].litlen, nodes[cur].off);
nodes[cur].reps = reps.values();
}
let inr = ip + cur;
let (prefix_low, source_low) = floor_at(inr);
if IS_ULTRA {
if let Some(prev_match) = replaced_match {
let ll1_inc = price_model.ll_price(1) as i32 - price_model.ll_price(0) as i32;
if ll1_inc < 0 && cur + 1 <= horizon && inr < src.len() {
let with1literal = prev_match.price as i32
+ price_model.literal_byte_price(src[inr]) as i32
+ ll1_inc;
let new_litlen = nodes[cur].litlen + 1;
let with_more_literals = nodes[cur].price as i32
+ price_model.literal_byte_price(src[inr]) as i32
+ price_model.ll_price(new_litlen) as i32
- price_model.ll_price(nodes[cur].litlen) as i32;
if with1literal < with_more_literals
&& (with1literal as u32) < nodes[cur + 1].price
{
let prev = cur - prev_match.mlen as usize;
let mut rep_offsets = RepeatOffsets::from_values(nodes[prev].reps);
let _ = rep_offsets.resolve_values(nodes[prev].litlen, prev_match.off);
nodes[cur + 1] = OptimalPathNode {
price: with1literal as u32,
off: prev_match.off,
mlen: prev_match.mlen,
litlen: 1,
reps: rep_offsets.values(),
};
if last_pos < cur + 1 {
last_pos = cur + 1;
}
}
}
}
}
if inr > limit {
cur += 1;
continue;
}
if cur == last_pos {
break;
}
if !IS_ULTRA
&& cur + 1 <= horizon
&& nodes[cur + 1].price <= nodes[cur].price + OPT_PRICE_UNIT / 2
{
cur += 1;
continue;
}
if inr < source_finder.next_to_update {
candidates.clear();
} else {
if ext_dict_mode {
source_finder.update_tree_unified(
&virtual_buf,
prefix_len,
inr,
params.search_depth,
);
} else {
source_finder.update_tree_unified(src, 0, inr, params.search_depth);
}
collect_optimal_matches_two_phase(
&mut candidates,
&mut tree_matches,
&mut dict_match_buf,
&virtual_buf,
prefix_len,
inr,
nodes[cur].reps,
nodes[cur].litlen as usize,
params,
prefix_low,
source_low,
source_finder,
dict_finder,
hash3.as_mut(),
ext_dict_mode,
sufficient_len,
);
if let Some(ldm_candidates) = ldm_candidates.as_mut() {
ldm_candidates.offer(
&mut candidates,
(inr - block_start) as u32,
(src.len() - inr) as u32,
params.min_match,
);
}
}
{
if !candidates.is_empty() {
let best_candidate = candidates.last().expect("non-empty");
let uncapped_longest = best_candidate.length;
if uncapped_longest > sufficient_len
|| cur + uncapped_longest as usize >= horizon
|| inr + uncapped_longest as usize >= src.len()
{
forced_last_stretch = Some((best_candidate.offset_value, uncapped_longest));
forced_last_cur = cur;
break;
}
update_optimal_match_nodes::<IS_ULTRA>(
&mut nodes[..=horizon],
cur,
&mut last_pos,
&candidates,
&price_model,
horizon,
min_match,
);
}
}
cur += 1;
}
if last_pos + 1 <= horizon {
nodes[last_pos + 1].price = MAX_PRICE;
}
if let Some((off, mlen)) = forced_last_stretch {
let tail_literals = backtrace_optimal_path(
&nodes[..=forced_last_cur],
forced_last_cur,
&mut backtrace_buf,
);
for &(literal_length, offset_value, match_length) in &backtrace_buf {
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
literal_length,
offset_value,
match_length,
)?;
}
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
tail_literals,
off,
mlen,
)?;
ip = anchor;
continue;
}
let tail_literals =
backtrace_optimal_path(&nodes[..=last_pos], last_pos, &mut backtrace_buf);
if backtrace_buf.is_empty() {
ip = anchor + tail_literals as usize;
continue;
}
for &(literal_length, offset_value, match_length) in &backtrace_buf {
emit_optimal_sequence(
plan,
src,
&mut anchor,
&mut repeat_offsets,
&mut price_model,
literal_length,
offset_value,
match_length,
)?;
}
ip = anchor;
}
plan.literals.extend_from_slice(&src[anchor..]);
plan.repeat_offsets = repeat_offsets;
plan.opt_price_state = Some(price_model.to_persisted_state());
plan.opt_nodes = nodes;
plan.opt_tree_matches = tree_matches;
plan.opt_dict_matches = dict_match_buf;
plan.opt_candidates = candidates;
plan.opt_backtrace = backtrace_buf;
plan.opt_hash3 = hash3;
Ok(())
}