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

//! `Murmur`, a suite of non-cryptographic hash functions that was used for hash-based lookups.
//!
//! by Austin Appleby (aappleby (AT) gmail)
//!
//! https://sites.google.com/site/murmurhash/
//!
//! Extremely simple - compiles down to ~52 instructions on x86.
//!
//! Excellent distribution - Passes chi-squared tests for practically all keysets & bucket sizes.
//!
//! Excellent avalanche behavior - Maximum bias is under 0.5%.
//!
//! Excellent collision resistance - Passes Bob Jenkin's frog.c torture-test.
//! No collisions possible for 4-byte keys, no small (1- to 7-bit) differentials.
//!
//! Excellent performance - measured on an Intel Core 2 Duo @ 2.4 ghz
//!
//!    - `OneAtATime` - 354.163715 mb/sec
//!    - `FNV` - 443.668038 mb/sec
//!    - `SuperFastHash` - 985.335173 mb/sec
//!    - `lookup3` - 988.080652 mb/sec
//!    - `MurmurHash` 1.0 - 1363.293480 mb/sec
//!    - `MurmurHash` 2.0 - 2056.885653 mb/sec
//!
//! # Example
//!
//! ```
//! use std::hash::{Hash, Hasher};
//!
//! use fasthash::{murmur, MurmurHasher};
//!
//! fn hash<T: Hash>(t: &T) -> u64 {
//!     let mut s: MurmurHasher = Default::default();
//!     t.hash(&mut s);
//!     s.finish()
//! }
//!
//! let h = murmur::hash32(b"hello world\xff");
//!
//! assert_eq!(h, hash(&"hello world") as u32);
//! ```
//!
use std::os::raw::c_void;

use ffi;

use hasher::{FastHash, FastHasher};

/// `MurmurHash` 32-bit hash functions
pub struct Murmur {}

impl FastHash for Murmur {
    type Value = u32;
    type Seed = u32;

    #[inline]
    fn hash_with_seed<T: AsRef<[u8]>>(bytes: &T, seed: u32) -> u32 {
        unsafe {
            ffi::MurmurHash1(bytes.as_ref().as_ptr() as *const c_void,
                             bytes.as_ref().len() as i32,
                             seed)
        }
    }
}

impl_hasher!(MurmurHasher, Murmur);

/// `MurmurHash` 32-bit aligned hash functions
pub struct MurmurAligned {}

impl FastHash for MurmurAligned {
    type Value = u32;
    type Seed = u32;

    #[inline]
    fn hash_with_seed<T: AsRef<[u8]>>(bytes: &T, seed: u32) -> u32 {
        unsafe {
            ffi::MurmurHash1Aligned(bytes.as_ref().as_ptr() as *const c_void,
                                    bytes.as_ref().len() as i32,
                                    seed)
        }
    }
}

impl_hasher!(MurmurAlignedHasher, MurmurAligned);

/// `MurmurHash` 32-bit hash functions for a byte array.
#[inline]
pub fn hash32<T: AsRef<[u8]>>(v: &T) -> u32 {
    Murmur::hash(v)
}

/// `MurmurHash` 32-bit hash function for a byte array.
/// For convenience, a 32-bit seed is also hashed into the result.
#[inline]
pub fn hash32_with_seed<T: AsRef<[u8]>>(v: &T, seed: u32) -> u32 {
    Murmur::hash_with_seed(v, seed)
}

/// `MurmurHash` 32-bit aligned hash functions for a byte array.
#[inline]
pub fn hash32_aligned<T: AsRef<[u8]>>(v: &T) -> u32 {
    MurmurAligned::hash(v)
}

/// `MurmurHash` 32-bit aligned hash function for a byte array.
/// For convenience, a 32-bit seed is also hashed into the result.
#[inline]
pub fn hash32_aligned_with_seed<T: AsRef<[u8]>>(v: &T, seed: u32) -> u32 {
    MurmurAligned::hash_with_seed(v, seed)
}

#[cfg(test)]
mod tests {
    use std::hash::Hasher;

    use hasher::{FastHash, FastHasher};
    use super::*;

    #[test]
    fn test_murmur() {
        assert_eq!(Murmur::hash(b"hello"), 1773990585);
        assert_eq!(Murmur::hash_with_seed(b"hello", 123), 2155802495);
        assert_eq!(Murmur::hash(b"helloworld"), 567127608);

        let mut h = MurmurHasher::new();

        h.write(b"hello");
        assert_eq!(h.finish(), 1773990585);

        h.write(b"world");
        assert_eq!(h.finish(), 567127608);
    }

    #[test]
    fn test_murmur_aligned() {
        assert_eq!(MurmurAligned::hash(b"hello"), 1773990585);
        assert_eq!(MurmurAligned::hash_with_seed(b"hello", 123), 2155802495);
        assert_eq!(MurmurAligned::hash(b"helloworld"), 567127608);

        let mut h = MurmurAlignedHasher::new();

        h.write(b"hello");
        assert_eq!(h.finish(), 1773990585);

        h.write(b"world");
        assert_eq!(h.finish(), 567127608);
    }
}