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