use super::groups::{DeepLzScratchPool, group_lz_threads};
use super::lz77;
use super::lz77::{
LzToken, estimate_literal_and_run_bits, estimate_streams_bits,
lz77_compress_for_speed_with_depth, lz77_run_count,
};
use crate::coder_scratch::CoderScratch;
use crate::thread_pool::ThreadPool;
pub(super) enum TreeStreams<T> {
Literals(Vec<Vec<T>>),
Lz(Vec<Vec<LzToken>>),
}
pub(super) const LZ_LITERAL_ALTERNATIVE_MAX_RATIO: f64 = 0.98;
pub(super) const LZ_DEEP_MATCHER_MAX_RATIO_PALETTE: f64 = 1.6;
pub(super) const LZ_DEEP_MATCHER_MAX_RATIO_RCT: f64 = 1.01;
const VECTOR_PALETTE_LZ_MAX_RATIO: f64 = 1.20;
pub(super) const VARIANT_WRITE_TOLERANCE: f64 = 1.005;
const PRICED_LZ_MAX_RATIO: f64 = 0.95;
pub(super) fn priced_tree_streams<T: lz77::LiteralToken>(
speed: crate::Speed,
tokens: &[&[T]],
e_lit: f64,
num_contexts: usize,
min_symbol: u32,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<Vec<Vec<LzToken>>> {
type Parser<T> = fn(
&[T],
&lz77::LiteralPrices,
&lz77::MatchPrices,
usize,
&mut Vec<u32>,
) -> Option<Vec<LzToken>>;
let prices = lz77::LiteralPrices::new(tokens, num_contexts);
let threads = group_lz_threads(speed, pool);
let tables = DeepLzScratchPool::new(threads);
let max_probes = if speed.effort().lz_priced_search() {
64
} else {
lz77::PRICED_MAX_PROBES
};
let parse = |scratch: &mut CoderScratch,
match_prices: &lz77::MatchPrices,
parser: Parser<T>| {
pool.steal_map_with_threads(scratch, tokens.len(), threads, |k, _scratch| {
tables.with_depth(|table| parser(tokens[k], &prices, match_prices, max_probes, table))
})
};
let complete = |streams: Vec<Option<Vec<LzToken>>>| -> Vec<Vec<LzToken>> {
streams
.into_iter()
.zip(tokens)
.map(|(stream, literal)| {
stream.unwrap_or_else(|| literal.iter().map(|t| t.as_lz()).collect())
})
.collect()
};
let estimate = |streams: &[Vec<LzToken>], scratch: &mut CoderScratch| {
let slices: Vec<&[LzToken]> = streams.iter().map(Vec::as_slice).collect();
estimate_streams_bits(&slices, num_contexts, min_symbol, pool, scratch)
};
let first = parse(
scratch,
&lz77::MatchPrices::initial(),
lz77::lz77_compress_priced::<T>,
);
if first.iter().all(Option::is_none) {
return None;
}
let learned = {
let kept: Vec<&[LzToken]> = first.iter().flatten().map(Vec::as_slice).collect();
lz77::MatchPrices::learned(&kept, num_contexts)
};
let first = complete(first);
let first_bits = estimate(&first, scratch);
let max_ratio = if speed.effort().lz_priced_search() {
0.99
} else {
PRICED_LZ_MAX_RATIO
};
if first_bits >= e_lit * max_ratio {
return None;
}
let second_parser: Parser<T> = if speed.effort().lz_optimal_parse() {
lz77::lz77_compress_optimal::<T>
} else {
lz77::lz77_compress_priced::<T>
};
let second = parse(scratch, &learned, second_parser);
if second.iter().all(Option::is_none) {
return Some(first);
}
let second = complete(second);
if estimate(&second, scratch) < first_bits {
Some(second)
} else {
Some(first)
}
}
pub(super) fn choose_tree_streams<T: lz77::LiteralToken>(
speed: crate::Speed,
tokens: Vec<Vec<T>>,
distance_ctx: u32,
num_contexts: usize,
min_symbol: u32,
deep_lz_max_ratio: f64,
prune_trailing_lz: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Vec<TreeStreams<T>> {
let extra = if speed.effort().lz_priced_search() {
let slices: Vec<&[T]> = tokens.iter().map(Vec::as_slice).collect();
let (e_lit, _) =
estimate_literal_and_run_bits(&slices, num_contexts, min_symbol, pool, scratch);
priced_tree_streams(
speed,
&slices,
e_lit,
num_contexts,
min_symbol,
pool,
scratch,
)
} else {
None
};
let mut variants = choose_tree_streams_standard(
speed,
tokens,
distance_ctx,
num_contexts,
min_symbol,
deep_lz_max_ratio,
prune_trailing_lz,
pool,
scratch,
);
if let Some(extra) = extra {
variants.push(TreeStreams::Lz(extra));
}
variants
}
fn choose_tree_streams_standard<T: lz77::LiteralToken>(
speed: crate::Speed,
tokens: Vec<Vec<T>>,
distance_ctx: u32,
num_contexts: usize,
min_symbol: u32,
deep_lz_max_ratio: f64,
prune_trailing_lz: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Vec<TreeStreams<T>> {
let raw: usize = tokens.iter().map(Vec::len).sum();
let run_counts = pool.steal_map(scratch, tokens.len(), |k, _scratch| {
lz77_run_count(&tokens[k])
});
let run_len: usize = run_counts.iter().sum();
let deep = |scratch: &mut CoderScratch| -> Vec<Vec<LzToken>> {
let deep_lz = DeepLzScratchPool::new(group_lz_threads(speed, pool));
pool.steal_map_with_threads(
scratch,
tokens.len(),
group_lz_threads(speed, pool),
|k, scratch| {
deep_lz.with_depth(|depth| {
lz77_compress_for_speed_with_depth(
&tokens[k],
distance_ctx,
speed,
depth,
Some(run_counts[k]),
scratch,
)
})
},
)
};
if (run_len as f64) >= LZ_LITERAL_ALTERNATIVE_MAX_RATIO * raw as f64 {
return vec![TreeStreams::Lz(deep(scratch))];
}
let raw_slices: Vec<&[T]> = tokens.iter().map(Vec::as_slice).collect();
let (e_lit, e_run) =
estimate_literal_and_run_bits(&raw_slices, num_contexts, min_symbol, pool, scratch);
if e_run > e_lit * deep_lz_max_ratio {
if let Some(priced) = priced_tree_streams(
crate::Speed::Slow,
&raw_slices,
e_lit,
num_contexts,
min_symbol,
pool,
scratch,
) {
return vec![TreeStreams::Literals(tokens), TreeStreams::Lz(priced)];
}
return vec![TreeStreams::Literals(tokens)];
}
let lz = deep(scratch);
let slices: Vec<&[LzToken]> = lz.iter().map(Vec::as_slice).collect();
let e_lz = estimate_streams_bits(&slices, num_contexts, min_symbol, pool, scratch);
if prune_trailing_lz && e_lz >= e_lit * VECTOR_PALETTE_LZ_MAX_RATIO {
vec![TreeStreams::Literals(tokens)]
} else if e_lz < e_lit {
vec![TreeStreams::Lz(lz), TreeStreams::Literals(tokens)]
} else {
vec![TreeStreams::Literals(tokens), TreeStreams::Lz(lz)]
}
}