libcxx/include/__random/subtract_with_carry_engine.h

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