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