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