1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 
3 #include <sys/types.h>
4 #include <stdbool.h>
5 #include <stdint.h>
6 
7 /*
8   "Murmur" hash provided by Austin, tanjent@gmail.com
9   http://murmurhash.googlepages.com/
10 
11   Note - This code makes a few assumptions about how your machine behaves -
12 
13   1. We can read a 4-byte value from any address without crashing
14   2. sizeof(int) == 4
15 
16   And it has a few limitations -
17   1. It will not work incrementally.
18   2. It will not produce the same results on little-endian and big-endian
19   machines.
20 
21   Updated to murmur2 hash - BP
22 */
23 
24 uint32_t murmur_hash(const char *key, size_t length);
25 
murmur_hash(const char *key, size_t length)26 uint32_t murmur_hash(const char *key, size_t length)
27 {
28   /*
29     'm' and 'r' are mixing constants generated offline.  They're not
30     really 'magic', they just happen to work well.
31   */
32 
33   const unsigned int m= 0x5bd1e995;
34   const unsigned int seed= (0xdeadbeef * length);
35   const int r= 24;
36 
37 
38   /* Initialize the hash to a 'random' value */
39 
40   unsigned int h= seed ^ length;
41 
42   /* Mix 4 bytes at a time into the hash */
43 
44   const unsigned char * data= (const unsigned char *)key;
45 
46   while(length >= 4)
47   {
48     unsigned int k = *(unsigned int *)data;
49 
50     k *= m;
51     k ^= k >> r;
52     k *= m;
53 
54     h *= m;
55     h ^= k;
56 
57     data += 4;
58     length -= 4;
59   }
60 
61   /* Handle the last few bytes of the input array */
62 
63   switch(length)
64   {
65   case 3: h ^= data[2] << 16;
66   case 2: h ^= data[1] << 8;
67   case 1: h ^= data[0];
68           h *= m;
69   };
70 
71   /*
72     Do a few final mixes of the hash to ensure the last few bytes are
73     well-incorporated.
74   */
75 
76   h ^= h >> 13;
77   h *= m;
78   h ^= h >> 15;
79 
80   return h;
81 }
82