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_SUBTRACT_WITH_CARRY_ENGINE_H 10 #define _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H 11 12 #include <__algorithm/equal.h> 13 #include <__algorithm/min.h> 14 #include <__config> 15 #include <__random/is_seed_sequence.h> 16 #include <__random/linear_congruential_engine.h> 17 #include <cstddef> 18 #include <cstdint> 19 #include <iosfwd> 20 #include <limits> 21 22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 23 # pragma GCC system_header 24 #endif 25 26 _LIBCPP_PUSH_MACROS 27 #include <__undef_macros> 28 29 _LIBCPP_BEGIN_NAMESPACE_STD 30 31 template<class _UIntType, size_t __w, size_t __s, size_t __r> 32 class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine; 33 34 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 35 _LIBCPP_HIDE_FROM_ABI bool 36 operator==( 37 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x, 38 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y); 39 40 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 41 _LIBCPP_INLINE_VISIBILITY 42 bool 43 operator!=( 44 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x, 45 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y); 46 47 template <class _CharT, class _Traits, 48 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 49 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& 50 operator<<(basic_ostream<_CharT, _Traits>& __os, 51 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x); 52 53 template <class _CharT, class _Traits, 54 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 55 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& 56 operator>>(basic_istream<_CharT, _Traits>& __is, 57 subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x); 58 59 template<class _UIntType, size_t __w, size_t __s, size_t __r> 60 class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine 61 { 62 public: 63 // types 64 typedef _UIntType result_type; 65 66 private: 67 result_type __x_[__r]; 68 result_type __c_; 69 size_t __i_; 70 71 static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits; 72 static_assert( 0 < __w, "subtract_with_carry_engine invalid parameters"); 73 static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters"); 74 static_assert( 0 < __s, "subtract_with_carry_engine invalid parameters"); 75 static_assert(__s < __r, "subtract_with_carry_engine invalid parameters"); 76 public: 77 static _LIBCPP_CONSTEXPR const result_type _Min = 0; 78 static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) : 79 (result_type(1) << __w) - result_type(1); 80 static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters"); 81 82 // engine characteristics 83 static _LIBCPP_CONSTEXPR const size_t word_size = __w; 84 static _LIBCPP_CONSTEXPR const size_t short_lag = __s; 85 static _LIBCPP_CONSTEXPR const size_t long_lag = __r; 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 static _LIBCPP_CONSTEXPR const result_type default_seed = 19780503u; 91 92 // constructors and seeding functions 93 #ifndef _LIBCPP_CXX03_LANG 94 _LIBCPP_INLINE_VISIBILITY 95 subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {} 96 _LIBCPP_INLINE_VISIBILITY 97 explicit subtract_with_carry_engine(result_type __sd) { seed(__sd); } 98 #else 99 _LIBCPP_INLINE_VISIBILITY 100 explicit subtract_with_carry_engine(result_type __sd = default_seed) { 101 seed(__sd); 102 } 103 #endif 104 template<class _Sseq> 105 _LIBCPP_INLINE_VISIBILITY 106 explicit subtract_with_carry_engine(_Sseq& __q, 107 typename enable_if<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value>::type* = 0) 108 {seed(__q);} 109 _LIBCPP_INLINE_VISIBILITY 110 void seed(result_type __sd = default_seed) 111 {seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());} 112 template<class _Sseq> 113 _LIBCPP_INLINE_VISIBILITY 114 typename enable_if 115 < 116 __is_seed_sequence<_Sseq, subtract_with_carry_engine>::value, 117 void 118 >::type 119 seed(_Sseq& __q) 120 {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());} 121 122 // generating functions 123 _LIBCPP_HIDE_FROM_ABI result_type operator()(); 124 _LIBCPP_INLINE_VISIBILITY 125 void discard(unsigned long long __z) {for (; __z; --__z) operator()();} 126 127 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 128 friend 129 bool 130 operator==( 131 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x, 132 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y); 133 134 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 135 friend 136 bool 137 operator!=( 138 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x, 139 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y); 140 141 template <class _CharT, class _Traits, 142 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 143 friend 144 basic_ostream<_CharT, _Traits>& 145 operator<<(basic_ostream<_CharT, _Traits>& __os, 146 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x); 147 148 template <class _CharT, class _Traits, 149 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 150 friend 151 basic_istream<_CharT, _Traits>& 152 operator>>(basic_istream<_CharT, _Traits>& __is, 153 subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x); 154 155 private: 156 157 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 1>); 158 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 2>); 159 template<class _Sseq> 160 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>); 161 template<class _Sseq> 162 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>); 163 }; 164 165 template<class _UIntType, size_t __w, size_t __s, size_t __r> 166 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size; 167 168 template<class _UIntType, size_t __w, size_t __s, size_t __r> 169 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag; 170 171 template<class _UIntType, size_t __w, size_t __s, size_t __r> 172 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::long_lag; 173 174 template<class _UIntType, size_t __w, size_t __s, size_t __r> 175 _LIBCPP_CONSTEXPR const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type 176 subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed; 177 178 template<class _UIntType, size_t __w, size_t __s, size_t __r> 179 void 180 subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, 181 integral_constant<unsigned, 1>) 182 { 183 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> 184 __e(__sd == 0u ? default_seed : __sd); 185 for (size_t __i = 0; __i < __r; ++__i) 186 __x_[__i] = static_cast<result_type>(__e() & _Max); 187 __c_ = __x_[__r-1] == 0; 188 __i_ = 0; 189 } 190 191 template<class _UIntType, size_t __w, size_t __s, size_t __r> 192 void 193 subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, 194 integral_constant<unsigned, 2>) 195 { 196 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> 197 __e(__sd == 0u ? default_seed : __sd); 198 for (size_t __i = 0; __i < __r; ++__i) 199 { 200 result_type __e0 = __e(); 201 __x_[__i] = static_cast<result_type>( 202 (__e0 + ((uint64_t)__e() << 32)) & _Max); 203 } 204 __c_ = __x_[__r-1] == 0; 205 __i_ = 0; 206 } 207 208 template<class _UIntType, size_t __w, size_t __s, size_t __r> 209 template<class _Sseq> 210 void 211 subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, 212 integral_constant<unsigned, 1>) 213 { 214 const unsigned __k = 1; 215 uint32_t __ar[__r * __k]; 216 __q.generate(__ar, __ar + __r * __k); 217 for (size_t __i = 0; __i < __r; ++__i) 218 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max); 219 __c_ = __x_[__r-1] == 0; 220 __i_ = 0; 221 } 222 223 template<class _UIntType, size_t __w, size_t __s, size_t __r> 224 template<class _Sseq> 225 void 226 subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, 227 integral_constant<unsigned, 2>) 228 { 229 const unsigned __k = 2; 230 uint32_t __ar[__r * __k]; 231 __q.generate(__ar, __ar + __r * __k); 232 for (size_t __i = 0; __i < __r; ++__i) 233 __x_[__i] = static_cast<result_type>( 234 (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max); 235 __c_ = __x_[__r-1] == 0; 236 __i_ = 0; 237 } 238 239 template<class _UIntType, size_t __w, size_t __s, size_t __r> 240 _UIntType 241 subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()() 242 { 243 const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r]; 244 result_type& __xr = __x_[__i_]; 245 result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1; 246 __xr = (__xs - __xr - __c_) & _Max; 247 __c_ = __new_c; 248 __i_ = (__i_ + 1) % __r; 249 return __xr; 250 } 251 252 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 253 _LIBCPP_HIDE_FROM_ABI bool 254 operator==( 255 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x, 256 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y) 257 { 258 if (__x.__c_ != __y.__c_) 259 return false; 260 if (__x.__i_ == __y.__i_) 261 return _VSTD::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_); 262 if (__x.__i_ == 0 || __y.__i_ == 0) 263 { 264 size_t __j = _VSTD::min(_Rp - __x.__i_, _Rp - __y.__i_); 265 if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j, 266 __y.__x_ + __y.__i_)) 267 return false; 268 if (__x.__i_ == 0) 269 return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_); 270 return _VSTD::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j); 271 } 272 if (__x.__i_ < __y.__i_) 273 { 274 size_t __j = _Rp - __y.__i_; 275 if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j), 276 __y.__x_ + __y.__i_)) 277 return false; 278 if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp, 279 __y.__x_)) 280 return false; 281 return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_, 282 __y.__x_ + (_Rp - (__x.__i_ + __j))); 283 } 284 size_t __j = _Rp - __x.__i_; 285 if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j), 286 __x.__x_ + __x.__i_)) 287 return false; 288 if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp, 289 __x.__x_)) 290 return false; 291 return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_, 292 __x.__x_ + (_Rp - (__y.__i_ + __j))); 293 } 294 295 template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 296 inline _LIBCPP_INLINE_VISIBILITY 297 bool 298 operator!=( 299 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x, 300 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y) 301 { 302 return !(__x == __y); 303 } 304 305 template <class _CharT, class _Traits, 306 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 307 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& 308 operator<<(basic_ostream<_CharT, _Traits>& __os, 309 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x) 310 { 311 __save_flags<_CharT, _Traits> __lx(__os); 312 typedef basic_ostream<_CharT, _Traits> _Ostream; 313 __os.flags(_Ostream::dec | _Ostream::left); 314 _CharT __sp = __os.widen(' '); 315 __os.fill(__sp); 316 __os << __x.__x_[__x.__i_]; 317 for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__j) 318 __os << __sp << __x.__x_[__j]; 319 for (size_t __j = 0; __j < __x.__i_; ++__j) 320 __os << __sp << __x.__x_[__j]; 321 __os << __sp << __x.__c_; 322 return __os; 323 } 324 325 template <class _CharT, class _Traits, 326 class _UInt, size_t _Wp, size_t _Sp, size_t _Rp> 327 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& 328 operator>>(basic_istream<_CharT, _Traits>& __is, 329 subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x) 330 { 331 __save_flags<_CharT, _Traits> __lx(__is); 332 typedef basic_istream<_CharT, _Traits> _Istream; 333 __is.flags(_Istream::dec | _Istream::skipws); 334 _UInt __t[_Rp+1]; 335 for (size_t __i = 0; __i < _Rp+1; ++__i) 336 __is >> __t[__i]; 337 if (!__is.fail()) 338 { 339 for (size_t __i = 0; __i < _Rp; ++__i) 340 __x.__x_[__i] = __t[__i]; 341 __x.__c_ = __t[_Rp]; 342 __x.__i_ = 0; 343 } 344 return __is; 345 } 346 347 _LIBCPP_END_NAMESPACE_STD 348 349 _LIBCPP_POP_MACROS 350 351 #endif // _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H 352