Home | History | Annotate | Download | only in src 
      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 #include "sqliteInt.h"
     19 
     20 
     21 /* All threads share a single random number generator.
     22 ** This structure is the current state of the generator.
     23 */
     24 static SQLITE_WSD struct sqlite3PrngType {
     25   unsigned char isInit;          /* True if initialized */
     26   unsigned char i, j;            /* State variables */
     27   unsigned char s[256];          /* State variables */
     28 } sqlite3Prng;
     29 
     30 /*
     31 ** Get a single 8-bit random value from the RC4 PRNG.  The Mutex
     32 ** must be held while executing this routine.
     33 **
     34 ** Why not just use a library random generator like lrand48() for this?
     35 ** Because the OP_NewRowid opcode in the VDBE depends on having a very
     36 ** good source of random numbers.  The lrand48() library function may
     37 ** well be good enough.  But maybe not.  Or maybe lrand48() has some
     38 ** subtle problems on some systems that could cause problems.  It is hard
     39 ** to know.  To minimize the risk of problems due to bad lrand48()
     40 ** implementations, SQLite uses this random number generator based
     41 ** on RC4, which we know works very well.
     42 **
     43 ** (Later):  Actually, OP_NewRowid does not depend on a good source of
     44 ** randomness any more.  But we will leave this code in all the same.
     45 */
     46 static u8 randomByte(void){
     47   unsigned char t;
     48 
     49 
     50   /* The "wsdPrng" macro will resolve to the pseudo-random number generator
     51   ** state vector.  If writable static data is unsupported on the target,
     52   ** we have to locate the state vector at run-time.  In the more common
     53   ** case where writable static data is supported, wsdPrng can refer directly
     54   ** to the "sqlite3Prng" state vector declared above.
     55   */
     56 #ifdef SQLITE_OMIT_WSD
     57   struct sqlite3PrngType *p = &GLOBAL(struct sqlite3PrngType, sqlite3Prng);
     58 # define wsdPrng p[0]
     59 #else
     60 # define wsdPrng sqlite3Prng
     61 #endif
     62 
     63 
     64   /* Initialize the state of the random number generator once,
     65   ** the first time this routine is called.  The seed value does
     66   ** not need to contain a lot of randomness since we are not
     67   ** trying to do secure encryption or anything like that...
     68   **
     69   ** Nothing in this file or anywhere else in SQLite does any kind of
     70   ** encryption.  The RC4 algorithm is being used as a PRNG (pseudo-random
     71   ** number generator) not as an encryption device.
     72   */
     73   if( !wsdPrng.isInit ){
     74     int i;
     75     char k[256];
     76     wsdPrng.j = 0;
     77     wsdPrng.i = 0;
     78     sqlite3OsRandomness(sqlite3_vfs_find(0), 256, k);
     79     for(i=0; i<256; i++){
     80       wsdPrng.s[i] = (u8)i;
     81     }
     82     for(i=0; i<256; i++){
     83       wsdPrng.j += wsdPrng.s[i] + k[i];
     84       t = wsdPrng.s[wsdPrng.j];
     85       wsdPrng.s[wsdPrng.j] = wsdPrng.s[i];
     86       wsdPrng.s[i] = t;
     87     }
     88     wsdPrng.isInit = 1;
     89   }
     90 
     91   /* Generate and return single random byte
     92   */
     93   wsdPrng.i++;
     94   t = wsdPrng.s[wsdPrng.i];
     95   wsdPrng.j += t;
     96   wsdPrng.s[wsdPrng.i] = wsdPrng.s[wsdPrng.j];
     97   wsdPrng.s[wsdPrng.j] = t;
     98   t += wsdPrng.s[wsdPrng.i];
     99   return wsdPrng.s[t];
    100 }
    101 
    102 /*
    103 ** Return N random bytes.
    104 */
    105 void sqlite3_randomness(int N, void *pBuf){
    106   unsigned char *zBuf = pBuf;
    107 #if SQLITE_THREADSAFE
    108   sqlite3_mutex *mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PRNG);
    109 #endif
    110   sqlite3_mutex_enter(mutex);
    111   while( N-- ){
    112     *(zBuf++) = randomByte();
    113   }
    114   sqlite3_mutex_leave(mutex);
    115 }
    116 
    117 #ifndef SQLITE_OMIT_BUILTIN_TEST
    118 /*
    119 ** For testing purposes, we sometimes want to preserve the state of
    120 ** PRNG and restore the PRNG to its saved state at a later time, or
    121 ** to reset the PRNG to its initial state.  These routines accomplish
    122 ** those tasks.
    123 **
    124 ** The sqlite3_test_control() interface calls these routines to
    125 ** control the PRNG.
    126 */
    127 static SQLITE_WSD struct sqlite3PrngType sqlite3SavedPrng;
    128 void sqlite3PrngSaveState(void){
    129   memcpy(
    130     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
    131     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
    132     sizeof(sqlite3Prng)
    133   );
    134 }
    135 void sqlite3PrngRestoreState(void){
    136   memcpy(
    137     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
    138     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
    139     sizeof(sqlite3Prng)
    140   );
    141 }
    142 void sqlite3PrngResetState(void){
    143   GLOBAL(struct sqlite3PrngType, sqlite3Prng).isInit = 0;
    144 }
    145 #endif /* SQLITE_OMIT_BUILTIN_TEST */
    146