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