1// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! # Fx Hash
12//!
13//! This hashing algorithm was extracted from the Rustc compiler. This is the same hashing
14//! algorithm used for some internal operations in Firefox. The strength of this algorithm
15//! is in hashing 8 bytes at a time on 64-bit platforms, where the FNV algorithm works on one
16//! byte at a time.
17//!
18//! ## Disclaimer
19//!
20//! It is **not a cryptographically secure** hash, so it is strongly recommended that you do
21//! not use this hash for cryptographic purproses. Furthermore, this hashing algorithm was
22//! not designed to prevent any attacks for determining collisions which could be used to
23//! potentially cause quadratic behavior in `HashMap`s. So it is not recommended to expose
24//! this hash in places where collissions or DDOS attacks may be a concern.
25
26use core::convert::TryInto;
27use core::ops::BitXor;
28
29const ROTATE: u32 = 5;
30const SEED64: u64 = 0x517cc1b727220a95;
31const SEED32: u32 = (SEED64 & 0xFFFF_FFFF) as u32;
32
33#[cfg(target_pointer_width = "32")]
34const SEED: usize = SEED32 as usize;
35#[cfg(target_pointer_width = "64")]
36const SEED: usize = SEED64 as usize;
37
38trait HashWord {
39 fn hash_word(&mut self, word: Self);
40}
41
42impl HashWord for usize {
43 #[inline]
44 fn hash_word(&mut self, word: Self) {
45 *self = self.rotate_left(ROTATE).bitxor(word).wrapping_mul(SEED);
46 }
47}
48
49impl HashWord for u32 {
50 #[inline]
51 fn hash_word(&mut self, word: Self) {
52 *self = self.rotate_left(ROTATE).bitxor(word).wrapping_mul(SEED32);
53 }
54}
55
56impl HashWord for u64 {
57 #[inline]
58 fn hash_word(&mut self, word: Self) {
59 *self = self.rotate_left(ROTATE).bitxor(word).wrapping_mul(SEED64);
60 }
61}
62
63#[cfg(target_endian = "little")]
64fn read_u32(buf: &[u8]) -> u32 {
65 u32::from_le_bytes(buf[..4].try_into().unwrap())
66}
67
68#[cfg(target_endian = "little")]
69fn read_u64(buf: &[u8]) -> u64 {
70 u64::from_le_bytes(buf[..8].try_into().unwrap())
71}
72
73#[cfg(target_endian = "big")]
74fn read_u32(buf: &[u8]) -> u32 {
75 u32::from_be_bytes(buf[..4].try_into().unwrap())
76}
77
78#[cfg(target_endian = "big")]
79fn read_u64(buf: &[u8]) -> u64 {
80 u64::from_be_bytes(buf[..8].try_into().unwrap())
81}
82
83#[inline]
84#[cfg(target_pointer_width = "32")]
85fn write(initial_state: usize, mut bytes: &[u8]) -> usize {
86 let mut hash = initial_state as u32;
87 while bytes.len() >= 4 {
88 let n = read_u32(bytes);
89 hash.hash_word(n);
90 bytes = bytes.split_at(4).1;
91 }
92
93 for byte in bytes {
94 hash.hash_word(*byte as u32);
95 }
96 hash as usize
97}
98
99#[inline]
100#[cfg(target_pointer_width = "64")]
101fn write(initial_state: usize, mut bytes: &[u8]) -> usize {
102 let mut hash: u64 = initial_state as u64;
103 while bytes.len() >= 8 {
104 let n: u64 = read_u64(buf:bytes);
105 hash.hash_word(n);
106 bytes = bytes.split_at(mid:8).1;
107 }
108
109 if bytes.len() >= 4 {
110 let n: u32 = read_u32(buf:bytes);
111 hash.hash_word(n as u64);
112 bytes = bytes.split_at(mid:4).1;
113 }
114
115 for byte: &u8 in bytes {
116 hash.hash_word(*byte as u64);
117 }
118 hash as usize
119}
120
121pub fn hash(bytes: &[u8]) -> usize {
122 write(initial_state:0usize, bytes)
123}
124