sqlite3/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 ** $Id$
  19 */
  20 #include "sqliteInt.h"
  21 #include "os.h"
  22
  23
  24 /*
  25 ** Get a single 8-bit random value from the RC4 PRNG.  The Mutex
  26 ** must be held while executing this routine.
  27 **
  28 ** Why not just use a library random generator like lrand48() for this?
  29 ** Because the OP_NewRowid opcode in the VDBE depends on having a very
  30 ** good source of random numbers.  The lrand48() library function may
  31 ** well be good enough.  But maybe not.  Or maybe lrand48() has some
  32 ** subtle problems on some systems that could cause problems.  It is hard
  33 ** to know.  To minimize the risk of problems due to bad lrand48()
  34 ** implementations, SQLite uses this random number generator based
  35 ** on RC4, which we know works very well.
  36 **
  37 ** (Later):  Actually, OP_NewRowid does not depend on a good source of
  38 ** randomness any more.  But we will leave this code in all the same.
  39 */
  40 static int randomByte(){
  41   unsigned char t;
  42
  43   /* All threads share a single random number generator.
  44   ** This structure is the current state of the generator.
  45   */
  46   static struct {
  47     unsigned char isInit;          /* True if initialized */
  48     unsigned char i, j;            /* State variables */
  49     unsigned char s[256];          /* State variables */
  50   } prng;
  51
  52   /* Initialize the state of the random number generator once,
  53   ** the first time this routine is called.  The seed value does
  54   ** not need to contain a lot of randomness since we are not
  55   ** trying to do secure encryption or anything like that...
  56   **
  57   ** Nothing in this file or anywhere else in SQLite does any kind of
  58   ** encryption.  The RC4 algorithm is being used as a PRNG (pseudo-random
  59   ** number generator) not as an encryption device.
  60   */
  61   if( !prng.isInit ){
  62     int i;
  63     char k[256];
  64     prng.j = 0;
  65     prng.i = 0;
  66     sqlite3OsRandomSeed(k);
  67     for(i=0; i<256; i++){
  68       prng.s[i] = i;
  69     }
  70     for(i=0; i<256; i++){
  71       prng.j += prng.s[i] + k[i];
  72       t = prng.s[prng.j];
  73       prng.s[prng.j] = prng.s[i];
  74       prng.s[i] = t;
  75     }
  76     prng.isInit = 1;
  77   }
  78
  79   /* Generate and return single random byte
  80   */
  81   prng.i++;
  82   t = prng.s[prng.i];
  83   prng.j += t;
  84   prng.s[prng.i] = prng.s[prng.j];
  85   prng.s[prng.j] = t;
  86   t += prng.s[prng.i];
  87   return prng.s[t];
  88 }
  89
  90 /*
  91 ** Return N random bytes.
  92 */
  93 void sqlite3Randomness(int N, void *pBuf){
  94   unsigned char *zBuf = pBuf;
  95   sqlite3OsEnterMutex();
  96   while( N-- ){
  97     *(zBuf++) = randomByte();
  98   }
  99   sqlite3OsLeaveMutex();
 100 }