use super::extra_tree;
use super::{ImageDim, K_GROUP_DIM};
use crate::bit_writer::BitWriter;
use crate::coder_scratch::CoderScratch;
use crate::encode_image::AlphaPlane;
use crate::encoding_context::EncodingContext;
#[derive(Clone)]
pub(super) struct ExtraSections {
pub(super) global: BitWriter,
pub(super) lf: Vec<BitWriter>,
pub(super) ac: Vec<BitWriter>,
}
impl ExtraSections {
pub(super) fn bits(&self) -> usize {
self.global.bits_written()
+ self.lf.iter().map(BitWriter::bits_written).sum::<usize>()
+ self.ac.iter().map(BitWriter::bits_written).sum::<usize>()
}
fn serialized_size(&self, color_bits: &[usize], dim: &ImageDim, last_pass: usize) -> usize {
let mut bits = color_bits.to_vec();
bits[0] += self.global.bits_written();
for (i, stream) in self.lf.iter().enumerate() {
bits[1 + i] += stream.bits_written();
}
let ac_start = 2 + dim.num_dc_groups + last_pass * dim.num_groups;
for (i, stream) in self.ac.iter().enumerate() {
bits[ac_start + i] += stream.bits_written();
}
super::sections::combined_sections_size(&bits)
}
}
pub(super) struct PreparedExtra {
sections: ExtraSections,
squeezed: Option<crate::lossy_modular::ExtraSqueeze>,
folds: Vec<ExtraSections>,
global_code_ans: bool,
}
impl PreparedExtra {
pub(crate) fn finish(
self,
ctx: &EncodingContext,
dim: &ImageDim,
dc_group_coords: &[(usize, usize)],
last_pass: usize,
color_bits: &[usize],
scratch: &mut CoderScratch,
) -> ExtraSections {
let original = self.sections;
let Some(squeezed) = self.squeezed else {
return original;
};
let Some(start) = squeezed.exact_tail_start() else {
return original;
};
let mut best = None;
let mut best_size = original.serialized_size(color_bits, dim, last_pass);
if !self.folds.is_empty() {
for sections in self.folds {
let size = sections.serialized_size(color_bits, dim, last_pass);
if size < best_size {
best = Some(sections);
best_size = size;
}
}
return best.unwrap_or(original);
}
for retained in [start, start + 2] {
let Some(candidate) = squeezed.without_exact_tail(retained) else {
continue;
};
let sections = squeezed_sections(
ctx,
&candidate,
dim,
dc_group_coords,
self.global_code_ans,
Some((&squeezed, &original)),
scratch,
);
let size = sections.serialized_size(color_bits, dim, last_pass);
if size < best_size {
best = Some(sections);
best_size = size;
}
}
best.unwrap_or(original)
}
}
pub(super) struct ExtraPalette {
pub(super) entries: Vec<i32>,
pub(super) indices: AlphaPlane,
}
const EXTRA_PALETTE_MAX_COLORS: usize = 256;
const GLOBAL_TREE_MAX_SAVING: usize = 4;
const GRADIENT_TREE_MAX_SAVING: f64 = 2.5;
fn extra_palette(plane: &AlphaPlane) -> Option<ExtraPalette> {
let range = match plane {
AlphaPlane::U8(_) => 1usize << 8,
AlphaPlane::U16 { bits, .. } => 1usize << bits,
AlphaPlane::F32(_) => return None,
};
let mut seen = vec![false; range];
for i in 0..plane.len() {
let v = plane.get_i32(i);
if v < 0 || v as usize >= range {
return None;
}
seen[v as usize] = true;
}
let entries: Vec<i32> = (0..range as i32).filter(|&v| seen[v as usize]).collect();
let (Some(&lo), Some(&hi)) = (entries.first(), entries.last()) else {
return None;
};
if entries.len() < 2
|| entries.len() > EXTRA_PALETTE_MAX_COLORS
|| 2 * entries.len() as i64 > i64::from(hi - lo) + 1
{
return None;
}
let mut index_of = vec![0u8; range];
for (index, &v) in entries.iter().enumerate() {
index_of[v as usize] = index as u8;
}
let indices = (0..plane.len())
.map(|i| index_of[plane.get_i32(i) as usize])
.collect();
Some(ExtraPalette {
entries,
indices: AlphaPlane::U8(indices),
})
}
fn lossless_sections(
ctx: &EncodingContext,
plane: &AlphaPlane,
palette: Option<&ExtraPalette>,
dim: &ImageDim,
num_dc_groups: usize,
global_code_ans: bool,
scratch: &mut CoderScratch,
) -> ExtraSections {
let mut sections = ExtraSections {
global: BitWriter::new(),
lf: (0..num_dc_groups).map(|_| BitWriter::new()).collect(),
ac: Vec::new(),
};
match palette {
Some(p) => crate::modular::write_global_palette_alpha_modular(
&p.entries,
plane.bits(),
scratch,
&mut sections.global,
),
None => crate::modular::write_global_alpha_modular(
plane,
dim.xsize,
dim.ysize,
ctx.extra_step,
global_code_ans,
scratch,
&mut sections.global,
),
}
let ac_plane = palette.map_or(plane, |p| &p.indices);
sections.ac = ctx
.thread_pool
.steal_map(scratch, dim.num_groups, |group_id, scratch| {
let x0 = (group_id % dim.xsize_groups) * K_GROUP_DIM;
let y0 = (group_id / dim.xsize_groups) * K_GROUP_DIM;
let mut w = BitWriter::new();
crate::modular::write_ac_group_alpha(
ac_plane,
dim.xsize,
dim.ysize,
x0,
y0,
K_GROUP_DIM.min(dim.xsize - x0),
K_GROUP_DIM.min(dim.ysize - y0),
ctx.extra_step,
scratch,
&mut w,
);
w
});
sections
}
fn squeezed_sections(
ctx: &EncodingContext,
squeezed: &crate::lossy_modular::ExtraSqueeze,
dim: &ImageDim,
dc_group_coords: &[(usize, usize)],
global_code_ans: bool,
previous: Option<(&crate::lossy_modular::ExtraSqueeze, &ExtraSections)>,
scratch: &mut CoderScratch,
) -> ExtraSections {
let mut global = BitWriter::new();
squeezed.write_global(global_code_ans, scratch, &mut global);
let lf = if let Some((_, previous)) =
previous.filter(|(original, _)| original.exact_tail_groups_unchanged(squeezed))
{
previous.lf.clone()
} else {
ctx.thread_pool
.steal_map(scratch, dc_group_coords.len(), |i, scratch| {
let (gx, gy) = dc_group_coords[i];
let mut w = BitWriter::new();
squeezed.write_lf_group(gx, gy, scratch, &mut w);
w
})
};
let ac = if let Some((_, previous)) =
previous.filter(|(original, _)| original.exact_tail_ac_unchanged(squeezed))
{
previous.ac.clone()
} else {
ctx.thread_pool
.steal_map(scratch, dim.num_groups, |group_id, scratch| {
let mut w = BitWriter::new();
squeezed.write_ac_group(
group_id % dim.xsize_groups,
group_id / dim.xsize_groups,
scratch,
&mut w,
);
w
})
};
ExtraSections { global, lf, ac }
}
struct JointSqueeze {
squeezed: crate::lossy_modular::ExtraSqueeze,
local: ExtraSections,
folds: Vec<(crate::lossy_modular::ExtraSqueeze, ExtraSections)>,
rep: Option<usize>,
tree: Option<extra_tree::GlobalExtraTree>,
ans: bool,
}
impl JointSqueeze {
#[allow(clippy::too_many_arguments)]
fn plan(
ctx: &EncodingContext,
squeezed: crate::lossy_modular::ExtraSqueeze,
local: ExtraSections,
dim: &ImageDim,
dc_group_coords: &[(usize, usize)],
ans: bool,
streams: &extra_tree::GlobalStreams<'_>,
scratch: &mut CoderScratch,
) -> Self {
let folds: Vec<(crate::lossy_modular::ExtraSqueeze, ExtraSections)> = squeezed
.exact_tail_start()
.map(|start| {
[start, start + 2]
.into_iter()
.filter_map(|retained| squeezed.without_exact_tail(retained))
.map(|fold| {
let sections = squeezed_sections(
ctx,
&fold,
dim,
dc_group_coords,
ans,
Some((&squeezed, &local)),
scratch,
);
(fold, sections)
})
.collect()
})
.unwrap_or_default();
let rep = (0..folds.len())
.min_by_key(|&i| folds[i].1.bits())
.filter(|&i| folds[i].1.bits() < local.bits());
let (rep_squeeze, rep_sections) =
rep.map_or((&squeezed, &local), |i| (&folds[i].0, &folds[i].1));
let tree = extra_tree::plan_global_squeeze_tree(
ctx,
rep_squeeze,
dim,
streams,
rep_sections,
scratch,
);
Self {
squeezed,
local,
folds,
rep,
tree,
ans,
}
}
fn bits(&self) -> usize {
let rep = self.rep.map_or(&self.local, |i| &self.folds[i].1);
rep.bits() - self.tree.as_ref().map_or(0, |t| t.saving())
}
fn finish(self, streams: &mut extra_tree::GlobalStreams<'_>) -> PreparedExtra {
if let Some(tree) = self.tree {
let mut sections = self.rep.map_or(self.local, |i| self.folds[i].1.clone());
tree.apply(streams, &mut sections);
return PreparedExtra {
sections,
squeezed: None,
folds: Vec::new(),
global_code_ans: self.ans,
};
}
PreparedExtra {
sections: self.local,
squeezed: Some(self.squeezed),
folds: self
.folds
.into_iter()
.map(|(_, sections)| sections)
.collect(),
global_code_ans: self.ans,
}
}
}
pub(super) fn prepare_extra_sections(
ctx: &EncodingContext,
plane: &AlphaPlane,
dim: &ImageDim,
dc_group_coords: &[(usize, usize)],
last_pass: usize,
mut streams: extra_tree::GlobalStreams<'_>,
scratch: &mut CoderScratch,
) -> PreparedExtra {
let single = dim.xsize <= K_GROUP_DIM && dim.ysize <= K_GROUP_DIM;
let lossless_plane = ctx.extra_step == 1 && !plane.is_constant();
let mut palette = lossless_plane.then(|| extra_palette(plane)).flatten();
let ans = !streams.code.use_prefix_code;
let groups = dc_group_coords.len();
let mut lossless = match palette.as_ref().filter(|_| !single) {
Some(p) => {
let indexed = lossless_sections(ctx, plane, Some(p), dim, groups, ans, scratch);
if ctx.extra_plane_tree.is_some() {
indexed
} else {
let plain = lossless_sections(ctx, plane, None, dim, groups, ans, scratch);
if plain.bits() < indexed.bits() {
palette = None;
plain
} else {
indexed
}
}
}
None => lossless_sections(ctx, plane, None, dim, groups, ans, scratch),
};
let squeezed = (ctx.extra_squeeze_distance > 0.0 && !plane.is_constant())
.then(|| {
crate::lossy_modular::ExtraSqueeze::new(
plane,
dim.xsize,
dim.ysize,
ctx.extra_squeeze_distance,
ctx.extra_learned_trees,
ctx.extra_context_trees,
)
})
.flatten();
let lossy = squeezed
.as_ref()
.map(|s| squeezed_sections(ctx, s, dim, dc_group_coords, ans, None, scratch));
let global_tree = (lossless_plane
&& ctx.extra_plane_tree.is_some_and(|budget| {
lossy.as_ref().is_none_or(|lossy| {
if budget.gradient_only {
(lossless.bits() as f64) < GRADIENT_TREE_MAX_SAVING * lossy.bits() as f64
} else {
lossless.bits() < GLOBAL_TREE_MAX_SAVING * lossy.bits()
}
})
}))
.then(|| {
extra_tree::plan_global_extra_tree(
ctx,
plane,
palette.as_ref(),
dim,
last_pass,
&streams,
&lossless,
scratch,
)
})
.flatten();
let lossless_bits = lossless.bits() - global_tree.as_ref().map_or(0, |t| t.saving());
match lossy {
Some(lossy) if lossy.bits() < lossless_bits => {
let squeezed = squeezed.expect("lossy sections come from a squeeze");
if ctx.speed.effort().extra_global_tree {
let joint = JointSqueeze::plan(
ctx,
squeezed,
lossy,
dim,
dc_group_coords,
ans,
&streams,
scratch,
);
let levels = lossy_palette(
ctx,
plane,
&joint.squeezed,
joint.bits(),
dim,
last_pass,
&mut streams,
scratch,
);
return levels.unwrap_or_else(|| joint.finish(&mut streams));
}
if let Some(levels) = lossy_palette(
ctx,
plane,
&squeezed,
lossy.bits(),
dim,
last_pass,
&mut streams,
scratch,
) {
return levels;
}
PreparedExtra {
sections: lossy,
squeezed: squeezed.exact_tail_start().is_some().then_some(squeezed),
folds: Vec::new(),
global_code_ans: ans,
}
}
_ => {
if let Some(tree) = global_tree {
tree.apply(&mut streams, &mut lossless);
}
PreparedExtra {
sections: lossless,
squeezed: None,
folds: Vec::new(),
global_code_ans: ans,
}
}
}
}
fn squeezed_error(
plane: &AlphaPlane,
squeezed: &crate::lossy_modular::ExtraSqueeze,
weights: &[f32],
) -> f64 {
let max = (1i64 << plane.bits()) - 1;
squeezed
.reconstruct()
.iter()
.zip(weights)
.enumerate()
.map(|(i, (&v, &w))| {
let e = i64::from(v).clamp(0, max) - i64::from(plane.get_i32(i));
f64::from(w) * (e * e) as f64
})
.sum()
}
const PALETTE_SCREEN: f64 = 4.0;
#[allow(clippy::too_many_arguments)]
fn lossy_palette(
ctx: &EncodingContext,
plane: &AlphaPlane,
squeezed: &crate::lossy_modular::ExtraSqueeze,
squeezed_bits: usize,
dim: &ImageDim,
last_pass: usize,
streams: &mut extra_tree::GlobalStreams<'_>,
scratch: &mut CoderScratch,
) -> Option<PreparedExtra> {
if ctx.extra_plane_tree.is_none() || ctx.extra_step != 1 {
return None;
}
let weights = super::extra_levels::error_weights(plane, dim.xsize, dim.ysize);
let budget =
super::extra_levels::LOSSY_PALETTE_ERROR * squeezed_error(plane, squeezed, &weights);
let levels = super::extra_levels::fewest_levels(plane, &weights, budget)?;
let indices: Vec<i32> = (0..levels.len()).map(|i| levels.get_i32(i)).collect();
let estimate = crate::lossy_modular::palette_index_bits(&indices, dim.xsize, dim.ysize);
if estimate > PALETTE_SCREEN * squeezed_bits as f64 {
return None;
}
let single = dim.xsize <= K_GROUP_DIM && dim.ysize <= K_GROUP_DIM;
let ans = !streams.code.use_prefix_code;
let palette = extra_palette(&levels);
let groups = dim.num_dc_groups;
let local_palette = palette.as_ref().filter(|_| !single);
let mut sections = lossless_sections(ctx, &levels, local_palette, dim, groups, ans, scratch);
let tree = extra_tree::plan_global_extra_tree(
ctx,
&levels,
palette.as_ref(),
dim,
last_pass,
streams,
§ions,
scratch,
);
if sections.bits() - tree.as_ref().map_or(0, |t| t.saving()) >= squeezed_bits {
return None;
}
if let Some(tree) = tree {
tree.apply(streams, &mut sections);
}
Some(PreparedExtra {
sections,
squeezed: None,
folds: Vec::new(),
global_code_ans: ans,
})
}
pub(super) fn zero_alpha_for_lossy(
alpha: Option<&AlphaPlane>,
pixels: usize,
) -> Option<AlphaPlane> {
match alpha {
Some(AlphaPlane::U8(_)) => Some(AlphaPlane::U8(vec![0; pixels])),
Some(AlphaPlane::U16 { bits, .. }) => Some(AlphaPlane::U16 {
data: vec![0; pixels],
bits: *bits,
}),
Some(AlphaPlane::F32(_)) => Some(AlphaPlane::F32(vec![0; pixels])),
None => None,
}
}
#[cfg(test)]
mod tests {
use super::*;
fn writer(bits: usize) -> BitWriter {
let mut w = BitWriter::new();
for _ in 0..bits {
w.write(1, 1);
}
w
}
#[test]
fn extra_size_matches_aligned_sections_and_last_pass() {
for (width, height) in [(63, 61), (513, 17), (2051, 257)] {
let dim = ImageDim::new(width, height);
for passes in [1, 3] {
let count = 2 + dim.num_dc_groups + passes * dim.num_groups;
for boundary in [7, 8184, 8191, 139256] {
let color_bits: Vec<usize> = (0..count).map(|i| boundary + i % 8).collect();
let extra = ExtraSections {
global: writer(13),
lf: (0..dim.num_dc_groups).map(|i| writer(5 + i)).collect(),
ac: (0..dim.num_groups).map(|i| writer(9 + i)).collect(),
};
let mut sections: Vec<BitWriter> =
color_bits.iter().map(|&bits| writer(bits)).collect();
sections[0].append(&extra.global);
for (i, lf) in extra.lf.iter().enumerate() {
sections[1 + i].append(lf);
}
let last_ac = 2 + dim.num_dc_groups + (passes - 1) * dim.num_groups;
for (i, ac) in extra.ac.iter().enumerate() {
sections[last_ac + i].append(ac);
}
let mut output = BitWriter::new();
super::super::sections::combine_sections(&mut sections, &mut output);
assert_eq!(
extra.serialized_size(&color_bits, &dim, passes - 1),
output.bits_written() / 8,
);
}
}
}
}
}