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