File: mptRandom.h

package info (click to toggle)
libopenmpt 0.4.3-1+deb10u1
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 7,724 kB
  • sloc: cpp: 99,820; sh: 4,503; ansic: 3,449; makefile: 480
file content (630 lines) | stat: -rw-r--r-- 17,582 bytes parent folder | download | duplicates (2)
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
/*
 * mptRandom.h
 * -----------
 * Purpose: PRNG
 * Notes  : (currently none)
 * Authors: OpenMPT Devs
 * The OpenMPT source code is released under the BSD license. Read LICENSE for more details.
 */


#pragma once

#include "BuildSettings.h"

#include "mptMutex.h"

#include <limits>
#include <random>

#ifdef MODPLUG_TRACKER
#include <cstdlib>
#endif // MODPLUG_TRACKER


OPENMPT_NAMESPACE_BEGIN


// NOTE:
//  We implement our own PRNG and distribution functions as the implementations
// of std::uniform_int_distribution is either wrong (not uniform in MSVC2010) or
// not guaranteed to be livelock-free for bad PRNGs (in GCC, Clang, boost).
// We resort to a simpler implementation with only power-of-2 result ranges for
// both the underlying PRNG and our interface function. This saves us from
// complicated code having to deal with partial bits of entropy.
//  Our interface still somewhat follows the mindset of C++11 <random> (with the
// addition of a simple wrapper function mpt::random which saves the caller from
// instantiating distribution objects for the common uniform distribution case.
//  We are still using std::random_device for initial seeding when avalable and
// after working around its set of problems.


