use super::pyramid::Pyramid;
use crate::coder_scratch::CoderScratch;
use crate::entropy::{ALPHABET_SIZE, Token, f_log2, pack_signed, uint_encode};
use crate::lossless::kit::{
PREDICTOR_GRADIENT, selected_grad_pack_interior_fn, tokenize_plane_rows,
};
use crate::squeeze::{Channel, fold_quantized_step};
const MODEL_BITS_PER_CHANNEL: f64 = 48.0;
const MAX_COARSE_SAMPLES: usize = 1 << 18;
const MAX_COARSE_CHANNELS: usize = 256;
struct SymbolCost {
counts: [u32; ALPHABET_SIZE],
raw_bits: u64,
total: u32,
}
impl Default for SymbolCost {
fn default() -> Self {
Self {
counts: [0; ALPHABET_SIZE],
raw_bits: 0,
total: 0,
}
}
}
impl SymbolCost {
fn add(&mut self, value: u32) {
let (symbol, bits, _) = uint_encode(value);
self.counts[symbol as usize] += 1;
self.raw_bits += u64::from(bits);
self.total += 1;
}
fn bits(&self) -> f64 {
let total = f64::from(self.total);
self.raw_bits as f64
+ self
.counts
.iter()
.filter(|&&count| count != 0)
.map(|&count| f64::from(count) * f_log2(total / f64::from(count)))
.sum::<f64>()
}
}
fn channel_bits(ch: &Channel, tokens: &mut Vec<Token>, scratch: &mut CoderScratch) -> f64 {
let mut zero = SymbolCost::default();
for &value in &ch.data {
zero.add(pack_signed(value));
}
tokens.clear();
tokenize_plane_rows(
0,
|y| &ch.data[y * ch.w..][..ch.w],
ch.w,
ch.h,
PREDICTOR_GRADIENT,
selected_grad_pack_interior_fn(),
&mut scratch.gradient,
tokens,
);
let mut gradient = SymbolCost::default();
for token in tokens.iter() {
gradient.add(token.value);
}
zero.bits().min(gradient.bits()) + MODEL_BITS_PER_CHANNEL
}
fn prefix_bits(channels: &[Channel], scratch: &mut CoderScratch) -> f64 {
let mut tokens = Vec::new();
channels
.iter()
.map(|channel| channel_bits(channel, &mut tokens, scratch))
.sum()
}
impl Pyramid {
pub(super) fn fold_last(&mut self) -> bool {
if self.steps.len() <= 1 {
return false;
}
let step = *self.steps.last().unwrap();
if !step.in_place || step.begin_c != 0 {
return false;
}
let offset = step.num_c;
if offset == 0 || offset > self.channels.len() / 2 {
return false;
}
for c in 0..step.num_c {
let avg = &self.channels[c];
let res = &self.channels[offset + c];
let dims = if step.horizontal {
avg.w.checked_add(res.w).map(|w| (w, avg.h))
} else {
avg.h.checked_add(res.h).map(|h| (avg.w, h))
};
if dims.is_none_or(|(w, h)| w > self.group_dim() || h > self.group_dim()) {
return false;
}
}
if !fold_quantized_step(&mut self.channels, &mut self.quants, &step) {
return false;
}
self.steps.pop();
true
}
}
pub(super) fn select_fold(
q: &Pyramid,
speed: crate::Speed,
scratch: &mut CoderScratch,
) -> Option<usize> {
if q.dc_frame
|| q.palette.is_some()
|| !speed.effort().predictor_search
|| q.channels.len() != q.quants.len()
{
return None;
}
let last = *q.steps.last()?;
if last.num_c == 0 || last.begin_c != 0 || !last.in_place {
return None;
}
let exhaustive = speed.effort().ans_exhaustive();
let cuts: &[usize] = if exhaustive { &[2, 4, 6] } else { &[4] };
let shared_steps = q
.steps
.iter()
.rev()
.take_while(|step| step.in_place && step.begin_c == 0 && step.num_c == last.num_c)
.count();
let max_fold = cuts
.iter()
.copied()
.filter(|&count| count <= shared_steps && count < q.steps.len())
.max()?;
let prefix = (max_fold + 1).checked_mul(last.num_c)?;
if prefix > MAX_COARSE_CHANNELS {
return None;
}
let original = q.channels.get(..prefix)?;
let quants = q.quants.get(..prefix)?;
let mut samples = 0usize;
for (ch, &quant) in original.iter().zip(quants) {
samples = samples.checked_add(ch.data.len())?;
if quant == 0
|| ch.w.checked_mul(ch.h)? != ch.data.len()
|| ch.w > q.group_dim()
|| ch.h > q.group_dim()
|| samples > MAX_COARSE_SAMPLES
{
return None;
}
}
let baseline = prefix_bits(original, scratch);
let mut channels = original.to_vec();
let mut quants = quants.to_vec();
let mut best = None;
let pixels = q.xsize.checked_mul(q.ysize)?;
let mut best_gain = 8.0 * (32.0 + pixels as f64 / 2048.0);
for folded in 1..=max_fold {
let step = &q.steps[q.steps.len() - folded];
let fits = (0..step.num_c).all(|c| {
let avg = &channels[c];
let residual = &channels[step.num_c + c];
let dims = if step.horizontal {
avg.w.checked_add(residual.w).map(|w| (w, avg.h))
} else {
avg.h.checked_add(residual.h).map(|h| (avg.w, h))
};
dims.is_some_and(|(w, h)| w <= q.group_dim() && h <= q.group_dim())
});
if !fits {
break;
}
if !fold_quantized_step(&mut channels, &mut quants, step) {
return None;
}
if cuts.contains(&folded) {
let gain = baseline - prefix_bits(&channels, scratch);
if gain > best_gain {
best = Some(folded);
best_gain = gain;
}
}
}
best
}
#[cfg(test)]
mod tests {
use super::super::pyramid::PlainInput;
use super::*;
use crate::coding::CodingTransform;
fn plane(w: usize, h: usize, f: impl Fn(usize, usize) -> i32) -> Pyramid {
let input = PlainInput {
color: vec![(0..w * h).map(|i| f(i % w, i / w)).collect()],
extra: Vec::new(),
max: 65535.0,
coding: CodingTransform::Rgb,
};
Pyramid::plain(
&input,
w,
h,
0.00001,
false,
&crate::thread_pool::ThreadPool::new(1),
)
.unwrap()
}
#[test]
fn flat_prefix_is_not_worth_a_full_frame_trial() {
let q = plane(257, 65, |_, _| 12000);
assert_eq!(
select_fold(&q, crate::Speed::Slow, &mut CoderScratch::default()),
None
);
}
#[test]
fn screen_does_not_modify_the_quantized_pyramid() {
let q = plane(129, 65, |x, y| 20000 + x as i32 * 113 - y as i32 * 59);
let data: Vec<_> = q.channels.iter().map(|ch| ch.data.clone()).collect();
let quants = q.quants.clone();
let steps = q
.steps
.iter()
.map(|s| (s.horizontal, s.in_place, s.begin_c, s.num_c))
.collect::<Vec<_>>();
let _ = select_fold(&q, crate::Speed::Slow, &mut CoderScratch::default());
assert!(
q.channels
.iter()
.zip(data)
.all(|(ch, data)| ch.data == data)
);
assert_eq!(q.quants, quants);
assert_eq!(
q.steps
.iter()
.map(|s| (s.horizontal, s.in_place, s.begin_c, s.num_c))
.collect::<Vec<_>>(),
steps
);
}
#[test]
fn malformed_and_overflowing_prefixes_are_rejected() {
let mut q = plane(65, 65, |x, y| 12000 + (x * y) as i32);
q.quants[0] = u32::MAX;
assert_eq!(
select_fold(&q, crate::Speed::Slow, &mut CoderScratch::default()),
None
);
q.quants[0] = 1;
q.channels[0].data.pop();
assert_eq!(
select_fold(&q, crate::Speed::Slow, &mut CoderScratch::default()),
None
);
}
#[test]
fn screen_can_select_a_profitable_coarse_representation() {
let input = PlainInput {
color: (0..3).map(|c| vec![12000 + c * 1300; 128 * 128]).collect(),
extra: Vec::new(),
max: 65535.0,
coding: CodingTransform::Rgb,
};
let q = Pyramid::plain(
&input,
128,
128,
0.00001,
false,
&crate::thread_pool::ThreadPool::new(1),
)
.unwrap();
assert_eq!(
select_fold(&q, crate::Speed::Slow, &mut CoderScratch::default()),
Some(4),
);
}
#[test]
fn signed_extremes_use_a_bounded_symbol_histogram() {
let ch = Channel {
data: vec![i32::MIN, i32::MAX, 0, -1, 1, i32::MIN],
w: 3,
h: 2,
hshift: 0,
vshift: 0,
};
let bits = channel_bits(&ch, &mut Vec::new(), &mut CoderScratch::default());
assert!(bits.is_finite() && bits >= MODEL_BITS_PER_CHANNEL);
assert!(bits <= MODEL_BITS_PER_CHANNEL + 40.0 * ch.data.len() as f64);
}
}