Return to random.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / src

Annotation of embedaddon/sqlite3/src/random.c, revision 1.1

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