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_SUBTRACT_WITH_CARRY_ENGINE_H
10 #define _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H
11 
12 #include <__algorithm/equal.h>
13 #include <__algorithm/min.h>
14 #include <__config>
15 #include <__random/is_seed_sequence.h>
16 #include <__random/linear_congruential_engine.h>
17 #include <cstddef>
18 #include <cstdint>
19 #include <iosfwd>
20 #include <limits>
21 
22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
23 #  pragma GCC system_header
24 #endif
25 
26 _LIBCPP_PUSH_MACROS
27 #include <__undef_macros>
28 
29 _LIBCPP_BEGIN_NAMESPACE_STD
30 
31 template<class _UIntType, size_t __w, size_t __s, size_t __r>
32 class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine;
33 
34 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
35 _LIBCPP_HIDE_FROM_ABI bool
36 operator==(
37     const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
38     const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
39 
40 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
41 _LIBCPP_INLINE_VISIBILITY
42 bool
43 operator!=(
44     const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
45     const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
46 
47 template <class _CharT, class _Traits,
48           class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
49 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
50 operator<<(basic_ostream<_CharT, _Traits>& __os,
51            const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
52 
53 template <class _CharT, class _Traits,
54           class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
55 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
56 operator>>(basic_istream<_CharT, _Traits>& __is,
57            subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
58 
59 template<class _UIntType, size_t __w, size_t __s, size_t __r>
60 class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine
61 {
62 public:
63     // types
64     typedef _UIntType result_type;
65 
66 private:
67     result_type __x_[__r];
68     result_type  __c_;
69     size_t      __i_;
70 
71     static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
72     static_assert(  0 <  __w, "subtract_with_carry_engine invalid parameters");
73     static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters");
74     static_assert(  0 <  __s, "subtract_with_carry_engine invalid parameters");
75     static_assert(__s <  __r, "subtract_with_carry_engine invalid parameters");
76 public:
77     static _LIBCPP_CONSTEXPR const result_type _Min = 0;
78     static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
79                                                       (result_type(1) << __w) - result_type(1);
80     static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");
81 
82     // engine characteristics
83     static _LIBCPP_CONSTEXPR const size_t word_size = __w;
84     static _LIBCPP_CONSTEXPR const size_t short_lag = __s;
85     static _LIBCPP_CONSTEXPR const size_t long_lag = __r;
86     _LIBCPP_INLINE_VISIBILITY
87     static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
88     _LIBCPP_INLINE_VISIBILITY
89     static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
90     static _LIBCPP_CONSTEXPR const result_type default_seed = 19780503u;
91 
92     // constructors and seeding functions
93 #ifndef _LIBCPP_CXX03_LANG
94     _LIBCPP_INLINE_VISIBILITY
95     subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {}
96     _LIBCPP_INLINE_VISIBILITY
97     explicit subtract_with_carry_engine(result_type __sd) { seed(__sd); }
98 #else
99     _LIBCPP_INLINE_VISIBILITY
100     explicit subtract_with_carry_engine(result_type __sd = default_seed) {
101       seed(__sd);
102     }
103 #endif
104     template<class _Sseq>
105         _LIBCPP_INLINE_VISIBILITY
106         explicit subtract_with_carry_engine(_Sseq& __q,
107         typename enable_if<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value>::type* = 0)
108         {seed(__q);}
109     _LIBCPP_INLINE_VISIBILITY
110     void seed(result_type __sd = default_seed)
111         {seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
112     template<class _Sseq>
113         _LIBCPP_INLINE_VISIBILITY
114         typename enable_if
115         <
116             __is_seed_sequence<_Sseq, subtract_with_carry_engine>::value,
117             void
118         >::type
119         seed(_Sseq& __q)
120             {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
121 
122     // generating functions
123     _LIBCPP_HIDE_FROM_ABI result_type operator()();
124     _LIBCPP_INLINE_VISIBILITY
125     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
126 
127     template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
128     friend
129     bool
130     operator==(
131         const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
132         const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
133 
134     template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
135     friend
136     bool
137     operator!=(
138         const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
139         const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
140 
141     template <class _CharT, class _Traits,
142               class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
143     friend
144     basic_ostream<_CharT, _Traits>&
145     operator<<(basic_ostream<_CharT, _Traits>& __os,
146                const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
147 
148     template <class _CharT, class _Traits,
149               class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
150     friend
151     basic_istream<_CharT, _Traits>&
152     operator>>(basic_istream<_CharT, _Traits>& __is,
153                subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
154 
155 private:
156 
157     _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 1>);
158     _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 2>);
159     template<class _Sseq>
160     _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
161     template<class _Sseq>
162     _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
163 };
164 
165 template<class _UIntType, size_t __w, size_t __s, size_t __r>
166     _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size;
167 
168 template<class _UIntType, size_t __w, size_t __s, size_t __r>
169     _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag;
170 
171 template<class _UIntType, size_t __w, size_t __s, size_t __r>
172     _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::long_lag;
173 
174 template<class _UIntType, size_t __w, size_t __s, size_t __r>
175     _LIBCPP_CONSTEXPR const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type
176     subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed;
177 
178 template<class _UIntType, size_t __w, size_t __s, size_t __r>
179 void
180 subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
181         integral_constant<unsigned, 1>)
182 {
183     linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
184         __e(__sd == 0u ? default_seed : __sd);
185     for (size_t __i = 0; __i < __r; ++__i)
186         __x_[__i] = static_cast<result_type>(__e() & _Max);
187     __c_ = __x_[__r-1] == 0;
188     __i_ = 0;
189 }
190 
191 template<class _UIntType, size_t __w, size_t __s, size_t __r>
192 void
193 subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
194         integral_constant<unsigned, 2>)
195 {
196     linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
197         __e(__sd == 0u ? default_seed : __sd);
198     for (size_t __i = 0; __i < __r; ++__i)
199     {
200         result_type __e0 = __e();
201         __x_[__i] = static_cast<result_type>(
202                                     (__e0 + ((uint64_t)__e() << 32)) & _Max);
203     }
204     __c_ = __x_[__r-1] == 0;
205     __i_ = 0;
206 }
207 
208 template<class _UIntType, size_t __w, size_t __s, size_t __r>
209 template<class _Sseq>
210 void
211 subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
212         integral_constant<unsigned, 1>)
213 {
214     const unsigned __k = 1;
215     uint32_t __ar[__r * __k];
216     __q.generate(__ar, __ar + __r * __k);
217     for (size_t __i = 0; __i < __r; ++__i)
218         __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
219     __c_ = __x_[__r-1] == 0;
220     __i_ = 0;
221 }
222 
223 template<class _UIntType, size_t __w, size_t __s, size_t __r>
224 template<class _Sseq>
225 void
226 subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
227         integral_constant<unsigned, 2>)
228 {
229     const unsigned __k = 2;
230     uint32_t __ar[__r * __k];
231     __q.generate(__ar, __ar + __r * __k);
232     for (size_t __i = 0; __i < __r; ++__i)
233         __x_[__i] = static_cast<result_type>(
234                   (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
235     __c_ = __x_[__r-1] == 0;
236     __i_ = 0;
237 }
238 
239 template<class _UIntType, size_t __w, size_t __s, size_t __r>
240 _UIntType
241 subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()()
242 {
243     const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
244     result_type& __xr = __x_[__i_];
245     result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
246     __xr = (__xs - __xr - __c_) & _Max;
247     __c_ = __new_c;
248     __i_ = (__i_ + 1) % __r;
249     return __xr;
250 }
251 
252 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
253 _LIBCPP_HIDE_FROM_ABI bool
254 operator==(
255     const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
256     const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
257 {
258     if (__x.__c_ != __y.__c_)
259         return false;
260     if (__x.__i_ == __y.__i_)
261         return _VSTD::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_);
262     if (__x.__i_ == 0 || __y.__i_ == 0)
263     {
264         size_t __j = _VSTD::min(_Rp - __x.__i_, _Rp - __y.__i_);
265         if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
266                          __y.__x_ + __y.__i_))
267             return false;
268         if (__x.__i_ == 0)
269             return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_);
270         return _VSTD::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j);
271     }
272     if (__x.__i_ < __y.__i_)
273     {
274         size_t __j = _Rp - __y.__i_;
275         if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
276                          __y.__x_ + __y.__i_))
277             return false;
278         if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp,
279                          __y.__x_))
280             return false;
281         return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
282                            __y.__x_ + (_Rp - (__x.__i_ + __j)));
283     }
284     size_t __j = _Rp - __x.__i_;
285     if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
286                      __x.__x_ + __x.__i_))
287         return false;
288     if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp,
289                      __x.__x_))
290         return false;
291     return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
292                        __x.__x_ + (_Rp - (__y.__i_ + __j)));
293 }
294 
295 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
296 inline _LIBCPP_INLINE_VISIBILITY
297 bool
298 operator!=(
299     const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
300     const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
301 {
302     return !(__x == __y);
303 }
304 
305 template <class _CharT, class _Traits,
306           class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
307 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
308 operator<<(basic_ostream<_CharT, _Traits>& __os,
309            const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
310 {
311     __save_flags<_CharT, _Traits> __lx(__os);
312     typedef basic_ostream<_CharT, _Traits> _Ostream;
313     __os.flags(_Ostream::dec | _Ostream::left);
314     _CharT __sp = __os.widen(' ');
315     __os.fill(__sp);
316     __os << __x.__x_[__x.__i_];
317     for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__j)
318         __os << __sp << __x.__x_[__j];
319     for (size_t __j = 0; __j < __x.__i_; ++__j)
320         __os << __sp << __x.__x_[__j];
321     __os << __sp << __x.__c_;
322     return __os;
323 }
324 
325 template <class _CharT, class _Traits,
326           class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
327 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
328 operator>>(basic_istream<_CharT, _Traits>& __is,
329            subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
330 {
331     __save_flags<_CharT, _Traits> __lx(__is);
332     typedef basic_istream<_CharT, _Traits> _Istream;
333     __is.flags(_Istream::dec | _Istream::skipws);
334     _UInt __t[_Rp+1];
335     for (size_t __i = 0; __i < _Rp+1; ++__i)
336         __is >> __t[__i];
337     if (!__is.fail())
338     {
339         for (size_t __i = 0; __i < _Rp; ++__i)
340             __x.__x_[__i] = __t[__i];
341         __x.__c_ = __t[_Rp];
342         __x.__i_ = 0;
343     }
344     return __is;
345 }
346 
347 _LIBCPP_END_NAMESPACE_STD
348 
349 _LIBCPP_POP_MACROS
350 
351 #endif // _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H
352