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