rs_alloc/
hash.rs

1//
2// Copyright 2020-Present (c) Raja Lehtihet & Wael El Oraiby
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are met:
6//
7// 1. Redistributions of source code must retain the above copyright notice,
8// this list of conditions and the following disclaimer.
9//
10// 2. Redistributions in binary form must reproduce the above copyright notice,
11// this list of conditions and the following disclaimer in the documentation
12// and/or other materials provided with the distribution.
13//
14// 3. Neither the name of the copyright holder nor the names of its contributors
15// may be used to endorse or promote products derived from this software without
16// specific prior written permission.
17//
18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28// POSSIBILITY OF SUCH DAMAGE.
29//
30pub trait Hash {
31    fn hash(&self) -> usize;
32}
33
34impl Hash for &[u8] {
35    fn hash(&self) -> usize {
36        murmur_hash_64a(self, 0xcae4f57) as usize
37    }
38}
39
40// from: https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c
41// Copyright 2014 (c) Salvatore Sanfilippo <antirez at gmail dot com> - 3-Clause BSD license
42/* Our hash function is MurmurHash2, 64 bit version.
43 * It was modified for Redis in order to provide the same result in
44 * big and little endian archs (endian neutral). */
45pub fn murmur_hash_64a (key: &[u8], seed: u64) -> u64 {
46    let m = 0xc6a4a7935bd1e995;
47    let r = 47;
48    let mut h = seed ^ ((key.len() as u64).wrapping_mul(m));
49    let mut i = 0;
50    let len = key.len() & 7;
51
52    let end = key.len() - len;
53
54    while i < end {
55        let mut k = key[i + 0] as u64;
56        k |= (key[i + 1] as u64) << 8;
57        k |= (key[i + 2] as u64) << 16;
58        k |= (key[i + 3] as u64) << 24;
59        k |= (key[i + 4] as u64) << 32;
60        k |= (key[i + 5] as u64) << 40;
61        k |= (key[i + 6] as u64) << 48;
62        k |= (key[i + 7] as u64) << 56;
63
64        k = k.wrapping_mul(m);
65        k ^= k >> r;
66        k = k.wrapping_mul(m);
67        h ^= k;
68        h = h.wrapping_mul(m);
69        i += 8;
70    }
71
72    let shifts  = [0, 8, 16, 24, 32, 40, 48];
73    let offsets = [0, 1, 2, 3, 4, 5, 6];
74    if len != 0 {
75        for i in 0..len {
76            let idx = len - i - 1;
77            h ^= (key[end + offsets[idx]] as u64) << shifts[idx];
78        }
79        h = h.wrapping_mul(m);
80    }
81
82    h ^= h >> r;
83    h = h.wrapping_mul(m);
84    h ^= h >> r;
85    h
86}
rs_alloc/hash.rs

rs_alloc/
hash.rs
