blob: 2690d60218773920db8173e33665667552e74a84 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#pragma once
#include <vespa/vespalib/stllike/string.h>
namespace search::predicate {
/**
* Hash function used for predicate fields.
*/
struct PredicateHash {
static uint64_t hash64(vespalib::stringref aKey) {
return hash64(aKey.data(), aKey.size());
}
static uint64_t hash64(const void *data, uint32_t origLen) {
uint64_t a, b, c;
int offset; // Current offset into the entire key.
const uint8_t *aKey = static_cast<const uint8_t *>(data);
// Set up the internal state
int anInitval = 0;
a = b = anInitval; // the previous hash value
c = 0x9e3779b97f4a7c13LL; // the golden ratio; an arbitrary value
offset = 0;
uint32_t len = origLen;
// handle most of the key
while (len >= 24) {
a += ((0xffLL & aKey[offset+0]) +
((0xffLL & aKey[offset+1])<<8) +
((0xffLL & aKey[offset+2])<<16) +
((0xffLL & aKey[offset+3])<<24) +
((0xffLL & aKey[offset+4])<<32) +
((0xffLL & aKey[offset+5])<<40) +
((0xffLL & aKey[offset+6])<<48) +
((0xffLL & aKey[offset+7])<<56));
b += ((0xffLL & aKey[offset+8]) +
((0xffLL & aKey[offset+9])<<8) +
((0xffLL & aKey[offset+10])<<16) +
((0xffLL & aKey[offset+11])<<24) +
((0xffLL & aKey[offset+12])<<32) +
((0xffLL & aKey[offset+13])<<40) +
((0xffLL & aKey[offset+14])<<48) +
((0xffLL & aKey[offset+15])<<56));
c += ((0xffLL & aKey[offset+16]) +
((0xffLL & aKey[offset+17])<<8) +
((0xffLL & aKey[offset+18])<<16) +
((0xffLL & aKey[offset+19])<<24) +
((0xffLL & aKey[offset+20])<<32) +
((0xffLL & aKey[offset+21])<<40) +
((0xffLL & aKey[offset+22])<<48) +
((0xffLL & aKey[offset+23])<<56));
// Mix. This arithmetic must match the mix below.
a -= b; a -= c; a ^= (c>>43);
b -= c; b -= a; b ^= (a<<9);
c -= a; c -= b; c ^= (b>>8);
a -= b; a -= c; a ^= (c>>38);
b -= c; b -= a; b ^= (a<<23);
c -= a; c -= b; c ^= (b>>5);
a -= b; a -= c; a ^= (c>>35);
b -= c; b -= a; b ^= (a<<49);
c -= a; c -= b; c ^= (b>>11);
a -= b; a -= c; a ^= (c>>12);
b -= c; b -= a; b ^= (a<<18);
c -= a; c -= b; c ^= (b>>22);
// End mix.
offset += 24; len -= 24;
}
// handle the last 23 bytes
c += origLen;
switch(len) { // all the case statements fall through
case 23: c+=((0xffLL & aKey[offset+22])<<56); [[fallthrough]];
case 22: c+=((0xffLL & aKey[offset+21])<<48); [[fallthrough]];
case 21: c+=((0xffLL & aKey[offset+20])<<40); [[fallthrough]];
case 20: c+=((0xffLL & aKey[offset+19])<<32); [[fallthrough]];
case 19: c+=((0xffLL & aKey[offset+18])<<24); [[fallthrough]];
case 18: c+=((0xffLL & aKey[offset+17])<<16); [[fallthrough]];
case 17: c+=((0xffLL & aKey[offset+16])<<8); [[fallthrough]];
// the first byte of c is reserved for the length
case 16: b+=((0xffLL & aKey[offset+15])<<56); [[fallthrough]];
case 15: b+=((0xffLL & aKey[offset+14])<<48); [[fallthrough]];
case 14: b+=((0xffLL & aKey[offset+13])<<40); [[fallthrough]];
case 13: b+=((0xffLL & aKey[offset+12])<<32); [[fallthrough]];
case 12: b+=((0xffLL & aKey[offset+11])<<24); [[fallthrough]];
case 11: b+=((0xffLL & aKey[offset+10])<<16); [[fallthrough]];
case 10: b+=((0xffLL & aKey[offset+ 9])<<8); [[fallthrough]];
case 9: b+=( 0xffLL & aKey[offset+ 8]); [[fallthrough]];
case 8: a+=((0xffLL & aKey[offset+ 7])<<56); [[fallthrough]];
case 7: a+=((0xffLL & aKey[offset+ 6])<<48); [[fallthrough]];
case 6: a+=((0xffLL & aKey[offset+ 5])<<40); [[fallthrough]];
case 5: a+=((0xffLL & aKey[offset+ 4])<<32); [[fallthrough]];
case 4: a+=((0xffLL & aKey[offset+ 3])<<24); [[fallthrough]];
case 3: a+=((0xffLL & aKey[offset+ 2])<<16); [[fallthrough]];
case 2: a+=((0xffLL & aKey[offset+ 1])<<8); [[fallthrough]];
case 1: a+=( 0xffLL & aKey[offset+ 0]);
// case 0: nothing left to add
}
// Mix. This arithmetic must match the mix above.
a -= b; a -= c; a ^= (c>>43);
b -= c; b -= a; b ^= (a<<9);
c -= a; c -= b; c ^= (b>>8);
a -= b; a -= c; a ^= (c>>38);
b -= c; b -= a; b ^= (a<<23);
c -= a; c -= b; c ^= (b>>5);
a -= b; a -= c; a ^= (c>>35);
b -= c; b -= a; b ^= (a<<49);
c -= a; c -= b; c ^= (b>>11);
a -= b; a -= c; a ^= (c>>12);
b -= c; b -= a; b ^= (a<<18);
c -= a; c -= b; c ^= (b>>22);
// End mix.
return c;
}
};
}
|
