1 4545b700 2021-10-15 thomas //-----------------------------------------------------------------------------
 2 4545b700 2021-10-15 thomas // MurmurHash2 was written by Austin Appleby, and is placed in the public
 3 4545b700 2021-10-15 thomas // domain. The author hereby disclaims copyright to this source code.
 4 4545b700 2021-10-15 thomas 
 5 4545b700 2021-10-15 thomas /* Obtained from https://github.com/aappleby/smhasher */
 6 4545b700 2021-10-15 thomas 
 7 4545b700 2021-10-15 thomas #include <stdint.h>
 8 f1b55c5c 2022-07-16 thomas #include <string.h>
 9 4545b700 2021-10-15 thomas 
10 4545b700 2021-10-15 thomas #include "murmurhash2.h"
11 4545b700 2021-10-15 thomas 
12 4545b700 2021-10-15 thomas uint32_t
13 f1b55c5c 2022-07-16 thomas murmurhash2(const unsigned char * key, int len, uint32_t seed)
14 4545b700 2021-10-15 thomas {
15 4545b700 2021-10-15 thomas   // 'm' and 'r' are mixing constants generated offline.
16 4545b700 2021-10-15 thomas   // They're not really 'magic', they just happen to work well.
17 4545b700 2021-10-15 thomas 
18 4545b700 2021-10-15 thomas   const uint32_t m = 0x5bd1e995;
19 4545b700 2021-10-15 thomas   const int r = 24;
20 4545b700 2021-10-15 thomas 
21 4545b700 2021-10-15 thomas   // Initialize the hash to a 'random' value
22 4545b700 2021-10-15 thomas 
23 4545b700 2021-10-15 thomas   uint32_t h = seed ^ len;
24 4545b700 2021-10-15 thomas 
25 4545b700 2021-10-15 thomas   // Mix 4 bytes at a time into the hash
26 4545b700 2021-10-15 thomas 
27 f1b55c5c 2022-07-16 thomas   const unsigned char *data = key;
28 4545b700 2021-10-15 thomas 
29 4545b700 2021-10-15 thomas   while(len >= 4)
30 4545b700 2021-10-15 thomas   {
31 f1b55c5c 2022-07-16 thomas     uint32_t k;
32 4545b700 2021-10-15 thomas 
33 f1b55c5c 2022-07-16 thomas     memcpy(&k, data, sizeof(k));
34 f1b55c5c 2022-07-16 thomas 
35 4545b700 2021-10-15 thomas     k *= m;
36 4545b700 2021-10-15 thomas     k ^= k >> r;
37 4545b700 2021-10-15 thomas     k *= m;
38 4545b700 2021-10-15 thomas 
39 4545b700 2021-10-15 thomas     h *= m;
40 4545b700 2021-10-15 thomas     h ^= k;
41 4545b700 2021-10-15 thomas 
42 4545b700 2021-10-15 thomas     data += 4;
43 4545b700 2021-10-15 thomas     len -= 4;
44 4545b700 2021-10-15 thomas   }
45 4545b700 2021-10-15 thomas 
46 4545b700 2021-10-15 thomas   // Handle the last few bytes of the input array
47 4545b700 2021-10-15 thomas 
48 4545b700 2021-10-15 thomas   switch(len)
49 4545b700 2021-10-15 thomas   {
50 4545b700 2021-10-15 thomas   case 3: h ^= data[2] << 16;
51 4545b700 2021-10-15 thomas   case 2: h ^= data[1] << 8;
52 4545b700 2021-10-15 thomas   case 1: h ^= data[0];
53 4545b700 2021-10-15 thomas       h *= m;
54 4545b700 2021-10-15 thomas   };
55 4545b700 2021-10-15 thomas 
56 4545b700 2021-10-15 thomas   // Do a few final mixes of the hash to ensure the last few
57 4545b700 2021-10-15 thomas   // bytes are well-incorporated.
58 4545b700 2021-10-15 thomas 
59 4545b700 2021-10-15 thomas   h ^= h >> 13;
60 4545b700 2021-10-15 thomas   h *= m;
61 4545b700 2021-10-15 thomas   h ^= h >> 15;
62 4545b700 2021-10-15 thomas 
63 4545b700 2021-10-15 thomas   return h;
64 f1b55c5c 2022-07-16 thomas }