265 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___RANDOM_UNIFORM_INT_DISTRIBUTION_H10#define _LIBCPP___RANDOM_UNIFORM_INT_DISTRIBUTION_H11 12#include <__bit/countl.h>13#include <__config>14#include <__cstddef/size_t.h>15#include <__random/is_valid.h>16#include <__random/log2.h>17#include <__type_traits/conditional.h>18#include <__type_traits/make_unsigned.h>19#include <cstdint>20#include <iosfwd>21#include <limits>22 23#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)24# pragma GCC system_header25#endif26 27_LIBCPP_PUSH_MACROS28#include <__undef_macros>29 30_LIBCPP_BEGIN_NAMESPACE_STD31 32template <class _Engine, class _UIntType>33class __independent_bits_engine {34public:35 // types36 typedef _UIntType result_type;37 38private: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_LANG54 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min + _Working_result_type(1);55#else56 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min() + _Working_result_type(1);57#endif58 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 62public:63 // constructors and seeding functions64 _LIBCPP_HIDE_FROM_ABI __independent_bits_engine(_Engine& __e, size_t __w);65 66 // generating functions67 _LIBCPP_HIDE_FROM_ABI result_type operator()() { return __eval(integral_constant<bool, _Rp != 0>()); }68 69private:70 _LIBCPP_HIDE_FROM_ABI result_type __eval(false_type);71 _LIBCPP_HIDE_FROM_ABI result_type __eval(true_type);72};73 74template <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 else84 __y0_ = 0;85 if (_Rp - __y0_ > __y0_ / __n_) {86 ++__n_;87 __w0_ = __w_ / __n_;88 if (__w0_ < _WDt)89 __y0_ = (_Rp >> __w0_) << __w0_;90 else91 __y0_ = 0;92 }93 __n0_ = __n_ - __w_ % __n_;94 if (__w0_ < _WDt - 1)95 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);96 else97 __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 102template <class _Engine, class _UIntType>103inline _UIntType __independent_bits_engine<_Engine, _UIntType>::__eval(false_type) {104 return static_cast<result_type>(__e_() & __mask0_);105}106 107template <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 else119 __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 else130 __sp = 0;131 __sp += __u & __mask1_;132 }133 return __sp;134}135 136template <class _IntType = int>137class uniform_int_distribution {138 static_assert(__libcpp_random_is_valid_inttype<_IntType>::value, "IntType must be a supported integer type");139 140public:141 // types142 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 163private:164 param_type __p_;165 166public:167 // constructors and reset functions168#ifndef _LIBCPP_CXX03_LANG169 _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#else174 explicit uniform_int_distribution(result_type __a = 0, result_type __b = numeric_limits<result_type>::max())175 : __p_(param_type(__a, __b)) {}176#endif177 _LIBCPP_HIDE_FROM_ABI explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}178 _LIBCPP_HIDE_FROM_ABI void reset() {}179 180 // generating functions181 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 functions189 _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 bool199 operator==(const uniform_int_distribution& __x, const uniform_int_distribution& __y) {200 return __x.__p_ == __y.__p_;201 }202 _LIBCPP_HIDE_FROM_ABI friend bool203 operator!=(const uniform_int_distribution& __x, const uniform_int_distribution& __y) {204 return !(__x == __y);205 }206};207 208template <class _IntType>209template <class _URNG>210typename 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 232template <class _CharT, class _Traits, class _IT>233_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&234operator<<(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 243template <class _CharT, class _Traits, class _IT>244_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&245operator>>(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_STD261 262_LIBCPP_POP_MACROS263 264#endif // _LIBCPP___RANDOM_UNIFORM_INT_DISTRIBUTION_H265