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