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