use crate::encode_image::AlphaPlane;
use crate::encoding_context::EncodingContext;
use crate::image::Image3F;
use msssim_lite::{GrayImage, PreparedReference, Rect};
const VIEW_SLACK: f64 = 1e-4;
pub(super) struct Incumbent {
luma_scale: f32,
views: Vec<PreparedReference>,
deficits: Vec<f64>,
}
#[derive(Default)]
pub(super) struct GateCache {
errors: std::sync::OnceLock<PlaneErrors>,
proxy: std::sync::OnceLock<Option<Incumbent>>,
#[cfg(feature = "extraslow")]
exact: std::sync::OnceLock<Option<ExactReference>>,
}
#[derive(Default)]
struct PlaneErrors {
squared: u64,
max: u8,
endpoints: usize,
}
fn plane_errors(source: &[u8], candidate: &[u8]) -> PlaneErrors {
let mut result = PlaneErrors::default();
const CHUNK: usize = 32768;
for (source, candidate) in source.chunks(CHUNK).zip(candidate.chunks(CHUNK)) {
let (mut squared, mut max, mut endpoints) = (0u32, 0u8, 0u32);
for (&s, &v) in source.iter().zip(candidate) {
let error = s.abs_diff(v);
squared += u32::from(error).pow(2);
max = max.max(error);
endpoints += u32::from(((s == 0) | (s == 255)) & (error != 0));
}
result.squared += u64::from(squared);
result.max = result.max.max(max);
result.endpoints += endpoints as usize;
}
result
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Gate {
Proxy,
#[cfg(feature = "extraslow")]
Exact,
}
impl Gate {
fn select(ctx: &EncodingContext) -> Self {
#[cfg(feature = "extraslow")]
if ctx.function_fields_exact {
return Self::Exact;
}
let _ = ctx;
Self::Proxy
}
}
#[cfg(test)]
pub(super) fn acceptable(
ctx: &EncodingContext,
color: &Image3F,
source: &AlphaPlane,
incumbent: &AlphaPlane,
candidate: &AlphaPlane,
with_residual: bool,
cache: &GateCache,
) -> bool {
score(
ctx,
color,
source,
incumbent,
candidate,
with_residual,
cache,
)
.is_some()
}
pub(super) fn score(
ctx: &EncodingContext,
color: &Image3F,
source: &AlphaPlane,
incumbent: &AlphaPlane,
candidate: &AlphaPlane,
with_residual: bool,
cache: &GateCache,
) -> Option<f64> {
let (AlphaPlane::U8(source), AlphaPlane::U8(incumbent), AlphaPlane::U8(candidate)) =
(source, incumbent, candidate)
else {
return None;
};
let (width, height) = (color.xsize(), color.ysize());
let pixels = width.checked_mul(height)?;
if source.len() != pixels || incumbent.len() != pixels || candidate.len() != pixels {
return None;
}
if candidate == incumbent {
return Some(f64::INFINITY);
}
let errors = plane_errors(source, candidate);
if errors.squared == 0 {
return Some(0.0);
}
let incumbent_errors = cache.errors.get_or_init(|| plane_errors(source, incumbent));
if errors.squared > incumbent_errors.squared {
return None;
}
if with_residual {
if errors.endpoints > incumbent_errors.endpoints {
return None;
}
} else if errors.max > incumbent_errors.max
|| errors.max > 2
|| errors.squared * 25 > pixels as u64 * 9
|| errors.endpoints != 0
{
return None;
}
let layout = Layout {
width,
height,
black: ctx.extra_black,
color,
};
let gate = Gate::select(ctx);
match gate {
Gate::Proxy => {
let reference = cache
.proxy
.get_or_init(|| {
let luma_scale = if ctx.extra_black {
1.0
} else {
source_luma_scale(ctx, color)
};
let views = layout.prepare(ctx, source, luma_scale)?;
let deficits = layout.deficits(ctx, &views, incumbent, luma_scale)?;
Some(Incumbent {
luma_scale,
views,
deficits,
})
})
.as_ref()?;
let deficits = local_rect(source, candidate, width, height)
.and_then(|rect| {
layout.patch_deficits(
ctx,
&reference.views,
candidate,
reference.luma_scale,
rect,
)
})
.or_else(|| {
layout.deficits(ctx, &reference.views, candidate, reference.luma_scale)
})?;
let reference = &reference.deficits;
let not_worse = |new: f64, old: f64| new <= old * (1.0 + 1e-6) + 1e-9;
let pooled: f64 = deficits.iter().sum();
let passes = if with_residual {
let no_view_worse = deficits
.iter()
.zip(reference)
.all(|(&new, &old)| new <= old + VIEW_SLACK);
no_view_worse && not_worse(pooled, reference.iter().sum())
} else {
deficits
.iter()
.zip(reference)
.all(|(&new, &old)| not_worse(new, old))
};
passes.then_some(pooled)
}
#[cfg(feature = "extraslow")]
Gate::Exact => {
let views = exact_views(ctx, color, source, incumbent, candidate, &cache.exact)?;
let passes = if with_residual {
let ss: f64 = views.iter().map(|v| v[1] - v[0]).sum();
let cv: f64 = views.iter().map(|v| v[3] - v[2]).sum();
ss >= 0.0 && cv <= 3e-3
} else {
views.iter().all(|&[ss_old, ss_new, cv_old, cv_new]| {
ss_new + 1e-6 >= ss_old && cv_new <= cv_old * (1.0 + 1e-6) + 1e-12
})
};
passes.then(|| -views.iter().map(|v| v[1]).sum::<f64>())
}
}
}
#[cfg(feature = "extraslow")]
pub(super) struct ExactReference {
rgb: Vec<[u8; 3]>,
views: Vec<ExactView>,
}
#[cfg(feature = "extraslow")]
struct ExactView {
ssimulacra2: ssimu2_lite::PreparedReference,
cvvdp: cvvdp_lite::PreparedReference,
incumbent: (f64, f64),
}
#[cfg(feature = "extraslow")]
fn exact_views(
ctx: &EncodingContext,
color: &Image3F,
source: &[u8],
incumbent: &[u8],
candidate: &[u8],
cache: &std::sync::OnceLock<Option<ExactReference>>,
) -> Option<Vec<[f64; 4]>> {
let (width, height) = (color.xsize(), color.ysize());
let views = if ctx.extra_black { 2 } else { 3 };
let size = (width, height);
let reference = cache
.get_or_init(|| {
let rgb = if ctx.extra_black {
Vec::new()
} else {
source_srgb8(ctx, color)
};
let metric = cvvdp_lite::CvvdpLite::new(cvvdp_lite::Display::standard_4k()).ok()?;
let prepared = ctx
.thread_pool
.map(views, |view| {
let mut samples = vec![[0; 3]; source.len()];
composite(view, ctx.extra_black, source, &rgb, &mut samples);
let mut workspace = cvvdp_lite::Workspace::new();
let (ss, cv) = ctx.thread_pool.join(
|| ssimu2_lite::PreparedReference::new(ss2_image(&samples, size)?).ok(),
|| {
metric
.prepare_reference_with(vdp_image(&samples, size)?, &mut workspace)
.ok()
},
);
let (ssimulacra2, cvvdp) = (ss?, cv?);
composite(view, ctx.extra_black, incumbent, &rgb, &mut samples);
let incumbent =
exact_compare(ctx, size, &samples, &ssimulacra2, &cvvdp, workspace)?;
Some(ExactView {
ssimulacra2,
cvvdp,
incumbent,
})
})
.into_iter()
.collect::<Option<Vec<_>>>()?;
Some(ExactReference {
rgb,
views: prepared,
})
})
.as_ref()?;
ctx.thread_pool
.map(views, |view| {
let prepared = &reference.views[view];
let mut samples = vec![[0; 3]; candidate.len()];
composite(
view,
ctx.extra_black,
candidate,
&reference.rgb,
&mut samples,
);
let (ss_new, cv_new) = exact_compare(
ctx,
size,
&samples,
&prepared.ssimulacra2,
&prepared.cvvdp,
cvvdp_lite::Workspace::new(),
)?;
let (ss_old, cv_old) = prepared.incumbent;
Some([ss_old, ss_new, cv_old, cv_new])
})
.into_iter()
.collect()
}
#[cfg(feature = "extraslow")]
fn exact_compare(
ctx: &EncodingContext,
size: (usize, usize),
samples: &[[u8; 3]],
ssimulacra2: &ssimu2_lite::PreparedReference,
cvvdp: &cvvdp_lite::PreparedReference,
workspace: cvvdp_lite::Workspace,
) -> Option<(f64, f64)> {
let (ss, cv) = ctx.thread_pool.join(
|| ssimulacra2.compare(ss2_image(samples, size)?).ok(),
|| {
Some(
cvvdp
.evaluator_with(workspace)
.compare(vdp_image(samples, size)?)
.ok()?
.distortion,
)
},
);
let (ss, cv) = (ss?, cv?);
(ss.is_finite() && cv.is_finite()).then_some((ss, cv))
}
#[cfg(feature = "extraslow")]
fn ss2_image(
samples: &[[u8; 3]],
(width, height): (usize, usize),
) -> Option<ssimu2_lite::RgbImage<'_>> {
ssimu2_lite::RgbImage::srgb8(samples.as_flattened(), width, height, width * 3).ok()
}
#[cfg(feature = "extraslow")]
fn vdp_image(
samples: &[[u8; 3]],
(width, height): (usize, usize),
) -> Option<cvvdp_lite::RgbImage<'_>> {
cvvdp_lite::RgbImage::srgb8(samples.as_flattened(), width, height, width * 3).ok()
}
#[cfg(feature = "extraslow")]
fn composite(view: usize, black_plate: bool, plane: &[u8], rgb: &[[u8; 3]], out: &mut [[u8; 3]]) {
debug_assert_eq!(plane.len(), out.len());
if view == 0 || black_plate {
let flip = if view == 0 { 0 } else { 255 };
for (&alpha, dst) in plane.iter().zip(out) {
*dst = [alpha ^ flip; 3];
}
} else {
let background = if view == 1 { 0 } else { 255 };
crate::simd::rgb8_blend::blend_over_gray(out, rgb, plane, background);
}
}
#[cfg(feature = "extraslow")]
fn source_srgb8(ctx: &EncodingContext, color: &Image3F) -> Vec<[u8; 3]> {
let (width, height) = (color.xsize(), color.ysize());
let mut rgb = vec![[0; 3]; width * height];
if rgb.is_empty() {
return rgb;
}
let rows = height.div_ceil(ctx.thread_pool.num_threads());
let mut bands: Vec<_> = rgb.chunks_mut(width * rows).collect();
let srgb = Srgb8::table();
ctx.thread_pool.for_each_mut(&mut bands, |band, dst| {
let mut linear: [Vec<f32>; 3] = std::array::from_fn(|_| vec![0.0; width]);
for (row, dst) in dst.chunks_exact_mut(width).enumerate() {
let y = band * rows + row;
let [r, g, b] = &mut linear;
crate::xyb::xyb_to_rgb_rows(
&ctx.xyb,
[
&color.plane_row(0, y)[..width],
&color.plane_row(1, y)[..width],
&color.plane_row(2, y)[..width],
],
[r, g, b],
);
for (((&r, &g), &b), dst) in r.iter().zip(g.iter()).zip(b.iter()).zip(dst) {
*dst = [srgb.convert(r), srgb.convert(g), srgb.convert(b)];
}
}
});
rgb
}
#[cfg(feature = "extraslow")]
const SRGB8_STEPS: usize = 4096;
#[cfg(feature = "extraslow")]
struct Srgb8 {
bounds: [f32; 256],
guess: [u8; SRGB8_STEPS + 1],
}
#[cfg(feature = "extraslow")]
impl Srgb8 {
fn table() -> &'static Self {
static TABLE: std::sync::OnceLock<Srgb8> = std::sync::OnceLock::new();
TABLE.get_or_init(|| {
let mut bounds = [f32::INFINITY; 256];
for (i, bound) in bounds[..255].iter_mut().enumerate() {
let encoded = (i as f64 + 0.5) / 255.0;
*bound = (if encoded <= 0.04045 {
encoded / 12.92
} else {
((encoded + 0.055) / 1.055).powf(2.4)
}) as f32;
}
let guess = std::array::from_fn(|i| {
let linear = i as f32 / SRGB8_STEPS as f32;
bounds.partition_point(|&bound| bound <= linear) as u8
});
Self { bounds, guess }
})
}
fn convert(&self, linear: f32) -> u8 {
let linear = if linear > 0.0 { linear.min(1.0) } else { 0.0 };
let value = self.guess[(linear * SRGB8_STEPS as f32) as usize];
value + u8::from(linear >= self.bounds[usize::from(value)])
}
}
fn source_luma_scale(ctx: &EncodingContext, color: &Image3F) -> f32 {
let (width, height) = (color.xsize(), color.ysize());
let mut peak = crate::xyb::rgb_to_xyb_pixel_f32(&ctx.xyb, 1.0, 1.0, 1.0).1;
for y in 0..height {
peak = color.plane_row(1, y)[..width]
.iter()
.fold(peak, |peak, &value| peak.max(finite_luma(value)));
}
if peak > 0.0 { 1.0 / peak } else { 1.0 }
}
fn finite_luma(value: f32) -> f32 {
if value.is_finite() {
value.max(0.0)
} else {
0.0
}
}
const PROXY_TILE: usize = 8 << (msssim_lite::DEFAULT_SCALES - 1);
fn local_rect(source: &[u8], candidate: &[u8], width: usize, height: usize) -> Option<Rect> {
let budget = width.div_ceil(PROXY_TILE) * height.div_ceil(PROXY_TILE) / 8;
if budget == 0 {
return None;
}
let rows = source
.chunks_exact(width)
.zip(candidate.chunks_exact(width));
let y0 = rows.clone().position(|(a, b)| a != b)?;
let y1 = rows.clone().rposition(|(a, b)| a != b)? + 1;
let tile_rows = y1.div_ceil(PROXY_TILE) - y0 / PROXY_TILE;
if tile_rows > budget {
return None;
}
let (mut x0, mut x1) = (width, 0);
for (a, b) in rows.skip(y0).take(y1 - y0) {
if a[..x0] != b[..x0] {
x0 = a[..x0].iter().zip(&b[..x0]).position(|(a, b)| a != b)?;
}
if a[x1..] != b[x1..] {
x1 += a[x1..].iter().zip(&b[x1..]).rposition(|(a, b)| a != b)? + 1;
}
let tile_columns = x1.div_ceil(PROXY_TILE) - x0 / PROXY_TILE;
if tile_columns * tile_rows > budget {
return None;
}
}
Some(Rect::new(x0, y0, x1, y1))
}
fn ink_amount(sample: u8) -> f32 {
1.0 - f32::from(sample) * (1.0 / 255.0)
}
#[derive(Clone, Copy)]
struct Layout<'a> {
width: usize,
height: usize,
black: bool,
color: &'a Image3F,
}
impl Layout<'_> {
fn views(&self) -> usize {
if self.black { 2 } else { 3 }
}
fn with_view<T>(
&self,
view: usize,
plane: &[u8],
luma_scale: f32,
use_image: impl FnOnce(GrayImage<'_>) -> Option<T>,
) -> Option<T> {
if view == 0 {
let image = GrayImage::u8(plane, self.width, self.height, self.width).ok()?;
return use_image(image);
}
let samples: Vec<f32> = if self.black {
plane.iter().copied().map(ink_amount).collect()
} else {
self.composite(
view,
plane,
luma_scale,
Rect::new(0, 0, self.width, self.height),
)
};
let image = GrayImage::unit_f32(&samples, self.width, self.height, self.width).ok()?;
use_image(image)
}
fn composite(&self, view: usize, plane: &[u8], scale: f32, rect: Rect) -> Vec<f32> {
if view == 1 {
self.lightness_composite::<false>(plane, scale, rect)
} else {
self.lightness_composite::<true>(plane, scale, rect)
}
}
fn lightness_composite<const WHITE: bool>(
&self,
plane: &[u8],
scale: f32,
rect: Rect,
) -> Vec<f32> {
let mut samples = Vec::with_capacity((rect.x1 - rect.x0) * (rect.y1 - rect.y0));
for y in rect.y0..rect.y1 {
let row = y * self.width;
let alpha = &plane[row + rect.x0..row + rect.x1];
let luma = &self.color.plane_row(1, y)[rect.x0..rect.x1];
samples.extend(alpha.iter().zip(luma).map(|(&alpha, &luma)| {
let alpha = f32::from(alpha) * (1.0 / 255.0);
let lightness = (finite_luma(luma) * scale) * alpha;
if WHITE {
lightness + 1.0 - alpha
} else {
lightness
}
}));
}
samples
}
fn patch_deficits(
&self,
ctx: &EncodingContext,
reference: &[PreparedReference],
plane: &[u8],
scale: f32,
rect: Rect,
) -> Option<Vec<f64>> {
let width = rect.x1 - rect.x0;
let height = rect.y1 - rect.y0;
ctx.thread_pool
.map(reference.len(), |view| {
let samples: Vec<f32>;
let patch = if view == 0 {
let start = rect.y0 * self.width + rect.x0;
GrayImage::u8(&plane[start..], width, height, self.width).ok()?
} else {
samples = if self.black {
let mut samples = Vec::with_capacity(width * height);
for y in rect.y0..rect.y1 {
let start = y * self.width + rect.x0;
samples.extend(
plane[start..start + width].iter().copied().map(ink_amount),
);
}
samples
} else {
self.composite(view, plane, scale, rect)
};
GrayImage::unit_f32(&samples, width, height, width).ok()?
};
let deficit = reference[view]
.compare_patch(patch, rect.x0, rect.y0)
.ok()?
.deficit();
deficit.is_finite().then_some(deficit)
})
.into_iter()
.collect()
}
fn prepare(
&self,
ctx: &EncodingContext,
plane: &[u8],
luma_scale: f32,
) -> Option<Vec<PreparedReference>> {
ctx.thread_pool
.map(self.views(), |view| {
self.with_view(view, plane, luma_scale, |image| {
PreparedReference::new(image).ok()
})
})
.into_iter()
.collect()
}
fn deficits(
&self,
ctx: &EncodingContext,
reference: &[PreparedReference],
plane: &[u8],
luma_scale: f32,
) -> Option<Vec<f64>> {
ctx.thread_pool
.map(reference.len(), |view| {
self.with_view(view, plane, luma_scale, |image| {
let score = reference[view].compare(image).ok()?;
Some(score.deficit()).filter(|deficit| deficit.is_finite())
})
})
.into_iter()
.collect()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn context() -> EncodingContext {
EncodingContext::new(
crate::Speed::Slow,
crate::Arbiter::Ssimulacra2,
crate::xyb::XybMatrix::SPEC,
1.5,
1,
)
}
#[test]
fn error_statistics_include_all_chunks_and_the_tail() {
let source = vec![0u8; 32768 * 3 + 1];
let mut candidate = vec![255u8; source.len()];
*candidate.last_mut().unwrap() = 7;
let errors = plane_errors(&source, &candidate);
assert_eq!(errors.squared, (32768 * 3) * 255u64.pow(2) + 49);
assert_eq!(errors.max, 255);
assert_eq!(errors.endpoints, source.len());
}
#[cfg(feature = "extraslow")]
#[test]
fn exact_color_composites_match_integer_rounding() {
let alpha: Vec<_> = (0..=255).flat_map(|a| [a; 256]).chain([253]).collect();
let rgb: Vec<_> = (0..alpha.len())
.map(|i| {
let v = i as u8;
[v, v.wrapping_add(17), 255 - v]
})
.collect();
let mut out = vec![[0; 3]; alpha.len()];
for view in 1..=2 {
composite(view, false, &alpha, &rgb, &mut out);
for ((&a, &src), &dst) in alpha.iter().zip(&rgb).zip(&out) {
let expected = src.map(|v| {
let covered = (u32::from(a) * u32::from(v) * 2 + 255) / 510;
(covered + if view == 1 { 0 } else { 255 - u32::from(a) }) as u8
});
assert_eq!(dst, expected);
}
}
}
#[cfg(feature = "extraslow")]
#[test]
fn srgb_lookup_resolves_rounding_boundaries() {
let table = Srgb8::table();
for (i, &boundary) in table.bounds[..255].iter().enumerate() {
assert_eq!(table.convert(boundary.next_down()), i as u8);
assert_eq!(table.convert(boundary), i as u8 + 1);
assert_eq!(table.convert(boundary.next_up()), i as u8 + 1);
}
assert_eq!(table.convert(f32::NAN), 0);
assert_eq!(table.convert(f32::NEG_INFINITY), 0);
assert_eq!(table.convert(f32::INFINITY), 255);
}
#[test]
fn local_alpha_and_ink_trials_match_full_scoring() {
let (width, height) = (195, 133);
let mut color = Image3F::try_new(width, height).unwrap();
for y in 0..height {
for (x, sample) in color.plane_row_mut(1, y)[..width].iter_mut().enumerate() {
*sample = ((x * 13 + y * 17) % 127) as f32 / 256.0;
}
}
let source: Vec<u8> = (0..width * height).map(|i| 40 + (i % 127) as u8).collect();
let incumbent: Vec<u8> = source.iter().map(|&sample| sample + 2).collect();
let mut candidate = source.clone();
let rect = Rect::new(width - 7, height - 8, width, height);
for y in rect.y0..rect.y1 {
for x in rect.x0..rect.x1 {
candidate[y * width + x] += 1;
}
}
assert_eq!(local_rect(&source, &candidate, width, height), Some(rect));
let mut spread = candidate.clone();
spread[0] += 1;
assert!(local_rect(&source, &spread, width, height).is_none());
for black in [false, true] {
let mut ctx = context();
ctx.extra_black = black;
let layout = Layout {
width,
height,
black,
color: &color,
};
let scale = if black {
1.0
} else {
source_luma_scale(&ctx, &color)
};
let references = layout.prepare(&ctx, &source, scale).unwrap();
let full = layout
.deficits(&ctx, &references, &candidate, scale)
.unwrap();
let local = layout
.patch_deficits(&ctx, &references, &candidate, scale, rect)
.unwrap();
for (full, local) in full.iter().zip(&local) {
assert!((full - local).abs() < 1e-12);
}
let source = AlphaPlane::U8(source.clone());
let incumbent = AlphaPlane::U8(incumbent.clone());
let candidate = AlphaPlane::U8(candidate.clone());
let cache = GateCache::default();
for with_residual in [false, true, false] {
let pooled = score(
&ctx,
&color,
&source,
&incumbent,
&candidate,
with_residual,
&cache,
)
.expect("the local candidate improves on the ordinary coding");
assert!((pooled - full.iter().sum::<f64>()).abs() < 1e-12);
}
}
}
#[test]
fn preserves_exact_alpha_and_hard_endpoints() {
let ctx = context();
let color = Image3F::try_new(32, 32).unwrap();
let source = AlphaPlane::U8(vec![0; 32 * 32]);
let softened = AlphaPlane::U8(vec![1; 32 * 32]);
assert!(!acceptable(
&ctx,
&color,
&source,
&source,
&softened,
false,
&Default::default()
));
assert!(acceptable(
&ctx,
&color,
&source,
&softened,
&source,
false,
&Default::default()
));
}
#[test]
fn residual_candidates_are_judged_by_pooled_structure() {
let ctx = context();
let (width, height) = (70, 45);
let color = Image3F::try_new(width, height).unwrap();
let ramp: Vec<u8> = (0..width * height)
.map(|i| (40 + (i % width) * 2) as u8)
.collect();
let incumbent = AlphaPlane::U8(ramp.iter().map(|&v| v + 2).collect());
let closer = AlphaPlane::U8(ramp.iter().map(|&v| v + 1).collect());
let banded = AlphaPlane::U8(ramp.iter().map(|&v| v / 4 * 4).collect());
let source = AlphaPlane::U8(ramp);
let cache = Default::default();
assert!(acceptable(
&ctx, &color, &source, &incumbent, &closer, true, &cache
));
assert!(!acceptable(
&ctx, &color, &source, &incumbent, &banded, true, &cache
));
}
}