ceph/src/boost/boost/random/independent_bits.hpp

   1 /* boost random/independent_bits.hpp header file
   2  *
   3  * Copyright Steven Watanabe 2011
   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_INDEPENDENT_BITS_HPP
  15 #define BOOST_RANDOM_INDEPENDENT_BITS_HPP
  16
  17 #include <istream>
  18 #include <iosfwd>
  19 #include <boost/assert.hpp>
  20 #include <boost/limits.hpp>
  21 #include <boost/config.hpp>
  22 #include <boost/cstdint.hpp>
  23 #include <boost/integer/integer_mask.hpp>
  24 #include <boost/random/traits.hpp>
  25 #include <boost/random/detail/config.hpp>
  26 #include <boost/random/detail/integer_log2.hpp>
  27 #include <boost/random/detail/operators.hpp>
  28 #include <boost/random/detail/seed.hpp>
  29 #include <boost/random/detail/seed_impl.hpp>
  30 #include <boost/random/detail/signed_unsigned_tools.hpp>
  31
  32 namespace boost {
  33 namespace random {
  34
  35 /**
  36  * An instantiation of class template @c independent_bits_engine
  37  * model a \pseudo_random_number_generator.  It generates random
  38  * numbers distributed between [0, 2^w) by combining one or
  39  * more invocations of the base engine.
  40  *
  41  * Requires: 0 < w <= std::numeric_limits<UIntType>::digits
  42  */
  43 template<class Engine, std::size_t w, class UIntType>
  44 class independent_bits_engine
  45 {
  46 public:
  47     typedef Engine base_type;
  48     typedef UIntType result_type;
  49     typedef typename Engine::result_type base_result_type;
  50
  51     // Required by old Boost.Random concept
  52     BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
  53
  54     /** Returns the smallest value that the generator can produce. */
  55     static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION ()
  56     { return 0; }
  57     /** Returns the largest value that the generator can produce. */
  58     static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
  59     { return max_imp(boost::is_integral<UIntType>()); }
  60
  61     /**
  62      * Constructs an @c independent_bits_engine using the
  63      * default constructor of the base generator.
  64      */
  65     independent_bits_engine() { }
  66
  67     /**
  68      * Constructs an @c independent_bits_engine, using seed as
  69      * the constructor argument for both base generators.
  70      */
  71     BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(independent_bits_engine,
  72         base_result_type, seed_arg)
  73     {
  74         _base.seed(seed_arg);
  75     }
  76
  77     /**
  78      * Constructs an @c independent_bits_engine, using seq as
  79      * the constructor argument for the base generator.
  80      */
  81     BOOST_RANDOM_DETAIL_SEED_SEQ_CONSTRUCTOR(independent_bits_engine,
  82         SeedSeq, seq)
  83     { _base.seed(seq); }
  84
  85     /** Constructs an @c independent_bits_engine by copying @c base. */
  86     independent_bits_engine(const base_type& base_arg) : _base(base_arg) {}
  87
  88     /**
  89      * Contructs an @c independent_bits_engine with
  90      * values from the range defined by the input iterators first
  91      * and last.  first will be modified to point to the element
  92      * after the last one used.
  93      *
  94      * Throws: @c std::invalid_argument if the input range is too small.
  95      *
  96      * Exception Safety: Basic
  97      */
  98     template<class It>
  99     independent_bits_engine(It& first, It last) : _base(first, last) { }
 100
 101     /**
 102      * Seeds an @c independent_bits_engine using the default
 103      * seed of the base generator.
 104      */
 105     void seed() { _base.seed(); }
 106
 107     /**
 108      * Seeds an @c independent_bits_engine, using @c seed as the
 109      * seed for the base generator.
 110      */
 111     BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(independent_bits_engine,
 112         base_result_type, seed_arg)
 113     { _base.seed(seed_arg); }
 114
 115     /**
 116      * Seeds an @c independent_bits_engine, using @c seq to
 117      * seed the base generator.
 118      */
 119     BOOST_RANDOM_DETAIL_SEED_SEQ_SEED(independent_bits_engine,
 120         SeedSeq, seq)
 121     { _base.seed(seq); }
 122
 123     /**
 124      * Seeds an @c independent_bits_engine with
 125      * values from the range defined by the input iterators first
 126      * and last.  first will be modified to point to the element
 127      * after the last one used.
 128      *
 129      * Throws: @c std::invalid_argument if the input range is too small.
 130      *
 131      * Exception Safety: Basic
 132      */
 133     template<class It> void seed(It& first, It last)
 134     { _base.seed(first, last); }
 135
 136     /** Returns the next value of the generator. */
 137     result_type operator()()
 138     {
 139         // While it may seem wasteful to recalculate this
 140         // every time, both msvc and gcc can propagate
 141         // constants, resolving this at compile time.
 142         base_unsigned range =
 143             detail::subtract<base_result_type>()((_base.max)(), (_base.min)());
 144         std::size_t m =
 145             (range == (std::numeric_limits<base_unsigned>::max)()) ?
 146                 std::numeric_limits<base_unsigned>::digits :
 147                 detail::integer_log2(range + 1);
 148         std::size_t n = (w + m - 1) / m;
 149         std::size_t w0, n0;
 150         base_unsigned y0, y1;
 151         base_unsigned y0_mask, y1_mask;
 152         calc_params(n, range, w0, n0, y0, y1, y0_mask, y1_mask);
 153         if(base_unsigned(range - y0 + 1) > y0 / n) {
 154             // increment n and try again.
 155             ++n;
 156             calc_params(n, range, w0, n0, y0, y1, y0_mask, y1_mask);
 157         }
 158
 159         BOOST_ASSERT(n0*w0 + (n - n0)*(w0 + 1) == w);
 160
 161         BOOST_ASSERT((n == 1) == (w0 == w));
 162
 163         // special case to avoid undefined behavior from shifting
 164         if(n == 1) {
 165             BOOST_ASSERT(n0 == 1);
 166             base_unsigned u;
 167             do {
 168                 u = detail::subtract<base_result_type>()(_base(), (_base.min)());
 169             } while(u > base_unsigned(y0 - 1));
 170             return u & y0_mask;
 171         }
 172
 173         result_type S = 0;
 174         for(std::size_t k = 0; k < n0; ++k) {
 175             base_unsigned u;
 176             do {
 177                 u = detail::subtract<base_result_type>()(_base(), (_base.min)());
 178             } while(u > base_unsigned(y0 - 1));
 179             S = (S << w0) + (u & y0_mask);
 180         }
 181         for(std::size_t k = 0; k < (n - n0); ++k) {
 182             base_unsigned u;
 183             do {
 184                 u = detail::subtract<base_result_type>()(_base(), (_base.min)());
 185             } while(u > base_unsigned(y1 - 1));
 186             S = (S << (w0 + 1)) + (u & y1_mask);
 187         }
 188         return S;
 189     }
 190
 191     /** Fills a range with random values */
 192     template<class Iter>
 193     void generate(Iter first, Iter last)
 194     { detail::generate_from_int(*this, first, last); }
 195
 196     /** Advances the state of the generator by @c z. */
 197     void discard(boost::uintmax_t z)
 198     {
 199         for(boost::uintmax_t i = 0; i < z; ++i) {
 200             (*this)();
 201         }
 202     }
 203
 204     const base_type& base() const { return _base; }
 205
 206     /**
 207      * Writes the textual representation if the generator to a @c std::ostream.
 208      * The textual representation of the engine is the textual representation
 209      * of the base engine.
 210      */
 211     BOOST_RANDOM_DETAIL_OSTREAM_OPERATOR(os, independent_bits_engine, r)
 212     {
 213         os << r._base;
 214         return os;
 215     }
 216
 217     /**
 218      * Reads the state of an @c independent_bits_engine from a
 219      * @c std::istream.
 220      */
 221     BOOST_RANDOM_DETAIL_ISTREAM_OPERATOR(is, independent_bits_engine, r)
 222     {
 223         is >> r._base;
 224         return is;
 225     }
 226
 227     /**
 228      * Returns: true iff the two @c independent_bits_engines will
 229      * produce the same sequence of values.
 230      */
 231     BOOST_RANDOM_DETAIL_EQUALITY_OPERATOR(independent_bits_engine, x, y)
 232     { return x._base == y._base; }
 233     /**
 234      * Returns: true iff the two @c independent_bits_engines will
 235      * produce different sequences of values.
 236      */
 237     BOOST_RANDOM_DETAIL_INEQUALITY_OPERATOR(independent_bits_engine)
 238
 239 private:
 240
 241     /// \cond show_private
 242     typedef typename boost::random::traits::make_unsigned<base_result_type>::type base_unsigned;
 243
 244     static BOOST_CONSTEXPR UIntType max_imp(const boost::true_type&)
 245     {
 246        return boost::low_bits_mask_t<w>::sig_bits;
 247     }
 248     static UIntType max_imp(const boost::false_type&)
 249     {
 250        // We have a multiprecision integer type:
 251        BOOST_STATIC_ASSERT(std::numeric_limits<UIntType>::is_specialized);
 252        return w < std::numeric_limits<UIntType>::digits ? UIntType((UIntType(1) << w) - 1) : UIntType((((UIntType(1) << (w - 1)) - 1) << 1) | 1u);
 253     }
 254
 255     void calc_params(
 256         std::size_t n, base_unsigned range,
 257         std::size_t& w0, std::size_t& n0,
 258         base_unsigned& y0, base_unsigned& y1,
 259         base_unsigned& y0_mask, base_unsigned& y1_mask)
 260     {
 261         BOOST_ASSERT(w >= n);
 262         w0 = w/n;
 263         n0 = n - w % n;
 264         y0_mask = (base_unsigned(2) << (w0 - 1)) - 1;
 265         y1_mask = (y0_mask << 1) | 1;
 266         y0 = (range + 1) & ~y0_mask;
 267         y1 = (range + 1) & ~y1_mask;
 268         BOOST_ASSERT(y0 != 0 || base_unsigned(range + 1) == 0);
 269     }
 270     /// \endcond
 271
 272     Engine _base;
 273 };
 274
 275 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 276 template<class Engine, std::size_t w, class UIntType>
 277 const bool independent_bits_engine<Engine, w, UIntType>::has_fixed_range;
 278 #endif
 279
 280 } // namespace random
 281 } // namespace boost
 282
 283 #endif // BOOST_RANDOM_INDEPENDENT_BITS_HPP