1 #ifndef RANDOM_GEN__HPP
2 #define RANDOM_GEN__HPP
3
4 /* $Id: random_gen.hpp 574980 2018-11-21 14:24:48Z ucko $
5 * ===========================================================================
6 *
7 * PUBLIC DOMAIN NOTICE
8 * National Center for Biotechnology Information
9 *
10 * This software/database is a "United States Government Work" under the
11 * terms of the United States Copyright Act. It was written as part of
12 * the author's official duties as a United States Government employee and
13 * thus cannot be copyrighted. This software/database is freely available
14 * to the public for use. The National Library of Medicine and the U.S.
15 * Government have not placed any restriction on its use or reproduction.
16 *
17 * Although all reasonable efforts have been taken to ensure the accuracy
18 * and reliability of the software and data, the NLM and the U.S.
19 * Government do not and cannot warrant the performance or results that
20 * may be obtained by using this software or data. The NLM and the U.S.
21 * Government disclaim all warranties, express or implied, including
22 * warranties of performance, merchantability or fitness for any particular
23 * purpose.
24 *
25 * Please cite the author in any work or product based on this material.
26 *
27 * ===========================================================================
28 *
29 * Authors: Clifford Clausen, Denis Vakatov, Jim Ostell, Jonathan Kans,
30 * Greg Schuler, Eugene Vasilchenko
31 * Contact: Clifford Clausen
32 *
33 * File Description:
34 * Random namber generator.
35 */
36
37 #include <corelib/ncbistd.hpp>
38
39
40 /** @addtogroup RandomGen
41 *
42 * @{
43 */
44
45
46 BEGIN_NCBI_SCOPE
47
48
49
50
51 /////////////////////////////////////////////////////////////////////////////
52 /// CRandom::
53 ///
54 /// Wraps a system-dependent random generator (could be slow due to
55 /// system calls), and implements lagged Fibonacci (LFG) random number
56 /// generator with lags 33 and 13, modulus 2^31, and operation '+'
57 ///
58 /// LFG is a slightly modified version of Nlm_Random() found in the NCBI C
59 /// toolkit. It generates uniform random numbers between 0 and 2^31 - 1 (inclusive).
60 /// It can be 100 times faster than system-dependent one.
61 ///
62 /// More details and literature refs are provided in "random_gen.cpp".
63
64
65 class NCBI_XUTIL_EXPORT CRandom
66 {
67 public:
68 /// Type of the generated integer value and/or the seed value
69 typedef Uint4 TValue;
70
71 /// Random generator to use in the GetRand() functions
72 enum EGetRandMethod {
73 eGetRand_LFG, ///< Use lagged Fibonacci (LFG) random number generator
74 eGetRand_Sys ///< Use system-dependent random generator
75 };
76
77 /// If "method" is:
78 /// - eGetRand_LFG -- use LFG generator seeded with a hard-coded seed
79 /// - eGetRand_Sys -- use system-dependent generator
80 CRandom(EGetRandMethod method = eGetRand_LFG);
81
82 /// Use LFG random generator seeded with "seed"
83 CRandom(TValue seed);
84
85 /// Get the next random number in the interval [0..GetMax()] (inclusive)
86 /// @sa EGetRandMethod
87 /// @note eGetRand_LFG generator could be 100 times faster
88 /// than eGetRand_Sys one
89 TValue GetRand(void);
90
91 /// Get random number in the interval [min_value..max_value] (inclusive)
92 /// @sa EGetRandMethod
93 /// @note eGetRand_LFG generator could be 100 times faster
94 /// than eGetRand_Sys one
95 TValue GetRand(TValue min_value, TValue max_value);
96
97 /// Get random Uint8 number
98 /// @sa EGetRandMethod
99 /// @note eGetRand_LFG generator could be 100 times faster
100 /// than eGetRand_Sys one
101 Uint8 GetRandUint8(void);
102
103 /// Get random number in the interval [min_value..max_value] (inclusive)
104 /// @sa EGetRandMethod
105 /// @note eGetRand_LFG generator could be 100 times faster
106 /// than eGetRand_Sys one
107 Uint8 GetRandUint8(Uint8 min_value, Uint8 max_value);
108
109 /// Get random number in the interval [min_value..max_value] (inclusive)
110 /// @sa EGetRandMethod
111 /// @note eGetRand_LFG generator could be 100 times faster
112 /// than eGetRand_Sys one
113 size_t GetRandSize_t(size_t min_value, size_t max_value);
114
115 /// Get random number in the interval [0..size-1] (e.g. index in array)
116 /// @sa EGetRandMethod
117 /// @note eGetRand_LFG generator could be 100 times faster
118 /// than eGetRand_Sys one
119 TValue GetRandIndex(TValue size);
120
121 /// Get random number in the interval [0..size-1] (e.g. index in array)
122 /// @sa EGetRandMethod
123 /// @note eGetRand_LFG generator could be 100 times faster
124 /// than eGetRand_Sys one
125 Uint8 GetRandIndexUint8(Uint8 size);
126
127 /// Get random number in the interval [0..size-1] (e.g. index in array)
128 /// @sa EGetRandMethod
129 /// @note eGetRand_LFG generator could be 100 times faster
130 /// than eGetRand_Sys one
131 size_t GetRandIndexSize_t(size_t size);
132
133 /// The max. value GetRand() returns
134 static TValue GetMax(void);
135
136 /// Get the random generator type
137 EGetRandMethod GetRandMethod(void) const;
138
139 // LFG only:
140
141 /// Re-initialize (re-seed) the generator using platform-specific
142 /// randomization.
143 /// @note Does nothing if system generator is used.
144 void Randomize(void);
145
146 /// Seed the random number generator with "seed".
147 /// @attention Throw exception if non-LFG (i.e. system) generator is used.
148 void SetSeed(TValue seed);
149
150 /// Get the last set seed (LFG only)
151 /// @attention Throw exception if non-LFG (i.e. system) generator is used.
152 TValue GetSeed(void) const;
153
154 /// Reset random number generator to initial startup condition (LFG only)
155 /// @attention Throw exception if non-LFG (i.e. system) generator is used.
156 void Reset(void);
157
158 private:
159 enum {
160 kStateSize = 33 // size of state array
161 };
162 EGetRandMethod m_RandMethod;
163 TValue m_State[kStateSize];
164 int m_RJ;
165 int m_RK;
166 TValue m_Seed;
167
168 TValue x_GetRand32Bits(void);
169 Uint8 x_GetRand64Bits(void);
170 TValue x_GetSysRand32Bits(void) const;
171
172 // prevent copying
173 CRandom(const CRandom&);
174 CRandom& operator=(const CRandom&);
175 };
176
177
178 /// Exceptions generated by CRandom class
179 class NCBI_XUTIL_EXPORT CRandomException : public CException
180 {
181 public:
182 enum EErrCode {
183 eUnavailable, ///< System-dependent generator is not available
184 eUnexpectedRandMethod, ///< The user called method which is not
185 ///< allowed for the used generator.
186 eSysGeneratorError ///< Error getting a random value from the
187 ///< system-dependent generator.
188 };
189
GetErrCodeString(void) const190 virtual const char* GetErrCodeString(void) const override
191 {
192 switch (GetErrCode()) {
193 case eUnavailable : return "eUnavailable";
194 case eUnexpectedRandMethod : return "eUnexpectedRandMethod";
195 case eSysGeneratorError : return "eSysGeneratorError";
196 default : return CException::GetErrCodeString();
197 }
198 }
199
200 NCBI_EXCEPTION_DEFAULT(CRandomException, CException);
201 };
202
203
204
205 /* @} */
206
207
208 /////////////////////////////////////////////////////////////////////////////
209 // IMPLEMENTATION of INLINE functions
210 /////////////////////////////////////////////////////////////////////////////
211
212
213 /////////////////////////////////////////////////////////////////////////////
214 // CRandom::
215 //
216
x_GetRand32Bits(void)217 inline CRandom::TValue CRandom::x_GetRand32Bits(void)
218 {
219 if (m_RandMethod == eGetRand_Sys)
220 return x_GetSysRand32Bits();
221
222 register TValue r;
223
224 r = m_State[m_RK] + m_State[m_RJ--];
225 m_State[m_RK--] = r;
226
227 if ( m_RK < 0 ) {
228 m_RK = kStateSize - 1;
229 }
230 else if ( m_RJ < 0 ) {
231 m_RJ = kStateSize - 1;
232 }
233
234 return r;
235 }
236
237
GetRand(void)238 inline CRandom::TValue CRandom::GetRand(void)
239 {
240 return x_GetRand32Bits() >> 1; // discard the least-random bit
241 }
242
243
GetRandUint8(void)244 inline Uint8 CRandom::GetRandUint8(void)
245 {
246 Uint8 v1 = x_GetRand32Bits();
247 return (v1 << 32)+x_GetRand32Bits();
248 }
249
250
GetRandIndex(TValue size)251 inline CRandom::TValue CRandom::GetRandIndex(TValue size)
252 {
253 if ( (size & (size-1)) == 0 ) { // only one bit set - power of 2
254 // get high bits via multiplication - it's faster than division
255 return TValue(Uint8(x_GetRand32Bits())*size >> 32);
256 }
257
258 TValue bits, r;
259 do {
260 bits = x_GetRand32Bits();
261 r = bits % size;
262 } while ( bits > r - size ); // 32-bit overflow is intentional
263 return r;
264 }
265
266
GetRandIndexSize_t(size_t size)267 inline size_t CRandom::GetRandIndexSize_t(size_t size)
268 {
269 #if SIZEOF_SIZE_T == 4
270 return GetRandIndex(Uint4(size));
271 #else
272 return GetRandIndexUint8(size);
273 #endif
274 }
275
276
GetRand(TValue min_value,TValue max_value)277 inline CRandom::TValue CRandom::GetRand(TValue min_value, TValue max_value)
278 {
279 return min_value + GetRandIndex(max_value - min_value + 1);
280 }
281
282
GetRandUint8(Uint8 min_value,Uint8 max_value)283 inline Uint8 CRandom::GetRandUint8(Uint8 min_value, Uint8 max_value)
284 {
285 return min_value + GetRandIndexUint8(max_value - min_value + 1);
286 }
287
288
GetRandSize_t(size_t min_value,size_t max_value)289 inline size_t CRandom::GetRandSize_t(size_t min_value, size_t max_value)
290 {
291 return min_value + GetRandIndexSize_t(max_value - min_value + 1);
292 }
293
294
GetMax(void)295 inline CRandom::TValue CRandom::GetMax(void)
296 {
297 return 0x7fffffff;
298 }
299
300
GetRandMethod(void) const301 inline CRandom::EGetRandMethod CRandom::GetRandMethod(void) const
302 {
303 return m_RandMethod;
304 }
305
306
307 END_NCBI_SCOPE
308
309 #endif /* RANDOM_GEN__HPP */
310