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 4545b700 2021-10-15 thomas 
 9 4545b700 2021-10-15 thomas #include "murmurhash2.h"
10 4545b700 2021-10-15 thomas 
11 4545b700 2021-10-15 thomas uint32_t
12 4eaf4387 2021-10-16 thomas murmurhash2(const void * key, int len, uint32_t seed)
13 4545b700 2021-10-15 thomas {
14 4545b700 2021-10-15 thomas   // 'm' and 'r' are mixing constants generated offline.
15 4545b700 2021-10-15 thomas   // They're not really 'magic', they just happen to work well.
16 4545b700 2021-10-15 thomas 
17 4545b700 2021-10-15 thomas   const uint32_t m = 0x5bd1e995;
18 4545b700 2021-10-15 thomas   const int r = 24;
19 4545b700 2021-10-15 thomas 
20 4545b700 2021-10-15 thomas   // Initialize the hash to a 'random' value
21 4545b700 2021-10-15 thomas 
22 4545b700 2021-10-15 thomas   uint32_t h = seed ^ len;
23 4545b700 2021-10-15 thomas 
24 4545b700 2021-10-15 thomas   // Mix 4 bytes at a time into the hash
25 4545b700 2021-10-15 thomas 
26 4eaf4387 2021-10-16 thomas   const unsigned char *data = (const unsigned char *)key;
27 4545b700 2021-10-15 thomas 
28 4545b700 2021-10-15 thomas   while(len >= 4)
29 4545b700 2021-10-15 thomas   {
30 4eaf4387 2021-10-16 thomas     uint32_t k = *(uint32_t*)data;
31 4545b700 2021-10-15 thomas 
32 4545b700 2021-10-15 thomas     k *= m;
33 4545b700 2021-10-15 thomas     k ^= k >> r;
34 4545b700 2021-10-15 thomas     k *= m;
35 4545b700 2021-10-15 thomas 
36 4545b700 2021-10-15 thomas     h *= m;
37 4545b700 2021-10-15 thomas     h ^= k;
38 4545b700 2021-10-15 thomas 
39 4545b700 2021-10-15 thomas     data += 4;
40 4545b700 2021-10-15 thomas     len -= 4;
41 4545b700 2021-10-15 thomas   }
42 4545b700 2021-10-15 thomas 
43 4545b700 2021-10-15 thomas   // Handle the last few bytes of the input array
44 4545b700 2021-10-15 thomas 
45 4545b700 2021-10-15 thomas   switch(len)
46 4545b700 2021-10-15 thomas   {
47 4545b700 2021-10-15 thomas   case 3: h ^= data[2] << 16;
48 4545b700 2021-10-15 thomas   case 2: h ^= data[1] << 8;
49 4545b700 2021-10-15 thomas   case 1: h ^= data[0];
50 4545b700 2021-10-15 thomas       h *= m;
51 4545b700 2021-10-15 thomas   };
52 4545b700 2021-10-15 thomas 
53 4545b700 2021-10-15 thomas   // Do a few final mixes of the hash to ensure the last few
54 4545b700 2021-10-15 thomas   // bytes are well-incorporated.
55 4545b700 2021-10-15 thomas 
56 4545b700 2021-10-15 thomas   h ^= h >> 13;
57 4545b700 2021-10-15 thomas   h *= m;
58 4545b700 2021-10-15 thomas   h ^= h >> 15;
59 4545b700 2021-10-15 thomas 
60 4545b700 2021-10-15 thomas   return h;
61 4eaf4387 2021-10-16 thomas }