falcon_library/
duplicates.rs

1//! Finding duplicate items: exact copies by content hash, and near copies
2//! by a perceptual hash of their thumbnails. See the Import chapter of the
3//! docs; Eagle stores no hash in item JSON, so nothing here writes to items.
4
5use std::collections::{HashMap, HashSet};
6use std::fs::{self, File};
7use std::io;
8use std::path::Path;
9use std::time::UNIX_EPOCH;
10
11use image::DynamicImage;
12use image::imageops::FilterType;
13use serde::{Deserialize, Serialize};
14
15use crate::library::Library;
16use crate::model::Item;
17use crate::thumbnail;
18
19/// BLAKE3 hash of a file's bytes, as 64 lowercase hex digits.
20pub fn content_hash(path: &Path) -> io::Result<String> {
21    let mut hasher = blake3::Hasher::new();
22    hasher.update_reader(File::open(path)?)?;
23    Ok(hasher.finalize().to_hex().to_string())
24}
25
26/// Cached hashes of one item's original, valid while its size and mtime
27/// stay the same.
28#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
29pub struct CacheEntry {
30    pub size: u64,
31    /// The original's modification time, ms.
32    pub mtime: u64,
33    #[serde(default, skip_serializing_if = "Option::is_none")]
34    pub content: Option<String>,
35    #[serde(default, skip_serializing_if = "Option::is_none")]
36    pub perceptual: Option<u64>,
37}
38
39/// Hashes keyed by item id, which the caller can keep between runs (it is
40/// plain JSON; falcon doesn't store it in the library).
41#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
42pub struct HashCache {
43    pub entries: HashMap<String, CacheEntry>,
44}
45
46impl HashCache {
47    /// Loads a cache saved with [`HashCache::save`]; empty if missing or
48    /// unreadable.
49    pub fn load(path: &Path) -> HashCache {
50        fs::read(path).ok().and_then(|b| serde_json::from_slice(&b).ok()).unwrap_or_default()
51    }
52
53    pub fn save(&self, path: &Path) -> io::Result<()> {
54        fs::write(path, serde_json::to_vec(self).map_err(io::Error::other)?)
55    }
56
57    /// The entry for `id` if it still matches the file's size and mtime;
58    /// otherwise a fresh one replaces it.
59    fn entry(&mut self, id: &str, size: u64, mtime: u64) -> &mut CacheEntry {
60        let e = self.entries.entry(id.to_string()).or_insert(CacheEntry { size, mtime, content: None, perceptual: None });
61        if e.size != size || e.mtime != mtime {
62            *e = CacheEntry { size, mtime, content: None, perceptual: None };
63        }
64        e
65    }
66}
67
68/// Size and mtime (ms) of a file.
69fn stamp(path: &Path) -> Option<(u64, u64)> {
70    let m = fs::metadata(path).ok()?;
71    let mtime = m.modified().ok()?.duration_since(UNIX_EPOCH).ok()?.as_millis() as u64;
72    Some((m.len(), mtime))
73}
74
75/// Puts each group's ids in library order and orders the groups by their
76/// first member.
77fn tidy(mut groups: Vec<Vec<String>>, order: &HashMap<&str, usize>) -> Vec<Vec<String>> {
78    for g in &mut groups {
79        g.sort_by_key(|id| order.get(id.as_str()).copied().unwrap_or(usize::MAX));
80    }
81    groups.retain(|g| g.len() > 1);
82    groups.sort_by_key(|g| order.get(g[0].as_str()).copied().unwrap_or(usize::MAX));
83    groups
84}
85
86/// Items not in the trash, and among `only` when given.
87fn live<'a>(lib: &'a Library, only: Option<&HashSet<String>>) -> Vec<&'a Item> {
88    lib.items().iter().filter(|i| !i.is_deleted && only.is_none_or(|o| o.contains(&i.id))).collect()
89}
90
91/// Groups of items (not in the trash) whose originals are byte-identical.
92pub fn find_exact_duplicates(lib: &Library) -> Vec<Vec<String>> {
93    find_exact_duplicates_cached(lib, &mut HashCache::default())
94}
95
96/// [`find_exact_duplicates`] with a cache. Only files that share their size
97/// with another file are hashed.
98pub fn find_exact_duplicates_cached(lib: &Library, cache: &mut HashCache) -> Vec<Vec<String>> {
99    find_exact_duplicates_in(lib, None, cache)
100}
101
102/// [`find_exact_duplicates_cached`] among the items in `only` (all live
103/// items when `None`), as Eagle scans the selection or the current list.
104pub fn find_exact_duplicates_in(lib: &Library, only: Option<&HashSet<String>>, cache: &mut HashCache) -> Vec<Vec<String>> {
105    let items = live(lib, only);
106    let order: HashMap<&str, usize> = items.iter().enumerate().map(|(n, i)| (i.id.as_str(), n)).collect();
107    let mut by_size: HashMap<u64, Vec<(&Item, u64)>> = HashMap::new();
108    for item in &items {
109        if let Some((size, mtime)) = stamp(&item.original_path(lib.root())) {
110            by_size.entry(size).or_default().push((item, mtime));
111        }
112    }
113    let mut by_hash: HashMap<String, Vec<String>> = HashMap::new();
114    for (size, group) in by_size.into_iter().filter(|(_, g)| g.len() > 1) {
115        for (item, mtime) in group {
116            let e = cache.entry(&item.id, size, mtime);
117            if e.content.is_none() {
118                e.content = content_hash(&item.original_path(lib.root())).ok();
119            }
120            if let Some(h) = e.content.clone() {
121                by_hash.entry(h).or_default().push(item.id.clone());
122            }
123        }
124    }
125    tidy(by_hash.into_values().collect(), &order)
126}
127
128/// A 64-bit perceptual hash (pHash): the image is reduced to 32×32 grey,
129/// transformed with a 2-D DCT, and each of the 8×8 lowest frequencies
130/// becomes a bit, set when it is above their median (the DC term excluded
131/// from the median).
132pub fn perceptual_hash(img: &DynamicImage) -> u64 {
133    const N: usize = 32;
134    let grey = img.resize_exact(N as u32, N as u32, FilterType::Triangle).to_luma8();
135    let px: Vec<f64> = grey.pixels().map(|p| f64::from(p.0[0])).collect();
136    let cos: Vec<f64> = (0..8 * N)
137        .map(|i| {
138            let (u, x) = (i / N, i % N);
139            ((2 * x + 1) as f64 * u as f64 * std::f64::consts::PI / (2 * N) as f64).cos()
140        })
141        .collect();
142    // Rows first, keeping only the 8 lowest frequencies, then columns.
143    let mut rows = vec![0.0; N * 8];
144    for y in 0..N {
145        for u in 0..8 {
146            rows[y * 8 + u] = (0..N).map(|x| px[y * N + x] * cos[u * N + x]).sum();
147        }
148    }
149    let mut coeffs = [0.0f64; 64];
150    for v in 0..8 {
151        for u in 0..8 {
152            coeffs[v * 8 + u] = (0..N).map(|y| rows[y * 8 + u] * cos[v * N + y]).sum();
153        }
154    }
155    let mut ac: Vec<f64> = coeffs[1..].to_vec();
156    ac.sort_by(f64::total_cmp);
157    let median = (ac[31] + ac[32]) / 2.0;
158    coeffs.iter().enumerate().fold(0u64, |h, (i, &c)| if c > median { h | (1 << i) } else { h })
159}
160
161/// Number of differing bits.
162pub fn hamming(a: u64, b: u64) -> u32 {
163    (a ^ b).count_ones()
164}
165
166/// The picture a perceptual hash is taken from: the thumbnail, or the
167/// original for small images shown without one.
168fn picture(item: &Item, root: &Path) -> Option<(std::path::PathBuf, DynamicImage)> {
169    let path = item.thumbnail_path(root).or_else(|| {
170        let o = item.original_path(root);
171        (thumbnail::is_supported(&item.ext) && item.ext != "svg").then_some(o)
172    })?;
173    let img = thumbnail::decode(&path).ok()?;
174    Some((path, img))
175}
176
177/// Groups of items whose pictures' perceptual hashes are at most
178/// `threshold` bits apart (about 10 suits resized or recompressed copies).
179/// Groups are linked transitively.
180pub fn find_near_duplicates(lib: &Library, threshold: u32) -> Vec<Vec<String>> {
181    find_near_duplicates_cached(lib, threshold, &mut HashCache::default())
182}
183
184/// [`find_near_duplicates`] with a cache. Entries are keyed on the
185/// original's size and mtime, like the content hash, since a thumbnail
186/// only changes with its original.
187pub fn find_near_duplicates_cached(lib: &Library, threshold: u32, cache: &mut HashCache) -> Vec<Vec<String>> {
188    find_near_duplicates_in(lib, None, threshold, cache)
189}
190
191/// [`find_near_duplicates_cached`] among the items in `only`; items
192/// outside it never link two groups together.
193pub fn find_near_duplicates_in(lib: &Library, only: Option<&HashSet<String>>, threshold: u32, cache: &mut HashCache) -> Vec<Vec<String>> {
194    let items = live(lib, only);
195    let order: HashMap<&str, usize> = items.iter().enumerate().map(|(n, i)| (i.id.as_str(), n)).collect();
196    let mut hashes: Vec<(&str, u64)> = Vec::new();
197    for item in &items {
198        let Some((size, mtime)) = stamp(&item.original_path(lib.root())) else { continue };
199        let e = cache.entry(&item.id, size, mtime);
200        if e.perceptual.is_none() {
201            e.perceptual = picture(item, lib.root()).map(|(_, img)| perceptual_hash(&img));
202        }
203        if let Some(h) = e.perceptual {
204            hashes.push((item.id.as_str(), h));
205        }
206    }
207    tidy(group_close(&hashes, threshold), &order)
208}
209
210/// Links every pair within `threshold` and returns the connected groups.
211pub fn group_close(hashes: &[(&str, u64)], threshold: u32) -> Vec<Vec<String>> {
212    let mut parent: Vec<usize> = (0..hashes.len()).collect();
213    fn root(p: &mut [usize], mut i: usize) -> usize {
214        while p[i] != i {
215            p[i] = p[p[i]];
216            i = p[i];
217        }
218        i
219    }
220    for i in 0..hashes.len() {
221        for j in i + 1..hashes.len() {
222            if hamming(hashes[i].1, hashes[j].1) <= threshold {
223                let (a, b) = (root(&mut parent, i), root(&mut parent, j));
224                parent[a.max(b)] = a.min(b);
225            }
226        }
227    }
228    let mut groups: HashMap<usize, Vec<String>> = HashMap::new();
229    for (i, (id, _)) in hashes.iter().enumerate() {
230        let r = root(&mut parent, i);
231        groups.entry(r).or_default().push(id.to_string());
232    }
233    groups.into_values().collect()
234}
235
236#[cfg(test)]
237mod tests {
238    use super::*;
239    use crate::import::ImportOptions;
240    use image::{Rgb, RgbImage};
241
242    fn scene(w: u32, h: u32) -> DynamicImage {
243        DynamicImage::ImageRgb8(RgbImage::from_fn(w, h, |x, y| {
244            let (fx, fy) = (x as f32 / w as f32, y as f32 / h as f32);
245            let disc = ((fx - 0.3).powi(2) + (fy - 0.4).powi(2)).sqrt() < 0.2;
246            if disc { Rgb([240, 200, 40]) } else { Rgb([(fx * 120.0) as u8, 60, (fy * 200.0) as u8]) }
247        }))
248    }
249
250    fn other(w: u32, h: u32) -> DynamicImage {
251        DynamicImage::ImageRgb8(RgbImage::from_fn(w, h, |x, y| {
252            let stripe = (x / 16 + y / 24) % 2 == 0;
253            if stripe { Rgb([20, 20, 20]) } else { Rgb([230, 240, 250]) }
254        }))
255    }
256
257    #[test]
258    fn perceptual_distances() {
259        let a = perceptual_hash(&scene(400, 300));
260        assert_eq!(hamming(a, perceptual_hash(&scene(400, 300))), 0);
261        let resized = perceptual_hash(&scene(400, 300).resize_exact(173, 130, FilterType::CatmullRom));
262        assert!(hamming(a, resized) <= 4, "resized copy: {}", hamming(a, resized));
263        let far = hamming(a, perceptual_hash(&other(400, 300)));
264        assert!(far >= 20, "unrelated: {far}");
265    }
266
267    #[test]
268    fn grouping() {
269        let g = group_close(&[("a", 0), ("b", 0b11), ("c", 0b1111), ("d", u64::MAX)], 2);
270        let mut g: Vec<Vec<String>> = g.into_iter().map(|mut x| { x.sort(); x }).collect();
271        g.sort();
272        assert_eq!(g, [vec!["a", "b", "c"], vec!["d"]]);
273    }
274
275    #[test]
276    fn finds_duplicates_in_a_library() {
277        let tmp = tempfile::tempdir().unwrap();
278        let mut lib = Library::create(tmp.path().join("D.library")).unwrap();
279        let opts = ImportOptions { palette: false, ..Default::default() };
280        let save = |name: &str, img: &DynamicImage| {
281            let p = tmp.path().join(name);
282            img.save(&p).unwrap();
283            p
284        };
285        let a = lib.import_file(save("a.png", &scene(1200, 900)), &opts).unwrap();
286        let b = lib.import_file(save("b.png", &scene(1200, 900)), &opts).unwrap();
287        let c = lib.import_file(save("c.png", &scene(1000, 750)), &opts).unwrap();
288        let d = lib.import_file(save("d.png", &other(1200, 900)), &opts).unwrap();
289
290        assert_eq!(find_exact_duplicates(&lib), [vec![a.clone(), b.clone()]]);
291        let near = find_near_duplicates(&lib, 10);
292        assert_eq!(near, [vec![a.clone(), b.clone(), c.clone()]]);
293        assert!(!near[0].contains(&d));
294
295        let mut cache = HashCache::default();
296        find_exact_duplicates_cached(&lib, &mut cache);
297        find_near_duplicates_cached(&lib, 10, &mut cache);
298        assert!(cache.entries[&a].perceptual.is_some());
299        let path = tmp.path().join("cache.json");
300        cache.save(&path).unwrap();
301        assert_eq!(HashCache::load(&path), cache);
302    }
303}
falcon_library/duplicates.rs

falcon_library/
duplicates.rs
