fastmurmur3/
murmur3rs.rs

1#![allow(unreachable_code)]
2use std::ops::Shl;
3use crate::{
4    match_fallthrough,
5    match_fallthrough_reverse_branches,
6    match_fallthrough_make_loops,
7    match_fallthrough_make_match
8};
9
10
11#[inline]
12pub fn hash(data: &[u8]) -> u128 {
13    murmur3_x64_128(data, 0)
14}
15
16/// This macro only prints if we're in test mode.
17macro_rules! test_println {
18    ($($arg:tt)*) => {
19        if cfg!(test) {
20            println!($($arg)*)
21        }
22    }
23}
24
25
26#[inline]
27pub fn murmur3_x64_128(data: &[u8], seed: u64) -> u128 {
28    const C1: u64 = 0x87c3_7b91_1142_53d5;
29    const C2: u64 = 0x4cf5_ad43_2745_937f;
30    const C3: u64 = 0x52dc_e729;
31    const C4: u64 = 0x3849_5ab5;
32    const R1: u32 = 27;
33    const R2: u32 = 31;
34    const R3: u32 = 33;
35    const M: u64 = 5;
36    const BLOCK_SIZE: usize = 16;
37    const HALF_BLOCK_SIZE: usize = BLOCK_SIZE / 2;
38    let len = data.len();
39    let full_block_len = data.len() / BLOCK_SIZE * BLOCK_SIZE;
40
41    let mut h1: u64 = seed;
42    let mut h2: u64 = seed;
43
44    for slice in data[..full_block_len].chunks(BLOCK_SIZE) {
45        let k1 = u64::from_le_bytes(unsafe {*(
46            slice.as_ptr() as *const [u8; HALF_BLOCK_SIZE]
47        )});
48        let k2 = u64::from_le_bytes(unsafe {*(
49            slice.as_ptr().offset(HALF_BLOCK_SIZE as isize) as *const [u8; HALF_BLOCK_SIZE]
50        )});
51        h1 ^= k1.wrapping_mul(C1).rotate_left(R2).wrapping_mul(C2);
52        h1 = h1
53            .rotate_left(R1)
54            .wrapping_add(h2)
55            .wrapping_mul(M)
56            .wrapping_add(C3);
57        h2 ^= k2.wrapping_mul(C2).rotate_left(R3).wrapping_mul(C1);
58        h2 = h2
59            .rotate_left(R2)
60            .wrapping_add(h1)
61            .wrapping_mul(M)
62            .wrapping_add(C4);
63    }
64
65    let buf = &data[full_block_len..];
66    let trailing_len = buf.len();
67    let mut k1 = 0;
68    let mut k2 = 0;
69    // this macro saves about 8% on performance compared to a huge if statement.
70    match_fallthrough!(trailing_len, {
71        15 => k2 ^= (buf[14] as u64).shl(48),
72        14 => k2 ^= (buf[13] as u64).shl(40),
73        13 => k2 ^= (buf[12] as u64).shl(32),
74        12 => k2 ^= (buf[11] as u64).shl(24),
75        11 => k2 ^= (buf[10] as u64).shl(16),
76        10 => k2 ^= (buf[9] as u64).shl(8),
77        9 => {
78            k2 ^= buf[8] as u64;
79            k2 = k2.wrapping_mul(C2)
80                .rotate_left(33)
81                .wrapping_mul(C1);
82            h2 ^= k2;
83        },
84        8 => k1 ^= (buf[7] as u64).shl(56),
85        7 => k1 ^= (buf[6] as u64).shl(48),
86        6 => k1 ^= (buf[5] as u64).shl(40),
87        5 => k1 ^= (buf[4] as u64).shl(32),
88        4 => k1 ^= (buf[3] as u64).shl(24),
89        3 => k1 ^= (buf[2] as u64).shl(16),
90        2 => k1 ^= (buf[1] as u64).shl(8),
91        1 => k1 ^= buf[0] as u64,
92        0 => {
93            k1 = k1.wrapping_mul(C1)
94                .rotate_left(R2)
95                .wrapping_mul(C2);
96            h1 ^= k1;
97            break;
98        },
99        _ => unreachable!()
100    });
101
102    h1 ^= len as u64;
103    h2 ^= len as u64;
104    h1 = h1.wrapping_add(h2);
105    h2 = h2.wrapping_add(h1);
106    h1 = fmix64(h1);
107    h2 = fmix64(h2);
108    h1 = h1.wrapping_add(h2);
109    h2 = h2.wrapping_add(h1);
110    u128::from_ne_bytes(unsafe {*([h1, h2].as_ptr() as *const [u8; 16])})
111}
112
113
114trait XorShift {
115    fn xor_shr(&self, shift: u32) -> Self;
116}
117
118
119impl XorShift for u64 {
120    fn xor_shr(&self, shift: u32) -> Self {
121        self ^ (self >> shift)
122    }
123}
124
125
126fn fmix64(k: u64) -> u64 {
127    const C1: u64 = 0xff51_afd7_ed55_8ccd;
128    const C2: u64 = 0xc4ce_b9fe_1a85_ec53;
129    const R: u32 = 33;
130    k
131        .xor_shr(R)
132        .wrapping_mul(C1)
133        .xor_shr(R)
134        .wrapping_mul(C2)
135        .xor_shr(R)
136}
fastmurmur3/murmur3rs.rs

fastmurmur3/
murmur3rs.rs
