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: random.c,v 1.27 2008/10/07 15:25:48 drh Exp $ 19 */ 20 #include "sqliteInt.h" 21 22 23 /* All threads share a single random number generator. 24 ** This structure is the current state of the generator. 25 */ 26 static SQLITE_WSD struct sqlite3PrngType { 27 unsigned char isInit; /* True if initialized */ 28 unsigned char i, j; /* State variables */ 29 unsigned char s[256]; /* State variables */ 30 } sqlite3Prng = { 0, }; 31 32 /* 33 ** Get a single 8-bit random value from the RC4 PRNG. The Mutex 34 ** must be held while executing this routine. 35 ** 36 ** Why not just use a library random generator like lrand48() for this? 37 ** Because the OP_NewRowid opcode in the VDBE depends on having a very 38 ** good source of random numbers. The lrand48() library function may 39 ** well be good enough. But maybe not. Or maybe lrand48() has some 40 ** subtle problems on some systems that could cause problems. It is hard 41 ** to know. To minimize the risk of problems due to bad lrand48() 42 ** implementations, SQLite uses this random number generator based 43 ** on RC4, which we know works very well. 44 ** 45 ** (Later): Actually, OP_NewRowid does not depend on a good source of 46 ** randomness any more. But we will leave this code in all the same. 47 */ 48 static int randomByte(void){ 49 unsigned char t; 50 51 52 /* The "wsdPrng" macro will resolve to the pseudo-random number generator 53 ** state vector. If writable static data is unsupported on the target, 54 ** we have to locate the state vector at run-time. In the more common 55 ** case where writable static data is supported, wsdPrng can refer directly 56 ** to the "sqlite3Prng" state vector declared above. 57 */ 58 #ifdef SQLITE_OMIT_WSD 59 struct sqlite3PrngType *p = &GLOBAL(struct sqlite3PrngType, sqlite3Prng); 60 # define wsdPrng p[0] 61 #else 62 # define wsdPrng sqlite3Prng 63 #endif 64 65 66 /* Initialize the state of the random number generator once, 67 ** the first time this routine is called. The seed value does 68 ** not need to contain a lot of randomness since we are not 69 ** trying to do secure encryption or anything like that... 70 ** 71 ** Nothing in this file or anywhere else in SQLite does any kind of 72 ** encryption. The RC4 algorithm is being used as a PRNG (pseudo-random 73 ** number generator) not as an encryption device. 74 */ 75 if( !wsdPrng.isInit ){ 76 int i; 77 char k[256]; 78 wsdPrng.j = 0; 79 wsdPrng.i = 0; 80 sqlite3OsRandomness(sqlite3_vfs_find(0), 256, k); 81 for(i=0; i<256; i++){ 82 wsdPrng.s[i] = i; 83 } 84 for(i=0; i<256; i++){ 85 wsdPrng.j += wsdPrng.s[i] + k[i]; 86 t = wsdPrng.s[wsdPrng.j]; 87 wsdPrng.s[wsdPrng.j] = wsdPrng.s[i]; 88 wsdPrng.s[i] = t; 89 } 90 wsdPrng.isInit = 1; 91 } 92 93 /* Generate and return single random byte 94 */ 95 wsdPrng.i++; 96 t = wsdPrng.s[wsdPrng.i]; 97 wsdPrng.j += t; 98 wsdPrng.s[wsdPrng.i] = wsdPrng.s[wsdPrng.j]; 99 wsdPrng.s[wsdPrng.j] = t; 100 t += wsdPrng.s[wsdPrng.i]; 101 return wsdPrng.s[t]; 102 } 103 104 /* 105 ** Return N random bytes. 106 */ 107 void sqlite3_randomness(int N, void *pBuf){ 108 unsigned char *zBuf = pBuf; 109 #if SQLITE_THREADSAFE 110 sqlite3_mutex *mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PRNG); 111 #endif 112 sqlite3_mutex_enter(mutex); 113 while( N-- ){ 114 *(zBuf++) = randomByte(); 115 } 116 sqlite3_mutex_leave(mutex); 117 } 118 119 #ifndef SQLITE_OMIT_BUILTIN_TEST 120 /* 121 ** For testing purposes, we sometimes want to preserve the state of 122 ** PRNG and restore the PRNG to its saved state at a later time, or 123 ** to reset the PRNG to its initial state. These routines accomplish 124 ** those tasks. 125 ** 126 ** The sqlite3_test_control() interface calls these routines to 127 ** control the PRNG. 128 */ 129 static SQLITE_WSD struct sqlite3PrngType sqlite3SavedPrng = { 0, }; 130 void sqlite3PrngSaveState(void){ 131 memcpy( 132 &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng), 133 &GLOBAL(struct sqlite3PrngType, sqlite3Prng), 134 sizeof(sqlite3Prng) 135 ); 136 } 137 void sqlite3PrngRestoreState(void){ 138 memcpy( 139 &GLOBAL(struct sqlite3PrngType, sqlite3Prng), 140 &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng), 141 sizeof(sqlite3Prng) 142 ); 143 } 144 void sqlite3PrngResetState(void){ 145 GLOBAL(struct sqlite3PrngType, sqlite3Prng).isInit = 0; 146 } 147 #endif /* SQLITE_OMIT_BUILTIN_TEST */ 148