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_LINEAR_CONGRUENTIAL_ENGINE_H 10 #define _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H 11 12 #include <__config> 13 #include <__random/is_seed_sequence.h> 14 #include <cstdint> 15 #include <iosfwd> 16 #include <type_traits> 17 18 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 19 #pragma GCC system_header 20 #endif 21 22 _LIBCPP_PUSH_MACROS 23 #include <__undef_macros> 24 25 _LIBCPP_BEGIN_NAMESPACE_STD 26 27 template <unsigned long long __a, unsigned long long __c, 28 unsigned long long __m, unsigned long long _Mp, 29 bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_Mp-__c)/__a), 30 bool _OverflowOK = ((__m | (__m-1)) > __m), // m = 2^n 31 bool _SchrageOK = (__a != 0 && __m != 0 && __m % __a <= __m / __a)> // r <= q 32 struct __lce_alg_picker 33 { 34 static_assert(__a != 0 || __m != 0 || !_MightOverflow || _OverflowOK || _SchrageOK, 35 "The current values of a, c, and m cannot generate a number " 36 "within bounds of linear_congruential_engine."); 37 38 static _LIBCPP_CONSTEXPR const bool __use_schrage = _MightOverflow && 39 !_OverflowOK && 40 _SchrageOK; 41 }; 42 43 template <unsigned long long __a, unsigned long long __c, 44 unsigned long long __m, unsigned long long _Mp, 45 bool _UseSchrage = __lce_alg_picker<__a, __c, __m, _Mp>::__use_schrage> 46 struct __lce_ta; 47 48 // 64 49 50 template <unsigned long long __a, unsigned long long __c, unsigned long long __m> 51 struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true> 52 { 53 typedef unsigned long long result_type; 54 _LIBCPP_INLINE_VISIBILITY 55 static result_type next(result_type __x) 56 { 57 // Schrage's algorithm 58 const result_type __q = __m / __a; 59 const result_type __r = __m % __a; 60 const result_type __t0 = __a * (__x % __q); 61 const result_type __t1 = __r * (__x / __q); 62 __x = __t0 + (__t0 < __t1) * __m - __t1; 63 __x += __c - (__x >= __m - __c) * __m; 64 return __x; 65 } 66 }; 67 68 template <unsigned long long __a, unsigned long long __m> 69 struct __lce_ta<__a, 0, __m, (unsigned long long)(~0), true> 70 { 71 typedef unsigned long long result_type; 72 _LIBCPP_INLINE_VISIBILITY 73 static result_type next(result_type __x) 74 { 75 // Schrage's algorithm 76 const result_type __q = __m / __a; 77 const result_type __r = __m % __a; 78 const result_type __t0 = __a * (__x % __q); 79 const result_type __t1 = __r * (__x / __q); 80 __x = __t0 + (__t0 < __t1) * __m - __t1; 81 return __x; 82 } 83 }; 84 85 template <unsigned long long __a, unsigned long long __c, unsigned long long __m> 86 struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), false> 87 { 88 typedef unsigned long long result_type; 89 _LIBCPP_INLINE_VISIBILITY 90 static result_type next(result_type __x) 91 { 92 return (__a * __x + __c) % __m; 93 } 94 }; 95 96 template <unsigned long long __a, unsigned long long __c> 97 struct __lce_ta<__a, __c, 0, (unsigned long long)(~0), false> 98 { 99 typedef unsigned long long result_type; 100 _LIBCPP_INLINE_VISIBILITY 101 static result_type next(result_type __x) 102 { 103 return __a * __x + __c; 104 } 105 }; 106 107 // 32 108 109 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> 110 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), true> 111 { 112 typedef unsigned result_type; 113 _LIBCPP_INLINE_VISIBILITY 114 static result_type next(result_type __x) 115 { 116 const result_type __a = static_cast<result_type>(_Ap); 117 const result_type __c = static_cast<result_type>(_Cp); 118 const result_type __m = static_cast<result_type>(_Mp); 119 // Schrage's algorithm 120 const result_type __q = __m / __a; 121 const result_type __r = __m % __a; 122 const result_type __t0 = __a * (__x % __q); 123 const result_type __t1 = __r * (__x / __q); 124 __x = __t0 + (__t0 < __t1) * __m - __t1; 125 __x += __c - (__x >= __m - __c) * __m; 126 return __x; 127 } 128 }; 129 130 template <unsigned long long _Ap, unsigned long long _Mp> 131 struct __lce_ta<_Ap, 0, _Mp, unsigned(~0), true> 132 { 133 typedef unsigned result_type; 134 _LIBCPP_INLINE_VISIBILITY 135 static result_type next(result_type __x) 136 { 137 const result_type __a = static_cast<result_type>(_Ap); 138 const result_type __m = static_cast<result_type>(_Mp); 139 // Schrage's algorithm 140 const result_type __q = __m / __a; 141 const result_type __r = __m % __a; 142 const result_type __t0 = __a * (__x % __q); 143 const result_type __t1 = __r * (__x / __q); 144 __x = __t0 + (__t0 < __t1) * __m - __t1; 145 return __x; 146 } 147 }; 148 149 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> 150 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), false> 151 { 152 typedef unsigned result_type; 153 _LIBCPP_INLINE_VISIBILITY 154 static result_type next(result_type __x) 155 { 156 const result_type __a = static_cast<result_type>(_Ap); 157 const result_type __c = static_cast<result_type>(_Cp); 158 const result_type __m = static_cast<result_type>(_Mp); 159 return (__a * __x + __c) % __m; 160 } 161 }; 162 163 template <unsigned long long _Ap, unsigned long long _Cp> 164 struct __lce_ta<_Ap, _Cp, 0, unsigned(~0), false> 165 { 166 typedef unsigned result_type; 167 _LIBCPP_INLINE_VISIBILITY 168 static result_type next(result_type __x) 169 { 170 const result_type __a = static_cast<result_type>(_Ap); 171 const result_type __c = static_cast<result_type>(_Cp); 172 return __a * __x + __c; 173 } 174 }; 175 176 // 16 177 178 template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b> 179 struct __lce_ta<__a, __c, __m, (unsigned short)(~0), __b> 180 { 181 typedef unsigned short result_type; 182 _LIBCPP_INLINE_VISIBILITY 183 static result_type next(result_type __x) 184 { 185 return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(~0)>::next(__x)); 186 } 187 }; 188 189 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 190 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine; 191 192 template <class _CharT, class _Traits, 193 class _Up, _Up _Ap, _Up _Cp, _Up _Np> 194 _LIBCPP_INLINE_VISIBILITY 195 basic_ostream<_CharT, _Traits>& 196 operator<<(basic_ostream<_CharT, _Traits>& __os, 197 const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&); 198 199 template <class _CharT, class _Traits, 200 class _Up, _Up _Ap, _Up _Cp, _Up _Np> 201 basic_istream<_CharT, _Traits>& 202 operator>>(basic_istream<_CharT, _Traits>& __is, 203 linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x); 204 205 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 206 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine 207 { 208 public: 209 // types 210 typedef _UIntType result_type; 211 212 private: 213 result_type __x_; 214 215 static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(~0); 216 217 static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters"); 218 static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters"); 219 static_assert(is_unsigned<_UIntType>::value, "_UIntType must be unsigned type"); 220 public: 221 static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u: 0u; 222 static _LIBCPP_CONSTEXPR const result_type _Max = __m - 1u; 223 static_assert(_Min < _Max, "linear_congruential_engine invalid parameters"); 224 225 // engine characteristics 226 static _LIBCPP_CONSTEXPR const result_type multiplier = __a; 227 static _LIBCPP_CONSTEXPR const result_type increment = __c; 228 static _LIBCPP_CONSTEXPR const result_type modulus = __m; 229 _LIBCPP_INLINE_VISIBILITY 230 static _LIBCPP_CONSTEXPR result_type min() {return _Min;} 231 _LIBCPP_INLINE_VISIBILITY 232 static _LIBCPP_CONSTEXPR result_type max() {return _Max;} 233 static _LIBCPP_CONSTEXPR const result_type default_seed = 1u; 234 235 // constructors and seeding functions 236 #ifndef _LIBCPP_CXX03_LANG 237 _LIBCPP_INLINE_VISIBILITY 238 linear_congruential_engine() : linear_congruential_engine(default_seed) {} 239 _LIBCPP_INLINE_VISIBILITY 240 explicit linear_congruential_engine(result_type __s) { seed(__s); } 241 #else 242 _LIBCPP_INLINE_VISIBILITY 243 explicit linear_congruential_engine(result_type __s = default_seed) { 244 seed(__s); 245 } 246 #endif 247 template<class _Sseq> 248 _LIBCPP_INLINE_VISIBILITY 249 explicit linear_congruential_engine(_Sseq& __q, 250 typename enable_if<__is_seed_sequence<_Sseq, linear_congruential_engine>::value>::type* = 0) 251 {seed(__q);} 252 _LIBCPP_INLINE_VISIBILITY 253 void seed(result_type __s = default_seed) 254 {seed(integral_constant<bool, __m == 0>(), 255 integral_constant<bool, __c == 0>(), __s);} 256 template<class _Sseq> 257 _LIBCPP_INLINE_VISIBILITY 258 typename enable_if 259 < 260 __is_seed_sequence<_Sseq, linear_congruential_engine>::value, 261 void 262 >::type 263 seed(_Sseq& __q) 264 {__seed(__q, integral_constant<unsigned, 265 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32 266 : (__m > 0x100000000ull))>());} 267 268 // generating functions 269 _LIBCPP_INLINE_VISIBILITY 270 result_type operator()() 271 {return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_));} 272 _LIBCPP_INLINE_VISIBILITY 273 void discard(unsigned long long __z) {for (; __z; --__z) operator()();} 274 275 friend _LIBCPP_INLINE_VISIBILITY 276 bool operator==(const linear_congruential_engine& __x, 277 const linear_congruential_engine& __y) 278 {return __x.__x_ == __y.__x_;} 279 friend _LIBCPP_INLINE_VISIBILITY 280 bool operator!=(const linear_congruential_engine& __x, 281 const linear_congruential_engine& __y) 282 {return !(__x == __y);} 283 284 private: 285 286 _LIBCPP_INLINE_VISIBILITY 287 void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;} 288 _LIBCPP_INLINE_VISIBILITY 289 void seed(true_type, false_type, result_type __s) {__x_ = __s;} 290 _LIBCPP_INLINE_VISIBILITY 291 void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ? 292 1 : __s % __m;} 293 _LIBCPP_INLINE_VISIBILITY 294 void seed(false_type, false_type, result_type __s) {__x_ = __s % __m;} 295 296 template<class _Sseq> 297 void __seed(_Sseq& __q, integral_constant<unsigned, 1>); 298 template<class _Sseq> 299 void __seed(_Sseq& __q, integral_constant<unsigned, 2>); 300 301 template <class _CharT, class _Traits, 302 class _Up, _Up _Ap, _Up _Cp, _Up _Np> 303 friend 304 basic_ostream<_CharT, _Traits>& 305 operator<<(basic_ostream<_CharT, _Traits>& __os, 306 const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&); 307 308 template <class _CharT, class _Traits, 309 class _Up, _Up _Ap, _Up _Cp, _Up _Np> 310 friend 311 basic_istream<_CharT, _Traits>& 312 operator>>(basic_istream<_CharT, _Traits>& __is, 313 linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x); 314 }; 315 316 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 317 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 318 linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier; 319 320 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 321 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 322 linear_congruential_engine<_UIntType, __a, __c, __m>::increment; 323 324 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 325 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 326 linear_congruential_engine<_UIntType, __a, __c, __m>::modulus; 327 328 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 329 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 330 linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed; 331 332 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 333 template<class _Sseq> 334 void 335 linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, 336 integral_constant<unsigned, 1>) 337 { 338 const unsigned __k = 1; 339 uint32_t __ar[__k+3]; 340 __q.generate(__ar, __ar + __k + 3); 341 result_type __s = static_cast<result_type>(__ar[3] % __m); 342 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; 343 } 344 345 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 346 template<class _Sseq> 347 void 348 linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, 349 integral_constant<unsigned, 2>) 350 { 351 const unsigned __k = 2; 352 uint32_t __ar[__k+3]; 353 __q.generate(__ar, __ar + __k + 3); 354 result_type __s = static_cast<result_type>((__ar[3] + 355 ((uint64_t)__ar[4] << 32)) % __m); 356 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; 357 } 358 359 template <class _CharT, class _Traits, 360 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 361 inline _LIBCPP_INLINE_VISIBILITY 362 basic_ostream<_CharT, _Traits>& 363 operator<<(basic_ostream<_CharT, _Traits>& __os, 364 const linear_congruential_engine<_UIntType, __a, __c, __m>& __x) 365 { 366 __save_flags<_CharT, _Traits> __lx(__os); 367 typedef basic_ostream<_CharT, _Traits> _Ostream; 368 __os.flags(_Ostream::dec | _Ostream::left); 369 __os.fill(__os.widen(' ')); 370 return __os << __x.__x_; 371 } 372 373 template <class _CharT, class _Traits, 374 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 375 basic_istream<_CharT, _Traits>& 376 operator>>(basic_istream<_CharT, _Traits>& __is, 377 linear_congruential_engine<_UIntType, __a, __c, __m>& __x) 378 { 379 __save_flags<_CharT, _Traits> __lx(__is); 380 typedef basic_istream<_CharT, _Traits> _Istream; 381 __is.flags(_Istream::dec | _Istream::skipws); 382 _UIntType __t; 383 __is >> __t; 384 if (!__is.fail()) 385 __x.__x_ = __t; 386 return __is; 387 } 388 389 typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> 390 minstd_rand0; 391 typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> 392 minstd_rand; 393 394 _LIBCPP_END_NAMESPACE_STD 395 396 _LIBCPP_POP_MACROS 397 398 #endif // _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H 399