hsieh_hash/
lib.rs

1// The "SuperFastHash" byte sequence hash function
2// Copyright (C) 2003  Paul Hsieh
3// Copyright (C) 2019  Xiphoseer
4//
5// This library is free software; you can redistribute it and/or
6// modify it under the terms of the GNU Lesser General Public
7// License as published by the Free Software Foundation; either
8// version 2.1 of the License, or (at your option) any later version.
9//
10// This library is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13// Lesser General Public License for more details.
14//
15// You should have received a copy of the GNU Lesser General Public
16// License along with this library; if not, write to the Free Software
17// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18
19//! This crate contains the `Hsieh Hash` or `SuperFastHash` function
20//! created by Paul Hsieh and presented at <http://www.azillionmonkeys.com/qed/hash.html>
21//!
22//! ```rust
23//! use hsieh_hash::digest;
24//!
25//! let hash = digest("Hello World!".as_bytes());
26//! assert_eq!(hash, 1774740540);
27//! ```
28//!
29//! The hash value is initialized with the lenght of the input, so
30//! the algorithm cannot be used incrementally.
31
32use core::num::Wrapping;
33
34/// Calculate the Hash of a byte slice
35pub fn digest(mut data: &[u8]) -> u32 {
36    let len: u32 = data.len() as u32;
37    let mut hash: Wrapping<u32> = Wrapping(len);
38
39    if len == 0 {
40        return 0;
41    }
42
43    let remainder = len & 3;
44    let block_count = len >> 2;
45
46    /* Main loop */
47    for _i in 0..block_count {
48        hash += Wrapping(u16::from_le_bytes([data[0], data[1]]) as u32);
49        let temp = Wrapping(u16::from_le_bytes([data[2], data[3]]) as u32) << 11 ^ hash;
50        hash = hash << 16 ^ temp;
51        data = &data[4..];
52        hash += hash >> 11;
53    }
54
55    /* Handle end cases */
56    match remainder {
57        0 => {
58            // Do nothing
59        }
60        1 => {
61            hash += Wrapping(data[0] as u32);
62            hash ^= hash << 10;
63            hash += hash >> 1;
64        },
65        2 => {
66            hash += Wrapping(u16::from_le_bytes([data[0], data[1]]) as u32);
67            hash ^= hash << 11;
68            hash += hash >> 17;
69        },
70        3 => {
71            hash += Wrapping(u16::from_le_bytes([data[0], data[1]]) as u32);
72            hash ^= hash << 16;
73            hash ^= Wrapping(data[2] as u32) << 18;
74            hash += hash >> 11;
75        },
76        _ => {
77            panic!("Please investigate");
78        }
79    }
80
81    /* Force "avalanching" of final 127 bits */
82    hash ^= hash << 3;
83    hash += hash >> 5;
84    hash ^= hash << 4;
85    hash += hash >> 17;
86    hash ^= hash << 25;
87    hash += hash >> 6;
88
89    return hash.0;
90}
91
92#[cfg(test)]
93mod hiesh_tests {
94    use super::digest;
95
96    #[test]
97    fn test_digest() {
98        assert_eq!(digest("Hello World!".as_bytes()), 1774740540);
99        assert_eq!(digest("Hsieh Hash".as_bytes()), 1552477933);
100        assert_eq!(digest("SuperFastHash".as_bytes()), 2245601745);
101        assert_eq!(digest("pirateDay".as_bytes()), 2774317235);
102    }
103}
hsieh_hash/lib.rs

hsieh_hash/
lib.rs
