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