oxedyne/fe2o3/fe2o3_hash/tests/fingerprint.rs
8.8 KiB, 5 runs
created by r1870400018:67804, 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 | //! The pinned vectors were worked out by an independent SipHash-1-3-128 written in Python from the |
| 2 | //! paper (the same code gives the reference's published `a3817f04ba25a8e66df67214c7550293` for |
| 3 | //! SipHash-2-4-128 of nothing). A change to one of them is a change to every cache key built on it. |
| 4 | |
| 5 | use oxedyne_fe2o3_hash::fingerprint::Fingerprint; |
| 6 | use oxedyne_fe2o3_hash::fingerprint::Fingerprinter; |
| 7 | use oxedyne_fe2o3_hash::fingerprint::LazyFingerprint; |
| 8 | |
| 9 | use std::cell::Cell; |
| 10 | use std::collections::HashSet; |
| 11 | use std::collections::hash_map::DefaultHasher; |
| 12 | use std::hash::Hash; |
| 13 | use std::hash::Hasher; |
| 14 | |
| 15 | fn hex(b: &[u8]) -> String { Fingerprint::of(b).to_string() } |
| 16 | |
| 17 | fn ramp(n: usize) -> Vec<u8> { (0..n).map(|i| i as u8).collect() } |
| 18 | |
| 19 | #[test] |
| 20 | fn pinned_vectors_of_byte_strings() { |
| 21 | assert_eq!(hex(b""), "013030dd6adb62fdbea58827b2bc7ee7"); |
| 22 | assert_eq!(hex(b"a"), "678aae375dd72f49a84f7c63de373c08"); |
| 23 | assert_eq!(hex(b"abc"), "01d65f4901d5d4b2e81efa46153f7543"); |
| 24 | assert_eq!(hex(&ramp(15)), "09017e1eeccd21296c52bdb205557ec1"); |
| 25 | assert_eq!(hex(&ramp(64)), "c2666aba59a7c84e36a54a4bf2de5312"); |
| 26 | assert_eq!(hex(&ramp(255)), "e93ebbaed065a4f1a558210ac1a428f5"); |
| 27 | } |
| 28 | |
| 29 | #[test] |
| 30 | fn pinned_vector_of_typed_writes() { |
| 31 | // The bytes are 01, 0302, 07060504, 0f0e0d0c0b0a0908, feffffff, 01, 0000c03f, the eight bytes of |
| 32 | // -0.25, fdffffffffffffff, then the length 6 and "h\xc3\xa9llo": 54 bytes, six blocks and a tail of six. |
| 33 | let mut f = Fingerprinter::new(); |
| 34 | f.write_u8(1); |
| 35 | f.write_u16(0x0203); |
| 36 | f.write_u32(0x0405_0607); |
| 37 | f.write_u64(0x0809_0a0b_0c0d_0e0f); |
| 38 | f.write_i32(-2); |
| 39 | f.write_bool(true); |
| 40 | f.write_f32(1.5); |
| 41 | f.write_f64(-0.25); |
| 42 | f.write_i64(-3); |
| 43 | f.write_str("h\u{e9}llo"); |
| 44 | assert_eq!(f.finish().to_string(), "c6b9ca07a4088efab5ba8ddb602e2150"); |
| 45 | } |
| 46 | |
| 47 | #[test] |
| 48 | fn pinned_vector_of_a_nested_part() { |
| 49 | let mut f = Fingerprinter::new(); |
| 50 | f.write_u8(9); |
| 51 | f.nest(|p| { |
| 52 | p.write_str("inner"); |
| 53 | p.write_u32(7); |
| 54 | }); |
| 55 | f.write_u8(10); |
| 56 | assert_eq!(f.finish().to_string(), "6301e3b3ab0b3006845b8494dfc82486"); |
| 57 | |
| 58 | // The part's own fingerprint, written by hand, is the same stream. |
| 59 | let mut part = Fingerprinter::new(); |
| 60 | part.write_str("inner"); |
| 61 | part.write_u32(7); |
| 62 | assert_eq!(part.finish().to_string(), "58c93206e007b54bba1b72eadd64e307"); |
| 63 | let mut g = Fingerprinter::new(); |
| 64 | g.write_u8(9); |
| 65 | g.write_fingerprint(part.finish()); |
| 66 | g.write_u8(10); |
| 67 | assert_eq!(g.finish(), f.finish()); |
| 68 | } |
| 69 | |
| 70 | #[test] |
| 71 | fn a_stream_is_the_same_however_it_is_cut() { |
| 72 | let all = ramp(70); |
| 73 | for n in 0..all.len() { |
| 74 | let whole = Fingerprint::of(&all[..n]); |
| 75 | // Every single cut. |
| 76 | for cut in 0..=n { |
| 77 | let mut f = Fingerprinter::new(); |
| 78 | f.write(&all[..cut]); |
| 79 | f.write(&all[cut..n]); |
| 80 | assert_eq!(f.finish(), whole, "length {} cut at {}", n, cut); |
| 81 | } |
| 82 | // Byte by byte. |
| 83 | let mut f = Fingerprinter::new(); |
| 84 | for b in &all[..n] { |
| 85 | f.write_u8(*b); |
| 86 | } |
| 87 | assert_eq!(f.finish(), whole, "length {} one byte at a time", n); |
| 88 | } |
| 89 | } |
| 90 | |
| 91 | #[test] |
| 92 | fn an_integer_is_its_little_endian_bytes_at_any_offset() { |
| 93 | for skew in 0..9usize { |
| 94 | let pad = ramp(skew); |
| 95 | let mut a = Fingerprinter::new(); |
| 96 | a.write(&pad); |
| 97 | a.write_u64(0x1122_3344_5566_7788); |
| 98 | a.write_u32(0x99aa_bbcc); |
| 99 | a.write_u16(0xddee); |
| 100 | a.write_usize(0x0102_0304); |
| 101 | a.write_i32(-5); |
| 102 | a.write_i64(-6); |
| 103 | a.write_f32(0.5); |
| 104 | a.write_f64(2.5); |
| 105 | a.write_bool(false); |
| 106 | let mut bytes = pad.clone(); |
| 107 | bytes.extend_from_slice(&0x1122_3344_5566_7788u64.to_le_bytes()); |
| 108 | bytes.extend_from_slice(&0x99aa_bbccu32.to_le_bytes()); |
| 109 | bytes.extend_from_slice(&0xddeeu16.to_le_bytes()); |
| 110 | bytes.extend_from_slice(&0x0102_0304u64.to_le_bytes()); |
| 111 | bytes.extend_from_slice(&(-5i32).to_le_bytes()); |
| 112 | bytes.extend_from_slice(&(-6i64).to_le_bytes()); |
| 113 | bytes.extend_from_slice(&0.5f32.to_bits().to_le_bytes()); |
| 114 | bytes.extend_from_slice(&2.5f64.to_bits().to_le_bytes()); |
| 115 | bytes.push(0); |
| 116 | assert_eq!(a.finish(), Fingerprint::of(&bytes), "after {} bytes of padding", skew); |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | #[test] |
| 121 | fn finish_does_not_consume_and_the_stream_goes_on() { |
| 122 | let mut f = Fingerprinter::new(); |
| 123 | f.write(b"abc"); |
| 124 | let first = f.finish(); |
| 125 | assert_eq!(f.finish(), first); |
| 126 | f.write(b"d"); |
| 127 | assert_eq!(first, Fingerprint::of(b"abc")); |
| 128 | assert_eq!(f.finish(), Fingerprint::of(b"abcd")); |
| 129 | } |
| 130 | |
| 131 | #[test] |
| 132 | fn what_is_written_matters_in_value_in_order_and_in_length() { |
| 133 | let two = |a: &str, b: &str| { |
| 134 | let mut f = Fingerprinter::new(); |
| 135 | f.write_str(a); |
| 136 | f.write_str(b); |
| 137 | f.finish() |
| 138 | }; |
| 139 | assert_ne!(two("ab", "c"), two("a", "bc")); |
| 140 | assert_ne!(two("a", "b"), two("b", "a")); |
| 141 | assert_ne!(Fingerprint::of(&[0]), Fingerprint::of(&[0, 0])); |
| 142 | assert_ne!(Fingerprint::of(&[]), Fingerprint::of(&[0])); |
| 143 | let mut p = Fingerprinter::new(); |
| 144 | p.write_f64(f64::NAN); |
| 145 | let mut q = Fingerprinter::new(); |
| 146 | q.write_f64(f64::from_bits(f64::NAN.to_bits() ^ 1)); |
| 147 | assert_ne!(p.finish(), q.finish(), "a float goes by its bits"); |
| 148 | // A part nested is not the same as its writes made flat. |
| 149 | let mut flat = Fingerprinter::new(); |
| 150 | flat.write_u32(7); |
| 151 | let mut nested = Fingerprinter::new(); |
| 152 | nested.nest(|p| p.write_u32(7)); |
| 153 | assert_ne!(flat.finish(), nested.finish()); |
| 154 | } |
| 155 | |
| 156 | #[test] |
| 157 | fn many_distinct_inputs_give_distinct_fingerprints_and_halves() { |
| 158 | let mut all = HashSet::new(); |
| 159 | let mut los = HashSet::new(); |
| 160 | let mut his = HashSet::new(); |
| 161 | for i in 0..200_000u64 { |
| 162 | let mut f = Fingerprinter::new(); |
| 163 | f.write_u64(i); |
| 164 | let fp = f.finish(); |
| 165 | all.insert(fp); |
| 166 | los.insert(fp.as_u128() as u64); |
| 167 | his.insert((fp.as_u128() >> 64) as u64); |
| 168 | } |
| 169 | assert_eq!(all.len(), 200_000); |
| 170 | assert_eq!(los.len(), 200_000); |
| 171 | assert_eq!(his.len(), 200_000); |
| 172 | } |
| 173 | |
| 174 | #[test] |
| 175 | fn a_flipped_input_bit_flips_about_half_the_output_bits() { |
| 176 | let mut total = 0u32; |
| 177 | let runs = 256u32; |
| 178 | for i in 0..runs { |
| 179 | let x = (i as u64).wrapping_mul(0x9e37_79b9_7f4a_7c15); |
| 180 | let mut a = Fingerprinter::new(); |
| 181 | a.write_u64(x); |
| 182 | let mut b = Fingerprinter::new(); |
| 183 | b.write_u64(x ^ (1u64 << (i % 64))); |
| 184 | total += (a.finish().as_u128() ^ b.finish().as_u128()).count_ones(); |
| 185 | } |
| 186 | let mean = total as f64 / runs as f64; |
| 187 | assert!(mean > 56.0 && mean < 72.0, "mean flipped bits {} of 128", mean); |
| 188 | } |
| 189 | |
| 190 | #[test] |
| 191 | fn text_value_halves_and_fold() { |
| 192 | let fp = Fingerprint::from_u128(0x0123_4567_89ab_cdef_fedc_ba98_7654_3210); |
| 193 | assert_eq!(fp.to_string(), "0123456789abcdeffedcba9876543210"); |
| 194 | assert_eq!(format!("{:?}", fp), "Fingerprint(0123456789abcdeffedcba9876543210)"); |
| 195 | assert_eq!(fp.as_u128(), 0x0123_4567_89ab_cdef_fedc_ba98_7654_3210); |
| 196 | assert_eq!(fp.fold(), 0x0123_4567_89ab_cdef ^ 0xfedc_ba98_7654_3210); |
| 197 | assert_eq!(Fingerprint::default().as_u128(), 0); |
| 198 | assert!(Fingerprint::from_u128(1) < Fingerprint::from_u128(1 << 64)); |
| 199 | } |
| 200 | |
| 201 | #[test] |
| 202 | fn xor_folds_a_set_in_any_order() { |
| 203 | let (a, b, c) = (Fingerprint::of(b"a"), Fingerprint::of(b"b"), Fingerprint::of(b"c")); |
| 204 | let mut one = Fingerprint::default(); |
| 205 | for x in [a, b, c] { one ^= x; } |
| 206 | let mut two = Fingerprint::default(); |
| 207 | for x in [c, a, b] { two ^= x; } |
| 208 | assert_eq!(one, two); |
| 209 | assert_eq!(one, a ^ b ^ c); |
| 210 | assert_eq!(one.as_u128(), a.as_u128() ^ b.as_u128() ^ c.as_u128()); |
| 211 | assert_ne!(one, a ^ b); |
| 212 | } |
| 213 | |
| 214 | #[test] |
| 215 | fn equal_fingerprints_hash_alike() { |
| 216 | let h = |fp: Fingerprint| { |
| 217 | let mut s = DefaultHasher::new(); |
| 218 | fp.hash(&mut s); |
| 219 | s.finish() |
| 220 | }; |
| 221 | assert_eq!(h(Fingerprint::of(b"x")), h(Fingerprint::of(b"x"))); |
| 222 | assert_ne!(h(Fingerprint::of(b"x")), h(Fingerprint::of(b"y"))); |
| 223 | } |
| 224 | |
| 225 | #[test] |
| 226 | fn a_lazy_fingerprint_is_worked_out_once() { |
| 227 | let calls = Cell::new(0); |
| 228 | let lazy = LazyFingerprint::new(); |
| 229 | assert_eq!(lazy.get(), None); |
| 230 | let work = || { |
| 231 | calls.set(calls.get() + 1); |
| 232 | Fingerprint::of(b"work") |
| 233 | }; |
| 234 | let a = lazy.get_or_init(work); |
| 235 | let b = lazy.get_or_init(work); |
| 236 | assert_eq!(a, Fingerprint::of(b"work")); |
| 237 | assert_eq!(a, b); |
| 238 | assert_eq!(calls.get(), 1); |
| 239 | assert_eq!(lazy.get(), Some(a)); |
| 240 | } |
| 241 | |
| 242 | #[test] |
| 243 | fn a_clone_of_a_lazy_fingerprint_is_empty_so_a_changed_clone_is_never_stale() { |
| 244 | // A value with a fingerprint cached beside it. |
| 245 | #[derive(Clone, Default)] |
| 246 | struct Value { |
| 247 | text: String, |
| 248 | fp: LazyFingerprint, |
| 249 | } |
| 250 | impl Value { |
| 251 | fn fingerprint(&self) -> Fingerprint { self.fp.get_or_init(|| Fingerprint::of(self.text.as_bytes())) } |
| 252 | } |
| 253 | let a = Value { text: "before".to_string(), fp: LazyFingerprint::new() }; |
| 254 | let before = a.fingerprint(); |
| 255 | let mut b = a.clone(); |
| 256 | assert_eq!(b.fp.get(), None, "the clone starts empty"); |
| 257 | b.text.push_str(" and after"); |
| 258 | assert_ne!(b.fingerprint(), before, "the changed clone reads its own text"); |
| 259 | assert_eq!(a.fingerprint(), before, "the original is untouched"); |
| 260 | |
| 261 | // A value changed in place clears its own. |
| 262 | let mut c = a.clone(); |
| 263 | let first = c.fingerprint(); |
| 264 | c.text = "changed".to_string(); |
| 265 | assert_eq!(c.fingerprint(), first, "nothing told the cell, so it still holds the old one"); |
| 266 | c.fp.clear(); |
| 267 | assert_ne!(c.fingerprint(), first); |
| 268 | } |
| 269 | |
| 270 | #[test] |
| 271 | fn a_lazy_fingerprint_takes_no_part_in_equality_hashing_or_debug_output() { |
| 272 | let a = LazyFingerprint::new(); |
| 273 | let b = LazyFingerprint::new(); |
| 274 | b.get_or_init(|| Fingerprint::of(b"set")); |
| 275 | assert_eq!(a, b); |
| 276 | assert_eq!(format!("{:?}", a), format!("{:?}", b)); |
| 277 | let h = |l: &LazyFingerprint| { |
| 278 | let mut s = DefaultHasher::new(); |
| 279 | l.hash(&mut s); |
| 280 | s.finish() |
| 281 | }; |
| 282 | assert_eq!(h(&a), h(&b)); |
| 283 | } |