mux/src/svdrand.cpp

Go to the documentation of this file.

// svdrand.cpp -- Random Numbers.
//
// $Id: svdrand.cpp,v 1.7 2006/01/07 07:44:46 sdennis Exp $
//
// MUX 2.4
// Copyright (C) 1998 through 2004 Solid Vertical Domains, Ltd. All
// rights not explicitly given are reserved.
//
// Random Numbers from Makoto Matsumoto and Takuji Nishimura.
//
#include "copyright.h"
#include "autoconf.h"
#include "config.h"
#include "externs.h"

#include "timeutil.h"

#include "svdhash.h"
#include "svdrand.h"

#ifdef WIN32
#include <wincrypt.h>
typedef BOOL WINAPI FCRYPTACQUIRECONTEXT(HCRYPTPROV *, LPCTSTR, LPCTSTR, DWORD, DWORD);
typedef BOOL WINAPI FCRYPTRELEASECONTEXT(HCRYPTPROV, DWORD);
typedef BOOL WINAPI FCRYPTGENRANDOM(HCRYPTPROV, DWORD, BYTE *);
#else // WIN32
#include <sys/stat.h>
#include <sys/types.h>
#include <fcntl.h>
#include <unistd.h>
#endif // WIN32

// Seed the generator.
//
static void sgenrand(UINT32);
static void sgenrand_from_array(UINT32 *, int);

// Returns a random 32-bit integer.
//
static UINT32 genrand(void);

#define NUM_RANDOM_UINT32 1024

bool bCryptoAPI = false;
static bool bSeeded = false;
void SeedRandomNumberGenerator(void)
{
    if (bSeeded) return;
    bSeeded = true;

    UINT32 aRandomSystemBytes[NUM_RANDOM_UINT32];
    unsigned int nRandomSystemBytes = 0;

#ifdef HAVE_DEV_URANDOM
    // Try to seed the PRNG from /dev/urandom
    // If it doesn't work, just seed the normal way
    //
    int fd = open("/dev/urandom", O_RDONLY);

    if (fd >= 0)
    {
        int len = read(fd, aRandomSystemBytes, sizeof aRandomSystemBytes);
        close(fd);
        if (len > 0)
        {
            nRandomSystemBytes = len/sizeof(UINT32);
        }
    }
#endif // HAVE_DEV_URANDOM
#ifdef WIN32
    // The Cryto API became available on Windows with Win95 OSR2. Using Crypto
    // API as follows lets us to fallback gracefully when running on pre-OSR2
    // Win95.
    //
    bCryptoAPI = false;
    HINSTANCE hAdvAPI32 = LoadLibrary("advapi32");
    if (hAdvAPI32)
    {
        FCRYPTACQUIRECONTEXT *fpCryptAcquireContext;
        FCRYPTRELEASECONTEXT *fpCryptReleaseContext;
        FCRYPTGENRANDOM *fpCryptGenRandom;

        // Find the entry points for CryptoAcquireContext, CrytpoGenRandom,
        // and CryptoReleaseContext.
        //
        fpCryptAcquireContext = (FCRYPTACQUIRECONTEXT *)
            GetProcAddress(hAdvAPI32, "CryptAcquireContextA");
        fpCryptReleaseContext = (FCRYPTRELEASECONTEXT *)
            GetProcAddress(hAdvAPI32, "CryptReleaseContext");
        fpCryptGenRandom = (FCRYPTGENRANDOM *)
            GetProcAddress(hAdvAPI32, "CryptGenRandom");

        if (  fpCryptAcquireContext
           && fpCryptReleaseContext
           && fpCryptGenRandom)
        {
            HCRYPTPROV hProv;

            if (  fpCryptAcquireContext(&hProv, NULL, NULL, PROV_DSS, 0)
               || fpCryptAcquireContext(&hProv, NULL, NULL, PROV_DSS, CRYPT_NEWKEYSET))
            {
                if (fpCryptGenRandom(hProv, sizeof aRandomSystemBytes,
                    (BYTE *)aRandomSystemBytes))
                {
                    nRandomSystemBytes = NUM_RANDOM_UINT32;
                    bCryptoAPI = true;
                }
                fpCryptReleaseContext(hProv, 0);
            }
        }
        FreeLibrary(hAdvAPI32);
    }
#endif // WIN32

    if (nRandomSystemBytes >= sizeof(UINT32))
    {
        unsigned int i;
        for (i = 0; i < nRandomSystemBytes; i++)
        {
            aRandomSystemBytes[i] &= 0xFFFFFFFFUL;
        }
        sgenrand_from_array(aRandomSystemBytes, nRandomSystemBytes);
        return;
    }

    // Determine the initial seed.
    //
    CLinearTimeAbsolute lsaNow;
    lsaNow.GetUTC();
    INT64 i64Seed = lsaNow.Return100ns();
    int pid = getpid();

    UINT32 nSeed = CRC32_ProcessBuffer(0, &i64Seed, sizeof(INT64));
    nSeed = CRC32_ProcessBuffer(nSeed, &pid, sizeof(pid));

    if (nSeed <= 1000)
    {
        nSeed += 22261048;
    }

    // ASSERT: 1000 < nSeed

    sgenrand(nSeed);
}

