Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_hash/src/fingerprint.rs

7.9 KiB, 6 runs

created by r1870400018:67802, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Content fingerprints, the 128 bit keys of an incremental cache.
2//!
3//! A [`Fingerprinter`] is SipHash-1-3 with its 128 bit output under a fixed key (the reference
4//! test key, bytes `00` to `0f`), so a fingerprint is the same on every run, platform and release;
5//! the pinned vectors in `tests/fingerprint.rs` are the promise. It is not a cryptographic hash.
6//! A fingerprint stands for a stream of bytes however the stream was cut into writes, and every
7//! integer is written little-endian at its own width, so `usize` is eight bytes on a 32 bit target
8//! too.
9
10use std::fmt;
11use std::hash::Hash;
12use std::hash::Hasher;
13use std::ops::BitXor;
14use std::ops::BitXorAssign;
15use std::sync::OnceLock;
16
17// The reference test key of the SipHash paper.
18const K0: u64 = 0x0706_0504_0302_0100;
19const K1: u64 = 0x0f0e_0d0c_0b0a_0908;
20
21/// A 128 bit content fingerprint. Its text form is the 32 hex digits of the value, `hi` first.
22#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord)]
23pub struct Fingerprint(u128);
24
25impl Fingerprint {
26 pub const fn from_u128(v: u128) -> Self { Self(v) }
27
28 pub const fn as_u128(self) -> u128 { self.0 }
29
30 /// The fingerprint of a byte string.
31 pub fn of(bytes: &[u8]) -> Self {
32 let mut f = Fingerprinter::new();
33 f.write(bytes);
34 f.finish()
35 }
36
37 /// The halves xored into 64 bits, for a key that must stay a `u64`. A caller that can hold the
38 /// whole fingerprint should.
39 pub const fn fold(self) -> u64 { (self.0 as u64) ^ ((self.0 >> 64) as u64) }
40}
41
42// Xor folds the fingerprints of a set whose order does not matter, each element appearing once.
43impl BitXor for Fingerprint {
44 type Output = Self;
45 fn bitxor(self, rhs: Self) -> Self { Self(self.0 ^ rhs.0) }
46}
47
48impl BitXorAssign for Fingerprint {
49 fn bitxor_assign(&mut self, rhs: Self) { self.0 ^= rhs.0; }
50}
51
52impl fmt::Display for Fingerprint {
53 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
54 write!(f, "{:032x}", self.0)
55 }
56}
57
58impl fmt::Debug for Fingerprint {
59 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
60 write!(f, "Fingerprint({:032x})", self.0)
61 }
62}
63
64// The value is already uniform, so one half is the whole hash a map needs.
65impl Hash for Fingerprint {
66 fn hash<H: Hasher>(&self, state: &mut H) {
67 state.write_u64(self.0 as u64);
68 }
69}
70
71/// A streaming fingerprint builder. A write of an integer is a write of its little-endian bytes,
72/// and a float goes by its bit pattern, so `NaN` is not folded to one value.
73#[derive(Clone, Debug)]
74pub struct Fingerprinter {
75 v0: u64,
76 v1: u64,
77 v2: u64,
78 v3: u64,
79 tail: u64, // Bytes waiting for a full block, little-endian.
80 ntail: u32, // How many of them, 0 to 7.
81 len: u64, // Bytes written.
82}
83
84impl Default for Fingerprinter {
85 fn default() -> Self { Self::new() }
86}
87
88impl Fingerprinter {
89 pub fn new() -> Self {
90 Self {
91 v0: K0 ^ 0x736f_6d65_7073_6575,
92 v1: K1 ^ 0x646f_7261_6e64_6f6d ^ 0xee, // The 128 bit output mode.
93 v2: K0 ^ 0x6c79_6765_6e65_7261,
94 v3: K1 ^ 0x7465_6462_7974_6573,
95 tail: 0,
96 ntail: 0,
97 len: 0,
98 }
99 }
100
101 #[inline(always)]
102 fn round(&mut self) {
103 self.v0 = self.v0.wrapping_add(self.v1);
104 self.v1 = self.v1.rotate_left(13) ^ self.v0;
105 self.v0 = self.v0.rotate_left(32);
106 self.v2 = self.v2.wrapping_add(self.v3);
107 self.v3 = self.v3.rotate_left(16) ^ self.v2;
108 self.v0 = self.v0.wrapping_add(self.v3);
109 self.v3 = self.v3.rotate_left(21) ^ self.v0;
110 self.v2 = self.v2.wrapping_add(self.v1);
111 self.v1 = self.v1.rotate_left(17) ^ self.v2;
112 self.v2 = self.v2.rotate_left(32);
113 }
114
115 #[inline(always)]
116 fn block(&mut self, m: u64) {
117 self.v3 ^= m;
118 self.round();
119 self.v0 ^= m;
120 }
121
122 // Appends the low `n` bytes of `v`, 1 to 8 of them, the bytes above being zero.
123 #[inline(always)]
124 fn push(&mut self, v: u64, n: u32) {
125 self.len = self.len.wrapping_add(n as u64);
126 let have = self.ntail;
127 let t = self.tail | (v << (8 * have));
128 if have + n < 8 {
129 self.tail = t;
130 self.ntail = have + n;
131 return;
132 }
133 self.block(t);
134 let used = 8 - have;
135 self.ntail = n - used;
136 self.tail = if used < 8 { v >> (8 * used) } else { 0 };
137 }
138
139 pub fn write_u8(&mut self, v: u8) { self.push(v as u64, 1); }
140 pub fn write_u16(&mut self, v: u16) { self.push(v as u64, 2); }
141 pub fn write_u32(&mut self, v: u32) { self.push(v as u64, 4); }
142 pub fn write_i32(&mut self, v: i32) { self.write_u32(v as u32); }
143 pub fn write_i64(&mut self, v: i64) { self.write_u64(v as u64); }
144 pub fn write_usize(&mut self, v: usize) { self.write_u64(v as u64); }
145 pub fn write_bool(&mut self, v: bool) { self.push(v as u64, 1); }
146 pub fn write_f32(&mut self, v: f32) { self.write_u32(v.to_bits()); }
147 pub fn write_f64(&mut self, v: f64) { self.write_u64(v.to_bits()); }
148
149 pub fn write_u64(&mut self, v: u64) {
150 if self.ntail == 0 {
151 self.len = self.len.wrapping_add(8);
152 self.block(v);
153 } else {
154 self.push(v, 8);
155 }
156 }
157
158 pub fn write(&mut self, bytes: &[u8]) {
159 let mut rest = bytes;
160 if rest.is_empty() {
161 return;
162 }
163 if self.ntail != 0 {
164 let n = ((8 - self.ntail) as usize).min(rest.len());
165 let (a, b) = rest.split_at(n);
166 self.push(le_word(a), n as u32);
167 rest = b;
168 }
169 let mut chunks = rest.chunks_exact(8);
170 for c in &mut chunks {
171 self.len = self.len.wrapping_add(8);
172 self.block(le_word(c));
173 }
174 let more = chunks.remainder();
175 if !more.is_empty() {
176 self.push(le_word(more), more.len() as u32);
177 }
178 }
179
180 /// Writes the length, then the bytes, so "ab" then "c" differs from "a" then "bc".
181 pub fn write_str(&mut self, s: &str) {
182 self.write_u64(s.len() as u64);
183 self.write(s.as_bytes());
184 }
185
186 /// Writes the 16 bytes of a fingerprint that stands for a part already hashed.
187 pub fn write_fingerprint(&mut self, fp: Fingerprint) {
188 self.write_u64(fp.0 as u64);
189 self.write_u64((fp.0 >> 64) as u64);
190 }
191
192 /// Hashes what `f` writes on its own, then writes that fingerprint here. A part is then the
193 /// same 16 bytes to its parent however long it is, and can be hashed once and reused.
194 pub fn nest<F: FnOnce(&mut Fingerprinter)>(&mut self, f: F) {
195 let mut part = Fingerprinter::new();
196 f(&mut part);
197 self.write_fingerprint(part.finish());
198 }
199
200 /// The fingerprint of everything written so far. The builder is not consumed, so it can go on.
201 pub fn finish(&self) -> Fingerprint {
202 let mut s = self.clone();
203 s.block((s.len << 56) | s.tail);
204 s.v2 ^= 0xee;
205 s.round();
206 s.round();
207 s.round();
208 let lo = s.v0 ^ s.v1 ^ s.v2 ^ s.v3;
209 s.v1 ^= 0xdd;
210 s.round();
211 s.round();
212 s.round();
213 let hi = s.v0 ^ s.v1 ^ s.v2 ^ s.v3;
214 Fingerprint(((hi as u128) << 64) | (lo as u128))
215 }
216}
217
218// Up to eight bytes as one little-endian word.
219#[inline(always)]
220fn le_word(b: &[u8]) -> u64 {
221 let mut w = 0u64;
222 for (i, x) in b.iter().enumerate() {
223 w |= (*x as u64) << (8 * i);
224 }
225 w
226}
227
228/// A fingerprint worked out on first use and kept. It is a cache beside a value, not a part of
229/// it, so cloning gives an empty cell, and it takes no part in equality, hashing or debug output
230/// (which would otherwise differ with whether the fingerprint had been read). A value that is
231/// cloned and then changed therefore never reads the fingerprint of what it was.
232#[derive(Default)]
233pub struct LazyFingerprint {
234 cell: OnceLock<Fingerprint>,
235}
236
237impl LazyFingerprint {
238 pub const fn new() -> Self { Self { cell: OnceLock::new() } }
239
240 pub fn get(&self) -> Option<Fingerprint> { self.cell.get().copied() }
241
242 /// The kept fingerprint, worked out by `f` if there is none yet.
243 pub fn get_or_init<F: FnOnce() -> Fingerprint>(&self, f: F) -> Fingerprint {
244 *self.cell.get_or_init(f)
245 }
246
247 /// Forgets the fingerprint. A value changed in place must call this.
248 pub fn clear(&mut self) { self.cell.take(); }
249}
250
251impl fmt::Debug for LazyFingerprint {
252 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.write_str("LazyFingerprint") }
253}
254
255impl Clone for LazyFingerprint {
256 fn clone(&self) -> Self { Self::new() }
257}
258
259impl PartialEq for LazyFingerprint {
260 fn eq(&self, _: &Self) -> bool { true }
261}
262
263impl Eq for LazyFingerprint {}
264
265impl Hash for LazyFingerprint {
266 fn hash<H: Hasher>(&self, _: &mut H) {}
267}