Fix a problem causing the recovery extension to use excessive memory and CPU time...
[sqlite.git] / src / random.c
blobea8431ba9409dbabefc972fe22f6d1e78dd328c7
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.
11 *************************************************************************
12 ** This file contains code to implement a pseudo-random number
13 ** generator (PRNG) for SQLite.
15 ** Random numbers are used by some of the database backends in order
16 ** to generate random integer keys for tables or random filenames.
18 #include "sqliteInt.h"
21 /* All threads share a single random number generator.
22 ** This structure is the current state of the generator.
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;
31 /* The RFC-7539 ChaCha20 block function
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]);
53 for(i=0; i<16; i++) out[i] = x[i]+in[i];
57 ** Return N random bytes.
59 void sqlite3_randomness(int N, void *pBuf){
60 unsigned char *zBuf = pBuf;
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.
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
75 #if SQLITE_THREADSAFE
76 sqlite3_mutex *mutex;
77 #endif
79 #ifndef SQLITE_OMIT_AUTOINIT
80 if( sqlite3_initialize() ) return;
81 #endif
83 #if SQLITE_THREADSAFE
84 mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PRNG);
85 #endif
87 sqlite3_mutex_enter(mutex);
88 if( N<=0 || pBuf==0 ){
89 wsdPrng.s[0] = 0;
90 sqlite3_mutex_leave(mutex);
91 return;
94 /* Initialize the state of the random number generator once,
95 ** the first time this routine is called.
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
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]);
108 wsdPrng.s[15] = wsdPrng.s[12];
109 wsdPrng.s[12] = 0;
110 wsdPrng.n = 0;
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;
120 if( wsdPrng.n>0 ){
121 memcpy(zBuf, wsdPrng.out, wsdPrng.n);
122 N -= wsdPrng.n;
123 zBuf += wsdPrng.n;
125 wsdPrng.s[12]++;
126 chacha_block((u32*)wsdPrng.out, wsdPrng.s);
127 wsdPrng.n = 64;
129 sqlite3_mutex_leave(mutex);
132 #ifndef SQLITE_UNTESTABLE
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.
139 ** The sqlite3_test_control() interface calls these routines to
140 ** control the PRNG.
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)
150 void sqlite3PrngRestoreState(void){
151 memcpy(
152 &GLOBAL(struct sqlite3PrngType, sqlite3Prng),
153 &GLOBAL(struct sqlite3PrngType, sqlite3SavedPrng),
154 sizeof(sqlite3Prng)
157 #endif /* SQLITE_UNTESTABLE */