use super::{NUM_TREE_CONTEXTS, build_balanced_tree_tokens};
use crate::bit_writer::BitWriter;
use crate::coder_scratch::{CoderScratch, LZ77_MAX_CONTEXTS, LzEntropyScratch};
use crate::entropy::{
EntropyCode, Histogram, Token, build_huffman_codes_into, cluster_histograms_fixed,
optimize_entropy_code, write_entropy_code, write_token,
};
pub(super) const LZ77_MIN_SYMBOL: u32 = 64;
pub(super) const LZ77_MIN_LENGTH: u32 = 3;
pub(super) const LZ77_DIST_VALUE: u32 = 1;
pub(super) const LZ77_NUM_SPECIAL_DISTANCES: u32 = 120;
#[inline]
pub(super) fn lz77_length_encode(length_value: u32) -> (u32, u32, u32) {
if length_value < 16 {
(length_value, 0, 0)
} else {
let n = 31 - length_value.leading_zeros();
let token = 16 + n - 4;
let nbits = n;
let bits = length_value - (1 << n);
(token, nbits, bits)
}
}
#[derive(Clone, Copy)]
pub(crate) struct LzToken {
context: u32,
value: u32,
distance: u32,
}
impl LzToken {
#[inline]
fn pixel(context: u32, value: u32) -> Self {
Self {
context,
value,
distance: 0,
}
}
#[inline]
fn lz77(context: u32, length_value: u32, distance_value: u32) -> Self {
debug_assert_ne!(distance_value, 0);
Self {
context,
value: length_value,
distance: distance_value,
}
}
#[inline]
fn is_lz77(self) -> bool {
self.distance != 0
}
}
#[inline]
fn fingerprint(tokens: &[Token], pos: usize) -> u32 {
let mut hash = 0x9e37_79b9u32;
for token in &tokens[pos..tokens.len().min(pos + 3)] {
hash ^= token.value.wrapping_mul(0x85eb_ca6b).rotate_left(13);
hash = hash.wrapping_mul(0xc2b2_ae35) ^ token.context;
}
hash
}
#[inline]
fn hash(tokens: &[Token], pos: usize) -> usize {
const HASH_BITS: usize = 18;
fingerprint(tokens, pos) as usize & ((1 << HASH_BITS) - 1)
}
fn has_repetition(tokens: &[Token], scratch: &mut Vec<u32>) -> bool {
const MAX_SAMPLES: usize = 8_192;
const SAMPLE_TABLE_SIZE: usize = 1 << 14;
if tokens.len() < 256 {
return true;
}
let stride = tokens.len().div_ceil(MAX_SAMPLES).max(1);
if scratch.len() < SAMPLE_TABLE_SIZE {
scratch.resize(SAMPLE_TABLE_SIZE, 0);
}
scratch.fill(0);
let table = scratch;
let mut samples = 0usize;
let mut repeats = 0usize;
for pos in (0..tokens.len().saturating_sub(2)).step_by(stride) {
let fingerprint = fingerprint(tokens, pos) | 1;
let slot = fingerprint as usize & (SAMPLE_TABLE_SIZE - 1);
repeats += usize::from(table[slot] == fingerprint);
table[slot] = fingerprint;
samples += 1;
}
repeats * 5 >= samples
}
fn match_len(tokens: &[Token], a: usize, b: usize) -> usize {
const MAX_MATCH: usize = 1 << 20;
let max_len = (tokens.len() - b).min(MAX_MATCH);
let mut len = 0usize;
while len < max_len {
let x = tokens[a + len];
let y = tokens[b + len];
if x.context != y.context || x.value != y.value {
break;
}
len += 1;
if a + len == b {
let period = b - a;
while len < max_len {
let x = tokens[b + len - period];
let y = tokens[b + len];
if x.context != y.context || x.value != y.value {
break;
}
len += 1;
}
break;
}
}
len
}
fn find_match(
tokens: &[Token],
pos: usize,
head: &[u32],
prev: &[u32],
max_probes: usize,
) -> (usize, usize) {
if pos + LZ77_MIN_LENGTH as usize > tokens.len() {
return (0, 0);
}
let mut candidate = head[hash(tokens, pos)];
let mut best_len = 0usize;
let mut best_dist = 0usize;
let mut probes = 0usize;
while candidate != u32::MAX && probes < max_probes {
let candidate_pos = candidate as usize;
let distance = pos - candidate_pos;
if distance <= u32::MAX as usize {
let len = match_len(tokens, candidate_pos, pos);
if len > best_len || (len == best_len && distance < best_dist) {
best_len = len;
best_dist = distance;
}
}
candidate = prev[candidate_pos];
probes += 1;
}
(best_len, best_dist)
}
#[cfg(test)]
fn lz77_compress(tokens: &[Token]) -> Vec<LzToken> {
let mut scratch = CoderScratch::default();
lz77_compress_with_depth_into(tokens, 8, &mut scratch.lz_depth, &mut scratch.lz_candidate);
scratch.lz_candidate.clone()
}
#[derive(Clone)]
struct RunLzTokens<'a> {
tokens: &'a [Token],
pos: usize,
pending: Option<LzToken>,
}
impl<'a> RunLzTokens<'a> {
fn new(tokens: &'a [Token]) -> Self {
Self {
tokens,
pos: 0,
pending: None,
}
}
}
impl Iterator for RunLzTokens<'_> {
type Item = LzToken;
fn next(&mut self) -> Option<Self::Item> {
if let Some(token) = self.pending.take() {
return Some(token);
}
let token = *self.tokens.get(self.pos)?;
let mut end = self.pos + 1;
while end < self.tokens.len()
&& self.tokens[end].context == token.context
&& self.tokens[end].value == token.value
{
end += 1;
}
let copied = end - self.pos - 1;
self.pos += 1;
if copied >= LZ77_MIN_LENGTH as usize {
self.pending = Some(LzToken::lz77(
token.context,
copied as u32 - LZ77_MIN_LENGTH,
LZ77_DIST_VALUE,
));
self.pos = end;
}
Some(LzToken::pixel(token.context, token.value))
}
}
#[inline]
pub(super) fn lz77_compress_for_speed(
tokens: &[Token],
distance_context: u32,
speed: crate::Speed,
scratch: &mut CoderScratch,
) -> Vec<LzToken> {
if speed == crate::Speed::Fast || !has_repetition(tokens, &mut scratch.lz_repetitions) {
return lz77_compress_runs(tokens);
}
lz77_compress_with_depth_into(tokens, 8, &mut scratch.lz_depth, &mut scratch.lz_candidate);
let run_token_count = run_token_count(tokens);
if scratch.lz_candidate.len() * 100 > run_token_count * 90 {
return lz77_compress_runs(tokens);
}
let deep_bits = estimate_payload_bits(
scratch.lz_candidate.iter().copied(),
distance_context,
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
let run_bits = estimate_payload_bits(
RunLzTokens::new(tokens),
distance_context,
&mut scratch.lz_entropy,
&mut scratch.huffman_pool,
);
if deep_bits * 100 <= run_bits * 90 {
scratch.lz_candidate.clone()
} else {
lz77_compress_runs(tokens)
}
}
fn estimate_payload_bits<I>(
tokens: I,
distance_context: u32,
scratch: &mut LzEntropyScratch,
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
) -> u64
where
I: Iterator<Item = LzToken> + Clone,
{
let num_contexts = distance_context as usize + 1;
assert!(num_contexts <= LZ77_MAX_CONTEXTS);
let histograms = &mut scratch.histograms[..num_contexts];
histograms.fill(Histogram::new());
for (context, slot) in scratch.context_map[..num_contexts].iter_mut().enumerate() {
*slot = context as u8;
}
lz_add_histograms(
tokens.clone(),
&scratch.context_map[..num_contexts],
histograms,
LZ77_MIN_SYMBOL,
distance_context,
);
let codes = &mut scratch.prefix_codes[..num_contexts];
build_huffman_codes_into(histograms, codes, huffman_pool);
let mut bits = 0u64;
for token in tokens {
if token.is_lz77() {
let (symbol, nbits, _) = lz77_length_encode(token.value);
bits += codes[token.context as usize].depths[(LZ77_MIN_SYMBOL + symbol) as usize]
as u64
+ nbits as u64;
let (symbol, nbits, _) = crate::entropy::uint_encode(token.distance);
bits += codes[distance_context as usize].depths[symbol as usize] as u64 + nbits as u64;
} else {
let (symbol, nbits, _) = crate::entropy::uint_encode(token.value);
bits += codes[token.context as usize].depths[symbol as usize] as u64 + nbits as u64;
}
}
bits
}
fn run_token_count(tokens: &[Token]) -> usize {
let mut count = 0usize;
let mut i = 0usize;
while i < tokens.len() {
count += 1;
let token = tokens[i];
let mut end = i + 1;
while end < tokens.len()
&& tokens[end].context == token.context
&& tokens[end].value == token.value
{
end += 1;
}
if end - i > LZ77_MIN_LENGTH as usize {
count += 1;
i = end;
} else {
i += 1;
}
}
count
}
pub(super) fn lz77_compress_runs(tokens: &[Token]) -> Vec<LzToken> {
let mut out = Vec::with_capacity(run_token_count(tokens));
out.extend(RunLzTokens::new(tokens));
out
}
fn lz77_compress_with_depth_into(
tokens: &[Token],
max_probes: usize,
scratch: &mut Vec<u32>,
out: &mut Vec<LzToken>,
) {
out.clear();
debug_assert!(
out.capacity() >= tokens.len(),
"LZ77 candidate scratch was not fully preallocated"
);
const HEAD_LEN: usize = 1 << 18;
let total = HEAD_LEN + tokens.len();
if scratch.len() < total {
scratch.resize(total, u32::MAX);
}
scratch[..HEAD_LEN].fill(u32::MAX);
let (head, tail) = scratch.split_at_mut(HEAD_LEN);
let (prev, _) = tail.split_at_mut(tokens.len());
let mut i = 0usize;
while i < tokens.len() {
let (match_len, distance) = find_match(tokens, i, head, prev, max_probes);
let threshold = if distance <= 16 { 4 } else { 5 };
if match_len >= threshold {
let token_hash = hash(tokens, i);
let old_head = head[token_hash];
prev[i] = old_head;
head[token_hash] = i as u32;
let (next_len, _) = if i + 1 < tokens.len() {
find_match(tokens, i + 1, head, prev, max_probes)
} else {
(0, 0)
};
if next_len > match_len + 1 {
let token = tokens[i];
out.push(LzToken::pixel(token.context, token.value));
i += 1;
continue;
}
head[token_hash] = old_head;
prev[i] = u32::MAX;
let distance_value = if distance == 1 {
LZ77_DIST_VALUE
} else {
LZ77_NUM_SPECIAL_DISTANCES + distance as u32 - 1
};
out.push(LzToken::lz77(
tokens[i].context,
match_len as u32 - LZ77_MIN_LENGTH,
distance_value,
));
for pos in i..i + match_len {
let token_hash = hash(tokens, pos);
prev[pos] = head[token_hash];
head[token_hash] = pos as u32;
}
i += match_len;
} else {
let token = tokens[i];
out.push(LzToken::pixel(token.context, token.value));
let token_hash = hash(tokens, i);
prev[i] = head[token_hash];
head[token_hash] = i as u32;
i += 1;
}
}
}
fn lz_add_histograms<I>(
toks: I,
context_map: &[u8],
histograms: &mut [Histogram],
min_symbol: u32,
distance_context: u32,
) where
I: IntoIterator<Item = LzToken>,
{
for t in toks {
if t.is_lz77() {
let (len_tok, _, _) = lz77_length_encode(t.value);
let pixel_cluster = context_map[t.context as usize] as usize;
histograms[pixel_cluster].add(min_symbol + len_tok);
let dist_cluster = context_map[distance_context as usize] as usize;
let (symbol, _, _) = crate::entropy::uint_encode(t.distance);
histograms[dist_cluster].add(symbol);
} else {
let (sym, _, _) = crate::entropy::uint_encode(t.value);
let cluster = context_map[t.context as usize] as usize;
histograms[cluster].add(sym);
}
}
}
pub(super) fn build_lz_pixel_code<'tokens, 'scratch, I>(
streams: I,
nb_chans: usize,
min_symbol: u32,
refined: bool,
scratch: &'scratch mut LzEntropyScratch,
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
) -> EntropyCode<'scratch>
where
I: Iterator<Item = &'tokens [LzToken]> + Clone,
{
let distance_context = nb_chans as u32;
let num_contexts = nb_chans + 1;
assert!(num_contexts <= LZ77_MAX_CONTEXTS);
let refined = refined
&& streams.clone().any(|toks| {
toks.iter()
.any(|token| token.is_lz77() && token.distance != LZ77_DIST_VALUE)
});
let LzEntropyScratch {
histograms,
prefix_codes,
context_map,
configs,
clustering,
} = scratch;
let histograms = &mut histograms[..num_contexts];
histograms.fill(Histogram::new());
for (context, slot) in context_map[..num_contexts].iter_mut().enumerate() {
*slot = context as u8;
}
for toks in streams.clone() {
lz_add_histograms(
toks.iter().copied(),
&context_map[..num_contexts],
histograms,
min_symbol,
distance_context,
);
}
let num_clusters = cluster_histograms_fixed(
histograms,
&mut context_map[..num_contexts],
refined,
clustering,
huffman_pool,
);
let histograms = &mut histograms[..num_clusters];
let configs = &mut configs[..num_clusters];
if refined {
let mut raw_values = vec![Vec::<u32>::new(); num_clusters];
let mut literal_values = vec![Vec::<u32>::new(); num_clusters];
for toks in streams.clone() {
for &tok in toks {
if tok.is_lz77() {
raw_values[context_map[distance_context as usize] as usize].push(tok.distance);
} else {
let cluster = context_map[tok.context as usize] as usize;
raw_values[cluster].push(tok.value);
literal_values[cluster].push(tok.value);
}
}
}
for (cluster, values) in raw_values.iter().enumerate() {
let selected = crate::entropy::select_hybrid_config(values, huffman_pool);
configs[cluster] = if literal_values[cluster].iter().all(|&value| {
crate::entropy::uint_encode_with_config(value, selected).0 < min_symbol
}) {
selected
} else {
crate::entropy::HybridUintConfig::DEFAULT
};
}
histograms.fill(Histogram::new());
for toks in streams {
for &tok in toks {
if tok.is_lz77() {
let (len_tok, _, _) = lz77_length_encode(tok.value);
histograms[context_map[tok.context as usize] as usize]
.add(min_symbol + len_tok);
let cluster = context_map[distance_context as usize] as usize;
let (symbol, _, _) =
crate::entropy::uint_encode_with_config(tok.distance, configs[cluster]);
histograms[cluster].add(symbol);
} else {
let cluster = context_map[tok.context as usize] as usize;
let (symbol, _, _) =
crate::entropy::uint_encode_with_config(tok.value, configs[cluster]);
histograms[cluster].add(symbol);
}
}
}
} else {
configs.fill(crate::entropy::HybridUintConfig::DEFAULT);
}
let prefix_codes = &mut prefix_codes[..num_clusters];
build_huffman_codes_into(histograms, prefix_codes, huffman_pool);
for pc in prefix_codes.iter_mut() {
let mut nonzero = 0;
let mut idx = 0;
for (i, &d) in pc.depths.iter().enumerate() {
if d != 0 {
nonzero += 1;
idx = i;
if nonzero > 1 {
break;
}
}
}
if nonzero == 1 {
if idx == 0 {
pc.depths[idx] = 0;
pc.bits[idx] = 0;
} else {
pc.depths[0] = 1;
pc.bits[0] = 0;
pc.depths[idx] = 1;
pc.bits[idx] = 1;
}
}
}
EntropyCode {
context_map: &context_map[..num_contexts],
num_contexts,
prefix_codes,
hybrid_uint_configs: configs,
num_prefix_codes: num_clusters,
orig_context_map: None,
orig_num_contexts: num_contexts,
use_prefix_code: true,
ans_freqs: &[],
ans_symbols: &[],
}
}
#[inline]
pub(super) fn write_lz_token(
t: LzToken,
distance_context: u32,
code: &EntropyCode<'_>,
min_symbol: u32,
w: &mut BitWriter,
) {
if t.is_lz77() {
let (len_tok, len_nbits, len_bits) = lz77_length_encode(t.value);
let sym = min_symbol + len_tok;
let pcluster = code.context_map[t.context as usize] as usize;
let pc = &code.prefix_codes[pcluster];
let d = pc.depths[sym as usize] as usize;
debug_assert!(
d > 0,
"LZ77 length symbol {} unrepresented in histogram",
sym
);
let data = (pc.bits[sym as usize] as u64) | ((len_bits as u64) << d);
w.write(d + len_nbits as usize, data);
let dcluster = code.context_map[distance_context as usize] as usize;
let dc = &code.prefix_codes[dcluster];
let (dist_symbol, dist_nbits, dist_bits) =
crate::entropy::uint_encode_with_config(t.distance, code.hybrid_uint_configs[dcluster]);
let dd = dc.depths[dist_symbol as usize] as usize;
if dd > 0 {
let data = dc.bits[dist_symbol as usize] as u64 | ((dist_bits as u64) << dd);
w.write(dd + dist_nbits as usize, data);
} else if dist_nbits != 0 {
w.write(dist_nbits as usize, dist_bits as u64);
}
} else {
let cluster = code.context_map[t.context as usize] as usize;
let (sym, nbits, bits) =
crate::entropy::uint_encode_with_config(t.value, code.hybrid_uint_configs[cluster]);
let pc = &code.prefix_codes[cluster];
let d = pc.depths[sym as usize] as usize;
let data = (pc.bits[sym as usize] as u64) | ((bits as u64) << d);
w.write(d + nbits as usize, data);
}
}
fn write_lz77_header(min_symbol: u32, w: &mut BitWriter) {
w.write(1, 1); w.write(2, 0b11);
w.write(15, (min_symbol - 8) as u64);
w.write(2, 0b00);
w.write(4, 4);
w.write(3, 0);
w.write(3, 0);
}
pub(super) fn write_local_tree_lz77(
predictors: &[u32],
pixel_code: &EntropyCode<'_>,
min_symbol: u32,
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
w: &mut BitWriter,
) {
let tree_tokens = build_balanced_tree_tokens(predictors);
write_tree_lz77(&tree_tokens, pixel_code, min_symbol, huffman_pool, w);
}
pub(super) fn write_tree_lz77(
tree_tokens: &[Token],
pixel_code: &EntropyCode<'_>,
min_symbol: u32,
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
w: &mut BitWriter,
) {
let tree_code = optimize_entropy_code(tree_tokens, NUM_TREE_CONTEXTS, huffman_pool);
let tree_code_ref = tree_code.as_ref();
w.write(1, 0);
write_entropy_code(&tree_code_ref, huffman_pool, w);
for tok in tree_tokens {
write_token(*tok, &tree_code_ref, w);
}
write_lz77_header(min_symbol, w);
write_entropy_code(pixel_code, huffman_pool, w);
}
#[cfg(test)]
mod tests {
use super::*;
fn expand(stream: &[LzToken]) -> Vec<Token> {
let mut out = Vec::new();
for &token in stream {
if token.is_lz77() {
let distance = if token.distance == LZ77_DIST_VALUE {
1
} else {
(token.distance - LZ77_NUM_SPECIAL_DISTANCES + 1) as usize
};
for _ in 0..token.value + LZ77_MIN_LENGTH {
let source = out.len() - distance;
out.push(out[source]);
}
} else {
out.push(Token::new(token.context, token.value));
}
}
out
}
fn same_tokens(a: &[Token], b: &[Token]) -> bool {
a.len() == b.len()
&& a.iter()
.zip(b)
.all(|(a, b)| a.context == b.context && a.value == b.value)
}
#[test]
fn hash_chain_finds_non_run_matches_and_round_trips() {
let pattern: Vec<Token> = (0..37)
.map(|i| Token::new((i % 3) as u32, ((i * 29 + i * i) % 251) as u32))
.collect();
let mut input = pattern.clone();
input.extend((0..11).map(|i| Token::new(1, 900 + i)));
input.extend_from_slice(&pattern);
input.extend_from_slice(&pattern);
let compressed = lz77_compress(&input);
assert!(
compressed
.iter()
.any(|token| token.is_lz77() && token.distance >= LZ77_NUM_SPECIAL_DISTANCES)
);
assert!(same_tokens(&expand(&compressed), &input));
}
#[test]
fn hash_chain_uses_compact_distance_for_runs() {
let input = vec![Token::new(0, 7); 128];
let compressed = lz77_compress(&input);
assert!(
compressed
.iter()
.any(|token| token.is_lz77() && token.distance == LZ77_DIST_VALUE)
);
assert!(same_tokens(&expand(&compressed), &input));
}
#[test]
fn lz_token_is_compact() {
assert_eq!(std::mem::size_of::<LzToken>(), 12);
}
#[test]
fn fixed_context_storage_covers_the_largest_squeeze_tree() {
let steps = crate::squeeze::default_squeeze_steps(
crate::encode_image::MAX_DIMENSION,
crate::encode_image::MAX_DIMENSION,
4,
);
let contexts = 4 * (steps.len() + 1) + 1;
assert_eq!(steps.len(), 54);
assert_eq!(contexts, LZ77_MAX_CONTEXTS);
}
#[test]
fn speed_policy_keeps_fast_run_only_and_slow_structured_search() {
let pattern: Vec<Token> = (0..64)
.map(|i| Token::new((i % 3) as u32, ((i * 37 + 11) % 257) as u32))
.collect();
let input: Vec<Token> = pattern.iter().copied().cycle().take(512).collect();
let mut scratch = CoderScratch::default();
let fast = lz77_compress_for_speed(&input, 3, crate::Speed::Fast, &mut scratch);
assert!(
!fast
.iter()
.any(|token| token.is_lz77() && token.distance != LZ77_DIST_VALUE)
);
let slow = lz77_compress_for_speed(&input, 3, crate::Speed::Slow, &mut scratch);
assert!(
slow.iter()
.any(|token| token.is_lz77() && token.distance != LZ77_DIST_VALUE)
);
assert!(same_tokens(&expand(&slow), &input));
}
fn tokens(n: usize, period: usize) -> Vec<Token> {
(0..n)
.map(|i| Token::new((i % 3) as u32, (i % period) as u32))
.collect()
}
#[test]
fn hash_chain_scratch_is_reset_between_calls() {
let big = tokens(200_000, 7);
let small = tokens(5_000, 7);
let clean = std::thread::spawn({
let small = small.clone();
move || {
let mut scratch = Vec::new();
let mut out = Vec::with_capacity(small.len());
lz77_compress_with_depth_into(&small, 8, &mut scratch, &mut out);
out.len()
}
})
.join()
.unwrap();
let mut scratch = Vec::new();
let mut out = Vec::with_capacity(big.len());
lz77_compress_with_depth_into(&big, 8, &mut scratch, &mut out);
lz77_compress_with_depth_into(&small, 8, &mut scratch, &mut out);
assert_eq!(clean, out.len());
}
#[test]
fn deep_search_handles_varied_stream_lengths() {
let mut scratch = Vec::new();
let mut out = Vec::with_capacity(50_000);
for len in [1_000usize, 50_000, 3_000] {
lz77_compress_with_depth_into(&tokens(len, 5), 8, &mut scratch, &mut out);
}
}
}