1 use std::mem;
2 
fmix64(mut k: u64) -> u643 fn fmix64(mut k: u64) -> u64 {
4     k ^= k >> 33;
5     k = k.wrapping_mul(0xff51afd7ed558ccdu64);
6     k ^= k >> 33;
7     k = k.wrapping_mul(0xc4ceb9fe1a85ec53u64);
8     k ^= k >> 33;
9 
10     return k;
11 }
12 
get_128_block(bytes: &[u8], index: usize) -> (u64, u64)13 fn get_128_block(bytes: &[u8], index: usize) -> (u64, u64) {
14     let b64: &[u64] = unsafe { mem::transmute(bytes) };
15 
16     return (b64[index], b64[index + 1]);
17 }
18 
murmurhash3_x64_128(bytes: &[u8], seed: u64) -> (u64, u64)19 pub fn murmurhash3_x64_128(bytes: &[u8], seed: u64) -> (u64, u64) {
20     let c1 = 0x87c37b91114253d5u64;
21     let c2 = 0x4cf5ad432745937fu64;
22     let read_size = 16;
23     let len = bytes.len() as u64;
24     let block_count = len / read_size;
25 
26     let (mut h1, mut h2) = (seed, seed);
27 
28 
29     for i in 0..block_count as usize {
30         let (mut k1, mut k2) = get_128_block(bytes, i * 2);
31 
32         k1 = k1.wrapping_mul(c1);
33         k1 = k1.rotate_left(31);
34         k1 = k1.wrapping_mul(c2);
35         h1 ^= k1;
36 
37         h1 = h1.rotate_left(27);
38         h1 = h1.wrapping_add(h2);
39         h1 = h1.wrapping_mul(5);
40         h1 = h1.wrapping_add(0x52dce729);
41 
42         k2 = k2.wrapping_mul(c2);
43         k2 = k2.rotate_left(33);
44         k2 = k2.wrapping_mul(c1);
45         h2 ^= k2;
46 
47         h2 = h2.rotate_left(31);
48         h2 = h2.wrapping_add(h1);
49         h2 = h2.wrapping_mul(5);
50         h2 = h2.wrapping_add(0x38495ab5);
51     }
52 
53 
54     let (mut k1, mut k2) = (0u64, 0u64);
55 
56     if len & 15 == 15 { k2 ^= (bytes[(block_count * read_size) as usize + 14] as u64) << 48; }
57     if len & 15 >= 14 { k2 ^= (bytes[(block_count * read_size) as usize + 13] as u64) << 40; }
58     if len & 15 >= 13 { k2 ^= (bytes[(block_count * read_size) as usize + 12] as u64) << 32; }
59     if len & 15 >= 12 { k2 ^= (bytes[(block_count * read_size) as usize + 11] as u64) << 24; }
60     if len & 15 >= 11 { k2 ^= (bytes[(block_count * read_size) as usize + 10] as u64) << 16; }
61     if len & 15 >= 10 { k2 ^= (bytes[(block_count * read_size) as usize +  9] as u64) <<  8; }
62     if len & 15 >=  9 { k2 ^=  bytes[(block_count * read_size) as usize +  8] as u64;
63         k2 = k2.wrapping_mul(c2);
64         k2 = k2.rotate_left(33);
65         k2 = k2.wrapping_mul(c1);
66         h2 ^= k2;
67     }
68 
69     if len & 15 >= 8 { k1 ^= (bytes[(block_count * read_size) as usize + 7] as u64) << 56; }
70     if len & 15 >= 7 { k1 ^= (bytes[(block_count * read_size) as usize + 6] as u64) << 48; }
71     if len & 15 >= 6 { k1 ^= (bytes[(block_count * read_size) as usize + 5] as u64) << 40; }
72     if len & 15 >= 5 { k1 ^= (bytes[(block_count * read_size) as usize + 4] as u64) << 32; }
73     if len & 15 >= 4 { k1 ^= (bytes[(block_count * read_size) as usize + 3] as u64) << 24; }
74     if len & 15 >= 3 { k1 ^= (bytes[(block_count * read_size) as usize + 2] as u64) << 16; }
75     if len & 15 >= 2 { k1 ^= (bytes[(block_count * read_size) as usize + 1] as u64) <<  8; }
76     if len & 15 >= 1 { k1 ^=  bytes[(block_count * read_size) as usize + 0] as u64;
77         k1 = k1.wrapping_mul(c1);
78         k1 = k1.rotate_left(31);
79         k1 = k1.wrapping_mul(c2);
80         h1 ^= k1;
81     }
82 
83     h1 ^= bytes.len() as u64;
84     h2 ^= bytes.len() as u64;
85 
86     h1 = h1.wrapping_add(h2);
87     h2 = h2.wrapping_add(h1);
88 
89     h1 = fmix64(h1);
90     h2 = fmix64(h2);
91 
92     h1 = h1.wrapping_add(h2);
93     h2 = h2.wrapping_add(h1);
94 
95     return (h1, h2);
96 }
97 
98 #[cfg(test)]
99 mod test {
100     use super::murmurhash3_x64_128;
101 
102     #[test]
test_empty_string()103     fn test_empty_string() {
104         assert!(murmurhash3_x64_128("".as_bytes(), 0) == (0, 0));
105     }
106 
107     #[test]
test_tail_lengths()108     fn test_tail_lengths() {
109         assert!(murmurhash3_x64_128("1".as_bytes(), 0)
110             == (8213365047359667313, 10676604921780958775));
111         assert!(murmurhash3_x64_128("12".as_bytes(), 0)
112             == (5355690773644049813, 9855895140584599837));
113         assert!(murmurhash3_x64_128("123".as_bytes(), 0)
114             == (10978418110857903978, 4791445053355511657));
115         assert!(murmurhash3_x64_128("1234".as_bytes(), 0)
116             == (619023178690193332, 3755592904005385637));
117         assert!(murmurhash3_x64_128("12345".as_bytes(), 0)
118             == (2375712675693977547, 17382870096830835188));
119         assert!(murmurhash3_x64_128("123456".as_bytes(), 0)
120             == (16435832985690558678, 5882968373513761278));
121         assert!(murmurhash3_x64_128("1234567".as_bytes(), 0)
122             == (3232113351312417698, 4025181827808483669));
123         assert!(murmurhash3_x64_128("12345678".as_bytes(), 0)
124             == (4272337174398058908, 10464973996478965079));
125         assert!(murmurhash3_x64_128("123456789".as_bytes(), 0)
126             == (4360720697772133540, 11094893415607738629));
127         assert!(murmurhash3_x64_128("123456789a".as_bytes(), 0)
128             == (12594836289594257748, 2662019112679848245));
129         assert!(murmurhash3_x64_128("123456789ab".as_bytes(), 0)
130             == (6978636991469537545, 12243090730442643750));
131         assert!(murmurhash3_x64_128("123456789abc".as_bytes(), 0)
132             == (211890993682310078, 16480638721813329343));
133         assert!(murmurhash3_x64_128("123456789abcd".as_bytes(), 0)
134             == (12459781455342427559, 3193214493011213179));
135         assert!(murmurhash3_x64_128("123456789abcde".as_bytes(), 0)
136             == (12538342858731408721, 9820739847336455216));
137         assert!(murmurhash3_x64_128("123456789abcdef".as_bytes(), 0)
138             == (9165946068217512774, 2451472574052603025));
139         assert!(murmurhash3_x64_128("123456789abcdef1".as_bytes(), 0)
140             == (9259082041050667785, 12459473952842597282));
141     }
142 
143     #[test]
test_large_data()144     fn test_large_data() {
145         assert!(murmurhash3_x64_128("Lorem ipsum dolor sit amet, consectetur adipiscing elit. Etiam at consequat massa. Cras eleifend pellentesque ex, at dignissim libero maximus ut. Sed eget nulla felis".as_bytes(), 0)
146             == (9455322759164802692, 17863277201603478371));
147     }
148 
149     #[cfg(feature="nightly")]
150     mod bench {
151         extern crate rand;
152         extern crate test;
153 
154         use std::iter::FromIterator;
155         use self::rand::Rng;
156         use self::test::{Bencher, black_box};
157 
158         use super::super::murmurhash3_x64_128;
159 
run_bench(b: &mut Bencher, size: u64)160         fn run_bench(b: &mut Bencher, size: u64) {
161             let mut data: Vec<u8> = FromIterator::from_iter((0..size).map(|_| 0u8));
162             rand::thread_rng().fill_bytes(&mut data);
163 
164             b.bytes = size;
165             b.iter(|| {
166                 black_box(murmurhash3_x64_128(&data, 0));
167             });
168         }
169 
170         #[bench]
bench_random_256k(b: &mut Bencher)171         fn bench_random_256k(b: &mut Bencher) {
172             run_bench(b, 256 * 1024);
173         }
174 
175         #[bench]
bench_random_16b(b: &mut Bencher)176         fn bench_random_16b(b: &mut Bencher) {
177             run_bench(b, 16);
178         }
179 
180     }
181 }
182