sl@0: /*
sl@0: ** 2001 September 15
sl@0: **
sl@0: ** The author disclaims copyright to this source code.  In place of
sl@0: ** a legal notice, here is a blessing:
sl@0: **
sl@0: **    May you do good and not evil.
sl@0: **    May you find forgiveness for yourself and forgive others.
sl@0: **    May you share freely, never taking more than you give.
sl@0: **
sl@0: *************************************************************************
sl@0: ** This file contains code to implement a pseudo-random number
sl@0: ** generator (PRNG) for SQLite.
sl@0: **
sl@0: ** Random numbers are used by some of the database backends in order
sl@0: ** to generate random integer keys for tables or random filenames.
sl@0: **
sl@0: ** $Id: random.c,v 1.27 2008/10/07 15:25:48 drh Exp $
sl@0: */
sl@0: #include "sqliteInt.h"
sl@0: 
sl@0: 
sl@0: /* All threads share a single random number generator.
sl@0: ** This structure is the current state of the generator.
sl@0: */
sl@0: static SQLITE_WSD struct sqlite3PrngType {
sl@0:   unsigned char isInit;          /* True if initialized */
sl@0:   unsigned char i, j;            /* State variables */
sl@0:   unsigned char s[256];          /* State variables */
sl@0: } sqlite3Prng = { 0, };
sl@0: 
sl@0: /*
sl@0: ** Get a single 8-bit random value from the RC4 PRNG.  The Mutex
sl@0: ** must be held while executing this routine.
sl@0: **
sl@0: ** Why not just use a library random generator like lrand48() for this?
sl@0: ** Because the OP_NewRowid opcode in the VDBE depends on having a very
sl@0: ** good source of random numbers.  The lrand48() library function may
sl@0: ** well be good enough.  But maybe not.  Or maybe lrand48() has some
sl@0: ** subtle problems on some systems that could cause problems.  It is hard
sl@0: ** to know.  To minimize the risk of problems due to bad lrand48()
sl@0: ** implementations, SQLite uses this random number generator based
sl@0: ** on RC4, which we know works very well.
sl@0: **
sl@0: ** (Later):  Actually, OP_NewRowid does not depend on a good source of
sl@0: ** randomness any more.  But we will leave this code in all the same.
sl@0: */
sl@0: static int randomByte(void){
sl@0:   unsigned char t;
sl@0: 
sl@0: 
sl@0:   /* The "wsdPrng" macro will resolve to the pseudo-random number generator
sl@0:   ** state vector.  If writable static data is unsupported on the target,
sl@0:   ** we have to locate the state vector at run-time.  In the more common
sl@0:   ** case where writable static data is supported, wsdPrng can refer directly
sl@0:   ** to the "sqlite3Prng" state vector declared above.
sl@0:   */
sl@0: #ifdef SQLITE_OMIT_WSD
sl@0:   struct sqlite3PrngType *p = &GLOBAL(struct sqlite3PrngType, sqlite3Prng);
sl@0: # define wsdPrng p[0]
sl@0: #else
sl@0: # define wsdPrng sqlite3Prng
sl@0: #endif
sl@0: 
sl@0: 
sl@0:   /* Initialize the state of the random number generator once,
sl@0:   ** the first time this routine is called.  The seed value does
sl@0:   ** not need to contain a lot of randomness since we are not
sl@0:   ** trying to do secure encryption or anything like that...
sl@0:   **
sl@0:   ** Nothing in this file or anywhere else in SQLite does any kind of
sl@0:   ** encryption.  The RC4 algorithm is being used as a PRNG (pseudo-random
sl@0:   ** number generator) not as an encryption device.
sl@0:   */
sl@0:   if( !wsdPrng.isInit ){
sl@0:     int i;
sl@0:     char k[256];
sl@0:     wsdPrng.j = 0;
sl@0:     wsdPrng.i = 0;
sl@0:     sqlite3OsRandomness(sqlite3_vfs_find(0), 256, k);
sl@0:     for(i=0; i<256; i++){
sl@0:       wsdPrng.s[i] = i;
sl@0:     }
sl@0:     for(i=0; i<256; i++){
sl@0:       wsdPrng.j += wsdPrng.s[i] + k[i];
sl@0:       t = wsdPrng.s[wsdPrng.j];
sl@0:       wsdPrng.s[wsdPrng.j] = wsdPrng.s[i];
sl@0:       wsdPrng.s[i] = t;
sl@0:     }
sl@0:     wsdPrng.isInit = 1;
sl@0:   }
sl@0: 
sl@0:   /* Generate and return single random byte
sl@0:   */
sl@0:   wsdPrng.i++;
sl@0:   t = wsdPrng.s[wsdPrng.i];
sl@0:   wsdPrng.j += t;
sl@0:   wsdPrng.s[wsdPrng.i] = wsdPrng.s[wsdPrng.j];
sl@0:   wsdPrng.s[wsdPrng.j] = t;
sl@0:   t += wsdPrng.s[wsdPrng.i];
sl@0:   return wsdPrng.s[t];
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return N random bytes.
sl@0: */
sl@0: void sqlite3_randomness(int N, void *pBuf){
sl@0:   unsigned char *zBuf = pBuf;
sl@0: #if SQLITE_THREADSAFE
sl@0:   sqlite3_mutex *mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PRNG);
sl@0: #endif
sl@0:   sqlite3_mutex_enter(mutex);
sl@0:   while( N-- ){
sl@0:     *(zBuf++) = randomByte();
sl@0:   }
sl@0:   sqlite3_mutex_leave(mutex);
sl@0: }
sl@0: 
sl@0: #ifndef SQLITE_OMIT_BUILTIN_TEST
sl@0: /*
sl@0: ** For testing purposes, we sometimes want to preserve the state of
sl@0: ** PRNG and restore the PRNG to its saved state at a later time, or
sl@0: ** to reset the PRNG to its initial state.  These routines accomplish
sl@0: ** those tasks.
sl@0: **
sl@0: ** The sqlite3_test_control() interface calls these routines to
sl@0: ** control the PRNG.
sl@0: */
sl@0: static SQLITE_WSD struct sqlite3PrngType sqlite3SavedPrng = { 0, };
sl@0: void sqlite3PrngSaveState(void){
sl@0:   memcpy(
sl@0:     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
sl@0:     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
sl@0:     sizeof(sqlite3Prng)
sl@0:   );
sl@0: }
sl@0: void sqlite3PrngRestoreState(void){
sl@0:   memcpy(
sl@0:     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
sl@0:     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
sl@0:     sizeof(sqlite3Prng)
sl@0:   );
sl@0: }
sl@0: void sqlite3PrngResetState(void){
sl@0:   GLOBAL(struct sqlite3PrngType, sqlite3Prng).isInit = 0;
sl@0: }
sl@0: #endif /* SQLITE_OMIT_BUILTIN_TEST */