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