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