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