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 <__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