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