C++ pseudo-random number generation

C++11 introduced a wonderful pseudo-random number generation library. In this article, I implement a custom uniform random bit generator based on Xoofff.

Xoofff generator

The C++ random number generator facilities are designed in a very general and powerful way. Specifically, the bit generators, engines and distributions are all separate from each other. This makes it trivial to extend the library in arbitrary ways without needing to reinvent the wheel. The provided engines are not cryptographically strong; for example, it is trivial to recover the entire state of the Mersenne Twister engine simply by observing a relatively small amount of output from it. Once the state has been recovered, it is easy to predict all future numbers from it. For some applications, this is problematic. Thankfully, it is easy to create a custom generator based on cryptographically-strong Xoofff:

template<typename ResultType = uint_fast8_t>
class Xoofff_Generator
{
	static_assert(std::is_unsigned_v<ResultType>, "ResultType must be of unsigned integral type");

private:
	Xoofff_Instance xi;
	std::vector<ResultType> buf;
	size_t ptr;

public:
	using result_type = ResultType;

	static constexpr auto min = std::numeric_limits<ResultType>::min;
	static constexpr auto max = std::numeric_limits<ResultType>::max;

	explicit Xoofff_Generator(const Xoofff_Instance &rxi) : xi{rxi}, buf(8'192), ptr{size(buf)}
	{
	}

	explicit Xoofff_Generator(Xoofff_Instance &&mxi) : xi{std::move(mxi)}, buf(8'192), ptr{size(buf)}
	{
	}

	ResultType operator()()
	{
		if (ptr == size(buf))
		{
			if (Xoofff_Expand(&xi, reinterpret_cast<BitSequence *>(data(buf)), 8 * sizeof(ResultType) * size(buf), Xoofff_FlagNone) != 0)
			{
				throw std::runtime_error{"Xoofff_Expand"};
			}

			ptr = {};
		}

		return buf[ptr++];
	}
};

As long as the key remains a secret, this Xoofff-based generator will produce uniformly random bits that are computationally indistinguishable from true randomness. Note that I also maintain a buffer to take advantage of parallelism. This bit generator is blazing fast: 34.97 picoseconds per bit (3.33 GiB per second) on an Intel Xeon Silver 4110 CPU with AVX-512, on a single thread. As if this isn't powerful enough, we can now plug it into any of the provided distributions like so:

Xoofff_Instance xoofff{};
Xoofff_MaskDerivation(&xoofff, ...);
Xoofff_Compress(&xoofff, ...);

Xoofff_Generator gen{xoofff};
std::binomial_distribution dist{1'000, 0.5};
std::cout << "Number of heads in 1,000 flips: " << dist(gen) << std::endl;

The best part about all of this is that we don't need to reinvent the wheel as far as finding an efficient algorithm for drawing random numbers according to a binomial distribution. We can simply use the one provided to us from the standard library, and pass the custom generator into it.

This article sums up why C++ is my favorite language. A lot of thought goes into the design of the standard libraries (performance, extensibility, usability, ...), and I believe the random number library is a prime example of this.