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