__cxx03/__random/subtract_with_carry_engine.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___CXX03___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H
0010 #define _LIBCPP___CXX03___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H
0011
0012 #include <__cxx03/__algorithm/equal.h>
0013 #include <__cxx03/__algorithm/min.h>
0014 #include <__cxx03/__config>
0015 #include <__cxx03/__random/is_seed_sequence.h>
0016 #include <__cxx03/__random/linear_congruential_engine.h>
0017 #include <__cxx03/cstddef>
0018 #include <__cxx03/cstdint>
0019 #include <__cxx03/iosfwd>
0020 #include <__cxx03/limits>
0021
0022 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0023 #  pragma GCC system_header
0024 #endif
0025
0026 _LIBCPP_PUSH_MACROS
0027 #include <__cxx03/__undef_macros>
0028
0029 _LIBCPP_BEGIN_NAMESPACE_STD
0030
0031 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0032 class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine;
0033
0034 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0035 _LIBCPP_HIDE_FROM_ABI bool operator==(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
0036                                       const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
0037
0038 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0039 _LIBCPP_HIDE_FROM_ABI bool operator!=(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
0040                                       const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
0041
0042 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0043 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
0044 operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
0045
0046 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0047 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
0048 operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
0049
0050 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0051 class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine {
0052 public:
0053   // types
0054   typedef _UIntType result_type;
0055
0056 private:
0057   result_type __x_[__r];
0058   result_type __c_;
0059   size_t __i_;
0060
0061   static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
0062   static_assert(0 < __w, "subtract_with_carry_engine invalid parameters");
0063   static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters");
0064   static_assert(0 < __s, "subtract_with_carry_engine invalid parameters");
0065   static_assert(__s < __r, "subtract_with_carry_engine invalid parameters");
0066
0067 public:
0068   static _LIBCPP_CONSTEXPR const result_type _Min = 0;
0069   static _LIBCPP_CONSTEXPR const result_type _Max =
0070       __w == _Dt ? result_type(~0) : (result_type(1) << __w) - result_type(1);
0071   static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");
0072
0073   // engine characteristics
0074   static _LIBCPP_CONSTEXPR const size_t word_size = __w;
0075   static _LIBCPP_CONSTEXPR const size_t short_lag = __s;
0076   static _LIBCPP_CONSTEXPR const size_t long_lag  = __r;
0077   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
0078   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
0079   static _LIBCPP_CONSTEXPR const result_type default_seed = 19780503u;
0080
0081   // constructors and seeding functions
0082 #ifndef _LIBCPP_CXX03_LANG
0083   _LIBCPP_HIDE_FROM_ABI subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {}
0084   _LIBCPP_HIDE_FROM_ABI explicit subtract_with_carry_engine(result_type __sd) { seed(__sd); }
0085 #else
0086   _LIBCPP_HIDE_FROM_ABI explicit subtract_with_carry_engine(result_type __sd = default_seed) { seed(__sd); }
0087 #endif
0088   template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value, int> = 0>
0089   _LIBCPP_HIDE_FROM_ABI explicit subtract_with_carry_engine(_Sseq& __q) {
0090     seed(__q);
0091   }
0092   _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd = default_seed) {
0093     seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());
0094   }
0095   template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value, int> = 0>
0096   _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) {
0097     __seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());
0098   }
0099
0100   // generating functions
0101   _LIBCPP_HIDE_FROM_ABI result_type operator()();
0102   _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) {
0103     for (; __z; --__z)
0104       operator()();
0105   }
0106
0107   template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0108   friend bool operator==(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
0109                          const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
0110
0111   template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0112   friend bool operator!=(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
0113                          const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
0114
0115   template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0116   friend basic_ostream<_CharT, _Traits>&
0117   operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
0118
0119   template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0120   friend basic_istream<_CharT, _Traits>&
0121   operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
0122
0123 private:
0124   _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 1>);
0125   _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 2>);
0126   template <class _Sseq>
0127   _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
0128   template <class _Sseq>
0129   _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
0130 };
0131
0132 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0133 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size;
0134
0135 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0136 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag;
0137
0138 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0139 _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::long_lag;
0140
0141 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0142 _LIBCPP_CONSTEXPR const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type
0143     subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed;
0144
0145 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0146 void subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, integral_constant<unsigned, 1>) {
0147   linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> __e(__sd == 0u ? default_seed : __sd);
0148   for (size_t __i = 0; __i < __r; ++__i)
0149     __x_[__i] = static_cast<result_type>(__e() & _Max);
0150   __c_ = __x_[__r - 1] == 0;
0151   __i_ = 0;
0152 }
0153
0154 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0155 void subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, integral_constant<unsigned, 2>) {
0156   linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> __e(__sd == 0u ? default_seed : __sd);
0157   for (size_t __i = 0; __i < __r; ++__i) {
0158     result_type __e0 = __e();
0159     __x_[__i]        = static_cast<result_type>((__e0 + ((uint64_t)__e() << 32)) & _Max);
0160   }
0161   __c_ = __x_[__r - 1] == 0;
0162   __i_ = 0;
0163 }
0164
0165 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0166 template <class _Sseq>
0167 void subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, integral_constant<unsigned, 1>) {
0168   const unsigned __k = 1;
0169   uint32_t __ar[__r * __k];
0170   __q.generate(__ar, __ar + __r * __k);
0171   for (size_t __i = 0; __i < __r; ++__i)
0172     __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
0173   __c_ = __x_[__r - 1] == 0;
0174   __i_ = 0;
0175 }
0176
0177 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0178 template <class _Sseq>
0179 void subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, integral_constant<unsigned, 2>) {
0180   const unsigned __k = 2;
0181   uint32_t __ar[__r * __k];
0182   __q.generate(__ar, __ar + __r * __k);
0183   for (size_t __i = 0; __i < __r; ++__i)
0184     __x_[__i] = static_cast<result_type>((__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
0185   __c_ = __x_[__r - 1] == 0;
0186   __i_ = 0;
0187 }
0188
0189 template <class _UIntType, size_t __w, size_t __s, size_t __r>
0190 _UIntType subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()() {
0191   const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
0192   result_type& __xr       = __x_[__i_];
0193   result_type __new_c     = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
0194   __xr                    = (__xs - __xr - __c_) & _Max;
0195   __c_                    = __new_c;
0196   __i_                    = (__i_ + 1) % __r;
0197   return __xr;
0198 }
0199
0200 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0201 _LIBCPP_HIDE_FROM_ABI bool operator==(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
0202                                       const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y) {
0203   if (__x.__c_ != __y.__c_)
0204     return false;
0205   if (__x.__i_ == __y.__i_)
0206     return std::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_);
0207   if (__x.__i_ == 0 || __y.__i_ == 0) {
0208     size_t __j = std::min(_Rp - __x.__i_, _Rp - __y.__i_);
0209     if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j, __y.__x_ + __y.__i_))
0210       return false;
0211     if (__x.__i_ == 0)
0212       return std::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_);
0213     return std::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j);
0214   }
0215   if (__x.__i_ < __y.__i_) {
0216     size_t __j = _Rp - __y.__i_;
0217     if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j), __y.__x_ + __y.__i_))
0218       return false;
0219     if (!std::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp, __y.__x_))
0220       return false;
0221     return std::equal(__x.__x_, __x.__x_ + __x.__i_, __y.__x_ + (_Rp - (__x.__i_ + __j)));
0222   }
0223   size_t __j = _Rp - __x.__i_;
0224   if (!std::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j), __x.__x_ + __x.__i_))
0225     return false;
0226   if (!std::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp, __x.__x_))
0227     return false;
0228   return std::equal(__y.__x_, __y.__x_ + __y.__i_, __x.__x_ + (_Rp - (__y.__i_ + __j)));
0229 }
0230
0231 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0232 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
0233                                              const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y) {
0234   return !(__x == __y);
0235 }
0236
0237 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0238 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
0239 operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x) {
0240   __save_flags<_CharT, _Traits> __lx(__os);
0241   typedef basic_ostream<_CharT, _Traits> _Ostream;
0242   __os.flags(_Ostream::dec | _Ostream::left);
0243   _CharT __sp = __os.widen(' ');
0244   __os.fill(__sp);
0245   __os << __x.__x_[__x.__i_];
0246   for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__j)
0247     __os << __sp << __x.__x_[__j];
0248   for (size_t __j = 0; __j < __x.__i_; ++__j)
0249     __os << __sp << __x.__x_[__j];
0250   __os << __sp << __x.__c_;
0251   return __os;
0252 }
0253
0254 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
0255 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
0256 operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x) {
0257   __save_flags<_CharT, _Traits> __lx(__is);
0258   typedef basic_istream<_CharT, _Traits> _Istream;
0259   __is.flags(_Istream::dec | _Istream::skipws);
0260   _UInt __t[_Rp + 1];
0261   for (size_t __i = 0; __i < _Rp + 1; ++__i)
0262     __is >> __t[__i];
0263   if (!__is.fail()) {
0264     for (size_t __i = 0; __i < _Rp; ++__i)
0265       __x.__x_[__i] = __t[__i];
0266     __x.__c_ = __t[_Rp];
0267     __x.__i_ = 0;
0268   }
0269   return __is;
0270 }
0271
0272 _LIBCPP_END_NAMESPACE_STD
0273
0274 _LIBCPP_POP_MACROS
0275
0276 #endif // _LIBCPP___CXX03___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H