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
105// When building the library, we mark some constructors and functions of mersenne_twister as constexpr
106// to allow constant initialization. This will no longer be necessary once this is constexpr in the
107// standard.
108#ifdef _LIBCPP_BUILDING_LIBRARY
109# define _LIBCPP_MERSENNE_TWISTER_CONSTEXPR constexpr
110#else
111# define _LIBCPP_MERSENNE_TWISTER_CONSTEXPR
112#endif
113
114template <class _UIntType,
115 size_t __w,
116 size_t __n,
117 size_t __m,
118 size_t __r,
119 _UIntType __a,
120 size_t __u,
121 _UIntType __d,
122 size_t __s,
123 _UIntType __b,
124 size_t __t,
125 _UIntType __c,
126 size_t __l,
127 _UIntType __f>
128class mersenne_twister_engine {
129public:
130 // types
131 typedef _UIntType result_type;
132
133private:
134 result_type __x_[__n];
135 size_t __i_;
136
137 static_assert(0 < __m, "mersenne_twister_engine invalid parameters");
138 static_assert(__m <= __n, "mersenne_twister_engine invalid parameters");
139 static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
140 static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters");
141 static_assert(2 <= __w, "mersenne_twister_engine invalid parameters");
142 static_assert(__r <= __w, "mersenne_twister_engine invalid parameters");
143 static_assert(__u <= __w, "mersenne_twister_engine invalid parameters");
144 static_assert(__s <= __w, "mersenne_twister_engine invalid parameters");
145 static_assert(__t <= __w, "mersenne_twister_engine invalid parameters");
146 static_assert(__l <= __w, "mersenne_twister_engine invalid parameters");
147
148public:
149 static _LIBCPP_CONSTEXPR const result_type _Min = 0;
150 static _LIBCPP_CONSTEXPR const result_type _Max =
151 __w == _Dt ? result_type(~0) : (result_type(1) << __w) - result_type(1);
152 static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters");
153 static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters");
154 static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters");
155 static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters");
156 static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters");
157 static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters");
158
159 // engine characteristics
160 static inline _LIBCPP_CONSTEXPR const size_t word_size = __w;
161 static inline _LIBCPP_CONSTEXPR const size_t state_size = __n;
162 static inline _LIBCPP_CONSTEXPR const size_t shift_size = __m;
163 static inline _LIBCPP_CONSTEXPR const size_t mask_bits = __r;
164 static inline _LIBCPP_CONSTEXPR const result_type xor_mask = __a;
165 static inline _LIBCPP_CONSTEXPR const size_t tempering_u = __u;
166 static inline _LIBCPP_CONSTEXPR const result_type tempering_d = __d;
167 static inline _LIBCPP_CONSTEXPR const size_t tempering_s = __s;
168 static inline _LIBCPP_CONSTEXPR const result_type tempering_b = __b;
169 static inline _LIBCPP_CONSTEXPR const size_t tempering_t = __t;
170 static inline _LIBCPP_CONSTEXPR const result_type tempering_c = __c;
171 static inline _LIBCPP_CONSTEXPR const size_t tempering_l = __l;
172 static inline _LIBCPP_CONSTEXPR const result_type initialization_multiplier = __f;
173 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
174 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
175 static inline _LIBCPP_CONSTEXPR const result_type default_seed = 5489u;
176
177 // constructors and seeding functions
178#ifndef _LIBCPP_CXX03_LANG
179 _LIBCPP_MERSENNE_TWISTER_CONSTEXPR _LIBCPP_HIDE_FROM_ABI mersenne_twister_engine()
180 : mersenne_twister_engine(default_seed) {}
181 _LIBCPP_MERSENNE_TWISTER_CONSTEXPR _LIBCPP_HIDE_FROM_ABI explicit mersenne_twister_engine(result_type __sd) {
182 seed(__sd);
183 }
184#else
185 _LIBCPP_HIDE_FROM_ABI explicit mersenne_twister_engine(result_type __sd = default_seed) { seed(__sd); }
186#endif
187 template <class _Sseq, __enable_if_t<__is_seed_sequence_v<_Sseq, mersenne_twister_engine>, int> = 0>
188 _LIBCPP_HIDE_FROM_ABI explicit mersenne_twister_engine(_Sseq& __q) {
189 seed(__q);
190 }
191 _LIBCPP_MERSENNE_TWISTER_CONSTEXPR _LIBCPP_HIDE_FROM_ABI void
192 seed(result_type __sd = default_seed) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {
193 __x_[0] = __sd & _Max;
194 for (size_t __i = 1; __i < __n; ++__i)
195 __x_[__i] = (__f * (__x_[__i - 1] ^ __rshift<__w - 2>(__x_[__i - 1])) + __i) & _Max;
196 __i_ = 0;
197 __update_all_states();
198 }
199 template <class _Sseq, __enable_if_t<__is_seed_sequence_v<_Sseq, mersenne_twister_engine>, int> = 0>
200 _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) {
201 const unsigned __k = 1 + (__w - 1) / 32;
202 static_assert(__k <= 2);
203 uint32_t __ar[__n * __k];
204 __q.generate(__ar, __ar + __n * __k);
205 for (size_t __i = 0; __i < __n; ++__i) {
206 if _LIBCPP_CONSTEXPR (__k == 1) {
207 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
208 } else {
209 __x_[__i] = static_cast<result_type>((__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
210 }
211 }
212 const result_type __mask = __r == _Dt ? result_type(~0) : (result_type(1) << __r) - result_type(1);
213 __i_ = 0;
214 if ((__x_[0] & ~__mask) == 0) {
215 size_t __i = 1;
216 for (; __i < __n; ++__i)
217 if (__x_[__i] != 0)
218 break;
219 if (__i == __n)
220 __x_[0] = result_type(1) << (__w - 1);
221 }
222 __update_all_states();
223 }
224
225 _LIBCPP_MERSENNE_TWISTER_CONSTEXPR void __update_state(size_t __i, size_t __k) {
226 const size_t __j = (__i + 1) % __n;
227 const result_type __mask = __r == _Dt ? result_type(~0) : (result_type(1) << __r) - result_type(1);
228 const result_type __yp = (__x_[__i] & ~__mask) | (__x_[__j] & __mask);
229 __x_[__i] = __x_[__k] ^ __rshift<1>(__yp) ^ (__a * (__yp & 1));
230 }
231
232 _LIBCPP_MERSENNE_TWISTER_CONSTEXPR void __update_state(size_t __i) { __update_state(__i, (__i + __m) % __n); }
233
234 _LIBCPP_MERSENNE_TWISTER_CONSTEXPR void __update_all_states() {
235 size_t __i = 0;
236 // This is split into two loops to help the compiler vectorize the code
237 for (; __i != (__n - __m); ++__i)
238 __update_state(__i);
239 for (size_t __j = 0; __i != __n; ++__i, ++__j)
240 __update_state(__i, __j);
241 }
242
243 // generating functions
244 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI result_type operator()() {
245 result_type __val = __x_[__i_];
246 if (++__i_ == __n) [[__unlikely__]] {
247 __update_all_states();
248 __i_ = 0;
249 }
250 result_type __z = __val ^ (__rshift<__u>(__val) & __d);
251 __z ^= __lshift<__s>(__z) & __b;
252 __z ^= __lshift<__t>(__z) & __c;
253 return __z ^ __rshift<__l>(__z);
254 }
255
256 _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) {
257 for (; __z; --__z)
258 (void)operator()();
259 }
260
261 template <class _UInt,
262 size_t _Wp,
263 size_t _Np,
264 size_t _Mp,
265 size_t _Rp,
266 _UInt _Ap,
267 size_t _Up,
268 _UInt _Dp,
269 size_t _Sp,
270 _UInt _Bp,
271 size_t _Tp,
272 _UInt _Cp,
273 size_t _Lp,
274 _UInt _Fp>
275 friend bool operator==(
276 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
277 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
278
279 template <class _CharT,
280 class _Traits,
281 class _UInt,
282 size_t _Wp,
283 size_t _Np,
284 size_t _Mp,
285 size_t _Rp,
286 _UInt _Ap,
287 size_t _Up,
288 _UInt _Dp,
289 size_t _Sp,
290 _UInt _Bp,
291 size_t _Tp,
292 _UInt _Cp,
293 size_t _Lp,
294 _UInt _Fp>
295 friend basic_ostream<_CharT, _Traits>& operator<<(
296 basic_ostream<_CharT, _Traits>& __os,
297 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
298
299 template <class _CharT,
300 class _Traits,
301 class _UInt,
302 size_t _Wp,
303 size_t _Np,
304 size_t _Mp,
305 size_t _Rp,
306 _UInt _Ap,
307 size_t _Up,
308 _UInt _Dp,
309 size_t _Sp,
310 _UInt _Bp,
311 size_t _Tp,
312 _UInt _Cp,
313 size_t _Lp,
314 _UInt _Fp>
315 friend basic_istream<_CharT, _Traits>&
316 operator>>(basic_istream<_CharT, _Traits>& __is,
317 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
318
319private:
320 template <size_t __count>
321 _LIBCPP_HIDE_FROM_ABI static result_type __lshift(result_type __x) {
322 if _LIBCPP_CONSTEXPR (__count < __w) {
323 return (__x << __count) & _Max;
324 } else {
325 return result_type(0);
326 }
327 }
328
329 template <size_t __count>
330 _LIBCPP_MERSENNE_TWISTER_CONSTEXPR _LIBCPP_HIDE_FROM_ABI static result_type __rshift(result_type __x) {
331 if _LIBCPP_CONSTEXPR (__count < _Dt) {
332 return __x >> __count;
333 } else {
334 return result_type(0);
335 }
336 }
337};
338
339template <class _UInt,
340 size_t _Wp,
341 size_t _Np,
342 size_t _Mp,
343 size_t _Rp,
344 _UInt _Ap,
345 size_t _Up,
346 _UInt _Dp,
347 size_t _Sp,
348 _UInt _Bp,
349 size_t _Tp,
350 _UInt _Cp,
351 size_t _Lp,
352 _UInt _Fp>
353_LIBCPP_HIDE_FROM_ABI bool
354operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
355 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y) {
356 if (__x.__i_ == __y.__i_)
357 return std::equal(__x.__x_, __x.__x_ + _Np, __y.__x_);
358 if (__x.__i_ == 0 || __y.__i_ == 0) {
359 size_t __j = std::min(_Np - __x.__i_, _Np - __y.__i_);
360 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j, __y.__x_ + __y.__i_))
361 return false;
362 if (__x.__i_ == 0)
363 return std::equal(__x.__x_ + __j, __x.__x_ + _Np, __y.__x_);
364 return std::equal(__x.__x_, __x.__x_ + (_Np - __j), __y.__x_ + __j);
365 }
366 if (__x.__i_ < __y.__i_) {
367 size_t __j = _Np - __y.__i_;
368 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j), __y.__x_ + __y.__i_))
369 return false;
370 if (!std::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Np, __y.__x_))
371 return false;
372 return std::equal(__x.__x_, __x.__x_ + __x.__i_, __y.__x_ + (_Np - (__x.__i_ + __j)));
373 }
374 size_t __j = _Np - __x.__i_;
375 if (!std::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j), __x.__x_ + __x.__i_))
376 return false;
377 if (!std::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Np, __x.__x_))
378 return false;
379 return std::equal(__y.__x_, __y.__x_ + __y.__i_, __x.__x_ + (_Np - (__y.__i_ + __j)));
380}
381
382template <class _UInt,
383 size_t _Wp,
384 size_t _Np,
385 size_t _Mp,
386 size_t _Rp,
387 _UInt _Ap,
388 size_t _Up,
389 _UInt _Dp,
390 size_t _Sp,
391 _UInt _Bp,
392 size_t _Tp,
393 _UInt _Cp,
394 size_t _Lp,
395 _UInt _Fp>
396inline _LIBCPP_HIDE_FROM_ABI bool
397operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
398 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y) {
399 return !(__x == __y);
400}
401
402template <class _CharT,
403 class _Traits,
404 class _UInt,
405 size_t _Wp,
406 size_t _Np,
407 size_t _Mp,
408 size_t _Rp,
409 _UInt _Ap,
410 size_t _Up,
411 _UInt _Dp,
412 size_t _Sp,
413 _UInt _Bp,
414 size_t _Tp,
415 _UInt _Cp,
416 size_t _Lp,
417 _UInt _Fp>
418_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
419operator<<(basic_ostream<_CharT, _Traits>& __os,
420 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x) {
421 __save_flags<_CharT, _Traits> __lx(__os);
422 typedef basic_ostream<_CharT, _Traits> _Ostream;
423 __os.flags(_Ostream::dec | _Ostream::left);
424 _CharT __sp = __os.widen(' ');
425 __os.fill(__sp);
426 __os << __x.__x_[__x.__i_];
427 for (size_t __j = __x.__i_ + 1; __j < _Np; ++__j)
428 __os << __sp << __x.__x_[__j];
429 for (size_t __j = 0; __j < __x.__i_; ++__j)
430 __os << __sp << __x.__x_[__j];
431 return __os;
432}
433
434template <class _CharT,
435 class _Traits,
436 class _UInt,
437 size_t _Wp,
438 size_t _Np,
439 size_t _Mp,
440 size_t _Rp,
441 _UInt _Ap,
442 size_t _Up,
443 _UInt _Dp,
444 size_t _Sp,
445 _UInt _Bp,
446 size_t _Tp,
447 _UInt _Cp,
448 size_t _Lp,
449 _UInt _Fp>
450_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
451operator>>(basic_istream<_CharT, _Traits>& __is,
452 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x) {
453 __save_flags<_CharT, _Traits> __lx(__is);
454 typedef basic_istream<_CharT, _Traits> _Istream;
455 __is.flags(_Istream::dec | _Istream::skipws);
456 _UInt __t[_Np];
457 for (size_t __i = 0; __i < _Np; ++__i)
458 __is >> __t[__i];
459 if (!__is.fail()) {
460 for (size_t __i = 0; __i < _Np; ++__i)
461 __x.__x_[__i] = __t[__i];
462 __x.__i_ = 0;
463 }
464 return __is;
465}
466
467typedef mersenne_twister_engine<
468 uint_fast32_t,
469 32,
470 624,
471 397,
472 31,
473 0x9908b0df,
474 11,
475 0xffffffff,
476 7,
477 0x9d2c5680,
478 15,
479 0xefc60000,
480 18,
481 1812433253>
482 mt19937;
483typedef mersenne_twister_engine<
484 uint_fast64_t,
485 64,
486 312,
487 156,
488 31,
489 0xb5026f5aa96619e9ULL,
490 29,
491 0x5555555555555555ULL,
492 17,
493 0x71d67fffeda60000ULL,
494 37,
495 0xfff7eee000000000ULL,
496 43,
497 6364136223846793005ULL>
498 mt19937_64;
499
500_LIBCPP_END_NAMESPACE_STD
501
502_LIBCPP_POP_MACROS
503
504#endif // _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H
505