read_fonts/collections/
fnv.rs

1//! A fork of the `fnv` crate from <https://github.com/servo/rust-fnv>. The code is forked since it
2//! is small and to reduce the maintenance overhead of importing into other monorepos.
3//!
4//! FNV is an implementation of the Fowler–Noll–Vo hash function.
5//!
6//! ## About
7//!
8//! The FNV hash function is a custom `Hasher` implementation that is more
9//! efficient for smaller hash keys.
10//!
11//! The Rust Standard Library documentation states that while the default `Hasher` implementation,
12//! SipHash, is good in many cases, it is notably slower than other algorithms with short keys, such
13//! as when you have a map of integers to other values.  In cases like these, FNV is demonstrably
14//! faster.
15//!
16//! Its disadvantages are that it performs badly on larger inputs, and provides no protection
17//! against collision attacks, where a malicious user can craft specific keys designed to slow a
18//! hasher down. Thus, it is important to profile your program to ensure that you are using small
19//! hash keys, and be certain that your program could not be exposed to malicious inputs (including
20//! being a networked server).
21//!
22//! The Rust compiler itself uses FNV, as it is not worried about denial-of-service attacks, and can
23//! assume that its inputs are going to be small—a perfect use case for FNV.
24use std::hash::{BuildHasherDefault, Hasher};
25
26const INITIAL_STATE: u64 = 0xcbf2_9ce4_8422_2325;
27const PRIME: u64 = 0x0100_0000_01b3;
28
29#[derive(Clone)]
30pub struct FnvHasher(u64);
31
32impl Default for FnvHasher {
33    #[inline]
34    fn default() -> FnvHasher {
35        FnvHasher(INITIAL_STATE)
36    }
37}
38
39impl Hasher for FnvHasher {
40    #[inline]
41    fn finish(&self) -> u64 {
42        self.0
43    }
44
45    #[inline]
46    fn write(&mut self, bytes: &[u8]) {
47        let FnvHasher(mut hash) = *self;
48        for byte in bytes {
49            hash ^= u64::from(*byte);
50            hash = hash.wrapping_mul(PRIME);
51        }
52        *self = FnvHasher(hash);
53    }
54}
55
56pub type FnvBuildHasher = BuildHasherDefault<FnvHasher>;
57pub type FnvHashMap<K, V> = std::collections::HashMap<K, V, FnvBuildHasher>;
58
59#[cfg(test)]
60mod test {
61    use super::*;
62    use std::hash::Hasher;
63
64    fn fnv1a(bytes: &[u8]) -> u64 {
65        let mut hasher = FnvHasher::default();
66        hasher.write(bytes);
67        hasher.finish()
68    }
69
70    #[test]
71    fn basic_tests() {
72        assert_eq!(fnv1a(b""), 0xcbf29ce484222325);
73        assert_eq!(fnv1a(b"a"), 0xaf63dc4c8601ec8c);
74        assert_eq!(fnv1a(b"b"), 0xaf63df4c8601f1a5);
75        assert_eq!(fnv1a(b"c"), 0xaf63de4c8601eff2);
76        assert_eq!(fnv1a(b"d"), 0xaf63d94c8601e773);
77        assert_eq!(fnv1a(b"e"), 0xaf63d84c8601e5c0);
78        assert_eq!(fnv1a(b"f"), 0xaf63db4c8601ead9);
79        assert_eq!(fnv1a(b"fo"), 0x08985907b541d342);
80        assert_eq!(fnv1a(b"foo"), 0xdcb27518fed9d577);
81        assert_eq!(fnv1a(b"foob"), 0xdd120e790c2512af);
82        assert_eq!(fnv1a(b"fooba"), 0xcac165afa2fef40a);
83        assert_eq!(fnv1a(b"foobar"), 0x85944171f73967e8);
84        assert_eq!(fnv1a(b"\0"), 0xaf63bd4c8601b7df);
85        assert_eq!(fnv1a(b"a\0"), 0x089be207b544f1e4);
86        assert_eq!(fnv1a(b"b\0"), 0x08a61407b54d9b5f);
87        assert_eq!(fnv1a(b"c\0"), 0x08a2ae07b54ab836);
88        assert_eq!(fnv1a(b"d\0"), 0x0891b007b53c4869);
89        assert_eq!(fnv1a(b"e\0"), 0x088e4a07b5396540);
90        assert_eq!(fnv1a(b"f\0"), 0x08987c07b5420ebb);
91        assert_eq!(fnv1a(b"fo\0"), 0xdcb28a18fed9f926);
92        assert_eq!(fnv1a(b"foo\0"), 0xdd1270790c25b935);
93    }
94}
read_fonts/collections/fnv.rs

read_fonts/collections/
fnv.rs
