sudachi/util/
fxhash.rs

1/*
2 *  Copyright (c) 2021 Works Applications Co., Ltd.
3 *
4 *  Licensed under the Apache License, Version 2.0 (the "License");
5 *  you may not use this file except in compliance with the License.
6 *  You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 *   Unless required by applicable law or agreed to in writing, software
11 *  distributed under the License is distributed on an "AS IS" BASIS,
12 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 *  See the License for the specific language governing permissions and
14 *  limitations under the License.
15 */
16
17// Adopted from: https://github.com/cbreeden/fxhash/blob/master/lib.rs
18// Removed functionality that were useless for us
19// Original Copyright:
20
21// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
22// file at the top-level directory of this distribution and at
23// http://rust-lang.org/COPYRIGHT.
24//
25// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
26// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
27// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
28// option. This file may not be copied, modified, or distributed
29// except according to those terms.
30
31//! # Fx Hash
32//!
33//! This hashing algorithm was extracted from the Rustc compiler.  This is the same hashing
34//! algorithm used for some internal operations in Firefox.  The strength of this algorithm
35//! is in hashing 8 bytes at a time on 64-bit platforms, where the FNV algorithm works on one
36//! byte at a time.
37//!
38//! ## Disclaimer
39//!
40//! It is **not a cryptographically secure** hash, so it is strongly recommended that you do
41//! not use this hash for cryptographic purproses.  Furthermore, this hashing algorithm was
42//! not designed to prevent any attacks for determining collisions which could be used to
43//! potentially cause quadratic behavior in `HashMap`s.  So it is not recommended to expose
44//! this hash in places where collissions or DDOS attacks may be a concern.
45
46use std::convert::TryInto;
47use std::default::Default;
48use std::hash::{BuildHasherDefault, Hasher};
49use std::ops::BitXor;
50
51/// A builder for default Fx hashers.
52pub type FxBuildHasher = BuildHasherDefault<FxHasher64>;
53
54const ROTATE: u32 = 5;
55const SEED64: u64 = 0x51_7c_c1_b7_27_22_0a_95;
56const SEED32: u32 = 0x9e_37_79_b9;
57
58#[cfg(target_pointer_width = "64")]
59const SEED: usize = SEED64 as usize;
60
61trait HashWord {
62    fn hash_word(&mut self, _: Self);
63}
64
65macro_rules! impl_hash_word {
66    ($($ty:ty = $key:ident),* $(,)*) => (
67        $(
68            impl HashWord for $ty {
69                #[inline(always)]
70                fn hash_word(&mut self, word: Self) {
71                    *self = self.rotate_left(ROTATE).bitxor(word).wrapping_mul($key);
72                }
73            }
74        )*
75    )
76}
77
78impl_hash_word!(usize = SEED, u32 = SEED32, u64 = SEED64);
79
80#[inline]
81fn write64(mut hash: u64, mut bytes: &[u8]) -> u64 {
82    while bytes.len() >= 8 {
83        let (data, rem) = bytes.split_at(8);
84        hash.hash_word(u64::from_ne_bytes(data.try_into().unwrap()));
85        bytes = rem;
86    }
87
88    if bytes.len() >= 4 {
89        let (data, rem) = bytes.split_at(4);
90        hash.hash_word(u32::from_ne_bytes(data.try_into().unwrap()) as u64);
91        bytes = rem;
92    }
93
94    if bytes.len() >= 2 {
95        let (data, rem) = bytes.split_at(2);
96        hash.hash_word(u16::from_ne_bytes(data.try_into().unwrap()) as u64);
97        bytes = rem;
98    }
99
100    if let Some(&byte) = bytes.first() {
101        hash.hash_word(u64::from(byte));
102    }
103
104    hash
105}
106
107/// This hashing algorithm was extracted from the Rustc compiler.
108/// This is the same hashing algorithm used for some internal operations in Firefox.
109/// The strength of this algorithm is in hashing 8 bytes at a time on any platform,
110/// where the FNV algorithm works on one byte at a time.
111///
112/// This hashing algorithm should not be used for cryptographic, or in scenarios where
113/// DOS attacks are a concern.
114#[derive(Debug, Clone)]
115pub struct FxHasher64 {
116    hash: u64,
117}
118
119impl Default for FxHasher64 {
120    #[inline]
121    fn default() -> FxHasher64 {
122        FxHasher64 { hash: 0 }
123    }
124}
125
126impl Hasher for FxHasher64 {
127    #[inline]
128    fn finish(&self) -> u64 {
129        self.hash
130    }
131
132    #[inline]
133    fn write(&mut self, bytes: &[u8]) {
134        self.hash = write64(self.hash, bytes);
135    }
136
137    #[inline]
138    fn write_u8(&mut self, i: u8) {
139        self.hash.hash_word(u64::from(i));
140    }
141
142    #[inline]
143    fn write_u16(&mut self, i: u16) {
144        self.hash.hash_word(u64::from(i));
145    }
146
147    #[inline]
148    fn write_u32(&mut self, i: u32) {
149        self.hash.hash_word(u64::from(i));
150    }
151
152    #[inline]
153    fn write_u64(&mut self, i: u64) {
154        self.hash.hash_word(i);
155    }
156
157    #[inline]
158    fn write_usize(&mut self, i: usize) {
159        self.hash.hash_word(i as u64);
160    }
161}
sudachi/util/fxhash.rs

sudachi/util/
fxhash.rs
