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
124
125
126
127
128
129
130
131
132
133
134
135
|
//-----------------------------------------------------------------------------
// xxHash Library
// Copyright (c) 2012-2021 Yann Collet
// Copyright (c) 2023 Marvin Borner
// All rights reserved.
//
// BSD 2-Clause License (https://www.opensource.org/licenses/bsd-license.php)
//
// xxHash3
//-----------------------------------------------------------------------------
#include <string.h>
#include <lib/hash.h>
#define XXH_PRIME_1 11400714785074694791ULL
#define XXH_PRIME_2 14029467366897019727ULL
#define XXH_PRIME_3 1609587929392839161ULL
#define XXH_PRIME_4 9650029242287828579ULL
#define XXH_PRIME_5 2870177450012600261ULL
static uint64_t XXH_read64(void *memptr)
{
uint64_t val;
memcpy(&val, memptr, sizeof(val));
return val;
}
static uint32_t XXH_read32(void *memptr)
{
uint32_t val;
memcpy(&val, memptr, sizeof(val));
return val;
}
static uint64_t XXH_rotl64(uint64_t x, int r)
{
return (x << r) | (x >> (64 - r));
}
hash_t hash(void *data, size_t len, uint64_t seed)
{
uint8_t *p = (uint8_t *)data;
uint8_t *end = p + len;
uint64_t h64;
if (len >= 32) {
uint8_t *limit = end - 32;
uint64_t v1 = seed + XXH_PRIME_1 + XXH_PRIME_2;
uint64_t v2 = seed + XXH_PRIME_2;
uint64_t v3 = seed + 0;
uint64_t v4 = seed - XXH_PRIME_1;
do {
v1 += XXH_read64(p) * XXH_PRIME_2;
v1 = XXH_rotl64(v1, 31);
v1 *= XXH_PRIME_1;
v2 += XXH_read64(p + 8) * XXH_PRIME_2;
v2 = XXH_rotl64(v2, 31);
v2 *= XXH_PRIME_1;
v3 += XXH_read64(p + 16) * XXH_PRIME_2;
v3 = XXH_rotl64(v3, 31);
v3 *= XXH_PRIME_1;
v4 += XXH_read64(p + 24) * XXH_PRIME_2;
v4 = XXH_rotl64(v4, 31);
v4 *= XXH_PRIME_1;
p += 32;
} while (p <= limit);
h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) +
XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
v1 *= XXH_PRIME_2;
v1 = XXH_rotl64(v1, 31);
v1 *= XXH_PRIME_1;
h64 ^= v1;
h64 = h64 * XXH_PRIME_1 + XXH_PRIME_4;
v2 *= XXH_PRIME_2;
v2 = XXH_rotl64(v2, 31);
v2 *= XXH_PRIME_1;
h64 ^= v2;
h64 = h64 * XXH_PRIME_1 + XXH_PRIME_4;
v3 *= XXH_PRIME_2;
v3 = XXH_rotl64(v3, 31);
v3 *= XXH_PRIME_1;
h64 ^= v3;
h64 = h64 * XXH_PRIME_1 + XXH_PRIME_4;
v4 *= XXH_PRIME_2;
v4 = XXH_rotl64(v4, 31);
v4 *= XXH_PRIME_1;
h64 ^= v4;
h64 = h64 * XXH_PRIME_1 + XXH_PRIME_4;
} else {
h64 = seed + XXH_PRIME_5;
}
h64 += (uint64_t)len;
while (p + 8 <= end) {
uint64_t k1 = XXH_read64(p);
k1 *= XXH_PRIME_2;
k1 = XXH_rotl64(k1, 31);
k1 *= XXH_PRIME_1;
h64 ^= k1;
h64 = XXH_rotl64(h64, 27) * XXH_PRIME_1 + XXH_PRIME_4;
p += 8;
}
if (p + 4 <= end) {
h64 ^= (uint64_t)(XXH_read32(p)) * XXH_PRIME_1;
h64 = XXH_rotl64(h64, 23) * XXH_PRIME_2 + XXH_PRIME_3;
p += 4;
}
while (p < end) {
h64 ^= (*p) * XXH_PRIME_5;
h64 = XXH_rotl64(h64, 11) * XXH_PRIME_1;
p++;
}
h64 ^= h64 >> 33;
h64 *= XXH_PRIME_2;
h64 ^= h64 >> 29;
h64 *= XXH_PRIME_3;
h64 ^= h64 >> 32;
return h64;
}
|
