Merge #9792: FastRandomContext improvements and switch to ChaCha20

4fd2d2f Add a FastRandomContext::randrange and use it (Pieter Wuille)
1632922 Switch FastRandomContext to ChaCha20 (Pieter Wuille)
e04326f Add ChaCha20 (Pieter Wuille)
663fbae FastRandom benchmark (Pieter Wuille)
c21cbe6 Introduce FastRandomContext::randbool() (Pieter Wuille)

Tree-SHA512: 7fff61e3f6d6dc6ac846ca643d877b377db609646dd401a0e8f50b052c6b9bcd2f5fc34de6bbf28f04afd1724f6279ee163ead5f37d724fb782a00239f35db1d

1 files changed, 71 insertions, 7 deletions

diff --git a/src/random.h b/src/random.h
index 0464bdce14..9551e1c461 100644
--- a/src/random.h
+++ b/src/random.h
@@ -6,6 +6,8 @@
 #ifndef BITCOIN_RANDOM_H
 #define BITCOIN_RANDOM_H
 
+#include "crypto/chacha20.h"
+#include "crypto/common.h"
 #include "uint256.h"
 
 #include <stdint.h>
@@ -33,17 +35,79 @@ void GetStrongRandBytes(unsigned char* buf, int num);
  * This class is not thread-safe.
  */
 class FastRandomContext {
+private:
+    bool requires_seed;
+    ChaCha20 rng;
+
+    unsigned char bytebuf[64];
+    int bytebuf_size;
+
+    uint64_t bitbuf;
+    int bitbuf_size;
+
+    void RandomSeed();
+
+    void FillByteBuffer()
+    {
+        if (requires_seed) {
+            RandomSeed();
+        }
+        rng.Output(bytebuf, sizeof(bytebuf));
+        bytebuf_size = sizeof(bytebuf);
+    }
+
+    void FillBitBuffer()
+    {
+        bitbuf = rand64();
+        bitbuf_size = 64;
+    }
+
 public:
-    explicit FastRandomContext(bool fDeterministic=false);
+    explicit FastRandomContext(bool fDeterministic = false);
+
+    /** Initialize with explicit seed (only for testing) */
+    explicit FastRandomContext(const uint256& seed);
+
+    /** Generate a random 64-bit integer. */
+    uint64_t rand64()
+    {
+        if (bytebuf_size < 8) FillByteBuffer();
+        uint64_t ret = ReadLE64(bytebuf + 64 - bytebuf_size);
+        bytebuf_size -= 8;
+        return ret;
+    }
 
-    uint32_t rand32() {
-        Rz = 36969 * (Rz & 65535) + (Rz >> 16);
-        Rw = 18000 * (Rw & 65535) + (Rw >> 16);
-        return (Rw << 16) + Rz;
+    /** Generate a random (bits)-bit integer. */
+    uint64_t randbits(int bits) {
+        if (bits == 0) {
+            return 0;
+        } else if (bits > 32) {
+            return rand64() >> (64 - bits);
+        } else {
+            if (bitbuf_size < bits) FillBitBuffer();
+            uint64_t ret = bitbuf & (~(uint64_t)0 >> (64 - bits));
+            bitbuf >>= bits;
+            bitbuf_size -= bits;
+            return ret;
+        }
     }
 
-    uint32_t Rz;
-    uint32_t Rw;
+    /** Generate a random integer in the range [0..range). */
+    uint64_t randrange(uint64_t range)
+    {
+        --range;
+        int bits = CountBits(range);
+        while (true) {
+            uint64_t ret = randbits(bits);
+            if (ret <= range) return ret;
+        }
+    }
+
+    /** Generate a random 32-bit integer. */
+    uint32_t rand32() { return randbits(32); }
+
+    /** Generate a random boolean. */
+    bool randbool() { return randbits(1); }
 };
 
 /* Number of random bytes returned by GetOSRand.