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