265 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___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H10#define _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H11 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_header25#endif26 27_LIBCPP_PUSH_MACROS28#include <__undef_macros>29 30_LIBCPP_BEGIN_NAMESPACE_STD31 32template <class _UIntType, size_t __w, size_t __s, size_t __r>33class subtract_with_carry_engine;34 35template <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 39template <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 43template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>44_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&45operator<<(basic_ostream<_CharT, _Traits>& __os, const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);46 47template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>48_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&49operator>>(basic_istream<_CharT, _Traits>& __is, subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);50 51template <class _UIntType, size_t __w, size_t __s, size_t __r>52class subtract_with_carry_engine {53public:54 // types55 typedef _UIntType result_type;56 57private: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 68public: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 characteristics75 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 functions83#ifndef _LIBCPP_CXX03_LANG84 _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#else87 _LIBCPP_HIDE_FROM_ABI explicit subtract_with_carry_engine(result_type __sd = default_seed) { seed(__sd); }88#endif89 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 functions102 _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 124private: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 133template <class _UIntType, size_t __w, size_t __s, size_t __r>134void 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 142template <class _UIntType, size_t __w, size_t __s, size_t __r>143void 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 153template <class _UIntType, size_t __w, size_t __s, size_t __r>154template <class _Sseq>155void 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 165template <class _UIntType, size_t __w, size_t __s, size_t __r>166template <class _Sseq>167void 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 177template <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 188template <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 219template <class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>220inline _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 225template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>226_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&227operator<<(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 242template <class _CharT, class _Traits, class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>243_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&244operator>>(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_STD261 262_LIBCPP_POP_MACROS263 264#endif // _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H265