src/third_party/sqlite/src/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 ** 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 */