]>
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 | ||
4831981d SL |
18 | #if __GNUC__ >= 7 |
19 | _Pragma("GCC diagnostic ignored \"-Wimplicit-fallthrough\"") | |
20 | #endif | |
21 | ||
57d0e6b2 KS |
22 | //----------------------------------------------------------------------------- |
23 | // Platform-specific functions and macros | |
24 | ||
25 | // Microsoft Visual Studio | |
26 | ||
27 | #if defined(_MSC_VER) | |
28 | ||
29 | #define BIG_CONSTANT(x) (x) | |
30 | ||
31 | // Other compilers | |
32 | ||
33 | #else // defined(_MSC_VER) | |
34 | ||
35 | #define BIG_CONSTANT(x) (x##LLU) | |
36 | ||
37 | #endif // !defined(_MSC_VER) | |
38 | ||
39 | //----------------------------------------------------------------------------- | |
40 | ||
41 | uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed ) | |
42 | { | |
43 | // 'm' and 'r' are mixing constants generated offline. | |
44 | // They're not really 'magic', they just happen to work well. | |
45 | ||
46 | const uint32_t m = 0x5bd1e995; | |
47 | const int r = 24; | |
48 | ||
49 | // Initialize the hash to a 'random' value | |
50 | ||
51 | uint32_t h = seed ^ len; | |
52 | ||
53 | // Mix 4 bytes at a time into the hash | |
54 | ||
55 | const unsigned char * data = (const unsigned char *)key; | |
56 | ||
9ed794a3 | 57 | while (len >= 4) |
57d0e6b2 KS |
58 | { |
59 | uint32_t k = *(uint32_t*)data; | |
60 | ||
61 | k *= m; | |
62 | k ^= k >> r; | |
63 | k *= m; | |
64 | ||
65 | h *= m; | |
66 | h ^= k; | |
67 | ||
68 | data += 4; | |
69 | len -= 4; | |
70 | } | |
71 | ||
72 | // Handle the last few bytes of the input array | |
73 | ||
74 | switch(len) | |
75 | { | |
2c5248e2 ZJS |
76 | case 3: h ^= data[2] << 16; /* fall through */ |
77 | case 2: h ^= data[1] << 8; /* fall through */ | |
78 | case 1: h ^= data[0]; /* fall through */ | |
57d0e6b2 KS |
79 | h *= m; |
80 | }; | |
81 | ||
82 | // Do a few final mixes of the hash to ensure the last few | |
83 | // bytes are well-incorporated. | |
84 | ||
85 | h ^= h >> 13; | |
86 | h *= m; | |
87 | h ^= h >> 15; | |
88 | ||
89 | return h; | |
90 | } |