271 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___CXX03___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H10#define _LIBCPP___CXX03___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H11 12#include <__cxx03/__algorithm/equal.h>13#include <__cxx03/__algorithm/min.h>14#include <__cxx03/__config>15#include <__cxx03/__random/is_seed_sequence.h>16#include <__cxx03/__random/linear_congruential_engine.h>17#include <__cxx03/cstddef>18#include <__cxx03/cstdint>19#include <__cxx03/iosfwd>20#include <__cxx03/limits>21 22#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)23# pragma GCC system_header24#endif25 26_LIBCPP_PUSH_MACROS27#include <__cxx03/__undef_macros>28 29_LIBCPP_BEGIN_NAMESPACE_STD30 31template <class _UIntType, size_t __w, size_t __s, size_t __r>32class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine;33 34template <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 38template <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 42template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>43_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&44operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);45 46template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>47_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&48operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);49 50template <class _UIntType, size_t __w, size_t __s, size_t __r>51class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine {52public:53 // types54 typedef _UIntType result_type;55 56private:57 result_type __x_[__r];58 result_type __c_;59 size_t __i_;60 61 static 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 67public:68 static const result_type _Min = 0;69 static const result_type _Max = __w == _Dt ? result_type(~0) : (result_type(1) << __w) - result_type(1);70 static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");71 72 // engine characteristics73 static const size_t word_size = __w;74 static const size_t short_lag = __s;75 static const size_t long_lag = __r;76 _LIBCPP_HIDE_FROM_ABI static result_type min() { return _Min; }77 _LIBCPP_HIDE_FROM_ABI static result_type max() { return _Max; }78 static const result_type default_seed = 19780503u;79 80 // constructors and seeding functions81 _LIBCPP_HIDE_FROM_ABI explicit subtract_with_carry_engine(result_type __sd = default_seed) { seed(__sd); }82 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value, int> = 0>83 _LIBCPP_HIDE_FROM_ABI explicit subtract_with_carry_engine(_Sseq& __q) {84 seed(__q);85 }86 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd = default_seed) {87 seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());88 }89 template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value, int> = 0>90 _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) {91 __seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());92 }93 94 // generating functions95 _LIBCPP_HIDE_FROM_ABI result_type operator()();96 _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) {97 for (; __z; --__z)98 operator()();99 }100 101 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>102 friend bool operator==(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,103 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);104 105 template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>106 friend bool operator!=(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,107 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);108 109 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>110 friend basic_ostream<_CharT, _Traits>&111 operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);112 113 template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>114 friend basic_istream<_CharT, _Traits>&115 operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);116 117private:118 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 1>);119 _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd, integral_constant<unsigned, 2>);120 template <class _Sseq>121 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);122 template <class _Sseq>123 _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);124};125 126template <class _UIntType, size_t __w, size_t __s, size_t __r>127const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size;128 129template <class _UIntType, size_t __w, size_t __s, size_t __r>130const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag;131 132template <class _UIntType, size_t __w, size_t __s, size_t __r>133const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::long_lag;134 135template <class _UIntType, size_t __w, size_t __s, size_t __r>136const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type137 subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed;138 139template <class _UIntType, size_t __w, size_t __s, size_t __r>140void subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, integral_constant<unsigned, 1>) {141 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> __e(__sd == 0u ? default_seed : __sd);142 for (size_t __i = 0; __i < __r; ++__i)143 __x_[__i] = static_cast<result_type>(__e() & _Max);144 __c_ = __x_[__r - 1] == 0;145 __i_ = 0;146}147 148template <class _UIntType, size_t __w, size_t __s, size_t __r>149void subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, integral_constant<unsigned, 2>) {150 linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> __e(__sd == 0u ? default_seed : __sd);151 for (size_t __i = 0; __i < __r; ++__i) {152 result_type __e0 = __e();153 __x_[__i] = static_cast<result_type>((__e0 + ((uint64_t)__e() << 32)) & _Max);154 }155 __c_ = __x_[__r - 1] == 0;156 __i_ = 0;157}158 159template <class _UIntType, size_t __w, size_t __s, size_t __r>160template <class _Sseq>161void subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, integral_constant<unsigned, 1>) {162 const unsigned __k = 1;163 uint32_t __ar[__r * __k];164 __q.generate(__ar, __ar + __r * __k);165 for (size_t __i = 0; __i < __r; ++__i)166 __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);167 __c_ = __x_[__r - 1] == 0;168 __i_ = 0;169}170 171template <class _UIntType, size_t __w, size_t __s, size_t __r>172template <class _Sseq>173void subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, integral_constant<unsigned, 2>) {174 const unsigned __k = 2;175 uint32_t __ar[__r * __k];176 __q.generate(__ar, __ar + __r * __k);177 for (size_t __i = 0; __i < __r; ++__i)178 __x_[__i] = static_cast<result_type>((__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);179 __c_ = __x_[__r - 1] == 0;180 __i_ = 0;181}182 183template <class _UIntType, size_t __w, size_t __s, size_t __r>184_UIntType subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()() {185 const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];186 result_type& __xr = __x_[__i_];187 result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;188 __xr = (__xs - __xr - __c_) & _Max;189 __c_ = __new_c;190 __i_ = (__i_ + 1) % __r;191 return __xr;192}193 194template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>195_LIBCPP_HIDE_FROM_ABI bool operator==(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,196 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y) {197 if (__x.__c_ != __y.__c_)198 return false;199 if (__x.__i_ == __y.__i_)200 return std::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_);201 if (__x.__i_ == 0 || __y.__i_ == 0) {202 size_t __j = std::min(_Rp - __x.__i_, _Rp - __y.__i_);203 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j, __y.__x_ + __y.__i_))204 return false;205 if (__x.__i_ == 0)206 return std::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_);207 return std::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j);208 }209 if (__x.__i_ < __y.__i_) {210 size_t __j = _Rp - __y.__i_;211 if (!std::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j), __y.__x_ + __y.__i_))212 return false;213 if (!std::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp, __y.__x_))214 return false;215 return std::equal(__x.__x_, __x.__x_ + __x.__i_, __y.__x_ + (_Rp - (__x.__i_ + __j)));216 }217 size_t __j = _Rp - __x.__i_;218 if (!std::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j), __x.__x_ + __x.__i_))219 return false;220 if (!std::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp, __x.__x_))221 return false;222 return std::equal(__y.__x_, __y.__x_ + __y.__i_, __x.__x_ + (_Rp - (__y.__i_ + __j)));223}224 225template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>226inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,227 const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y) {228 return !(__x == __y);229}230 231template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>232_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&233operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x) {234 __save_flags<_CharT, _Traits> __lx(__os);235 typedef basic_ostream<_CharT, _Traits> _Ostream;236 __os.flags(_Ostream::dec | _Ostream::left);237 _CharT __sp = __os.widen(' ');238 __os.fill(__sp);239 __os << __x.__x_[__x.__i_];240 for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__j)241 __os << __sp << __x.__x_[__j];242 for (size_t __j = 0; __j < __x.__i_; ++__j)243 __os << __sp << __x.__x_[__j];244 __os << __sp << __x.__c_;245 return __os;246}247 248template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>249_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&250operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x) {251 __save_flags<_CharT, _Traits> __lx(__is);252 typedef basic_istream<_CharT, _Traits> _Istream;253 __is.flags(_Istream::dec | _Istream::skipws);254 _UInt __t[_Rp + 1];255 for (size_t __i = 0; __i < _Rp + 1; ++__i)256 __is >> __t[__i];257 if (!__is.fail()) {258 for (size_t __i = 0; __i < _Rp; ++__i)259 __x.__x_[__i] = __t[__i];260 __x.__c_ = __t[_Rp];261 __x.__i_ = 0;262 }263 return __is;264}265 266_LIBCPP_END_NAMESPACE_STD267 268_LIBCPP_POP_MACROS269 270#endif // _LIBCPP___CXX03___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H271