Oregami
Repositories/oxedyne/fe2o3

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
5use oxedyne_fe2o3_hash::fingerprint::Fingerprint;
6use oxedyne_fe2o3_hash::fingerprint::Fingerprinter;
7use oxedyne_fe2o3_hash::fingerprint::LazyFingerprint;
8
9use std::cell::Cell;
10use std::collections::HashSet;
11use std::collections::hash_map::DefaultHasher;
12use std::hash::Hash;
13use std::hash::Hasher;
14
15fn hex(b: &[u8]) -> String { Fingerprint::of(b).to_string() }
16
17fn ramp(n: usize) -> Vec<u8> { (0..n).map(|i| i as u8).collect() }
18
19#[test]
20fn 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]
30fn 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]
48fn 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]
71fn 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]
92fn 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]
121fn 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]
132fn 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]
157fn 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]
175fn 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]
191fn 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]
202fn 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]
215fn 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]
226fn 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]
243fn 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]
271fn 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}