GoodRandom.cs

using System;
using System.Diagnostics;
using System.Security.Cryptography;
using BenchmarkDotNet.Attributes;

namespace ConsoleApp2 {
    public class Benchmarking {
        private static readonly GoodRandom Rng1;
        private static readonly GoodRandom Rng2;
        private static readonly Random Rng3;

        static Benchmarking() {
            Rng1 = new GoodRandom();
            Rng2 = new GoodRandom((string) null);
            Rng3 = new Random(0);
        }

        [Benchmark]
        public static int Random1() { return Rng1.Next(); }

        [Benchmark]
        public static int Random2() { return Rng2.Next(); }

        [Benchmark]
        public static int Random3() { return Rng3.Next(); }
    }

    public class Program {
        private static void Main() {
            // BenchmarkRunner.Run<Benchmarking>();

            var randoms = new int[10];
            using (var rng = new GoodRandom("test")) {
                for (var i = 0; i < randoms.Length; i++) {
                    randoms[i] = rng.Next();
                }
            }

            var same = true;
            using (var rng = new GoodRandom("test")) {
                foreach (var t in randoms) {
                    same = same && t == rng.Next();
                }
            }
            Console.WriteLine(same);
        }
    }

    public sealed class GoodRandom : Random, IDisposable {
        private const int Size = 1024;
        private readonly byte[] _buffer;
        private readonly bool _failOnExhaustion;
        private readonly RNGCryptoServiceProvider _rng;
        private readonly CryptoPseudoRandom _seededrng;
        private int _available;

        /// <summary>
        ///     Produces a cryptographically strong random number generator.
        /// </summary>
        public GoodRandom() : this(null, new RNGCryptoServiceProvider(), null) { }

        /// <summary>
        ///     Produces a seeded pseudorandom number generator with perf characteristics similar to a cryptographically strong
        ///     random number generator.
        /// </summary>
        /// <remarks>
        ///     This is about 5x slower than the default constructor, but it returns the same values repeatedly.
        /// </remarks>
        /// <param name="seed">seed used to generate key for algorithm; if null, the algorithm will use a random seed</param>
        public GoodRandom(string seed) : this(null, null, new CryptoPseudoRandom(seed)) { }

        /// <summary>
        ///     Produces a generator that starts by reading results from the provided buffer and then throws an exception when the
        ///     buffer is exhausted.
        /// </summary>
        /// <remarks>
        ///     You might use this in a hot path with a large buffer generated ahead of time:
        ///     <code>
        /// // before critical section:
        /// var rng = new GoodRandom();
        /// var buffer = new byte[10000];
        /// rng.GetBytes(buffer);
        /// 
        /// // in hot path:
        /// var hotrng = new GoodRandom(buffer);
        /// // use hotrng
        /// </code>
        /// </remarks>
        /// <param name="initialBuffer"></param>
        public GoodRandom(byte[] initialBuffer) : this(initialBuffer, null, null) { }

        private GoodRandom(byte[] initialBuffer, RNGCryptoServiceProvider rng, CryptoPseudoRandom seeded) {
            if (initialBuffer != null) {
                _buffer = new byte[initialBuffer.Length];
                _available = 0;
                Buffer.BlockCopy(initialBuffer, 0, _buffer, 0, _buffer.Length);
                _failOnExhaustion = true;
            } else {
                _buffer = new byte[Size];
                _available = _buffer.Length;
            }
            _rng = rng;
            _seededrng = seeded;
        }

        public override int Next() => BitConverter.ToInt32(_buffer, FindOffset(sizeof(int))) & int.MaxValue;

        public override int Next(int minValue, int maxValue) {
            if (minValue > maxValue) {
                throw new ArgumentOutOfRangeException(nameof(minValue), nameof(minValue) + " must not be greater than " + nameof(maxValue));
            }
            // contract for Random.Next(int, int) permits this for some reason:
            if (minValue == maxValue) return minValue;

            var range = (long) maxValue - minValue;
            if (range <= int.MaxValue) {
                return InternalNext((int) range) + minValue;
            }
            var sample = NextUInt32() % range + minValue;
            return (int) sample;
        }

        public override int Next(int maxValue) {
            if (maxValue < 0) {
                throw new ArgumentOutOfRangeException(nameof(maxValue), nameof(maxValue) + " must be non-negative.");
            }
            // contract for Random.Next(int) permits this for some reason:
            if (maxValue == 0) {
                return 0;
            }
            return InternalNext(maxValue);
        }

        public byte NextByte() => _buffer[FindOffset(1)];

        public override void NextBytes(byte[] buffer) {
            if (buffer == null) throw new ArgumentNullException(nameof(buffer));
            // this could be more efficient
            if (buffer.Length > Size) {
                Fill(buffer);
                return;
            }

            var offset = FindOffset(buffer.Length);
            Buffer.BlockCopy(_buffer, offset, buffer, 0, buffer.Length);
        }

        // Random.NextDouble uses 32-bit values, but an 80 bit double has 62-63 bits of fraction space; not really sure which is better...
        // This one might be less uniform? I'm not entirely sure how to detect bias here.
        const ulong MBIG = 0x8000000000000000;
        const ulong M1 = MBIG - 1;
        public override double NextDouble() => (NextUInt64() & M1) * (1.0 / MBIG);

