src/rand/GaloisLFSR.hpp

   1 #ifndef BLANK_RAND_GALOISLFSR_HPP_
   2 #define BLANK_RAND_GALOISLFSR_HPP_
   3
   4 #include <cstdint>
   5 #include <limits>
   6
   7
   8 namespace blank {
   9
  10 class GaloisLFSR {
  11
  12 public:
  13         // seed should be non-zero
  14         explicit GaloisLFSR(std::uint64_t seed) noexcept
  15         : state(seed) {
  16                 if (state == 0) {
  17                         state = 1;
  18                 }
  19         }
  20
  21         // get the next bit
  22         bool operator ()() noexcept {
  23                 bool result = state & 1;
  24                 state >>= 1;
  25                 if (result) {
  26                         state |= 0x8000000000000000;
  27                         state ^= mask;
  28                 } else {
  29                         state &= 0x7FFFFFFFFFFFFFFF;
  30                 }
  31                 return result;
  32         }
  33
  34         template<class T>
  35         T operator ()(T &out) noexcept {
  36                 constexpr int num_bits =
  37                         std::numeric_limits<T>::digits +
  38                         std::numeric_limits<T>::is_signed;
  39                 for (int i = 0; i < num_bits; ++i) {
  40                         operator ()();
  41                 }
  42                 return out = static_cast<T>(state);
  43         }
  44
  45         /// special case for randrom(boolean), since static_cast<bool>(0b10) == true
  46         bool operator ()(bool &out) noexcept {
  47                 return out = operator ()();
  48         }
  49
  50         template<class T>
  51         T Next() noexcept {
  52                 T next;
  53                 return (*this)(next);
  54         }
  55
  56         float SNorm() noexcept {
  57                 return float(Next<std::uint32_t>()) * (1.0f / 2147483647.5f) - 1.0f;
  58         }
  59
  60         float UNorm() noexcept {
  61                 return float(Next<std::uint32_t>()) * (1.0f / 4294967295.0f);
  62         }
  63
  64         template<class Container>
  65         typename Container::reference From(Container &c) {
  66                 return c[Next<typename Container::size_type>() % c.size()];
  67         }
  68         template<class Container>
  69         typename Container::const_reference From(const Container &c) {
  70                 return c[Next<typename Container::size_type>() % c.size()];
  71         }
  72
  73 private:
  74         std::uint64_t state;
  75         // bits 64, 63, 61, and 60 set to 1 (counting from 1 lo to hi)
  76         static constexpr std::uint64_t mask = 0xD800000000000000;
  77
  78 };
  79
  80 }
  81
  82 #endif