blob: dbb205336e372f136a4a2e4de3bac3fb4c9db441 [file] [log] [blame]
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +00001//-----------------------------------------------------------------------------
aappleby@google.comc2b49e02011-04-08 21:13:25 +00002// MurmurHash2 was written by Austin Appleby, and is placed in the public
aappleby@google.comc8e8bf82011-04-08 21:07:48 +00003// domain. The author hereby disclaims copyright to this source code.
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +00004
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
aappleby@google.comc8e8bf82011-04-08 21:07:48 +000016#include "MurmurHash2.h"
17
18//-----------------------------------------------------------------------------
19// Platform-specific functions and macros
20
21// Microsoft Visual Studio
22
23#if defined(_MSC_VER)
24
25#define BIG_CONSTANT(x) (x)
26
27// Other compilers
28
29#else // defined(_MSC_VER)
30
31#define BIG_CONSTANT(x) (x##LLU)
32
33#endif // !defined(_MSC_VER)
34
35//-----------------------------------------------------------------------------
36
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000037uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed )
38{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000039 // 'm' and 'r' are mixing constants generated offline.
40 // They're not really 'magic', they just happen to work well.
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000041
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000042 const uint32_t m = 0x5bd1e995;
43 const int r = 24;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000044
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000045 // Initialize the hash to a 'random' value
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000046
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000047 uint32_t h = seed ^ len;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000048
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000049 // Mix 4 bytes at a time into the hash
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000050
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000051 const unsigned char * data = (const unsigned char *)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000052
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000053 while(len >= 4)
54 {
55 uint32_t k = *(uint32_t*)data;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000056
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000057 k *= m;
58 k ^= k >> r;
59 k *= m;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000060
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000061 h *= m;
62 h ^= k;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000063
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000064 data += 4;
65 len -= 4;
66 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000067
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000068 // Handle the last few bytes of the input array
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000069
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000070 switch(len)
71 {
72 case 3: h ^= data[2] << 16;
73 case 2: h ^= data[1] << 8;
74 case 1: h ^= data[0];
75 h *= m;
76 };
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000077
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000078 // Do a few final mixes of the hash to ensure the last few
79 // bytes are well-incorporated.
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000080
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000081 h ^= h >> 13;
82 h *= m;
83 h ^= h >> 15;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000084
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000085 return h;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000086}
87
88//-----------------------------------------------------------------------------
89// MurmurHash2, 64-bit versions, by Austin Appleby
90
91// The same caveats as 32-bit MurmurHash2 apply here - beware of alignment
92// and endian-ness issues if used across multiple platforms.
93
94// 64-bit hash for 64-bit platforms
95
96uint64_t MurmurHash64A ( const void * key, int len, uint64_t seed )
97{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000098 const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995);
99 const int r = 47;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000100
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000101 uint64_t h = seed ^ (len * m);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000102
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000103 const uint64_t * data = (const uint64_t *)key;
104 const uint64_t * end = data + (len/8);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000105
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000106 while(data != end)
107 {
108 uint64_t k = *data++;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000109
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000110 k *= m;
111 k ^= k >> r;
112 k *= m;
113
114 h ^= k;
115 h *= m;
116 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000117
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000118 const unsigned char * data2 = (const unsigned char*)data;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000119
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000120 switch(len & 7)
121 {
122 case 7: h ^= uint64_t(data2[6]) << 48;
123 case 6: h ^= uint64_t(data2[5]) << 40;
124 case 5: h ^= uint64_t(data2[4]) << 32;
125 case 4: h ^= uint64_t(data2[3]) << 24;
126 case 3: h ^= uint64_t(data2[2]) << 16;
127 case 2: h ^= uint64_t(data2[1]) << 8;
128 case 1: h ^= uint64_t(data2[0]);
129 h *= m;
130 };
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000131
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000132 h ^= h >> r;
133 h *= m;
134 h ^= h >> r;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000135
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000136 return h;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000137}
138
139
140// 64-bit hash for 32-bit platforms
141
142uint64_t MurmurHash64B ( const void * key, int len, uint64_t seed )
143{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000144 const uint32_t m = 0x5bd1e995;
145 const int r = 24;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000146
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000147 uint32_t h1 = uint32_t(seed) ^ len;
148 uint32_t h2 = uint32_t(seed >> 32);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000149
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000150 const uint32_t * data = (const uint32_t *)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000151
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000152 while(len >= 8)
153 {
154 uint32_t k1 = *data++;
155 k1 *= m; k1 ^= k1 >> r; k1 *= m;
156 h1 *= m; h1 ^= k1;
157 len -= 4;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000158
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000159 uint32_t k2 = *data++;
160 k2 *= m; k2 ^= k2 >> r; k2 *= m;
161 h2 *= m; h2 ^= k2;
162 len -= 4;
163 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000164
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000165 if(len >= 4)
166 {
167 uint32_t k1 = *data++;
168 k1 *= m; k1 ^= k1 >> r; k1 *= m;
169 h1 *= m; h1 ^= k1;
170 len -= 4;
171 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000172
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000173 switch(len)
174 {
175 case 3: h2 ^= ((unsigned char*)data)[2] << 16;
176 case 2: h2 ^= ((unsigned char*)data)[1] << 8;
177 case 1: h2 ^= ((unsigned char*)data)[0];
178 h2 *= m;
179 };
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000180
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000181 h1 ^= h2 >> 18; h1 *= m;
182 h2 ^= h1 >> 22; h2 *= m;
183 h1 ^= h2 >> 17; h1 *= m;
184 h2 ^= h1 >> 19; h2 *= m;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000185
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000186 uint64_t h = h1;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000187
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000188 h = (h << 32) | h2;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000189
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000190 return h;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000191}
192
193//-----------------------------------------------------------------------------
194// MurmurHash2A, by Austin Appleby
195
196// This is a variant of MurmurHash2 modified to use the Merkle-Damgard
197// construction. Bulk speed should be identical to Murmur2, small-key speed
198// will be 10%-20% slower due to the added overhead at the end of the hash.
199
200// This variant fixes a minor issue where null keys were more likely to
201// collide with each other than expected, and also makes the function
202// more amenable to incremental implementations.
203
204#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
205
206uint32_t MurmurHash2A ( const void * key, int len, uint32_t seed )
207{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000208 const uint32_t m = 0x5bd1e995;
209 const int r = 24;
210 uint32_t l = len;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000211
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000212 const unsigned char * data = (const unsigned char *)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000213
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000214 uint32_t h = seed;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000215
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000216 while(len >= 4)
217 {
218 uint32_t k = *(uint32_t*)data;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000219
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000220 mmix(h,k);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000221
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000222 data += 4;
223 len -= 4;
224 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000225
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000226 uint32_t t = 0;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000227
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000228 switch(len)
229 {
230 case 3: t ^= data[2] << 16;
231 case 2: t ^= data[1] << 8;
232 case 1: t ^= data[0];
233 };
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000234
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000235 mmix(h,t);
236 mmix(h,l);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000237
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000238 h ^= h >> 13;
239 h *= m;
240 h ^= h >> 15;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000241
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000242 return h;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000243}
244
245//-----------------------------------------------------------------------------
246// CMurmurHash2A, by Austin Appleby
247
248// This is a sample implementation of MurmurHash2A designed to work
249// incrementally.
250
251// Usage -
252
253// CMurmurHash2A hasher
254// hasher.Begin(seed);
255// hasher.Add(data1,size1);
256// hasher.Add(data2,size2);
257// ...
258// hasher.Add(dataN,sizeN);
259// uint32_t hash = hasher.End()
260
261class CMurmurHash2A
262{
263public:
264
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000265 void Begin ( uint32_t seed = 0 )
266 {
267 m_hash = seed;
268 m_tail = 0;
269 m_count = 0;
270 m_size = 0;
271 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000272
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000273 void Add ( const unsigned char * data, int len )
274 {
275 m_size += len;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000276
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000277 MixTail(data,len);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000278
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000279 while(len >= 4)
280 {
281 uint32_t k = *(uint32_t*)data;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000282
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000283 mmix(m_hash,k);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000284
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000285 data += 4;
286 len -= 4;
287 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000288
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000289 MixTail(data,len);
290 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000291
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000292 uint32_t End ( void )
293 {
294 mmix(m_hash,m_tail);
295 mmix(m_hash,m_size);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000296
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000297 m_hash ^= m_hash >> 13;
298 m_hash *= m;
299 m_hash ^= m_hash >> 15;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000300
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000301 return m_hash;
302 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000303
304private:
305
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000306 static const uint32_t m = 0x5bd1e995;
307 static const int r = 24;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000308
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000309 void MixTail ( const unsigned char * & data, int & len )
310 {
311 while( len && ((len<4) || m_count) )
312 {
313 m_tail |= (*data++) << (m_count * 8);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000314
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000315 m_count++;
316 len--;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000317
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000318 if(m_count == 4)
319 {
320 mmix(m_hash,m_tail);
321 m_tail = 0;
322 m_count = 0;
323 }
324 }
325 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000326
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000327 uint32_t m_hash;
328 uint32_t m_tail;
329 uint32_t m_count;
330 uint32_t m_size;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000331};
332
333//-----------------------------------------------------------------------------
334// MurmurHashNeutral2, by Austin Appleby
335
336// Same as MurmurHash2, but endian- and alignment-neutral.
337// Half the speed though, alas.
338
339uint32_t MurmurHashNeutral2 ( const void * key, int len, uint32_t seed )
340{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000341 const uint32_t m = 0x5bd1e995;
342 const int r = 24;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000343
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000344 uint32_t h = seed ^ len;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000345
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000346 const unsigned char * data = (const unsigned char *)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000347
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000348 while(len >= 4)
349 {
350 uint32_t k;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000351
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000352 k = data[0];
353 k |= data[1] << 8;
354 k |= data[2] << 16;
355 k |= data[3] << 24;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000356
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000357 k *= m;
358 k ^= k >> r;
359 k *= m;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000360
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000361 h *= m;
362 h ^= k;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000363
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000364 data += 4;
365 len -= 4;
366 }
367
368 switch(len)
369 {
370 case 3: h ^= data[2] << 16;
371 case 2: h ^= data[1] << 8;
372 case 1: h ^= data[0];
373 h *= m;
374 };
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000375
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000376 h ^= h >> 13;
377 h *= m;
378 h ^= h >> 15;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000379
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000380 return h;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000381}
382
383//-----------------------------------------------------------------------------
384// MurmurHashAligned2, by Austin Appleby
385
386// Same algorithm as MurmurHash2, but only does aligned reads - should be safer
387// on certain platforms.
388
389// Performance will be lower than MurmurHash2
390
391#define MIX(h,k,m) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
392
aappleby@google.comc2b49e02011-04-08 21:13:25 +0000393
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000394uint32_t MurmurHashAligned2 ( const void * key, int len, uint32_t seed )
395{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000396 const uint32_t m = 0x5bd1e995;
397 const int r = 24;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000398
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000399 const unsigned char * data = (const unsigned char *)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000400
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000401 uint32_t h = seed ^ len;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000402
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000403 int align = (uint64_t)data & 3;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000404
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000405 if(align && (len >= 4))
406 {
407 // Pre-load the temp registers
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000408
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000409 uint32_t t = 0, d = 0;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000410
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000411 switch(align)
412 {
413 case 1: t |= data[2] << 16;
414 case 2: t |= data[1] << 8;
415 case 3: t |= data[0];
416 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000417
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000418 t <<= (8 * align);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000419
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000420 data += 4-align;
421 len -= 4-align;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000422
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000423 int sl = 8 * (4-align);
424 int sr = 8 * align;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000425
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000426 // Mix
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000427
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000428 while(len >= 4)
429 {
430 d = *(uint32_t *)data;
431 t = (t >> sr) | (d << sl);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000432
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000433 uint32_t k = t;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000434
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000435 MIX(h,k,m);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000436
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000437 t = d;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000438
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000439 data += 4;
440 len -= 4;
441 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000442
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000443 // Handle leftover data in temp registers
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000444
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000445 d = 0;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000446
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000447 if(len >= align)
448 {
449 switch(align)
450 {
451 case 3: d |= data[2] << 16;
452 case 2: d |= data[1] << 8;
453 case 1: d |= data[0];
454 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000455
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000456 uint32_t k = (t >> sr) | (d << sl);
457 MIX(h,k,m);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000458
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000459 data += align;
460 len -= align;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000461
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000462 //----------
463 // Handle tail bytes
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000464
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000465 switch(len)
466 {
467 case 3: h ^= data[2] << 16;
468 case 2: h ^= data[1] << 8;
469 case 1: h ^= data[0];
470 h *= m;
471 };
472 }
473 else
474 {
475 switch(len)
476 {
477 case 3: d |= data[2] << 16;
478 case 2: d |= data[1] << 8;
479 case 1: d |= data[0];
480 case 0: h ^= (t >> sr) | (d << sl);
481 h *= m;
482 }
483 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000484
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000485 h ^= h >> 13;
486 h *= m;
487 h ^= h >> 15;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000488
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000489 return h;
490 }
491 else
492 {
493 while(len >= 4)
494 {
495 uint32_t k = *(uint32_t *)data;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000496
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000497 MIX(h,k,m);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000498
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000499 data += 4;
500 len -= 4;
501 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000502
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000503 //----------
504 // Handle tail bytes
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000505
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000506 switch(len)
507 {
508 case 3: h ^= data[2] << 16;
509 case 2: h ^= data[1] << 8;
510 case 1: h ^= data[0];
511 h *= m;
512 };
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000513
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000514 h ^= h >> 13;
515 h *= m;
516 h ^= h >> 15;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000517
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000518 return h;
519 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000520}
521
522//-----------------------------------------------------------------------------
523