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