MUX: mux/src/svdrand.cpp File Reference

00316 {
00317     UINT32 y;
00318 
00319     if (--left == 0)
00320     {
00321         next_state();
00322     }
00323     y = *next++;
00324 
00325     // Tempering.
00326     //
00327     y ^= (y >> 11);
00328     y ^= (y << 7) & 0x9d2c5680UL;
00329     y ^= (y << 15) & 0xefc60000UL;
00330     y ^= (y >> 18);
00331 
00332     return y;
00333 }

static void next_state ( void ) [static]

Definition at line 287 of file svdrand.cpp.

References bSeeded, left, M, mt, N, next, SeedRandomNumberGenerator(), and TWIST.

Referenced by genrand().

00288 {
00289     UINT32 *p = mt;
00290     int j;
00291 
00292     if (!bSeeded)
00293     {
00294         SeedRandomNumberGenerator();
00295     }
00296 
00297     for (j = N-M+1; --j; p++)
00298     {
00299         *p = p[M] ^ TWIST(p[0], p[1]);
00300     }
00301 
00302     for (j = M; --j; p++)
00303     {
00304         *p = p[M-N] ^ TWIST(p[0], p[1]);
00305     }
00306 
00307     *p = p[M-N] ^ TWIST(p[0], mt[0]);
00308 
00309     left = N;
00310     next = mt;
00311 }

INT32 RandomINT32	(	INT32	lLow,
		INT32	lHigh
	)

Definition at line 148 of file svdrand.cpp.

References genrand(), INT32_MAX_VALUE, and UINT32_MAX_VALUE.

Referenced by ChoosePrimes(), do_kill(), FUNCTION(), GenerateSalt(), move_object(), promote_match(), sane_qsort(), and setup_que().

00149 {
00150     // Validate parameters
00151     //
00152     if (lHigh < lLow)
00153     {
00154         return -1;
00155     }
00156     else if (lHigh == lLow)
00157     {
00158         return lLow;
00159     }
00160 
00161     UINT32 x = lHigh-lLow;
00162     if (INT32_MAX_VALUE < x)
00163     {
00164         return -1;
00165     }
00166     x++;
00167 
00168     // We can now look for an random number on the interval [0,x-1].
00169     //
00170 
00171     // In order to be perfectly conservative about not introducing any
00172     // further sources of statistical bias, we're going to call getrand()
00173     // until we get a number less than the greatest representable
00174     // multiple of x. We'll then return n mod x.
00175     //
00176     // N.B. This loop happens in randomized constant time, and pretty
00177     // damn fast randomized constant time too, since
00178     //
00179     //      P(UINT32_MAX_VALUE - n < UINT32_MAX_VALUE % x) < 0.5, for any x.
00180     //
00181     // So even for the least desireable x, the average number of times
00182     // we will call getrand() is less than 2.
00183     //
00184     UINT32 n;
00185     UINT32 nLimit = UINT32_MAX_VALUE - (UINT32_MAX_VALUE%x);
00186 
00187     do
00188     {
00189         n = genrand();
00190     } while (n >= nLimit);
00191 
00192     return lLow + (n % x);
00193 }

void SeedRandomNumberGenerator ( void )

Definition at line 46 of file svdrand.cpp.

References bCryptoAPI, bSeeded, CRC32_ProcessBuffer(), CLinearTimeAbsolute::GetUTC(), NUM_RANDOM_UINT32, CLinearTimeAbsolute::Return100ns(), sgenrand(), and sgenrand_from_array().

Referenced by CHashFile::CHashFile(), CHashTable::CHashTable(), dbconvert(), main(), and next_state().

