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              60 : static int randomByte(void){
      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              60 :   if( !prng.isInit ){
      62                 :     int i;
      63                 :     char k[256];
      64               4 :     prng.j = 0;
      65               4 :     prng.i = 0;
      66               4 :     sqlite3OsRandomSeed(k);
      67            1028 :     for(i=0; i<256; i++){
      68            1024 :       prng.s[i] = i;
      69                 :     }
      70            1028 :     for(i=0; i<256; i++){
      71            1024 :       prng.j += prng.s[i] + k[i];
      72            1024 :       t = prng.s[prng.j];
      73            1024 :       prng.s[prng.j] = prng.s[i];
      74            1024 :       prng.s[i] = t;
      75                 :     }
      76               4 :     prng.isInit = 1;
      77                 :   }
      78                 : 
      79                 :   /* Generate and return single random byte
      80                 :   */
      81              60 :   prng.i++;
      82              60 :   t = prng.s[prng.i];
      83              60 :   prng.j += t;
      84              60 :   prng.s[prng.i] = prng.s[prng.j];
      85              60 :   prng.s[prng.j] = t;
      86              60 :   t += prng.s[prng.i];
      87              60 :   return prng.s[t];
      88                 : }
      89                 : 
      90                 : /*
      91                 : ** Return N random bytes.
      92                 : */
      93              15 : void sqlite3Randomness(int N, void *pBuf){
      94              15 :   unsigned char *zBuf = pBuf;
      95              15 :   sqlite3OsEnterMutex();
      96              90 :   while( N-- ){
      97              60 :     *(zBuf++) = randomByte();
      98                 :   }
      99              15 :   sqlite3OsLeaveMutex();
     100              15 : }