// RandomINT32 -- return a long on the interval [lLow, lHigh]
//
INT32 RandomINT32(INT32 lLow, INT32 lHigh)
{
    // Validate parameters
    //
    if (lHigh < lLow)
    {
        return -1;
    }
    else if (lHigh == lLow)
    {
        return lLow;
    }

    UINT32 x = lHigh-lLow;
    if (INT32_MAX_VALUE < x)
    {
        return -1;
    }
    x++;

    // We can now look for an random number on the interval [0,x-1].
    //

    // In order to be perfectly conservative about not introducing any
    // further sources of statistical bias, we're going to call getrand()
    // until we get a number less than the greatest representable
    // multiple of x. We'll then return n mod x.
    //
    // N.B. This loop happens in randomized constant time, and pretty
    // damn fast randomized constant time too, since
    //
    //      P(UINT32_MAX_VALUE - n < UINT32_MAX_VALUE % x) < 0.5, for any x.
    //
    // So even for the least desireable x, the average number of times
    // we will call getrand() is less than 2.
    //
    UINT32 n;
    UINT32 nLimit = UINT32_MAX_VALUE - (UINT32_MAX_VALUE%x);

    do
    {
        n = genrand();
    } while (n >= nLimit);

    return lLow + (n % x);
}

/* A C-program for MT19937, with initialization improved 2002/2/10.*/
/* Coded by Takuji Nishimura and Makoto Matsumoto.                 */
/* This is a faster version by taking Shawn Cokus's optimization,  */
/* Matthe Bellew's simplification, Isaku Wada's real version.      */

/* Before using, initialize the state by using init_genrand(seed)  */
/* or init_by_array(init_key, key_length).                         */

/* This library is free software.                                  */
/* This library is distributed in the hope that it will be useful, */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of  */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.            */

/* Copyright (C) 1997, 2002 Makoto Matsumoto and Takuji Nishimura. */
/* Any feedback is very welcome.                                   */
/* http://www.math.keio.ac.jp/matumoto/emt.html                    */
/* email: matumoto@math.keio.ac.jp                                 */

#define N 624
#define M 397
#define MATRIX_A 0x9908b0dfUL
#define UMASK 0x80000000UL // most significant w-r bits
#define LMASK 0x7fffffffUL // least significant r bits
#define MIXBITS(u,v) ( ((u) & UMASK) | ((v) & LMASK) )
#define TWIST(u,v) ((MIXBITS(u,v) >> 1) ^ ((v)&1UL ? MATRIX_A : 0UL))

static UINT32 mt[N];
static int left = 1;
static UINT32 *next;

// initializes mt[N] with a seed.
//
static void sgenrand(UINT32 nSeed)
{
    int j;
    mt[0] = nSeed & 0xffffffffUL;
    for (j = 1; j < N; j++)
    {
        // See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier.
        // In the previous versions, MSBs of the seed affect
        // only MSBs of the array mt[].
        // 2002/01/09 modified by Makoto Matsumoto.
        //
        mt[j] = 1812433253UL * (mt[j-1] ^ (mt[j-1] >> 30)) + j;
        mt[j] &= 0xffffffffUL;  // for >32 bit machines.
    }
    left = 1;
}

// initialize by an array with array-length
// init_key is the array for initializing keys
// key_length is its length
//
static void sgenrand_from_array(UINT32 *init_key, int key_length)
{
    sgenrand(19650218UL);
    int i = 1;
    int j = 0;
    int k = (N > key_length ? N : key_length);
    for (; k; k--)
    {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
              + init_key[j] + j;
        mt[i] &= 0xffffffffUL; // for > 32-bit machines.
        i++;
        j++;
        if (i >= N)
        {
            mt[0] = mt[N-1];
            i = 1;
        }
        if (j >= key_length)
        {
            j = 0;
        }
    }
    for (k = N-1; k; k--)
    {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL)) - i;
        mt[i] &= 0xffffffffUL; // for > 32-bit machines.
        i++;
        if (i >= N)
        {
            mt[0] = mt[N-1];
            i = 1;
        }
    }

    mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
    left = 1;
}

static void next_state(void)
{
    UINT32 *p = mt;
    int j;

    if (!bSeeded)
    {
        SeedRandomNumberGenerator();
    }

    for (j = N-M+1; --j; p++)
    {
        *p = p[M] ^ TWIST(p[0], p[1]);
    }

    for (j = M; --j; p++)
    {
        *p = p[M-N] ^ TWIST(p[0], p[1]);
    }

    *p = p[M-N] ^ TWIST(p[0], mt[0]);

    left = N;
    next = mt;
}

// generates a random number on the interval [0,0xffffffff]
//
static UINT32 genrand(void)
{
    UINT32 y;

    if (--left == 0)
    {
        next_state();
    }
    y = *next++;

    // Tempering.
    //
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
}

---