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