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