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