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