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_UNIFORM_INT_DISTRIBUTION_H
10 #define _LIBCPP___RANDOM_UNIFORM_INT_DISTRIBUTION_H
11
12 #include <__config>
13 #include <__random/is_valid.h>
14 #include <__random/log2.h>
15 #include <bit>
16 #include <cstddef>
17 #include <cstdint>
18 #include <iosfwd>
19 #include <limits>
20 #include <type_traits>
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 _Engine, class _UIntType>
32 class __independent_bits_engine
33 {
34 public:
35 // types
36 typedef _UIntType result_type;
37
38 private:
39 typedef typename _Engine::result_type _Engine_result_type;
40 typedef __conditional_t<sizeof(_Engine_result_type) <= sizeof(result_type), result_type, _Engine_result_type>
41 _Working_result_type;
42
43 _Engine& __e_;
44 size_t __w_;
45 size_t __w0_;
46 size_t __n_;
47 size_t __n0_;
48 _Working_result_type __y0_;
49 _Working_result_type __y1_;
50 _Engine_result_type __mask0_;
51 _Engine_result_type __mask1_;
52
53 #ifdef _LIBCPP_CXX03_LANG
54 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
55 + _Working_result_type(1);
56 #else
57 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
58 + _Working_result_type(1);
59 #endif
60 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
61 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
62 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
63
64 public:
65 // constructors and seeding functions
66 __independent_bits_engine(_Engine& __e, size_t __w);
67
68 // generating functions
operator()69 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
70
71 private:
72 result_type __eval(false_type);
73 result_type __eval(true_type);
74 };
75
76 template<class _Engine, class _UIntType>
77 __independent_bits_engine<_Engine, _UIntType>
__independent_bits_engine(_Engine & __e,size_t __w)78 ::__independent_bits_engine(_Engine& __e, size_t __w)
79 : __e_(__e),
80 __w_(__w)
81 {
82 __n_ = __w_ / __m + (__w_ % __m != 0);
83 __w0_ = __w_ / __n_;
84 if (_Rp == 0)
85 __y0_ = _Rp;
86 else if (__w0_ < _WDt)
87 __y0_ = (_Rp >> __w0_) << __w0_;
88 else
89 __y0_ = 0;
90 if (_Rp - __y0_ > __y0_ / __n_)
91 {
92 ++__n_;
93 __w0_ = __w_ / __n_;
94 if (__w0_ < _WDt)
95 __y0_ = (_Rp >> __w0_) << __w0_;
96 else
97 __y0_ = 0;
98 }
99 __n0_ = __n_ - __w_ % __n_;
100 if (__w0_ < _WDt - 1)
101 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);
102 else
103 __y1_ = 0;
104 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
105 _Engine_result_type(0);
106 __mask1_ = __w0_ < _EDt - 1 ?
107 _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
108 _Engine_result_type(~0);
109 }
110
111 template<class _Engine, class _UIntType>
112 inline
113 _UIntType
__eval(false_type)114 __independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
115 {
116 return static_cast<result_type>(__e_() & __mask0_);
117 }
118
119 template<class _Engine, class _UIntType>
120 _UIntType
__eval(true_type)121 __independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
122 {
123 const size_t _WRt = numeric_limits<result_type>::digits;
124 result_type _Sp = 0;
125 for (size_t __k = 0; __k < __n0_; ++__k)
126 {
127 _Engine_result_type __u;
128 do
129 {
130 __u = __e_() - _Engine::min();
131 } while (__u >= __y0_);
132 if (__w0_ < _WRt)
133 _Sp <<= __w0_;
134 else
135 _Sp = 0;
136 _Sp += __u & __mask0_;
137 }
138 for (size_t __k = __n0_; __k < __n_; ++__k)
139 {
140 _Engine_result_type __u;
141 do
142 {
143 __u = __e_() - _Engine::min();
144 } while (__u >= __y1_);
145 if (__w0_ < _WRt - 1)
146 _Sp <<= __w0_ + 1;
147 else
148 _Sp = 0;
149 _Sp += __u & __mask1_;
150 }
151 return _Sp;
152 }
153
154 template<class _IntType = int>
155 class uniform_int_distribution
156 {
157 static_assert(__libcpp_random_is_valid_inttype<_IntType>::value, "IntType must be a supported integer type");
158 public:
159 // types
160 typedef _IntType result_type;
161
162 class param_type
163 {
164 result_type __a_;
165 result_type __b_;
166 public:
167 typedef uniform_int_distribution distribution_type;
168
169 explicit param_type(result_type __a = 0,
170 result_type __b = numeric_limits<result_type>::max())
__a_(__a)171 : __a_(__a), __b_(__b) {}
172
a()173 result_type a() const {return __a_;}
b()174 result_type b() const {return __b_;}
175
176 _LIBCPP_HIDE_FROM_ABI
177 friend bool operator==(const param_type& __x, const param_type& __y)
178 {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
179 _LIBCPP_HIDE_FROM_ABI
180 friend bool operator!=(const param_type& __x, const param_type& __y)
181 {return !(__x == __y);}
182 };
183
184 private:
185 param_type __p_;
186
187 public:
188 // constructors and reset functions
189 #ifndef _LIBCPP_CXX03_LANG
uniform_int_distribution()190 uniform_int_distribution() : uniform_int_distribution(0) {}
191 explicit uniform_int_distribution(
192 result_type __a, result_type __b = numeric_limits<result_type>::max())
__p_(param_type (__a,__b))193 : __p_(param_type(__a, __b)) {}
194 #else
195 explicit uniform_int_distribution(
196 result_type __a = 0,
197 result_type __b = numeric_limits<result_type>::max())
198 : __p_(param_type(__a, __b)) {}
199 #endif
uniform_int_distribution(const param_type & __p)200 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
reset()201 void reset() {}
202
203 // generating functions
operator()204 template<class _URNG> result_type operator()(_URNG& __g)
205 {return (*this)(__g, __p_);}
206 template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
207
208 // property functions
a()209 result_type a() const {return __p_.a();}
b()210 result_type b() const {return __p_.b();}
211
param()212 param_type param() const {return __p_;}
param(const param_type & __p)213 void param(const param_type& __p) {__p_ = __p;}
214
min()215 result_type min() const {return a();}
max()216 result_type max() const {return b();}
217
218 _LIBCPP_HIDE_FROM_ABI
219 friend bool operator==(const uniform_int_distribution& __x,
220 const uniform_int_distribution& __y)
221 {return __x.__p_ == __y.__p_;}
222 _LIBCPP_HIDE_FROM_ABI
223 friend bool operator!=(const uniform_int_distribution& __x,
224 const uniform_int_distribution& __y)
225 {return !(__x == __y);}
226 };
227
228 template<class _IntType>
229 template<class _URNG>
230 typename uniform_int_distribution<_IntType>::result_type
operator()231 uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
232 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
233 {
234 static_assert(__libcpp_random_is_valid_urng<_URNG>::value, "");
235 typedef __conditional_t<sizeof(result_type) <= sizeof(uint32_t), uint32_t, __make_unsigned_t<result_type> >
236 _UIntType;
237 const _UIntType _Rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1);
238 if (_Rp == 1)
239 return __p.a();
240 const size_t _Dt = numeric_limits<_UIntType>::digits;
241 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
242 if (_Rp == 0)
243 return static_cast<result_type>(_Eng(__g, _Dt)());
244 size_t __w = _Dt - std::__countl_zero(_Rp) - 1;
245 if ((_Rp & (numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0)
246 ++__w;
247 _Eng __e(__g, __w);
248 _UIntType __u;
249 do
250 {
251 __u = __e();
252 } while (__u >= _Rp);
253 return static_cast<result_type>(__u + __p.a());
254 }
255
256 template <class _CharT, class _Traits, class _IT>
257 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
258 operator<<(basic_ostream<_CharT, _Traits>& __os,
259 const uniform_int_distribution<_IT>& __x)
260 {
261 __save_flags<_CharT, _Traits> __lx(__os);
262 typedef basic_ostream<_CharT, _Traits> _Ostream;
263 __os.flags(_Ostream::dec | _Ostream::left);
264 _CharT __sp = __os.widen(' ');
265 __os.fill(__sp);
266 return __os << __x.a() << __sp << __x.b();
267 }
268
269 template <class _CharT, class _Traits, class _IT>
270 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
271 operator>>(basic_istream<_CharT, _Traits>& __is,
272 uniform_int_distribution<_IT>& __x)
273 {
274 typedef uniform_int_distribution<_IT> _Eng;
275 typedef typename _Eng::result_type result_type;
276 typedef typename _Eng::param_type param_type;
277 __save_flags<_CharT, _Traits> __lx(__is);
278 typedef basic_istream<_CharT, _Traits> _Istream;
279 __is.flags(_Istream::dec | _Istream::skipws);
280 result_type __a;
281 result_type __b;
282 __is >> __a >> __b;
283 if (!__is.fail())
284 __x.param(param_type(__a, __b));
285 return __is;
286 }
287
288 _LIBCPP_END_NAMESPACE_STD
289
290 _LIBCPP_POP_MACROS
291
292 #endif // _LIBCPP___RANDOM_UNIFORM_INT_DISTRIBUTION_H
293