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