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