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
min()87 static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
88 _LIBCPP_INLINE_VISIBILITY
max()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
subtract_with_carry_engine()95 subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {}
96 _LIBCPP_INLINE_VISIBILITY
subtract_with_carry_engine(result_type __sd)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, __enable_if_t<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value, int> = 0>
105 _LIBCPP_INLINE_VISIBILITY
subtract_with_carry_engine(_Sseq & __q)106 explicit subtract_with_carry_engine(_Sseq& __q)
107 {seed(__q);}
108 _LIBCPP_INLINE_VISIBILITY
109 void seed(result_type __sd = default_seed)
110 {seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
111 template<class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value, int> = 0>
112 _LIBCPP_INLINE_VISIBILITY
113 void
seed(_Sseq & __q)114 seed(_Sseq& __q)
115 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
116
117 // generating functions
118 _LIBCPP_HIDE_FROM_ABI result_type operator()();
119 _LIBCPP_INLINE_VISIBILITY
discard(unsigned long long __z)120 void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
121
122 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
123 friend
124 bool
125 operator==(
126 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
127 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
128
129 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
130 friend
131 bool
132 operator!=(
133 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
134 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
135
136 template <class _CharT, class _Traits,
137 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
138 friend
139 basic_ostream<_CharT, _Traits>&
140 operator<<(basic_ostream<_CharT, _Traits>& __os,
141 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
142
143 template <class _CharT, class _Traits,
144 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
145 friend
146 basic_istream<_CharT, _Traits>&
147 operator>>(basic_istream<_CharT, _Traits>& __is,
148 subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
149
150 private:
151
152 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 1>);
153 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 2>);
154 template<class _Sseq>
155 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
156 template<class _Sseq>
157 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
158 };
159
160 template<class _UIntType, size_t __w, size_t __s, size_t __r>
161 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size;
162
163 template<class _UIntType, size_t __w, size_t __s, size_t __r>
164 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag;
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>::long_lag;
168
169 template<class _UIntType, size_t __w, size_t __s, size_t __r>
170 _LIBCPP_CONSTEXPR const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type
171 subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed;
172
173 template<class _UIntType, size_t __w, size_t __s, size_t __r>
174 void
seed(result_type __sd,integral_constant<unsigned,1>)175 subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
176 integral_constant<unsigned, 1>)
177 {
178 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
179 __e(__sd == 0u ? default_seed : __sd);
180 for (size_t __i = 0; __i < __r; ++__i)
181 __x_[__i] = static_cast<result_type>(__e() & _Max);
182 __c_ = __x_[__r-1] == 0;
183 __i_ = 0;
184 }
185
186 template<class _UIntType, size_t __w, size_t __s, size_t __r>
187 void
seed(result_type __sd,integral_constant<unsigned,2>)188 subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
189 integral_constant<unsigned, 2>)
190 {
191 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
192 __e(__sd == 0u ? default_seed : __sd);
193 for (size_t __i = 0; __i < __r; ++__i)
194 {
195 result_type __e0 = __e();
196 __x_[__i] = static_cast<result_type>(
197 (__e0 + ((uint64_t)__e() << 32)) & _Max);
198 }
199 __c_ = __x_[__r-1] == 0;
200 __i_ = 0;
201 }
202
203 template<class _UIntType, size_t __w, size_t __s, size_t __r>
204 template<class _Sseq>
205 void
__seed(_Sseq & __q,integral_constant<unsigned,1>)206 subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
207 integral_constant<unsigned, 1>)
208 {
209 const unsigned __k = 1;
210 uint32_t __ar[__r * __k];
211 __q.generate(__ar, __ar + __r * __k);
212 for (size_t __i = 0; __i < __r; ++__i)
213 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
214 __c_ = __x_[__r-1] == 0;
215 __i_ = 0;
216 }
217
218 template<class _UIntType, size_t __w, size_t __s, size_t __r>
219 template<class _Sseq>
220 void
__seed(_Sseq & __q,integral_constant<unsigned,2>)221 subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
222 integral_constant<unsigned, 2>)
223 {
224 const unsigned __k = 2;
225 uint32_t __ar[__r * __k];
226 __q.generate(__ar, __ar + __r * __k);
227 for (size_t __i = 0; __i < __r; ++__i)
228 __x_[__i] = static_cast<result_type>(
229 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
230 __c_ = __x_[__r-1] == 0;
231 __i_ = 0;
232 }
233
234 template<class _UIntType, size_t __w, size_t __s, size_t __r>
235 _UIntType
operator()236 subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()()
237 {
238 const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
239 result_type& __xr = __x_[__i_];
240 result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
241 __xr = (__xs - __xr - __c_) & _Max;
242 __c_ = __new_c;
243 __i_ = (__i_ + 1) % __r;
244 return __xr;
245 }
246
247 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
248 _LIBCPP_HIDE_FROM_ABI bool
249 operator==(
250 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
251 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
252 {
253 if (__x.__c_ != __y.__c_)
254 return false;
255 if (__x.__i_ == __y.__i_)
256 return _VSTD::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_);
257 if (__x.__i_ == 0 || __y.__i_ == 0)
258 {
259 size_t __j = _VSTD::min(_Rp - __x.__i_, _Rp - __y.__i_);
260 if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
261 __y.__x_ + __y.__i_))
262 return false;
263 if (__x.__i_ == 0)
264 return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_);
265 return _VSTD::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j);
266 }
267 if (__x.__i_ < __y.__i_)
268 {
269 size_t __j = _Rp - __y.__i_;
270 if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
271 __y.__x_ + __y.__i_))
272 return false;
273 if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp,
274 __y.__x_))
275 return false;
276 return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
277 __y.__x_ + (_Rp - (__x.__i_ + __j)));
278 }
279 size_t __j = _Rp - __x.__i_;
280 if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
281 __x.__x_ + __x.__i_))
282 return false;
283 if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp,
284 __x.__x_))
285 return false;
286 return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
287 __x.__x_ + (_Rp - (__y.__i_ + __j)));
288 }
289
290 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
291 inline _LIBCPP_INLINE_VISIBILITY
292 bool
293 operator!=(
294 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
295 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
296 {
297 return !(__x == __y);
298 }
299
300 template <class _CharT, class _Traits,
301 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
302 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
303 operator<<(basic_ostream<_CharT, _Traits>& __os,
304 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
305 {
306 __save_flags<_CharT, _Traits> __lx(__os);
307 typedef basic_ostream<_CharT, _Traits> _Ostream;
308 __os.flags(_Ostream::dec | _Ostream::left);
309 _CharT __sp = __os.widen(' ');
310 __os.fill(__sp);
311 __os << __x.__x_[__x.__i_];
312 for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__j)
313 __os << __sp << __x.__x_[__j];
314 for (size_t __j = 0; __j < __x.__i_; ++__j)
315 __os << __sp << __x.__x_[__j];
316 __os << __sp << __x.__c_;
317 return __os;
318 }
319
320 template <class _CharT, class _Traits,
321 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
322 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
323 operator>>(basic_istream<_CharT, _Traits>& __is,
324 subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
325 {
326 __save_flags<_CharT, _Traits> __lx(__is);
327 typedef basic_istream<_CharT, _Traits> _Istream;
328 __is.flags(_Istream::dec | _Istream::skipws);
329 _UInt __t[_Rp+1];
330 for (size_t __i = 0; __i < _Rp+1; ++__i)
331 __is >> __t[__i];
332 if (!__is.fail())
333 {
334 for (size_t __i = 0; __i < _Rp; ++__i)
335 __x.__x_[__i] = __t[__i];
336 __x.__c_ = __t[_Rp];
337 __x.__i_ = 0;
338 }
339 return __is;
340 }
341
342 _LIBCPP_END_NAMESPACE_STD
343
344 _LIBCPP_POP_MACROS
345
346 #endif // _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H
347