1 | /* boost random/seed_seq.hpp header file |
2 | * |
3 | * Copyright Steven Watanabe 2010 |
4 | * Distributed under the Boost Software License, Version 1.0. (See |
5 | * accompanying file LICENSE_1_0.txt or copy at |
6 | * http://www.boost.org/LICENSE_1_0.txt) |
7 | * |
8 | * See http://www.boost.org for most recent version including documentation. |
9 | * |
10 | * $Id$ |
11 | * |
12 | */ |
13 | |
14 | #ifndef BOOST_RANDOM_SEED_SEQ_HPP |
15 | #define BOOST_RANDOM_SEED_SEQ_HPP |
16 | |
17 | #include <boost/config.hpp> |
18 | #include <boost/cstdint.hpp> |
19 | #include <boost/range/begin.hpp> |
20 | #include <boost/range/end.hpp> |
21 | #include <cstddef> |
22 | #include <vector> |
23 | #include <algorithm> |
24 | #include <iterator> |
25 | |
26 | #ifndef BOOST_NO_CXX11_HDR_INITIALIZER_LIST |
27 | #include <initializer_list> |
28 | #endif |
29 | |
30 | namespace boost { |
31 | namespace random { |
32 | |
33 | /** |
34 | * The class @c seed_seq stores a sequence of 32-bit words |
35 | * for seeding a \pseudo_random_number_generator. These |
36 | * words will be combined to fill the entire state of the |
37 | * generator. |
38 | */ |
39 | class seed_seq { |
40 | public: |
41 | typedef boost::uint_least32_t result_type; |
42 | |
43 | /** Initializes a seed_seq to hold an empty sequence. */ |
44 | seed_seq() {} |
45 | #ifndef BOOST_NO_CXX11_HDR_INITIALIZER_LIST |
46 | /** Initializes the sequence from an initializer_list. */ |
47 | template<class T> |
48 | seed_seq(const std::initializer_list<T>& il) : v(il.begin(), il.end()) {} |
49 | #endif |
50 | /** Initializes the sequence from an iterator range. */ |
51 | template<class Iter> |
52 | seed_seq(Iter first, Iter last) : v(first, last) {} |
53 | /** Initializes the sequence from Boost.Range range. */ |
54 | template<class Range> |
55 | explicit seed_seq(const Range& range) |
56 | : v(boost::begin(range), boost::end(range)) {} |
57 | |
58 | /** |
59 | * Fills a range with 32-bit values based on the stored sequence. |
60 | * |
61 | * Requires: Iter must be a Random Access Iterator whose value type |
62 | * is an unsigned integral type at least 32 bits wide. |
63 | */ |
64 | template<class Iter> |
65 | void generate(Iter first, Iter last) const |
66 | { |
67 | typedef typename std::iterator_traits<Iter>::value_type value_type; |
68 | std::fill(first, last, static_cast<value_type>(0x8b8b8b8bu)); |
69 | std::size_t s = v.size(); |
70 | std::size_t n = last - first; |
71 | std::size_t t = |
72 | (n >= 623) ? 11 : |
73 | (n >= 68) ? 7 : |
74 | (n >= 39) ? 5 : |
75 | (n >= 7) ? 3 : |
76 | (n - 1)/2; |
77 | std::size_t p = (n - t) / 2; |
78 | std::size_t q = p + t; |
79 | std::size_t m = (std::max)(s+1, n); |
80 | value_type mask = 0xffffffffu; |
81 | for(std::size_t k = 0; k < m; ++k) { |
82 | value_type r1 = static_cast<value_type> |
83 | (*(first + k%n) ^ *(first + (k+p)%n) ^ *(first + (k+n-1)%n)); |
84 | r1 = r1 ^ (r1 >> 27); |
85 | r1 = (r1 * 1664525u) & mask; |
86 | value_type r2 = static_cast<value_type>(r1 + |
87 | ((k == 0) ? s : |
88 | (k <= s) ? k % n + v[k - 1] : |
89 | (k % n))); |
90 | *(first + (k+p)%n) = (*(first + (k+p)%n) + r1) & mask; |
91 | *(first + (k+q)%n) = (*(first + (k+q)%n) + r2) & mask; |
92 | *(first + k%n) = r2; |
93 | } |
94 | for(std::size_t k = m; k < m + n; ++k) { |
95 | value_type r3 = static_cast<value_type> |
96 | ((*(first + k%n) + *(first + (k+p)%n) + *(first + (k+n-1)%n)) |
97 | & mask); |
98 | r3 = r3 ^ (r3 >> 27); |
99 | r3 = (r3 * 1566083941u) & mask; |
100 | value_type r4 = static_cast<value_type>(r3 - k%m); |
101 | *(first + (k+p)%n) ^= r3; |
102 | *(first + (k+q)%n) ^= r4; |
103 | *(first + k%n) = r4; |
104 | } |
105 | } |
106 | /** Returns the size of the sequence. */ |
107 | std::size_t size() const { return v.size(); } |
108 | /** Writes the stored sequence to iter. */ |
109 | template<class Iter> |
110 | void param(Iter out) { std::copy(v.begin(), v.end(), out); } |
111 | private: |
112 | std::vector<result_type> v; |
113 | }; |
114 | |
115 | } |
116 | } |
117 | |
118 | #endif |
119 | |