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