devpage_design/compare/
mod.rs

1//! Comparing two drawings of the same scene, by the engine's one rule.
2
3use crate::resolve::{self};
4
5/// A PNG's or JPEG's pixels, straight RGBA.
6/// How far apart two drawings of the same scene may be. Two rasterizers of one
7/// display list differ only in how they anti-alias an edge: a pixel on an edge
8/// takes some value between the colors either side of it, and each rasterizer
9/// picks a slightly different one. So a pixel is **unexplained** when, in some
10/// channel, its value lies more than [`EDGE`] outside the range of the other
11/// drawing's pixels around it (itself and its eight neighbours), in either
12/// direction. A missing or moved part — a divider, an icon, a word — leaves
13/// pixels no neighbour in the other drawing explains. At most [`SHARE`] of the
14/// pixels may be unexplained, and no 8-connected cluster of them may be larger
15/// than [`CLUSTER`].
16pub const EDGE: u8 = 8;
17/// The largest share of pixels that may be unexplained.
18pub const SHARE: f64 = 0.0005;
19/// The largest cluster of touching unexplained pixels.
20pub const CLUSTER: usize = 4;
21
22/// How two drawings of the same size differ.
23#[derive(Debug, Clone, Copy, PartialEq)]
24pub struct Difference {
25    /// The share of pixels that are unexplained.
26    pub share: f64,
27    /// The size of the largest 8-connected cluster of unexplained pixels.
28    pub cluster: usize,
29    /// The largest difference in any channel between the same pixel of each.
30    pub max: u8,
31}
32
33impl Difference {
34    /// Whether this is only the anti-aliasing two rasterizers may differ by.
35    pub fn within_tolerance(&self) -> bool {
36        self.share <= SHARE && self.cluster <= CLUSTER
37    }
38}
39
40/// How two RGBA buffers `width` pixels wide differ; `None` when their sizes
41/// differ.
42pub fn compare(a: &[u8], b: &[u8], width: usize) -> Option<Difference> {
43    if a.len() != b.len() || width == 0 || !a.len().is_multiple_of(4 * width) {
44        return None;
45    }
46    let count = a.len() / 4;
47    let height = count / width;
48    let neighbours = |i: usize| {
49        let (x, y) = (i % width, i / width);
50        let xs = x.saturating_sub(1)..=(x + 1).min(width - 1);
51        (y.saturating_sub(1)..=(y + 1).min(height - 1))
52            .flat_map(move |ny| xs.clone().map(move |nx| ny * width + nx))
53    };
54    // Whether pixel `i` of `p` lies outside what `q` has around it.
55    let outside = |p: &[u8], q: &[u8], i: usize| {
56        (0..4).any(|c| {
57            let v = p[4 * i + c];
58            let (lo, hi) = neighbours(i).fold((u8::MAX, 0), |(lo, hi), n| {
59                (lo.min(q[4 * n + c]), hi.max(q[4 * n + c]))
60            });
61            v.saturating_add(EDGE) < lo || v > hi.saturating_add(EDGE)
62        })
63    };
64    let max = a
65        .iter()
66        .zip(b)
67        .map(|(x, y)| x.abs_diff(*y))
68        .max()
69        .unwrap_or(0);
70    let unexplained: Vec<bool> = (0..count)
71        .map(|i| outside(a, b, i) || outside(b, a, i))
72        .collect();
73    let mut seen = vec![false; count];
74    let (mut total, mut cluster) = (0, 0);
75    let mut stack = Vec::new();
76    for start in 0..count {
77        if !unexplained[start] || seen[start] {
78            continue;
79        }
80        seen[start] = true;
81        stack.push(start);
82        let mut size = 0;
83        while let Some(i) = stack.pop() {
84            size += 1;
85            for n in neighbours(i) {
86                if unexplained[n] && !seen[n] {
87                    seen[n] = true;
88                    stack.push(n);
89                }
90            }
91        }
92        total += size;
93        cluster = cluster.max(size);
94    }
95    Some(Difference {
96        share: total as f64 / count.max(1) as f64,
97        cluster,
98        max,
99    })
100}
101
102/// Whether two RGBA buffers `width` pixels wide are the same drawing within
103/// the tolerance; otherwise how they differ, or `None` for different sizes.
104pub fn matches(a: &[u8], b: &[u8], width: usize) -> Result<(), Option<Difference>> {
105    match compare(a, b, width) {
106        Some(d) if d.within_tolerance() => Ok(()),
107        other => Err(other),
108    }
109}
110
111/// A PNG's or JPEG's pixels as straight RGBA, with its width and height —
112/// for comparing drawings.
113pub fn pixels(data: &[u8]) -> Option<(Vec<u8>, u32, u32)> {
114    let image = resolve::decode(data).ok()?;
115    Some((image.data.data().to_vec(), image.width, image.height))
116}
117
118#[cfg(test)]
119mod tests;
devpage_design/compare/mod.rs

devpage_design/compare/
mod.rs
