Repository Public License
1<!-- ORIX Clean / File: docs/architecture/duplicates.md / Author: Simon-Pierre Boucher / Contact: contact@spboucher.ai -->2# Duplicates and similar images34Two analyses run on a scanned tree. Exact duplicates are a proof of equality (SHA-256, then a byte comparison5before removal). Similar images are a perceptual judgement and are never treated as equal. Sources:6`DuplicateDetection/DuplicateFinder.swift`, `ImageSimilarity/SimilarImageFinder.swift`.78## Exact duplicates910### Pipeline1112```mermaid13flowchart TD14 Tree[ScanTree regular files] --> Filter[drop empty, dataless, package contents, below minimum size]15 Filter --> Links[names of an already counted inode are attached to it, not compared]16 Links --> BySize[group by logical size, keep groups of 2 or more]17 BySize --> Small{file larger than 48 KiB}18 Small -->|no| Full19 Small -->|yes| Sample[SHA-256 of three 16 KiB windows: head, middle, tail]20 Sample --> Bucket[regroup by size and sample digest]21 Bucket --> Full[streaming SHA-256 of the whole file]22 Full --> Groups[groups of equal size and digest]23 Groups --> Verify[byte-for-byte comparison in the deletion engine before any removal]24```25261. **Candidates by size.** `tree.forEachFile` collects regular files of at least `minimumSize` bytes (default 1;27 the application uses megabytes chosen by the user). Dataless files are skipped. Files inside packages are28 skipped unless `includePackageContents` is set. A node flagged `hardLinkDuplicate` is recorded under its29 file id as another name of the same inode and is not compared.302. **Sampled hash.** For files larger than three sample windows, `sampleHash` reads 16 KiB at the head, the31 middle and the tail with `pread` and hashes them. This only splits size groups cheaply; it never decides.323. **Full hash.** `fullHash` streams the file in 1 MiB chunks through CryptoKit `SHA256`. It opens with33 `O_NOFOLLOW`, requires a regular file, and returns nil if the size differs from the scanned size before or34 after reading, so a file that changed since the scan drops out.354. **Groups.** Files with the same size and digest form a `DuplicateGroup`, with members sorted by path and36 groups sorted by redundant content.375. **Verification at removal.** A duplicate `CleanupItem` carries `verifyAgainst`, the path of the copy that38 stays. `DeletionEngine` calls `identicalContents` (two `pread` streams and `memcmp`) immediately before39 moving the item, and skips it if the copies differ, if the kept copy is gone, if the kept copy is also40 selected, or if both paths are the same inode.4142Both hashing functions set `F_NOCACHE` on the descriptor so that hashing a large tree does not fill the unified43buffer cache.4445### Data structures4647| Type | Content |48|---|---|49| `DuplicateFile` | node index, path, modification date, allocated size, private size, file id, `mayShareBlocks`, clone id, `hardLinkPaths` |50| `DuplicateGroup` | hexadecimal digest, logical size, files; `redundantLogical`, `sharesStorage`, `recoverable(removing:)` |51| `DuplicateResult` | groups, candidate count, bytes hashed, duration, unreadable paths, cancelled |52| `DuplicateProgress` | stage (`grouping`, `sampling`, `hashing`, `done`), files done and total, bytes hashed |5354`redundantLogical` is `logicalSize * (count - 1)`: content held by the extra copies, not space that would be55freed. `sharesStorage` is true when two members have the same non-zero clone id or any member may share56blocks; the interface then says that removing a copy frees little. `recoverable(removing:)` returns a range57per the rules in `storage-accounting.md`.5859### Concurrency6061`parallelMap` starts up to `workers` dedicated threads at `.utility` quality of service. The default is half62the active processor count, clamped between 2 and 6. Workers pull indexes from a shared cursor and write63results into preallocated slots.6465Measured on the sample folder: 685 MB hashed in 0.069 s with 6 threads. This is a **warm-cache** figure: the66files had just been written and were in memory. A cold run is bound by the read speed of the disk, not by67SHA-256.6869### Invariants7071- Two files are in the same group only if their full SHA-256 digests and sizes are equal. The sampled hash72 cannot create a group (test `collisionsInThePreliminaryFilterDoNotCreateFalseGroups` forces every sample to73 collide).74- Hard links of one inode are one file, never a duplicate pair, and are not offered for removal.75- A cancelled run returns no groups.76- The engine never removes the last copy of a group: the kept copy must exist, differ in inode and be77 identical at removal time.7879### Failure handling8081| Situation | Result |82|---|---|83| File cannot be opened or read | Dropped from its group; path listed in `DuplicateResult.unreadable` |84| File changed size since the scan | Full hash returns nil; file dropped |85| Sample read fails | File dropped before full hashing |86| Symlink in place of the file | Refused by `O_NOFOLLOW` |87| Cancel | Workers stop at the next file or chunk; empty result with `cancelled == true` |8889### Not handled9091- Duplicate folders as units; only files are compared.92- Files inside packages by default (parts of an application or a photo library are not independent files).93- Dataless files: comparing them would download them.94- Automatic choice of the copy to keep in the application; the user chooses with "keep only". In a workflow95 the first path of each group, in path order, is kept.96- Link names are attached by file id alone, which is sufficient within one device.9798## Similar images99100### Method101102A 64-bit difference hash is the prefilter and Vision feature prints confirm. Clusters are built around a103representative image; similarity is not chained.104105```mermaid106flowchart TD107 Files[Image files by extension, 8 KiB or more, not dataless, not in packages] --> Thumb[ImageIO thumbnail, 448 px maximum, orientation applied]108 Thumb --> Hash[9 by 8 grey bitmap, 64-bit difference hash]109 Hash --> Pairs{Hamming distance of each pair}110 Pairs -->|4 bits or fewer| Strong[accepted on structure]111 Pairs -->|5 to 12 bits| Vision[Vision feature print distance]112 Pairs -->|more than 12 bits, fast mode| Drop[not similar]113 Pairs -->|more than 12 bits, thorough mode| Crop[Vision distance 0.25 or less]114 Vision -->|0.36 or less| Accept[accepted]115 Vision -->|more| Drop116 Crop --> Accept117 Strong --> Score[scored pairs, best first]118 Accept --> Score119 Score --> Cluster[join a cluster only if similar to its representative]120 Cluster --> Groups[SimilarGroup with confidence]121```122123- **Fingerprint.** `fingerprint` creates a thumbnail with `CGImageSourceCreateThumbnailAtIndex`, draws it into124 a 9 by 8 grey context and compares each pixel with its right neighbour, giving 64 bits. Pixel dimensions come125 from the image properties, swapped for rotated orientations. Fingerprints are computed in parallel.126- **Vision.** `VNGenerateImageFeaturePrintRequest` runs on the same thumbnail with `.scaleFill`; the distance127 is the Euclidean distance between the float vectors, computed with `vDSP_distancesq`. In fast mode the128 vector is computed lazily, only for images that appear in a pair needing it. In thorough mode it is computed129 for every image and every pair is judged, which also finds crops; thorough mode is limited to 3,000 images130 and falls back to fast above that (`SimilarResult.mode` reports the mode actually used).131- **Clustering.** Accepted pairs are sorted by score. The first pair founds a cluster with one image as132 representative. Another image joins only if it has an accepted score with that representative. "A is like133 B and B is like C" does not put A and C together.134- **Confidence.** The weakest link score in the cluster, clamped to 0 through 1. The structural score is135 `1 - bits / 32`; the perceptual score is `1 - distance / 0.72`.136137Supported extensions: jpg, jpeg, png, heic, heif, tiff, tif, gif, bmp, webp. Measured in fast mode on the138sample folder: 31 images in 0.21 s, about 150 images per second.139140### Rules in the application141142- Nothing is preselected. `AppModel.toggleSimilar` refuses to select the last remaining image of a group.143- A selected image is a `review`-risk item whose reason states that similar is not identical.144- There is no byte verification for similar images: they are different files by definition.145146### Failure handling147148- An image that cannot be decoded is counted in `SimilarResult.unreadable` and ignored (test149 `corruptImagesAreCountedNotCrashed`).150- If Vision returns no vector for an image, pairs that need it are rejected.151- A cancelled run returns no groups.152153### Not handled154155- RAW formats, videos, Live Photo pairs and bursts as such.156- Images inside photo libraries and other packages.157- Pair comparison is quadratic in the number of images; there is no index structure.158- Thresholds were chosen on generated test pictures and the sample folder, not on a labelled photo corpus.159