Crypto++  5.6.3
Free C++ class library of cryptographic schemes
mersenne.h
Go to the documentation of this file.
1 // mersenne.h - written and placed in public domain by Jeffrey Walton.
2 // Copyright assigned to Crypto++ project.
3 
4 //! \file
5 //! \brief Class file for Mersenne Twister
6 //! \note Suitable for Monte Carlo simulations, and not cryptographic use
7 
8 #ifndef CRYPTOPP_MERSENNE_TWISTER_H
9 #define CRYPTOPP_MERSENNE_TWISTER_H
10 
11 #include "cryptlib.h"
12 #include "secblock.h"
13 #include "misc.h"
14 
15 NAMESPACE_BEGIN(CryptoPP)
16 
17 //! \class MersenneTwister
18 //! \brief Mersenne Twister class for Monte-Carlo simulations
19 //! \tparam K Magic constant
20 //! \tparam M Period parameter
21 //! \tparam N Size of the state vector
22 //! \tparam F Multiplier constant
23 //! \tparam S Sefault seed
24 //! \details Provides the \p MersenneTwister implementation. The class is a header-only implementation
25 template <unsigned int K, unsigned int M, unsigned int N, unsigned int F, unsigned long S>
27 {
28 public:
29  //! \brief Construct a Mersenne Twister
30  //! \param seed 32-bit seed
31  //! \details Defaults to template parameter \p S due to changing algorithm
32  //! parameters over time
33  MersenneTwister(unsigned long seed = S) : m_seed(seed), m_idx(N)
34  {
35  m_state[0] = seed;
36  for (unsigned int i = 1; i < N+1; i++)
37  m_state[i] = word32(F * (m_state[i-1] ^ (m_state[i-1] >> 30)) + i);
38  }
39 
40  //! \brief Generate random array of bytes
41  //! \param output byte buffer
42  //! \param size length of the buffer, in bytes
43  //! \details Bytes are written to \p output in big endian order. If \p output length
44  //! is not a multiple of word32, then unused bytes are not accumulated for subsequent
45  //! calls to \p GenerateBlock. Rather, the unused tail bytes are discarded, and the
46  //! stream is continued at the next word32 boundary from the state array.
47  void GenerateBlock(byte *output, size_t size)
48  {
49  // Handle word32 size blocks
50  word32 temp;
51  for (size_t i=0; i < size/4; i++, output += 4)
52  {
53 #if defined(CRYPTOPP_ALLOW_UNALIGNED_DATA_ACCESS) && defined(IS_LITTLE_ENDIAN)
54  *((word32*)output) = ByteReverse(NextMersenneWord());
55 #elif defined(CRYPTOPP_ALLOW_UNALIGNED_DATA_ACCESS)
56  *((word32*)output) = NextMersenneWord();
57 #else
58  temp = NextMersenneWord();
59  output[3] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 0);
60  output[2] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 1);
61  output[1] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 2);
62  output[0] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 3);
63 #endif
64  }
65 
66  // No tail bytes
67  if (size%4 == 0)
68  {
69  // Wipe temp
70  *((volatile word32*)&temp) = 0;
71  return;
72  }
73 
74  // Handle tail bytes
75  temp = NextMersenneWord();
76  switch (size%4)
77  {
78  case 3: output[2] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 1); /* fall through */
79  case 2: output[1] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 2); /* fall through */
80  case 1: output[0] = CRYPTOPP_GET_BYTE_AS_BYTE(temp, 3); break;
81 
82  default: assert(0); ;;
83  }
84 
85  // Wipe temp
86  *((volatile word32*)&temp) = 0;
87  }
88 
89  //! \brief Generate a random 32-bit word in the range min to max, inclusive
90  //! \returns random 32-bit word in the range min to max, inclusive
91  //! \details If the 32-bit candidate is not within the range, then it is discarded
92  //! and a new candidate is used.
93  word32 GenerateWord32(word32 min=0, word32 max=0xffffffffL)
94  {
95  const word32 range = max-min;
96  if (range == 0xffffffffL)
97  return NextMersenneWord();
98 
99  const int maxBits = BitPrecision(range);
100  word32 value;
101 
102  do{
103  value = Crop(NextMersenneWord(), maxBits);
104  } while (value > range);
105 
106  return value+min;
107  }
108 
109  //! \brief Generate and discard n bytes
110  //! \param n the number of bytes to discard, rounded up to a <tt>word32</tt> size
111  //! \details If \p n is not a multiple of <tt>word32</tt>, then unused bytes are
112  //! not accumulated for subsequent calls to \p GenerateBlock. Rather, the unused
113  //! tail bytes are discarded, and the stream is continued at the next
114  //! <tt>word32</tt> boundary from the state array.
115  void DiscardBytes(size_t n)
116  {
117  for(size_t i=0; i < RoundUpToMultipleOf(n, 4U); i++)
118  NextMersenneWord();
119  }
120 
121 protected:
122 
123  //! \brief Returns the next 32-bit word from the state array
124  //! \returns the next 32-bit word from the state array
125  //! \details fetches the next word frm the state array, performs bit operations on
126  //! it, and then returns the value to the caller.
127  word32 NextMersenneWord()
128  {
129  if (m_idx >= N) { Twist(); }
130 
131  word32 temp = m_state[m_idx++];
132 
133  temp ^= (temp >> 11);
134  temp ^= (temp << 7) & 0x9D2C5680; // 0x9D2C5680 (2636928640)
135  temp ^= (temp << 15) & 0xEFC60000; // 0xEFC60000 (4022730752)
136 
137  return temp ^ (temp >> 18);
138  }
139 
140  //! \brief Performs the twist operaton on the state array
141  void Twist()
142  {
143  static const unsigned long magic[2]={0x0UL, K};
144  word32 kk, temp;
145 
146  assert(N >= M);
147  for (kk=0;kk<N-M;kk++)
148  {
149  temp = (m_state[kk] & 0x80000000)|(m_state[kk+1] & 0x7FFFFFFF);
150  m_state[kk] = m_state[kk+M] ^ (temp >> 1) ^ magic[temp & 0x1UL];
151  }
152 
153  for (;kk<N-1;kk++)
154  {
155  temp = (m_state[kk] & 0x80000000)|(m_state[kk+1] & 0x7FFFFFFF);
156  m_state[kk] = m_state[kk+(M-N)] ^ (temp >> 1) ^ magic[temp & 0x1UL];
157  }
158 
159  temp = (m_state[N-1] & 0x80000000)|(m_state[0] & 0x7FFFFFFF);
160  m_state[N-1] = m_state[M-1] ^ (temp >> 1) ^ magic[temp & 0x1UL];
161 
162  // Reset index
163  m_idx = 0;
164 
165  // Wipe temp
166  *((volatile word32*)&temp) = 0;
167  }
168 
169 private:
170 
171  //! \brief 32-bit word state array of size \p N
173  //! \brief the value used to seed the generator
174  unsigned int m_seed;
175  //! \brief the current index into the state array
176  unsigned int m_idx;
177 };
178 
179 //! \brief Original MT19937 generator provided in the ACM paper.
180 //! \details Also see http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf; uses 4537 as default initial seed.
181 typedef MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x10DCD /*69069*/, 4537> MT19937;
182 
183 //! \brief Updated MT19937 generator adapted to provide an array for initialization.
184 //! \details Also see http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html; uses 5489 as default initial seed.
185 //! \note Use this generator when interoperating with C++11's \p mt19937 class.
186 typedef MersenneTwister<0x9908B0DF /*2567483615*/, 397, 624, 0x6C078965 /*1812433253*/, 5489> MT19937ar;
187 
188 NAMESPACE_END
189 
190 #endif // CRYPTOPP_MERSENNE_TWISTER_H
191 
Utility functions for the Crypto++ library.
MersenneTwister< 0x9908B0DF, 397, 624, 0x10DCD, 4537 > MT19937
Original MT19937 generator provided in the ACM paper.
Definition: mersenne.h:181
Mersenne Twister class for Monte-Carlo simulations.
Definition: mersenne.h:26
Abstract base classes that provide a uniform interface to this library.
Interface for random number generators.
Definition: cryptlib.h:1085
Classes and functions for secure memory allocations.
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
Definition: misc.h:638
void DiscardBytes(size_t n)
Generate and discard n bytes.
Definition: mersenne.h:115
void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: mersenne.h:47
MersenneTwister< 0x9908B0DF, 397, 624, 0x6C078965, 5489 > MT19937ar
Updated MT19937 generator adapted to provide an array for initialization.
Definition: mersenne.h:186
T1 RoundUpToMultipleOf(const T1 &n, const T2 &m)
Rounds a value up to a multiple of a second value.
Definition: misc.h:759
Crypto++ library namespace.
word32 GenerateWord32(word32 min=0, word32 max=0xffffffffL)
Generate a random 32-bit word in the range min to max, inclusive.
Definition: mersenne.h:93
byte ByteReverse(byte value)
Reverses bytes in a 8-bit value.
Definition: misc.h:1551
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition: misc.h:565
MersenneTwister(unsigned long seed=S)
Construct a Mersenne Twister.
Definition: mersenne.h:33