src/random.c

   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 ** Return N random bytes.
  32 */
  33 void sqlite3_randomness(int N, void *pBuf){
  34   unsigned char t;
  35   unsigned char *zBuf = pBuf;
  36
  37   /* The "wsdPrng" macro will resolve to the pseudo-random number generator
  38   ** state vector.  If writable static data is unsupported on the target,
  39   ** we have to locate the state vector at run-time.  In the more common
  40   ** case where writable static data is supported, wsdPrng can refer directly
  41   ** to the "sqlite3Prng" state vector declared above.
  42   */
  43 #ifdef SQLITE_OMIT_WSD
  44   struct sqlite3PrngType *p = &GLOBAL(struct sqlite3PrngType, sqlite3Prng);
  45 # define wsdPrng p[0]
  46 #else
  47 # define wsdPrng sqlite3Prng
  48 #endif
  49
  50 #if SQLITE_THREADSAFE
  51   sqlite3_mutex *mutex;
  52 #endif
  53
  54 #ifndef SQLITE_OMIT_AUTOINIT
  55   if( sqlite3_initialize() ) return;
  56 #endif
  57
  58 #if SQLITE_THREADSAFE
  59   mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PRNG);
  60 #endif
  61
  62   sqlite3_mutex_enter(mutex);
  63   if( N<=0 || pBuf==0 ){
  64     wsdPrng.isInit = 0;
  65     sqlite3_mutex_leave(mutex);
  66     return;
  67   }
  68
  69   /* Initialize the state of the random number generator once,
  70   ** the first time this routine is called.  The seed value does
  71   ** not need to contain a lot of randomness since we are not
  72   ** trying to do secure encryption or anything like that...
  73   **
  74   ** Nothing in this file or anywhere else in SQLite does any kind of
  75   ** encryption.  The RC4 algorithm is being used as a PRNG (pseudo-random
  76   ** number generator) not as an encryption device.
  77   */
  78   if( !wsdPrng.isInit ){
  79     sqlite3_vfs *pVfs = sqlite3_vfs_find(0);
  80     int i;
  81     char k[256];
  82     wsdPrng.j = 0;
  83     wsdPrng.i = 0;
  84     if( NEVER(pVfs==0) ){
  85       memset(k, 0, sizeof(k));
  86     }else{
  87       sqlite3OsRandomness(pVfs, 256, k);
  88     }
  89     for(i=0; i<256; i++){
  90       wsdPrng.s[i] = (u8)i;
  91     }
  92     for(i=0; i<256; i++){
  93       wsdPrng.j += wsdPrng.s[i] + k[i];
  94       t = wsdPrng.s[wsdPrng.j];
  95       wsdPrng.s[wsdPrng.j] = wsdPrng.s[i];
  96       wsdPrng.s[i] = t;
  97     }
  98     wsdPrng.isInit = 1;
  99   }
 100
 101   assert( N>0 );
 102   do{
 103     wsdPrng.i++;
 104     t = wsdPrng.s[wsdPrng.i];
 105     wsdPrng.j += t;
 106     wsdPrng.s[wsdPrng.i] = wsdPrng.s[wsdPrng.j];
 107     wsdPrng.s[wsdPrng.j] = t;
 108     t += wsdPrng.s[wsdPrng.i];
 109     *(zBuf++) = wsdPrng.s[t];
 110   }while( --N );
 111   sqlite3_mutex_leave(mutex);
 112 }
 113
 114 #ifndef SQLITE_UNTESTABLE
 115 /*
 116 ** For testing purposes, we sometimes want to preserve the state of
 117 ** PRNG and restore the PRNG to its saved state at a later time, or
 118 ** to reset the PRNG to its initial state.  These routines accomplish
 119 ** those tasks.
 120 **
 121 ** The sqlite3_test_control() interface calls these routines to
 122 ** control the PRNG.
 123 */
 124 static SQLITE_WSD struct sqlite3PrngType sqlite3SavedPrng;
 125 void sqlite3PrngSaveState(void){
 126   memcpy(
 127     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
 128     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
 129     sizeof(sqlite3Prng)
 130   );
 131 }
 132 void sqlite3PrngRestoreState(void){
 133   memcpy(
 134     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
 135     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
 136     sizeof(sqlite3Prng)
 137   );
 138 }
 139 #endif /* SQLITE_UNTESTABLE */