]>
Commit | Line | Data |
---|---|---|
57d0e6b2 KS |
1 | //----------------------------------------------------------------------------- |
2 | // MurmurHash2 was written by Austin Appleby, and is placed in the public | |
3 | // domain. The author hereby disclaims copyright to this source code. | |
4 | ||
5 | // Note - This code makes a few assumptions about how your machine behaves - | |
6 | ||
7 | // 1. We can read a 4-byte value from any address without crashing | |
8 | // 2. sizeof(int) == 4 | |
9 | ||
10 | // And it has a few limitations - | |
11 | ||
12 | // 1. It will not work incrementally. | |
13 | // 2. It will not produce the same results on little-endian and big-endian | |
14 | // machines. | |
15 | ||
16 | #include "MurmurHash2.h" | |
17 | ||
18 | //----------------------------------------------------------------------------- | |
19 | // Platform-specific functions and macros | |
20 | ||
21 | // Microsoft Visual Studio | |
22 | ||
23 | #if defined(_MSC_VER) | |
24 | ||
25 | #define BIG_CONSTANT(x) (x) | |
26 | ||
27 | // Other compilers | |
28 | ||
29 | #else // defined(_MSC_VER) | |
30 | ||
31 | #define BIG_CONSTANT(x) (x##LLU) | |
32 | ||
33 | #endif // !defined(_MSC_VER) | |
34 | ||
35 | //----------------------------------------------------------------------------- | |
36 | ||
37 | uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed ) | |
38 | { | |
39 | // 'm' and 'r' are mixing constants generated offline. | |
40 | // They're not really 'magic', they just happen to work well. | |
41 | ||
42 | const uint32_t m = 0x5bd1e995; | |
43 | const int r = 24; | |
44 | ||
45 | // Initialize the hash to a 'random' value | |
46 | ||
47 | uint32_t h = seed ^ len; | |
48 | ||
49 | // Mix 4 bytes at a time into the hash | |
50 | ||
51 | const unsigned char * data = (const unsigned char *)key; | |
52 | ||
9ed794a3 | 53 | while (len >= 4) |
57d0e6b2 KS |
54 | { |
55 | uint32_t k = *(uint32_t*)data; | |
56 | ||
57 | k *= m; | |
58 | k ^= k >> r; | |
59 | k *= m; | |
60 | ||
61 | h *= m; | |
62 | h ^= k; | |
63 | ||
64 | data += 4; | |
65 | len -= 4; | |
66 | } | |
67 | ||
68 | // Handle the last few bytes of the input array | |
69 | ||
70 | switch(len) | |
71 | { | |
72 | case 3: h ^= data[2] << 16; | |
73 | case 2: h ^= data[1] << 8; | |
74 | case 1: h ^= data[0]; | |
75 | h *= m; | |
76 | }; | |
77 | ||
78 | // Do a few final mixes of the hash to ensure the last few | |
79 | // bytes are well-incorporated. | |
80 | ||
81 | h ^= h >> 13; | |
82 | h *= m; | |
83 | h ^= h >> 15; | |
84 | ||
85 | return h; | |
86 | } |