Sourcemeta Core 0.0.0
Loading...
Searching...
No Matches
json_hash.h
1#ifndef SOURCEMETA_CORE_JSON_HASH_H_
2#define SOURCEMETA_CORE_JSON_HASH_H_
3
4#include <sourcemeta/core/numeric.h>
5
6#include <bit> // std::endian
7#include <cassert> // assert
8#include <cstddef> // std::size_t
9#include <cstdint> // std::uint8_t, std::uint64_t
10#include <cstring> // std::memcpy
11#include <functional> // std::reference_wrapper
12
13namespace sourcemeta::core {
14
17template <typename T> struct HashJSON {
18 using hash_type = std::uint64_t;
19
20 auto operator()(const T &value) const noexcept -> hash_type {
21 if constexpr (requires { value.get().fast_hash(); }) {
22 return value.get().fast_hash();
23 } else {
24 return value.fast_hash();
25 }
26 }
27
29 [[nodiscard]]
30 auto is_perfect([[maybe_unused]] const hash_type hash) const noexcept
31 -> bool {
32 return false;
33 }
34};
35
38template <typename T> struct PropertyHashJSON {
40 struct HashType {
44 type a{0};
46 type b{0};
47
48 auto operator==(const HashType &) const noexcept -> bool = default;
49 };
50
52 [[nodiscard]]
53 constexpr auto packed(const char *data, const std::size_t size,
54 const std::uint8_t leading) const noexcept -> HashType {
55 HashType result;
56 assert(size > 0);
57 if consteval {
58 // A constant evaluation cannot memcpy through a reinterpret_cast, so pack
59 // the bytes arithmetically instead. This reproduces the runtime memcpy on
60 // a little-endian target, where the packed bytes read back as the same
61 // integer, which the static assertion enforces so the two can never
62 // silently diverge
63 static_assert(std::endian::native == std::endian::little);
64 result.a = static_cast<HashType::type>(leading);
65 for (std::size_t index = 0; index < size; index += 1) {
66 const auto byte{static_cast<HashType::type>(
67 static_cast<unsigned char>(data[index]))};
68 const auto position{index + 1};
69 if (position < 16) {
70 result.a |= byte << static_cast<int>(8 * position);
71 } else {
72 result.b |= byte << static_cast<int>(8 * (position - 16));
73 }
74 }
75 } else {
76 // The leading byte goes in before the key bytes rather than being merged
77 // in afterwards, as reading the whole hash back to modify it costs more
78 // than computing it in the first place
79 auto *const bytes{reinterpret_cast<unsigned char *>(&result)};
80 bytes[0] = leading;
81 std::memcpy(bytes + 1, data, size);
82 }
83
84 return result;
85 }
86
88 [[nodiscard]]
89 constexpr auto perfect(const char *data,
90 const std::size_t size) const noexcept -> HashType {
91 // The key bytes alone do not tell a key from the same key followed by NUL
92 // bytes, so the leading byte records the size. That makes the hash unique
93 // for every key of at most 31 bytes, and a lookup that matches it has
94 // compared the keys themselves
95 return this->packed(data, size, static_cast<std::uint8_t>(size));
96 }
97
98 // GCC does not optimise well across implicit type conversions such as
99 // std::string to std::string_view, so we provide separate overloads with
100 // duplicated logic instead of unifying on a single parameter type
101
102 constexpr auto operator()(const T &value) const noexcept -> HashType {
103 const auto size{value.size()};
104 switch (size) {
105 case 0:
106 return {};
107 case 1:
108 return this->perfect(value.data(), 1);
109 case 2:
110 return this->perfect(value.data(), 2);
111 case 3:
112 return this->perfect(value.data(), 3);
113 case 4:
114 return this->perfect(value.data(), 4);
115 case 5:
116 return this->perfect(value.data(), 5);
117 case 6:
118 return this->perfect(value.data(), 6);
119 case 7:
120 return this->perfect(value.data(), 7);
121 case 8:
122 return this->perfect(value.data(), 8);
123 case 9:
124 return this->perfect(value.data(), 9);
125 case 10:
126 return this->perfect(value.data(), 10);
127 case 11:
128 return this->perfect(value.data(), 11);
129 case 12:
130 return this->perfect(value.data(), 12);
131 case 13:
132 return this->perfect(value.data(), 13);
133 case 14:
134 return this->perfect(value.data(), 14);
135 case 15:
136 return this->perfect(value.data(), 15);
137 case 16:
138 return this->perfect(value.data(), 16);
139 case 17:
140 return this->perfect(value.data(), 17);
141 case 18:
142 return this->perfect(value.data(), 18);
143 case 19:
144 return this->perfect(value.data(), 19);
145 case 20:
146 return this->perfect(value.data(), 20);
147 case 21:
148 return this->perfect(value.data(), 21);
149 case 22:
150 return this->perfect(value.data(), 22);
151 case 23:
152 return this->perfect(value.data(), 23);
153 case 24:
154 return this->perfect(value.data(), 24);
155 case 25:
156 return this->perfect(value.data(), 25);
157 case 26:
158 return this->perfect(value.data(), 26);
159 case 27:
160 return this->perfect(value.data(), 27);
161 case 28:
162 return this->perfect(value.data(), 28);
163 case 29:
164 return this->perfect(value.data(), 29);
165 case 30:
166 return this->perfect(value.data(), 30);
167 case 31:
168 return this->perfect(value.data(), 31);
169 default:
170 // This case is specifically designed to be constant with regards to
171 // string length, and to exploit the fact that most JSON objects don't
172 // have a lot of entries, so hash collision is not as common. The sum
173 // is kept in 64 bits on purpose, as a modulo of the 128-bit hash type
174 // compiles to a library call rather than to an instruction, and the
175 // leading byte stays past every size that a perfect hash records there
176 const auto leading{32 +
177 ((size + static_cast<unsigned char>(value.front()) +
178 static_cast<unsigned char>(value.back())) %
179 223)};
180 return this->packed(value.data(), 31,
181 static_cast<std::uint8_t>(leading));
182 }
183 }
184
185 constexpr auto operator()(const char *data,
186 const std::size_t size) const noexcept -> HashType {
187 switch (size) {
188 case 0:
189 return {};
190 case 1:
191 return this->perfect(data, 1);
192 case 2:
193 return this->perfect(data, 2);
194 case 3:
195 return this->perfect(data, 3);
196 case 4:
197 return this->perfect(data, 4);
198 case 5:
199 return this->perfect(data, 5);
200 case 6:
201 return this->perfect(data, 6);
202 case 7:
203 return this->perfect(data, 7);
204 case 8:
205 return this->perfect(data, 8);
206 case 9:
207 return this->perfect(data, 9);
208 case 10:
209 return this->perfect(data, 10);
210 case 11:
211 return this->perfect(data, 11);
212 case 12:
213 return this->perfect(data, 12);
214 case 13:
215 return this->perfect(data, 13);
216 case 14:
217 return this->perfect(data, 14);
218 case 15:
219 return this->perfect(data, 15);
220 case 16:
221 return this->perfect(data, 16);
222 case 17:
223 return this->perfect(data, 17);
224 case 18:
225 return this->perfect(data, 18);
226 case 19:
227 return this->perfect(data, 19);
228 case 20:
229 return this->perfect(data, 20);
230 case 21:
231 return this->perfect(data, 21);
232 case 22:
233 return this->perfect(data, 22);
234 case 23:
235 return this->perfect(data, 23);
236 case 24:
237 return this->perfect(data, 24);
238 case 25:
239 return this->perfect(data, 25);
240 case 26:
241 return this->perfect(data, 26);
242 case 27:
243 return this->perfect(data, 27);
244 case 28:
245 return this->perfect(data, 28);
246 case 29:
247 return this->perfect(data, 29);
248 case 30:
249 return this->perfect(data, 30);
250 case 31:
251 return this->perfect(data, 31);
252 default:
253 // This case is specifically designed to be constant with regards to
254 // string length, and to exploit the fact that most JSON objects don't
255 // have a lot of entries, so hash collision is not as common. The sum
256 // is kept in 64 bits on purpose, as a modulo of the 128-bit hash type
257 // compiles to a library call rather than to an instruction, and the
258 // leading byte stays past every size that a perfect hash records there
259 const auto leading{32 + ((size + static_cast<unsigned char>(data[0]) +
260 static_cast<unsigned char>(data[size - 1])) %
261 223)};
262 return this->packed(data, 31, static_cast<std::uint8_t>(leading));
263 }
264 }
265
267 [[nodiscard]]
268 constexpr auto is_perfect(const HashType &hash) const noexcept -> bool {
269 // The first byte holds the size of a perfectly hashed key, so it is at
270 // most 31 and leaves the three bits above that range clear, which no
271 // imperfect hash does. Testing those three bits settles it with a single
272 // masked compare, where comparing the whole byte against 31 needs a mask
273 // and a compare of its own
274 return (hash.a & 224) == 0;
275 }
276};
277
283template <typename T> struct EqualJSON {
284 auto operator()(const T &left, const T &right) const -> bool {
285 if constexpr (requires { left.get() == right.get(); }) {
286 return left.get() == right.get();
287 } else {
288 return left == right;
289 }
290 }
291};
292
293} // namespace sourcemeta::core
294
295#endif
constexpr auto perfect(const char *data, const std::size_t size) const noexcept -> HashType
Compute a perfect hash from raw data.
Definition json_hash.h:89
constexpr auto packed(const char *data, const std::size_t size, const std::uint8_t leading) const noexcept -> HashType
Compute a hash from up to 31 bytes of raw data, behind a leading byte.
Definition json_hash.h:53
constexpr auto is_perfect(const HashType &hash) const noexcept -> bool
Check whether the given hash is a perfect hash.
Definition json_hash.h:268
auto is_perfect(const hash_type hash) const noexcept -> bool
Check whether the given hash is a perfect hash.
Definition json_hash.h:30
Definition json_hash.h:283
Definition json_hash.h:17
Definition json_hash.h:38
Definition numeric_uint128.h:28
The two halves that make up a property key hash.
Definition json_hash.h:40
sourcemeta::core::uint128_t type
The unsigned integer type each half is stored as.
Definition json_hash.h:42
type b
The second half of the hash.
Definition json_hash.h:46
type a
The first half of the hash.
Definition json_hash.h:44