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