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.c,v 1.27 2008/10/07 15:25:48 drh Exp $

    19 */

    20 #include "sqliteInt.h"

    21 

    22 

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

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

    25 */

    26 static SQLITE_WSD struct sqlite3PrngType {

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

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

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

    30 } sqlite3Prng = { 0, };

    31 

    32 /*

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

    34 ** must be held while executing this routine.

    35 **

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

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

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

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

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

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

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

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

    44 **

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

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

    47 */

    48 static int randomByte(void){

    49   unsigned char t;

    50 

    51 

    52   /* The "wsdPrng" macro will resolve to the pseudo-random number generator

    53   ** state vector.  If writable static data is unsupported on the target,

    54   ** we have to locate the state vector at run-time.  In the more common

    55   ** case where writable static data is supported, wsdPrng can refer directly

    56   ** to the "sqlite3Prng" state vector declared above.

    57   */

    58 #ifdef SQLITE_OMIT_WSD

    59   struct sqlite3PrngType *p = &GLOBAL(struct sqlite3PrngType, sqlite3Prng);

    60 # define wsdPrng p[0]

    61 #else

    62 # define wsdPrng sqlite3Prng

    63 #endif

    64 

    65 

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

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

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

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

    70   **

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

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

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

    74   */

    75   if( !wsdPrng.isInit ){

    76     int i;

    77     char k[256];

    78     wsdPrng.j = 0;

    79     wsdPrng.i = 0;

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

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

    82       wsdPrng.s[i] = i;

    83     }

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

    85       wsdPrng.j += wsdPrng.s[i] + k[i];

    86       t = wsdPrng.s[wsdPrng.j];

    87       wsdPrng.s[wsdPrng.j] = wsdPrng.s[i];

    88       wsdPrng.s[i] = t;

    89     }

    90     wsdPrng.isInit = 1;

    91   }

    92 

    93   /* Generate and return single random byte

    94   */

    95   wsdPrng.i++;

    96   t = wsdPrng.s[wsdPrng.i];

    97   wsdPrng.j += t;

    98   wsdPrng.s[wsdPrng.i] = wsdPrng.s[wsdPrng.j];

    99   wsdPrng.s[wsdPrng.j] = t;

   100   t += wsdPrng.s[wsdPrng.i];

   101   return wsdPrng.s[t];

   102 }

   103 

   104 /*

   105 ** Return N random bytes.

   106 */

   107 void sqlite3_randomness(int N, void *pBuf){

   108   unsigned char *zBuf = pBuf;

   109 #if SQLITE_THREADSAFE

   110   sqlite3_mutex *mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PRNG);

   111 #endif

   112   sqlite3_mutex_enter(mutex);

   113   while( N-- ){

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

   115   }

   116   sqlite3_mutex_leave(mutex);

   117 }

   118 

   119 #ifndef SQLITE_OMIT_BUILTIN_TEST

   120 /*

   121 ** For testing purposes, we sometimes want to preserve the state of

   122 ** PRNG and restore the PRNG to its saved state at a later time, or

   123 ** to reset the PRNG to its initial state.  These routines accomplish

   124 ** those tasks.

   125 **

   126 ** The sqlite3_test_control() interface calls these routines to

   127 ** control the PRNG.

   128 */

   129 static SQLITE_WSD struct sqlite3PrngType sqlite3SavedPrng = { 0, };

   130 void sqlite3PrngSaveState(void){

   131   memcpy(

   132     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),

   133     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),

   134     sizeof(sqlite3Prng)

   135   );

   136 }

   137 void sqlite3PrngRestoreState(void){

   138   memcpy(

   139     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),

   140     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),

   141     sizeof(sqlite3Prng)

   142   );

   143 }

   144 void sqlite3PrngResetState(void){

   145   GLOBAL(struct sqlite3PrngType, sqlite3Prng).isInit = 0;

   146 }

   147 #endif /* SQLITE_OMIT_BUILTIN_TEST */