379 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___CXX03___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H10#define _LIBCPP___CXX03___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H11 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_header22#endif23 24_LIBCPP_PUSH_MACROS25#include <__cxx03/__undef_macros>26 27_LIBCPP_BEGIN_NAMESPACE_STD28 29enum __lce_alg_type {30 _LCE_Full,31 _LCE_Part,32 _LCE_Schrage,33 _LCE_Promote,34};35 36template <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^n41 bool _Full = (!_HasOverflow || __m - 1ull <= (_Mp - __c) / __a), // (a * x + c) % m works42 bool _Part = (!_HasOverflow || __m - 1ull <= _Mp / __a), // (a * x) % m works43 bool _Schrage = (_HasOverflow && __m % __a <= __m / __a)> // r <= q44struct __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_INT12848 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#endif51};52 53template <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>58struct __lce_ta;59 60// 6461 62#ifndef _LIBCPP_HAS_NO_INT12863template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>64struct __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#endif76 77template <unsigned long long __a, unsigned long long __c, unsigned long long __m>78struct __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 algorithm82 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 92template <unsigned long long __a, unsigned long long __m>93struct __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 algorithm97 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 106template <unsigned long long __a, unsigned long long __c, unsigned long long __m>107struct __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) % m111 __x = (__a * __x) % __m;112 __x += __c - (__x >= __m - __c) * __m;113 return __x;114 }115};116 117template <unsigned long long __a, unsigned long long __c, unsigned long long __m>118struct __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 123template <unsigned long long __a, unsigned long long __c>124struct __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// 32130 131template <unsigned long long __a, unsigned long long __c, unsigned long long __m>132struct __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 139template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>140struct __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 algorithm147 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 157template <unsigned long long _Ap, unsigned long long _Mp>158struct __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 algorithm164 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 173template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>174struct __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) % m181 __x = (__a * __x) % __m;182 __x += __c - (__x >= __m - __c) * __m;183 return __x;184 }185};186 187template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>188struct __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 198template <unsigned long long _Ap, unsigned long long _Cp>199struct __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// 16209 210template <unsigned long long __a, unsigned long long __c, unsigned long long __m, __lce_alg_type __mode>211struct __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 218template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>219class _LIBCPP_TEMPLATE_VIS linear_congruential_engine;220 221template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>222_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&223operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);224 225template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>226_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&227operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);228 229template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>230class _LIBCPP_TEMPLATE_VIS linear_congruential_engine {231public:232 // types233 typedef _UIntType result_type;234 235private: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 244public: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 characteristics250 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 functions258 _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 functions275 _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 bool284 operator==(const linear_congruential_engine& __x, const linear_congruential_engine& __y) {285 return __x.__x_ == __y.__x_;286 }287 friend _LIBCPP_HIDE_FROM_ABI bool288 operator!=(const linear_congruential_engine& __x, const linear_congruential_engine& __y) {289 return !(__x == __y);290 }291 292private: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 312template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>313const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type314 linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier;315 316template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>317const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type318 linear_congruential_engine<_UIntType, __a, __c, __m>::increment;319 320template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>321const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type322 linear_congruential_engine<_UIntType, __a, __c, __m>::modulus;323 324template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>325const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type326 linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed;327 328template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>329template <class _Sseq>330void 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 338template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>339template <class _Sseq>340void 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 348template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>349inline _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&350operator<<(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 358template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>359_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&360operator>>(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 371typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> minstd_rand0;372typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> minstd_rand;373 374_LIBCPP_END_NAMESPACE_STD375 376_LIBCPP_POP_MACROS377 378#endif // _LIBCPP___CXX03___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H379