254 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___CXX03___RANDOM_UNIFORM_INT_DISTRIBUTION_H10#define _LIBCPP___CXX03___RANDOM_UNIFORM_INT_DISTRIBUTION_H11 12#include <__cxx03/__bit/countl.h>13#include <__cxx03/__config>14#include <__cxx03/__random/is_valid.h>15#include <__cxx03/__random/log2.h>16#include <__cxx03/__type_traits/conditional.h>17#include <__cxx03/__type_traits/make_unsigned.h>18#include <__cxx03/cstddef>19#include <__cxx03/cstdint>20#include <__cxx03/iosfwd>21#include <__cxx03/limits>22 23#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)24# pragma GCC system_header25#endif26 27_LIBCPP_PUSH_MACROS28#include <__cxx03/__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 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min + _Working_result_type(1);54 static const size_t __m = __log2<_Working_result_type, _Rp>::value;55 static const size_t _WDt = numeric_limits<_Working_result_type>::digits;56 static const size_t _EDt = numeric_limits<_Engine_result_type>::digits;57 58public:59 // constructors and seeding functions60 _LIBCPP_HIDE_FROM_ABI __independent_bits_engine(_Engine& __e, size_t __w);61 62 // generating functions63 _LIBCPP_HIDE_FROM_ABI result_type operator()() { return __eval(integral_constant<bool, _Rp != 0>()); }64 65private:66 _LIBCPP_HIDE_FROM_ABI result_type __eval(false_type);67 _LIBCPP_HIDE_FROM_ABI result_type __eval(true_type);68};69 70template <class _Engine, class _UIntType>71__independent_bits_engine<_Engine, _UIntType>::__independent_bits_engine(_Engine& __e, size_t __w)72 : __e_(__e), __w_(__w) {73 __n_ = __w_ / __m + (__w_ % __m != 0);74 __w0_ = __w_ / __n_;75 if (_Rp == 0)76 __y0_ = _Rp;77 else if (__w0_ < _WDt)78 __y0_ = (_Rp >> __w0_) << __w0_;79 else80 __y0_ = 0;81 if (_Rp - __y0_ > __y0_ / __n_) {82 ++__n_;83 __w0_ = __w_ / __n_;84 if (__w0_ < _WDt)85 __y0_ = (_Rp >> __w0_) << __w0_;86 else87 __y0_ = 0;88 }89 __n0_ = __n_ - __w_ % __n_;90 if (__w0_ < _WDt - 1)91 __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1);92 else93 __y1_ = 0;94 __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) : _Engine_result_type(0);95 __mask1_ = __w0_ < _EDt - 1 ? _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) : _Engine_result_type(~0);96}97 98template <class _Engine, class _UIntType>99inline _UIntType __independent_bits_engine<_Engine, _UIntType>::__eval(false_type) {100 return static_cast<result_type>(__e_() & __mask0_);101}102 103template <class _Engine, class _UIntType>104_UIntType __independent_bits_engine<_Engine, _UIntType>::__eval(true_type) {105 const size_t __w_rt = numeric_limits<result_type>::digits;106 result_type __sp = 0;107 for (size_t __k = 0; __k < __n0_; ++__k) {108 _Engine_result_type __u;109 do {110 __u = __e_() - _Engine::min();111 } while (__u >= __y0_);112 if (__w0_ < __w_rt)113 __sp <<= __w0_;114 else115 __sp = 0;116 __sp += __u & __mask0_;117 }118 for (size_t __k = __n0_; __k < __n_; ++__k) {119 _Engine_result_type __u;120 do {121 __u = __e_() - _Engine::min();122 } while (__u >= __y1_);123 if (__w0_ < __w_rt - 1)124 __sp <<= __w0_ + 1;125 else126 __sp = 0;127 __sp += __u & __mask1_;128 }129 return __sp;130}131 132template <class _IntType = int>133class uniform_int_distribution {134 static_assert(__libcpp_random_is_valid_inttype<_IntType>::value, "IntType must be a supported integer type");135 136public:137 // types138 typedef _IntType result_type;139 140 class param_type {141 result_type __a_;142 result_type __b_;143 144 public:145 typedef uniform_int_distribution distribution_type;146 147 _LIBCPP_HIDE_FROM_ABI explicit param_type(result_type __a = 0, result_type __b = numeric_limits<result_type>::max())148 : __a_(__a), __b_(__b) {}149 150 _LIBCPP_HIDE_FROM_ABI result_type a() const { return __a_; }151 _LIBCPP_HIDE_FROM_ABI result_type b() const { return __b_; }152 153 _LIBCPP_HIDE_FROM_ABI friend bool operator==(const param_type& __x, const param_type& __y) {154 return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;155 }156 _LIBCPP_HIDE_FROM_ABI friend bool operator!=(const param_type& __x, const param_type& __y) { return !(__x == __y); }157 };158 159private:160 param_type __p_;161 162public:163 // constructors and reset functions164 explicit uniform_int_distribution(result_type __a = 0, result_type __b = numeric_limits<result_type>::max())165 : __p_(param_type(__a, __b)) {}166 _LIBCPP_HIDE_FROM_ABI explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}167 _LIBCPP_HIDE_FROM_ABI void reset() {}168 169 // generating functions170 template <class _URNG>171 _LIBCPP_HIDE_FROM_ABI result_type operator()(_URNG& __g) {172 return (*this)(__g, __p_);173 }174 template <class _URNG>175 _LIBCPP_HIDE_FROM_ABI result_type operator()(_URNG& __g, const param_type& __p);176 177 // property functions178 _LIBCPP_HIDE_FROM_ABI result_type a() const { return __p_.a(); }179 _LIBCPP_HIDE_FROM_ABI result_type b() const { return __p_.b(); }180 181 _LIBCPP_HIDE_FROM_ABI param_type param() const { return __p_; }182 _LIBCPP_HIDE_FROM_ABI void param(const param_type& __p) { __p_ = __p; }183 184 _LIBCPP_HIDE_FROM_ABI result_type min() const { return a(); }185 _LIBCPP_HIDE_FROM_ABI result_type max() const { return b(); }186 187 _LIBCPP_HIDE_FROM_ABI friend bool188 operator==(const uniform_int_distribution& __x, const uniform_int_distribution& __y) {189 return __x.__p_ == __y.__p_;190 }191 _LIBCPP_HIDE_FROM_ABI friend bool192 operator!=(const uniform_int_distribution& __x, const uniform_int_distribution& __y) {193 return !(__x == __y);194 }195};196 197template <class _IntType>198template <class _URNG>199typename uniform_int_distribution<_IntType>::result_type uniform_int_distribution<_IntType>::operator()(200 _URNG& __g, const param_type& __p) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {201 static_assert(__libcpp_random_is_valid_urng<_URNG>::value, "");202 typedef __conditional_t<sizeof(result_type) <= sizeof(uint32_t), uint32_t, __make_unsigned_t<result_type> > _UIntType;203 const _UIntType __rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1);204 if (__rp == 1)205 return __p.a();206 const size_t __dt = numeric_limits<_UIntType>::digits;207 typedef __independent_bits_engine<_URNG, _UIntType> _Eng;208 if (__rp == 0)209 return static_cast<result_type>(_Eng(__g, __dt)());210 size_t __w = __dt - std::__countl_zero(__rp) - 1;211 if ((__rp & (numeric_limits<_UIntType>::max() >> (__dt - __w))) != 0)212 ++__w;213 _Eng __e(__g, __w);214 _UIntType __u;215 do {216 __u = __e();217 } while (__u >= __rp);218 return static_cast<result_type>(__u + __p.a());219}220 221template <class _CharT, class _Traits, class _IT>222_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&223operator<<(basic_ostream<_CharT, _Traits>& __os, const uniform_int_distribution<_IT>& __x) {224 __save_flags<_CharT, _Traits> __lx(__os);225 typedef basic_ostream<_CharT, _Traits> _Ostream;226 __os.flags(_Ostream::dec | _Ostream::left);227 _CharT __sp = __os.widen(' ');228 __os.fill(__sp);229 return __os << __x.a() << __sp << __x.b();230}231 232template <class _CharT, class _Traits, class _IT>233_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&234operator>>(basic_istream<_CharT, _Traits>& __is, uniform_int_distribution<_IT>& __x) {235 typedef uniform_int_distribution<_IT> _Eng;236 typedef typename _Eng::result_type result_type;237 typedef typename _Eng::param_type param_type;238 __save_flags<_CharT, _Traits> __lx(__is);239 typedef basic_istream<_CharT, _Traits> _Istream;240 __is.flags(_Istream::dec | _Istream::skipws);241 result_type __a;242 result_type __b;243 __is >> __a >> __b;244 if (!__is.fail())245 __x.param(param_type(__a, __b));246 return __is;247}248 249_LIBCPP_END_NAMESPACE_STD250 251_LIBCPP_POP_MACROS252 253#endif // _LIBCPP___CXX03___RANDOM_UNIFORM_INT_DISTRIBUTION_H254