boost/random/seed_seq.hpp

0001 /* boost random/seed_seq.hpp header file
0002  *
0003  * Copyright Steven Watanabe 2010
0004  * Distributed under the Boost Software License, Version 1.0. (See
0005  * accompanying file LICENSE_1_0.txt or copy at
0006  * http://www.boost.org/LICENSE_1_0.txt)
0007  *
0008  * See http://www.boost.org for most recent version including documentation.
0009  *
0010  * $Id$
0011  *
0012  */
0013
0014 #ifndef BOOST_RANDOM_SEED_SEQ_HPP
0015 #define BOOST_RANDOM_SEED_SEQ_HPP
0016
0017 #include <boost/config.hpp>
0018 #include <boost/cstdint.hpp>
0019 #include <boost/range/begin.hpp>
0020 #include <boost/range/end.hpp>
0021 #include <cstddef>
0022 #include <vector>
0023 #include <algorithm>
0024 #include <iterator>
0025
0026 #ifndef BOOST_NO_CXX11_HDR_INITIALIZER_LIST
0027 #include <initializer_list>
0028 #endif
0029
0030 namespace boost {
0031 namespace random {
0032
0033 /**
0034  * The class @c seed_seq stores a sequence of 32-bit words
0035  * for seeding a \pseudo_random_number_generator.  These
0036  * words will be combined to fill the entire state of the
0037  * generator.
0038  */
0039 class seed_seq {
0040 public:
0041     typedef boost::uint_least32_t result_type;
0042
0043     /** Initializes a seed_seq to hold an empty sequence. */
0044     seed_seq() {}
0045 #ifndef BOOST_NO_CXX11_HDR_INITIALIZER_LIST
0046     /** Initializes the sequence from an initializer_list. */
0047     template<class T>
0048     seed_seq(const std::initializer_list<T>& il) : v(il.begin(), il.end()) {}
0049 #endif
0050     /** Initializes the sequence from an iterator range. */
0051     template<class Iter>
0052     seed_seq(Iter first, Iter last) : v(first, last) {}
0053     /** Initializes the sequence from Boost.Range range. */
0054     template<class Range>
0055     explicit seed_seq(const Range& range)
0056       : v(boost::begin(range), boost::end(range)) {}
0057
0058     /**
0059      * Fills a range with 32-bit values based on the stored sequence.
0060      *
0061      * Requires: Iter must be a Random Access Iterator whose value type
0062      * is an unsigned integral type at least 32 bits wide.
0063      */
0064     template<class Iter>
0065     void generate(Iter first, Iter last) const
0066     {
0067         typedef typename std::iterator_traits<Iter>::value_type value_type;
0068         std::fill(first, last, static_cast<value_type>(0x8b8b8b8bu));
0069         std::size_t s = v.size();
0070         std::size_t n = last - first;
0071         std::size_t t =
0072             (n >= 623) ? 11 :
0073             (n >=  68) ?  7 :
0074             (n >=  39) ?  5 :
0075             (n >=   7) ?  3 :
0076             (n - 1)/2;
0077         std::size_t p = (n - t) / 2;
0078         std::size_t q = p + t;
0079         std::size_t m = (std::max)(s+1, n);
0080         value_type mask = 0xffffffffu;
0081         for(std::size_t k = 0; k < m; ++k) {
0082             value_type r1 = static_cast<value_type>
0083                 (*(first + k%n) ^ *(first + (k+p)%n) ^ *(first + (k+n-1)%n));
0084             r1 = r1 ^ (r1 >> 27);
0085             r1 = (r1 * 1664525u) & mask;
0086             value_type r2 = static_cast<value_type>(r1 +
0087                 ((k == 0) ? s :
0088                  (k <= s) ? k % n + v[k - 1] :
0089                  (k % n)));
0090             *(first + (k+p)%n) = (*(first + (k+p)%n) + r1) & mask;
0091             *(first + (k+q)%n) = (*(first + (k+q)%n) + r2) & mask;
0092             *(first + k%n) = r2;
0093         }
0094         for(std::size_t k = m; k < m + n; ++k) {
0095             value_type r3 = static_cast<value_type>
0096                 ((*(first + k%n) + *(first + (k+p)%n) + *(first + (k+n-1)%n))
0097                 & mask);
0098             r3 = r3 ^ (r3 >> 27);
0099             r3 = (r3 * 1566083941u) & mask;
0100             value_type r4 = static_cast<value_type>(r3 - k%n);
0101             *(first + (k+p)%n) ^= r3;
0102             *(first + (k+q)%n) ^= r4;
0103             *(first + k%n) = r4;
0104         }
0105     }
0106     /** Returns the size of the sequence. */
0107     std::size_t size() const { return v.size(); }
0108     /** Writes the stored sequence to iter. */
0109     template<class Iter>
0110     void param(Iter out) { std::copy(v.begin(), v.end(), out); }
0111 private:
0112     std::vector<result_type> v;
0113 };
0114
0115 }
0116 }
0117
0118 #endif