summaryrefslogtreecommitdiff
path: root/src/common/hash.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/hash.cpp')
-rw-r--r--src/common/hash.cpp97
1 files changed, 64 insertions, 33 deletions
diff --git a/src/common/hash.cpp b/src/common/hash.cpp
index c49c2f60e..5aa5118eb 100644
--- a/src/common/hash.cpp
+++ b/src/common/hash.cpp
@@ -5,7 +5,6 @@
5#if defined(_MSC_VER) 5#if defined(_MSC_VER)
6#include <stdlib.h> 6#include <stdlib.h>
7#endif 7#endif
8
9#include "common_funcs.h" 8#include "common_funcs.h"
10#include "common_types.h" 9#include "common_types.h"
11#include "hash.h" 10#include "hash.h"
@@ -36,7 +35,7 @@ static FORCE_INLINE u64 fmix64(u64 k) {
36// platforms (MurmurHash3_x64_128). It was taken from: 35// platforms (MurmurHash3_x64_128). It was taken from:
37// https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp 36// https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
38void MurmurHash3_128(const void* key, int len, u32 seed, void* out) { 37void MurmurHash3_128(const void* key, int len, u32 seed, void* out) {
39 const u8 * data = (const u8*)key; 38 const u8* data = (const u8*)key;
40 const int nblocks = len / 16; 39 const int nblocks = len / 16;
41 40
42 u64 h1 = seed; 41 u64 h1 = seed;
@@ -47,52 +46,84 @@ void MurmurHash3_128(const void* key, int len, u32 seed, void* out) {
47 46
48 // Body 47 // Body
49 48
50 const u64 * blocks = (const u64 *)(data); 49 const u64* blocks = (const u64*)(data);
51 50
52 for (int i = 0; i < nblocks; i++) { 51 for (int i = 0; i < nblocks; i++) {
53 u64 k1 = getblock64(blocks,i*2+0); 52 u64 k1 = getblock64(blocks, i * 2 + 0);
54 u64 k2 = getblock64(blocks,i*2+1); 53 u64 k2 = getblock64(blocks, i * 2 + 1);
55 54
56 k1 *= c1; k1 = _rotl64(k1,31); k1 *= c2; h1 ^= k1; 55 k1 *= c1;
57 56 k1 = _rotl64(k1, 31);
58 h1 = _rotl64(h1,27); h1 += h2; h1 = h1*5+0x52dce729; 57 k1 *= c2;
59 58 h1 ^= k1;
60 k2 *= c2; k2 = _rotl64(k2,33); k2 *= c1; h2 ^= k2; 59
61 60 h1 = _rotl64(h1, 27);
62 h2 = _rotl64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5; 61 h1 += h2;
62 h1 = h1 * 5 + 0x52dce729;
63
64 k2 *= c2;
65 k2 = _rotl64(k2, 33);
66 k2 *= c1;
67 h2 ^= k2;
68
69 h2 = _rotl64(h2, 31);
70 h2 += h1;
71 h2 = h2 * 5 + 0x38495ab5;
63 } 72 }
64 73
65 // Tail 74 // Tail
66 75
67 const u8 * tail = (const u8*)(data + nblocks*16); 76 const u8* tail = (const u8*)(data + nblocks * 16);
68 77
69 u64 k1 = 0; 78 u64 k1 = 0;
70 u64 k2 = 0; 79 u64 k2 = 0;
71 80
72 switch (len & 15) { 81 switch (len & 15) {
73 case 15: k2 ^= ((u64)tail[14]) << 48; 82 case 15:
74 case 14: k2 ^= ((u64)tail[13]) << 40; 83 k2 ^= ((u64)tail[14]) << 48;
75 case 13: k2 ^= ((u64)tail[12]) << 32; 84 case 14:
76 case 12: k2 ^= ((u64)tail[11]) << 24; 85 k2 ^= ((u64)tail[13]) << 40;
77 case 11: k2 ^= ((u64)tail[10]) << 16; 86 case 13:
78 case 10: k2 ^= ((u64)tail[ 9]) << 8; 87 k2 ^= ((u64)tail[12]) << 32;
79 case 9: k2 ^= ((u64)tail[ 8]) << 0; 88 case 12:
80 k2 *= c2; k2 = _rotl64(k2,33); k2 *= c1; h2 ^= k2; 89 k2 ^= ((u64)tail[11]) << 24;
81 90 case 11:
82 case 8: k1 ^= ((u64)tail[ 7]) << 56; 91 k2 ^= ((u64)tail[10]) << 16;
83 case 7: k1 ^= ((u64)tail[ 6]) << 48; 92 case 10:
84 case 6: k1 ^= ((u64)tail[ 5]) << 40; 93 k2 ^= ((u64)tail[9]) << 8;
85 case 5: k1 ^= ((u64)tail[ 4]) << 32; 94 case 9:
86 case 4: k1 ^= ((u64)tail[ 3]) << 24; 95 k2 ^= ((u64)tail[8]) << 0;
87 case 3: k1 ^= ((u64)tail[ 2]) << 16; 96 k2 *= c2;
88 case 2: k1 ^= ((u64)tail[ 1]) << 8; 97 k2 = _rotl64(k2, 33);
89 case 1: k1 ^= ((u64)tail[ 0]) << 0; 98 k2 *= c1;
90 k1 *= c1; k1 = _rotl64(k1,31); k1 *= c2; h1 ^= k1; 99 h2 ^= k2;
100
101 case 8:
102 k1 ^= ((u64)tail[7]) << 56;
103 case 7:
104 k1 ^= ((u64)tail[6]) << 48;
105 case 6:
106 k1 ^= ((u64)tail[5]) << 40;
107 case 5:
108 k1 ^= ((u64)tail[4]) << 32;
109 case 4:
110 k1 ^= ((u64)tail[3]) << 24;
111 case 3:
112 k1 ^= ((u64)tail[2]) << 16;
113 case 2:
114 k1 ^= ((u64)tail[1]) << 8;
115 case 1:
116 k1 ^= ((u64)tail[0]) << 0;
117 k1 *= c1;
118 k1 = _rotl64(k1, 31);
119 k1 *= c2;
120 h1 ^= k1;
91 }; 121 };
92 122
93 // Finalization 123 // Finalization
94 124
95 h1 ^= len; h2 ^= len; 125 h1 ^= len;
126 h2 ^= len;
96 127
97 h1 += h2; 128 h1 += h2;
98 h2 += h1; 129 h2 += h1;