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) -> 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].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) -> f32 {
let mut energy = 0.0;
for c in 0..3 {
let mut sum = 0.0;
for y in y0..y0 + PATCH_TILE {
sum += img.plane_row(c, y)[x0..x0 + PATCH_TILE].iter().sum::<f32>();
}
let mean = sum / (PATCH_TILE * PATCH_TILE) as f32;
for y in y0..y0 + PATCH_TILE {
energy += img.plane_row(c, y)[x0..x0 + PATCH_TILE]
.iter()
.map(|v| (v - mean).abs())
.sum::<f32>();
}
}
energy / (PATCH_TILE * PATCH_TILE) as f32
}
const MIN_PATCH_ENERGY: f32 = 0.017;
const MIN_PATCH_OCCURRENCES: usize = 5;
pub(crate) fn find_lossy_patches(
linear: &Image3F,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Option<LossyPatches> {
let tile = PATCH_TILE;
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))
.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();
for candidates in buckets.into_values() {
if candidates.len() < MIN_PATCH_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_PATCH_OCCURRENCES),
);
}
groups.retain(|g| tile_energy(linear, g[0].0, g[0].1) >= MIN_PATCH_ENERGY);
groups.sort_by_key(|g| (std::cmp::Reverse(g.len()), g[0]));
groups.truncate(256);
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>) {
let tile = PATCH_TILE;
let atlas_cols = groups.len().min(16);
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 {
atlas_x,
atlas_y,
ref_frame,
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) ref_frame: u32,
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 },
Patched(&'a [PatchReference]),
}
impl ModularFrameKind<'_> {
pub(crate) fn is_regular(self) -> bool {
matches!(self, Self::Regular)
}
}
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));
}
groups.sort_by_key(|g| (std::cmp::Reverse(g.len()), g[0]));
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 {
atlas_x,
atlas_y,
ref_frame: PATCH_REF_ID,
positions,
});
}
Some(LosslessPatches {
atlas,
base,
references,
})
}
#[cfg(test)]
mod tests {
use super::*;
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));
}
}
}