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, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0> 250 _LIBCPP_INLINE_VISIBILITY 251 explicit linear_congruential_engine(_Sseq& __q) 252 {seed(__q);} 253 _LIBCPP_INLINE_VISIBILITY 254 void seed(result_type __s = default_seed) 255 {seed(integral_constant<bool, __m == 0>(), 256 integral_constant<bool, __c == 0>(), __s);} 257 template<class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0> 258 _LIBCPP_INLINE_VISIBILITY 259 void 260 seed(_Sseq& __q) 261 {__seed(__q, integral_constant<unsigned, 262 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32 263 : (__m > 0x100000000ull))>());} 264 265 // generating functions 266 _LIBCPP_INLINE_VISIBILITY 267 result_type operator()() 268 {return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_));} 269 _LIBCPP_INLINE_VISIBILITY 270 void discard(unsigned long long __z) {for (; __z; --__z) operator()();} 271 272 friend _LIBCPP_INLINE_VISIBILITY 273 bool operator==(const linear_congruential_engine& __x, 274 const linear_congruential_engine& __y) 275 {return __x.__x_ == __y.__x_;} 276 friend _LIBCPP_INLINE_VISIBILITY 277 bool operator!=(const linear_congruential_engine& __x, 278 const linear_congruential_engine& __y) 279 {return !(__x == __y);} 280 281 private: 282 283 _LIBCPP_INLINE_VISIBILITY 284 void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;} 285 _LIBCPP_INLINE_VISIBILITY 286 void seed(true_type, false_type, result_type __s) {__x_ = __s;} 287 _LIBCPP_INLINE_VISIBILITY 288 void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ? 289 1 : __s % __m;} 290 _LIBCPP_INLINE_VISIBILITY 291 void seed(false_type, false_type, result_type __s) {__x_ = __s % __m;} 292 293 template<class _Sseq> 294 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>); 295 template<class _Sseq> 296 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>); 297 298 template <class _CharT, class _Traits, 299 class _Up, _Up _Ap, _Up _Cp, _Up _Np> 300 friend 301 basic_ostream<_CharT, _Traits>& 302 operator<<(basic_ostream<_CharT, _Traits>& __os, 303 const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&); 304 305 template <class _CharT, class _Traits, 306 class _Up, _Up _Ap, _Up _Cp, _Up _Np> 307 friend 308 basic_istream<_CharT, _Traits>& 309 operator>>(basic_istream<_CharT, _Traits>& __is, 310 linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x); 311 }; 312 313 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 314 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 315 linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier; 316 317 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 318 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 319 linear_congruential_engine<_UIntType, __a, __c, __m>::increment; 320 321 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 322 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 323 linear_congruential_engine<_UIntType, __a, __c, __m>::modulus; 324 325 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 326 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 327 linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed; 328 329 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 330 template<class _Sseq> 331 void 332 linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, 333 integral_constant<unsigned, 1>) 334 { 335 const unsigned __k = 1; 336 uint32_t __ar[__k+3]; 337 __q.generate(__ar, __ar + __k + 3); 338 result_type __s = static_cast<result_type>(__ar[3] % __m); 339 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; 340 } 341 342 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 343 template<class _Sseq> 344 void 345 linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, 346 integral_constant<unsigned, 2>) 347 { 348 const unsigned __k = 2; 349 uint32_t __ar[__k+3]; 350 __q.generate(__ar, __ar + __k + 3); 351 result_type __s = static_cast<result_type>((__ar[3] + 352 ((uint64_t)__ar[4] << 32)) % __m); 353 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; 354 } 355 356 template <class _CharT, class _Traits, 357 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 358 inline _LIBCPP_INLINE_VISIBILITY 359 basic_ostream<_CharT, _Traits>& 360 operator<<(basic_ostream<_CharT, _Traits>& __os, 361 const linear_congruential_engine<_UIntType, __a, __c, __m>& __x) 362 { 363 __save_flags<_CharT, _Traits> __lx(__os); 364 typedef basic_ostream<_CharT, _Traits> _Ostream; 365 __os.flags(_Ostream::dec | _Ostream::left); 366 __os.fill(__os.widen(' ')); 367 return __os << __x.__x_; 368 } 369 370 template <class _CharT, class _Traits, 371 class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 372 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& 373 operator>>(basic_istream<_CharT, _Traits>& __is, 374 linear_congruential_engine<_UIntType, __a, __c, __m>& __x) 375 { 376 __save_flags<_CharT, _Traits> __lx(__is); 377 typedef basic_istream<_CharT, _Traits> _Istream; 378 __is.flags(_Istream::dec | _Istream::skipws); 379 _UIntType __t; 380 __is >> __t; 381 if (!__is.fail()) 382 __x.__x_ = __t; 383 return __is; 384 } 385 386 typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> 387 minstd_rand0; 388 typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> 389 minstd_rand; 390 391 _LIBCPP_END_NAMESPACE_STD 392 393 _LIBCPP_POP_MACROS 394 395 #endif // _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H 396