00047 {
00048     if (bSeeded) return;
00049     bSeeded = true;
00050 
00051     UINT32 aRandomSystemBytes[NUM_RANDOM_UINT32];
00052     unsigned int nRandomSystemBytes = 0;
00053 
00054 #ifdef HAVE_DEV_URANDOM
00055     // Try to seed the PRNG from /dev/urandom
00056     // If it doesn't work, just seed the normal way
00057     //
00058     int fd = open("/dev/urandom", O_RDONLY);
00059 
00060     if (fd >= 0)
00061     {
00062         int len = read(fd, aRandomSystemBytes, sizeof aRandomSystemBytes);
00063         close(fd);
00064         if (len > 0)
00065         {
00066             nRandomSystemBytes = len/sizeof(UINT32);
00067         }
00068     }
00069 #endif // HAVE_DEV_URANDOM
00070 #ifdef WIN32
00071     // The Cryto API became available on Windows with Win95 OSR2. Using Crypto
00072     // API as follows lets us to fallback gracefully when running on pre-OSR2
00073     // Win95.
00074     //
00075     bCryptoAPI = false;
00076     HINSTANCE hAdvAPI32 = LoadLibrary("advapi32");
00077     if (hAdvAPI32)
00078     {
00079         FCRYPTACQUIRECONTEXT *fpCryptAcquireContext;
00080         FCRYPTRELEASECONTEXT *fpCryptReleaseContext;
00081         FCRYPTGENRANDOM *fpCryptGenRandom;
00082 
00083         // Find the entry points for CryptoAcquireContext, CrytpoGenRandom,
00084         // and CryptoReleaseContext.
00085         //
00086         fpCryptAcquireContext = (FCRYPTACQUIRECONTEXT *)
00087             GetProcAddress(hAdvAPI32, "CryptAcquireContextA");
00088         fpCryptReleaseContext = (FCRYPTRELEASECONTEXT *)
00089             GetProcAddress(hAdvAPI32, "CryptReleaseContext");
00090         fpCryptGenRandom = (FCRYPTGENRANDOM *)
00091             GetProcAddress(hAdvAPI32, "CryptGenRandom");
00092 
00093         if (  fpCryptAcquireContext
00094            && fpCryptReleaseContext
00095            && fpCryptGenRandom)
00096         {
00097             HCRYPTPROV hProv;
00098 
00099             if (  fpCryptAcquireContext(&hProv, NULL, NULL, PROV_DSS, 0)
00100                || fpCryptAcquireContext(&hProv, NULL, NULL, PROV_DSS, CRYPT_NEWKEYSET))
00101             {
00102                 if (fpCryptGenRandom(hProv, sizeof aRandomSystemBytes,
00103                     (BYTE *)aRandomSystemBytes))
00104                 {
00105                     nRandomSystemBytes = NUM_RANDOM_UINT32;
00106                     bCryptoAPI = true;
00107                 }
00108                 fpCryptReleaseContext(hProv, 0);
00109             }
00110         }
00111         FreeLibrary(hAdvAPI32);
00112     }
00113 #endif // WIN32
00114 
00115     if (nRandomSystemBytes >= sizeof(UINT32))
00116     {
00117         unsigned int i;
00118         for (i = 0; i < nRandomSystemBytes; i++)
00119         {
00120             aRandomSystemBytes[i] &= 0xFFFFFFFFUL;
00121         }
00122         sgenrand_from_array(aRandomSystemBytes, nRandomSystemBytes);
00123         return;
00124     }
00125 
00126     // Determine the initial seed.
00127     //
00128     CLinearTimeAbsolute lsaNow;
00129     lsaNow.GetUTC();
00130     INT64 i64Seed = lsaNow.Return100ns();
00131     int pid = getpid();
00132 
00133     UINT32 nSeed = CRC32_ProcessBuffer(0, &i64Seed, sizeof(INT64));
00134     nSeed = CRC32_ProcessBuffer(nSeed, &pid, sizeof(pid));
00135 
00136     if (nSeed <= 1000)
00137     {
00138         nSeed += 22261048;
00139     }
00140 
00141     // ASSERT: 1000 < nSeed
00142 
00143     sgenrand(nSeed);
00144 }

