1 //-----------------------------------------------------------------------------
2 // MurmurHash was written by Austin Appleby, and is placed in the public
3 // domain. The author hereby disclaims copyright to this source code.
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
12 // 1. It will not work incrementally.
13 // 2. It will not produce the same results on little-endian and big-endian
14 // machines.
15
16 #include "MurmurHash1.h"
17
18 //-----------------------------------------------------------------------------
19
MurmurHash1(const void * key,int len,uint32_t seed)20 uint32_t MurmurHash1 ( const void * key, int len, uint32_t seed )
21 {
22 const unsigned int m = 0xc6a4a793;
23
24 const int r = 16;
25
26 unsigned int h = seed ^ (len * m);
27
28 //----------
29
30 const unsigned char * data = (const unsigned char *)key;
31
32 while(len >= 4)
33 {
34 unsigned int k = *(unsigned int *)data;
35
36 h += k;
37 h *= m;
38 h ^= h >> 16;
39
40 data += 4;
41 len -= 4;
42 }
43
44 //----------
45
46 switch(len)
47 {
48 case 3:
49 h += data[2] << 16;
50 case 2:
51 h += data[1] << 8;
52 case 1:
53 h += data[0];
54 h *= m;
55 h ^= h >> r;
56 };
57
58 //----------
59
60 h *= m;
61 h ^= h >> 10;
62 h *= m;
63 h ^= h >> 17;
64
65 return h;
66 }
67
68 //-----------------------------------------------------------------------------
69 // MurmurHash1Aligned, by Austin Appleby
70
71 // Same algorithm as MurmurHash1, but only does aligned reads - should be safer
72 // on certain platforms.
73
74 // Performance should be equal to or better than the simple version.
75
MurmurHash1Aligned(const void * key,int len,unsigned int seed)76 unsigned int MurmurHash1Aligned ( const void * key, int len, unsigned int seed )
77 {
78 const unsigned int m = 0xc6a4a793;
79 const int r = 16;
80
81 const unsigned char * data = (const unsigned char *)key;
82
83 unsigned int h = seed ^ (len * m);
84
85 int align = (uint64_t)data & 3;
86
87 if(align && (len >= 4))
88 {
89 // Pre-load the temp registers
90
91 unsigned int t = 0, d = 0;
92
93 switch(align)
94 {
95 case 1: t |= data[2] << 16;
96 case 2: t |= data[1] << 8;
97 case 3: t |= data[0];
98 }
99
100 t <<= (8 * align);
101
102 data += 4-align;
103 len -= 4-align;
104
105 int sl = 8 * (4-align);
106 int sr = 8 * align;
107
108 // Mix
109
110 while(len >= 4)
111 {
112 d = *(unsigned int *)data;
113 t = (t >> sr) | (d << sl);
114 h += t;
115 h *= m;
116 h ^= h >> r;
117 t = d;
118
119 data += 4;
120 len -= 4;
121 }
122
123 // Handle leftover data in temp registers
124
125 int pack = len < align ? len : align;
126
127 d = 0;
128
129 switch(pack)
130 {
131 case 3: d |= data[2] << 16;
132 case 2: d |= data[1] << 8;
133 case 1: d |= data[0];
134 case 0: h += (t >> sr) | (d << sl);
135 h *= m;
136 h ^= h >> r;
137 }
138
139 data += pack;
140 len -= pack;
141 }
142 else
143 {
144 while(len >= 4)
145 {
146 h += *(unsigned int *)data;
147 h *= m;
148 h ^= h >> r;
149
150 data += 4;
151 len -= 4;
152 }
153 }
154
155 //----------
156 // Handle tail bytes
157
158 switch(len)
159 {
160 case 3: h += data[2] << 16;
161 case 2: h += data[1] << 8;
162 case 1: h += data[0];
163 h *= m;
164 h ^= h >> r;
165 };
166
167 h *= m;
168 h ^= h >> 10;
169 h *= m;
170 h ^= h >> 17;
171
172 return h;
173 }
174
175