ds@1952: /*
ds@1952: ** 2001 September 15
ds@1952: **
ds@1952: ** The author disclaims copyright to this source code.  In place of
ds@1952: ** a legal notice, here is a blessing:
ds@1952: **
ds@1952: **    May you do good and not evil.
ds@1952: **    May you find forgiveness for yourself and forgive others.
ds@1952: **    May you share freely, never taking more than you give.
ds@1952: **
ds@1952: *************************************************************************
ds@1952: ** This file contains code to implement a pseudo-random number
ds@1952: ** generator (PRNG) for SQLite.
ds@1952: **
ds@1952: ** Random numbers are used by some of the database backends in order
ds@1952: ** to generate random integer keys for tables or random filenames.
ds@1952: **
ds@1952: ** $Id$
ds@1952: */
ds@1952: #include "sqliteInt.h"
ds@1952: 
ds@1952: 
ds@1952: /*
ds@1952: ** Get a single 8-bit random value from the RC4 PRNG.  The Mutex
ds@1952: ** must be held while executing this routine.
ds@1952: **
ds@1952: ** Why not just use a library random generator like lrand48() for this?
ds@1952: ** Because the OP_NewRowid opcode in the VDBE depends on having a very
ds@1952: ** good source of random numbers.  The lrand48() library function may
ds@1952: ** well be good enough.  But maybe not.  Or maybe lrand48() has some
ds@1952: ** subtle problems on some systems that could cause problems.  It is hard
ds@1952: ** to know.  To minimize the risk of problems due to bad lrand48()
ds@1952: ** implementations, SQLite uses this random number generator based
ds@1952: ** on RC4, which we know works very well.
ds@1952: **
ds@1952: ** (Later):  Actually, OP_NewRowid does not depend on a good source of
ds@1952: ** randomness any more.  But we will leave this code in all the same.
ds@1952: */
ds@1952: static int randomByte(void){
ds@1952:   unsigned char t;
ds@1952: 
ds@1952:   /* All threads share a single random number generator.
ds@1952:   ** This structure is the current state of the generator.
ds@1952:   */
ds@1952:   static struct {
ds@1952:     unsigned char isInit;          /* True if initialized */
ds@1952:     unsigned char i, j;            /* State variables */
ds@1952:     unsigned char s[256];          /* State variables */
ds@1952:   } prng;
ds@1952: 
ds@1952:   /* Initialize the state of the random number generator once,
ds@1952:   ** the first time this routine is called.  The seed value does
ds@1952:   ** not need to contain a lot of randomness since we are not
ds@1952:   ** trying to do secure encryption or anything like that...
ds@1952:   **
ds@1952:   ** Nothing in this file or anywhere else in SQLite does any kind of
ds@1952:   ** encryption.  The RC4 algorithm is being used as a PRNG (pseudo-random
ds@1952:   ** number generator) not as an encryption device.
ds@1952:   */
ds@1952:   if( !prng.isInit ){
ds@1952:     int i;
ds@1952:     char k[256];
ds@1952:     prng.j = 0;
ds@1952:     prng.i = 0;
ds@1952:     sqlite3OsRandomness(sqlite3_vfs_find(0), 256, k);
ds@1952:     for(i=0; i<256; i++){
ds@1952:       prng.s[i] = i;
ds@1952:     }
ds@1952:     for(i=0; i<256; i++){
ds@1952:       prng.j += prng.s[i] + k[i];
ds@1952:       t = prng.s[prng.j];
ds@1952:       prng.s[prng.j] = prng.s[i];
ds@1952:       prng.s[i] = t;
ds@1952:     }
ds@1952:     prng.isInit = 1;
ds@1952:   }
ds@1952: 
ds@1952:   /* Generate and return single random byte
ds@1952:   */
ds@1952:   prng.i++;
ds@1952:   t = prng.s[prng.i];
ds@1952:   prng.j += t;
ds@1952:   prng.s[prng.i] = prng.s[prng.j];
ds@1952:   prng.s[prng.j] = t;
ds@1952:   t += prng.s[prng.i];
ds@1952:   return prng.s[t];
ds@1952: }
ds@1952: 
ds@1952: /*
ds@1952: ** Return N random bytes.
ds@1952: */
ds@1952: void sqlite3Randomness(int N, void *pBuf){
ds@1952:   unsigned char *zBuf = pBuf;
ds@1952:   static sqlite3_mutex *mutex = 0;
ds@1952:   if( mutex==0 ){
ds@1952:     mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_PRNG);
ds@1952:   }
ds@1952:   sqlite3_mutex_enter(mutex);
ds@1952:   while( N-- ){
ds@1952:     *(zBuf++) = randomByte();
ds@1952:   }
ds@1952:   sqlite3_mutex_leave(mutex);
ds@1952: }