diff options
Diffstat (limited to 'contrib/llvm-project/libcxx/include/__random/linear_congruential_engine.h')
| -rw-r--r-- | contrib/llvm-project/libcxx/include/__random/linear_congruential_engine.h | 387 |
1 files changed, 387 insertions, 0 deletions
diff --git a/contrib/llvm-project/libcxx/include/__random/linear_congruential_engine.h b/contrib/llvm-project/libcxx/include/__random/linear_congruential_engine.h new file mode 100644 index 000000000000..9d77649e9cfc --- /dev/null +++ b/contrib/llvm-project/libcxx/include/__random/linear_congruential_engine.h @@ -0,0 +1,387 @@ +//===----------------------------------------------------------------------===// +// +// 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_LINEAR_CONGRUENTIAL_ENGINE_H +#define _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H + +#include <__config> +#include <__random/is_seed_sequence.h> +#include <__type_traits/enable_if.h> +#include <__type_traits/integral_constant.h> +#include <__type_traits/is_unsigned.h> +#include <cstdint> +#include <iosfwd> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +enum __lce_alg_type { + _LCE_Full, + _LCE_Part, + _LCE_Schrage, + _LCE_Promote, +}; + +template <unsigned long long __a, + unsigned long long __c, + unsigned long long __m, + unsigned long long _Mp, + bool _HasOverflow = (__a != 0ull && (__m & (__m - 1ull)) != 0ull), // a != 0, m != 0, m != 2^n + bool _Full = (!_HasOverflow || __m - 1ull <= (_Mp - __c) / __a), // (a * x + c) % m works + bool _Part = (!_HasOverflow || __m - 1ull <= _Mp / __a), // (a * x) % m works + bool _Schrage = (_HasOverflow && __m % __a <= __m / __a)> // r <= q +struct __lce_alg_picker { + static _LIBCPP_CONSTEXPR const __lce_alg_type __mode = + _Full ? _LCE_Full + : _Part ? _LCE_Part + : _Schrage ? _LCE_Schrage + : _LCE_Promote; + +#ifdef _LIBCPP_HAS_NO_INT128 + static_assert(_Mp != (unsigned long long)(-1) || _Full || _Part || _Schrage, + "The current values for a, c, and m are not currently supported on platforms without __int128"); +#endif +}; + +template <unsigned long long __a, + unsigned long long __c, + unsigned long long __m, + unsigned long long _Mp, + __lce_alg_type _Mode = __lce_alg_picker<__a, __c, __m, _Mp>::__mode> +struct __lce_ta; + +// 64 + +#ifndef _LIBCPP_HAS_NO_INT128 +template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> +struct __lce_ta<_Ap, _Cp, _Mp, (unsigned long long)(-1), _LCE_Promote> { + typedef unsigned long long result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __xp) { + __extension__ using __calc_type = unsigned __int128; + const __calc_type __a = static_cast<__calc_type>(_Ap); + const __calc_type __c = static_cast<__calc_type>(_Cp); + const __calc_type __m = static_cast<__calc_type>(_Mp); + const __calc_type __x = static_cast<__calc_type>(__xp); + return static_cast<result_type>((__a * __x + __c) % __m); + } +}; +#endif + +template <unsigned long long __a, unsigned long long __c, unsigned long long __m> +struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Schrage> { + typedef unsigned long long result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + // Schrage's algorithm + const result_type __q = __m / __a; + const result_type __r = __m % __a; + const result_type __t0 = __a * (__x % __q); + const result_type __t1 = __r * (__x / __q); + __x = __t0 + (__t0 < __t1) * __m - __t1; + __x += __c - (__x >= __m - __c) * __m; + return __x; + } +}; + +template <unsigned long long __a, unsigned long long __m> +struct __lce_ta<__a, 0ull, __m, (unsigned long long)(-1), _LCE_Schrage> { + typedef unsigned long long result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + // Schrage's algorithm + const result_type __q = __m / __a; + const result_type __r = __m % __a; + const result_type __t0 = __a * (__x % __q); + const result_type __t1 = __r * (__x / __q); + __x = __t0 + (__t0 < __t1) * __m - __t1; + return __x; + } +}; + +template <unsigned long long __a, unsigned long long __c, unsigned long long __m> +struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Part> { + typedef unsigned long long result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + // Use (((a*x) % m) + c) % m + __x = (__a * __x) % __m; + __x += __c - (__x >= __m - __c) * __m; + return __x; + } +}; + +template <unsigned long long __a, unsigned long long __c, unsigned long long __m> +struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Full> { + typedef unsigned long long result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return (__a * __x + __c) % __m; } +}; + +template <unsigned long long __a, unsigned long long __c> +struct __lce_ta<__a, __c, 0ull, (unsigned long long)(-1), _LCE_Full> { + typedef unsigned long long result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return __a * __x + __c; } +}; + +// 32 + +template <unsigned long long __a, unsigned long long __c, unsigned long long __m> +struct __lce_ta<__a, __c, __m, unsigned(-1), _LCE_Promote> { + typedef unsigned result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + return static_cast<result_type>(__lce_ta<__a, __c, __m, (unsigned long long)(-1)>::next(__x)); + } +}; + +template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> +struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Schrage> { + typedef unsigned result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + const result_type __a = static_cast<result_type>(_Ap); + const result_type __c = static_cast<result_type>(_Cp); + const result_type __m = static_cast<result_type>(_Mp); + // Schrage's algorithm + const result_type __q = __m / __a; + const result_type __r = __m % __a; + const result_type __t0 = __a * (__x % __q); + const result_type __t1 = __r * (__x / __q); + __x = __t0 + (__t0 < __t1) * __m - __t1; + __x += __c - (__x >= __m - __c) * __m; + return __x; + } +}; + +template <unsigned long long _Ap, unsigned long long _Mp> +struct __lce_ta<_Ap, 0ull, _Mp, unsigned(-1), _LCE_Schrage> { + typedef unsigned result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + const result_type __a = static_cast<result_type>(_Ap); + const result_type __m = static_cast<result_type>(_Mp); + // Schrage's algorithm + const result_type __q = __m / __a; + const result_type __r = __m % __a; + const result_type __t0 = __a * (__x % __q); + const result_type __t1 = __r * (__x / __q); + __x = __t0 + (__t0 < __t1) * __m - __t1; + return __x; + } +}; + +template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> +struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Part> { + typedef unsigned result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + const result_type __a = static_cast<result_type>(_Ap); + const result_type __c = static_cast<result_type>(_Cp); + const result_type __m = static_cast<result_type>(_Mp); + // Use (((a*x) % m) + c) % m + __x = (__a * __x) % __m; + __x += __c - (__x >= __m - __c) * __m; + return __x; + } +}; + +template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> +struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Full> { + typedef unsigned result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + const result_type __a = static_cast<result_type>(_Ap); + const result_type __c = static_cast<result_type>(_Cp); + const result_type __m = static_cast<result_type>(_Mp); + return (__a * __x + __c) % __m; + } +}; + +template <unsigned long long _Ap, unsigned long long _Cp> +struct __lce_ta<_Ap, _Cp, 0ull, unsigned(-1), _LCE_Full> { + typedef unsigned result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + const result_type __a = static_cast<result_type>(_Ap); + const result_type __c = static_cast<result_type>(_Cp); + return __a * __x + __c; + } +}; + +// 16 + +template <unsigned long long __a, unsigned long long __c, unsigned long long __m, __lce_alg_type __mode> +struct __lce_ta<__a, __c, __m, (unsigned short)(-1), __mode> { + typedef unsigned short result_type; + _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { + return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(-1)>::next(__x)); + } +}; + +template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +class _LIBCPP_TEMPLATE_VIS linear_congruential_engine; + +template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> +_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& +operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&); + +template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> +_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& +operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x); + +template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +class _LIBCPP_TEMPLATE_VIS linear_congruential_engine { +public: + // types + typedef _UIntType result_type; + +private: + result_type __x_; + + static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(-1); + + static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters"); + static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters"); + static_assert(is_unsigned<_UIntType>::value, "_UIntType must be unsigned type"); + +public: + static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u : 0u; + static _LIBCPP_CONSTEXPR const result_type _Max = __m - _UIntType(1u); + static_assert(_Min < _Max, "linear_congruential_engine invalid parameters"); + + // engine characteristics + static _LIBCPP_CONSTEXPR const result_type multiplier = __a; + static _LIBCPP_CONSTEXPR const result_type increment = __c; + static _LIBCPP_CONSTEXPR const result_type modulus = __m; + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type min() { return _Min; } + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type max() { return _Max; } + static _LIBCPP_CONSTEXPR const result_type default_seed = 1u; + + // constructors and seeding functions +#ifndef _LIBCPP_CXX03_LANG + _LIBCPP_HIDE_FROM_ABI linear_congruential_engine() : linear_congruential_engine(default_seed) {} + _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s) { seed(__s); } +#else + _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s = default_seed) { seed(__s); } +#endif + template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(_Sseq& __q) { + seed(__q); + } + _LIBCPP_HIDE_FROM_ABI void seed(result_type __s = default_seed) { + seed(integral_constant<bool, __m == 0>(), integral_constant<bool, __c == 0>(), __s); + } + template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) { + __seed( + __q, + integral_constant<unsigned, + 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1) / 32 : (__m > 0x100000000ull))>()); + } + + // generating functions + _LIBCPP_HIDE_FROM_ABI result_type operator()() { + return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_)); + } + _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) { + for (; __z; --__z) + operator()(); + } + + friend _LIBCPP_HIDE_FROM_ABI bool + operator==(const linear_congruential_engine& __x, const linear_congruential_engine& __y) { + return __x.__x_ == __y.__x_; + } + friend _LIBCPP_HIDE_FROM_ABI bool + operator!=(const linear_congruential_engine& __x, const linear_congruential_engine& __y) { + return !(__x == __y); + } + +private: + _LIBCPP_HIDE_FROM_ABI void seed(true_type, true_type, result_type __s) { __x_ = __s == 0 ? 1 : __s; } + _LIBCPP_HIDE_FROM_ABI void seed(true_type, false_type, result_type __s) { __x_ = __s; } + _LIBCPP_HIDE_FROM_ABI void seed(false_type, true_type, result_type __s) { __x_ = __s % __m == 0 ? 1 : __s % __m; } + _LIBCPP_HIDE_FROM_ABI void seed(false_type, false_type, result_type __s) { __x_ = __s % __m; } + + template <class _Sseq> + _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>); + template <class _Sseq> + _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>); + + template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> + friend basic_ostream<_CharT, _Traits>& + operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&); + + template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> + friend basic_istream<_CharT, _Traits>& + operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x); +}; + +template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type + linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier; + +template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type + linear_congruential_engine<_UIntType, __a, __c, __m>::increment; + +template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type + linear_congruential_engine<_UIntType, __a, __c, __m>::modulus; + +template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type + linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed; + +template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +template <class _Sseq> +void linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, integral_constant<unsigned, 1>) { + const unsigned __k = 1; + uint32_t __ar[__k + 3]; + __q.generate(__ar, __ar + __k + 3); + result_type __s = static_cast<result_type>(__ar[3] % __m); + __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; +} + +template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +template <class _Sseq> +void linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, integral_constant<unsigned, 2>) { + const unsigned __k = 2; + uint32_t __ar[__k + 3]; + __q.generate(__ar, __ar + __k + 3); + result_type __s = static_cast<result_type>((__ar[3] + ((uint64_t)__ar[4] << 32)) % __m); + __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; +} + +template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +inline _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& +operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_UIntType, __a, __c, __m>& __x) { + __save_flags<_CharT, _Traits> __lx(__os); + typedef basic_ostream<_CharT, _Traits> _Ostream; + __os.flags(_Ostream::dec | _Ostream::left); + __os.fill(__os.widen(' ')); + return __os << __x.__x_; +} + +template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> +_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& +operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_UIntType, __a, __c, __m>& __x) { + __save_flags<_CharT, _Traits> __lx(__is); + typedef basic_istream<_CharT, _Traits> _Istream; + __is.flags(_Istream::dec | _Istream::skipws); + _UIntType __t; + __is >> __t; + if (!__is.fail()) + __x.__x_ = __t; + return __is; +} + +typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> minstd_rand0; +typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> minstd_rand; + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H |