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 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> 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 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 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()) 171 : __a_(__a), __b_(__b) {} 172 173 result_type a() const {return __a_;} 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 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()) 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 200 explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {} 201 void reset() {} 202 203 // generating functions 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 209 result_type a() const {return __p_.a();} 210 result_type b() const {return __p_.b();} 211 212 param_type param() const {return __p_;} 213 void param(const param_type& __p) {__p_ = __p;} 214 215 result_type min() const {return a();} 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 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