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 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> 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 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 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()) 172 : __a_(__a), __b_(__b) {} 173 174 _LIBCPP_HIDE_FROM_ABI result_type a() const {return __a_;} 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 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()) 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 201 _LIBCPP_HIDE_FROM_ABI explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {} 202 _LIBCPP_HIDE_FROM_ABI void reset() {} 203 204 // generating functions 205 template<class _URNG> 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 212 _LIBCPP_HIDE_FROM_ABI result_type a() const {return __p_.a();} 213 _LIBCPP_HIDE_FROM_ABI result_type b() const {return __p_.b();} 214 215 _LIBCPP_HIDE_FROM_ABI param_type param() const {return __p_;} 216 _LIBCPP_HIDE_FROM_ABI void param(const param_type& __p) {__p_ = __p;} 217 218 _LIBCPP_HIDE_FROM_ABI result_type min() const {return a();} 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 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