src/random.c

   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   u32 s[16];                 /* 64 bytes of chacha20 state */
  26   u8 out[64];                /* Output bytes */
  27   u8 n;                      /* Output bytes remaining */
  28 } sqlite3Prng;
  29
  30
  31 /* The RFC-7539 ChaCha20 block function
  32 */
  33 #define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
  34 #define QR(a, b, c, d) ( \
  35     a += b, d ^= a, d = ROTL(d,16), \
  36     c += d, b ^= c, b = ROTL(b,12), \
  37     a += b, d ^= a, d = ROTL(d, 8), \
  38     c += d, b ^= c, b = ROTL(b, 7))
  39 static void chacha_block(u32 *out, const u32 *in){
  40   int i;
  41   u32 x[16];
  42   memcpy(x, in, 64);
  43   for(i=0; i<10; i++){
  44     QR(x[0], x[4], x[ 8], x[12]);
  45     QR(x[1], x[5], x[ 9], x[13]);
  46     QR(x[2], x[6], x[10], x[14]);
  47     QR(x[3], x[7], x[11], x[15]);
  48     QR(x[0], x[5], x[10], x[15]);
  49     QR(x[1], x[6], x[11], x[12]);
  50     QR(x[2], x[7], x[ 8], x[13]);
  51     QR(x[3], x[4], x[ 9], x[14]);
  52   }
  53   for(i=0; i<16; i++) out[i] = x[i]+in[i];
  54 }
  55
  56 /*
  57 ** Return N random bytes.
  58 */
  59 void sqlite3_randomness(int N, void *pBuf){
  60   unsigned char *zBuf = pBuf;
  61
  62   /* The "wsdPrng" macro will resolve to the pseudo-random number generator
  63   ** state vector.  If writable static data is unsupported on the target,
  64   ** we have to locate the state vector at run-time.  In the more common
  65   ** case where writable static data is supported, wsdPrng can refer directly
  66   ** to the "sqlite3Prng" state vector declared above.
  67   */
  68 #ifdef SQLITE_OMIT_WSD
  69   struct sqlite3PrngType *p = &GLOBAL(struct sqlite3PrngType, sqlite3Prng);
  70 # define wsdPrng p[0]
  71 #else
  72 # define wsdPrng sqlite3Prng
  73 #endif
  74
  75 #if SQLITE_THREADSAFE
  76   sqlite3_mutex *mutex;
  77 #endif
  78
  79 #ifndef SQLITE_OMIT_AUTOINIT
  80   if( sqlite3_initialize() ) return;
  81 #endif
  82
  83 #if SQLITE_THREADSAFE
  84   mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PRNG);
  85 #endif
  86
  87   sqlite3_mutex_enter(mutex);
  88   if( N<=0 || pBuf==0 ){
  89     wsdPrng.s[0] = 0;
  90     sqlite3_mutex_leave(mutex);
  91     return;
  92   }
  93
  94   /* Initialize the state of the random number generator once,
  95   ** the first time this routine is called.
  96   */
  97   if( wsdPrng.s[0]==0 ){
  98     sqlite3_vfs *pVfs = sqlite3_vfs_find(0);
  99     static const u32 chacha20_init[] = {
 100       0x61707865, 0x3320646e, 0x79622d32, 0x6b206574
 101     };
 102     memcpy(&wsdPrng.s[0], chacha20_init, 16);
 103     if( NEVER(pVfs==0) ){
 104       memset(&wsdPrng.s[4], 0, 44);
 105     }else{
 106       sqlite3OsRandomness(pVfs, 44, (char*)&wsdPrng.s[4]);
 107     }
 108     wsdPrng.s[15] = wsdPrng.s[12];
 109     wsdPrng.s[12] = 0;
 110     wsdPrng.n = 0;
 111   }
 112
 113   assert( N>0 );
 114   while( 1 /* exit by break */ ){
 115     if( N<=wsdPrng.n ){
 116       memcpy(zBuf, &wsdPrng.out[wsdPrng.n-N], N);
 117       wsdPrng.n -= N;
 118       break;
 119     }
 120     if( wsdPrng.n>0 ){
 121       memcpy(zBuf, wsdPrng.out, wsdPrng.n);
 122       N -= wsdPrng.n;
 123       zBuf += wsdPrng.n;
 124     }
 125     wsdPrng.s[12]++;
 126     chacha_block((u32*)wsdPrng.out, wsdPrng.s);
 127     wsdPrng.n = 64;
 128   }
 129   sqlite3_mutex_leave(mutex);
 130 }
 131
 132 #ifndef SQLITE_UNTESTABLE
 133 /*
 134 ** For testing purposes, we sometimes want to preserve the state of
 135 ** PRNG and restore the PRNG to its saved state at a later time, or
 136 ** to reset the PRNG to its initial state.  These routines accomplish
 137 ** those tasks.
 138 **
 139 ** The sqlite3_test_control() interface calls these routines to
 140 ** control the PRNG.
 141 */
 142 static SQLITE_WSD struct sqlite3PrngType sqlite3SavedPrng;
 143 void sqlite3PrngSaveState(void){
 144   memcpy(
 145     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
 146     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
 147     sizeof(sqlite3Prng)
 148   );
 149 }
 150 void sqlite3PrngRestoreState(void){
 151   memcpy(
 152     &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
 153     &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
 154     sizeof(sqlite3Prng)
 155   );
 156 }
 157 #endif /* SQLITE_UNTESTABLE */