use super::{ImageDim, K_DC_GROUP_DIM, K_GROUP_DIM};
use crate::bit_writer::BitWriter;
use crate::util::fast_hypot_f64;
fn write_toc(
sizes: &[usize],
permutation: Option<(&[u32], &mut Vec<crate::entropy::HuffmanNode>)>,
w: &mut BitWriter,
) {
match permutation {
Some((permutation, huffman_pool)) => {
w.write(1, 1);
crate::coeff_order::write_permutation(permutation, huffman_pool, w);
}
None => w.write(1, 0),
}
w.zero_pad_to_byte();
let k_bits = [10usize, 14, 22, 30];
for &s in sizes {
let mut offset: usize = 0;
let mut ok = false;
for (i, &b) in k_bits.iter().enumerate() {
if s < offset + (1usize << b) {
w.write(2, i as u64);
w.write(b, (s - offset) as u64);
ok = true;
break;
}
offset += 1usize << b;
}
assert!(ok, "section size {} too large for TOC", s);
}
w.zero_pad_to_byte();
}
pub(crate) fn combine_sections(sections: &mut Vec<BitWriter>, writer: &mut BitWriter) {
combine_sections_ordered(sections, None, writer);
}
pub(crate) fn combined_sections_size(section_bits: &[usize]) -> usize {
let sizes: Vec<usize> = if section_bits.len() == 4 {
vec![section_bits.iter().sum::<usize>().div_ceil(8)]
} else {
section_bits.iter().map(|bits| bits.div_ceil(8)).collect()
};
let mut toc = BitWriter::new();
write_toc(&sizes, None, &mut toc);
toc.bits_written() / 8 + sizes.iter().sum::<usize>()
}
pub(super) fn combine_sections_ordered(
sections: &mut Vec<BitWriter>,
order: Option<(&[usize], &mut Vec<crate::entropy::HuffmanNode>)>,
writer: &mut BitWriter,
) {
if sections.len() == 4 {
let tail: Vec<BitWriter> = sections.drain(1..).collect();
for s in &tail {
sections[0].append(s);
}
}
let order = order.filter(|(order, _)| {
sections.len() > 1 && order.iter().enumerate().any(|(slot, &i)| slot != i)
});
let Some((order, huffman_pool)) = order else {
let sizes: Vec<usize> = sections
.iter()
.map(|s| s.bits_written().div_ceil(8))
.collect();
write_toc(&sizes, None, writer);
writer.append_byte_aligned(sections);
return;
};
debug_assert_eq!(order.len(), sections.len());
let mut permutation = vec![0u32; order.len()];
for (slot, &i) in order.iter().enumerate() {
permutation[i] = slot as u32;
}
let mut taken: Vec<Option<BitWriter>> = sections.drain(..).map(Some).collect();
sections.extend(order.iter().map(|&i| taken[i].take().expect("permutation")));
let sizes: Vec<usize> = sections
.iter()
.map(|s| s.bits_written().div_ceil(8))
.collect();
write_toc(&sizes, Some((&permutation, huffman_pool)), writer);
writer.append_byte_aligned(sections);
}
pub(super) fn group_section_order(
dim: &ImageDim,
num_passes: usize,
group_order: crate::GroupOrder,
) -> Vec<usize> {
let sorted = |xgroups: usize, ygroups: usize, group_dim: usize| -> Vec<usize> {
let mut keys: Vec<(i64, f64, f64, usize)> = (0..xgroups * ygroups)
.map(|g| {
let (x0, y0) = ((g % xgroups) * group_dim, (g / xgroups) * group_dim);
let w = group_dim.min(dim.xsize - x0);
let h = group_dim.min(dim.ysize - y0);
let center = (x0 as f64 + w as f64 / 2.0, y0 as f64 + h as f64 / 2.0);
let (band, radius, angle) = group_order_key(dim, group_dim, center, group_order);
(band, radius, angle, g)
})
.collect();
keys.sort_by(|a, b| {
a.0.cmp(&b.0)
.then(a.1.total_cmp(&b.1))
.then(a.2.total_cmp(&b.2))
.then(a.3.cmp(&b.3))
});
keys.into_iter().map(|(.., g)| g).collect()
};
let dc = sorted(dim.xsize_dc_groups, dim.ysize_dc_groups, K_DC_GROUP_DIM);
let ac = sorted(dim.xsize_groups, dim.ysize_groups, K_GROUP_DIM);
let mut order = vec![0];
order.extend(dc.iter().map(|&g| 1 + g));
order.push(1 + dim.num_dc_groups);
for pass in 0..num_passes {
let base = 2 + dim.num_dc_groups + pass * dim.num_groups;
order.extend(ac.iter().map(|&g| base + g));
}
order
}
fn group_order_key(
dim: &ImageDim,
group_dim: usize,
center: (f64, f64),
group_order: crate::GroupOrder,
) -> (i64, f64, f64) {
let (w, h) = (dim.xsize as f64, dim.ysize as f64);
let (dx, dy) = (center.0 - w / 2.0, center.1 - h / 2.0);
let radius = fast_hypot_f64(dx, dy);
let angle = dx.atan2(-dy).rem_euclid(std::f64::consts::TAU);
let g = group_dim as f64;
match group_order {
crate::GroupOrder::Diagonals => {
let diagonal = fast_hypot_f64(w, h);
let main = (w * center.1 - h * center.0).abs() / diagonal;
let anti = (w * (h - center.1) - h * center.0).abs() / diagonal;
((main.min(anti) / (0.5 * g)).floor() as i64, radius, angle)
}
_ => ((radius / g).floor() as i64, 0.0, angle),
}
}
#[cfg(test)]
mod tests {
#[test]
fn section_size_matches_serialization_at_padding_and_toc_boundaries() {
for sizes in [
vec![1, 2, 3, 4],
vec![8191, 1, 1, 1],
vec![8192, 1, 1, 1],
vec![1, 2, 3, 4, 5],
vec![8184, 8185, 8193, 139256, 139257],
] {
let sections: Vec<_> = sizes
.iter()
.map(|&bits| {
let mut section = crate::bit_writer::BitWriter::new();
for _ in 0..bits {
section.write(1, 1);
}
section
})
.collect();
let expected = super::combined_sections_size(&sizes);
for prefix_bits in 0..8 {
let mut writer = crate::bit_writer::BitWriter::new();
writer.write(prefix_bits, 0);
super::combine_sections(&mut sections.clone(), &mut writer);
assert_eq!(writer.into_bytes().len(), expected);
}
}
}
#[test]
fn center_first_order_is_rings_around_the_center() {
let dim = super::ImageDim::new(2048, 1365);
let order = super::group_section_order(&dim, 2, crate::GroupOrder::CenterFirst);
let n = dim.num_groups;
assert_eq!(order.len(), 3 + 2 * n);
let mut sorted = order.clone();
sorted.sort_unstable();
assert!(sorted.iter().enumerate().all(|(i, &v)| i == v));
assert_eq!(&order[..3], &[0, 1, 2]);
let first: Vec<usize> = order[3..7].iter().map(|&s| s - 3).collect();
assert_eq!(first, [20, 28, 27, 19]);
let pass1: Vec<usize> = order[3 + n..].iter().map(|&s| s - 3 - n).collect();
let pass0: Vec<usize> = order[3..3 + n].iter().map(|&s| s - 3).collect();
assert_eq!(pass0, pass1);
}
#[test]
fn diagonal_order_draws_an_x_first() {
let dim = super::ImageDim::new(2048, 1365);
let order = super::group_section_order(&dim, 1, crate::GroupOrder::Diagonals);
let groups: Vec<usize> = order[3..].iter().map(|&s| s - 3).collect();
let mut x: Vec<usize> = groups[..12].to_vec();
x.sort_unstable();
assert_eq!(x, [9, 10, 13, 14, 19, 20, 26, 27, 28, 29, 33, 38]);
let mut sorted = groups.clone();
sorted.sort_unstable();
assert!(sorted.iter().enumerate().all(|(i, &v)| i == v));
}
}