namespace mpt
{


#ifdef MPT_BUILD_FUZZER
static const uint32 FUZZER_RNG_SEED = 3141592653u; // pi
#endif // MPT_BUILD_FUZZER


namespace detail
{

MPT_CONSTEXPR11_FUN int lower_bound_entropy_bits(unsigned int x)
{
	// easy to compile-time evaluate even for stupid compilers
	return
		x >= 0xffffffffu ? 32 :
		x >= 0x7fffffffu ? 31 :
		x >= 0x3fffffffu ? 30 :
		x >= 0x1fffffffu ? 29 :
		x >= 0x0fffffffu ? 28 :
		x >= 0x07ffffffu ? 27 :
		x >= 0x03ffffffu ? 26 :
		x >= 0x01ffffffu ? 25 :
		x >= 0x00ffffffu ? 24 :
		x >= 0x007fffffu ? 23 :
		x >= 0x003fffffu ? 22 :
		x >= 0x001fffffu ? 21 :
		x >= 0x000fffffu ? 20 :
		x >= 0x0007ffffu ? 19 :
		x >= 0x0003ffffu ? 18 :
		x >= 0x0001ffffu ? 17 :
		x >= 0x0000ffffu ? 16 :
		x >= 0x00007fffu ? 15 :
		x >= 0x00003fffu ? 14 :
		x >= 0x00001fffu ? 13 :
		x >= 0x00000fffu ? 12 :
		x >= 0x000007ffu ? 11 :
		x >= 0x000003ffu ? 10 :
		x >= 0x000001ffu ?  9 :
		x >= 0x000000ffu ?  8 :
		x >= 0x0000007fu ?  7 :
		x >= 0x0000003fu ?  6 :
		x >= 0x0000001fu ?  5 :
		x >= 0x0000000fu ?  4 :
		x >= 0x00000007u ?  3 :
		x >= 0x00000003u ?  2 :
		x >= 0x00000001u ?  1 :
		0;
}

}


template <typename Trng> struct engine_traits
{
	typedef typename Trng::result_type result_type;
	static MPT_CONSTEXPR11_FUN int result_bits()
	{
		return Trng::result_bits();
	}
	template<typename Trd>
	static inline Trng make(Trd & rd)
	{
		return Trng(rd);
	}
};


template <typename T, typename Trng>
inline T random(Trng & rng)
{
	STATIC_ASSERT(std::numeric_limits<T>::is_integer);
	typedef typename std::make_unsigned<T>::type unsigned_T;
	const unsigned int rng_bits = mpt::engine_traits<Trng>::result_bits();
	unsigned_T result = 0;
	for(std::size_t entropy = 0; entropy < (sizeof(T) * 8); entropy += rng_bits)
	{
		MPT_CONSTANT_IF(rng_bits < (sizeof(T) * 8))
		{
			MPT_CONSTEXPR11_VAR unsigned int shift_bits = rng_bits % (sizeof(T) * 8); // silence utterly stupid MSVC and GCC warnings about shifting by too big amount (in which case this branch is not even taken however)
			result = (result << shift_bits) ^ static_cast<unsigned_T>(rng());
		} else
		{
			result = static_cast<unsigned_T>(rng());
		}
	}
	return static_cast<T>(result);
}

template <typename T, std::size_t required_entropy_bits, typename Trng>
inline T random(Trng & rng)
{
	STATIC_ASSERT(std::numeric_limits<T>::is_integer);
	typedef typename std::make_unsigned<T>::type unsigned_T;
	const unsigned int rng_bits = mpt::engine_traits<Trng>::result_bits();
	unsigned_T result = 0;
	for(std::size_t entropy = 0; entropy < std::min<std::size_t>(required_entropy_bits, sizeof(T) * 8); entropy += rng_bits)
	{
		MPT_CONSTANT_IF(rng_bits < (sizeof(T) * 8))
		{
			MPT_CONSTEXPR11_VAR unsigned int shift_bits = rng_bits % (sizeof(T) * 8); // silence utterly stupid MSVC and GCC warnings about shifting by too big amount (in which case this branch is not even taken however)
			result = (result << shift_bits) ^ static_cast<unsigned_T>(rng());
		} else
		{
			result = static_cast<unsigned_T>(rng());
		}
	}
	MPT_CONSTANT_IF(required_entropy_bits >= (sizeof(T) * 8))
	{
		return static_cast<T>(result);
	} else
	{
		return static_cast<T>(result & ((static_cast<unsigned_T>(1) << required_entropy_bits) - static_cast<unsigned_T>(1)));
	}
}

template <typename T, typename Trng>
inline T random(Trng & rng, std::size_t required_entropy_bits)
{
	STATIC_ASSERT(std::numeric_limits<T>::is_integer);
	typedef typename std::make_unsigned<T>::type unsigned_T;
	const unsigned int rng_bits = mpt::engine_traits<Trng>::result_bits();
	unsigned_T result = 0;
	for(std::size_t entropy = 0; entropy < std::min<std::size_t>(required_entropy_bits, sizeof(T) * 8); entropy += rng_bits)
	{
		MPT_CONSTANT_IF(rng_bits < (sizeof(T) * 8))
		{
			MPT_CONSTEXPR11_VAR unsigned int shift_bits = rng_bits % (sizeof(T) * 8); // silence utterly stupid MSVC and GCC warnings about shifting by too big amount (in which case this branch is not even taken however)
			result = (result << shift_bits) ^ static_cast<unsigned_T>(rng());
		} else
		{
			result = static_cast<unsigned_T>(rng());
		}
	}
	if(required_entropy_bits >= (sizeof(T) * 8))
	{
		return static_cast<T>(result);
	} else
	{
		return static_cast<T>(result & ((static_cast<unsigned_T>(1) << required_entropy_bits) - static_cast<unsigned_T>(1)));
	}
}

template <typename Tf> struct float_traits { };
template <> struct float_traits<float> {
	typedef uint32 mantissa_uint_type;
	enum : int { mantissa_bits = 24 };
};
template <> struct float_traits<double> {
	typedef uint64 mantissa_uint_type;
	enum : int { mantissa_bits = 53 };
};
template <> struct float_traits<long double> {
	typedef uint64 mantissa_uint_type;
	enum : int { mantissa_bits = 63 };
};

template <typename T>
struct uniform_real_distribution
{
private:
	T a;
	T b;
public:
	inline uniform_real_distribution(T a, T b)
		: a(a)
		, b(b)
	{
		return;
	}
	template <typename Trng>
	inline T operator()(Trng & rng) const
	{
		typedef typename float_traits<T>::mantissa_uint_type uint_type;
		const int bits = float_traits<T>::mantissa_bits;
		return ((b - a) * static_cast<T>(mpt::random<uint_type, bits>(rng)) / static_cast<T>((static_cast<uint_type>(1u) << bits))) + a;
	}
};


template <typename T, typename Trng>
inline T random(Trng & rng, T min, T max)
{
	STATIC_ASSERT(!std::numeric_limits<T>::is_integer);
	typedef mpt::uniform_real_distribution<T> dis_type;
	dis_type dis(min, max);
	return static_cast<T>(dis(rng));
}


namespace rng
{

#if MPT_COMPILER_MSVC
#pragma warning(push)
#pragma warning(disable:4724) // potential mod by 0
#endif // MPT_COMPILER_MSVC

template <typename Tstate, typename Tvalue, Tstate m, Tstate a, Tstate c, Tstate result_mask, int result_shift, int result_bits_>
class lcg
{
public:
	typedef Tstate state_type;
	typedef Tvalue result_type;
private:
	state_type state;
public:
	template <typename Trng>
	explicit inline lcg(Trng & rd)
		: state(mpt::random<state_type>(rd))
	{
		operator()(); // we return results from the current state and update state after returning. results in better pipelining.
	}
	explicit inline lcg(state_type seed)
		: state(seed)
	{
		operator()(); // we return results from the current state and update state after returning. results in better pipelining.
	}
public:
	static MPT_CONSTEXPR11_FUN result_type min()
	{
		return static_cast<result_type>(0);
	}
	static MPT_CONSTEXPR11_FUN result_type max()
	{
		STATIC_ASSERT(((result_mask >> result_shift) << result_shift) == result_mask);
		return static_cast<result_type>(result_mask >> result_shift);
	}
	static MPT_CONSTEXPR11_FUN int result_bits()
	{
		STATIC_ASSERT(((static_cast<Tstate>(1) << result_bits_) - 1) == (result_mask >> result_shift));
		return result_bits_;
	}
	inline result_type operator()()
	{
		// we return results from the current state and update state after returning. results in better pipelining.
		state_type s = state;
		result_type result = static_cast<result_type>((s & result_mask) >> result_shift);
		s = Util::ModIfNotZero<state_type, m>((a * s) + c);
		state = s;
		return result;
	}
};

#if MPT_COMPILER_MSVC
#pragma warning(pop)
#endif // MPT_COMPILER_MSVC

typedef lcg<uint32, uint16, 0u, 214013u, 2531011u, 0x7fff0000u, 16, 15> lcg_msvc;
typedef lcg<uint32, uint16, 0x80000000u, 1103515245u, 12345u, 0x7fff0000u, 16, 15> lcg_c99;
typedef lcg<uint64, uint32, 0ull, 6364136223846793005ull, 1ull, 0xffffffff00000000ull, 32, 32> lcg_musl;

} // namespace rng


#ifdef MODPLUG_TRACKER

namespace rng
{

class crand
{
public:
	typedef void state_type;
	typedef int result_type;
private:
	static void reseed(uint32 seed);
public:
	template <typename Trd>
	static void reseed(Trd & rd)
	{
		reseed(mpt::random<uint32>(rd));
	}
public:
	crand() { }
	explicit crand(const std::string &) { }
public:
	static MPT_CONSTEXPR11_FUN result_type min()
	{
		return 0;
	}
	static MPT_CONSTEXPR11_FUN result_type max()
	{
		return RAND_MAX;
	}
	static MPT_CONSTEXPR11_FUN int result_bits()
	{
		return detail::lower_bound_entropy_bits(RAND_MAX);
	}
	result_type operator()();
};

} // namespace rng

#endif // MODPLUG_TRACKER


//  C++11 std::random_device may be implemented as a deterministic PRNG.
//  There is no way to seed this PRNG and it is allowed to be seeded with the
// same value on each program invocation. This makes std::random_device
// completely useless even as a non-cryptographic entropy pool.
//  We fallback to time-seeded std::mt19937 if std::random_device::entropy() is
// 0 or less.
class sane_random_device
{
private:
	mpt::mutex m;
	std::string token;
	std::random_device rd;
	bool rd_reliable;
	std::unique_ptr<std::mt19937> rd_fallback;
public:
	typedef unsigned int result_type;
private:
	void init_fallback();
public:
	sane_random_device();
	sane_random_device(const std::string & token);
	static MPT_CONSTEXPR11_FUN result_type min()
	{
		return std::numeric_limits<result_type>::min();
	}
	static MPT_CONSTEXPR11_FUN result_type max()
	{
		return std::numeric_limits<result_type>::max();
	}
	static MPT_CONSTEXPR11_FUN int result_bits()
	{
		return sizeof(result_type) * 8;
	}
	result_type operator()();
};


template <std::size_t N>
class seed_seq_values
{
private:
	unsigned int seeds[N];
public:
	template <typename Trd>
	explicit seed_seq_values(Trd & rd)
	{
		for(std::size_t i = 0; i < N; ++i)
		{
			seeds[i] = rd();
		}
	}
	const unsigned int * begin() const
	{
		return seeds + 0;
	}
	const unsigned int * end() const
	{
		return seeds + N;
	}
};


// C++11 random does not provide any sane way to determine the amount of entropy
// required to seed a particular engine. VERY STUPID.
// List the ones we are likely to use.

template <> struct engine_traits<std::mt19937> {
	enum : std::size_t { seed_bits = sizeof(std::mt19937::result_type) * 8 * std::mt19937::state_size };
	typedef std::mt19937 rng_type;
	typedef rng_type::result_type result_type;
	static MPT_CONSTEXPR11_FUN int result_bits() { return rng_type::word_size; }
	template<typename Trd> static inline rng_type make(Trd & rd)
	{
		std::unique_ptr<mpt::seed_seq_values<seed_bits / sizeof(unsigned int)>> values = mpt::make_unique<mpt::seed_seq_values<seed_bits / sizeof(unsigned int)>>(rd);
		std::seed_seq seed(values->begin(), values->end());
		return rng_type(seed);
	}
};

template <> struct engine_traits<std::mt19937_64> {
	enum : std::size_t { seed_bits = sizeof(std::mt19937_64::result_type) * 8 * std::mt19937_64::state_size };
	typedef std::mt19937_64 rng_type;
	typedef rng_type::result_type result_type;
	static MPT_CONSTEXPR11_FUN int result_bits() { return rng_type::word_size; }
	template<typename Trd> static inline rng_type make(Trd & rd)
	{
		std::unique_ptr<mpt::seed_seq_values<seed_bits / sizeof(unsigned int)>> values = mpt::make_unique<mpt::seed_seq_values<seed_bits / sizeof(unsigned int)>>(rd);
		std::seed_seq seed(values->begin(), values->end());
		return rng_type(seed);
	}
};

template <> struct engine_traits<std::ranlux24_base> {
	enum : std::size_t { seed_bits = std::ranlux24_base::word_size };
	typedef std::ranlux24_base rng_type;
	typedef rng_type::result_type result_type;
	static MPT_CONSTEXPR11_FUN int result_bits() { return rng_type::word_size; }
	template<typename Trd> static inline rng_type make(Trd & rd)
	{
		mpt::seed_seq_values<seed_bits / sizeof(unsigned int)> values(rd);
		std::seed_seq seed(values.begin(), values.end());
		return rng_type(seed);
	}
};

template <> struct engine_traits<std::ranlux48_base> {
	enum : std::size_t { seed_bits = std::ranlux48_base::word_size };
	typedef std::ranlux48_base rng_type;
	typedef rng_type::result_type result_type;
	static MPT_CONSTEXPR11_FUN int result_bits() { return rng_type::word_size; }
	template<typename Trd> static inline rng_type make(Trd & rd)
	{
		mpt::seed_seq_values<seed_bits / sizeof(unsigned int)> values(rd);
		std::seed_seq seed(values.begin(), values.end());
		return rng_type(seed);
	}
};

template <> struct engine_traits<std::ranlux24> {
	enum : std::size_t { seed_bits = std::ranlux24_base::word_size };
	typedef std::ranlux24 rng_type;
	typedef rng_type::result_type result_type;
	static MPT_CONSTEXPR11_FUN int result_bits() { return std::ranlux24_base::word_size; }
	template<typename Trd> static inline rng_type make(Trd & rd)
	{
		mpt::seed_seq_values<seed_bits / sizeof(unsigned int)> values(rd);
		std::seed_seq seed(values.begin(), values.end());
		return rng_type(seed);
	}
};

template <> struct engine_traits<std::ranlux48> {
	enum : std::size_t { seed_bits = std::ranlux48_base::word_size };
	typedef std::ranlux48 rng_type;
	typedef rng_type::result_type result_type;
	static MPT_CONSTEXPR11_FUN int result_bits() { return std::ranlux48_base::word_size; }
	template<typename Trd> static inline rng_type make(Trd & rd)
	{
		mpt::seed_seq_values<seed_bits / sizeof(unsigned int)> values(rd);
		std::seed_seq seed(values.begin(), values.end());
		return rng_type(seed);
	}
};


class prng_random_device_seeder
{
private:
	uint8 generate_seed8();
	uint16 generate_seed16();
	uint32 generate_seed32();
	uint64 generate_seed64();
protected:
	template <typename T> inline T generate_seed();
protected:
	prng_random_device_seeder();
};

template <> inline uint8 prng_random_device_seeder::generate_seed() { return generate_seed8(); }
template <> inline uint16 prng_random_device_seeder::generate_seed() { return generate_seed16(); }
template <> inline uint32 prng_random_device_seeder::generate_seed() { return generate_seed32(); }
template <> inline uint64 prng_random_device_seeder::generate_seed() { return generate_seed64(); }

template <typename Trng = mpt::rng::lcg_musl>
class prng_random_device
	: public prng_random_device_seeder
{
public:
	typedef unsigned int result_type;
private:
	mpt::mutex m;
	Trng rng;
public:
	prng_random_device()
		: rng(generate_seed<typename Trng::state_type>())
	{
		return;
	}
	prng_random_device(const std::string &)
		: rng(generate_seed<typename Trng::state_type>())
	{
		return;
	}
	static MPT_CONSTEXPR11_FUN result_type min()
	{
		return std::numeric_limits<unsigned int>::min();
	}
	static MPT_CONSTEXPR11_FUN result_type max()
	{
		return std::numeric_limits<unsigned int>::max();
	}
	static MPT_CONSTEXPR11_FUN int result_bits()
	{
		return sizeof(unsigned int) * 8;
	}
	result_type operator()()
	{
		MPT_LOCK_GUARD<mpt::mutex> l(m);
		return mpt::random<unsigned int>(rng);
	}
};


#ifdef MPT_BUILD_FUZZER

//  1. Use deterministic seeding
typedef mpt::prng_random_device<mpt::rng::lcg_musl> random_device;

//  2. Use fast PRNGs in order to not waste time fuzzing more complex PRNG
//     implementations.
typedef mpt::rng::lcg_msvc fast_prng;
typedef mpt::rng::lcg_musl good_prng;

#else // !MPT_BUILD_FUZZER

// mpt::random_device always generates 32 bits of entropy
typedef mpt::sane_random_device random_device;

// We cannot use std::minstd_rand here because it has not a power-of-2 sized
// output domain which we rely upon.
typedef mpt::rng::lcg_msvc fast_prng; // about 3 ALU operations, ~32bit of state, suited for inner loops
typedef std::ranlux48      good_prng;

#endif // MPT_BUILD_FUZZER


typedef mpt::good_prng default_prng;


template <typename Trng, typename Trd>
inline Trng make_prng(Trd & rd)
{
	return mpt::engine_traits<Trng>::make(rd);
}


template <typename Trng>
class thread_safe_prng
	: private Trng
{
private:
	mpt::mutex m;
public:
	typedef typename Trng::result_type result_type;
public:
	template <typename Trd>
	explicit thread_safe_prng(Trd & rd)
		: Trng(mpt::make_prng<Trng>(rd))
	{
		return;
	}
	thread_safe_prng(Trng rng)
		: Trng(rng)
	{
		return;
	}
public:
	static MPT_CONSTEXPR11_FUN typename engine_traits<Trng>::result_type min()
	{
		return Trng::min();
	}
	static MPT_CONSTEXPR11_FUN typename engine_traits<Trng>::result_type max()
	{
		return Trng::max();
	}
	static MPT_CONSTEXPR11_FUN int result_bits()
	{
		return engine_traits<Trng>::result_bits();
	}
public:
	typename engine_traits<Trng>::result_type operator()()
	{
		MPT_LOCK_GUARD<mpt::mutex> l(m);
		return Trng::operator()();
	}
};


mpt::random_device & global_random_device();
mpt::thread_safe_prng<mpt::default_prng> & global_prng();

#if defined(MODPLUG_TRACKER) && !defined(MPT_BUILD_WINESUPPORT)
void set_global_random_device(mpt::random_device *rd);
void set_global_prng(mpt::thread_safe_prng<mpt::default_prng> *rng);
#endif // MODPLUG_TRACKER && !MPT_BUILD_WINESUPPORT


} // namespace mpt


OPENMPT_NAMESPACE_END