Seregon/ShadPKG

A tool for deriving PKG packet encryption keys for ps4 written in c++

C++/47.3 KB/No license
external/tsl/robin_growth_policy.h
raw
ShadPKG / external / tsl / robin_growth_policy.h
1/**
2 * MIT License
3 *
4 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24#ifndef TSL_ROBIN_GROWTH_POLICY_H
25#define TSL_ROBIN_GROWTH_POLICY_H
26 
27#include <algorithm>
28#include <array>
29#include <climits>
30#include <cmath>
31#include <cstddef>
32#include <cstdint>
33#include <iterator>
34#include <limits>
35#include <ratio>
36#include <stdexcept>
37 
38// A change of the major version indicates an API and/or ABI break (change of
39// in-memory layout of the data structure)
40#define TSL_RH_VERSION_MAJOR 1
41// A change of the minor version indicates the addition of a feature without
42// impact on the API/ABI
43#define TSL_RH_VERSION_MINOR 4
44// A change of the patch version indicates a bugfix without additional
45// functionality
46#define TSL_RH_VERSION_PATCH 0
47 
48#ifdef TSL_DEBUG
49#define tsl_rh_assert(expr) assert(expr)
50#else
51#define tsl_rh_assert(expr) (static_cast<void>(0))
52#endif
53 
54/**
55 * If exceptions are enabled, throw the exception passed in parameter, otherwise
56 * call std::terminate.
57 */
58#if (defined(__cpp_exceptions) || defined(__EXCEPTIONS) || \
59 (defined(_MSC_VER) && defined(_CPPUNWIND))) && \
60 !defined(TSL_NO_EXCEPTIONS)
61#define TSL_RH_THROW_OR_TERMINATE(ex, msg) throw ex(msg)
62#else
63#define TSL_RH_NO_EXCEPTIONS
64#ifdef TSL_DEBUG
65#include <iostream>
66#define TSL_RH_THROW_OR_TERMINATE(ex, msg) \
67 do { \
68 std::cerr << msg << std::endl; \
69 std::terminate(); \
70 } while (0)
71#else
72#define TSL_RH_THROW_OR_TERMINATE(ex, msg) std::terminate()
73#endif
74#endif
75 
76#if defined(__GNUC__) || defined(__clang__)
77#define TSL_RH_LIKELY(exp) (__builtin_expect(!!(exp), true))
78#else
79#define TSL_RH_LIKELY(exp) (exp)
80#endif
81 
82#define TSL_RH_UNUSED(x) static_cast<void>(x)
83 
84namespace tsl {
85namespace rh {
86 
87/**
88 * Grow the hash table by a factor of GrowthFactor keeping the bucket count to a
89 * power of two. It allows the table to use a mask operation instead of a modulo
90 * operation to map a hash to a bucket.
91 *
92 * GrowthFactor must be a power of two >= 2.
93 */
94template <std::size_t GrowthFactor>
95class power_of_two_growth_policy {
96 public:
97 /**
98 * Called on the hash table creation and on rehash. The number of buckets for
99 * the table is passed in parameter. This number is a minimum, the policy may
100 * update this value with a higher value if needed (but not lower).
101 *
102 * If 0 is given, min_bucket_count_in_out must still be 0 after the policy
103 * creation and bucket_for_hash must always return 0 in this case.
104 */
105 explicit power_of_two_growth_policy(std::size_t& min_bucket_count_in_out) {
106 if (min_bucket_count_in_out > max_bucket_count()) {
107 TSL_RH_THROW_OR_TERMINATE(std::length_error,
108 "The hash table exceeds its maximum size.");
109 }
110 
111 if (min_bucket_count_in_out > 0) {
112 min_bucket_count_in_out =
113 round_up_to_power_of_two(min_bucket_count_in_out);
114 m_mask = min_bucket_count_in_out - 1;
115 } else {
116 m_mask = 0;
117 }
118 }
119 
120 /**
121 * Return the bucket [0, bucket_count()) to which the hash belongs.
122 * If bucket_count() is 0, it must always return 0.
123 */
124 std::size_t bucket_for_hash(std::size_t hash) const noexcept {
125 return hash & m_mask;
126 }
127 
128 /**
129 * Return the number of buckets that should be used on next growth.
130 */
131 std::size_t next_bucket_count() const {
132 if ((m_mask + 1) > max_bucket_count() / GrowthFactor) {
133 TSL_RH_THROW_OR_TERMINATE(std::length_error,
134 "The hash table exceeds its maximum size.");
135 }
136 
137 return (m_mask + 1) * GrowthFactor;
138 }
139 
140 /**
141 * Return the maximum number of buckets supported by the policy.
142 */
143 std::size_t max_bucket_count() const {
144 // Largest power of two.
145 return (std::numeric_limits<std::size_t>::max() / 2) + 1;
146 }
147 
148 /**
149 * Reset the growth policy as if it was created with a bucket count of 0.
150 * After a clear, the policy must always return 0 when bucket_for_hash is
151 * called.
152 */
153 void clear() noexcept { m_mask = 0; }
154 
155 private:
156 static std::size_t round_up_to_power_of_two(std::size_t value) {
157 if (is_power_of_two(value)) {
158 return value;
159 }
160 
161 if (value == 0) {
162 return 1;
163 }
164 
165 --value;
166 for (std::size_t i = 1; i < sizeof(std::size_t) * CHAR_BIT; i *= 2) {
167 value |= value >> i;
168 }
169 
170 return value + 1;
171 }
172 
173 static constexpr bool is_power_of_two(std::size_t value) {
174 return value != 0 && (value & (value - 1)) == 0;
175 }
176 
177 protected:
178 static_assert(is_power_of_two(GrowthFactor) && GrowthFactor >= 2,
179 "GrowthFactor must be a power of two >= 2.");
180 
181 std::size_t m_mask;
182};
183 
184/**
185 * Grow the hash table by GrowthFactor::num / GrowthFactor::den and use a modulo
186 * to map a hash to a bucket. Slower but it can be useful if you want a slower
187 * growth.
188 */
189template <class GrowthFactor = std::ratio<3, 2>>
190class mod_growth_policy {
191 public:
192 explicit mod_growth_policy(std::size_t& min_bucket_count_in_out) {
193 if (min_bucket_count_in_out > max_bucket_count()) {
194 TSL_RH_THROW_OR_TERMINATE(std::length_error,
195 "The hash table exceeds its maximum size.");
196 }
197 
198 if (min_bucket_count_in_out > 0) {
199 m_mod = min_bucket_count_in_out;
200 } else {
201 m_mod = 1;
202 }
203 }
204 
205 std::size_t bucket_for_hash(std::size_t hash) const noexcept {
206 return hash % m_mod;
207 }
208 
209 std::size_t next_bucket_count() const {
210 if (m_mod == max_bucket_count()) {
211 TSL_RH_THROW_OR_TERMINATE(std::length_error,
212 "The hash table exceeds its maximum size.");
213 }
214 
215 const double next_bucket_count =
216 std::ceil(double(m_mod) * REHASH_SIZE_MULTIPLICATION_FACTOR);
217 if (!std::isnormal(next_bucket_count)) {
218 TSL_RH_THROW_OR_TERMINATE(std::length_error,
219 "The hash table exceeds its maximum size.");
220 }
221 
222 if (next_bucket_count > double(max_bucket_count())) {
223 return max_bucket_count();
224 } else {
225 return std::size_t(next_bucket_count);
226 }
227 }
228 
229 std::size_t max_bucket_count() const { return MAX_BUCKET_COUNT; }
230 
231 void clear() noexcept { m_mod = 1; }
232 
233 private:
234 static constexpr double REHASH_SIZE_MULTIPLICATION_FACTOR =
235 1.0 * GrowthFactor::num / GrowthFactor::den;
236 static const std::size_t MAX_BUCKET_COUNT =
237 std::size_t(double(std::numeric_limits<std::size_t>::max() /
238 REHASH_SIZE_MULTIPLICATION_FACTOR));
239 
240 static_assert(REHASH_SIZE_MULTIPLICATION_FACTOR >= 1.1,
241 "Growth factor should be >= 1.1.");
242 
243 std::size_t m_mod;
244};
245 
246namespace detail {
247 
248#if SIZE_MAX >= ULLONG_MAX
249#define TSL_RH_NB_PRIMES 51
250#elif SIZE_MAX >= ULONG_MAX
251#define TSL_RH_NB_PRIMES 40
252#else
253#define TSL_RH_NB_PRIMES 23
254#endif
255 
256inline constexpr std::array<std::size_t, TSL_RH_NB_PRIMES> PRIMES = {{
257 1u,
258 5u,
259 17u,
260 29u,
261 37u,
262 53u,
263 67u,
264 79u,
265 97u,
266 131u,
267 193u,
268 257u,
269 389u,
270 521u,
271 769u,
272 1031u,
273 1543u,
274 2053u,
275 3079u,
276 6151u,
277 12289u,
278 24593u,
279 49157u,
280#if SIZE_MAX >= ULONG_MAX
281 98317ul,
282 196613ul,
283 393241ul,
284 786433ul,
285 1572869ul,
286 3145739ul,
287 6291469ul,
288 12582917ul,
289 25165843ul,
290 50331653ul,
291 100663319ul,
292 201326611ul,
293 402653189ul,
294 805306457ul,
295 1610612741ul,
296 3221225473ul,
297 4294967291ul,
298#endif
299#if SIZE_MAX >= ULLONG_MAX
300 6442450939ull,
301 12884901893ull,
302 25769803751ull,
303 51539607551ull,
304 103079215111ull,
305 206158430209ull,
306 412316860441ull,
307 824633720831ull,
308 1649267441651ull,
309 3298534883309ull,
310 6597069766657ull,
311#endif
312}};
313 
314template <unsigned int IPrime>
315static constexpr std::size_t mod(std::size_t hash) {
316 return hash % PRIMES[IPrime];
317}
318 
319// MOD_PRIME[iprime](hash) returns hash % PRIMES[iprime]. This table allows for
320// faster modulo as the compiler can optimize the modulo code better with a
321// constant known at the compilation.
322inline constexpr std::array<std::size_t (*)(std::size_t), TSL_RH_NB_PRIMES>
323 MOD_PRIME = {{
324 &mod<0>, &mod<1>, &mod<2>, &mod<3>, &mod<4>, &mod<5>,
325 &mod<6>, &mod<7>, &mod<8>, &mod<9>, &mod<10>, &mod<11>,
326 &mod<12>, &mod<13>, &mod<14>, &mod<15>, &mod<16>, &mod<17>,
327 &mod<18>, &mod<19>, &mod<20>, &mod<21>, &mod<22>,
328#if SIZE_MAX >= ULONG_MAX
329 &mod<23>, &mod<24>, &mod<25>, &mod<26>, &mod<27>, &mod<28>,
330 &mod<29>, &mod<30>, &mod<31>, &mod<32>, &mod<33>, &mod<34>,
331 &mod<35>, &mod<36>, &mod<37>, &mod<38>, &mod<39>,
332#endif
333#if SIZE_MAX >= ULLONG_MAX
334 &mod<40>, &mod<41>, &mod<42>, &mod<43>, &mod<44>, &mod<45>,
335 &mod<46>, &mod<47>, &mod<48>, &mod<49>, &mod<50>,
336#endif
337 }};
338 
339} // namespace detail
340 
341/**
342 * Grow the hash table by using prime numbers as bucket count. Slower than
343 * tsl::rh::power_of_two_growth_policy in general but will probably distribute
344 * the values around better in the buckets with a poor hash function.
345 *
346 * To allow the compiler to optimize the modulo operation, a lookup table is
347 * used with constant primes numbers.
348 *
349 * With a switch the code would look like:
350 * \code
351 * switch(iprime) { // iprime is the current prime of the hash table
352 * case 0: hash % 5ul;
353 * break;
354 * case 1: hash % 17ul;
355 * break;
356 * case 2: hash % 29ul;
357 * break;
358 * ...
359 * }
360 * \endcode
361 *
362 * Due to the constant variable in the modulo the compiler is able to optimize
363 * the operation by a series of multiplications, substractions and shifts.
364 *
365 * The 'hash % 5' could become something like 'hash - (hash * 0xCCCCCCCD) >> 34)
366 * * 5' in a 64 bits environment.
367 */
368class prime_growth_policy {
369 public:
370 explicit prime_growth_policy(std::size_t& min_bucket_count_in_out) {
371 auto it_prime = std::lower_bound(
372 detail::PRIMES.begin(), detail::PRIMES.end(), min_bucket_count_in_out);
373 if (it_prime == detail::PRIMES.end()) {
374 TSL_RH_THROW_OR_TERMINATE(std::length_error,
375 "The hash table exceeds its maximum size.");
376 }
377 
378 m_iprime = static_cast<unsigned int>(
379 std::distance(detail::PRIMES.begin(), it_prime));
380 if (min_bucket_count_in_out > 0) {
381 min_bucket_count_in_out = *it_prime;
382 } else {
383 min_bucket_count_in_out = 0;
384 }
385 }
386 
387 std::size_t bucket_for_hash(std::size_t hash) const noexcept {
388 return detail::MOD_PRIME[m_iprime](hash);
389 }
390 
391 std::size_t next_bucket_count() const {
392 if (m_iprime + 1 >= detail::PRIMES.size()) {
393 TSL_RH_THROW_OR_TERMINATE(std::length_error,
394 "The hash table exceeds its maximum size.");
395 }
396 
397 return detail::PRIMES[m_iprime + 1];
398 }
399 
400 std::size_t max_bucket_count() const { return detail::PRIMES.back(); }
401 
402 void clear() noexcept { m_iprime = 0; }
403 
404 private:
405 unsigned int m_iprime;
406 
407 static_assert(std::numeric_limits<decltype(m_iprime)>::max() >=
408 detail::PRIMES.size(),
409 "The type of m_iprime is not big enough.");
410};
411 
412} // namespace rh
413} // namespace tsl
414 
415#endif
416