use crate::adaptive_quant::dirty_log2f;
use crate::bit_writer::BitWriter;
use crate::entropy::{
Histogram, OwnedEntropyCode, Token, build_huffman_codes, cluster_histograms, uint_encode,
write_entropy_code,
};
pub(crate) const LZ77_MIN_SYMBOL: u32 = 64;
pub(crate) const LZ77_MIN_LENGTH: u32 = 3;
pub(crate) const LZ77_DIST_VALUE: u32 = 0;
#[inline]
pub(crate) 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, Debug, PartialEq)]
pub(crate) enum AcLz {
Lit { context: u32, value: u32 },
Copy { context: u32, length_value: u32 },
}
pub(crate) fn lz77_ac_tokens(tokens: &[Token]) -> impl Iterator<Item = AcLz> + '_ {
struct Runs<'a> {
tokens: &'a [Token],
copy: Option<AcLz>,
}
impl Iterator for Runs<'_> {
type Item = AcLz;
fn next(&mut self) -> Option<AcLz> {
if let Some(copy) = self.copy.take() {
return Some(copy);
}
let (token, rest) = self.tokens.split_first()?;
self.tokens = rest;
if token.value != 0 {
let extra = rest
.iter()
.take_while(|t| t.context == token.context && t.value == token.value)
.count();
if extra >= LZ77_MIN_LENGTH as usize {
self.copy = Some(AcLz::Copy {
context: token.context,
length_value: extra as u32 - LZ77_MIN_LENGTH,
});
self.tokens = &rest[extra..];
}
}
Some(AcLz::Lit {
context: token.context,
value: token.value,
})
}
}
Runs { tokens, copy: None }
}
#[cfg(test)]
pub(crate) fn lz77_compress_ac(tokens: &[Token]) -> Vec<AcLz> {
let n = tokens.len();
let mut out: Vec<AcLz> = Vec::with_capacity(n);
let mut i = 0;
while i < n {
let t = tokens[i];
out.push(AcLz::Lit {
context: t.context,
value: t.value,
});
if t.value == 0 {
i += 1;
continue;
}
let mut j = i + 1;
while j < n && tokens[j].context == t.context && tokens[j].value == t.value {
j += 1;
}
let run_extra = (j - i - 1) as u32; if run_extra >= LZ77_MIN_LENGTH {
out.push(AcLz::Copy {
context: t.context,
length_value: run_extra - LZ77_MIN_LENGTH,
});
i = j;
} else {
i += 1;
}
}
out
}
#[allow(dead_code)] pub(crate) fn build_lz_code_no_cluster(
streams: &[Vec<AcLz>],
num_contexts: usize,
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
) -> OwnedEntropyCode {
let distance_context = (num_contexts - 1) as u32;
let mut histograms = vec![Histogram::new(); num_contexts];
for stream in streams {
for t in stream {
match *t {
AcLz::Lit { context, value } => {
let (sym, _, _) = uint_encode(value);
histograms[context as usize].add(sym);
}
AcLz::Copy {
context,
length_value,
} => {
let (len_tok, _, _) = lz77_length_encode(length_value);
histograms[context as usize].add(LZ77_MIN_SYMBOL + len_tok);
histograms[distance_context as usize].add(LZ77_DIST_VALUE);
}
}
}
}
let context_map: Vec<u8> = (0..num_contexts as u8).collect();
let mut prefix_codes = build_huffman_codes(&histograms, huffman_pool);
for pc in &mut prefix_codes {
let mut nonzero = 0usize;
let mut idx = 0usize;
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[0] = 0;
pc.bits[0] = 0;
} else {
pc.depths[0] = 1;
pc.bits[0] = 0;
pc.depths[idx] = 1;
pc.bits[idx] = 1;
}
}
pc.update_single_symbol();
}
OwnedEntropyCode {
context_map,
prefix_codes,
hybrid_uint_configs: vec![crate::entropy::HybridUintConfig::DEFAULT; num_contexts],
orig_context_map: None,
orig_num_contexts: num_contexts,
use_prefix_code: true,
ans_histograms: Vec::new(),
ans_pricing_freqs: Vec::new(),
ans_symbols: Vec::new(),
ans_reverse_maps: Vec::new(),
}
}
pub(crate) fn build_ac_lz_code<'a>(
streams: impl IntoIterator<Item = &'a [Token]>,
num_contexts: usize,
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
) -> (OwnedEntropyCode, u64) {
let distance_context = num_contexts - 1;
let mut histograms = vec![Histogram::new(); num_contexts];
let mut bits = 0u64;
for stream in streams {
for t in lz77_ac_tokens(stream) {
match t {
AcLz::Lit { context, value } => {
let (sym, nbits, _) = uint_encode(value);
histograms[context as usize].add(sym);
bits += nbits as u64;
}
AcLz::Copy {
context,
length_value,
} => {
let (sym, nbits, _) = lz77_length_encode(length_value);
histograms[context as usize].add(LZ77_MIN_SYMBOL + sym);
histograms[distance_context].add(LZ77_DIST_VALUE);
bits += nbits as u64;
}
}
}
}
let mut context_map = Vec::new();
cluster_histograms(&mut histograms, &mut context_map, huffman_pool);
let prefix_codes = build_huffman_codes(&histograms, huffman_pool);
for (histogram, code) in histograms.iter().zip(&prefix_codes) {
if !code.single_symbol {
for (&count, &depth) in histogram.counts.iter().zip(&code.depths) {
bits += count as u64 * depth as u64;
}
}
}
(
OwnedEntropyCode {
context_map,
prefix_codes,
hybrid_uint_configs: vec![crate::entropy::HybridUintConfig::DEFAULT; histograms.len()],
orig_context_map: None,
orig_num_contexts: num_contexts,
use_prefix_code: true,
ans_histograms: Vec::new(),
ans_pricing_freqs: Vec::new(),
ans_symbols: Vec::new(),
ans_reverse_maps: Vec::new(),
},
bits,
)
}
#[cfg(test)]
pub(crate) fn estimate_ac_lz_bits(
streams: &[Vec<AcLz>],
code: &OwnedEntropyCode,
num_contexts: usize,
) -> u64 {
let distance_context = num_contexts - 1;
let mut bits: u64 = 0;
for stream in streams {
for t in stream {
match *t {
AcLz::Lit { context, value } => {
let (sym, nbits, _) = uint_encode(value);
let cl = code.context_map[context as usize] as usize;
let pc = &code.prefix_codes[cl];
let d = if pc.single_symbol {
0
} else {
pc.depths[sym as usize] as u64
};
bits += d + nbits as u64;
}
AcLz::Copy {
context,
length_value,
} => {
let (len_tok, len_nbits, _) = lz77_length_encode(length_value);
let sym = LZ77_MIN_SYMBOL + len_tok;
let cl = code.context_map[context as usize] as usize;
let pc = &code.prefix_codes[cl];
let d = if pc.single_symbol {
0
} else {
pc.depths[sym as usize] as u64
};
bits += d + len_nbits as u64;
let (dsym, dnbits, _) = uint_encode(LZ77_DIST_VALUE);
let dcl = code.context_map[distance_context] as usize;
let dpc = &code.prefix_codes[dcl];
let dd = if dpc.single_symbol {
0
} else {
dpc.depths[dsym as usize] as u64
};
bits += dd + dnbits as u64;
}
}
}
}
bits
}
pub(crate) fn estimate_ac_plain_bits<'a, I>(streams: I, code: &OwnedEntropyCode) -> u64
where
I: IntoIterator<Item = &'a [Token]>,
{
if !code.use_prefix_code {
let cost: Vec<Vec<f32>> = code
.ans_histograms
.iter()
.map(|histogram| {
histogram
.freqs
.iter()
.map(|&f| {
if f == 0 {
crate::entropy::ANS_LOG_TAB_SIZE as f32
} else {
crate::entropy::ANS_LOG_TAB_SIZE as f32 - dirty_log2f(f as f32)
}
})
.collect()
})
.collect();
let mut bits = 0.0f64;
for tokens in streams {
for t in tokens {
let cl = code.context_map[t.context as usize] as usize;
let (sym, nbits, _) =
crate::entropy::uint_encode_with_config(t.value, code.hybrid_uint_configs[cl]);
bits += cost[cl][sym as usize] as f64 + nbits as f64;
}
}
return bits as u64;
}
let mut bits: u64 = 0;
for tokens in streams {
for t in tokens {
let cl = code.context_map[t.context as usize] as usize;
let (sym, nbits, _) =
crate::entropy::uint_encode_with_config(t.value, code.hybrid_uint_configs[cl]);
bits += code.prefix_codes[cl].depths[sym as usize] as u64 + nbits as u64;
}
}
bits
}
#[inline]
pub(crate) fn write_ac_lz(
t: AcLz,
code: &OwnedEntropyCode,
num_contexts: usize,
w: &mut BitWriter,
) {
let distance_context = num_contexts - 1;
match t {
AcLz::Lit { context, value } => {
let (sym, nbits, bits) = uint_encode(value);
let cluster = code.context_map[context as usize] as usize;
let pc = &code.prefix_codes[cluster];
if pc.single_symbol {
w.write(nbits as usize, bits as u64);
} else {
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);
}
}
AcLz::Copy {
context,
length_value,
} => {
let (len_tok, len_nbits, len_bits) = lz77_length_encode(length_value);
let sym = LZ77_MIN_SYMBOL + len_tok;
let pcluster = code.context_map[context as usize] as usize;
let pc = &code.prefix_codes[pcluster];
if pc.single_symbol {
w.write(len_nbits as usize, len_bits as u64);
} else {
let d = pc.depths[sym as usize] as usize;
debug_assert!(d > 0, "LZ77 AC length symbol {} unrepresented", sym);
let data = (pc.bits[sym as usize] as u64) | ((len_bits as u64) << d);
w.write(d + len_nbits as usize, data);
}
let (dsym, dnbits, dbits) = uint_encode(LZ77_DIST_VALUE);
let dcluster = code.context_map[distance_context] as usize;
let dpc = &code.prefix_codes[dcluster];
if dpc.single_symbol {
w.write(dnbits as usize, dbits as u64);
} else {
let dd = dpc.depths[dsym as usize] as usize;
let ddata = (dpc.bits[dsym as usize] as u64) | ((dbits as u64) << dd);
w.write(dd + dnbits as usize, ddata);
}
}
}
}
pub(crate) fn write_ac_lz_header_and_code(
code: &OwnedEntropyCode,
huffman_pool: &mut Vec<crate::entropy::HuffmanNode>,
w: &mut BitWriter,
) {
w.write(1, 1); w.write(2, 0b11);
w.write(15, (LZ77_MIN_SYMBOL - 8) as u64);
w.write(2, 0b00);
w.write(4, 4);
w.write(3, 0);
w.write(3, 0);
write_entropy_code(&code.as_ref(), huffman_pool, w);
}
#[cfg(test)]
mod tests {
use super::estimate_ac_plain_bits;
use crate::ac_context::K_NUM_AC_CONTEXTS;
use crate::entropy::{Token, optimize_entropy_code_ac};
#[test]
fn plain_estimate_prices_the_ans_path_below_the_huffman_floor() {
let tokens: Vec<Token> = (0..20_000)
.map(|i| Token {
context: 0,
value: u32::from(i % 100 == 0),
})
.collect();
let mut scratch = crate::coder_scratch::CoderScratch::default();
let code = optimize_entropy_code_ac(&tokens, K_NUM_AC_CONTEXTS, &mut scratch.huffman_pool);
assert!(
!code.use_prefix_code,
"expected the rANS path for this stream"
);
let estimate = estimate_ac_plain_bits(std::iter::once(tokens.as_slice()), &code);
let huffman_floor = tokens.len() as u64;
assert!(
estimate < huffman_floor / 2,
"ANS estimate {estimate} should be far below the {huffman_floor}-bit Huffman floor"
);
}
}
#[cfg(test)]
mod lz77_distance_tests {
use super::{AcLz, LZ77_DIST_VALUE, LZ77_MIN_LENGTH, lz77_compress_ac, lz77_length_encode};
use crate::entropy::Token;
fn decode(stream: &[AcLz]) -> Vec<(u32, u32)> {
let mut out: Vec<(u32, u32)> = Vec::new();
for item in stream {
match *item {
AcLz::Lit { context, value } => out.push((context, value)),
AcLz::Copy {
context: _,
length_value,
} => {
let length = length_value + LZ77_MIN_LENGTH;
let distance = (LZ77_DIST_VALUE + 1).min(out.len() as u32).max(1) as usize;
for _ in 0..length {
let src = out.len() - distance;
out.push(out[src]);
}
}
}
}
out
}
#[test]
fn lz77_round_trips_including_runs_with_history() {
let cases: Vec<Vec<Token>> = vec![
vec![Token::new(0, 5); 8],
{
let mut v = vec![Token::new(0, 9), Token::new(0, 3)];
v.extend(std::iter::repeat_n(Token::new(0, 7), 10));
v
},
{
let mut v = Vec::new();
for i in 0..6u32 {
v.push(Token::new(0, i));
v.extend(std::iter::repeat_n(Token::new(0, 100 + i), 5));
}
v
},
];
for tokens in cases {
let expected: Vec<(u32, u32)> = tokens.iter().map(|t| (t.context, t.value)).collect();
let compressed = lz77_compress_ac(&tokens);
assert_eq!(decode(&compressed), expected);
}
}
#[test]
fn lz77_length_tokens_stay_in_alphabet() {
for length_value in [0u32, 1, 7, 63, 255, 4095] {
let (tok, nbits, _) = lz77_length_encode(length_value);
assert!(tok < 64, "length token {tok} escapes the alphabet");
assert!(nbits <= 32);
}
}
}
#[cfg(test)]
mod streaming_tests {
use super::*;
#[test]
fn streamed_runs_and_histogram_price_match_materialized_reference() {
let mut seed = 71u32;
for n in [0, 1, 2, 3, 4, 5, 17, 255, 4096] {
for value in [0, 1, 16, 257] {
let mut tokens = Vec::new();
for i in 0..n {
seed ^= seed << 13;
seed ^= seed >> 17;
seed ^= seed << 5;
tokens.push(Token::new(
(i / 71 % 7) as u32,
if i % 97 < 80 { value } else { seed % 1000 },
));
}
let expected = lz77_compress_ac(&tokens);
assert_eq!(lz77_ac_tokens(&tokens).collect::<Vec<_>>(), expected);
let (code, bits) =
build_ac_lz_code(std::iter::once(tokens.as_slice()), 8, &mut Vec::new());
assert_eq!(bits, estimate_ac_lz_bits(&[expected], &code, 8));
}
}
}
}