Debian Codegraph @

libcxx/include/__cxx03/__random/subtract_with_carry_engine.h

raw
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___CXX03___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H
10 #define _LIBCPP___CXX03___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H
11
12 #include <__cxx03/__algorithm/equal.h>
13 #include <__cxx03/__algorithm/min.h>
14 #include <__cxx03/__config>
15 #include <__cxx03/__random/is_seed_sequence.h>
16 #include <__cxx03/__random/linear_congruential_engine.h>
17 #include <__cxx03/cstddef>
18 #include <__cxx03/cstdint>
19 #include <__cxx03/iosfwd>
20 #include <__cxx03/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 <__cxx03/__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 operator==(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
36 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
37
38 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
39 _LIBCPP_HIDE_FROM_ABI bool operator!=(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
40 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
41
42 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
43 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
44 operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
45
46 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
47 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
48 operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
49
50 template <class _UIntType, size_t __w, size_t __s, size_t __r>
51 class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine {
52 public:
53 // types
54 typedef _UIntType result_type;
55
56 private:
57 result_type __x_[__r];
58 result_type __c_;
59 size_t __i_;
60
61 static const result_type _Dt = numeric_limits<result_type>::digits;
62 static_assert(0 < __w, "subtract_with_carry_engine invalid parameters");
63 static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters");
64 static_assert(0 < __s, "subtract_with_carry_engine invalid parameters");
65 static_assert(__s < __r, "subtract_with_carry_engine invalid parameters");
66
67 public:
68 static const result_type _Min = 0;
69 static const result_type _Max = __w == _Dt ? result_type(~0) : (result_type(1) << __w) - result_type(1);
70 static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");
71
72 // engine characteristics
73 static const size_t word_size = __w;
74 static const size_t short_lag = __s;
75 static const size_t long_lag = __r;
76 _LIBCPP_HIDE_FROM_ABI static result_type min() { return _Min; }
77 _LIBCPP_HIDE_FROM_ABI static result_type max() { return _Max; }
78 static const result_type default_seed = 19780503u;
79
80 // constructors and seeding functions
81 _LIBCPP_HIDE_FROM_ABI explicit subtract_with_carry_engine(result_type __sd = default_seed) { seed(__sd); }
82 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value, int> = 0>
83 _LIBCPP_HIDE_FROM_ABI explicit subtract_with_carry_engine(_Sseq& __q) {
84 seed(__q);
85 }
86 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd = default_seed) {
87 seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());
88 }
89 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value, int> = 0>
90 _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) {
91 __seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());
92 }
93
94 // generating functions
95 _LIBCPP_HIDE_FROM_ABI result_type operator()();
96 _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) {
97 for (; __z; --__z)
98 operator()();
99 }
100
101 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
102 friend bool operator==(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
103 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
104
105 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
106 friend bool operator!=(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
107 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
108
109 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
110 friend basic_ostream<_CharT, _Traits>&
111 operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
112
113 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
114 friend basic_istream<_CharT, _Traits>&
115 operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
116
117 private:
118 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 1>);
119 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 2>);
120 template <class _Sseq>
121 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
122 template <class _Sseq>
123 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
124 };
125
126 template <class _UIntType, size_t __w, size_t __s, size_t __r>
127 const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size;
128
129 template <class _UIntType, size_t __w, size_t __s, size_t __r>
130 const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag;
131
132 template <class _UIntType, size_t __w, size_t __s, size_t __r>
133 const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::long_lag;
134
135 template <class _UIntType, size_t __w, size_t __s, size_t __r>
136 const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type
137 subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed;
138
139 template <class _UIntType, size_t __w, size_t __s, size_t __r>
140 void subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, integral_constant<unsigned, 1>) {
141 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> __e(__sd == 0u ? default_seed : __sd);
142 for (size_t __i = 0; __i < __r; ++__i)
143 __x_[__i] = static_cast<result_type>(__e() & _Max);
144 __c_ = __x_[__r - 1] == 0;
145 __i_ = 0;
146 }
147
148 template <class _UIntType, size_t __w, size_t __s, size_t __r>
149 void subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, integral_constant<unsigned, 2>) {
150 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> __e(__sd == 0u ? default_seed : __sd);
151 for (size_t __i = 0; __i < __r; ++__i) {
152 result_type __e0 = __e();
153 __x_[__i] = static_cast<result_type>((__e0 + ((uint64_t)__e() << 32)) & _Max);
154 }
155 __c_ = __x_[__r - 1] == 0;
156 __i_ = 0;
157 }
158
159 template <class _UIntType, size_t __w, size_t __s, size_t __r>
160 template <class _Sseq>
161 void subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, integral_constant<unsigned, 1>) {
162 const unsigned __k = 1;
163 uint32_t __ar[__r * __k];
164 __q.generate(__ar, __ar + __r * __k);
165 for (size_t __i = 0; __i < __r; ++__i)
166 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
167 __c_ = __x_[__r - 1] == 0;
168 __i_ = 0;
169 }
170
171 template <class _UIntType, size_t __w, size_t __s, size_t __r>
172 template <class _Sseq>
173 void subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, integral_constant<unsigned, 2>) {
174 const unsigned __k = 2;
175 uint32_t __ar[__r * __k];
176 __q.generate(__ar, __ar + __r * __k);
177 for (size_t __i = 0; __i < __r; ++__i)
178 __x_[__i] = static_cast<result_type>((__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
179 __c_ = __x_[__r - 1] == 0;
180 __i_ = 0;
181 }
182
183 template <class _UIntType, size_t __w, size_t __s, size_t __r>
184 _UIntType subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()() {
185 const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
186 result_type& __xr = __x_[__i_];
187 result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
188 __xr = (__xs - __xr - __c_) & _Max;
189 __c_ = __new_c;
190 __i_ = (__i_ + 1) % __r;
191 return __xr;
192 }
193
194 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
195 _LIBCPP_HIDE_FROM_ABI bool operator==(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
196 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y) {
197 if (__x.__c_ != __y.__c_)
198 return false;
199 if (__x.__i_ == __y.__i_)
200 return std::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_);
201 if (__x.__i_ == 0 || __y.__i_ == 0) {
202 size_t __j = std::min(_Rp - __x.__i_, _Rp - __y.__i_);
203 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j, __y.__x_ + __y.__i_))
204 return false;
205 if (__x.__i_ == 0)
206 return std::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_);
207 return std::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j);
208 }
209 if (__x.__i_ < __y.__i_) {
210 size_t __j = _Rp - __y.__i_;
211 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j), __y.__x_ + __y.__i_))
212 return false;
213 if (!std::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp, __y.__x_))
214 return false;
215 return std::equal(__x.__x_, __x.__x_ + __x.__i_, __y.__x_ + (_Rp - (__x.__i_ + __j)));
216 }
217 size_t __j = _Rp - __x.__i_;
218 if (!std::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j), __x.__x_ + __x.__i_))
219 return false;
220 if (!std::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp, __x.__x_))
221 return false;
222 return std::equal(__y.__x_, __y.__x_ + __y.__i_, __x.__x_ + (_Rp - (__y.__i_ + __j)));
223 }
224
225 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
226 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
227 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y) {
228 return !(__x == __y);
229 }
230
231 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
232 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
233 operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x) {
234 __save_flags<_CharT, _Traits> __lx(__os);
235 typedef basic_ostream<_CharT, _Traits> _Ostream;
236 __os.flags(_Ostream::dec | _Ostream::left);
237 _CharT __sp = __os.widen(' ');
238 __os.fill(__sp);
239 __os << __x.__x_[__x.__i_];
240 for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__j)
241 __os << __sp << __x.__x_[__j];
242 for (size_t __j = 0; __j < __x.__i_; ++__j)
243 __os << __sp << __x.__x_[__j];
244 __os << __sp << __x.__c_;
245 return __os;
246 }
247
248 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
249 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
250 operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x) {
251 __save_flags<_CharT, _Traits> __lx(__is);
252 typedef basic_istream<_CharT, _Traits> _Istream;
253 __is.flags(_Istream::dec | _Istream::skipws);
254 _UInt __t[_Rp + 1];
255 for (size_t __i = 0; __i < _Rp + 1; ++__i)
256 __is >> __t[__i];
257 if (!__is.fail()) {
258 for (size_t __i = 0; __i < _Rp; ++__i)
259 __x.__x_[__i] = __t[__i];
260 __x.__c_ = __t[_Rp];
261 __x.__i_ = 0;
262 }
263 return __is;
264 }
265
266 _LIBCPP_END_NAMESPACE_STD
267
268 _LIBCPP_POP_MACROS
269
270 #endif // _LIBCPP___CXX03___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H