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_INDEPENDENT_BITS_ENGINE_H 10 #define _LIBCPP___RANDOM_INDEPENDENT_BITS_ENGINE_H 11 12 #include <__config> 13 #include <__random/is_seed_sequence.h> 14 #include <__random/log2.h> 15 #include <__utility/move.h> 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 template<class _Engine, size_t __w, class _UIntType> 30 class _LIBCPP_TEMPLATE_VIS independent_bits_engine 31 { 32 template <class _UInt, _UInt _R0, size_t _Wp, size_t _Mp> 33 class __get_n 34 { 35 static _LIBCPP_CONSTEXPR const size_t _Dt = numeric_limits<_UInt>::digits; 36 static _LIBCPP_CONSTEXPR const size_t _Np = _Wp / _Mp + (_Wp % _Mp != 0); 37 static _LIBCPP_CONSTEXPR const size_t _W0 = _Wp / _Np; 38 static _LIBCPP_CONSTEXPR const _UInt _Y0 = _W0 >= _Dt ? 0 : (_R0 >> _W0) << _W0; 39 public: 40 static _LIBCPP_CONSTEXPR const size_t value = _R0 - _Y0 > _Y0 / _Np ? _Np + 1 : _Np; 41 }; 42 public: 43 // types 44 typedef _UIntType result_type; 45 46 private: 47 _Engine __e_; 48 49 static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits; 50 static_assert( 0 < __w, "independent_bits_engine invalid parameters"); 51 static_assert(__w <= _Dt, "independent_bits_engine invalid parameters"); 52 53 typedef typename _Engine::result_type _Engine_result_type; 54 typedef __conditional_t<sizeof(_Engine_result_type) <= sizeof(result_type), result_type, _Engine_result_type> 55 _Working_result_type; 56 #ifdef _LIBCPP_CXX03_LANG 57 static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min 58 + _Working_result_type(1); 59 #else 60 static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min() 61 + _Working_result_type(1); 62 #endif 63 static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value; 64 static _LIBCPP_CONSTEXPR const size_t __n = __get_n<_Working_result_type, _Rp, __w, __m>::value; 65 static _LIBCPP_CONSTEXPR const size_t __w0 = __w / __n; 66 static _LIBCPP_CONSTEXPR const size_t __n0 = __n - __w % __n; 67 static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits; 68 static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits; 69 static _LIBCPP_CONSTEXPR const _Working_result_type __y0 = __w0 >= _WDt ? 0 : 70 (_Rp >> __w0) << __w0; 71 static _LIBCPP_CONSTEXPR const _Working_result_type __y1 = __w0 >= _WDt - 1 ? 0 : 72 (_Rp >> (__w0+1)) << (__w0+1); 73 static _LIBCPP_CONSTEXPR const _Engine_result_type __mask0 = __w0 > 0 ? 74 _Engine_result_type(~0) >> (_EDt - __w0) : 75 _Engine_result_type(0); 76 static _LIBCPP_CONSTEXPR const _Engine_result_type __mask1 = __w0 < _EDt - 1 ? 77 _Engine_result_type(~0) >> (_EDt - (__w0 + 1)) : 78 _Engine_result_type(~0); 79 public: 80 static _LIBCPP_CONSTEXPR const result_type _Min = 0; 81 static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) : 82 (result_type(1) << __w) - result_type(1); 83 static_assert(_Min < _Max, "independent_bits_engine invalid parameters"); 84 85 // engine characteristics 86 _LIBCPP_INLINE_VISIBILITY 87 static _LIBCPP_CONSTEXPR result_type min() { return _Min; } 88 _LIBCPP_INLINE_VISIBILITY 89 static _LIBCPP_CONSTEXPR result_type max() { return _Max; } 90 91 // constructors and seeding functions 92 _LIBCPP_INLINE_VISIBILITY 93 independent_bits_engine() {} 94 _LIBCPP_INLINE_VISIBILITY 95 explicit independent_bits_engine(const _Engine& __e) 96 : __e_(__e) {} 97 #ifndef _LIBCPP_CXX03_LANG 98 _LIBCPP_INLINE_VISIBILITY 99 explicit independent_bits_engine(_Engine&& __e) 100 : __e_(_VSTD::move(__e)) {} 101 #endif // _LIBCPP_CXX03_LANG 102 _LIBCPP_INLINE_VISIBILITY 103 explicit independent_bits_engine(result_type __sd) : __e_(__sd) {} 104 template<class _Sseq> 105 _LIBCPP_INLINE_VISIBILITY 106 explicit independent_bits_engine(_Sseq& __q, 107 typename enable_if<__is_seed_sequence<_Sseq, independent_bits_engine>::value && 108 !is_convertible<_Sseq, _Engine>::value>::type* = 0) 109 : __e_(__q) {} 110 _LIBCPP_INLINE_VISIBILITY 111 void seed() {__e_.seed();} 112 _LIBCPP_INLINE_VISIBILITY 113 void seed(result_type __sd) {__e_.seed(__sd);} 114 template<class _Sseq> 115 _LIBCPP_INLINE_VISIBILITY 116 typename enable_if 117 < 118 __is_seed_sequence<_Sseq, independent_bits_engine>::value, 119 void 120 >::type 121 seed(_Sseq& __q) {__e_.seed(__q);} 122 123 // generating functions 124 _LIBCPP_INLINE_VISIBILITY 125 result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());} 126 _LIBCPP_INLINE_VISIBILITY 127 void discard(unsigned long long __z) {for (; __z; --__z) operator()();} 128 129 // property functions 130 _LIBCPP_INLINE_VISIBILITY 131 const _Engine& base() const _NOEXCEPT {return __e_;} 132 133 template<class _Eng, size_t _Wp, class _UInt> 134 friend 135 bool 136 operator==( 137 const independent_bits_engine<_Eng, _Wp, _UInt>& __x, 138 const independent_bits_engine<_Eng, _Wp, _UInt>& __y); 139 140 template<class _Eng, size_t _Wp, class _UInt> 141 friend 142 bool 143 operator!=( 144 const independent_bits_engine<_Eng, _Wp, _UInt>& __x, 145 const independent_bits_engine<_Eng, _Wp, _UInt>& __y); 146 147 template <class _CharT, class _Traits, 148 class _Eng, size_t _Wp, class _UInt> 149 friend 150 basic_ostream<_CharT, _Traits>& 151 operator<<(basic_ostream<_CharT, _Traits>& __os, 152 const independent_bits_engine<_Eng, _Wp, _UInt>& __x); 153 154 template <class _CharT, class _Traits, 155 class _Eng, size_t _Wp, class _UInt> 156 friend 157 basic_istream<_CharT, _Traits>& 158 operator>>(basic_istream<_CharT, _Traits>& __is, 159 independent_bits_engine<_Eng, _Wp, _UInt>& __x); 160 161 private: 162 _LIBCPP_INLINE_VISIBILITY 163 result_type __eval(false_type); 164 result_type __eval(true_type); 165 166 template <size_t __count> 167 _LIBCPP_INLINE_VISIBILITY 168 static 169 typename enable_if 170 < 171 __count < _Dt, 172 result_type 173 >::type 174 __lshift(result_type __x) {return __x << __count;} 175 176 template <size_t __count> 177 _LIBCPP_INLINE_VISIBILITY 178 static 179 typename enable_if 180 < 181 (__count >= _Dt), 182 result_type 183 >::type 184 __lshift(result_type) {return result_type(0);} 185 }; 186 187 template<class _Engine, size_t __w, class _UIntType> 188 inline 189 _UIntType 190 independent_bits_engine<_Engine, __w, _UIntType>::__eval(false_type) 191 { 192 return static_cast<result_type>(__e_() & __mask0); 193 } 194 195 template<class _Engine, size_t __w, class _UIntType> 196 _UIntType 197 independent_bits_engine<_Engine, __w, _UIntType>::__eval(true_type) 198 { 199 result_type _Sp = 0; 200 for (size_t __k = 0; __k < __n0; ++__k) 201 { 202 _Engine_result_type __u; 203 do 204 { 205 __u = __e_() - _Engine::min(); 206 } while (__u >= __y0); 207 _Sp = static_cast<result_type>(__lshift<__w0>(_Sp) + (__u & __mask0)); 208 } 209 for (size_t __k = __n0; __k < __n; ++__k) 210 { 211 _Engine_result_type __u; 212 do 213 { 214 __u = __e_() - _Engine::min(); 215 } while (__u >= __y1); 216 _Sp = static_cast<result_type>(__lshift<__w0+1>(_Sp) + (__u & __mask1)); 217 } 218 return _Sp; 219 } 220 221 template<class _Eng, size_t _Wp, class _UInt> 222 inline _LIBCPP_INLINE_VISIBILITY 223 bool 224 operator==( 225 const independent_bits_engine<_Eng, _Wp, _UInt>& __x, 226 const independent_bits_engine<_Eng, _Wp, _UInt>& __y) 227 { 228 return __x.base() == __y.base(); 229 } 230 231 template<class _Eng, size_t _Wp, class _UInt> 232 inline _LIBCPP_INLINE_VISIBILITY 233 bool 234 operator!=( 235 const independent_bits_engine<_Eng, _Wp, _UInt>& __x, 236 const independent_bits_engine<_Eng, _Wp, _UInt>& __y) 237 { 238 return !(__x == __y); 239 } 240 241 template <class _CharT, class _Traits, 242 class _Eng, size_t _Wp, class _UInt> 243 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& 244 operator<<(basic_ostream<_CharT, _Traits>& __os, 245 const independent_bits_engine<_Eng, _Wp, _UInt>& __x) 246 { 247 return __os << __x.base(); 248 } 249 250 template <class _CharT, class _Traits, 251 class _Eng, size_t _Wp, class _UInt> 252 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& 253 operator>>(basic_istream<_CharT, _Traits>& __is, 254 independent_bits_engine<_Eng, _Wp, _UInt>& __x) 255 { 256 _Eng __e; 257 __is >> __e; 258 if (!__is.fail()) 259 __x.__e_ = __e; 260 return __is; 261 } 262 263 _LIBCPP_END_NAMESPACE_STD 264 265 _LIBCPP_POP_MACROS 266 267 #endif // _LIBCPP___RANDOM_INDEPENDENT_BITS_ENGINE_H 268