        // matches precision of Random.NextDouble
        public double NextDoubleLowPrecision() => (Next() & 0x7FFFFFFF) * (1.0 / 0x80000000);

        public ushort NextUInt16() => BitConverter.ToUInt16(_buffer, FindOffset(sizeof(ushort)));

        public uint NextUInt32() => BitConverter.ToUInt32(_buffer, FindOffset(sizeof(uint)));

        public ulong NextUInt64() => BitConverter.ToUInt64(_buffer, FindOffset(sizeof(ulong)));

        protected override double Sample() => NextDouble();

        private void Fill(byte[] buffer) {
            if (_failOnExhaustion) ThrowExhaustion();
            if (_rng == null) {
                _seededrng.GetBytes(buffer);
            } else {
                _rng.GetBytes(buffer);
            }
        }

        private int FindOffset(int size) {
            if (size > Size) throw new ArgumentOutOfRangeException(nameof(size), size, "Must be <= " + Size);

            // this algorithm may throw away some bytes, it is important that _buffer.Length is large compared to size to keep the percentage low
            // a different algorithm might maintain some overhead to not lose any available buffer but that would cost some perf
            var offset = _available;
            _available += size;
            if (_available <= _buffer.Length) return offset;

            Fill(_buffer);
            offset = 0;
            _available = size;
            return offset;
        }

        private int InternalNext(int maxValue) {
            // in theory these loops could go forever; in practice the worst case
            // P = 0.5 that a value fails the loop condition on the first try
            // case 1: maxValue = 128, threshold = 128
            // NextByte() => 0-255
            // P(result>=128) = 127/256 (0.496)
            // case 2: maxValue = 32768... P = 32767/65536 (0.5)
            uint result;
            if (maxValue <= byte.MaxValue) {
                var threshold = byte.MaxValue - byte.MaxValue % maxValue;
                do {
                    result = NextByte();
                } while (result >= threshold);
            } else if (maxValue <= ushort.MaxValue) {
                var threshold = ushort.MaxValue - ushort.MaxValue % maxValue;
                do {
                    result = NextUInt16();
                } while (result >= threshold);
            } else {
                var threshold = uint.MaxValue - uint.MaxValue % (uint)maxValue;
                do {
                    result = Next();
                } while (result >= threshold);
            }
            return (int) (result % maxValue);
        }

        private void ThrowExhaustion() { throw new BufferExhaustionException(); }

        public void Dispose() {
            // no need for full dispose pattern because this class is sealed
            _rng?.Dispose();
            _seededrng?.Dispose();
        }
    }

    public class BufferExhaustionException : Exception {}

    public sealed class CryptoPseudoRandom : IDisposable {
        private readonly SymmetricAlgorithm _algorithm;
        private readonly byte[] _counter;
        private readonly ICryptoTransform _counterEncryptor;
        private readonly byte[] _encryptedCounter;
        private int _counterIndex;

        public CryptoPseudoRandom(string seed) {
            // initializes AES in CTR mode with a key derived from an unsalted hash of the seed or randomly generated if the seed is null
            _algorithm = SymmetricAlgorithm.Create("AES");
            Debug.Assert(_algorithm != null, "_algorithm != null");
            _algorithm.Mode = CipherMode.ECB;
            _algorithm.Padding = PaddingMode.None;
            if (!string.IsNullOrEmpty(seed)) {
                using (var keygen = new Rfc2898DeriveBytes(seed, new byte[8], 1)) {
                    _algorithm.Key = keygen.GetBytes(_algorithm.KeySize / 8);
                    _algorithm.IV = keygen.GetBytes(_algorithm.BlockSize / 8);
                }
            } else {
                _algorithm.GenerateKey();
                _algorithm.GenerateIV();
            }
            _counterEncryptor = _algorithm.CreateEncryptor(_algorithm.Key, _algorithm.IV);
            _encryptedCounter = new byte[_algorithm.BlockSize / 8];
            _counter = new byte[_algorithm.BlockSize / 8];
        }

        public void GetBytes(byte[] buffer) {
            var blocksize = _algorithm.BlockSize / 8;
            var local = _counter;
            var localEnc = _encryptedCounter;
            var counterIndex = _counterIndex;

            for (var i = 0; i < buffer.Length; i++) {
                if (counterIndex == 0) {
                    _counterEncryptor.TransformBlock(local, 0, blocksize, localEnc, 0);

                    // inlined increment function to improve performance
                    for (var i1 = 0; i1 < local.Length; i1++) {
                        if (local[i1] < byte.MaxValue) {
                            local[i1]++;
                            break;
                        }
                        local[i1] = 0;
                    }
                }
                buffer[i] = localEnc[counterIndex];
                counterIndex = (counterIndex + 1) % blocksize;
            }
            _counterIndex = counterIndex;
        }

        public void Dispose() {
            _counterEncryptor?.Dispose();
            _algorithm?.Dispose();
        }
    }
}