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*/
24static 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*/
46static 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*/
105void 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*/
127static SQLITE_WSD struct sqlite3PrngType sqlite3SavedPrng;
128void sqlite3PrngSaveState(void){
129  memcpy(
130    &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
131    &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
132    sizeof(sqlite3Prng)
133  );
134}
135void sqlite3PrngRestoreState(void){
136  memcpy(
137    &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
138    &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
139    sizeof(sqlite3Prng)
140  );
141}
142void sqlite3PrngResetState(void){
143  GLOBAL(struct sqlite3PrngType, sqlite3Prng).isInit = 0;
144}
145#endif /* SQLITE_OMIT_BUILTIN_TEST */
146