random/detail/gray_coded_qrng.hpp

0001 /* boost random/detail/gray_coded_qrng.hpp header file
0002  *
0003  * Copyright Justinas Vygintas Daugmaudis 2010-2018
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
0009 #ifndef BOOST_RANDOM_DETAIL_GRAY_CODED_QRNG_HPP
0010 #define BOOST_RANDOM_DETAIL_GRAY_CODED_QRNG_HPP
0011
0012 #include <boost/random/detail/qrng_base.hpp>
0013
0014 #include <boost/core/bit.hpp> // lsb
0015 #include <boost/throw_exception.hpp>
0016 #include <stdexcept>
0017
0018 #include <functional> // bit_xor
0019 #include <algorithm>
0020
0021 #include <boost/type_traits/conditional.hpp>
0022
0023 #include <boost/integer/integer_mask.hpp>
0024
0025 //!\file
0026 //!Describes the gray-coded quasi-random number generator base class template.
0027
0028 namespace boost {
0029 namespace random {
0030
0031 namespace qrng_detail {
0032
0033 template<class T> static int lsb( T x )
0034 {
0035   if( x == 0 )
0036   {
0037     BOOST_THROW_EXCEPTION( std::range_error( "qrng_detail::lsb: argument is 0" ) );
0038   }
0039
0040   return boost::core::countr_zero( x );
0041 }
0042
0043 template<class T> static int msb( T x )
0044 {
0045   if( x == 0 )
0046   {
0047     BOOST_THROW_EXCEPTION( std::range_error( "qrng_detail::msb: argument is 0" ) );
0048   }
0049
0050   return std::numeric_limits<T>::digits - 1 - boost::core::countl_zero( x );
0051 }
0052
0053 template<typename LatticeT>
0054 class gray_coded_qrng
0055   : public qrng_base<
0056       gray_coded_qrng<LatticeT>
0057     , LatticeT
0058     , typename LatticeT::value_type
0059     >
0060 {
0061 public:
0062   typedef typename LatticeT::value_type result_type;
0063   typedef result_type size_type;
0064
0065 private:
0066   typedef gray_coded_qrng<LatticeT> self_t;
0067   typedef qrng_base<self_t, LatticeT, size_type> base_t;
0068
0069   // The base needs to access modifying member f-ns, and we
0070   // don't want these functions to be available for the public use
0071   friend class qrng_base<self_t, LatticeT, size_type>;
0072
0073   // Respect lattice bit_count here
0074   struct check_nothing {
0075     inline static void bit_pos(unsigned) {}
0076     inline static void code_size(size_type) {}
0077   };
0078   struct check_bit_range {
0079     static void raise_bit_count() {
0080       boost::throw_exception( std::range_error("gray_coded_qrng: bit_count") );
0081     }
0082     inline static void bit_pos(unsigned bit_pos) {
0083       if (bit_pos >= LatticeT::bit_count)
0084         raise_bit_count();
0085     }
0086     inline static void code_size(size_type code) {
0087       if (code > (self_t::max)())
0088         raise_bit_count();
0089     }
0090   };
0091
0092   // We only want to check whether bit pos is outside the range if given bit_count
0093   // is narrower than the size_type, otherwise checks compile to nothing.
0094   BOOST_STATIC_ASSERT(LatticeT::bit_count <= std::numeric_limits<size_type>::digits);
0095
0096   typedef typename conditional<
0097       ((LatticeT::bit_count) < std::numeric_limits<size_type>::digits)
0098     , check_bit_range
0099     , check_nothing
0100   >::type check_bit_range_t;
0101
0102 public:
0103   //!Returns: Tight lower bound on the set of values returned by operator().
0104   //!
0105   //!Throws: nothing.
0106   static BOOST_CONSTEXPR result_type min BOOST_PREVENT_MACRO_SUBSTITUTION ()
0107   { return 0; }
0108
0109   //!Returns: Tight upper bound on the set of values returned by operator().
0110   //!
0111   //!Throws: nothing.
0112   static BOOST_CONSTEXPR result_type max BOOST_PREVENT_MACRO_SUBSTITUTION ()
0113   { return low_bits_mask_t<LatticeT::bit_count>::sig_bits; }
0114
0115   explicit gray_coded_qrng(std::size_t dimension)
0116     : base_t(dimension)
0117   {}
0118
0119   // default copy c-tor is fine
0120
0121   // default assignment operator is fine
0122
0123   void seed()
0124   {
0125     set_zero_state();
0126     update_quasi(0);
0127     base_t::reset_seq(0);
0128   }
0129
0130   void seed(const size_type init)
0131   {
0132     if (init != this->curr_seq())
0133     {
0134       // We don't want negative seeds.
0135       check_seed_sign(init);
0136
0137       size_type seq_code = init + 1;
0138       if (BOOST_UNLIKELY(!(init < seq_code)))
0139         boost::throw_exception( std::range_error("gray_coded_qrng: seed") );
0140
0141       seq_code ^= (seq_code >> 1);
0142       // Fail if we see that seq_code is outside bit range.
0143       // We do that before we even touch engine state.
0144       check_bit_range_t::code_size(seq_code);
0145
0146       set_zero_state();
0147       for (unsigned r = 0; seq_code != 0; ++r, seq_code >>= 1)
0148       {
0149         if (seq_code & static_cast<size_type>(1))
0150           update_quasi(r);
0151       }
0152     }
0153     // Everything went well, set the new seq count
0154     base_t::reset_seq(init);
0155   }
0156
0157 private:
0158
0159   void compute_seq(size_type seq)
0160   {
0161     // Find the position of the least-significant zero in sequence count.
0162     // This is the bit that changes in the Gray-code representation as
0163     // the count is advanced.
0164     // Xor'ing with max() has the effect of flipping all the bits in seq,
0165     // except for the sign bit.
0166     unsigned r = qrng_detail::lsb(static_cast<size_type>(seq ^ (self_t::max)()));
0167     check_bit_range_t::bit_pos(r);
0168     update_quasi(r);
0169   }
0170
0171   void update_quasi(unsigned r)
0172   {
0173     // Calculate the next state.
0174     std::transform(this->state_begin(), this->state_end(),
0175       this->lattice.iter_at(r * this->dimension()), this->state_begin(),
0176       std::bit_xor<result_type>());
0177   }
0178
0179   void set_zero_state()
0180   {
0181     std::fill(this->state_begin(), this->state_end(), result_type /*zero*/ ());
0182   }
0183 };
0184
0185 } // namespace qrng_detail
0186
0187 } // namespace random
0188 } // namespace boost
0189
0190 #endif // BOOST_RANDOM_DETAIL_GRAY_CODED_QRNG_HPP