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 | |
| 10 | use std::fmt; |
| 11 | use std::hash::Hash; |
| 12 | use std::hash::Hasher; |
| 13 | use std::ops::BitXor; |
| 14 | use std::ops::BitXorAssign; |
| 15 | use std::sync::OnceLock; |
| 16 | |
| 17 | // The reference test key of the SipHash paper. |
| 18 | const K0: u64 = 0x0706_0504_0302_0100; |
| 19 | const 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)] |
| 23 | pub struct Fingerprint(u128); |
| 24 | |
| 25 | impl 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. |
| 43 | impl BitXor for Fingerprint { |
| 44 | type Output = Self; |
| 45 | fn bitxor(self, rhs: Self) -> Self { Self(self.0 ^ rhs.0) } |
| 46 | } |
| 47 | |
| 48 | impl BitXorAssign for Fingerprint { |
| 49 | fn bitxor_assign(&mut self, rhs: Self) { self.0 ^= rhs.0; } |
| 50 | } |
| 51 | |
| 52 | impl fmt::Display for Fingerprint { |
| 53 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| 54 | write!(f, "{:032x}", self.0) |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | impl 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. |
| 65 | impl 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)] |
| 74 | pub 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 | |
| 84 | impl Default for Fingerprinter { |
| 85 | fn default() -> Self { Self::new() } |
| 86 | } |
| 87 | |
| 88 | impl 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)] |
| 220 | fn 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)] |
| 233 | pub struct LazyFingerprint { |
| 234 | cell: OnceLock<Fingerprint>, |
| 235 | } |
| 236 | |
| 237 | impl 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 | |
| 251 | impl fmt::Debug for LazyFingerprint { |
| 252 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.write_str("LazyFingerprint") } |
| 253 | } |
| 254 | |
| 255 | impl Clone for LazyFingerprint { |
| 256 | fn clone(&self) -> Self { Self::new() } |
| 257 | } |
| 258 | |
| 259 | impl PartialEq for LazyFingerprint { |
| 260 | fn eq(&self, _: &Self) -> bool { true } |
| 261 | } |
| 262 | |
| 263 | impl Eq for LazyFingerprint {} |
| 264 | |
| 265 | impl Hash for LazyFingerprint { |
| 266 | fn hash<H: Hasher>(&self, _: &mut H) {} |
| 267 | } |