boost/random/seed_seq.hpp

   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: seed_seq.hpp 85813 2013-09-21 20:17:00Z jewillco $
  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 =
  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 = 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 =
  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 = 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