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