src/rand/GaloisLFSR.hpp

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