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 2024 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#pragma once
#include <cinttypes>
#include <cstring>
namespace android::ftl::details {
// Based on CityHash64 v1.0.1 (http://code.google.com/p/cityhash/), but slightly
// modernized and trimmed for cases with bounded lengths.
template <typename T = std::uint64_t>
inline T read_unaligned(const void* ptr) {
T v;
std::memcpy(&v, ptr, sizeof(T));
return v;
}
template <bool NonZeroShift = false>
constexpr std::uint64_t rotate(std::uint64_t v, std::uint8_t shift) {
if constexpr (!NonZeroShift) {
if (shift == 0) return v;
}
return (v >> shift) | (v << (64 - shift));
}
constexpr std::uint64_t shift_mix(std::uint64_t v) {
return v ^ (v >> 47);
}
__attribute__((no_sanitize("unsigned-integer-overflow")))
constexpr std::uint64_t hash_length_16(std::uint64_t u, std::uint64_t v) {
constexpr std::uint64_t kPrime = 0x9ddfea08eb382d69ull;
auto a = (u ^ v) * kPrime;
a ^= (a >> 47);
auto b = (v ^ a) * kPrime;
b ^= (b >> 47);
b *= kPrime;
return b;
}
constexpr std::uint64_t kPrime0 = 0xc3a5c85c97cb3127ull;
constexpr std::uint64_t kPrime1 = 0xb492b66fbe98f273ull;
constexpr std::uint64_t kPrime2 = 0x9ae16a3b2f90404full;
constexpr std::uint64_t kPrime3 = 0xc949d7c7509e6557ull;
__attribute__((no_sanitize("unsigned-integer-overflow")))
inline std::uint64_t hash_length_0_to_16(const char* str, std::uint64_t length) {
if (length > 8) {
const auto a = read_unaligned(str);
const auto b = read_unaligned(str + length - 8);
return hash_length_16(a, rotate<true>(b + length, static_cast<std::uint8_t>(length))) ^ b;
}
if (length >= 4) {
const auto a = read_unaligned<std::uint32_t>(str);
const auto b = read_unaligned<std::uint32_t>(str + length - 4);
return hash_length_16(length + (a << 3), b);
}
if (length > 0) {
const auto a = static_cast<unsigned char>(str[0]);
const auto b = static_cast<unsigned char>(str[length >> 1]);
const auto c = static_cast<unsigned char>(str[length - 1]);
const auto y = static_cast<std::uint32_t>(a) + (static_cast<std::uint32_t>(b) << 8);
const auto z = static_cast<std::uint32_t>(length) + (static_cast<std::uint32_t>(c) << 2);
return shift_mix(y * kPrime2 ^ z * kPrime3) * kPrime2;
}
return kPrime2;
}
__attribute__((no_sanitize("unsigned-integer-overflow")))
inline std::uint64_t hash_length_17_to_32(const char* str, std::uint64_t length) {
const auto a = read_unaligned(str) * kPrime1;
const auto b = read_unaligned(str + 8);
const auto c = read_unaligned(str + length - 8) * kPrime2;
const auto d = read_unaligned(str + length - 16) * kPrime0;
return hash_length_16(rotate(a - b, 43) + rotate(c, 30) + d,
a + rotate(b ^ kPrime3, 20) - c + length);
}
__attribute__((no_sanitize("unsigned-integer-overflow")))
inline std::uint64_t hash_length_33_to_64(const char* str, std::uint64_t length) {
auto z = read_unaligned(str + 24);
auto a = read_unaligned(str) + (length + read_unaligned(str + length - 16)) * kPrime0;
auto b = rotate(a + z, 52);
auto c = rotate(a, 37);
a += read_unaligned(str + 8);
c += rotate(a, 7);
a += read_unaligned(str + 16);
const auto vf = a + z;
const auto vs = b + rotate(a, 31) + c;
a = read_unaligned(str + 16) + read_unaligned(str + length - 32);
z += read_unaligned(str + length - 8);
b = rotate(a + z, 52);
c = rotate(a, 37);
a += read_unaligned(str + length - 24);
c += rotate(a, 7);
a += read_unaligned(str + length - 16);
const auto wf = a + z;
const auto ws = b + rotate(a, 31) + c;
const auto r = shift_mix((vf + ws) * kPrime2 + (wf + vs) * kPrime0);
return shift_mix(r * kPrime0 + vs) * kPrime2;
}
} // namespace android::ftl::details
|