ceph/src/boost/boost/random/detail/gray_coded_qrng.hpp

   1 /* boost random/detail/gray_coded_qrng.hpp header file
   2  *
   3  * Copyright Justinas Vygintas Daugmaudis 2010-2018
   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
   9 #ifndef BOOST_RANDOM_DETAIL_GRAY_CODED_QRNG_HPP
  10 #define BOOST_RANDOM_DETAIL_GRAY_CODED_QRNG_HPP
  11
  12 #include <boost/random/detail/qrng_base.hpp>
  13
  14 #include <boost/multiprecision/integer.hpp> // lsb
  15
  16 #include <functional> // bit_xor
  17
  18 #include <boost/type_traits/conditional.hpp>
  19
  20 #include <boost/integer/integer_mask.hpp>
  21
  22 //!\file
  23 //!Describes the gray-coded quasi-random number generator base class template.
  24
  25 namespace boost {
  26 namespace random {
  27
  28 namespace qrng_detail {
  29
  30 template<typename LatticeT>
  31 class gray_coded_qrng
  32   : public qrng_base<
  33       gray_coded_qrng<LatticeT>
  34     , LatticeT
  35     , typename LatticeT::value_type
  36     >
  37 {
  38 public:
  39   typedef typename LatticeT::value_type result_type;
  40   typedef result_type size_type;
  41
  42 private:
  43   typedef gray_coded_qrng<LatticeT> self_t;
  44   typedef qrng_base<self_t, LatticeT, size_type> base_t;
  45
  46   // The base needs to access modifying member f-ns, and we
  47   // don't want these functions to be available for the public use
  48   friend class qrng_base<self_t, LatticeT, size_type>;
  49
  50   // Respect lattice bit_count here
  51   struct check_nothing {
  52     inline static void bit_pos(unsigned) {}
  53     inline static void code_size(size_type) {}
  54   };
  55   struct check_bit_range {
  56     static void raise_bit_count() {
  57       boost::throw_exception( std::range_error("gray_coded_qrng: bit_count") );
  58     }
  59     inline static void bit_pos(unsigned bit_pos) {
  60       if (bit_pos >= LatticeT::bit_count)
  61         raise_bit_count();
  62     }
  63     inline static void code_size(size_type code) {
  64       if (code > (self_t::max)())
  65         raise_bit_count();
  66     }
  67   };
  68
  69   // We only want to check whether bit pos is outside the range if given bit_count
  70   // is narrower than the size_type, otherwise checks compile to nothing.
  71   BOOST_STATIC_ASSERT(LatticeT::bit_count <= std::numeric_limits<size_type>::digits);
  72
  73   typedef typename conditional<
  74       ((LatticeT::bit_count) < std::numeric_limits<size_type>::digits)
  75     , check_bit_range
  76     , check_nothing
  77   >::type check_bit_range_t;
  78
  79 public:
  80   //!Returns: Tight lower bound on the set of values returned by operator().
  81   //!
  82   //!Throws: nothing.
  83   static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION ()
  84   { return 0; }
  85
  86   //!Returns: Tight upper bound on the set of values returned by operator().
  87   //!
  88   //!Throws: nothing.
  89   static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
  90   { return low_bits_mask_t<LatticeT::bit_count>::sig_bits; }
  91
  92   explicit gray_coded_qrng(std::size_t dimension)
  93     : base_t(dimension)
  94   {}
  95
  96   // default copy c-tor is fine
  97
  98   // default assignment operator is fine
  99
 100   void seed()
 101   {
 102     set_zero_state();
 103     update_quasi(0);
 104     base_t::reset_seq(0);
 105   }
 106
 107   void seed(const size_type init)
 108   {
 109     if (init != this->curr_seq())
 110     {
 111       // We don't want negative seeds.
 112       check_seed_sign(init);
 113
 114       size_type seq_code = boost::next(init);
 115       if (BOOST_UNLIKELY(!(init < seq_code)))
 116         boost::throw_exception( std::range_error("gray_coded_qrng: seed") );
 117
 118       seq_code ^= (seq_code >> 1);
 119       // Fail if we see that seq_code is outside bit range.
 120       // We do that before we even touch engine state.
 121       check_bit_range_t::code_size(seq_code);
 122
 123       set_zero_state();
 124       for (unsigned r = 0; seq_code != 0; ++r, seq_code >>= 1)
 125       {
 126         if (seq_code & static_cast<size_type>(1))
 127           update_quasi(r);
 128       }
 129     }
 130     // Everything went well, set the new seq count
 131     base_t::reset_seq(init);
 132   }
 133
 134 private:
 135   void compute_seq(size_type seq)
 136   {
 137     // Find the position of the least-significant zero in sequence count.
 138     // This is the bit that changes in the Gray-code representation as
 139     // the count is advanced.
 140     // Xor'ing with max() has the effect of flipping all the bits in seq,
 141     // except for the sign bit.
 142     unsigned r = multiprecision::lsb(seq ^ (self_t::max)());
 143     check_bit_range_t::bit_pos(r);
 144     update_quasi(r);
 145   }
 146
 147   void update_quasi(unsigned r)
 148   {
 149     // Calculate the next state.
 150     std::transform(this->state_begin(), this->state_end(),
 151       this->lattice.iter_at(r * this->dimension()), this->state_begin(),
 152       std::bit_xor<result_type>());
 153   }
 154
 155   void set_zero_state()
 156   {
 157     std::fill(this->state_begin(), this->state_end(), result_type /*zero*/ ());
 158   }
 159 };
 160
 161 } // namespace qrng_detail
 162
 163 } // namespace random
 164 } // namespace boost
 165
 166 #endif // BOOST_RANDOM_DETAIL_GRAY_CODED_QRNG_HPP