| 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___CXX03___RANDOM_SEED_SEQ_H |
| 10 |
#define _LIBCPP___CXX03___RANDOM_SEED_SEQ_H |
| 11 |
|
| 12 |
#include <__cxx03/__algorithm/copy.h> |
| 13 |
#include <__cxx03/__algorithm/fill.h> |
| 14 |
#include <__cxx03/__algorithm/max.h> |
| 15 |
#include <__cxx03/__config> |
| 16 |
#include <__cxx03/__iterator/iterator_traits.h> |
| 17 |
#include <__cxx03/__type_traits/is_unsigned.h> |
| 18 |
#include <__cxx03/cstdint> |
| 19 |
#include <__cxx03/vector> |
| 20 |
|
| 21 |
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
| 22 |
# pragma GCC system_header |
| 23 |
#endif |
| 24 |
|
| 25 |
_LIBCPP_PUSH_MACROS |
| 26 |
#include <__cxx03/__undef_macros> |
| 27 |
|
| 28 |
_LIBCPP_BEGIN_NAMESPACE_STD |
| 29 |
|
| 30 |
class _LIBCPP_TEMPLATE_VIS seed_seq { |
| 31 |
public: |
| 32 |
// types |
| 33 |
typedef uint32_t result_type; |
| 34 |
|
| 35 |
// constructors |
| 36 |
_LIBCPP_HIDE_FROM_ABI seed_seq() _NOEXCEPT {} |
| 37 |
|
| 38 |
template <class _InputIterator> |
| 39 |
_LIBCPP_HIDE_FROM_ABI seed_seq(_InputIterator __first, _InputIterator __last) { |
| 40 |
static_assert(is_integral<typename iterator_traits<_InputIterator>::value_type>::value, |
| 41 |
"Mandates: iterator_traits<InputIterator>::value_type is an integer type"); |
| 42 |
__init(__first, __last); |
| 43 |
} |
| 44 |
|
| 45 |
// generating functions |
| 46 |
template <class _RandomAccessIterator> |
| 47 |
_LIBCPP_HIDE_FROM_ABI void generate(_RandomAccessIterator __first, _RandomAccessIterator __last); |
| 48 |
|
| 49 |
// property functions |
| 50 |
_LIBCPP_HIDE_FROM_ABI size_t size() const _NOEXCEPT { return __v_.size(); } |
| 51 |
template <class _OutputIterator> |
| 52 |
_LIBCPP_HIDE_FROM_ABI void param(_OutputIterator __dest) const { |
| 53 |
std::copy(__v_.begin(), __v_.end(), __dest); |
| 54 |
} |
| 55 |
|
| 56 |
seed_seq(const seed_seq&) = delete; |
| 57 |
void operator=(const seed_seq&) = delete; |
| 58 |
|
| 59 |
_LIBCPP_HIDE_FROM_ABI static result_type _Tp(result_type __x) { return __x ^ (__x >> 27); } |
| 60 |
|
| 61 |
private: |
| 62 |
template <class _InputIterator> |
| 63 |
_LIBCPP_HIDE_FROM_ABI void __init(_InputIterator __first, _InputIterator __last); |
| 64 |
|
| 65 |
vector<result_type> __v_; |
| 66 |
}; |
| 67 |
|
| 68 |
template <class _InputIterator> |
| 69 |
void seed_seq::__init(_InputIterator __first, _InputIterator __last) { |
| 70 |
for (_InputIterator __s = __first; __s != __last; ++__s) |
| 71 |
__v_.push_back(*__s & 0xFFFFFFFF); |
| 72 |
} |
| 73 |
|
| 74 |
template <class _RandomAccessIterator> |
| 75 |
void seed_seq::generate(_RandomAccessIterator __first, _RandomAccessIterator __last) { |
| 76 |
using _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type; |
| 77 |
static_assert(is_unsigned<_ValueType>::value && sizeof(_ValueType) >= sizeof(uint32_t), |
| 78 |
"[rand.util.seedseq]/7 requires the value_type of the iterator to be an unsigned " |
| 79 |
"integer capable of accommodating 32-bit quantities."); |
| 80 |
|
| 81 |
if (__first != __last) { |
| 82 |
std::fill(__first, __last, 0x8b8b8b8b); |
| 83 |
const size_t __n = static_cast<size_t>(__last - __first); |
| 84 |
const size_t __s = __v_.size(); |
| 85 |
const size_t __t = (__n >= 623) ? 11 : (__n >= 68) ? 7 : (__n >= 39) ? 5 : (__n >= 7) ? 3 : (__n - 1) / 2; |
| 86 |
const size_t __p = (__n - __t) / 2; |
| 87 |
const size_t __q = __p + __t; |
| 88 |
const size_t __m = std::max(__s + 1, __n); |
| 89 |
// __k = 0; |
| 90 |
{ |
| 91 |
result_type __r = 1664525 * _Tp(__first[0] ^ __first[__p] ^ __first[__n - 1]); |
| 92 |
__first[__p] += __r; |
| 93 |
__r += __s; |
| 94 |
__first[__q] += __r; |
| 95 |
__first[0] = __r; |
| 96 |
} |
| 97 |
// Initialize indexing terms used with if statements as an optimization to |
| 98 |
// avoid calculating modulo n on every loop iteration for each term. |
| 99 |
size_t __kmodn = 0; // __k % __n |
| 100 |
size_t __k1modn = __n - 1; // (__k - 1) % __n |
| 101 |
size_t __kpmodn = __p % __n; // (__k + __p) % __n |
| 102 |
size_t __kqmodn = __q % __n; // (__k + __q) % __n |
| 103 |
|
| 104 |
for (size_t __k = 1; __k <= __s; ++__k) { |
| 105 |
if (++__kmodn == __n) |
| 106 |
__kmodn = 0; |
| 107 |
if (++__k1modn == __n) |
| 108 |
__k1modn = 0; |
| 109 |
if (++__kpmodn == __n) |
| 110 |
__kpmodn = 0; |
| 111 |
if (++__kqmodn == __n) |
| 112 |
__kqmodn = 0; |
| 113 |
|
| 114 |
result_type __r = 1664525 * _Tp(__first[__kmodn] ^ __first[__kpmodn] ^ __first[__k1modn]); |
| 115 |
__first[__kpmodn] += __r; |
| 116 |
__r += __kmodn + __v_[__k - 1]; |
| 117 |
__first[__kqmodn] += __r; |
| 118 |
__first[__kmodn] = __r; |
| 119 |
} |
| 120 |
for (size_t __k = __s + 1; __k < __m; ++__k) { |
| 121 |
if (++__kmodn == __n) |
| 122 |
__kmodn = 0; |
| 123 |
if (++__k1modn == __n) |
| 124 |
__k1modn = 0; |
| 125 |
if (++__kpmodn == __n) |
| 126 |
__kpmodn = 0; |
| 127 |
if (++__kqmodn == __n) |
| 128 |
__kqmodn = 0; |
| 129 |
|
| 130 |
result_type __r = 1664525 * _Tp(__first[__kmodn] ^ __first[__kpmodn] ^ __first[__k1modn]); |
| 131 |
__first[__kpmodn] += __r; |
| 132 |
__r += __kmodn; |
| 133 |
__first[__kqmodn] += __r; |
| 134 |
__first[__kmodn] = __r; |
| 135 |
} |
| 136 |
for (size_t __k = __m; __k < __m + __n; ++__k) { |
| 137 |
if (++__kmodn == __n) |
| 138 |
__kmodn = 0; |
| 139 |
if (++__k1modn == __n) |
| 140 |
__k1modn = 0; |
| 141 |
if (++__kpmodn == __n) |
| 142 |
__kpmodn = 0; |
| 143 |
if (++__kqmodn == __n) |
| 144 |
__kqmodn = 0; |
| 145 |
|
| 146 |
result_type __r = 1566083941 * _Tp(__first[__kmodn] + __first[__kpmodn] + __first[__k1modn]); |
| 147 |
__first[__kpmodn] ^= __r; |
| 148 |
__r -= __kmodn; |
| 149 |
__first[__kqmodn] ^= __r; |
| 150 |
__first[__kmodn] = __r; |
| 151 |
} |
| 152 |
} |
| 153 |
} |
| 154 |
|
| 155 |
_LIBCPP_END_NAMESPACE_STD |
| 156 |
|
| 157 |
_LIBCPP_POP_MACROS |
| 158 |
|
| 159 |
#endif // _LIBCPP___CXX03___RANDOM_SEED_SEQ_H |