NCBI C++ ToolKit
random_gen.cpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /* $Id: random_gen.cpp 85213 2019-01-24 19:25:20Z lavr $
2  * ===========================================================================
3  *
4  * PUBLIC DOMAIN NOTICE
5  * National Center for Biotechnology Information
6  *
7  * This software/database is a "United States Government Work" under the
8  * terms of the United States Copyright Act. It was written as part of
9  * the author's official duties as a United States Government employee and
10  * thus cannot be copyrighted. This software/database is freely available
11  * to the public for use. The National Library of Medicine and the U.S.
12  * Government have not placed any restriction on its use or reproduction.
13  *
14  * Although all reasonable efforts have been taken to ensure the accuracy
15  * and reliability of the software and data, the NLM and the U.S.
16  * Government do not and cannot warrant the performance or results that
17  * may be obtained by using this software or data. The NLM and the U.S.
18  * Government disclaim all warranties, express or implied, including
19  * warranties of performance, merchantability or fitness for any particular
20  * purpose.
21  *
22  * Please cite the author in any work or product based on this material.
23  *
24  * ===========================================================================
25  *
26  * Authors: Clifford Clausen, Denis Vakatov, Jim Ostell, Jonathan Kans,
27  * Greg Schuler, Eugene Vasilchenko
28  * Contact: Clifford Clausen
29  *
30  * File Description:
31  * CRandom is a lagged Fibonacci (LFG) random number generator (RNG)
32  * with lags 33 and 13, modulus 2^31, and operation '+'. It is a slightly
33  * modified version of Nlm_Random() found in the NCBI C toolkit.
34  * It generates uniform random numbers between 0 and 2^31 - 1 (inclusive).
35  *
36  * CRandom has been tested using the Diehard RNG test package
37  * developed by George Marsaglia, Prof., Dept of Statistics, Florida
38  * State University. CRandom in particular, and LFG type RNGs in general,
39  * cannot pass all of the Diehard RNG tests. Specifically, it fails the
40  * "Birthday" test as do other LFG RNGs. CRandom performs as well as
41  * other LFG RNGS, as provided in the Diehard test package. The LFG
42  * class of RNGs was chosen as the RNG for the NCBI C++ Toolkit as it
43  * provides the best tradeoff between time to generate a random number
44  * and performance on tests for randomness.
45  *
46  * For a download of Diehard software and documentation
47  * see http://stat.fsu.edu/~geo/diehard.html.
48  *
49  * For further information also see
50  * http://random.mat.sbg.ac.at/,
51  * http://csep1.phy.ornl.gov/rn/rn.html, and
52  * http://www.agner.org/random/.
53  *
54  * Some relevant papers are:
55  * 1. Hellekalek, P.: "Inversive pseudorandom number generators: concepts
56  * results, and links", In Alexopoulos, C and Kang, K, and Lilegdon, WR,
57  * and Goldsman, D, editor(s), Proceedings of the 1995 Winter Simulation
58  * Conference, pp 255-262, 1995.
59  * 2. Leeb, H: "Random Numbers for Computer Simulation", Master's thesis,
60  * University of Salzburg, 1995.
61  * 3. Marsaglia, G., "A Current View of Random Number Generators",
62  * Proceedings of 16th Symposium on the Interface, Atlanta, 1984, Elsevier
63  * Press.
64  * 4. Marsaglia, G. "Monkey Tests for Random Number Generators", Computers
65  * & Mathematics with Applications, Vol 9, pp. 1-10, 1993.
66  *
67  * For a list of other published papers, see
68  * http://random.mat.sbg.ac.at/literature and
69  * http://www.evensen.org/marsaglia/.
70  *
71  * class CRandom::
72  */
73 
74 #include <ncbi_pch.hpp>
75 #include <util/random_gen.hpp>
76 
77 #include <corelib/ncbitime.hpp>
78 #include <corelib/ncbi_process.hpp>
79 #include <corelib/ncbithr.hpp>
81 #include <corelib/ncbidiag.hpp>
82 
83 #if defined(NCBI_OS_UNIX) || defined(NCBI_OS_DARWIN)
84  #include <unistd.h>
85  #include <sys/types.h>
86  #include <sys/stat.h>
87  #include <fcntl.h>
88  #include <errno.h>
89  #include <string.h>
90 #elif defined(NCBI_OS_MSWIN)
91  #include <Wincrypt.h>
92 #endif /* NCBI_OS */
93 
94 
96 
97 
98 static const size_t kStateOffset = 12;
99 
100 #if defined(NCBI_OS_UNIX) || defined(NCBI_OS_DARWIN)
101 
102  static const char * kHardwareGeneratorDevice = "/dev/hwrng";
103  static const char * kSoftwareGeneratorDevice = "/dev/urandom";
104 
106  {
107  public:
109  m_Fd(-1)
110  {
111  m_Fd = open(kHardwareGeneratorDevice, O_RDONLY);
112  if (m_Fd == -1)
113  m_Fd = open(kSoftwareGeneratorDevice, O_RDONLY);
114  }
116  {
117  if (m_Fd != -1) {
118  close(m_Fd);
119  m_Fd = -1;
120  }
121  }
122 
123  bool IsInitialized(void) const
124  { return m_Fd != -1; }
125 
126  bool GetRand(CRandom::TValue * value, bool throw_on_error)
127  {
128  if (m_Fd == -1)
129  NCBI_THROW(CRandomException, eUnavailable,
130  "System-dependent generator is not available");
131 
132  for ( ; ; ) {
133  if (read(m_Fd, value, sizeof(CRandom::TValue)) ==
134  sizeof(CRandom::TValue))
135  return true;
136  if (errno != EINTR)
137  break;
138  }
139 
140  if (throw_on_error)
141  NCBI_THROW(CRandomException, eSysGeneratorError,
142  string("Error getting random value from the "
143  "system-dependent generator: ") +
144  strerror(errno));
145  return false;
146  }
147 
148  private:
149  int m_Fd;
150  };
151 
152 #elif defined(NCBI_OS_MSWIN)
153 
154  class CRandomSupplier
155  {
156  public:
157  CRandomSupplier() :
158  m_Provider(0), m_Initialized(false)
159  {
160  static DWORD providers[] =
161  { PROV_RSA_AES, PROV_RSA_FULL, PROV_RSA_SIG,
162  PROV_RSA_SCHANNEL, PROV_DSS, PROV_DSS_DH,
163  PROV_DH_SCHANNEL, PROV_FORTEZZA,
164  PROV_MS_EXCHANGE, PROV_SSL };
165  for ( size_t k = 0; k < sizeof(providers)/sizeof(providers[0]); ++k) {
166  if (CryptAcquireContext(&m_Provider, 0, 0, providers[k],
167  CRYPT_VERIFYCONTEXT | CRYPT_SILENT)) {
168  m_Initialized = true;
169  break;
170  }
171  }
172  }
174  {
175  if (m_Initialized) {
176  CryptReleaseContext(m_Provider, 0);
177  m_Initialized = false;
178  }
179  }
180 
181  bool IsInitialized(void) const
182  { return m_Initialized; }
183 
184  bool GetRand(CRandom::TValue * value, bool throw_on_error)
185  {
186  if (m_Initialized) {
187  if (CryptGenRandom(m_Provider, sizeof(CRandom::TValue),
188  reinterpret_cast<PBYTE>(value)))
189  return true;
190  }
191  if (throw_on_error) {
192  if (!m_Initialized)
193  NCBI_THROW(CRandomException, eUnavailable,
194  "System-dependent generator is not available");
195 
196  NCBI_THROW(CRandomException, eSysGeneratorError,
197  string("Error getting random value from the "
198  "system-dependent generator. Error code: ") +
199  NStr::NumericToString(GetLastError()));
200  }
201  return false;
202  }
203 
204  private:
205  HCRYPTPROV m_Provider;
206  bool m_Initialized;
207  };
208 
209 #endif /* NCBI_OS */
210 
212 
213 
214 
216  m_RandMethod(method)
217 {
218  if (method == eGetRand_Sys) {
219  if (!s_RandomSupplier->IsInitialized())
220  NCBI_THROW(CRandomException, eUnavailable,
221  "System-dependent generator is not available");
222  } else
223  Reset();
224 }
225 
226 
228  m_RandMethod(eGetRand_LFG)
229 {
230  SetSeed(seed);
231 }
232 
233 
234 void CRandom::Reset(void)
235 {
236  if (m_RandMethod == eGetRand_Sys)
237  NCBI_THROW(CRandomException, eUnexpectedRandMethod,
238  "CRandom::Reset() is not allowed for "
239  "system-dependent generator");
240 
241  // Static array used to initialize "m_State"
242  static const CRandom::TValue sm_State[CRandom::kStateSize] = {
243  0xd53f1852, 0xdfc78b83, 0x4f256096, 0xe643df7,
244  0x82c359bf, 0xc7794dfa, 0xd5e9ffaa, 0x2c8cb64a,
245  0x2f07b334, 0xad5a7eb5, 0x96dc0cde, 0x6fc24589,
246  0xa5853646, 0xe71576e2, 0xdae30df, 0xb09ce711,
247  0x5e56ef87, 0x4b4b0082, 0x6f4f340e, 0xc5bb17e8,
248  0xd788d765, 0x67498087, 0x9d7aba26, 0x261351d4,
249  0x411ee7ea, 0x393a263, 0x2c5a5835, 0xc115fcd8,
250  0x25e9132c, 0xd0c6e906, 0xc2bc5b2d, 0x6c065c98,
251  0x6e37bd55
252  };
253 
254 
255  _ASSERT(sizeof(sm_State) == sizeof(m_State));
257 
258  for (int i = 0; i < kStateSize; ++i) {
259  m_State[i] = sm_State[i];
260  }
261 
262  m_RJ = kStateOffset;
263  m_RK = kStateSize - 1;
264 }
265 
266 
268 {
269  if (m_RandMethod == eGetRand_Sys)
270  return;
271 
272  TValue seed;
273  if (s_RandomSupplier->GetRand(&seed, false)) {
274  SetSeed(seed);
275  return;
276  }
277 
278  CTime now(CTime::eCurrent);
279 
280  SetSeed(TValue(now.Second() ^
281  now.NanoSecond() ^
282  CCurrentProcess::GetPid() * 19 ^
283  CThread::GetSelf() * 5));
284 }
285 
286 
288 {
289  if (m_RandMethod == eGetRand_Sys)
290  NCBI_THROW(CRandomException, eUnexpectedRandMethod,
291  "CRandom::SetSeed(...) is not allowed for "
292  "system-dependent generator");
293 
295 
296  m_State[0] = m_Seed = seed;
297 
298  // linear congruential initializer
299  for (int i = 1; i < kStateSize; ++i) {
300  m_State[i] = 1103515245 * m_State[i-1] + 12345;
301  }
302 
303  m_RJ = kStateOffset;
304  m_RK = kStateSize - 1;
305 
306  for (int i = 0; i < 10 * kStateSize; ++i) {
307  GetRand();
308  }
309 }
310 
311 
313 {
314  if (m_RandMethod == eGetRand_Sys)
315  NCBI_THROW(CRandomException, eUnexpectedRandMethod,
316  "CRandom::GetSeed(...) is not allowed for "
317  "system-dependent generator");
318 
319  return m_Seed;
320 }
321 
322 
324 {
325  TValue r;
326  s_RandomSupplier->GetRand(&r, true);
327  return r;
328 }
329 
330 
332 {
333  if ( size <= kMax_UI4 ) {
334  return GetRandIndex(Uint4(size));
335  }
336 
337  if ( (size & (size-1)) == 0 ) { // only one bit set - power of 2
338  // get high bits via multiplication - it's faster than division
339  Uint8 bits = GetRandUint8();
340  while ( size <<= 1 ) {
341  bits >>= 1;
342  }
343  return bits;
344  }
345 
346  Uint8 bits, r;
347  do {
348  bits = GetRandUint8();
349  r = bits % size;
350  } while ( bits > r - size ); // 64-bit overflow is intentional
351  return r;
352 }
353 
354 
Exceptions generated by CRandom class.
Definition: random_gen.hpp:180
bool IsInitialized(void) const
Definition: random_gen.cpp:123
bool GetRand(CRandom::TValue *value, bool throw_on_error)
Definition: random_gen.cpp:126
CSafeStatic<>::
CTime –.
Definition: ncbitime.hpp:296
int close(int fd)
Definition: connection.cpp:45
#define NCBI_THROW(exception_class, err_code, message)
Generic macro to throw an exception, given the exception class, error code and message string.
Definition: ncbiexpt.hpp:704
uint32_t Uint4
4-byte (32-bit) unsigned integer
Definition: ncbitype.h:103
uint64_t Uint8
8-byte (64-bit) unsigned integer
Definition: ncbitype.h:105
#define kMax_UI4
Definition: ncbi_limits.h:219
static TPid GetPid(void)
Get process identifier (pid) for the current process.
TValue m_State[kStateSize]
Definition: random_gen.hpp:163
Uint4 TValue
Type of the generated integer value and/or the seed value.
Definition: random_gen.hpp:69
EGetRandMethod m_RandMethod
Definition: random_gen.hpp:162
TValue GetRand(void)
Get the next random number in the interval [0..GetMax()] (inclusive)
Definition: random_gen.hpp:238
TValue GetRandIndex(TValue size)
Get random number in the interval [0..size-1] (e.g.
Definition: random_gen.hpp:251
Uint8 GetRandUint8(void)
Get random Uint8 number.
Definition: random_gen.hpp:244
Uint8 GetRandIndexUint8(Uint8 size)
Get random number in the interval [0..size-1] (e.g.
Definition: random_gen.cpp:331
CRandom(EGetRandMethod method=eGetRand_LFG)
If "method" is:
Definition: random_gen.cpp:215
TValue GetSeed(void) const
Get the last set seed (LFG only)
Definition: random_gen.cpp:312
void SetSeed(TValue seed)
Seed the random number generator with "seed".
Definition: random_gen.cpp:287
EGetRandMethod
Random generator to use in the GetRand() functions.
Definition: random_gen.hpp:72
void Reset(void)
Reset random number generator to initial startup condition (LFG only)
Definition: random_gen.cpp:234
TValue m_Seed
Definition: random_gen.hpp:166
void Randomize(void)
Re-initialize (re-seed) the generator using platform-specific randomization.
Definition: random_gen.cpp:267
TValue x_GetSysRand32Bits(void) const
Definition: random_gen.cpp:323
@ eGetRand_Sys
Use system-dependent random generator.
Definition: random_gen.hpp:74
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
static enable_if< is_arithmetic< TNumeric >::value||is_convertible< TNumeric, Int8 >::value, string >::type NumericToString(TNumeric value, TNumToStringFlags flags=0, int base=10)
Convert numeric value to string.
Definition: ncbistr.hpp:673
static TID GetSelf(void)
Definition: ncbithr.cpp:515
long NanoSecond(void) const
Get nano-seconds.
Definition: ncbitime.hpp:2289
int Second(void) const
Get second.
Definition: ncbitime.hpp:2280
@ eCurrent
Use current time. See also CCurrentTime.
Definition: ncbitime.hpp:300
int i
const struct ncbi::grid::netcache::search::fields::SIZE size
const GenericPointer< typename T::ValueType > T2 value
Definition: pointer.h:1227
Defines process management classes.
Static variables safety - create on demand, destroy on application termination.
Defines NCBI C++ diagnostic APIs, classes, and macros.
Multi-threading – classes, functions, and features.
Defines: CTimeFormat - storage class for time format.
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
char * strerror(int n)
Definition: pcre2grep.c:1177
static CSafeStatic< CRandomSupplier > s_RandomSupplier
Definition: random_gen.cpp:211
static const char * kHardwareGeneratorDevice
Definition: random_gen.cpp:102
static const char * kSoftwareGeneratorDevice
Definition: random_gen.cpp:103
static const size_t kStateOffset
Definition: random_gen.cpp:98
unsigned int DWORD
Definition: sqltypes.h:98
#define _ASSERT
static int seed
Definition: test_table.cpp:132
Modified on Fri Sep 20 14:57:40 2024 by modify_doxy.py rev. 669887