c2pa_text_binding/
simhash.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! `com.writerslogic.text-fingerprint.1` — a durable 256-bit SimHash over the
4//! normalized surface stream, plus overlapping window fingerprints so an
5//! excerpt or truncated copy still matches. Embeds nothing in the text.
6//!
7//! Value: 32-byte SimHash, hex-encoded. Two values identify the same content
8//! when their Hamming distance is at most 32 / 256 (12.5%).
9
10use crate::normalize::canonical;
11use blake2::{Blake2b512, Digest};
12use std::collections::HashMap;
13
14/// Fingerprint width in bits.
15pub const FP_BITS: usize = 256;
16/// Whole-document / window match threshold: Hamming distance in bits.
17pub const MATCH_THRESHOLD: u32 = 32;
18/// Window length in normalized characters.
19pub const WINDOW_CHARS: usize = 512;
20/// Window step (50% overlap).
21pub const WINDOW_STEP: usize = 256;
22
23/// A 256-bit locality-sensitive hash.
24#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub struct Hash256(pub [u8; 32]);
26
27impl Hash256 {
28    /// Hamming distance in bits (0 = identical, 256 = opposite).
29    pub fn hamming(&self, other: &Self) -> u32 {
30        self.0
31            .iter()
32            .zip(other.0.iter())
33            .map(|(a, b)| (a ^ b).count_ones())
34            .sum()
35    }
36
37    /// Lowercase hex encoding of the 32 bytes.
38    pub fn to_hex(&self) -> String {
39        hex::encode(self.0)
40    }
41
42    /// Parse from a 64-character hex string.
43    pub fn from_hex(s: &str) -> Option<Self> {
44        let bytes = hex::decode(s).ok()?;
45        if bytes.len() != 32 {
46            return None;
47        }
48        let mut out = [0u8; 32];
49        out.copy_from_slice(&bytes);
50        Some(Hash256(out))
51    }
52}
53
54/// BLAKE2b-256 (first 32 bytes of BLAKE2b-512) of arbitrary bytes.
55pub(crate) fn blake2_256(bytes: &[u8]) -> [u8; 32] {
56    let mut h = Blake2b512::new();
57    h.update(bytes);
58    let digest = h.finalize();
59    let mut out = [0u8; 32];
60    out.copy_from_slice(&digest[..32]);
61    out
62}
63
64/// tf-weighted 256-bit SimHash over a bag of features, each a byte string with
65/// an integer weight. Shared by the surface and structural fingerprints.
66pub(crate) fn simhash_weighted<'a, I>(features: I) -> Hash256
67where
68    I: IntoIterator<Item = (&'a [u8], i64)>,
69{
70    let mut acc = [0i64; FP_BITS];
71    for (bytes, weight) in features {
72        let h = blake2_256(bytes);
73        for (bit, slot) in acc.iter_mut().enumerate() {
74            let set = (h[bit / 8] >> (7 - (bit % 8))) & 1 == 1;
75            *slot += if set { weight } else { -weight };
76        }
77    }
78    let mut out = [0u8; 32];
79    for (bit, &count) in acc.iter().enumerate() {
80        if count > 0 {
81            out[bit / 8] |= 1 << (7 - (bit % 8));
82        }
83    }
84    Hash256(out)
85}
86
87/// tf-weighted SimHash over overlapping character 4-grams of `chars`.
88fn simhash_4grams(chars: &[char]) -> Hash256 {
89    if chars.is_empty() {
90        return Hash256([0u8; 32]);
91    }
92    let n = 4.min(chars.len());
93    let mut counts: HashMap<String, i64> = HashMap::new();
94    for gram in chars.windows(n) {
95        let key: String = gram.iter().collect();
96        *counts.entry(key).or_insert(0) += 1;
97    }
98    simhash_weighted(counts.iter().map(|(k, w)| (k.as_bytes(), *w)))
99}
100
101/// A window fingerprint scoped by its `(start, len)` over the normalized stream.
102#[derive(Clone, Debug)]
103pub struct WindowFp {
104    pub start: usize,
105    pub len: usize,
106    pub hash: Hash256,
107}
108
109/// A whole-document fingerprint plus overlapping window fingerprints.
110#[derive(Clone, Debug)]
111pub struct Fingerprint {
112    pub whole: Hash256,
113    pub windows: Vec<WindowFp>,
114}
115
116impl Fingerprint {
117    /// Compute the fingerprint of `text`.
118    pub fn compute(text: &str) -> Self {
119        let norm = canonical(text);
120        let chars: Vec<char> = norm.chars().collect();
121        let whole = simhash_4grams(&chars);
122        let mut windows = Vec::new();
123        if chars.len() > WINDOW_CHARS {
124            let mut start = 0;
125            loop {
126                let end = (start + WINDOW_CHARS).min(chars.len());
127                windows.push(WindowFp {
128                    start,
129                    len: end - start,
130                    hash: simhash_4grams(&chars[start..end]),
131                });
132                if end == chars.len() {
133                    break;
134                }
135                start += WINDOW_STEP;
136            }
137        }
138        Fingerprint { whole, windows }
139    }
140
141    /// The best (smallest) Hamming distance from `candidate`'s whole-document
142    /// hash to this fingerprint's whole hash or any of its window hashes.
143    pub fn best_distance(&self, candidate: &Hash256) -> u32 {
144        let mut best = self.whole.hamming(candidate);
145        for w in &self.windows {
146            best = best.min(w.hash.hamming(candidate));
147        }
148        best
149    }
150
151    /// Whether `candidate`'s whole-document hash matches this fingerprint
152    /// (whole or any window) within [`MATCH_THRESHOLD`].
153    pub fn matches(&self, candidate: &Hash256) -> bool {
154        self.best_distance(candidate) <= MATCH_THRESHOLD
155    }
156}
157
158#[cfg(test)]
159mod tests {
160    use super::*;
161
162    const LONG: &str = "The principles of provenance require that a document's origin \
163        can be recovered even after it has been copied, reformatted, or lightly edited. \
164        A soft binding derives a durable value from the words themselves so that a \
165        manifest can be found again when the embedded one is stripped away by a careless \
166        copy-paste or an aggressive text pipeline that normalizes everything in sight.";
167
168    #[test]
169    fn identical_text_zero_distance() {
170        let a = Fingerprint::compute(LONG);
171        let b = Fingerprint::compute(LONG);
172        assert_eq!(a.whole.hamming(&b.whole), 0);
173    }
174
175    #[test]
176    fn reformatting_and_zero_width_survive() {
177        let a = Fingerprint::compute(LONG);
178        let reformatted = format!("  {}  ", LONG.to_uppercase().replace(' ', "\u{200B} "));
179        let b = Fingerprint::compute(&reformatted);
180        assert_eq!(
181            a.whole.hamming(&b.whole),
182            0,
183            "case + whitespace + zero-width must not change the fingerprint"
184        );
185    }
186
187    #[test]
188    fn single_word_edit_stays_within_threshold() {
189        let a = Fingerprint::compute(LONG);
190        let edited = LONG.replacen("copied", "duplicated", 1);
191        let b = Fingerprint::compute(&edited);
192        let d = a.whole.hamming(&b.whole);
193        assert!(
194            d <= MATCH_THRESHOLD,
195            "single-word edit distance {d} exceeded threshold"
196        );
197    }
198
199    #[test]
200    fn different_documents_diverge() {
201        let a = Fingerprint::compute(LONG);
202        let other = Fingerprint::compute(
203            "Chocolate chip cookies require flour, sugar, butter, eggs, and vanilla; \
204             preheat the oven to three hundred and fifty degrees before mixing anything.",
205        );
206        assert!(
207            a.whole.hamming(&other.whole) > MATCH_THRESHOLD,
208            "unrelated documents must exceed the match threshold"
209        );
210    }
211
212    #[test]
213    fn windows_present_for_long_text() {
214        let big = LONG.repeat(4);
215        let fp = Fingerprint::compute(&big);
216        assert!(
217            !fp.windows.is_empty(),
218            "long text must produce window blocks"
219        );
220        assert!(fp.windows.iter().all(|w| w.len <= WINDOW_CHARS));
221    }
222
223    #[test]
224    fn excerpt_matches_via_window() {
225        let big = LONG.repeat(3);
226        let fp = Fingerprint::compute(&big);
227        // Take a middle excerpt of the source words.
228        let excerpt: String = big.chars().skip(400).take(500).collect();
229        let ex = Fingerprint::compute(&excerpt);
230        assert!(
231            fp.matches(&ex.whole),
232            "an excerpt should match one of the window fingerprints"
233        );
234    }
235
236    #[test]
237    fn hex_roundtrip() {
238        let fp = Fingerprint::compute(LONG);
239        let hex = fp.whole.to_hex();
240        assert_eq!(hex.len(), 64);
241        assert_eq!(Hash256::from_hex(&hex), Some(fp.whole));
242    }
243
244    // Pinned test vector: fixed input -> fixed 256-bit value. Guards against
245    // any change to normalization, the n-gram scheme, or the hash.
246    #[test]
247    fn vector_whole_fingerprint() {
248        let fp = Fingerprint::compute("The quick brown fox jumps over the lazy dog.");
249        assert_eq!(
250            fp.whole.to_hex(),
251            "aa53230a3df3561f2f6d00bdd84907a5b628d2c694a445656620152bcad0d274",
252            "PIN: recompute and update this vector only on an intentional algorithm change"
253        );
254    }
255}
c2pa_text_binding/simhash.rs

c2pa_text_binding/
simhash.rs
