Replace the RC4-based PRNG with one based on ChaCha20. 3x faster.

FossilOrigin-Name: 084d8776fa95c75440530028171c56547a341c9a952ba2f29bb533b538603c78

1 files changed, 52 insertions, 31 deletions

diff --git a/src/random.c b/src/random.c
index 87f9e2cec..11c5a42b6 100644
--- a/src/random.c
+++ b/src/random.c
@@ -22,16 +22,38 @@
 ** This structure is the current state of the generator.
 */
 static SQLITE_WSD struct sqlite3PrngType {
-  unsigned char isInit;          /* True if initialized */
-  unsigned char i, j;            /* State variables */
-  unsigned char s[256];          /* State variables */
+  u32 s[16];                 /* 64 bytes of chacha20 state */
+  u8 out[64];                /* Output bytes */
+  u8 n;                      /* Output bytes remaining */
 } sqlite3Prng;
 
+#define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
+#define QR(a, b, c, d) (			\
+	a += b,  d ^= a,  d = ROTL(d,16),	\
+	c += d,  b ^= c,  b = ROTL(b,12),	\
+	a += b,  d ^= a,  d = ROTL(d, 8),	\
+	c += d,  b ^= c,  b = ROTL(b, 7))
+static void chacha_block(u32 *out, const u32 *in){
+  int i;
+  u32 x[16];
+  memcpy(x, in, 64);
+  for(i=0; i<10; i++){
+    QR(x[0], x[4], x[ 8], x[12]);
+    QR(x[1], x[5], x[ 9], x[13]);
+    QR(x[2], x[6], x[10], x[14]);
+    QR(x[3], x[7], x[11], x[15]);
+    QR(x[0], x[5], x[10], x[15]);
+    QR(x[1], x[6], x[11], x[12]);
+    QR(x[2], x[7], x[ 8], x[13]);
+    QR(x[3], x[4], x[ 9], x[14]);
+  }
+  for(i=0; i<16; i++) out[i] = x[i]+in[i];
+}
+
 /*
 ** Return N random bytes.
 */
 void sqlite3_randomness(int N, void *pBuf){
-  unsigned char t;
   unsigned char *zBuf = pBuf;
 
   /* The "wsdPrng" macro will resolve to the pseudo-random number generator
@@ -61,7 +83,7 @@ void sqlite3_randomness(int N, void *pBuf){
 
   sqlite3_mutex_enter(mutex);
   if( N<=0 || pBuf==0 ){
-    wsdPrng.isInit = 0;
+    wsdPrng.s[0] = 0;
     sqlite3_mutex_leave(mutex);
     return;
   }
@@ -75,39 +97,38 @@ void sqlite3_randomness(int N, void *pBuf){
   ** encryption.  The RC4 algorithm is being used as a PRNG (pseudo-random
   ** number generator) not as an encryption device.
   */
-  if( !wsdPrng.isInit ){
+  if( wsdPrng.s[0]==0 ){
     sqlite3_vfs *pVfs = sqlite3_vfs_find(0);
-    int i;
-    char k[256];
-    wsdPrng.j = 0;
-    wsdPrng.i = 0;
+    static const u32 chacha20_init[] = {
+      0x61707865, 0x3320646e, 0x79622d32, 0x6b206574
+    };
+    memcpy(&wsdPrng.s[0], chacha20_init, 16);
     if( NEVER(pVfs==0) ){
-      memset(k, 0, sizeof(k));
+      memset(&wsdPrng.s[4], 0, 44);
     }else{
-      sqlite3OsRandomness(pVfs, 256, k);
-    }
-    for(i=0; i<256; i++){
-      wsdPrng.s[i] = (u8)i;
+      sqlite3OsRandomness(pVfs, 44, (char*)&wsdPrng.s[4]);
     }
-    for(i=0; i<256; i++){
-      wsdPrng.j += wsdPrng.s[i] + k[i];
-      t = wsdPrng.s[wsdPrng.j];
-      wsdPrng.s[wsdPrng.j] = wsdPrng.s[i];
-      wsdPrng.s[i] = t;
-    }
-    wsdPrng.isInit = 1;
+    wsdPrng.s[16] = wsdPrng.s[12];
+    wsdPrng.s[12] = 0;
+    wsdPrng.n = 0;
   }
 
   assert( N>0 );
-  do{
-    wsdPrng.i++;
-    t = wsdPrng.s[wsdPrng.i];
-    wsdPrng.j += t;
-    wsdPrng.s[wsdPrng.i] = wsdPrng.s[wsdPrng.j];
-    wsdPrng.s[wsdPrng.j] = t;
-    t += wsdPrng.s[wsdPrng.i];
-    *(zBuf++) = wsdPrng.s[t];
-  }while( --N );
+  while( 1 /* exit by break */ ){
+    if( N<=wsdPrng.n ){
+      memcpy(zBuf, &wsdPrng.out[wsdPrng.n-N], N);
+      wsdPrng.n -= N;
+      break;
+    }
+    if( wsdPrng.n>0 ){
+      memcpy(zBuf, wsdPrng.out, wsdPrng.n);
+      N -= wsdPrng.n;
+      zBuf += wsdPrng.n;
+    }
+    wsdPrng.s[12]++;
+    chacha_block((u32*)wsdPrng.out, wsdPrng.s);
+    wsdPrng.n = 64;
+  }
   sqlite3_mutex_leave(mutex);
 }