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.10 2002/02/19 13:39:23 drh Exp $ 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_NewRecno 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 static int randomByte(){ 38 int t; 39 40 /* All threads share a single random number generator. 41 ** This structure is the current state of the generator. 42 */ 43 static struct { 44 int isInit; /* True if initialized */ 45 int i, j; /* State variables */ 46 int s[256]; /* State variables */ 47 } prng; 48 49 /* Initialize the state of the random number generator once, 50 ** the first time this routine is called. The seed value does 51 ** not need to contain a lot of randomness since we are not 52 ** trying to do secure encryption or anything like that... 53 ** 54 ** Nothing in this file or anywhere else in SQLite does any kind of 55 ** encryption. The RC4 algorithm is being used as a PRNG (pseudo-random 56 ** number generator) not as an encryption device. 57 */ 58 if( !prng.isInit ){ 59 int i; 60 char k[256]; 61 prng.j = 0; 62 prng.i = 0; 63 sqliteOsRandomSeed(k); 64 for(i=0; i<256; i++){ 65 prng.s[i] = i; 66 } 67 for(i=0; i<256; i++){ 68 int t; 69 prng.j = (prng.j + prng.s[i] + k[i]) & 0xff; 70 t = prng.s[prng.j]; 71 prng.s[prng.j] = prng.s[i]; 72 prng.s[i] = t; 73 } 74 prng.isInit = 1; 75 } 76 77 /* Generate and return single random byte 78 */ 79 prng.i = (prng.i + 1) & 0xff; 80 prng.j = (prng.j + prng.s[prng.i]) & 0xff; 81 t = prng.s[prng.i]; 82 prng.s[prng.i] = prng.s[prng.j]; 83 prng.s[prng.j] = t; 84 t = prng.s[prng.i] + prng.s[prng.j]; 85 return prng.s[t & 0xff]; 86 } 87 88 /* 89 ** Return an random 8-bit integer. 90 */ 91 int sqliteRandomByte(){ 92 int r; 93 sqliteOsEnterMutex(); 94 r = randomByte(); 95 sqliteOsLeaveMutex(); 96 return r; 97 } 98 99 /* 100 ** Return a random 32-bit integer. The integer is generated by making 101 ** 4 calls to sqliteRandomByte(). 102 */ 103 int sqliteRandomInteger(){ 104 int r; 105 int i; 106 sqliteOsEnterMutex(); 107 r = randomByte(); 108 for(i=1; i<4; i++){ 109 r = (r<<8) + randomByte(); 110 } 111 sqliteOsLeaveMutex(); 112 return r; 113 } 114