source: icXML/icXML-devel/src/icxmlc/murmurhash3.h @ 2720

Last change on this file since 2720 was 2720, checked in by cameron, 6 years ago

Initial check-in of icXML 0.8 source files

File size: 11.6 KB
Line 
1/*
2 *  Copyright © 2012 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icXML is a trademark of International Characters.
5 */
6
7/*
8 * @author Nigel Medforth, nigelm -at- interational-characters.com
9 * @version $Id: murmurhash3.h 207 2012-12-02 20:38:22Z robc $
10 *
11 */
12
13#ifndef MURMURHASH3_H
14#define MURMURHASH3_H
15
16#include <simd-lib/bitblock.hpp>
17
18#if defined(_MSC_VER)
19#include <stdlib.h>
20#define ROTL32(x,y)     _rotl(x,y)
21#define ROTL64(x,y)     _rotl64(x,y)
22#define BIG_CONSTANT(x) (x)
23#else   // defined(_MSC_VER)
24#define ROTL32(x,r)     (((x) << (r)) | ((x) >> (32 - (r))))
25#define ROTL64(x,r)     (((x) << (r)) | ((x) >> (64 - (r))))
26#define BIG_CONSTANT(x) (x##LLU)
27#endif // !defined(_MSC_VER)
28
29// MurmurHash3 32 x86, by Austin Appleby -- may require inclusion of MIT license?
30
31#define ALLOW_UNSAFE_CASTING
32
33typedef scanword_t hash_t;
34
35template<typename Char>
36class Murmur3
37{
38
39        public:
40
41                IDISA_ALWAYS_INLINE
42                static hash_t hash(const Char * const key, const hash_t length, const hash_t seed);
43
44        protected:
45
46                Murmur3() {}
47
48                virtual ~Murmur3() = 0;
49
50        private:
51
52                IDISA_ALWAYS_INLINE
53                static uint32_t hash32(const Char * const key, const hash_t length, const hash_t seed);
54
55                IDISA_ALWAYS_INLINE
56                static uint64_t hash64(const Char * const key, const hash_t length, const hash_t seed);
57
58                /// -----------------------------------------------------------------------------
59                /// Finalization mix - force all bits of a hash block to avalanche
60
61                IDISA_ALWAYS_INLINE
62                static uint32_t fmix32(uint32_t h)
63                {
64                        h ^= h >> 16;
65                        h *= 0x85ebca6b;
66                        h ^= h >> 13;
67                        h *= 0xc2b2ae35;
68                        h ^= h >> 16;
69                        return h;
70                }
71
72                IDISA_ALWAYS_INLINE
73                static uint64_t fmix64(uint64_t k)
74                {
75                        k ^= k >> 33;
76                        k *= BIG_CONSTANT(0xff51afd7ed558ccd);
77                        k ^= k >> 33;
78                        k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
79                        k ^= k >> 33;
80                        return k;
81                }
82
83};
84
85/// --------------------------------------------------------------------------------------------------------------
86/// N-BIT VERSION
87/// --------------------------------------------------------------------------------------------------------------
88
89template<typename Char>
90IDISA_ALWAYS_INLINE
91hash_t Murmur3<Char>::hash
92(
93        const Char * const              key
94        , const hash_t                  length
95        , const hash_t                  seed
96)
97{
98        if (unlikely(length == 0))
99        {
100                return seed;
101        }
102
103        if (sizeof(hash_t) == 8)
104        {
105                return static_cast<hash_t>(hash64(key, length, seed));
106        }
107        else
108        {
109                return static_cast<hash_t>(hash32(key, length, seed));
110        }
111}
112
113/// --------------------------------------------------------------------------------------------------------------
114/// 32-BIT VERSION
115/// --------------------------------------------------------------------------------------------------------------
116
117template<typename Char>
118IDISA_ALWAYS_INLINE
119uint32_t Murmur3<Char>::hash32
120(
121        const Char * const              key
122        , const hash_t                  length
123        , const hash_t                  seed
124)
125{
126        //const uint32_t ONE = 1;
127        const uint32_t CHARS_PER_HASH = (sizeof(uint32_t) / sizeof(Char));
128        const uint32_t LOG_2_CHARS_PER_HASH = CONST_LOG_2(CHARS_PER_HASH);
129        const uint32_t N_LOG_2_CHARS_PER_HASH = (sizeof(Char) * LOG_2_CHARS_PER_HASH);
130
131        const uint32_t BLOCKS = (length) >> LOG_2_CHARS_PER_HASH;
132
133        const uint32_t c1 = 0xcc9e2d51;
134        const uint32_t c2 = 0x1b873593;
135        const uint32_t c3 = 0xe6546b64;
136
137        const uint32_t * const BLOCK = reinterpret_cast<const uint32_t *>(key);
138
139        register uint32_t h = seed;
140        register uint32_t k;
141
142        for (uint32_t i = 0; i < BLOCKS; i++)
143        {
144                k = BLOCK[i];
145
146                k *= c1;
147                k = ROTL32(k, 15);
148                k *= c2;
149
150                h ^= k;
151                h = ROTL32(h, 13);
152                h = (h * 5) + c3;
153        }
154
155        #ifdef ALLOW_UNSAFE_CASTING
156
157                const register uint32_t t = length & (CHARS_PER_HASH - 1);
158                if (likely(t != 0))
159                {
160                        k = BLOCK[BLOCKS] << ((CHARS_PER_HASH - t) << N_LOG_2_CHARS_PER_HASH);
161                        k *= c1;
162                        k ^= ROTL32(k, 15);
163                        k *= c2;
164                        h ^= k;
165                }
166        #else
167
168                const Char * const tail =
169                        reinterpret_cast<const Char*>(&BLOCK[BLOCKS]);
170
171                k = 0;
172
173                if (sizeof(Char) == 1)
174                {
175                        switch ((length) & (CHARS_PER_HASH - 1))
176                        {
177                                case 3:         k  = (tail[2]) << 16;
178                                case 2:         k ^= (tail[1]) << 8;
179                                case 1:         k ^= (tail[0]);
180                                                        k *= c1;
181                                                        k = ROTL32(k, 15);
182                                                        k *= c2;
183                                                        h ^= k;
184                                case 0:         break;
185                                default:        UNREACHABLE;
186                        };
187                }
188                else if (sizeof(Char) == 2)
189                {
190                        switch ((length) & (CHARS_PER_HASH - 1))
191                        {
192                                case 1:         k ^= (tail[0]);
193                                                        k *= c1;
194                                                        k = ROTL32(k, 15);
195                                                        k *= c2;
196                                                        h ^= k;
197                                case 0:         break;
198                                default:        UNREACHABLE;
199                        };
200                }
201
202        #endif
203
204        return fmix32(h ^ length);
205}
206
207/// --------------------------------------------------------------------------------------------------------------
208/// 64-BIT VERSION
209/// --------------------------------------------------------------------------------------------------------------
210
211#if 1
212
213template<typename Char>
214IDISA_ALWAYS_INLINE
215uint64_t Murmur3<Char>::hash64
216(
217        const Char * const              key
218        , const hash_t                  length
219        , const hash_t                  seed
220)
221{
222//      const uint64_t ONE = 1;
223        const uint64_t CHARS_PER_HASH = (sizeof(uint64_t) / sizeof(Char));
224        const uint64_t LOG_2_CHARS_PER_HASH = CONST_LOG_2(CHARS_PER_HASH);
225        const uint64_t N_LOG_2_CHARS_PER_HASH = (sizeof(Char) * LOG_2_CHARS_PER_HASH);
226
227        const uint64_t BLOCKS = (length >> LOG_2_CHARS_PER_HASH);
228        const uint64_t * const BLOCK = reinterpret_cast<const uint64_t * const>(key);
229
230        register uint64_t h = seed;
231
232        const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
233        const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
234        const uint64_t c3 = 0x52dce729;
235
236        register uint64_t k;
237
238        for (uint64_t i = 0; i < BLOCKS; )
239        {
240                k = BLOCK[i++];
241                k *= c1;
242                k  = ROTL64(k, 31);
243                k *= c2;
244                h ^= k;
245                h = ROTL64(h, 27);
246                h = (h * 5) + c3;
247        }
248
249        //----------
250        // tail
251
252        #ifdef ALLOW_UNSAFE_CASTING
253                const register uint64_t t = length & (CHARS_PER_HASH - 1);
254                if (likely(t != 0))
255                {
256                        k = BLOCK[BLOCKS] << ((CHARS_PER_HASH - t) << N_LOG_2_CHARS_PER_HASH);
257                        k *= c1;
258                        k ^= ROTL64(k, 31);
259                        k *= c2;
260                        h ^= k;
261                }
262        #else
263
264                const Char * const tail =
265                        reinterpret_cast<const Char*>(&BLOCK[BLOCKS]);
266
267                k1 = 0;
268
269                if (sizeof(Char) == 1)
270                {
271                        switch (length & (CHARS_PER_HASH - 1))
272                        {
273                                case  7: k1 ^= uint64_t(tail[6]) << 48;
274                                case  6: k1 ^= uint64_t(tail[5]) << 40;
275                                case  5: k1 ^= uint64_t(tail[4]) << 32;
276                                case  4: k1 ^= uint64_t(tail[3]) << 24;
277                                case  3: k1 ^= uint64_t(tail[2]) << 16;
278                                case  2: k1 ^= uint64_t(tail[1]) << 8;
279                                case  1: k1 ^= uint64_t(tail[0]);
280                                                 k1 *= c1;
281                                                 k1  = ROTL64(k1, 31);
282                                                 k1 *= c2;
283                                                 h1 ^= k1;
284                                case 0break;
285                                default: UNREACHABLE;
286                        };
287                }
288                else if (sizeof(Char) == 2)
289                {
290                        switch (length & (CHARS_PER_HASH - 1))
291                        {
292                                case  3: k1 ^= uint64_t(tail[2]) << 32;
293                                case  2: k1 ^= uint64_t(tail[1]) << 16;
294                                case  1: k1 ^= uint64_t(tail[0]);
295                                                 k1 *= c1;
296                                                 k1  = ROTL64(k1, 31);
297                                                 k1 *= c2;
298                                                 h1 ^= k1;
299                                case 0break;
300                                default: UNREACHABLE;
301                        };
302                }
303                else if (sizeof(Char) == 4)
304                {
305                        switch (length & (CHARS_PER_HASH - 1))
306                        {
307
308                                case  1: k1 ^= uint64_t(tail[0]);
309                                                 k1 *= c1;
310                                                 k1  = ROTL64(k1, 31);
311                                                 k1 *= c2;
312                                                 h1 ^= k1;
313                                case 0break;
314                                default: UNREACHABLE;
315                        };
316                }
317
318        #endif
319
320        //----------
321        // finalization
322
323        return fmix64(h ^ length);
324}
325
326#else
327
328/**
329 The official Murmur3 hash for 64 bit uses the following code to seperately mix two 64 bit numbers into a single hash. I found
330 the performance was degraded using it but this could be useful in the symbol table.
331 **/
332
333template<typename Char>
334IDISA_ALWAYS_INLINE
335uint64_t Murmur3<Char>::hash64
336(
337        const Char * const              input
338        , const hash_t                  length
339)
340{
341        enum
342        {
343                CHARS_PER_HASH = (sizeof(uint64_t) / sizeof(Char)) * 2
344                , LOG_2_CHARS_PER_HASH = CONST_LOG_2(CHARS_PER_HASH)
345        };
346
347        const hash_t BLOCKS = (length >> LOG_2_CHARS_PER_HASH);
348        const uint64_t * const BLOCK = reinterpret_cast<const uint64_t * const>(input);
349
350        uint64_t h1 = seed;
351        uint64_t h2 = seed;
352
353        const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
354        const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
355        const uint64_t c3 = 0x52dce729;
356        const uint64_t c4 = 0x38495ab5;
357
358        register uint64_t k1;
359        register uint64_t k2;
360
361        for(hash_t i = 0; i < BLOCKS; i++)
362        {
363                k1 = BLOCK[i << 1];
364                k2 = BLOCK[i << 1 + 1];
365
366                k1 *= c1;
367                k1  = ROTL64(k1,31);
368                k1 *= c2;
369                h1 ^= k1;
370
371                h1 = ROTL64(h1,27);
372                h1 += h2;
373                h1 = (h1 * 5) + c3;
374
375                k2 *= c2;
376                k2  = ROTL64(k2,33);
377                k2 *= c1;
378                h2 ^= k2;
379
380                h2 = ROTL64(h2,31);
381                h2 += h1;
382                h2 = (h2 * 5) + c4;
383        }
384
385        //----------
386        // tail
387
388
389#ifdef ALLOW_UNSAFE_CASTING
390
391        register uint64_t t1 = length & (CHARS_PER_HASH - 1);
392        switch (t1 >> (LOG_2_CHARS_PER_HASH - 1))
393        {
394                case 1:
395                        k2 = BLOCK[(BLOCKS << 1) | 1] >> (t1 - (CHARS_PER_HASH / 2)) << (LOG_2_CHARS_PER_HASH - 1);
396                        k2 *= c2;
397                        k2  = ROTL64(k2,33);
398                        k2 *= c1;
399                        h2 ^= k2;
400                        t1 = 0;
401                case 0:
402                        k1 = BLOCK[BLOCKS << 1] >> (t1 << (LOG_2_CHARS_PER_HASH - 1));
403                        k1 *= c1;
404                        k1  = ROTL64(k1, 31);
405                        k1 *= c2;
406                        h1 ^= k1;
407                        break;
408                default: UNREACHABLE;
409        }
410
411
412#else
413
414        const Char * const tail =
415                reinterpret_cast<const Char*>(&BLOCK[BLOCKS << 1]);
416
417        k1 = 0;
418        k2 = 0;
419
420        if (sizeof(Char) == 1)
421        {
422                switch (length & (CHARS_PER_HASH - 1))
423                {
424                        case 15: k2 ^= uint64_t(tail[14]) << 48;
425                        case 14: k2 ^= uint64_t(tail[13]) << 40;
426                        case 13: k2 ^= uint64_t(tail[12]) << 32;
427                        case 12: k2 ^= uint64_t(tail[11]) << 24;
428                        case 11: k2 ^= uint64_t(tail[10]) << 16;
429                        case 10: k2 ^= uint64_t(tail[ 9]) << 8;
430                        case  9: k2 ^= uint64_t(tail[ 8]);
431                                         k2 *= c2;
432                                         k2  = ROTL64(k2,33);
433                                         k2 *= c1;
434                                         h2 ^= k2;
435                        case 8:  k1  = BLOCK[BLOCKS << 1];
436                                         k1 *= c1;
437                                         k1  = ROTL64(k1, 31);
438                                         k1 *= c2;
439                                         h1 ^= k1;
440                                         break;
441                        case  7: k1 ^= uint64_t(tail[ 6]) << 48;
442                        case  6: k1 ^= uint64_t(tail[ 5]) << 40;
443                        case  5: k1 ^= uint64_t(tail[ 4]) << 32;
444                        case  4: k1 ^= uint64_t(tail[ 3]) << 24;
445                        case  3: k1 ^= uint64_t(tail[ 2]) << 16;
446                        case  2: k1 ^= uint64_t(tail[ 1]) << 8;
447                        case  1: k1 ^= uint64_t(tail[ 0]);
448                                         k1 *= c1;
449                                         k1  = ROTL64(k1, 31);
450                                         k1 *= c2;
451                                         h1 ^= k1;
452                        case 0break;
453                        default: UNREACHABLE;
454                };
455        }
456        else if (sizeof(Char) == 2)
457        {
458                switch (length & (CHARS_PER_HASH - 1))
459                {
460                        case  7: k2 ^= uint64_t(tail[10]) << 32;
461                        case  6: k2 ^= uint64_t(tail[ 9]) << 16;
462                        case  5: k2 ^= uint64_t(tail[ 8]);
463                                         k2 *= c2;
464                                         k2  = ROTL64(k2,33);
465                                         k2 *= c1;
466                                         h2 ^= k2;
467                        case  4: k1  = BLOCK[BLOCKS << 1];
468                                         k1 *= c1;
469                                         k1  = ROTL64(k1, 31);
470                                         k1 *= c2;
471                                         h1 ^= k1;
472                                         break;
473                        case  3: k1 ^= uint64_t(tail[ 2]) << 32;
474                        case  2: k1 ^= uint64_t(tail[ 1]) << 16;
475                        case  1: k1 ^= uint64_t(tail[ 0]);
476                                         k1 *= c1;
477                                         k1  = ROTL64(k1, 31);
478                                         k1 *= c2;
479                                         h1 ^= k1;
480                        case 0break;
481                        default: UNREACHABLE;
482                };
483        }
484        else if (sizeof(Char) == 4)
485        {
486                switch (length & (CHARS_PER_HASH - 1))
487                {
488                        case  3: k2 ^= uint64_t(tail[ 8]);
489                                         k2 *= c2;
490                                         k2  = ROTL64(k2,33);
491                                         k2 *= c1;
492                                         h2 ^= k2;
493                        case  2: k1  = BLOCK[BLOCKS << 1];
494                                         k1 *= c1;
495                                         k1  = ROTL64(k1, 31);
496                                         k1 *= c2;
497                                         h1 ^= k1;
498                                         break;
499                        case  1: k1 ^= uint64_t(tail[ 0]);
500                                         k1 *= c1;
501                                         k1  = ROTL64(k1, 31);
502                                         k1 *= c2;
503                                         h1 ^= k1;
504                        case 0break;
505                        default: UNREACHABLE;
506                };
507        }
508        else if (sizeof(Char) == 8)
509        {
510                switch (length & (CHARS_PER_HASH - 1))
511                {
512                        case  1: k1 ^= uint64_t(tail[ 0]) << 0;
513                                         k1 *= c1;
514                                         k1  = ROTL64(k1, 31);
515                                         k1 *= c2;
516                                         h1 ^= k1;
517                        case 0break;
518                        default: UNREACHABLE;
519                };
520        }
521
522#endif
523
524        //----------
525        // finalization
526
527        h1 ^= length;
528        h2 ^= length;
529
530        // h1 += h2;
531        // h2 += h1;
532
533        h1 = fmix64(h1);
534        h2 = fmix64(h2);
535
536        // h1 += h2;
537        // h2 += h1;
538
539        return h1 ^ h2;
540}
541#endif
542
543template<typename Char>
544Murmur3<Char>::~Murmur3() {}
545
546#undef ROTL32
547#undef ROTL64
548
549#ifdef ALLOW_UNSAFE_CASTING
550#undef ALLOW_UNSAFE_CASTING
551#endif
552
553#endif // MURMURHASH3_H
Note: See TracBrowser for help on using the repository browser.