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
27template <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
32struct __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
43template <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>
46struct __lce_ta;
47
48// 64
49
50template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
51struct __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
68template <unsigned long long __a, unsigned long long __m>
69struct __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
85template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
86struct __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
96template <unsigned long long __a, unsigned long long __c>
97struct __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
109template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
110struct __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
130template <unsigned long long _Ap, unsigned long long _Mp>
131struct __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
149template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
150struct __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
163template <unsigned long long _Ap, unsigned long long _Cp>
164struct __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
178template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b>
179struct __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
189template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
190class _LIBCPP_TEMPLATE_VIS linear_congruential_engine;
191
192template <class _CharT, class _Traits,
193          class _Up, _Up _Ap, _Up _Cp, _Up _Np>
194_LIBCPP_INLINE_VISIBILITY
195basic_ostream<_CharT, _Traits>&
196operator<<(basic_ostream<_CharT, _Traits>& __os,
197           const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
198
199template <class _CharT, class _Traits,
200          class _Up, _Up _Ap, _Up _Cp, _Up _Np>
201_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
202operator>>(basic_istream<_CharT, _Traits>& __is,
203           linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
204
205template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
206class _LIBCPP_TEMPLATE_VIS linear_congruential_engine
207{
208public:
209    // types
210    typedef _UIntType result_type;
211
212private:
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");
220public:
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
284private:
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
316template <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
320template <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
324template <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
328template <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
332template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
333template<class _Sseq>
334void
335linear_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
345template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
346template<class _Sseq>
347void
348linear_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
359template <class _CharT, class _Traits,
360          class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
361inline _LIBCPP_INLINE_VISIBILITY
362basic_ostream<_CharT, _Traits>&
363operator<<(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
373template <class _CharT, class _Traits,
374          class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
375_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
376operator>>(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
389typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
390                                                                   minstd_rand0;
391typedef 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