use crate::adaptive_quant::dirty_log2f;
use crate::entropy::{ALPHABET_SIZE, OwnedEntropyCode, TokenSlice};
use crate::thread_pool::ThreadPool;
pub(crate) fn estimate_ac_plain_bits<'a, I>(streams: I, code: &OwnedEntropyCode) -> u64
where
I: IntoIterator,
I::Item: Into<TokenSlice<'a>>,
{
estimate_ac_plain_bits_shared(&mut streams.into_iter().map(Into::into), code)
}
fn estimate_ac_plain_bits_shared(
streams: &mut dyn Iterator<Item = TokenSlice<'_>>,
code: &OwnedEntropyCode,
) -> u64 {
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 {
bits += 32.0;
tokens.iter().for_each(|t| {
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 {
tokens.iter().for_each(|t| {
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]);
let prefix = &code.prefix_codes[cl];
let depth = if prefix.single_symbol {
0
} else {
prefix.depths[sym as usize]
};
bits += depth as u64 + nbits as u64;
});
}
bits
}
pub(crate) fn estimate_ac_plain_bits_pooled(
streams: &[TokenSlice<'_>],
code: &OwnedEntropyCode,
pool: Option<&ThreadPool>,
) -> u64 {
fn map<T: Send>(
pool: Option<&ThreadPool>,
len: usize,
f: impl Fn(usize) -> T + Sync,
) -> Vec<T> {
match pool {
Some(pool) => pool.map(len, f),
None => (0..len).map(f).collect(),
}
}
if code.use_prefix_code {
return map(pool, streams.len(), |i| {
let mut bits = 0u64;
streams[i].iter().for_each(|t| {
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]);
let prefix = &code.prefix_codes[cl];
let depth = if prefix.single_symbol {
0
} else {
prefix.depths[sym as usize]
};
bits += depth as u64 + nbits as u64;
});
bits
})
.into_iter()
.sum();
}
let num_clusters = code.ans_histograms.len();
let counted = map(pool, streams.len(), |i| {
let mut counts = vec![0u32; num_clusters * ALPHABET_SIZE];
let mut raw_bits = 0u64;
streams[i].iter().for_each(|t| {
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]);
counts[cl * ALPHABET_SIZE + sym as usize] += 1;
raw_bits += u64::from(nbits);
});
(counts, raw_bits)
});
let mut counts = vec![0u64; num_clusters * ALPHABET_SIZE];
let mut raw_bits = 0u64;
for (stream_counts, stream_raw_bits) in counted {
for (total, count) in counts.iter_mut().zip(stream_counts) {
*total += u64::from(count);
}
raw_bits += stream_raw_bits;
}
let mut bits = 32.0 * streams.len() as f64;
for (cl, histogram) in code.ans_histograms.iter().enumerate() {
for (sym, &f) in histogram.freqs.iter().enumerate() {
let count = counts[cl * ALPHABET_SIZE + sym];
if count == 0 {
continue;
}
let cost = 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)
};
bits += count as f64 * cost as f64;
}
}
bits += raw_bits as f64;
bits as u64
}
#[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"
);
}
}