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