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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

use core::{mem, slice};

use byteorder::{ByteOrder, LE};

/// 32-bit MurmurHash3 hasher
pub struct Hasher {
    buf: Buffer,
    index: Index,
    processed: u32,
    state: State,
}

struct State(u32);

#[derive(Clone, Copy)]
#[repr(align(4))]
struct Buffer {
    bytes: [u8; 4],
}

#[derive(Clone, Copy, PartialEq)]
enum Index {
    _0,
    _1,
    _2,
    _3,
}

impl Index {
    fn usize(&self) -> usize {
        match *self {
            Index::_0 => 0,
            Index::_1 => 1,
            Index::_2 => 2,
            Index::_3 => 3,
        }
    }
}

impl From<usize> for Index {
    fn from(x: usize) -> Self {
        match x % 4 {
            0 => Index::_0,
            1 => Index::_1,
            2 => Index::_2,
            3 => Index::_3,
            _ => unreachable!(),
        }
    }
}

impl Hasher {
    fn push(&mut self, buf: &[u8]) {
        let start = self.index.usize();
        let len = buf.len();
        // NOTE(unsafe) avoid calling `memcpy` on a 0-3 byte copy
        // self.buf.bytes[start..start+len].copy_from(buf);
        for i in 0..len {
            unsafe {
                *self.buf.bytes.get_unchecked_mut(start + i) = *buf.get_unchecked(i);
            }
        }
        self.index = Index::from(start + len);
    }
}

impl Default for Hasher {
    fn default() -> Self {
        Hasher {
            buf: unsafe { mem::uninitialized() },
            index: Index::_0,
            processed: 0,
            state: State(0),
        }
    }
}

impl ::Hasher for Hasher {
    fn finish(&self) -> u32 {
        // tail
        let mut state = match self.index {
            Index::_3 => {
                let mut block = 0;
                block ^= u32::from(self.buf.bytes[2]) << 16;
                block ^= u32::from(self.buf.bytes[1]) << 8;
                block ^= u32::from(self.buf.bytes[0]);
                self.state.0 ^ pre_mix(block)
            }
            Index::_2 => {
                let mut block = 0;
                block ^= u32::from(self.buf.bytes[1]) << 8;
                block ^= u32::from(self.buf.bytes[0]);
                self.state.0 ^ pre_mix(block)
            }
            Index::_1 => {
                let mut block = 0;
                block ^= u32::from(self.buf.bytes[0]);
                self.state.0 ^ pre_mix(block)
            }
            Index::_0 => self.state.0,
        };

        // finalization mix
        state ^= self.processed;
        state ^= state >> 16;
        state = state.wrapping_mul(0x85ebca6b);
        state ^= state >> 13;
        state = state.wrapping_mul(0xc2b2ae35);
        state ^= state >> 16;

        state
    }

    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        let len = bytes.len();
        self.processed += len as u32;

        let body = if self.index == Index::_0 {
            bytes
        } else {
            let index = self.index.usize();
            if len + index >= 4 {
                // we can complete a block using the data left in the buffer
                // NOTE(unsafe) avoid panicking branch (`slice_index_len_fail`)
                // let (head, body) = bytes.split_at(4 - index);
                let mid = 4 - index;
                let head = unsafe { slice::from_raw_parts(bytes.as_ptr(), mid) };
                let body = unsafe {
                    slice::from_raw_parts(bytes.as_ptr().offset(mid as isize), len - mid)
                };

                // NOTE(unsafe) avoid calling `memcpy` on a 0-3 byte copy
                // self.buf.bytes[index..].copy_from_slice(head);
                for i in 0..4 - index {
                    unsafe {
                        *self.buf.bytes.get_unchecked_mut(index + i) = *head.get_unchecked(i);
                    }
                }

                self.index = Index::_0;

                self.state.process_block(&self.buf.bytes);

                body
            } else {
                bytes
            }
        };

        for block in body.chunks(4) {
            if block.len() == 4 {
                self.state
                    .process_block(unsafe { &*(block.as_ptr() as *const _) });
            } else {
                self.push(block);
            }
        }

        // XXX is this faster?
        // for block in body.exact_chunks(4) {
        //     self.state
        //         .process_block(unsafe { &*(block.as_ptr() as *const _) });
        // }

        // let tail = body.split_at(body.len() / 4 * 4).1;

        // self.push(tail);
    }
}

const C1: u32 = 0xcc9e2d51;
const C2: u32 = 0x1b873593;
const R1: u32 = 15;

impl State {
    fn process_block(&mut self, block: &[u8; 4]) {
        self.0 ^= pre_mix(LE::read_u32(block));
        self.0 = self.0.rotate_left(13);
        self.0 = 5u32.wrapping_mul(self.0).wrapping_add(0xe6546b64);
    }
}

fn pre_mix(mut block: u32) -> u32 {
    block = block.wrapping_mul(C1);
    block = block.rotate_left(R1);
    block = block.wrapping_mul(C2);
    block
}