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, 30 unsigned long long __c, 31 unsigned long long __m, 32 unsigned long long _Mp, 33 bool _MightOverflow = (__a != 0 && __m != 0 && __m - 1 > (_Mp - __c) / __a), 34 bool _OverflowOK = ((__m | (__m - 1)) > __m), // m = 2^n 35 bool _SchrageOK = (__a != 0 && __m != 0 && __m % __a <= __m / __a)> // r <= q 36 struct __lce_alg_picker { 37 static_assert(__a != 0 || __m != 0 || !_MightOverflow || _OverflowOK || _SchrageOK, 38 "The current values of a, c, and m cannot generate a number " 39 "within bounds of linear_congruential_engine."); 40 41 static _LIBCPP_CONSTEXPR const bool __use_schrage = _MightOverflow && !_OverflowOK && _SchrageOK; 42 }; 43 44 template <unsigned long long __a, 45 unsigned long long __c, 46 unsigned long long __m, 47 unsigned long long _Mp, 48 bool _UseSchrage = __lce_alg_picker<__a, __c, __m, _Mp>::__use_schrage> 49 struct __lce_ta; 50 51 // 64 52 53 template <unsigned long long __a, unsigned long long __c, unsigned long long __m> 54 struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true> { 55 typedef unsigned long long result_type; 56 _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { 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 typedef unsigned long long result_type; 71 _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { 72 // Schrage's algorithm 73 const result_type __q = __m / __a; 74 const result_type __r = __m % __a; 75 const result_type __t0 = __a * (__x % __q); 76 const result_type __t1 = __r * (__x / __q); 77 __x = __t0 + (__t0 < __t1) * __m - __t1; 78 return __x; 79 } 80 }; 81 82 template <unsigned long long __a, unsigned long long __c, unsigned long long __m> 83 struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), false> { 84 typedef unsigned long long result_type; 85 _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return (__a * __x + __c) % __m; } 86 }; 87 88 template <unsigned long long __a, unsigned long long __c> 89 struct __lce_ta<__a, __c, 0, (unsigned long long)(~0), false> { 90 typedef unsigned long long result_type; 91 _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return __a * __x + __c; } 92 }; 93 94 // 32 95 96 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> 97 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), true> { 98 typedef unsigned result_type; 99 _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { 100 const result_type __a = static_cast<result_type>(_Ap); 101 const result_type __c = static_cast<result_type>(_Cp); 102 const result_type __m = static_cast<result_type>(_Mp); 103 // Schrage's algorithm 104 const result_type __q = __m / __a; 105 const result_type __r = __m % __a; 106 const result_type __t0 = __a * (__x % __q); 107 const result_type __t1 = __r * (__x / __q); 108 __x = __t0 + (__t0 < __t1) * __m - __t1; 109 __x += __c - (__x >= __m - __c) * __m; 110 return __x; 111 } 112 }; 113 114 template <unsigned long long _Ap, unsigned long long _Mp> 115 struct __lce_ta<_Ap, 0, _Mp, unsigned(~0), true> { 116 typedef unsigned result_type; 117 _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { 118 const result_type __a = static_cast<result_type>(_Ap); 119 const result_type __m = static_cast<result_type>(_Mp); 120 // Schrage's algorithm 121 const result_type __q = __m / __a; 122 const result_type __r = __m % __a; 123 const result_type __t0 = __a * (__x % __q); 124 const result_type __t1 = __r * (__x / __q); 125 __x = __t0 + (__t0 < __t1) * __m - __t1; 126 return __x; 127 } 128 }; 129 130 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> 131 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), false> { 132 typedef unsigned result_type; 133 _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { 134 const result_type __a = static_cast<result_type>(_Ap); 135 const result_type __c = static_cast<result_type>(_Cp); 136 const result_type __m = static_cast<result_type>(_Mp); 137 return (__a * __x + __c) % __m; 138 } 139 }; 140 141 template <unsigned long long _Ap, unsigned long long _Cp> 142 struct __lce_ta<_Ap, _Cp, 0, unsigned(~0), false> { 143 typedef unsigned result_type; 144 _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { 145 const result_type __a = static_cast<result_type>(_Ap); 146 const result_type __c = static_cast<result_type>(_Cp); 147 return __a * __x + __c; 148 } 149 }; 150 151 // 16 152 153 template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b> 154 struct __lce_ta<__a, __c, __m, (unsigned short)(~0), __b> { 155 typedef unsigned short result_type; 156 _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { 157 return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(~0)>::next(__x)); 158 } 159 }; 160 161 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 162 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine; 163 164 template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> 165 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& 166 operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&); 167 168 template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> 169 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& 170 operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x); 171 172 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 173 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine { 174 public: 175 // types 176 typedef _UIntType result_type; 177 178 private: 179 result_type __x_; 180 181 static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(~0); 182 183 static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters"); 184 static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters"); 185 static_assert(is_unsigned<_UIntType>::value, "_UIntType must be unsigned type"); 186 187 public: 188 static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u : 0u; 189 static _LIBCPP_CONSTEXPR const result_type _Max = __m - _UIntType(1u); 190 static_assert(_Min < _Max, "linear_congruential_engine invalid parameters"); 191 192 // engine characteristics 193 static _LIBCPP_CONSTEXPR const result_type multiplier = __a; 194 static _LIBCPP_CONSTEXPR const result_type increment = __c; 195 static _LIBCPP_CONSTEXPR const result_type modulus = __m; 196 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type min() { return _Min; } 197 _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type max() { return _Max; } 198 static _LIBCPP_CONSTEXPR const result_type default_seed = 1u; 199 200 // constructors and seeding functions 201 #ifndef _LIBCPP_CXX03_LANG 202 _LIBCPP_HIDE_FROM_ABI linear_congruential_engine() : linear_congruential_engine(default_seed) {} 203 _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s) { seed(__s); } 204 #else 205 _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s = default_seed) { seed(__s); } 206 #endif 207 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0> 208 _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(_Sseq& __q) { 209 seed(__q); 210 } 211 _LIBCPP_HIDE_FROM_ABI void seed(result_type __s = default_seed) { 212 seed(integral_constant<bool, __m == 0>(), integral_constant<bool, __c == 0>(), __s); 213 } 214 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0> 215 _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) { 216 __seed( 217 __q, 218 integral_constant<unsigned, 219 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1) / 32 : (__m > 0x100000000ull))>()); 220 } 221 222 // generating functions 223 _LIBCPP_HIDE_FROM_ABI result_type operator()() { 224 return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_)); 225 } 226 _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) { 227 for (; __z; --__z) 228 operator()(); 229 } 230 231 friend _LIBCPP_HIDE_FROM_ABI bool 232 operator==(const linear_congruential_engine& __x, const linear_congruential_engine& __y) { 233 return __x.__x_ == __y.__x_; 234 } 235 friend _LIBCPP_HIDE_FROM_ABI bool 236 operator!=(const linear_congruential_engine& __x, const linear_congruential_engine& __y) { 237 return !(__x == __y); 238 } 239 240 private: 241 _LIBCPP_HIDE_FROM_ABI void seed(true_type, true_type, result_type __s) { __x_ = __s == 0 ? 1 : __s; } 242 _LIBCPP_HIDE_FROM_ABI void seed(true_type, false_type, result_type __s) { __x_ = __s; } 243 _LIBCPP_HIDE_FROM_ABI void seed(false_type, true_type, result_type __s) { __x_ = __s % __m == 0 ? 1 : __s % __m; } 244 _LIBCPP_HIDE_FROM_ABI void seed(false_type, false_type, result_type __s) { __x_ = __s % __m; } 245 246 template <class _Sseq> 247 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>); 248 template <class _Sseq> 249 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>); 250 251 template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> 252 friend basic_ostream<_CharT, _Traits>& 253 operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&); 254 255 template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> 256 friend basic_istream<_CharT, _Traits>& 257 operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x); 258 }; 259 260 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 261 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 262 linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier; 263 264 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 265 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 266 linear_congruential_engine<_UIntType, __a, __c, __m>::increment; 267 268 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 269 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 270 linear_congruential_engine<_UIntType, __a, __c, __m>::modulus; 271 272 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 273 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type 274 linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed; 275 276 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 277 template <class _Sseq> 278 void linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, integral_constant<unsigned, 1>) { 279 const unsigned __k = 1; 280 uint32_t __ar[__k + 3]; 281 __q.generate(__ar, __ar + __k + 3); 282 result_type __s = static_cast<result_type>(__ar[3] % __m); 283 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; 284 } 285 286 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 287 template <class _Sseq> 288 void linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, integral_constant<unsigned, 2>) { 289 const unsigned __k = 2; 290 uint32_t __ar[__k + 3]; 291 __q.generate(__ar, __ar + __k + 3); 292 result_type __s = static_cast<result_type>((__ar[3] + ((uint64_t)__ar[4] << 32)) % __m); 293 __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; 294 } 295 296 template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 297 inline _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& 298 operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_UIntType, __a, __c, __m>& __x) { 299 __save_flags<_CharT, _Traits> __lx(__os); 300 typedef basic_ostream<_CharT, _Traits> _Ostream; 301 __os.flags(_Ostream::dec | _Ostream::left); 302 __os.fill(__os.widen(' ')); 303 return __os << __x.__x_; 304 } 305 306 template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> 307 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& 308 operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_UIntType, __a, __c, __m>& __x) { 309 __save_flags<_CharT, _Traits> __lx(__is); 310 typedef basic_istream<_CharT, _Traits> _Istream; 311 __is.flags(_Istream::dec | _Istream::skipws); 312 _UIntType __t; 313 __is >> __t; 314 if (!__is.fail()) 315 __x.__x_ = __t; 316 return __is; 317 } 318 319 typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> minstd_rand0; 320 typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> minstd_rand; 321 322 _LIBCPP_END_NAMESPACE_STD 323 324 _LIBCPP_POP_MACROS 325 326 #endif // _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H 327