1use crate::{ResourceAnalysis, image_backend::Decoded};
15use serde::{Deserialize, Serialize};
16use std::path::{Path, PathBuf};
17
18const GRID: usize = 16;
19const MAX_LUMA_DISTANCE: f32 = 0.022;
21const MAX_ALPHA_DISTANCE: f32 = 0.03;
22const MAX_CELL_DISTANCE: f32 = 0.16;
24const MAX_COLOR_DISTANCE: i32 = 14;
26const MAX_ASPECT_DIFFERENCE: f64 = 0.03;
27const MIN_VARIANCE: f32 = 0.0004;
29const RESIZED_DISTANCE: f32 = 0.012;
31
32#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
33#[serde(deny_unknown_fields)]
34pub struct Fingerprint {
35 pub luma: String,
37 pub alpha: String,
39 pub mean_rgb: [u8; 3],
40 pub detailed: bool,
42}
43
44#[derive(Debug, Clone, Serialize, Deserialize)]
45pub struct SimilarGroup {
46 pub kind: String,
49 pub members: Vec<usize>,
51 #[serde(default)]
54 pub comparisons: Vec<SimilarComparison>,
55 pub redundant_bytes: u64,
57}
58
59#[derive(Debug, Clone, Serialize, Deserialize)]
61pub struct SimilarComparison {
62 pub score: f32,
64 pub identical: bool,
65 pub brightness_difference: f32,
68 pub opacity_difference: f32,
69 pub color_difference: f32,
70 pub max_cell_difference: f32,
72}
73
74fn downscale(image: &Decoded, sample: impl Fn(&[f32]) -> f32) -> Vec<f32> {
76 let (width, height) = (image.info.width, image.info.height);
77 let mut sums = vec![0.0_f32; GRID * GRID];
78 let mut counts = vec![0_u32; GRID * GRID];
79 for y in 0..height {
80 let gy = y * GRID / height;
81 let row = &image.pixels[y * width * 4..(y + 1) * width * 4];
82 for (x, pixel) in row.as_chunks::<4>().0.iter().enumerate() {
83 let cell = gy * GRID + x * GRID / width;
84 sums[cell] += sample(pixel);
85 counts[cell] += 1;
86 }
87 }
88 (0..GRID * GRID)
90 .map(|cell| {
91 if counts[cell] > 0 {
92 return sums[cell] / counts[cell] as f32;
93 }
94 let (gx, gy) = (cell % GRID, cell / GRID);
95 let pixel = ((gy * height / GRID) * width + gx * width / GRID) * 4;
96 sample(&image.pixels[pixel..pixel + 4])
97 })
98 .collect()
99}
100
101fn encode(grid: &[f32]) -> String {
102 grid.iter()
103 .map(|v| format!("{:02x}", (v.clamp(0.0, 1.0) * 255.0).round() as u8))
104 .collect()
105}
106
107fn decode(hex: &str) -> Option<Vec<f32>> {
108 if hex.is_empty() {
109 return Some(vec![1.0; GRID * GRID]);
110 }
111 if hex.len() != GRID * GRID * 2 || !hex.is_ascii() {
112 return None;
113 }
114 (0..GRID * GRID)
115 .map(|cell| {
116 u8::from_str_radix(&hex[cell * 2..cell * 2 + 2], 16)
117 .ok()
118 .map(|v| f32::from(v) / 255.0)
119 })
120 .collect()
121}
122
123fn distance(a: &[f32], b: &[f32]) -> (f32, f32) {
125 let (mut total, mut worst) = (0.0_f32, 0.0_f32);
126 for (x, y) in a.iter().zip(b) {
127 let delta = (x - y).abs();
128 total += delta;
129 worst = worst.max(delta);
130 }
131 (total / a.len() as f32, worst)
132}
133
134pub(crate) fn fingerprint(image: &Decoded) -> Option<Fingerprint> {
135 if image.info.width == 0 || image.info.height == 0 || image.pixels.is_empty() {
136 return None;
137 }
138 let luma = downscale(image, |p| {
140 0.2126 * p[0] + 0.7152 * p[1] + 0.0722 * p[2] + (1.0 - p[3]) * 0.5
141 });
142 let alpha = downscale(image, |p| p[3]);
143 let mean = luma.iter().sum::<f32>() / luma.len() as f32;
144 let variance = luma.iter().map(|v| (v - mean).powi(2)).sum::<f32>() / luma.len() as f32;
145 let opaque = alpha.iter().all(|a| *a >= 0.999);
146 let mut color = [0.0_f64; 3];
147 let mut coverage = 0.0_f64;
148 for pixel in image.pixels.as_chunks::<4>().0 {
149 for (total, value) in color.iter_mut().zip(pixel) {
150 *total += f64::from(*value);
151 }
152 coverage += f64::from(pixel[3]);
153 }
154 let mean_rgb = color.map(|total| {
155 if coverage > 0.0 {
156 (total / coverage * 255.0).round().clamp(0.0, 255.0) as u8
157 } else {
158 0
159 }
160 });
161 Some(Fingerprint {
162 luma: encode(&luma),
163 alpha: if opaque {
164 String::new()
165 } else {
166 encode(&alpha)
167 },
168 mean_rgb,
169 detailed: variance >= MIN_VARIANCE,
170 })
171}
172
173fn variant_key(path: &Path) -> PathBuf {
176 let parent = path.parent().unwrap_or(Path::new(""));
177 if parent
178 .extension()
179 .is_some_and(|e| e == "imageset" || e == "appiconset")
180 {
181 return parent.to_path_buf();
182 }
183 let stem = path
184 .file_name()
185 .map(|name| name.to_string_lossy().to_string())
186 .unwrap_or_default();
187 let stem = stem.split('.').next().unwrap_or_default();
188 let stem = stem
189 .strip_suffix("@2x")
190 .or_else(|| stem.strip_suffix("@3x"))
191 .unwrap_or(stem)
192 .to_ascii_lowercase();
193 match crate::android::classify(path) {
194 Some(android) if android.area == "res" => android
196 .module
197 .join(android.source_set)
198 .join(android.res_type.unwrap_or_default())
199 .join(stem),
200 _ => parent.join(stem),
201 }
202}
203
204struct Entry {
205 index: usize,
206 bytes: u64,
207 sha256: Option<String>,
208 print: Fingerprint,
209 luma: Vec<f32>,
210 alpha: Vec<f32>,
211 aspect: f64,
212 dimensions: (usize, usize),
213 frames: usize,
214 variant: PathBuf,
215}
216
217fn compare(a: &Entry, b: &Entry) -> SimilarComparison {
218 let identical = a.sha256.is_some() && a.sha256 == b.sha256;
219 let (brightness_difference, luma_peak) = distance(&a.luma, &b.luma);
220 let (opacity_difference, alpha_peak) = distance(&a.alpha, &b.alpha);
221 let color_difference = a
222 .print
223 .mean_rgb
224 .iter()
225 .zip(b.print.mean_rgb)
226 .map(|(x, y)| f32::from(x.abs_diff(y)) / 255.0)
227 .fold(0.0_f32, f32::max);
228 let difference = brightness_difference
231 .max(opacity_difference)
232 .max(color_difference);
233 SimilarComparison {
234 score: if identical {
235 100.0
236 } else {
237 (100.0 * (1.0 - difference)).clamp(0.0, 99.9)
238 },
239 identical,
240 brightness_difference,
241 opacity_difference,
242 color_difference,
243 max_cell_difference: luma_peak.max(alpha_peak),
244 }
245}
246
247fn alike(a: &Entry, b: &Entry) -> bool {
248 if a.variant == b.variant {
249 return false;
250 }
251 if a.sha256.is_some() && a.sha256 == b.sha256 {
252 return true;
253 }
254 a.frames == 1
255 && b.frames == 1
256 && a.print.detailed
257 && b.print.detailed
258 && (a.aspect - b.aspect).abs() <= MAX_ASPECT_DIFFERENCE * a.aspect.max(b.aspect)
259 && a.print.mean_rgb.iter().zip(b.print.mean_rgb)
261 .all(|(x, y)| (i32::from(*x) - i32::from(y)).abs() <= MAX_COLOR_DISTANCE)
262 && {
263 let metrics = compare(a, b);
264 metrics.brightness_difference <= MAX_LUMA_DISTANCE
265 && metrics.opacity_difference <= MAX_ALPHA_DISTANCE
266 && metrics.max_cell_difference <= MAX_CELL_DISTANCE
267 }
268}
269
270pub(crate) fn group(resources: &[ResourceAnalysis]) -> Vec<SimilarGroup> {
272 let mut entries: Vec<Entry> = resources
273 .iter()
274 .enumerate()
275 .filter_map(|(index, resource)| {
276 let print = resource.fingerprint.clone()?;
277 let image = resource.image.as_ref()?;
278 Some(Entry {
279 index,
280 bytes: resource.resource.bytes,
281 sha256: resource.sha256.clone(),
282 luma: decode(&print.luma)?,
283 alpha: decode(&print.alpha)?,
284 aspect: image.width as f64 / image.height.max(1) as f64,
285 dimensions: (image.width, image.height),
286 frames: image.frames,
287 variant: variant_key(&resource.resource.path),
288 print,
289 })
290 })
291 .collect();
292 entries.sort_by(|a, b| b.bytes.cmp(&a.bytes).then(a.index.cmp(&b.index)));
296 let mut assigned = vec![false; entries.len()];
297 let mut clusters = Vec::new();
298 for a in 0..entries.len() {
299 if assigned[a] {
300 continue;
301 }
302 let mut members = vec![&entries[a]];
303 for b in a + 1..entries.len() {
304 if !assigned[b] && alike(&entries[a], &entries[b]) {
305 assigned[b] = true;
306 members.push(&entries[b]);
307 }
308 }
309 if members.len() > 1 {
310 assigned[a] = true;
311 clusters.push(members);
312 }
313 }
314 let mut groups: Vec<SimilarGroup> = clusters
315 .into_iter()
316 .filter(|members| members.len() > 1)
317 .map(|mut members| {
318 members.sort_by(|a, b| b.bytes.cmp(&a.bytes).then(a.index.cmp(&b.index)));
319 let first = members[0];
320 let identical = members
321 .iter()
322 .all(|m| m.sha256.is_some() && m.sha256 == first.sha256);
323 let resized = members.iter().any(|m| m.dimensions != first.dimensions)
324 && members
325 .iter()
326 .all(|m| distance(&m.luma, &first.luma).0 <= RESIZED_DISTANCE);
327 SimilarGroup {
328 kind: if identical {
329 "identical"
330 } else if resized {
331 "resized"
332 } else {
333 "similar"
334 }
335 .into(),
336 comparisons: members.iter().map(|m| compare(first, m)).collect(),
337 redundant_bytes: members.iter().skip(1).map(|m| m.bytes).sum(),
338 members: members.iter().map(|m| m.index).collect(),
339 }
340 })
341 .collect();
342 groups.sort_by(|a, b| {
343 b.redundant_bytes
344 .cmp(&a.redundant_bytes)
345 .then(a.members.cmp(&b.members))
346 });
347 groups
348}
349
350#[cfg(test)]
351mod tests {
352 use super::*;
353 use crate::{ImageInfo, Resource};
354
355 fn picture(width: usize, height: usize, paint: impl Fn(f32, f32) -> [f32; 4]) -> Decoded {
356 let mut pixels = Vec::with_capacity(width * height * 4);
357 for y in 0..height {
358 for x in 0..width {
359 let [r, g, b, a] = paint(
360 (x as f32 + 0.5) / width as f32,
361 (y as f32 + 0.5) / height as f32,
362 );
363 pixels.extend([r * a, g * a, b * a, a]);
364 }
365 }
366 Decoded {
367 info: ImageInfo {
368 decoder_type: "test".into(),
369 width,
370 height,
371 frames: 1,
372 bits_per_component: 8,
373 orientation: 1,
374 transparent_pixels: 0,
375 has_transparent_pixels: false,
376 },
377 pixels,
378 }
379 }
380
381 fn badge(tint: [f32; 3]) -> impl Fn(f32, f32) -> [f32; 4] {
383 move |x, y| {
384 let inside = (x - 0.5).powi(2) + (y - 0.5).powi(2) < 0.2;
385 let stripe = (y - 0.35).abs() < 0.08 && x > 0.3;
386 let shade = if stripe { 1.0 } else { 0.55 + 0.4 * x };
387 [
388 tint[0] * shade,
389 tint[1] * shade,
390 tint[2] * shade,
391 if inside { 1.0 } else { 0.0 },
392 ]
393 }
394 }
395
396 fn row(path: &str, image: &Decoded, sha: &str) -> ResourceAnalysis {
397 let mut row = ResourceAnalysis::new(&Resource::for_tests(path, "png"), "inspected");
398 row.resource.bytes = (image.info.width * image.info.height) as u64;
399 row.sha256 = Some(sha.repeat(64));
400 row.image = Some(image.info.clone());
401 row.fingerprint = fingerprint(image);
402 row
403 }
404
405 #[test]
406 fn the_same_picture_at_another_size_is_found_and_variants_are_not() {
407 let red = badge([0.9, 0.2, 0.2]);
408 let large = picture(300, 300, &red);
409 let small = picture(96, 96, &red);
410 let rows = vec![
411 row("Feature/A/badge_big.png", &large, "a"),
412 row("Feature/B/medal.png", &small, "b"),
413 row("Feature/C/icon@2x.png", &small, "c"),
415 row("Feature/C/icon@3x.png", &large, "d"),
416 ];
417 let groups = group(&rows);
418 assert_eq!(groups.len(), 1, "{groups:?}");
419 assert_eq!(groups[0].kind, "resized");
420 assert_eq!(groups[0].members.len(), 4);
422 let only_variants = group(&rows[2..]);
423 assert!(only_variants.is_empty(), "{only_variants:?}");
424 }
425
426 #[test]
427 fn identical_bytes_are_reported_as_identical_with_redundant_bytes() {
428 let image = picture(64, 64, badge([0.2, 0.5, 0.9]));
429 let rows = vec![
430 row("a/one.png", &image, "a"),
431 row("b/two.png", &image, "a"),
432 row("c/three.png", &image, "a"),
433 ];
434 let groups = group(&rows);
435 assert_eq!(groups[0].kind, "identical");
436 assert_eq!(groups[0].redundant_bytes, 2 * 64 * 64);
437 }
438
439 #[test]
440 fn different_tint_shape_or_alpha_is_not_a_duplicate() {
441 let base = picture(128, 128, badge([0.9, 0.2, 0.2]));
442 let blue = picture(128, 128, badge([0.2, 0.3, 0.9]));
443 let square = picture(128, 128, |x, y| {
444 let inside = (x - 0.5).abs() < 0.4 && (y - 0.5).abs() < 0.4;
445 [0.9 * x, 0.2, 0.2 * y, if inside { 1.0 } else { 0.0 }]
446 });
447 let opaque = picture(128, 128, |x, y| {
448 let [r, g, b, _] = badge([0.9, 0.2, 0.2])(x, y);
449 [r, g, b, 1.0]
450 });
451 let rows = vec![
452 row("a/base.png", &base, "a"),
453 row("b/blue.png", &blue, "b"),
454 row("c/square.png", &square, "c"),
455 row("d/opaque.png", &opaque, "d"),
456 ];
457 assert!(group(&rows).is_empty(), "{:?}", group(&rows));
458 }
459
460 #[test]
461 fn flat_images_only_match_by_exact_bytes() {
462 let white = picture(40, 40, |_, _| [1.0, 1.0, 1.0, 1.0]);
463 let nearly = picture(80, 80, |_, _| [0.99, 1.0, 1.0, 1.0]);
464 assert!(!fingerprint(&white).unwrap().detailed);
465 let rows = vec![row("a/w.png", &white, "a"), row("b/n.png", &nearly, "b")];
466 assert!(group(&rows).is_empty());
467 let same = vec![row("a/w.png", &white, "a"), row("b/w.png", &white, "a")];
468 assert_eq!(group(&same)[0].kind, "identical");
469 }
470
471 #[test]
472 fn android_density_and_locale_folders_of_one_name_are_variants() {
473 let image = picture(64, 64, badge([0.3, 0.8, 0.4]));
474 let big = picture(128, 128, badge([0.3, 0.8, 0.4]));
475 let rows = vec![
476 row("app/src/main/res/drawable-xhdpi/ic_ok.png", &image, "a"),
477 row("app/src/main/res/drawable-xxxhdpi/ic_ok.png", &big, "b"),
478 row(
479 "app/src/main/res/drawable-ldrtl-xhdpi/ic_ok.png",
480 &image,
481 "a",
482 ),
483 ];
484 assert!(group(&rows).is_empty());
485 let mut with_copy = rows;
486 with_copy.push(row(
487 "module/room/src/main/res/drawable-xhdpi/ic_done.png",
488 &image,
489 "a",
490 ));
491 assert_eq!(group(&with_copy).len(), 1);
492 }
493
494 #[test]
495 fn scores_distinguish_exact_reencoded_and_small_tint_changes() {
496 let base = picture(128, 128, badge([0.9, 0.2, 0.2]));
497 let slight = picture(128, 128, badge([0.89, 0.2, 0.2]));
498 let stronger = picture(128, 128, badge([0.86, 0.2, 0.2]));
499 let rows = vec![
500 row("a/base.png", &base, "a"),
501 row("b/exact.png", &base, "a"),
502 row("c/reencoded.png", &base, "b"),
503 row("d/slight.png", &slight, "c"),
504 row("e/stronger.png", &stronger, "d"),
505 ];
506 let groups = group(&rows);
507 assert_eq!(groups.len(), 1);
508 assert_eq!(groups[0].members, vec![0, 1, 2, 3, 4]);
509 let scores: Vec<_> = groups[0].comparisons.iter().map(|m| m.score).collect();
510 assert_eq!(scores[1], 100.0);
511 assert_eq!(scores[2], 99.9);
512 assert!(scores[2] > scores[3] && scores[3] > scores[4], "{scores:?}");
513 assert!(!groups[0].comparisons[2].identical);
514 println!(
515 "exact / reencoded / slight tint / stronger tint: {:?}",
516 &scores[1..]
517 );
518 }
519
520 #[test]
521 fn a_similarity_chain_cannot_claim_a_match_to_the_reference() {
522 let image = picture(64, 64, badge([0.2, 0.5, 0.9]));
524 let rows: Vec<_> = [100, 105, 110]
525 .iter()
526 .enumerate()
527 .map(|(i, level)| {
528 let mut resource = row(&format!("{i}/image.png"), &image, &i.to_string());
529 resource.fingerprint.as_mut().unwrap().luma =
530 format!("{level:02x}").repeat(GRID * GRID);
531 resource
532 })
533 .collect();
534 assert_eq!(group(&rows[..2])[0].members.len(), 2);
535 assert_eq!(group(&rows[1..])[0].members.len(), 2);
536 assert!(group(&[rows[0].clone(), rows[2].clone()]).is_empty());
537 let groups = group(&rows);
538 assert_eq!(groups.len(), 1);
539 assert_eq!(groups[0].members, vec![0, 1]);
540 assert_eq!(groups[0].comparisons.len(), 2);
541 }
542
543 #[test]
544 fn a_local_opacity_change_is_not_hidden_by_the_average() {
545 let image = picture(64, 64, |x, y| [x, y, 0.5, 1.0]);
546 let base = row("a/base.png", &image, "a");
547 let mut changed = row("b/changed.png", &image, "b");
548 changed.fingerprint.as_mut().unwrap().alpha = format!("00{}", "ff".repeat(GRID * GRID - 1));
551 assert!(group(&[base, changed]).is_empty());
552 }
553
554 #[test]
555 fn scores_follow_the_largest_reference_and_legacy_reports_remain_readable() {
556 let image = picture(64, 64, badge([0.2, 0.5, 0.9]));
557 let mut small = row("a/small.png", &image, "a");
558 small.resource.bytes = 10;
559 let large = row("b/large.png", &image, "b");
560 let groups = group(&[small, large]);
561 assert_eq!(groups[0].members, vec![1, 0]);
562 assert!(groups[0].comparisons[0].identical);
563 assert!(!groups[0].comparisons[1].identical);
564 let json = serde_json::to_string(&groups).unwrap();
565 let restored: Vec<SimilarGroup> = serde_json::from_str(&json).unwrap();
566 assert_eq!(restored[0].comparisons[1].score, 99.9);
567 let legacy: SimilarGroup =
568 serde_json::from_str(r#"{"kind":"similar","members":[0,1],"redundant_bytes":10}"#)
569 .unwrap();
570 assert!(legacy.comparisons.is_empty());
571 }
572
573 #[test]
574 fn matching_posters_do_not_prove_matching_animations() {
575 let image = picture(64, 64, badge([0.2, 0.5, 0.9]));
576 let still = row("a/still.png", &image, "a");
577 let mut animation = row("b/animated.png", &image, "b");
578 animation.image.as_mut().unwrap().frames = 2;
579 assert!(group(&[still, animation.clone()]).is_empty());
580 let mut copy = animation.clone();
581 copy.resource.path = "c/copy.png".into();
582 assert_eq!(group(&[animation, copy])[0].comparisons[1].score, 100.0);
583 }
584
585 #[test]
586 fn tiny_images_and_malformed_fingerprints_are_handled() {
587 let tiny = picture(5, 3, |x, y| [x, y, 0.5, 1.0]);
588 let print = fingerprint(&tiny).unwrap();
589 assert_eq!(print.luma.len(), GRID * GRID * 2);
590 assert_eq!(print.alpha, "");
591 let mut broken = row("a/x.png", &tiny, "a");
592 broken.fingerprint.as_mut().unwrap().luma = "zz".into();
593 assert!(group(&[broken, row("b/y.png", &tiny, "b")]).is_empty());
594 }
595}