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