?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[rtsan] Remove mkfifoat interceptor (#116997)
[llvm-project.git] / libcxx / include / __cxx03 / __random / linear_congruential_engine.h
blob94d140ae1a2d0fd6b1b424a663d8f4287ecef320
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 <__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 _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
LLVM monorepo