static void sgenrand ( UINT32 ) [static]

Definition at line 227 of file svdrand.cpp.

References left, mt, and N.

Referenced by SeedRandomNumberGenerator(), and sgenrand_from_array().

00228 {
00229     int j;
00230     mt[0] = nSeed & 0xffffffffUL;
00231     for (j = 1; j < N; j++)
00232     {
00233         // See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier.
00234         // In the previous versions, MSBs of the seed affect
00235         // only MSBs of the array mt[].
00236         // 2002/01/09 modified by Makoto Matsumoto.
00237         //
00238         mt[j] = 1812433253UL * (mt[j-1] ^ (mt[j-1] >> 30)) + j;
00239         mt[j] &= 0xffffffffUL;  // for >32 bit machines.
00240     }
00241     left = 1;
00242 }

static void sgenrand_from_array	(	UINT32 *	,
		int
	)			`[static]`

Definition at line 248 of file svdrand.cpp.

References left, mt, N, and sgenrand().

Referenced by SeedRandomNumberGenerator().

00249 {
00250     sgenrand(19650218UL);
00251     int i = 1;
00252     int j = 0;
00253     int k = (N > key_length ? N : key_length);
00254     for (; k; k--)
00255     {
00256         mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
00257               + init_key[j] + j;
00258         mt[i] &= 0xffffffffUL; // for > 32-bit machines.
00259         i++;
00260         j++;
00261         if (i >= N)
00262         {
00263             mt[0] = mt[N-1];
00264             i = 1;
00265         }
00266         if (j >= key_length)
00267         {
00268             j = 0;
00269         }
00270     }
00271     for (k = N-1; k; k--)
00272     {
00273         mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL)) - i;
00274         mt[i] &= 0xffffffffUL; // for > 32-bit machines.
00275         i++;
00276         if (i >= N)
00277         {
00278             mt[0] = mt[N-1];
00279             i = 1;
00280         }
00281     }
00282 
00283     mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
00284     left = 1;
00285 }

bool bCryptoAPI = false

Definition at line 44 of file svdrand.cpp.

Referenced by main(), and SeedRandomNumberGenerator().

bool bSeeded = false [static]

Definition at line 45 of file svdrand.cpp.

Referenced by next_state(), and SeedRandomNumberGenerator().

int left = 1 [static]

Definition at line 222 of file svdrand.cpp.

Referenced by add_to_output_queue(), genrand(), next_state(), queue_write_LEN(), safe_copy_buf(), sgenrand(), and sgenrand_from_array().

UINT32 mt[N] [static]

Definition at line 221 of file svdrand.cpp.

Referenced by next_state(), sgenrand(), and sgenrand_from_array().

UINT32* next [static]

Definition at line 223 of file svdrand.cpp.

Referenced by empty_obj(), genrand(), list_check(), match(), next_state(), process_sticky_dropto(), and stack_clr().

mux/src/svdrand.cpp File Reference

Defines

Functions

Variables

Define Documentation

Function Documentation

Variable Documentation


Defines
#define	NUM_RANDOM_UINT32 1024
#define	N 624
#define	M 397
#define	MATRIX_A 0x9908b0dfUL
#define	UMASK 0x80000000UL
#define	LMASK 0x7fffffffUL
#define	MIXBITS(u, v) ( ((u) & UMASK) \| ((v) & LMASK) )
#define	TWIST(u, v) ((MIXBITS(u,v) >> 1) ^ ((v)&1UL ? MATRIX_A : 0UL))
Functions
static void	sgenrand (UINT32)
static void	sgenrand_from_array (UINT32 *, int)
static UINT32	genrand (void)
void	SeedRandomNumberGenerator (void)
INT32	RandomINT32 (INT32 lLow, INT32 lHigh)
static void	next_state (void)
Variables
bool	bCryptoAPI = false
static bool	bSeeded = false
static UINT32	mt [N]
static int	left = 1
static UINT32 *	next