use super::{
LZ77_DIST_VALUE, LZ77_MIN_LENGTH, LZ77_MIN_SYMBOL, LZ77_NUM_SPECIAL_DISTANCES, LZ77_WINDOW,
LiteralToken, LzToken, lz77_length_encode,
};
use crate::adaptive_quant::{dirty_log2f, dirty_log2p1f};
use crate::entropy::{Token, f_log2};
const PRICE_SYMBOLS: usize = crate::entropy::ALPHABET_SIZE;
pub(in crate::lossless) struct LiteralPrices {
pub(super) bits: Vec<f32>,
}
impl LiteralPrices {
pub(in crate::lossless) fn new<T: LiteralToken>(streams: &[&[T]], num_contexts: usize) -> Self {
let mut counts = vec![0u32; num_contexts * PRICE_SYMBOLS];
let mut totals = vec![0u32; num_contexts];
for stream in streams {
for token in stream.iter() {
let token = token.as_token();
let (symbol, _, _) = crate::entropy::uint_encode(token.value);
counts[token.context as usize * PRICE_SYMBOLS + symbol as usize] += 1;
totals[token.context as usize] += 1;
}
}
let bits = counts
.iter()
.enumerate()
.map(|(i, &count)| {
if count == 0 {
0.0
} else {
(totals[i / PRICE_SYMBOLS] as f32 / count as f32).log2()
}
})
.collect();
Self { bits }
}
#[inline]
pub(super) fn of(&self, token: Token) -> f32 {
let (symbol, nbits, _) = crate::entropy::uint_encode(token.value);
self.bits[token.context as usize * PRICE_SYMBOLS + symbol as usize] + nbits as f32
}
}
const PRICED_LENGTH_BITS: f32 = 6.0;
const PRICED_DISTANCE_BITS: f32 = 6.0;
const PRICED_MIN_GAIN: f32 = 2.0;
const PRICED_RECENT_DISTANCES: usize = 4;
const PRICED_PROBE_TOKENS: usize = 1 << 17;
const PRICED_PROBE_MIN_SAVING: f64 = 0.1;
const PRICED_MAX_LENGTH: usize = 4096;
const PRICED_SKIP_MIN_LENGTH: usize = 16;
pub(in crate::lossless) const PRICED_MAX_PROBES: usize = 32;
const PRICED_GRAM: usize = 6;
const PRICED_HASH_BITS: u32 = 16;
const PRICED_NONE: u32 = u32::MAX;
pub(in crate::lossless) struct MatchPrices {
pub(super) length: f32,
pub(super) distance: [f32; PRICE_SYMBOLS],
}
impl MatchPrices {
pub(in crate::lossless) fn initial() -> Self {
Self {
length: PRICED_LENGTH_BITS,
distance: [PRICED_DISTANCE_BITS; PRICE_SYMBOLS],
}
}
pub(in crate::lossless) fn learned(streams: &[&[LzToken]], num_contexts: usize) -> Self {
let mut counts = vec![0u32; num_contexts * PRICE_SYMBOLS];
let mut totals = vec![0u32; num_contexts];
let mut distances = [0u32; PRICE_SYMBOLS];
let mut matches = 0u32;
for stream in streams {
for token in stream.iter() {
let context = token.context as usize;
totals[context] += 1;
if token.is_lz77() {
let (symbol, _, _) = lz77_length_encode(token.value);
counts[context * PRICE_SYMBOLS + (LZ77_MIN_SYMBOL + symbol) as usize] += 1;
let (symbol, _, _) = crate::entropy::uint_encode(token.distance);
distances[symbol as usize] += 1;
matches += 1;
}
}
}
if matches == 0 {
return Self::initial();
}
let mut length = 0f64;
for context in 0..num_contexts {
for symbol in LZ77_MIN_SYMBOL as usize..PRICE_SYMBOLS {
let count = counts[context * PRICE_SYMBOLS + symbol];
if count != 0 {
length += count as f64 * f_log2(totals[context] as f64 / count as f64);
}
}
}
let unseen = dirty_log2p1f(matches as f32);
Self {
length: (length / matches as f64) as f32,
distance: distances.map(|count| {
if count == 0 {
unseen
} else {
dirty_log2f(matches as f32 / count as f32)
}
}),
}
}
#[inline]
pub(super) fn of(&self, len: usize, distance: usize) -> f32 {
let (_, length_bits, _) = lz77_length_encode(len as u32 - LZ77_MIN_LENGTH);
let (symbol, distance_bits, _) = crate::entropy::uint_encode(lz77_distance_value(distance));
self.length + length_bits as f32 + self.distance[symbol as usize] + distance_bits as f32
}
}
#[inline]
fn lz77_distance_value(distance: usize) -> u32 {
if distance == 1 {
LZ77_DIST_VALUE
} else {
LZ77_NUM_SPECIAL_DISTANCES + distance as u32 - 1
}
}
#[inline]
fn priced_hash<T: LiteralToken>(tokens: &[T], pos: usize) -> usize {
let mut hash = 0x9e37_79b9u32;
for token in &tokens[pos..pos + PRICED_GRAM] {
hash = (hash ^ token.as_token().value).wrapping_mul(0x85eb_ca6b);
hash ^= hash >> 15;
}
(hash.wrapping_mul(0xc2b2_ae35) >> (32 - PRICED_HASH_BITS)) as usize
}
pub(in crate::lossless) fn lz77_compress_priced<T: LiteralToken>(
tokens: &[T],
prices: &LiteralPrices,
match_prices: &MatchPrices,
max_probes: usize,
scratch: &mut Vec<u32>,
) -> Option<Vec<LzToken>> {
let n = tokens.len();
let mut out: Vec<LzToken> = Vec::with_capacity(n.min(16 * 1024));
let heads_len = 1usize << PRICED_HASH_BITS;
scratch.clear();
scratch.resize(heads_len + n, PRICED_NONE);
let (heads, chain) = scratch.split_at_mut(heads_len);
let match_kernel = T::match_kernel();
let mut prefix: Vec<f32> = Vec::with_capacity(n + 1);
let mut sum = 0f64;
prefix.push(0.0);
for token in tokens {
sum += prices.of(token.as_token()) as f64;
prefix.push(sum as f32);
}
let span = |from: usize, len: usize| -> f32 { prefix[from + len] - prefix[from] };
let cheapest_match = match_prices.of(LZ77_MIN_LENGTH as usize, 1);
let insert = |heads: &mut [u32], chain: &mut [u32], pos: usize| {
if pos + PRICED_GRAM <= n {
let h = priced_hash(tokens, pos);
chain[pos] = heads[h];
heads[h] = pos as u32;
}
};
let mut recent = [0usize; PRICED_RECENT_DISTANCES];
let mut no_search_until = 0usize;
let (mut literal_bits, mut saved_bits) = (0f64, 0f64);
let mut probe_at = PRICED_PROBE_TOKENS.min(n / 2);
let mut i = 0usize;
while i < n {
if i >= probe_at {
probe_at = probe_at.saturating_mul(2);
if saved_bits < PRICED_PROBE_MIN_SAVING * (literal_bits + saved_bits) {
return None;
}
}
let limit = (n - i).min(PRICED_MAX_LENGTH);
let mut best = (0f32, 0usize, 0usize);
let mut longest = 0usize;
if i >= no_search_until && span(i, limit) - cheapest_match > PRICED_MIN_GAIN {
let mut consider = |len: usize, distance: usize| {
longest = longest.max(len);
if len >= LZ77_MIN_LENGTH as usize {
let gain = span(i, len) - match_prices.of(len, distance);
if gain > best.0 {
best = (gain, len, distance);
}
}
};
let measure = |from: usize| -> usize {
if !tokens[from].same(tokens[i]) {
return 0;
}
1 + match_kernel(&tokens[from + 1..from + limit], &tokens[i + 1..i + limit])
};
for &distance in &recent {
if distance != 0 && distance <= i {
consider(measure(i - distance), distance);
}
}
if i + PRICED_GRAM <= n {
let mut candidate = heads[priced_hash(tokens, i)];
for _ in 0..max_probes {
if candidate == PRICED_NONE {
break;
}
let from = candidate as usize;
if i - from > LZ77_WINDOW {
break;
}
let len = measure(from);
consider(len, i - from);
if len == limit {
break;
}
candidate = chain[from];
}
}
}
let (gain, len, distance) = best;
if gain > PRICED_MIN_GAIN {
out.push(LzToken::lz77(
tokens[i].as_token().context,
len as u32 - LZ77_MIN_LENGTH,
lz77_distance_value(distance),
));
if let Some(at) = recent.iter().position(|&d| d == distance) {
recent[..=at].rotate_right(1);
} else {
recent.rotate_right(1);
recent[0] = distance;
}
for pos in i..i + len {
insert(heads, chain, pos);
}
saved_bits += gain as f64;
i += len;
} else {
if longest >= PRICED_SKIP_MIN_LENGTH {
no_search_until = i + longest / 2;
}
let token = tokens[i].as_token();
literal_bits += prices.of(token) as f64;
out.push(LzToken::pixel(token.context, token.value));
insert(heads, chain, i);
i += 1;
}
}
Some(out)
}