1 /*

     2 ** 2001 September 15

     3 **

     4 ** The author disclaims copyright to this source code.  In place of

     5 ** a legal notice, here is a blessing:

     6 **

     7 **    May you do good and not evil.

     8 **    May you find forgiveness for yourself and forgive others.

     9 **    May you share freely, never taking more than you give.

    10 **

    11 *************************************************************************

    12 ** This file contains code to implement a pseudo-random number

    13 ** generator (PRNG) for SQLite.

    14 **

    15 ** Random numbers are used by some of the database backends in order

    16 ** to generate random integer keys for tables or random filenames.

    17 **

    18 ** $Id: random.cpp 1282 2008-11-13 09:31:33Z LarsPson $

    19 */

    20 #include "sqliteInt.h"

    21 

    22 

    23 /*

    24 ** Get a single 8-bit random value from the RC4 PRNG.  The Mutex

    25 ** must be held while executing this routine.

    26 **

    27 ** Why not just use a library random generator like lrand48() for this?

    28 ** Because the OP_NewRowid opcode in the VDBE depends on having a very

    29 ** good source of random numbers.  The lrand48() library function may

    30 ** well be good enough.  But maybe not.  Or maybe lrand48() has some

    31 ** subtle problems on some systems that could cause problems.  It is hard

    32 ** to know.  To minimize the risk of problems due to bad lrand48()

    33 ** implementations, SQLite uses this random number generator based

    34 ** on RC4, which we know works very well.

    35 **

    36 ** (Later):  Actually, OP_NewRowid does not depend on a good source of

    37 ** randomness any more.  But we will leave this code in all the same.

    38 */

    39 static int randomByte(void){

    40   unsigned char t;

    41 

    42   /* All threads share a single random number generator.

    43   ** This structure is the current state of the generator.

    44   */

    45   static struct {

    46     unsigned char isInit;          /* True if initialized */

    47     unsigned char i, j;            /* State variables */

    48     unsigned char s[256];          /* State variables */

    49   } prng;

    50 

    51   /* Initialize the state of the random number generator once,

    52   ** the first time this routine is called.  The seed value does

    53   ** not need to contain a lot of randomness since we are not

    54   ** trying to do secure encryption or anything like that...

    55   **

    56   ** Nothing in this file or anywhere else in SQLite does any kind of

    57   ** encryption.  The RC4 algorithm is being used as a PRNG (pseudo-random

    58   ** number generator) not as an encryption device.

    59   */

    60   if( !prng.isInit ){

    61     int i;

    62     char k[256];

    63     prng.j = 0;

    64     prng.i = 0;

    65     sqlite3OsRandomness(sqlite3_vfs_find(0), 256, k);

    66     for(i=0; i<256; i++){

    67       prng.s[i] = i;

    68     }

    69     for(i=0; i<256; i++){

    70       prng.j += prng.s[i] + k[i];

    71       t = prng.s[prng.j];

    72       prng.s[prng.j] = prng.s[i];

    73       prng.s[i] = t;

    74     }

    75     prng.isInit = 1;

    76   }

    77 

    78   /* Generate and return single random byte

    79   */

    80   prng.i++;

    81   t = prng.s[prng.i];

    82   prng.j += t;

    83   prng.s[prng.i] = prng.s[prng.j];

    84   prng.s[prng.j] = t;

    85   t += prng.s[prng.i];

    86   return prng.s[t];

    87 }

    88 

    89 /*

    90 ** Return N random bytes.

    91 */

    92 void sqlite3Randomness(int N, void *pBuf){

    93   unsigned char *zBuf = (unsigned char*)pBuf;

    94   static sqlite3_mutex *mutex = 0;

    95   if( mutex==0 ){

    96     mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_PRNG);

    97   }

    98   sqlite3_mutex_enter(mutex);

    99   while( N-- ){

   100     *(zBuf++) = randomByte();

   101   }

   102   sqlite3_mutex_leave(mutex);

   103 }