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