blob: 073f84dccff6034de33462ff1722d4dae1f146e9 [file] [log] [blame]
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H
#define _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H
#include <__algorithm/equal.h>
#include <__algorithm/min.h>
#include <__config>
#include <__random/is_seed_sequence.h>
#include <__random/linear_congruential_engine.h>
#include <cstddef>
#include <cstdint>
#include <iosfwd>
#include <limits>
#include <type_traits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header
#endif
_LIBCPP_PUSH_MACROS
#include <__undef_macros>
_LIBCPP_BEGIN_NAMESPACE_STD
template<class _UIntType, size_t __w, size_t __s, size_t __r>
class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine;
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
bool
operator==(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
_LIBCPP_INLINE_VISIBILITY
bool
operator!=(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
template<class _UIntType, size_t __w, size_t __s, size_t __r>
class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine
{
public:
// types
typedef _UIntType result_type;
private:
result_type __x_[__r];
result_type __c_;
size_t __i_;
static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
static_assert( 0 < __w, "subtract_with_carry_engine invalid parameters");
static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters");
static_assert( 0 < __s, "subtract_with_carry_engine invalid parameters");
static_assert(__s < __r, "subtract_with_carry_engine invalid parameters");
public:
static _LIBCPP_CONSTEXPR const result_type _Min = 0;
static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
(result_type(1) << __w) - result_type(1);
static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");
// engine characteristics
static _LIBCPP_CONSTEXPR const size_t word_size = __w;
static _LIBCPP_CONSTEXPR const size_t short_lag = __s;
static _LIBCPP_CONSTEXPR const size_t long_lag = __r;
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
static _LIBCPP_CONSTEXPR const result_type default_seed = 19780503u;
// constructors and seeding functions
#ifndef _LIBCPP_CXX03_LANG
_LIBCPP_INLINE_VISIBILITY
subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {}
_LIBCPP_INLINE_VISIBILITY
explicit subtract_with_carry_engine(result_type __sd) { seed(__sd); }
#else
_LIBCPP_INLINE_VISIBILITY
explicit subtract_with_carry_engine(result_type __sd = default_seed) {
seed(__sd);
}
#endif
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
explicit subtract_with_carry_engine(_Sseq& __q,
typename enable_if<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value>::type* = 0)
{seed(__q);}
_LIBCPP_INLINE_VISIBILITY
void seed(result_type __sd = default_seed)
{seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
typename enable_if
<
__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value,
void
>::type
seed(_Sseq& __q)
{__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
// generating functions
result_type operator()();
_LIBCPP_INLINE_VISIBILITY
void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
friend
bool
operator==(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
friend
bool
operator!=(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
friend
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
friend
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
private:
void seed(result_type __sd, integral_constant<unsigned, 1>);
void seed(result_type __sd, integral_constant<unsigned, 2>);
template<class _Sseq>
void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
template<class _Sseq>
void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
};
template<class _UIntType, size_t __w, size_t __s, size_t __r>
_LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size;
template<class _UIntType, size_t __w, size_t __s, size_t __r>
_LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag;
template<class _UIntType, size_t __w, size_t __s, size_t __r>
_LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::long_lag;
template<class _UIntType, size_t __w, size_t __s, size_t __r>
_LIBCPP_CONSTEXPR const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type
subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed;
template<class _UIntType, size_t __w, size_t __s, size_t __r>
void
subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
integral_constant<unsigned, 1>)
{
linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
__e(__sd == 0u ? default_seed : __sd);
for (size_t __i = 0; __i < __r; ++__i)
__x_[__i] = static_cast<result_type>(__e() & _Max);
__c_ = __x_[__r-1] == 0;
__i_ = 0;
}
template<class _UIntType, size_t __w, size_t __s, size_t __r>
void
subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
integral_constant<unsigned, 2>)
{
linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
__e(__sd == 0u ? default_seed : __sd);
for (size_t __i = 0; __i < __r; ++__i)
{
result_type __e0 = __e();
__x_[__i] = static_cast<result_type>(
(__e0 + ((uint64_t)__e() << 32)) & _Max);
}
__c_ = __x_[__r-1] == 0;
__i_ = 0;
}
template<class _UIntType, size_t __w, size_t __s, size_t __r>
template<class _Sseq>
void
subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
integral_constant<unsigned, 1>)
{
const unsigned __k = 1;
uint32_t __ar[__r * __k];
__q.generate(__ar, __ar + __r * __k);
for (size_t __i = 0; __i < __r; ++__i)
__x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
__c_ = __x_[__r-1] == 0;
__i_ = 0;
}
template<class _UIntType, size_t __w, size_t __s, size_t __r>
template<class _Sseq>
void
subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
integral_constant<unsigned, 2>)
{
const unsigned __k = 2;
uint32_t __ar[__r * __k];
__q.generate(__ar, __ar + __r * __k);
for (size_t __i = 0; __i < __r; ++__i)
__x_[__i] = static_cast<result_type>(
(__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
__c_ = __x_[__r-1] == 0;
__i_ = 0;
}
template<class _UIntType, size_t __w, size_t __s, size_t __r>
_UIntType
subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()()
{
const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
result_type& __xr = __x_[__i_];
result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
__xr = (__xs - __xr - __c_) & _Max;
__c_ = __new_c;
__i_ = (__i_ + 1) % __r;
return __xr;
}
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
bool
operator==(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
{
if (__x.__c_ != __y.__c_)
return false;
if (__x.__i_ == __y.__i_)
return _VSTD::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_);
if (__x.__i_ == 0 || __y.__i_ == 0)
{
size_t __j = _VSTD::min(_Rp - __x.__i_, _Rp - __y.__i_);
if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
__y.__x_ + __y.__i_))
return false;
if (__x.__i_ == 0)
return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_);
return _VSTD::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j);
}
if (__x.__i_ < __y.__i_)
{
size_t __j = _Rp - __y.__i_;
if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
__y.__x_ + __y.__i_))
return false;
if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp,
__y.__x_))
return false;
return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
__y.__x_ + (_Rp - (__x.__i_ + __j)));
}
size_t __j = _Rp - __x.__i_;
if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
__x.__x_ + __x.__i_))
return false;
if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp,
__x.__x_))
return false;
return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
__x.__x_ + (_Rp - (__y.__i_ + __j)));
}
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
{
return !(__x == __y);
}
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
{
__save_flags<_CharT, _Traits> __lx(__os);
typedef basic_ostream<_CharT, _Traits> _Ostream;
__os.flags(_Ostream::dec | _Ostream::left);
_CharT __sp = __os.widen(' ');
__os.fill(__sp);
__os << __x.__x_[__x.__i_];
for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__j)
__os << __sp << __x.__x_[__j];
for (size_t __j = 0; __j < __x.__i_; ++__j)
__os << __sp << __x.__x_[__j];
__os << __sp << __x.__c_;
return __os;
}
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
{
__save_flags<_CharT, _Traits> __lx(__is);
typedef basic_istream<_CharT, _Traits> _Istream;
__is.flags(_Istream::dec | _Istream::skipws);
_UInt __t[_Rp+1];
for (size_t __i = 0; __i < _Rp+1; ++__i)
__is >> __t[__i];
if (!__is.fail())
{
for (size_t __i = 0; __i < _Rp; ++__i)
__x.__x_[__i] = __t[__i];
__x.__c_ = __t[_Rp];
__x.__i_ = 0;
}
return __is;
}
_LIBCPP_END_NAMESPACE_STD
_LIBCPP_POP_MACROS
#endif // _LIBCPP___RANDOM_SUBTRACT_WITH_CARRY_ENGINE_H