1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H
10#define _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H
11
12#include <__algorithm/equal.h>
13#include <__algorithm/min.h>
14#include <__config>
15#include <__cstddef/size_t.h>
16#include <__random/is_seed_sequence.h>
17#include <__type_traits/enable_if.h>
18#include <cstdint>
19#include <iosfwd>
20#include <limits>
21
22#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
23# pragma GCC system_header
24#endif
25
26_LIBCPP_PUSH_MACROS
27#include <__undef_macros>
28
29_LIBCPP_BEGIN_NAMESPACE_STD
30
31template <class _UIntType,
32 size_t __w,
33 size_t __n,
34 size_t __m,
35 size_t __r,
36 _UIntType __a,
37 size_t __u,
38 _UIntType __d,
39 size_t __s,
40 _UIntType __b,
41 size_t __t,
42 _UIntType __c,
43 size_t __l,
44 _UIntType __f>
45class mersenne_twister_engine;
46
47template <class _UInt,
48 size_t _Wp,
49 size_t _Np,
50 size_t _Mp,
51 size_t _Rp,
52 _UInt _Ap,
53 size_t _Up,
54 _UInt _Dp,
55 size_t _Sp,
56 _UInt _Bp,
57 size_t _Tp,
58 _UInt _Cp,
59 size_t _Lp,
60 _UInt _Fp>
61_LIBCPP_HIDE_FROM_ABI bool
62operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
63 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
64
65template <class _CharT,
66 class _Traits,
67 class _UInt,
68 size_t _Wp,
69 size_t _Np,
70 size_t _Mp,
71 size_t _Rp,
72 _UInt _Ap,
73 size_t _Up,
74 _UInt _Dp,
75 size_t _Sp,
76 _UInt _Bp,
77 size_t _Tp,
78 _UInt _Cp,
79 size_t _Lp,
80 _UInt _Fp>
81_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
82operator<<(basic_ostream<_CharT, _Traits>& __os,
83 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
84
85template <class _CharT,
86 class _Traits,
87 class _UInt,
88 size_t _Wp,
89 size_t _Np,
90 size_t _Mp,
91 size_t _Rp,
92 _UInt _Ap,
93 size_t _Up,
94 _UInt _Dp,
95 size_t _Sp,
96 _UInt _Bp,
97 size_t _Tp,
98 _UInt _Cp,
99 size_t _Lp,
100 _UInt _Fp>
101_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
102operator>>(basic_istream<_CharT, _Traits>& __is,
103 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
104
105template <class _UIntType,
106 size_t __w,
107 size_t __n,
108 size_t __m,
109 size_t __r,
110 _UIntType __a,
111 size_t __u,
112 _UIntType __d,
113 size_t __s,
114 _UIntType __b,
115 size_t __t,
116 _UIntType __c,
117 size_t __l,
118 _UIntType __f>
119class mersenne_twister_engine {
120public:
121 // types
122 typedef _UIntType result_type;
123
124private:
125 result_type __x_[__n];
126 size_t __i_;
127
128 static_assert(0 < __m, "mersenne_twister_engine invalid parameters");
129 static_assert(__m <= __n, "mersenne_twister_engine invalid parameters");
130 static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
131 static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters");
132 static_assert(2 <= __w, "mersenne_twister_engine invalid parameters");
133 static_assert(__r <= __w, "mersenne_twister_engine invalid parameters");
134 static_assert(__u <= __w, "mersenne_twister_engine invalid parameters");
135 static_assert(__s <= __w, "mersenne_twister_engine invalid parameters");
136 static_assert(__t <= __w, "mersenne_twister_engine invalid parameters");
137 static_assert(__l <= __w, "mersenne_twister_engine invalid parameters");
138
139public:
140 static _LIBCPP_CONSTEXPR const result_type _Min = 0;
141 static _LIBCPP_CONSTEXPR const result_type _Max =
142 __w == _Dt ? result_type(~0) : (result_type(1) << __w) - result_type(1);
143 static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters");
144 static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters");
145 static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters");
146 static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters");
147 static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters");
148 static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters");
149
150 // engine characteristics
151 static inline _LIBCPP_CONSTEXPR const size_t word_size = __w;
152 static inline _LIBCPP_CONSTEXPR const size_t state_size = __n;
153 static inline _LIBCPP_CONSTEXPR const size_t shift_size = __m;
154 static inline _LIBCPP_CONSTEXPR const size_t mask_bits = __r;
155 static inline _LIBCPP_CONSTEXPR const result_type xor_mask = __a;
156 static inline _LIBCPP_CONSTEXPR const size_t tempering_u = __u;
157 static inline _LIBCPP_CONSTEXPR const result_type tempering_d = __d;
158 static inline _LIBCPP_CONSTEXPR const size_t tempering_s = __s;
159 static inline _LIBCPP_CONSTEXPR const result_type tempering_b = __b;
160 static inline _LIBCPP_CONSTEXPR const size_t tempering_t = __t;
161 static inline _LIBCPP_CONSTEXPR const result_type tempering_c = __c;
162 static inline _LIBCPP_CONSTEXPR const size_t tempering_l = __l;
163 static inline _LIBCPP_CONSTEXPR const result_type initialization_multiplier = __f;
164 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
165 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
166 static inline _LIBCPP_CONSTEXPR const result_type default_seed = 5489u;
167
168 // constructors and seeding functions
169#ifndef _LIBCPP_CXX03_LANG
170 _LIBCPP_HIDE_FROM_ABI mersenne_twister_engine() : mersenne_twister_engine(default_seed) {}
171 _LIBCPP_HIDE_FROM_ABI explicit mersenne_twister_engine(result_type __sd) { seed(__sd); }
172#else
173 _LIBCPP_HIDE_FROM_ABI explicit mersenne_twister_engine(result_type __sd = default_seed) { seed(__sd); }
174#endif
175 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, mersenne_twister_engine>::value, int> = 0>
176 _LIBCPP_HIDE_FROM_ABI explicit mersenne_twister_engine(_Sseq& __q) {
177 seed(__q);
178 }
179 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd = default_seed) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {
180 __x_[0] = __sd & _Max;
181 for (size_t __i = 1; __i < __n; ++__i)
182 __x_[__i] = (__f * (__x_[__i - 1] ^ __rshift<__w - 2>(__x_[__i - 1])) + __i) & _Max;
183 __i_ = 0;
184 }
185 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, mersenne_twister_engine>::value, int> = 0>
186 _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) {
187 __seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());
188 }
189
190 // generating functions
191 _LIBCPP_HIDE_FROM_ABI result_type operator()() {
192 const size_t __j = (__i_ + 1) % __n;
193 const result_type __mask = __r == _Dt ? result_type(~0) : (result_type(1) << __r) - result_type(1);
194 const result_type __yp = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask);
195 const size_t __k = (__i_ + __m) % __n;
196 __x_[__i_] = __x_[__k] ^ __rshift<1>(__yp) ^ (__a * (__yp & 1));
197 result_type __z = __x_[__i_] ^ (__rshift<__u>(__x_[__i_]) & __d);
198 __i_ = __j;
199 __z ^= __lshift<__s>(__z) & __b;
200 __z ^= __lshift<__t>(__z) & __c;
201 return __z ^ __rshift<__l>(__z);
202 }
203
204 _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) {
205 for (; __z; --__z)
206 operator()();
207 }
208
209 template <class _UInt,
210 size_t _Wp,
211 size_t _Np,
212 size_t _Mp,
213 size_t _Rp,
214 _UInt _Ap,
215 size_t _Up,
216 _UInt _Dp,
217 size_t _Sp,
218 _UInt _Bp,
219 size_t _Tp,
220 _UInt _Cp,
221 size_t _Lp,
222 _UInt _Fp>
223 friend bool operator==(
224 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
225 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
226
227 template <class _CharT,
228 class _Traits,
229 class _UInt,
230 size_t _Wp,
231 size_t _Np,
232 size_t _Mp,
233 size_t _Rp,
234 _UInt _Ap,
235 size_t _Up,
236 _UInt _Dp,
237 size_t _Sp,
238 _UInt _Bp,
239 size_t _Tp,
240 _UInt _Cp,
241 size_t _Lp,
242 _UInt _Fp>
243 friend basic_ostream<_CharT, _Traits>& operator<<(
244 basic_ostream<_CharT, _Traits>& __os,
245 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
246
247 template <class _CharT,
248 class _Traits,
249 class _UInt,
250 size_t _Wp,
251 size_t _Np,
252 size_t _Mp,
253 size_t _Rp,
254 _UInt _Ap,
255 size_t _Up,
256 _UInt _Dp,
257 size_t _Sp,
258 _UInt _Bp,
259 size_t _Tp,
260 _UInt _Cp,
261 size_t _Lp,
262 _UInt _Fp>
263 friend basic_istream<_CharT, _Traits>&
264 operator>>(basic_istream<_CharT, _Traits>& __is,
265 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
266
267private:
268 template <class _Sseq>
269 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>) {
270 const unsigned __k = 1;
271 uint32_t __ar[__n * __k];
272 __q.generate(__ar, __ar + __n * __k);
273 for (size_t __i = 0; __i < __n; ++__i)
274 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
275 const result_type __mask = __r == _Dt ? result_type(~0) : (result_type(1) << __r) - result_type(1);
276 __i_ = 0;
277 if ((__x_[0] & ~__mask) == 0) {
278 for (size_t __i = 1; __i < __n; ++__i)
279 if (__x_[__i] != 0)
280 return;
281 __x_[0] = result_type(1) << (__w - 1);
282 }
283 }
284
285 template <class _Sseq>
286 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>) {
287 const unsigned __k = 2;
288 uint32_t __ar[__n * __k];
289 __q.generate(__ar, __ar + __n * __k);
290 for (size_t __i = 0; __i < __n; ++__i)
291 __x_[__i] = static_cast<result_type>((__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
292 const result_type __mask = __r == _Dt ? result_type(~0) : (result_type(1) << __r) - result_type(1);
293 __i_ = 0;
294 if ((__x_[0] & ~__mask) == 0) {
295 for (size_t __i = 1; __i < __n; ++__i)
296 if (__x_[__i] != 0)
297 return;
298 __x_[0] = result_type(1) << (__w - 1);
299 }
300 }
301
302 template <size_t __count,
303 __enable_if_t<__count< __w, int> = 0> _LIBCPP_HIDE_FROM_ABI static result_type __lshift(result_type __x) {
304 return (__x << __count) & _Max;
305 }
306
307 template <size_t __count, __enable_if_t<(__count >= __w), int> = 0>
308 _LIBCPP_HIDE_FROM_ABI static result_type __lshift(result_type) {
309 return result_type(0);
310 }
311
312 template <size_t __count,
313 __enable_if_t<__count< _Dt, int> = 0> _LIBCPP_HIDE_FROM_ABI static result_type __rshift(result_type __x) {
314 return __x >> __count;
315 }
316
317 template <size_t __count, __enable_if_t<(__count >= _Dt), int> = 0>
318 _LIBCPP_HIDE_FROM_ABI static result_type __rshift(result_type) {
319 return result_type(0);
320 }
321};
322
323template <class _UInt,
324 size_t _Wp,
325 size_t _Np,
326 size_t _Mp,
327 size_t _Rp,
328 _UInt _Ap,
329 size_t _Up,
330 _UInt _Dp,
331 size_t _Sp,
332 _UInt _Bp,
333 size_t _Tp,
334 _UInt _Cp,
335 size_t _Lp,
336 _UInt _Fp>
337_LIBCPP_HIDE_FROM_ABI bool
338operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
339 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y) {
340 if (__x.__i_ == __y.__i_)
341 return std::equal(__x.__x_, __x.__x_ + _Np, __y.__x_);
342 if (__x.__i_ == 0 || __y.__i_ == 0) {
343 size_t __j = std::min(_Np - __x.__i_, _Np - __y.__i_);
344 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j, __y.__x_ + __y.__i_))
345 return false;
346 if (__x.__i_ == 0)
347 return std::equal(__x.__x_ + __j, __x.__x_ + _Np, __y.__x_);
348 return std::equal(__x.__x_, __x.__x_ + (_Np - __j), __y.__x_ + __j);
349 }
350 if (__x.__i_ < __y.__i_) {
351 size_t __j = _Np - __y.__i_;
352 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j), __y.__x_ + __y.__i_))
353 return false;
354 if (!std::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Np, __y.__x_))
355 return false;
356 return std::equal(__x.__x_, __x.__x_ + __x.__i_, __y.__x_ + (_Np - (__x.__i_ + __j)));
357 }
358 size_t __j = _Np - __x.__i_;
359 if (!std::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j), __x.__x_ + __x.__i_))
360 return false;
361 if (!std::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Np, __x.__x_))
362 return false;
363 return std::equal(__y.__x_, __y.__x_ + __y.__i_, __x.__x_ + (_Np - (__y.__i_ + __j)));
364}
365
366template <class _UInt,
367 size_t _Wp,
368 size_t _Np,
369 size_t _Mp,
370 size_t _Rp,
371 _UInt _Ap,
372 size_t _Up,
373 _UInt _Dp,
374 size_t _Sp,
375 _UInt _Bp,
376 size_t _Tp,
377 _UInt _Cp,
378 size_t _Lp,
379 _UInt _Fp>
380inline _LIBCPP_HIDE_FROM_ABI bool
381operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
382 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y) {
383 return !(__x == __y);
384}
385
386template <class _CharT,
387 class _Traits,
388 class _UInt,
389 size_t _Wp,
390 size_t _Np,
391 size_t _Mp,
392 size_t _Rp,
393 _UInt _Ap,
394 size_t _Up,
395 _UInt _Dp,
396 size_t _Sp,
397 _UInt _Bp,
398 size_t _Tp,
399 _UInt _Cp,
400 size_t _Lp,
401 _UInt _Fp>
402_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
403operator<<(basic_ostream<_CharT, _Traits>& __os,
404 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x) {
405 __save_flags<_CharT, _Traits> __lx(__os);
406 typedef basic_ostream<_CharT, _Traits> _Ostream;
407 __os.flags(_Ostream::dec | _Ostream::left);
408 _CharT __sp = __os.widen(' ');
409 __os.fill(__sp);
410 __os << __x.__x_[__x.__i_];
411 for (size_t __j = __x.__i_ + 1; __j < _Np; ++__j)
412 __os << __sp << __x.__x_[__j];
413 for (size_t __j = 0; __j < __x.__i_; ++__j)
414 __os << __sp << __x.__x_[__j];
415 return __os;
416}
417
418template <class _CharT,
419 class _Traits,
420 class _UInt,
421 size_t _Wp,
422 size_t _Np,
423 size_t _Mp,
424 size_t _Rp,
425 _UInt _Ap,
426 size_t _Up,
427 _UInt _Dp,
428 size_t _Sp,
429 _UInt _Bp,
430 size_t _Tp,
431 _UInt _Cp,
432 size_t _Lp,
433 _UInt _Fp>
434_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
435operator>>(basic_istream<_CharT, _Traits>& __is,
436 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x) {
437 __save_flags<_CharT, _Traits> __lx(__is);
438 typedef basic_istream<_CharT, _Traits> _Istream;
439 __is.flags(_Istream::dec | _Istream::skipws);
440 _UInt __t[_Np];
441 for (size_t __i = 0; __i < _Np; ++__i)
442 __is >> __t[__i];
443 if (!__is.fail()) {
444 for (size_t __i = 0; __i < _Np; ++__i)
445 __x.__x_[__i] = __t[__i];
446 __x.__i_ = 0;
447 }
448 return __is;
449}
450
451typedef mersenne_twister_engine<
452 uint_fast32_t,
453 32,
454 624,
455 397,
456 31,
457 0x9908b0df,
458 11,
459 0xffffffff,
460 7,
461 0x9d2c5680,
462 15,
463 0xefc60000,
464 18,
465 1812433253>
466 mt19937;
467typedef mersenne_twister_engine<
468 uint_fast64_t,
469 64,
470 312,
471 156,
472 31,
473 0xb5026f5aa96619e9ULL,
474 29,
475 0x5555555555555555ULL,
476 17,
477 0x71d67fffeda60000ULL,
478 37,
479 0xfff7eee000000000ULL,
480 43,
481 6364136223846793005ULL>
482 mt19937_64;
483
484_LIBCPP_END_NAMESPACE_STD
485
486_LIBCPP_POP_MACROS
487
488#endif // _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H
489