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