use crate::coder_scratch::CoderScratch;
use crate::image::{Image3F, Image3Si};
use crate::thread_pool::ThreadPool;
use std::collections::HashMap;
pub(crate) struct LossyPatches {
pub(crate) base: Image3F,
pub(crate) groups: Vec<Vec<(usize, usize)>>,
}
#[derive(Clone, Copy)]
pub(crate) enum VarDctFrameKind<'a> {
Regular,
ReferenceOnly { width: usize, height: usize },
Patched(&'a [PatchReference]),
}
fn hash_tile(linear: &Image3F, x0: usize, y0: usize, tile: usize) -> u64 {
let mut h: u64 = 0x9e37_79b9_7f4a_7c15;
for c in 0..3 {
for y in y0..y0 + tile {
let row = &linear.plane_row(c, y)[x0..x0 + tile];
for pair in row.as_chunks::<2>().0 {
let v = u64::from(pair[0].to_bits()) | (u64::from(pair[1].to_bits()) << 32);
h = (h ^ v).wrapping_mul(0xff51_afd7_ed55_8ccd);
h ^= h >> 29;
}
}
}
h
}
fn tile_energy(img: &Image3F, x0: usize, y0: usize, tile: usize) -> f32 {
let mut energy = 0.0;
for c in 0..3 {
let mut sum = 0.0;
for y in y0..y0 + tile {
sum += img.plane_row(c, y)[x0..x0 + tile].iter().sum::<f32>();
}
let mean = sum / (tile * tile) as f32;
for y in y0..y0 + tile {
energy += img.plane_row(c, y)[x0..x0 + tile]
.iter()
.map(|v| (v - mean).abs())
.sum::<f32>();
}
}
energy / (tile * tile) as f32
}
const MIN_PATCH_ENERGY: f32 = 0.017;
const MIN_PATCH_OCCURRENCES: usize = 5;
const MAX_PATCH_GROUPS: usize = 4096;
#[cfg(test)]
pub(crate) fn find_lossy_patches(
linear: &Image3F,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<LossyPatches> {
find_lossy_patches_sized(linear, PATCH_TILE, 0.0, pool, scratch)
}
static NEAR_TILE_UNIT: [f32; 3] = [0.0005, 0.0035, 0.006];
const NEAR_TILE_BUCKET_SCAN: usize = 24;
pub(crate) fn find_lossy_patches_sized(
linear: &Image3F,
tile: usize,
near: f32,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<LossyPatches> {
let width = linear.xsize();
let height = linear.ysize();
if width < tile || height < tile {
return None;
}
let (tiles_x, tiles_y) = (width / tile, height / tile);
let rows = pool.steal_map(scratch, tiles_y, |ty, _scratch| {
(0..tiles_x)
.map(|tx| hash_tile(linear, tx * tile, ty * tile, tile))
.collect::<Vec<u64>>()
});
let mut buckets: HashMap<u64, Vec<(usize, usize)>> =
HashMap::with_capacity(tiles_x.saturating_mul(tiles_y));
for (ty, row) in rows.into_iter().enumerate() {
for (tx, hash) in row.into_iter().enumerate() {
buckets
.entry(hash)
.or_default()
.push((tx * tile, ty * tile));
}
}
let mut groups = Vec::new();
let min_occurrences = MIN_PATCH_OCCURRENCES;
for candidates in buckets.into_values() {
if candidates.len() < min_occurrences {
continue;
}
let mut exact_groups: Vec<Vec<(usize, usize)>> = Vec::new();
for pos in candidates {
let matching = exact_groups.iter().position(|group| {
let first = group[0];
(0..3).all(|c| {
(0..tile).all(|dy| {
linear.plane_row(c, first.1 + dy)[first.0..first.0 + tile]
== linear.plane_row(c, pos.1 + dy)[pos.0..pos.0 + tile]
})
})
});
if let Some(i) = matching {
exact_groups[i].push(pos);
} else {
exact_groups.push(vec![pos]);
}
}
groups.extend(
exact_groups
.into_iter()
.filter(|g| g.len() >= min_occurrences),
);
}
if near > 0.0 {
sort_patch_groups(&mut groups);
let tol = NEAR_TILE_UNIT.map(|u| u * near);
let mut taken = vec![false; tiles_x * tiles_y];
for g in &groups {
for &(x, y) in g {
taken[(y / tile) * tiles_x + x / tile] = true;
}
}
let cell = tile / 2;
let signature = |x0: usize, y0: usize| -> [u64; 2] {
let mut means = [0f32; 6];
for cy in 0..2 {
for cx in 0..2 {
let mut sum = 0.0f32;
for dy in 0..cell {
let row = linear.plane_row(1, y0 + cy * cell + dy);
sum += row[x0 + cx * cell..x0 + (cx + 1) * cell]
.iter()
.sum::<f32>();
}
means[cy * 2 + cx] = sum / (cell * cell) as f32 / (16.0 * tol[1]);
}
}
for (slot, c) in [(4usize, 0usize), (5, 2)] {
let mut sum = 0.0f32;
for dy in 0..tile {
sum += linear.plane_row(c, y0 + dy)[x0..x0 + tile]
.iter()
.sum::<f32>();
}
means[slot] = sum / (tile * tile) as f32 / (16.0 * tol[c]);
}
[0.0f32, 0.5].map(|shift| {
let mut h: u64 = 0x9e37_79b9_7f4a_7c15 ^ shift.to_bits() as u64;
for m in means {
h = (h ^ (m + shift).floor() as i64 as u64).wrapping_mul(0xff51_afd7_ed55_8ccd);
h ^= h >> 29;
}
h
})
};
let within = |a: (usize, usize), b: (usize, usize)| -> bool {
(0..3).all(|c| {
(0..tile).all(|dy| {
let ra = &linear.plane_row(c, a.1 + dy)[a.0..a.0 + tile];
let rb = &linear.plane_row(c, b.1 + dy)[b.0..b.0 + tile];
ra.iter().zip(rb).all(|(p, q)| (p - q).abs() <= tol[c])
})
})
};
let exact_count = groups.len();
let mut table: HashMap<u64, Vec<usize>> = HashMap::new();
for (gi, g) in groups.iter().enumerate() {
for key in signature(g[0].0, g[0].1) {
table.entry(key).or_default().push(gi);
}
}
for ty in 0..tiles_y {
for tx in 0..tiles_x {
if taken[ty * tiles_x + tx] {
continue;
}
let pos = (tx * tile, ty * tile);
if tile_energy(linear, pos.0, pos.1, tile) < MIN_PATCH_ENERGY {
continue;
}
let keys = signature(pos.0, pos.1);
let found = keys.iter().find_map(|key| {
table
.get(key)?
.iter()
.take(NEAR_TILE_BUCKET_SCAN)
.copied()
.find(|&gi| within(groups[gi][0], pos))
});
match found {
Some(gi) => groups[gi].push(pos),
None => {
let mut registered = false;
for key in keys {
let bucket = table.entry(key).or_default();
if bucket.len() < NEAR_TILE_BUCKET_SCAN {
bucket.push(groups.len());
registered = true;
}
}
if registered {
groups.push(vec![pos]);
}
}
}
}
}
let mut index = 0;
groups.retain(|g| {
index += 1;
index <= exact_count || g.len() >= min_occurrences
});
}
groups.retain(|g| tile_energy(linear, g[0].0, g[0].1, tile) >= MIN_PATCH_ENERGY);
sort_patch_groups(&mut groups);
groups.truncate(MAX_PATCH_GROUPS);
if groups.is_empty() {
return None;
}
let mut base = linear.clone();
for positions in &groups {
for &(x, y) in positions {
for c in 0..3 {
for dy in 0..tile {
base.plane_row_mut(c, y + dy)[x..x + tile].fill(0.0);
}
}
}
}
Some(LossyPatches { base, groups })
}
pub(crate) fn pack_lossy_atlas(
linear: &Image3F,
groups: Vec<Vec<(usize, usize)>>,
ref_frame: u32,
) -> (Image3F, Vec<PatchReference>) {
pack_lossy_atlas_sized(linear, groups, PATCH_TILE, ref_frame)
}
pub(crate) fn stack_atlases(
top: Image3F,
bottom: Image3F,
bottom_refs: &mut [PatchReference],
) -> Image3F {
let top_h = top.ysize().next_multiple_of(16);
let width = top.xsize().max(bottom.xsize());
let mut atlas = Image3F::new(width, top_h + bottom.ysize());
for c in 0..3 {
for y in 0..top.ysize() {
atlas.plane_row_mut(c, y)[..top.xsize()]
.copy_from_slice(&top.plane_row(c, y)[..top.xsize()]);
}
for y in 0..bottom.ysize() {
atlas.plane_row_mut(c, top_h + y)[..bottom.xsize()]
.copy_from_slice(&bottom.plane_row(c, y)[..bottom.xsize()]);
}
}
for r in bottom_refs {
r.atlas_y += top_h;
}
atlas
}
pub(crate) fn pack_lossy_atlas_sized(
linear: &Image3F,
groups: Vec<Vec<(usize, usize)>>,
tile: usize,
ref_frame: u32,
) -> (Image3F, Vec<PatchReference>) {
let atlas_cols = groups.len().min(256 / tile);
let atlas_rows = groups.len().div_ceil(atlas_cols);
let mut atlas = Image3F::new(atlas_cols * tile, atlas_rows * tile);
let mut references = Vec::with_capacity(groups.len());
for (i, positions) in groups.into_iter().enumerate() {
let atlas_x = (i % atlas_cols) * tile;
let atlas_y = (i / atlas_cols) * tile;
let (sx, sy) = positions[0];
for c in 0..3 {
for dy in 0..tile {
atlas.plane_row_mut(c, atlas_y + dy)[atlas_x..atlas_x + tile]
.copy_from_slice(&linear.plane_row(c, sy + dy)[sx..sx + tile]);
}
}
references.push(PatchReference {
width: tile,
height: tile,
atlas_x,
atlas_y,
ref_frame,
add: false,
positions,
});
}
(atlas, references)
}
pub(crate) const PATCH_TILE: usize = 16;
pub(crate) const PATCH_REF_ID: u32 = 3;
pub(crate) const MODULAR_PATCH_REF_ID: u32 = 2;
pub(crate) const NUM_PATCH_CONTEXTS: usize = 10;
#[derive(Clone)]
pub(crate) struct PatchReference {
pub(crate) atlas_x: usize,
pub(crate) atlas_y: usize,
pub(crate) width: usize,
pub(crate) height: usize,
pub(crate) ref_frame: u32,
pub(crate) add: bool,
pub(crate) positions: Vec<(usize, usize)>,
}
pub(crate) struct LosslessPatches {
pub(crate) atlas: Image3Si,
pub(crate) base: Image3Si,
pub(crate) references: Vec<PatchReference>,
}
#[derive(Clone, Copy)]
pub(crate) enum ModularFrameKind<'a> {
Regular,
ReferenceOnly {
width: usize,
height: usize,
},
XybReferenceOnly {
width: usize,
height: usize,
},
Patched(&'a [PatchReference]),
}
impl ModularFrameKind<'_> {
pub(crate) fn is_regular(self) -> bool {
matches!(self, Self::Regular)
}
pub(crate) fn allows_learned_tree(self) -> bool {
true
}
}
fn hash_lossless_tile(linear: &Image3Si, x0: usize, y0: usize) -> u64 {
let mut h: u64 = 0x9e37_79b9_7f4a_7c15;
for c in 0..3 {
for y in y0..y0 + PATCH_TILE {
let row = &linear.plane_row(c, y)[x0..x0 + PATCH_TILE];
for pair in row.as_chunks::<2>().0 {
let v = u64::from(pair[0] as u32) | (u64::from(pair[1] as u32) << 32);
h = (h ^ v).wrapping_mul(0xff51_afd7_ed55_8ccd);
h ^= h >> 29;
}
}
}
h
}
pub(crate) fn find_lossless_patches(
linear: &Image3Si,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<LosslessPatches> {
let width = linear.xsize();
let height = linear.ysize();
if width < PATCH_TILE || height < PATCH_TILE {
return None;
}
let tiles_x = width / PATCH_TILE;
let tiles_y = height / PATCH_TILE;
let rows = pool.steal_map(scratch, tiles_y, |ty, _scratch| {
(0..tiles_x)
.map(|tx| hash_lossless_tile(linear, tx * PATCH_TILE, ty * PATCH_TILE))
.collect::<Vec<u64>>()
});
let mut buckets: HashMap<u64, Vec<(usize, usize)>> =
HashMap::with_capacity(tiles_x.saturating_mul(tiles_y));
for (ty, row) in rows.into_iter().enumerate() {
for (tx, hash) in row.into_iter().enumerate() {
buckets
.entry(hash)
.or_default()
.push((tx * PATCH_TILE, ty * PATCH_TILE));
}
}
let mut groups: Vec<Vec<(usize, usize)>> = Vec::new();
for candidates in buckets.into_values() {
if candidates.len() < 3 {
continue;
}
let mut exact_groups: Vec<Vec<(usize, usize)>> = Vec::new();
for pos in candidates {
let mut matching = None;
for (i, group) in exact_groups.iter().enumerate() {
let a = group[0];
let equal = (0..3).all(|c| {
(0..PATCH_TILE).all(|dy| {
linear.plane_row(c, a.1 + dy)[a.0..a.0 + PATCH_TILE]
== linear.plane_row(c, pos.1 + dy)[pos.0..pos.0 + PATCH_TILE]
})
});
if equal {
matching = Some(i);
break;
}
}
if let Some(i) = matching {
exact_groups[i].push(pos);
} else {
exact_groups.push(vec![pos]);
}
}
groups.extend(exact_groups.into_iter().filter(|g| g.len() >= 3));
}
sort_patch_groups(&mut groups);
groups.truncate(256);
if groups.is_empty() {
return None;
}
let atlas_cols = groups.len().min(16);
let atlas_rows = groups.len().div_ceil(atlas_cols);
let atlas_width = atlas_cols * PATCH_TILE;
let atlas_height = atlas_rows * PATCH_TILE;
let mut atlas = Image3Si::new(atlas_width, atlas_height);
let mut base = linear.clone();
let mut references = Vec::with_capacity(groups.len());
for (i, positions) in groups.into_iter().enumerate() {
let atlas_x = (i % atlas_cols) * PATCH_TILE;
let atlas_y = (i / atlas_cols) * PATCH_TILE;
let src = positions[0];
for c in 0..3 {
for dy in 0..PATCH_TILE {
atlas.plane_row_mut(c, atlas_y + dy)[atlas_x..atlas_x + PATCH_TILE]
.copy_from_slice(&linear.plane_row(c, src.1 + dy)[src.0..src.0 + PATCH_TILE]);
for &(x, y) in &positions {
base.plane_row_mut(c, y + dy)[x..x + PATCH_TILE].fill(0);
}
}
}
references.push(PatchReference {
width: PATCH_TILE,
height: PATCH_TILE,
atlas_x,
atlas_y,
ref_frame: PATCH_REF_ID,
add: false,
positions,
});
}
Some(LosslessPatches {
atlas,
base,
references,
})
}
const GLYPH_MAX_SIDE: usize = 64;
const GLYPH_BG_TILE: usize = 32;
const GLYPH_MIN_REPEAT_PIXELS: usize = 48;
const GLYPH_ATLAS_MAX_WIDTH: usize = 1024;
const GLYPH_KEY_BIAS: i64 = 1 << 20;
const GLYPH_KEY_MASK: u64 = (1 << 21) - 1;
#[inline]
fn color_key(c0: i32, c1: i32, c2: i32) -> u64 {
let f = |v: i32| ((v as i64 + GLYPH_KEY_BIAS) as u64) & GLYPH_KEY_MASK;
f(c0) << 42 | f(c1) << 21 | f(c2)
}
#[inline]
fn key_color(key: u64) -> [i32; 3] {
let f = |shift: u32| ((key >> shift) & GLYPH_KEY_MASK) as i64 - GLYPH_KEY_BIAS;
[f(42) as i32, f(21) as i32, f(0) as i32]
}
fn most_frequent_color(keys: &mut [u64]) -> u64 {
keys.sort_unstable();
let (mut best, mut best_run) = (keys[0], 0);
for run in keys.chunk_by(|a, b| a == b) {
if run.len() > best_run {
best = run[0];
best_run = run.len();
}
}
best
}
pub(crate) fn find_lossless_glyph_patches(linear: &Image3Si) -> Option<LosslessPatches> {
let width = linear.xsize();
let height = linear.ysize();
if width < GLYPH_BG_TILE || height < GLYPH_BG_TILE {
return None;
}
let tiles_x = width.div_ceil(GLYPH_BG_TILE);
let tiles_y = height.div_ceil(GLYPH_BG_TILE);
let mut modes = vec![0u64; tiles_x * tiles_y];
let mut keys: Vec<u64> = Vec::with_capacity(GLYPH_BG_TILE * GLYPH_BG_TILE);
for (ty, mode_row) in modes.chunks_exact_mut(tiles_x).enumerate() {
for (tx, mode) in mode_row.iter_mut().enumerate() {
let x0 = tx * GLYPH_BG_TILE;
let x1 = (x0 + GLYPH_BG_TILE).min(width);
keys.clear();
for y in ty * GLYPH_BG_TILE..((ty + 1) * GLYPH_BG_TILE).min(height) {
let c0 = &linear.plane_row(0, y)[x0..x1];
let c1 = &linear.plane_row(1, y)[x0..x1];
let c2 = &linear.plane_row(2, y)[x0..x1];
keys.extend(
c0.iter()
.zip(c1)
.zip(c2)
.map(|((&a, &b), &c)| color_key(a, b, c)),
);
}
*mode = most_frequent_color(&mut keys);
}
}
let mut ink = vec![false; width * height];
for (ty, band) in ink.chunks_mut(width * GLYPH_BG_TILE).enumerate() {
let ny0 = ty.saturating_sub(1);
let ny1 = (ty + 2).min(tiles_y);
let neighbors = &modes[ny0 * tiles_x..ny1 * tiles_x];
for tx in 0..tiles_x {
let nx0 = tx.saturating_sub(1);
let nx1 = (tx + 2).min(tiles_x);
let mut backgrounds = [0; 9];
let mut num_backgrounds = 0;
for row in neighbors.chunks_exact(tiles_x) {
for &key in &row[nx0..nx1] {
if !backgrounds[..num_backgrounds].contains(&key) {
backgrounds[num_backgrounds] = key;
num_backgrounds += 1;
}
}
}
let backgrounds = &backgrounds[..num_backgrounds];
let x0 = tx * GLYPH_BG_TILE;
let x1 = (x0 + GLYPH_BG_TILE).min(width);
for (dy, row) in band.chunks_exact_mut(width).enumerate() {
let y = ty * GLYPH_BG_TILE + dy;
let c0 = &linear.plane_row(0, y)[x0..x1];
let c1 = &linear.plane_row(1, y)[x0..x1];
let c2 = &linear.plane_row(2, y)[x0..x1];
for (((pixel, &a), &b), &c) in row[x0..x1].iter_mut().zip(c0).zip(c1).zip(c2) {
*pixel = !backgrounds.contains(&color_key(a, b, c));
}
}
}
}
struct Shape {
x0: usize,
y0: usize,
w: usize,
h: usize,
hash: u64,
}
let mut shapes: Vec<Shape> = Vec::new();
let mut stack: Vec<(usize, usize)> = Vec::new();
let mut next_pixel = 0;
while let Some(offset) = ink[next_pixel..].iter().position(|&pixel| pixel) {
let index = next_pixel + offset;
next_pixel = index + 1;
let (x, y) = (index % width, index / width);
let (mut x0, mut x1, mut y0, mut y1) = (x, x, y, y);
let mut count = 0usize;
stack.push((x, y));
ink[index] = false;
while let Some((cx, cy)) = stack.pop() {
count += 1;
x0 = x0.min(cx);
x1 = x1.max(cx);
y0 = y0.min(cy);
y1 = y1.max(cy);
let nx0 = cx.saturating_sub(1);
let nx1 = (cx + 2).min(width);
let ny0 = cy.saturating_sub(1);
let ny1 = (cy + 2).min(height);
for (dy, row) in ink[ny0 * width..ny1 * width]
.chunks_exact_mut(width)
.enumerate()
{
for (dx, pixel) in row[nx0..nx1].iter_mut().enumerate() {
if *pixel {
*pixel = false;
stack.push((nx0 + dx, ny0 + dy));
}
}
}
}
let (w, h) = (x1 - x0 + 1, y1 - y0 + 1);
if count < 2 || w > GLYPH_MAX_SIDE || h > GLYPH_MAX_SIDE {
continue;
}
let mut hash: u64 = 0x9e37_79b9_7f4a_7c15 ^ ((w as u64) << 32 | h as u64);
for c in 0..3 {
for row in linear.plane_data(c)[y0 * width..(y1 + 1) * width].chunks_exact(width) {
for &v in &row[x0..=x1] {
hash = (hash ^ (v as u32 as u64)).wrapping_mul(0xff51_afd7_ed55_8ccd);
hash ^= hash >> 29;
}
}
}
shapes.push(Shape { x0, y0, w, h, hash });
}
if shapes.len() < 4 {
return None;
}
let same_box = |a: &Shape, b: &Shape| -> bool {
a.w == b.w
&& a.h == b.h
&& (0..3).all(|c| {
let plane = linear.plane_data(c);
let a_rows = plane[a.y0 * width..(a.y0 + a.h) * width].chunks_exact(width);
let b_rows = plane[b.y0 * width..(b.y0 + b.h) * width].chunks_exact(width);
a_rows
.zip(b_rows)
.all(|(ar, br)| ar[a.x0..a.x0 + a.w] == br[b.x0..b.x0 + b.w])
})
};
struct ShapeGroup<'a> {
shape: &'a Shape,
positions: Vec<(usize, usize)>,
}
let mut buckets: HashMap<u64, Vec<ShapeGroup<'_>>> = HashMap::new();
for s in &shapes {
let groups = buckets.entry(s.hash).or_default();
match groups.iter_mut().find(|g| same_box(g.shape, s)) {
Some(g) => g.positions.push((s.x0, s.y0)),
None => groups.push(ShapeGroup {
shape: s,
positions: vec![(s.x0, s.y0)],
}),
}
}
let mut groups: Vec<_> = buckets
.into_values()
.flatten()
.filter(|g| {
let s = g.shape;
g.positions.len() >= 2 && (g.positions.len() - 1) * s.w * s.h >= GLYPH_MIN_REPEAT_PIXELS
})
.collect();
if groups.len() < 2 {
return None;
}
let (covered, total_area, max_width) =
groups.iter().fold((0, 0, 0), |(covered, area, w), g| {
let s = g.shape;
(
covered + g.positions.len() * s.w * s.h,
area + s.w * s.h,
w.max(s.w),
)
});
if covered * 200 < width * height {
return None;
}
groups.sort_by_key(|g| {
let s = g.shape;
(
std::cmp::Reverse(s.h),
std::cmp::Reverse((g.positions.len() - 1) * s.w * s.h),
s.y0,
s.x0,
)
});
let atlas_width = ((total_area as f64).sqrt() as usize * 3 / 2)
.max(max_width)
.clamp(16, GLYPH_ATLAS_MAX_WIDTH);
let mut slots: Vec<(usize, usize)> = Vec::with_capacity(groups.len());
let (mut cx, mut cy, mut shelf_h) = (0usize, 0usize, 0usize);
for g in &groups {
let s = g.shape;
if cx + s.w > atlas_width {
cx = 0;
cy += shelf_h;
shelf_h = 0;
}
slots.push((cx, cy));
cx += s.w;
shelf_h = shelf_h.max(s.h);
}
let atlas_height = cy + shelf_h;
let mut atlas = Image3Si::try_new(atlas_width, atlas_height).ok()?;
keys.clear();
keys.extend_from_slice(&modes);
let fill = key_color(most_frequent_color(&mut keys));
for (c, value) in fill.into_iter().enumerate() {
atlas.plane_mut(c).as_mut_slice().fill(value);
}
let mut base = linear.clone();
let mut references = Vec::with_capacity(groups.len());
for (g, (ax, ay)) in groups.into_iter().zip(slots) {
let s = g.shape;
for c in 0..3 {
let src = &linear.plane_data(c)[s.y0 * width..(s.y0 + s.h) * width];
let dst =
&mut atlas.plane_mut(c).as_mut_slice()[ay * atlas_width..(ay + s.h) * atlas_width];
for (dst_row, src_row) in dst
.chunks_exact_mut(atlas_width)
.zip(src.chunks_exact(width))
{
dst_row[ax..ax + s.w].copy_from_slice(&src_row[s.x0..s.x0 + s.w]);
}
}
for &(px, py) in &g.positions {
let fill = key_color(modes[(py / GLYPH_BG_TILE) * tiles_x + px / GLYPH_BG_TILE]);
for (c, value) in fill.into_iter().enumerate() {
let rows = &mut base.plane_mut(c).as_mut_slice()[py * width..(py + s.h) * width];
for row in rows.chunks_exact_mut(width) {
row[px..px + s.w].fill(value);
}
}
}
let mut positions = g.positions;
positions.sort_unstable_by_key(|&(x, y)| (y, x));
references.push(PatchReference {
atlas_x: ax,
atlas_y: ay,
width: s.w,
height: s.h,
ref_frame: PATCH_REF_ID,
add: false,
positions,
});
}
Some(LosslessPatches {
atlas,
base,
references,
})
}
const GLYPH_MAX_INK_SHARE: f64 = 0.6;
const GLYPH_SCREEN_STRIDE: usize = 64;
const GLYPH_SCREEN_MAX_INK: f64 = 0.6;
const GLYPH_ATLAS_MAX_HEIGHT: usize = 4096;
pub(crate) struct LossyGlyphPatches {
pub(crate) atlas: [Vec<i32>; 3],
pub(crate) atlas_width: usize,
pub(crate) atlas_height: usize,
pub(crate) base: Image3F,
pub(crate) references: Vec<PatchReference>,
}
pub(crate) struct GlyphParams {
pub(crate) min_occurrences: usize,
pub(crate) min_repeat_pixels: usize,
pub(crate) coarse: i32,
}
const GLYPH_MIN_COVER: f64 = 0.005;
pub(crate) fn find_lossy_glyph_patches(
xyb: &Image3F,
params: &GlyphParams,
) -> Option<LossyGlyphPatches> {
use crate::quant_weights::INV_DC_QUANT;
let (width, height) = (xyb.xsize(), xyb.ysize());
let bg_tile = GLYPH_BG_TILE;
if width < bg_tile || height < bg_tile {
return None;
}
{
let mut colors = [[0i32; 3]; PATCH_TILE * PATCH_TILE];
let mut sample_keys = [0u64; PATCH_TILE * PATCH_TILE];
let (mut ink, mut total) = (0usize, 0usize);
for y0 in (0..height.saturating_sub(PATCH_TILE)).step_by(GLYPH_SCREEN_STRIDE) {
for x0 in (0..width.saturating_sub(PATCH_TILE)).step_by(GLYPH_SCREEN_STRIDE) {
crate::xyb::quantize_xyb_tile_colors(xyb, x0, y0, 1, &mut colors);
let k = [params.coarse; 3];
for (key, c) in sample_keys.iter_mut().zip(&colors) {
let r = |v: i32, k: i32| (v as f32 / k as f32).round() as i32 * k;
*key = color_key(r(c[0], k[0]), r(c[1], k[1]), r(c[2] + c[0], k[2]));
}
let mut sorted = sample_keys;
let mode = most_frequent_color(&mut sorted);
ink += sample_keys.iter().filter(|&&key| key != mode).count();
total += sample_keys.len();
}
}
if ink as f64 > GLYPH_SCREEN_MAX_INK * total as f64 {
return None;
}
}
let [qy, qx, mut qb] = crate::xyb::quantize_xyb_channels(xyb, 1);
let (mut qy, mut qx) = (qy, qx);
for (b, &y) in qb.iter_mut().zip(&qy) {
*b += y;
}
for (plane, k) in [&mut qy, &mut qx, &mut qb]
.into_iter()
.zip([params.coarse; 3])
{
if k > 1 {
for v in plane.iter_mut() {
*v = (*v as f32 / k as f32).round() as i32 * k;
}
}
}
let planes = [&qy, &qx, &qb];
let keys: Vec<u64> = (0..width * height)
.map(|i| color_key(qy[i], qx[i], qb[i]))
.collect();
let tiles_x = width.div_ceil(bg_tile);
let tiles_y = height.div_ceil(bg_tile);
let mut modes = vec![0u64; tiles_x * tiles_y];
let mut tile_keys: Vec<u64> = Vec::with_capacity(bg_tile * bg_tile);
let band_len = width * bg_tile;
for (band, mode_row) in keys.chunks(band_len).zip(modes.chunks_exact_mut(tiles_x)) {
for (tx, mode) in mode_row.iter_mut().enumerate() {
let x0 = tx * bg_tile;
let x1 = (x0 + bg_tile).min(width);
tile_keys.clear();
tile_keys.extend(band.chunks_exact(width).flat_map(|row| &row[x0..x1]));
*mode = most_frequent_color(&mut tile_keys);
}
}
let mut ink = vec![false; width * height];
for (ty, (ink_band, key_band)) in ink
.chunks_mut(band_len)
.zip(keys.chunks(band_len))
.enumerate()
{
let neighbor_rows = &modes[ty.saturating_sub(1) * tiles_x..(ty + 2).min(tiles_y) * tiles_x];
for tx in 0..tiles_x {
let (nx0, nx1) = (tx.saturating_sub(1), (tx + 2).min(tiles_x));
let mut backgrounds = [0u64; 9];
let mut n = 0;
for &key in neighbor_rows
.chunks_exact(tiles_x)
.flat_map(|row| &row[nx0..nx1])
{
if !backgrounds[..n].contains(&key) {
backgrounds[n] = key;
n += 1;
}
}
let backgrounds = &backgrounds[..n];
let x0 = tx * bg_tile;
let x1 = (x0 + bg_tile).min(width);
for (ink_row, key_row) in ink_band
.chunks_exact_mut(width)
.zip(key_band.chunks_exact(width))
{
for (pixel, key) in ink_row[x0..x1].iter_mut().zip(&key_row[x0..x1]) {
*pixel = !backgrounds.contains(key);
}
}
}
}
let ink_pixels = ink.iter().filter(|&&p| p).count();
if ink_pixels as f64 > GLYPH_MAX_INK_SHARE * (width * height) as f64 {
return None;
}
struct Shape {
x0: usize,
y0: usize,
w: usize,
h: usize,
label: u32,
bg: [i32; 3],
hash: u64,
}
let mut label = vec![0u32; width * height];
let mut shapes: Vec<Shape> = Vec::new();
let mut stack: Vec<(usize, usize)> = Vec::new();
let mut next_label = 0u32;
let mut next_pixel = 0;
while let Some(offset) = ink[next_pixel..]
.iter()
.zip(&label[next_pixel..])
.position(|(&pixel, &owner)| pixel && owner == 0)
{
let start = next_pixel + offset;
next_pixel = start + 1;
next_label += 1;
let (x, y) = (start % width, start / width);
let (mut x0, mut x1, mut y0, mut y1) = (x, x, y, y);
let mut count = 0usize;
let mut bg_key: Option<u64> = None;
let mut one_bg = true;
stack.push((x, y));
label[start] = next_label;
while let Some((cx, cy)) = stack.pop() {
count += 1;
x0 = x0.min(cx);
x1 = x1.max(cx);
y0 = y0.min(cy);
y1 = y1.max(cy);
let (nx0, nx1) = (cx.saturating_sub(1), (cx + 2).min(width));
let (ny0, ny1) = (cy.saturating_sub(1), (cy + 2).min(height));
let window = ny0 * width..ny1 * width;
let rows = ink[window.clone()]
.chunks_exact(width)
.zip(label[window.clone()].chunks_exact_mut(width))
.zip(keys[window].chunks_exact(width));
for (dy, ((ink_row, label_row), key_row)) in rows.enumerate() {
let pixels = ink_row[nx0..nx1]
.iter()
.zip(&mut label_row[nx0..nx1])
.zip(&key_row[nx0..nx1]);
for (dx, ((&is_ink, owner), &key)) in pixels.enumerate() {
if is_ink {
if *owner == 0 {
*owner = next_label;
stack.push((nx0 + dx, ny0 + dy));
}
} else {
match bg_key {
None => bg_key = Some(key),
Some(k) => one_bg &= k == key,
}
}
}
}
}
let (w, h) = (x1 - x0 + 1, y1 - y0 + 1);
let Some(bg_key) = bg_key else { continue };
if !one_bg || count < 2 || w > GLYPH_MAX_SIDE || h > GLYPH_MAX_SIDE {
continue;
}
let bg = key_color(bg_key);
let mut hash: u64 = 0x9e37_79b9_7f4a_7c15 ^ ((w as u64) << 32 | h as u64);
let rows = y0 * width..(y1 + 1) * width;
for (plane, &bg) in planes.iter().zip(&bg) {
let plane_rows = plane[rows.clone()].chunks_exact(width);
let label_rows = label[rows.clone()].chunks_exact(width);
for (values, owners) in plane_rows.zip(label_rows) {
for (&value, &owner) in values[x0..=x1].iter().zip(&owners[x0..=x1]) {
let v = if owner == next_label { value - bg } else { 0 };
hash = (hash ^ (v as u32 as u64)).wrapping_mul(0xff51_afd7_ed55_8ccd);
hash ^= hash >> 29;
}
}
}
shapes.push(Shape {
x0,
y0,
w,
h,
label: next_label,
bg,
hash,
});
}
if shapes.len() < 4 {
return None;
}
let diff = |s: &Shape, c: usize, dx: usize, dy: usize| -> i32 {
let i = (s.y0 + dy) * width + s.x0 + dx;
if label[i] == s.label {
planes[c][i] - s.bg[c]
} else {
0
}
};
let same = |a: &Shape, b: &Shape| -> bool {
a.w == b.w
&& a.h == b.h
&& (0..3).all(|c| {
(0..a.h).all(|dy| (0..a.w).all(|dx| diff(a, c, dx, dy) == diff(b, c, dx, dy)))
})
};
let mut buckets: HashMap<u64, Vec<Vec<usize>>> = HashMap::new();
for (i, s) in shapes.iter().enumerate() {
let groups = buckets.entry(s.hash).or_default();
match groups.iter_mut().find(|g| same(&shapes[g[0]], s)) {
Some(g) => g.push(i),
None => groups.push(vec![i]),
}
}
let mut groups: Vec<Vec<usize>> = buckets
.into_values()
.flatten()
.filter(|g| {
let s = &shapes[g[0]];
g.len() >= params.min_occurrences
&& (g.len().max(2) - 1) * s.w * s.h >= params.min_repeat_pixels
})
.collect();
if groups.len() < 2 {
return None;
}
groups.sort_by_key(|g| {
let s = &shapes[g[0]];
(std::cmp::Reverse(g.len() * s.w * s.h), s.y0, s.x0)
});
let budget = GLYPH_ATLAS_MAX_WIDTH * GLYPH_ATLAS_MAX_HEIGHT * 3 / 4;
let mut area = 0usize;
let keep = groups
.iter()
.take_while(|g| {
let s = &shapes[g[0]];
area += s.w * s.h;
area <= budget
})
.count();
groups.truncate(keep);
let (covered, total_area, max_width) = groups.iter().fold((0, 0, 0), |(cv, ar, mw), g| {
let s = &shapes[g[0]];
(cv + g.len() * s.w * s.h, ar + s.w * s.h, mw.max(s.w))
});
if (covered as f64) < GLYPH_MIN_COVER * (width * height) as f64 {
return None;
}
groups.sort_by_key(|g| {
let s = &shapes[g[0]];
(
std::cmp::Reverse(s.h),
std::cmp::Reverse(g.len() * s.w * s.h),
s.y0,
s.x0,
)
});
let atlas_width = ((total_area as f64).sqrt() as usize * 3 / 2)
.max(max_width)
.clamp(16, GLYPH_ATLAS_MAX_WIDTH);
let mut slots: Vec<(usize, usize)> = Vec::with_capacity(groups.len());
let (mut cx, mut cy, mut shelf_h) = (0usize, 0usize, 0usize);
for g in &groups {
let s = &shapes[g[0]];
if cx + s.w > atlas_width {
cx = 0;
cy += shelf_h;
shelf_h = 0;
}
slots.push((cx, cy));
cx += s.w;
shelf_h = shelf_h.max(s.h);
}
let atlas_height = cy + shelf_h;
if atlas_height > GLYPH_ATLAS_MAX_HEIGHT {
return None;
}
let mut atlas = [
vec![0i32; atlas_width * atlas_height],
vec![0i32; atlas_width * atlas_height],
vec![0i32; atlas_width * atlas_height],
];
let steps = [
1.0 / INV_DC_QUANT[1],
1.0 / INV_DC_QUANT[0],
1.0 / INV_DC_QUANT[2],
];
let image_plane = [1usize, 0, 2];
let mut base = xyb.clone();
let mut references = Vec::with_capacity(groups.len());
for (g, (ax, ay)) in groups.into_iter().zip(slots) {
let s = &shapes[g[0]];
for dy in 0..s.h {
for dx in 0..s.w {
let at = (ay + dy) * atlas_width + ax + dx;
let d = [diff(s, 0, dx, dy), diff(s, 1, dx, dy), diff(s, 2, dx, dy)];
atlas[0][at] = d[0];
atlas[1][at] = d[1];
atlas[2][at] = d[2] - d[0];
}
}
let mut positions = Vec::with_capacity(g.len());
for &i in &g {
let o = &shapes[i];
positions.push((o.x0, o.y0));
for c in 0..3 {
for dy in 0..o.h {
let row = base.plane_row_mut(image_plane[c], o.y0 + dy);
for dx in 0..o.w {
let d = diff(o, c, dx, dy);
if d != 0 {
row[o.x0 + dx] -= d as f32 * steps[c];
}
}
}
}
}
positions.sort_unstable_by_key(|&(x, y)| (y, x));
references.push(PatchReference {
atlas_x: ax,
atlas_y: ay,
width: s.w,
height: s.h,
ref_frame: MODULAR_PATCH_REF_ID,
add: true,
positions,
});
}
Some(LossyGlyphPatches {
atlas,
atlas_width,
atlas_height,
base,
references,
})
}
fn sort_patch_groups(groups: &mut [Vec<(usize, usize)>]) {
groups.sort_by_key(|g| (std::cmp::Reverse(g.len()), g[0]));
}
#[cfg(test)]
mod tests {
use super::*;
fn assert_glyph_reconstruction(img: &Image3Si, plan: &LosslessPatches) {
let mut restored = plan.base.clone();
for r in &plan.references {
for &(x, y) in &r.positions {
for c in 0..3 {
for dy in 0..r.height {
restored.plane_row_mut(c, y + dy)[x..x + r.width].copy_from_slice(
&plan.atlas.plane_row(c, r.atlas_y + dy)
[r.atlas_x..r.atlas_x + r.width],
);
}
}
}
}
for c in 0..3 {
assert_eq!(restored.plane_data(c), img.plane_data(c));
}
}
#[test]
fn glyph_patches_preserve_signed_pixels_at_image_and_tile_edges() {
let mut img = Image3Si::new(131, 99);
let background = [-17, 255, -(1 << 20)];
for (c, value) in background.into_iter().enumerate() {
img.plane_mut(c).as_mut_slice().fill(value);
}
let diagonals = [(0, 0), (29, 25), (124, 92)];
let corners = [(126, 0), (61, 59), (0, 90)];
for (c, value) in [-(1 << 20), (1 << 20) - 1, 0].into_iter().enumerate() {
for &(x, y) in &diagonals {
for d in 0..7 {
img.plane_row_mut(c, y + d)[x + d] = value;
}
}
for &(x, y) in &corners {
for dy in 0..9 {
img.plane_row_mut(c, y + dy)[x] = value;
}
img.plane_row_mut(c, y + 8)[x..x + 5].fill(value);
}
}
let plan = find_lossless_glyph_patches(&img).expect("two repeated glyphs");
assert_eq!(plan.references.len(), 2);
for r in &plan.references {
match (r.width, r.height) {
(7, 7) => assert_eq!(r.positions, diagonals),
(5, 9) => assert_eq!(r.positions, corners),
dimensions => panic!("unexpected glyph box: {dimensions:?}"),
}
}
for (c, value) in background.into_iter().enumerate() {
assert!(plan.base.plane_data(c).iter().all(|&v| v == value));
}
assert_glyph_reconstruction(&img, &plan);
}
#[test]
fn glyph_patches_preserve_neighboring_background_colors() {
let mut img = Image3Si::new(99, 99);
for c in 0..3 {
for y in 0..img.ysize() {
for (x, pixel) in img.plane_row_mut(c, y).iter_mut().enumerate() {
*pixel = ((y / 32).min(2) * 3 + (x / 32).min(2) + c * 10) as i32;
}
}
}
for (w, h, positions) in [
(5, 7, [(2, 3), (35, 4), (69, 5)]),
(3, 9, [(3, 68), (36, 69), (70, 70)]),
] {
for (x, y) in positions {
for c in 0..3 {
for dy in 0..h {
img.plane_row_mut(c, y + dy)[x..x + w].fill(-100 - c as i32);
}
}
}
}
for (x, y) in [(35, 35), (49, 49)] {
for c in 0..3 {
for dy in 0..7 {
img.plane_row_mut(c, y + dy)[x..x + 5].fill((c * 10) as i32);
}
}
}
let plan = find_lossless_glyph_patches(&img).expect("two repeated glyphs");
assert_eq!(plan.references.len(), 2);
assert!(plan.references.iter().all(|r| r.positions.len() == 3));
assert_glyph_reconstruction(&img, &plan);
}
fn glyph_params(min_occurrences: usize) -> GlyphParams {
GlyphParams {
min_occurrences,
min_repeat_pixels: 0,
coarse: 1,
}
}
fn glyph_page() -> Image3F {
let (w, h) = (192usize, 128usize);
let mut img = Image3F::new(w, h);
for y in 0..h {
let bg = if y < 64 {
[4.0f32 / 4096.0, 307.0 / 512.0, 140.0 / 256.0]
} else {
[-8.0 / 4096.0, 102.0 / 512.0, 64.0 / 256.0]
};
for (c, &value) in bg.iter().enumerate() {
img.plane_row_mut(c, y)[..w].fill(value);
}
}
let mut stamp = |x0: usize, y0: usize, w: usize, h: usize, unit: f32| {
for dy in 0..h {
for dx in 0..w {
let ink = ((dx * 3 + dy * 5 + w) % 4) as f32 * unit;
img.plane_row_mut(1, y0 + dy)[x0 + dx] -= ink * 16.0 / 512.0;
img.plane_row_mut(2, y0 + dy)[x0 + dx] -= ink * 4.0 / 256.0;
img.plane_row_mut(0, y0 + dy)[x0 + dx] += ink * 2.0 / 4096.0;
}
}
};
for &(x, y) in &[(3, 5), (41, 9), (77, 22), (130, 37), (11, 75), (99, 101)] {
stamp(x, y, 5, 7, 2.0);
}
for &(x, y) in &[(20, 40), (160, 12), (60, 90), (140, 110)] {
stamp(x, y, 4, 4, 2.0);
}
stamp(150, 80, 6, 6, 1.0);
img
}
fn assert_glyph_plan_reconstructs(img: &Image3F, plan: &LossyGlyphPatches) {
use crate::quant_weights::INV_DC_QUANT;
let mut recon = plan.base.clone();
let [ay, ax, ab] = &plan.atlas;
for r in &plan.references {
assert!(r.add);
for &(px, py) in &r.positions {
for dy in 0..r.height {
for dx in 0..r.width {
let at = (r.atlas_y + dy) * plan.atlas_width + r.atlas_x + dx;
recon.plane_row_mut(1, py + dy)[px + dx] += ay[at] as f32 / INV_DC_QUANT[1];
recon.plane_row_mut(0, py + dy)[px + dx] += ax[at] as f32 / INV_DC_QUANT[0];
recon.plane_row_mut(2, py + dy)[px + dx] +=
(ab[at] + ay[at]) as f32 / INV_DC_QUANT[2];
}
}
}
}
for c in 0..3 {
for y in 0..img.ysize() {
for (a, b) in img.plane_row(c, y)[..img.xsize()]
.iter()
.zip(&recon.plane_row(c, y)[..img.xsize()])
{
assert!((a - b).abs() < 1e-5, "plane {c} row {y}: {a} vs {b}");
}
}
}
}
#[test]
fn lossy_glyph_patches_reconstruct_and_flatten_the_base() {
let img = glyph_page();
let repeated = find_lossy_glyph_patches(&img, &glyph_params(2)).expect("plan");
assert_eq!(repeated.references.len(), 2);
let mut counts: Vec<usize> = repeated
.references
.iter()
.map(|r| r.positions.len())
.collect();
counts.sort_unstable();
assert_eq!(counts, [4, 6]);
assert_glyph_plan_reconstructs(&img, &repeated);
let step = 1.0 / crate::quant_weights::INV_DC_QUANT[1];
assert!((repeated.base.plane_row(1, 8)[5] - 307.0 / 512.0).abs() <= step);
let all = find_lossy_glyph_patches(&img, &glyph_params(1)).expect("plan");
assert_eq!(all.references.len(), 3);
assert_glyph_plan_reconstructs(&img, &all);
}
#[test]
fn near_tiles_join_within_the_tolerance_only() {
let pool = ThreadPool::new(2);
let mut scratch = CoderScratch::default();
let tile = PATCH_TILE;
let mut img = Image3F::new(8 * tile, 2 * tile);
let mut state = 7u32;
let mut proto = vec![0f32; tile * tile];
for v in proto.iter_mut() {
state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
*v = (state >> 24) as f32 / 255.0 * 0.5;
}
for ty in 0..2 {
for tx in 0..8 {
for dy in 0..tile {
for dx in 0..tile {
state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
let noise = (state >> 24) as f32 / 255.0 * 0.5;
let value = if ty == 0 && tx < 6 {
proto[dy * tile + dx]
+ if tx >= 3 && (dx + dy) % 2 == 0 {
NEAR_TILE_UNIT[1] / 3.0
} else {
0.0
}
} else {
noise
};
img.plane_row_mut(1, ty * tile + dy)[tx * tile + dx] = value;
img.plane_row_mut(2, ty * tile + dy)[tx * tile + dx] = value;
}
}
}
}
assert!(find_lossy_patches_sized(&img, tile, 0.0, &pool, &mut scratch).is_none());
let plan = find_lossy_patches_sized(&img, tile, 1.0, &pool, &mut scratch).expect("near");
assert_eq!(plan.groups.len(), 1);
assert_eq!(plan.groups[0].len(), 6);
assert_eq!(plan.groups[0][0], (0, 0));
for _ in 0..4 {
let again =
find_lossy_patches_sized(&img, tile, 1.0, &pool, &mut scratch).expect("near");
assert_eq!(again.groups, plan.groups);
}
img.plane_row_mut(1, 3)[5 * tile + 3] += NEAR_TILE_UNIT[1] * 2.0;
let plan = find_lossy_patches_sized(&img, tile, 1.0, &pool, &mut scratch).expect("near");
assert_eq!(plan.groups[0].len(), 5);
}
fn equal_length_groups() -> Image3F {
let tile = PATCH_TILE;
let (cols, rows) = (6usize, 6usize);
let mut img = Image3F::new(cols * tile, rows * tile);
for ty in 0..rows {
for tx in 0..cols {
for c in 0..3 {
for dy in 0..tile {
let row = img.plane_row_mut(c, ty * tile + dy);
for dx in 0..tile {
row[tx * tile + dx] = ((tx * 31 + dy * 3 + dx + c) % 17) as f32 / 17.0;
}
}
}
}
}
img
}
fn equal_length_lossless_groups() -> Image3Si {
let tile = PATCH_TILE;
let (cols, rows) = (6usize, 4usize);
let mut img = Image3Si::new(cols * tile, rows * tile);
for ty in 0..rows {
for tx in 0..cols {
for c in 0..3 {
for dy in 0..tile {
let row = img.plane_row_mut(c, ty * tile + dy);
for dx in 0..tile {
row[tx * tile + dx] = ((tx * 31 + dy * 3 + dx + c) % 17) as i32 - 8;
}
}
}
}
}
img
}
#[test]
fn equal_length_groups_get_a_stable_atlas_order() {
let pool = ThreadPool::new(4);
let mut scratch = CoderScratch::default();
let img = equal_length_groups();
let signature =
|p: &LossyPatches| -> Vec<(usize, usize)> { p.groups.iter().map(|g| g[0]).collect() };
let plan = find_lossy_patches(&img, &pool, &mut scratch).expect("groups");
let first = signature(&plan);
assert_eq!(first.len(), 6);
assert!(
first.windows(2).all(|w| w[0] < w[1]),
"groups must follow the first occurrence in raster order: {first:?}"
);
let (atlas, refs) = pack_lossy_atlas(&img, plan.groups, PATCH_REF_ID);
assert_eq!((atlas.xsize(), atlas.ysize()), (6 * PATCH_TILE, PATCH_TILE));
for (i, r) in refs.iter().enumerate() {
assert_eq!((r.atlas_x, r.atlas_y), (i * PATCH_TILE, 0));
assert_eq!(r.ref_frame, PATCH_REF_ID);
assert_eq!(r.positions[0], first[i]);
}
for _ in 0..4 {
let again = find_lossy_patches(&img, &pool, &mut scratch).expect("groups");
assert_eq!(first, signature(&again));
}
}
#[test]
fn lossless_patch_discovery_is_thread_deterministic() {
let img = equal_length_lossless_groups();
let run = |threads| {
let pool = ThreadPool::new(threads);
let mut scratch = CoderScratch::default();
find_lossless_patches(&img, &pool, &mut scratch).expect("groups")
};
let single = run(1);
let parallel = run(4);
assert_eq!(single.references.len(), 6);
assert_eq!(single.references.len(), parallel.references.len());
for (a, b) in single.references.iter().zip(¶llel.references) {
assert_eq!((a.atlas_x, a.atlas_y), (b.atlas_x, b.atlas_y));
assert_eq!(a.positions, b.positions);
}
for c in 0..3 {
assert_eq!(single.atlas.plane_data(c), parallel.atlas.plane_data(c));
assert_eq!(single.base.plane_data(c), parallel.base.plane_data(c));
}
}
}