593 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H10#define _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H11 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_header24#endif25 26_LIBCPP_PUSH_MACROS27#include <__undef_macros>28 29_LIBCPP_BEGIN_NAMESPACE_STD30 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 bool62operator==(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 _UInt,66 size_t _Wp,67 size_t _Np,68 size_t _Mp,69 size_t _Rp,70 _UInt _Ap,71 size_t _Up,72 _UInt _Dp,73 size_t _Sp,74 _UInt _Bp,75 size_t _Tp,76 _UInt _Cp,77 size_t _Lp,78 _UInt _Fp>79_LIBCPP_HIDE_FROM_ABI bool80operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,81 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y);82 83template <class _CharT,84 class _Traits,85 class _UInt,86 size_t _Wp,87 size_t _Np,88 size_t _Mp,89 size_t _Rp,90 _UInt _Ap,91 size_t _Up,92 _UInt _Dp,93 size_t _Sp,94 _UInt _Bp,95 size_t _Tp,96 _UInt _Cp,97 size_t _Lp,98 _UInt _Fp>99_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&100operator<<(basic_ostream<_CharT, _Traits>& __os,101 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);102 103template <class _CharT,104 class _Traits,105 class _UInt,106 size_t _Wp,107 size_t _Np,108 size_t _Mp,109 size_t _Rp,110 _UInt _Ap,111 size_t _Up,112 _UInt _Dp,113 size_t _Sp,114 _UInt _Bp,115 size_t _Tp,116 _UInt _Cp,117 size_t _Lp,118 _UInt _Fp>119_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&120operator>>(basic_istream<_CharT, _Traits>& __is,121 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);122 123template <class _UIntType,124 size_t __w,125 size_t __n,126 size_t __m,127 size_t __r,128 _UIntType __a,129 size_t __u,130 _UIntType __d,131 size_t __s,132 _UIntType __b,133 size_t __t,134 _UIntType __c,135 size_t __l,136 _UIntType __f>137class mersenne_twister_engine {138public:139 // types140 typedef _UIntType result_type;141 142private:143 result_type __x_[__n];144 size_t __i_;145 146 static_assert(0 < __m, "mersenne_twister_engine invalid parameters");147 static_assert(__m <= __n, "mersenne_twister_engine invalid parameters");148 static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;149 static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters");150 static_assert(2 <= __w, "mersenne_twister_engine invalid parameters");151 static_assert(__r <= __w, "mersenne_twister_engine invalid parameters");152 static_assert(__u <= __w, "mersenne_twister_engine invalid parameters");153 static_assert(__s <= __w, "mersenne_twister_engine invalid parameters");154 static_assert(__t <= __w, "mersenne_twister_engine invalid parameters");155 static_assert(__l <= __w, "mersenne_twister_engine invalid parameters");156 157public:158 static _LIBCPP_CONSTEXPR const result_type _Min = 0;159 static _LIBCPP_CONSTEXPR const result_type _Max =160 __w == _Dt ? result_type(~0) : (result_type(1) << __w) - result_type(1);161 static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters");162 static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters");163 static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters");164 static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters");165 static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters");166 static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters");167 168 // engine characteristics169 static inline _LIBCPP_CONSTEXPR const size_t word_size = __w;170 static inline _LIBCPP_CONSTEXPR const size_t state_size = __n;171 static inline _LIBCPP_CONSTEXPR const size_t shift_size = __m;172 static inline _LIBCPP_CONSTEXPR const size_t mask_bits = __r;173 static inline _LIBCPP_CONSTEXPR const result_type xor_mask = __a;174 static inline _LIBCPP_CONSTEXPR const size_t tempering_u = __u;175 static inline _LIBCPP_CONSTEXPR const result_type tempering_d = __d;176 static inline _LIBCPP_CONSTEXPR const size_t tempering_s = __s;177 static inline _LIBCPP_CONSTEXPR const result_type tempering_b = __b;178 static inline _LIBCPP_CONSTEXPR const size_t tempering_t = __t;179 static inline _LIBCPP_CONSTEXPR const result_type tempering_c = __c;180 static inline _LIBCPP_CONSTEXPR const size_t tempering_l = __l;181 static inline _LIBCPP_CONSTEXPR const result_type initialization_multiplier = __f;182 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type min() { return _Min; }183 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type max() { return _Max; }184 static inline _LIBCPP_CONSTEXPR const result_type default_seed = 5489u;185 186 // constructors and seeding functions187#ifndef _LIBCPP_CXX03_LANG188 _LIBCPP_HIDE_FROM_ABI mersenne_twister_engine() : mersenne_twister_engine(default_seed) {}189 _LIBCPP_HIDE_FROM_ABI explicit mersenne_twister_engine(result_type __sd) { seed(__sd); }190#else191 _LIBCPP_HIDE_FROM_ABI explicit mersenne_twister_engine(result_type __sd = default_seed) { seed(__sd); }192#endif193 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, mersenne_twister_engine>::value, int> = 0>194 _LIBCPP_HIDE_FROM_ABI explicit mersenne_twister_engine(_Sseq& __q) {195 seed(__q);196 }197 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd = default_seed);198 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, mersenne_twister_engine>::value, int> = 0>199 _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) {200 __seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());201 }202 203 // generating functions204 _LIBCPP_HIDE_FROM_ABI result_type operator()();205 _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) {206 for (; __z; --__z)207 operator()();208 }209 210 template <class _UInt,211 size_t _Wp,212 size_t _Np,213 size_t _Mp,214 size_t _Rp,215 _UInt _Ap,216 size_t _Up,217 _UInt _Dp,218 size_t _Sp,219 _UInt _Bp,220 size_t _Tp,221 _UInt _Cp,222 size_t _Lp,223 _UInt _Fp>224 friend bool operator==(225 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,226 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y);227 228 template <class _UInt,229 size_t _Wp,230 size_t _Np,231 size_t _Mp,232 size_t _Rp,233 _UInt _Ap,234 size_t _Up,235 _UInt _Dp,236 size_t _Sp,237 _UInt _Bp,238 size_t _Tp,239 _UInt _Cp,240 size_t _Lp,241 _UInt _Fp>242 friend bool operator!=(243 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,244 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y);245 246 template <class _CharT,247 class _Traits,248 class _UInt,249 size_t _Wp,250 size_t _Np,251 size_t _Mp,252 size_t _Rp,253 _UInt _Ap,254 size_t _Up,255 _UInt _Dp,256 size_t _Sp,257 _UInt _Bp,258 size_t _Tp,259 _UInt _Cp,260 size_t _Lp,261 _UInt _Fp>262 friend basic_ostream<_CharT, _Traits>& operator<<(263 basic_ostream<_CharT, _Traits>& __os,264 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);265 266 template <class _CharT,267 class _Traits,268 class _UInt,269 size_t _Wp,270 size_t _Np,271 size_t _Mp,272 size_t _Rp,273 _UInt _Ap,274 size_t _Up,275 _UInt _Dp,276 size_t _Sp,277 _UInt _Bp,278 size_t _Tp,279 _UInt _Cp,280 size_t _Lp,281 _UInt _Fp>282 friend basic_istream<_CharT, _Traits>&283 operator>>(basic_istream<_CharT, _Traits>& __is,284 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x);285 286private:287 template <class _Sseq>288 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);289 template <class _Sseq>290 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);291 292 template <size_t __count,293 __enable_if_t<__count< __w, int> = 0> _LIBCPP_HIDE_FROM_ABI static result_type __lshift(result_type __x) {294 return (__x << __count) & _Max;295 }296 297 template <size_t __count, __enable_if_t<(__count >= __w), int> = 0>298 _LIBCPP_HIDE_FROM_ABI static result_type __lshift(result_type) {299 return result_type(0);300 }301 302 template <size_t __count,303 __enable_if_t<__count< _Dt, int> = 0> _LIBCPP_HIDE_FROM_ABI static result_type __rshift(result_type __x) {304 return __x >> __count;305 }306 307 template <size_t __count, __enable_if_t<(__count >= _Dt), int> = 0>308 _LIBCPP_HIDE_FROM_ABI static result_type __rshift(result_type) {309 return result_type(0);310 }311};312 313template <class _UIntType,314 size_t __w,315 size_t __n,316 size_t __m,317 size_t __r,318 _UIntType __a,319 size_t __u,320 _UIntType __d,321 size_t __s,322 _UIntType __b,323 size_t __t,324 _UIntType __c,325 size_t __l,326 _UIntType __f>327void mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::seed(328 result_type __sd) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK { // __w >= 2329 __x_[0] = __sd & _Max;330 for (size_t __i = 1; __i < __n; ++__i)331 __x_[__i] = (__f * (__x_[__i - 1] ^ __rshift<__w - 2>(__x_[__i - 1])) + __i) & _Max;332 __i_ = 0;333}334 335template <class _UIntType,336 size_t __w,337 size_t __n,338 size_t __m,339 size_t __r,340 _UIntType __a,341 size_t __u,342 _UIntType __d,343 size_t __s,344 _UIntType __b,345 size_t __t,346 _UIntType __c,347 size_t __l,348 _UIntType __f>349template <class _Sseq>350void mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::__seed(351 _Sseq& __q, integral_constant<unsigned, 1>) {352 const unsigned __k = 1;353 uint32_t __ar[__n * __k];354 __q.generate(__ar, __ar + __n * __k);355 for (size_t __i = 0; __i < __n; ++__i)356 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);357 const result_type __mask = __r == _Dt ? result_type(~0) : (result_type(1) << __r) - result_type(1);358 __i_ = 0;359 if ((__x_[0] & ~__mask) == 0) {360 for (size_t __i = 1; __i < __n; ++__i)361 if (__x_[__i] != 0)362 return;363 __x_[0] = result_type(1) << (__w - 1);364 }365}366 367template <class _UIntType,368 size_t __w,369 size_t __n,370 size_t __m,371 size_t __r,372 _UIntType __a,373 size_t __u,374 _UIntType __d,375 size_t __s,376 _UIntType __b,377 size_t __t,378 _UIntType __c,379 size_t __l,380 _UIntType __f>381template <class _Sseq>382void mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::__seed(383 _Sseq& __q, integral_constant<unsigned, 2>) {384 const unsigned __k = 2;385 uint32_t __ar[__n * __k];386 __q.generate(__ar, __ar + __n * __k);387 for (size_t __i = 0; __i < __n; ++__i)388 __x_[__i] = static_cast<result_type>((__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);389 const result_type __mask = __r == _Dt ? result_type(~0) : (result_type(1) << __r) - result_type(1);390 __i_ = 0;391 if ((__x_[0] & ~__mask) == 0) {392 for (size_t __i = 1; __i < __n; ++__i)393 if (__x_[__i] != 0)394 return;395 __x_[0] = result_type(1) << (__w - 1);396 }397}398 399template <class _UIntType,400 size_t __w,401 size_t __n,402 size_t __m,403 size_t __r,404 _UIntType __a,405 size_t __u,406 _UIntType __d,407 size_t __s,408 _UIntType __b,409 size_t __t,410 _UIntType __c,411 size_t __l,412 _UIntType __f>413_UIntType414mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::operator()() {415 const size_t __j = (__i_ + 1) % __n;416 const result_type __mask = __r == _Dt ? result_type(~0) : (result_type(1) << __r) - result_type(1);417 const result_type __yp = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask);418 const size_t __k = (__i_ + __m) % __n;419 __x_[__i_] = __x_[__k] ^ __rshift<1>(__yp) ^ (__a * (__yp & 1));420 result_type __z = __x_[__i_] ^ (__rshift<__u>(__x_[__i_]) & __d);421 __i_ = __j;422 __z ^= __lshift<__s>(__z) & __b;423 __z ^= __lshift<__t>(__z) & __c;424 return __z ^ __rshift<__l>(__z);425}426 427template <class _UInt,428 size_t _Wp,429 size_t _Np,430 size_t _Mp,431 size_t _Rp,432 _UInt _Ap,433 size_t _Up,434 _UInt _Dp,435 size_t _Sp,436 _UInt _Bp,437 size_t _Tp,438 _UInt _Cp,439 size_t _Lp,440 _UInt _Fp>441_LIBCPP_HIDE_FROM_ABI bool442operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,443 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y) {444 if (__x.__i_ == __y.__i_)445 return std::equal(__x.__x_, __x.__x_ + _Np, __y.__x_);446 if (__x.__i_ == 0 || __y.__i_ == 0) {447 size_t __j = std::min(_Np - __x.__i_, _Np - __y.__i_);448 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j, __y.__x_ + __y.__i_))449 return false;450 if (__x.__i_ == 0)451 return std::equal(__x.__x_ + __j, __x.__x_ + _Np, __y.__x_);452 return std::equal(__x.__x_, __x.__x_ + (_Np - __j), __y.__x_ + __j);453 }454 if (__x.__i_ < __y.__i_) {455 size_t __j = _Np - __y.__i_;456 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j), __y.__x_ + __y.__i_))457 return false;458 if (!std::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Np, __y.__x_))459 return false;460 return std::equal(__x.__x_, __x.__x_ + __x.__i_, __y.__x_ + (_Np - (__x.__i_ + __j)));461 }462 size_t __j = _Np - __x.__i_;463 if (!std::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j), __x.__x_ + __x.__i_))464 return false;465 if (!std::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Np, __x.__x_))466 return false;467 return std::equal(__y.__x_, __y.__x_ + __y.__i_, __x.__x_ + (_Np - (__y.__i_ + __j)));468}469 470template <class _UInt,471 size_t _Wp,472 size_t _Np,473 size_t _Mp,474 size_t _Rp,475 _UInt _Ap,476 size_t _Up,477 _UInt _Dp,478 size_t _Sp,479 _UInt _Bp,480 size_t _Tp,481 _UInt _Cp,482 size_t _Lp,483 _UInt _Fp>484inline _LIBCPP_HIDE_FROM_ABI bool485operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x,486 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __y) {487 return !(__x == __y);488}489 490template <class _CharT,491 class _Traits,492 class _UInt,493 size_t _Wp,494 size_t _Np,495 size_t _Mp,496 size_t _Rp,497 _UInt _Ap,498 size_t _Up,499 _UInt _Dp,500 size_t _Sp,501 _UInt _Bp,502 size_t _Tp,503 _UInt _Cp,504 size_t _Lp,505 _UInt _Fp>506_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&507operator<<(basic_ostream<_CharT, _Traits>& __os,508 const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x) {509 __save_flags<_CharT, _Traits> __lx(__os);510 typedef basic_ostream<_CharT, _Traits> _Ostream;511 __os.flags(_Ostream::dec | _Ostream::left);512 _CharT __sp = __os.widen(' ');513 __os.fill(__sp);514 __os << __x.__x_[__x.__i_];515 for (size_t __j = __x.__i_ + 1; __j < _Np; ++__j)516 __os << __sp << __x.__x_[__j];517 for (size_t __j = 0; __j < __x.__i_; ++__j)518 __os << __sp << __x.__x_[__j];519 return __os;520}521 522template <class _CharT,523 class _Traits,524 class _UInt,525 size_t _Wp,526 size_t _Np,527 size_t _Mp,528 size_t _Rp,529 _UInt _Ap,530 size_t _Up,531 _UInt _Dp,532 size_t _Sp,533 _UInt _Bp,534 size_t _Tp,535 _UInt _Cp,536 size_t _Lp,537 _UInt _Fp>538_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&539operator>>(basic_istream<_CharT, _Traits>& __is,540 mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp, _Bp, _Tp, _Cp, _Lp, _Fp>& __x) {541 __save_flags<_CharT, _Traits> __lx(__is);542 typedef basic_istream<_CharT, _Traits> _Istream;543 __is.flags(_Istream::dec | _Istream::skipws);544 _UInt __t[_Np];545 for (size_t __i = 0; __i < _Np; ++__i)546 __is >> __t[__i];547 if (!__is.fail()) {548 for (size_t __i = 0; __i < _Np; ++__i)549 __x.__x_[__i] = __t[__i];550 __x.__i_ = 0;551 }552 return __is;553}554 555typedef mersenne_twister_engine<556 uint_fast32_t,557 32,558 624,559 397,560 31,561 0x9908b0df,562 11,563 0xffffffff,564 7,565 0x9d2c5680,566 15,567 0xefc60000,568 18,569 1812433253>570 mt19937;571typedef mersenne_twister_engine<572 uint_fast64_t,573 64,574 312,575 156,576 31,577 0xb5026f5aa96619e9ULL,578 29,579 0x5555555555555555ULL,580 17,581 0x71d67fffeda60000ULL,582 37,583 0xfff7eee000000000ULL,584 43,585 6364136223846793005ULL>586 mt19937_64;587 588_LIBCPP_END_NAMESPACE_STD589 590_LIBCPP_POP_MACROS591 592#endif // _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H593