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