Debian Codegraph @

src/mpt/random/device.hpp

raw
1 /* SPDX-License-Identifier: BSL-1.0 OR BSD-3-Clause */
2
3 #ifndef MPT_RANDOM_DEVICE_HPP
4 #define MPT_RANDOM_DEVICE_HPP
5
6
7
8 #include "mpt/base/bit.hpp"
9 #include "mpt/base/detect.hpp"
10 #include "mpt/base/macros.hpp"
11 #include "mpt/base/math.hpp"
12 #include "mpt/base/integer.hpp"
13 #include "mpt/base/namespace.hpp"
14 #include "mpt/crc/crc.hpp"
15 #include "mpt/endian/integer.hpp"
16 #include "mpt/mutex/mutex.hpp"
17 #include "mpt/out_of_memory/out_of_memory.hpp"
18 #include "mpt/random/engine.hpp"
19 #include "mpt/random/engine_lcg.hpp"
20 #include "mpt/random/random.hpp"
21
22 #if !defined(MPT_LIBCXX_QUIRK_NO_CHRONO)
23 #include <chrono>
24 #endif // !MPT_LIBCXX_QUIRK_NO_CHRONO
25 #include <iterator>
26 #include <limits>
27 #include <memory>
28 #include <random>
29 #include <string>
30 #include <vector>
31
32 #include <cmath>
33 #include <cstring>
34 #if defined(MPT_LIBCXX_QUIRK_NO_CHRONO)
35 #include <ctime>
36 #endif // MPT_LIBCXX_QUIRK_NO_CHRONO
37
38
39
40 namespace mpt {
41 inline namespace MPT_INLINE_NS {
42
43
44 inline constexpr uint32 DETERMINISTIC_RNG_SEED = 3141592653u; // pi
45
46
47
48 template <typename T>
49 struct default_random_seed_hash {
50 };
51
52 template <>
53 struct default_random_seed_hash<uint8> {
54 using type = mpt::crc16;
55 };
56
57 template <>
58 struct default_random_seed_hash<uint16> {
59 using type = mpt::crc16;
60 };
61
62 template <>
63 struct default_random_seed_hash<uint32> {
64 using type = mpt::crc32c;
65 };
66
67 template <>
68 struct default_random_seed_hash<uint64> {
69 using type = mpt::crc64_jones;
70 };
71
72
73 class prng_random_device_time_seeder {
74
75 public:
76 template <typename T>
77 inline T generate_seed() {
78 // Note: CRC is actually not that good a choice here, but it is simple and we
79 // already have an implementaion available. Better choices for mixing entropy
80 // would be a hash function with proper avalanche characteristics or a block
81 // or stream cipher with any pre-choosen random key and IV. The only aspect we
82 // really need here is whitening of the bits.
83 typename mpt::default_random_seed_hash<T>::type hash;
84
85 #if !defined(MPT_LIBCXX_QUIRK_NO_CHRONO)
86 {
87 uint64be time;
88 time = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock().now().time_since_epoch()).count();
89 std::byte bytes[sizeof(time)];
90 std::memcpy(bytes, &time, sizeof(time));
91 hash(std::begin(bytes), std::end(bytes));
92 }
93 #if !defined(MPT_COMPILER_QUIRK_CHRONO_NO_HIGH_RESOLUTION_CLOCK)
94 // Avoid std::chrono::high_resolution_clock on Emscripten because availability is problematic in AudioWorklet context.
95 {
96 uint64be time;
97 time = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock().now().time_since_epoch()).count();
98 std::byte bytes[sizeof(time)];
99 std::memcpy(bytes, &time, sizeof(time));
100 hash(std::begin(bytes), std::end(bytes));
101 }
102 #endif // !MPT_COMPILER_QUIRK_CHRONO_NO_HIGH_RESOLUTION_CLOCK
103 #else // MPT_LIBCXX_QUIRK_NO_CHRONO
104 {
105 uint64be time;
106 time = static_cast<uint64>(std::time(nullptr));
107 std::byte bytes[sizeof(time)];
108 std::memcpy(bytes, &time, sizeof(time));
109 hash(std::begin(bytes), std::end(bytes));
110 }
111 #endif // !MPT_LIBCXX_QUIRK_NO_CHRONO
112
113 return static_cast<T>(hash.result());
114 }
115
116 public:
117 prng_random_device_time_seeder() = default;
118 };
119
120
121 // C++11 std::random_device may be implemented as a deterministic PRNG.
122 // There is no way to seed this PRNG and it is allowed to be seeded with the
123 // same value on each program invocation. This makes std::random_device
124 // completely useless even as a non-cryptographic entropy pool.
125 // We fallback to time-seeded std::mt19937 if std::random_device::entropy() is
126 // 0 or less.
127 class sane_random_device {
128 private:
129 mpt::mutex m;
130 std::string token;
131 #if !defined(MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE)
132 std::unique_ptr<std::random_device> prd;
133 #endif // !MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE
134 std::unique_ptr<std::mt19937> rd_fallback;
135
136 public:
137 using result_type = unsigned int;
138
139 private:
140 void init_fallback() {
141 if (!rd_fallback) {
142 if (token.length() > 0) {
143 uint64 seed_val = mpt::prng_random_device_time_seeder().generate_seed<uint64>();
144 std::vector<unsigned int> seeds;
145 seeds.push_back(static_cast<uint32>(seed_val >> 32));
146 seeds.push_back(static_cast<uint32>(seed_val >> 0));
147 for (std::size_t i = 0; i < token.length(); ++i) {
148 seeds.push_back(static_cast<unsigned int>(static_cast<unsigned char>(token[i])));
149 }
150 std::seed_seq seed(seeds.begin(), seeds.end());
151 rd_fallback = std::make_unique<std::mt19937>(seed);
152 } else {
153 uint64 seed_val = mpt::prng_random_device_time_seeder().generate_seed<uint64>();
154 unsigned int seeds[2];
155 seeds[0] = static_cast<uint32>(seed_val >> 32);
156 seeds[1] = static_cast<uint32>(seed_val >> 0);
157 std::seed_seq seed(seeds + 0, seeds + 2);
158 rd_fallback = std::make_unique<std::mt19937>(seed);
159 }
160 }
161 }
162
163 public:
164 sane_random_device() {
165 #if !defined(MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE)
166 try {
167 prd = std::make_unique<std::random_device>();
168 if (!((*prd).entropy() > 0.0)) {
169 init_fallback();
170 }
171 } catch (mpt::out_of_memory e) {
172 mpt::rethrow_out_of_memory(e);
173 } catch (const std::exception &) {
174 init_fallback();
175 }
176 #else // MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE
177 init_fallback();
178 #endif // !MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE
179 }
180 sane_random_device(const std::string & token_)
181 : token(token_) {
182 #if !defined(MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE)
183 try {
184 prd = std::make_unique<std::random_device>(token);
185 if (!((*prd).entropy() > 0.0)) {
186 init_fallback();
187 }
188 } catch (mpt::out_of_memory e) {
189 mpt::rethrow_out_of_memory(e);
190 } catch (const std::exception &) {
191 init_fallback();
192 }
193 #else // MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE
194 init_fallback();
195 #endif // !MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE
196 }
197 static MPT_CONSTEXPRINLINE result_type min() {
198 return std::numeric_limits<result_type>::min();
199 }
200 static MPT_CONSTEXPRINLINE result_type max() {
201 return std::numeric_limits<result_type>::max();
202 }
203 static MPT_CONSTEXPRINLINE int result_bits() {
204 return sizeof(result_type) * 8;
205 }
206 result_type operator()() {
207 mpt::lock_guard<mpt::mutex> l(m);
208 result_type result = 0;
209 #if !defined(MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE)
210 if (prd) {
211 try {
212 if constexpr (std::random_device::min() != 0 || !mpt::is_mask(std::random_device::max())) {
213 // insane std::random_device
214 // This implementation is not exactly uniformly distributed but good enough
215 // for OpenMPT.
216 constexpr double rd_min = static_cast<double>(std::random_device::min());
217 constexpr double rd_max = static_cast<double>(std::random_device::max());
218 constexpr double rd_range = rd_max - rd_min;
219 constexpr double rd_size = rd_range + 1.0;
220 const double rd_entropy = mpt::log2(rd_size);
221 const int iterations = static_cast<int>(std::ceil(result_bits() / rd_entropy));
222 double tmp = 0.0;
223 for (int i = 0; i < iterations; ++i) {
224 tmp = (tmp * rd_size) + (static_cast<double>((*prd)()) - rd_min);
225 }
226 double result_01 = std::floor(tmp / std::pow(rd_size, iterations));
227 result = static_cast<result_type>(std::floor(result_01 * (static_cast<double>(max() - min()) + 1.0))) + min();
228 } else {
229 // sane std::random_device
230 result = 0;
231 std::size_t rd_bits = mpt::lower_bound_entropy_bits(std::random_device::max());
232 for (std::size_t entropy = 0; entropy < (sizeof(result_type) * 8); entropy += rd_bits) {
233 if (rd_bits < (sizeof(result_type) * 8)) {
234 result = (result << rd_bits) | static_cast<result_type>((*prd)());
235 } else {
236 result = result | static_cast<result_type>((*prd)());
237 }
238 }
239 }
240 } catch (const std::exception &) {
241 init_fallback();
242 }
243 }
244 if (rd_fallback) {
245 // std::random_device is unreliable
246 // XOR the generated random number with more entropy from the time-seeded
247 // PRNG.
248 // Note: This is safe even if the std::random_device itself is implemented
249 // as a std::mt19937 PRNG because we are very likely using a different
250 // seed.
251 result ^= mpt::random<result_type>(*rd_fallback);
252 }
253 #else // MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE
254 result ^= mpt::random<result_type>(*rd_fallback);
255 #endif // !MPT_COMPILER_QUIRK_RANDOM_NO_RANDOM_DEVICE
256 return result;
257 }
258 };
259
260
261 class prng_random_device_deterministic_seeder {
262 protected:
263 template <typename T>
264 constexpr T generate_seed() noexcept {
265 return static_cast<T>(mpt::DETERMINISTIC_RNG_SEED);
266 }
267
268 protected:
269 prng_random_device_deterministic_seeder() = default;
270 };
271
272 template <typename Trng = mpt::lcg_musl, typename seeder = mpt::prng_random_device_time_seeder>
273 class prng_random_device
274 : private seeder {
275 public:
276 using result_type = unsigned int;
277
278 private:
279 mpt::mutex m;
280 Trng rng;
281
282 public:
283 prng_random_device()
284 : rng(seeder::template generate_seed<typename Trng::state_type>()) {
285 return;
286 }
287 prng_random_device(const std::string &)
288 : rng(seeder::template generate_seed<typename Trng::state_type>()) {
289 return;
290 }
291 static MPT_CONSTEXPRINLINE result_type min() {
292 return std::numeric_limits<unsigned int>::min();
293 }
294 static MPT_CONSTEXPRINLINE result_type max() {
295 return std::numeric_limits<unsigned int>::max();
296 }
297 static MPT_CONSTEXPRINLINE int result_bits() {
298 return sizeof(unsigned int) * 8;
299 }
300 result_type operator()() {
301 mpt::lock_guard<mpt::mutex> l(m);
302 return mpt::random<unsigned int>(rng);
303 }
304 };
305
306
307 using deterministic_random_device = mpt::prng_random_device<mpt::lcg_musl, mpt::prng_random_device_deterministic_seeder>;
308
309
310 } // namespace MPT_INLINE_NS
311 } // namespace mpt
312
313
314
315 #endif // MPT_RANDOM_DEVICE_HPP