Custom impl of std::random_device?

[kripken]

Right now we use libc++'s impl, which accesses /dev/random as a file. That brings in the filesystem support code which is bad for code size, and also as filesystem code it currently gets proxied to the main thread.

Instead, a simple C++ impl could just call emscripten_random which calls into JS.

This might be upstreamable into libc++. If not, maybe we can have a directory of things that override the default files in libc++?

[sbc100]

A separate file or a local patch to libc++ seem reasonable.

Upstream would be even better

[Akaricchi]

Instead, a simple C++ impl could just call emscripten_random which calls into JS.

emscripten_random just calls Math.random, which isn't cryptographically secure. On the other hand, /dev/random is emulated with the crypto API, and actually refuses to work if that's not available. So do we want std::random_device to be a real entropy source or not? cppreference says it's fine to implement it as a deterministic PRNG (it says nothing about the nature or quality of the PRNG):

std::random_device may be implemented in terms of an implementation-defined pseudo-random number engine if a non-deterministic source (e.g. a hardware device) is not available to the implementation. In this case each std::random_device object may generate the same number sequence.

If we don't care about real randomness, then wouldn't it be better to implement a tiny and fast PRNG in C++ like splitmix64 or the xoshiro family, to avoid calling into JS every time? emscripten_random can be used to just seed it once.

Otherwise, crypto.getRandomValues should be exposed more directly by emscripten (an emscripten_get_entropy function?)

[kripken]

Good points @Akaricchi . Yeah, given the spec doesn't seem to say much about the quality of the random numbers, then Math.random might be best for code size, unless a custom PRNG can be almost equally small? If it's reasonable close then that sounds good for avoiding JS, yes.

[Akaricchi]

Well here's SplitMix64

uint64_t splitmix64(uint64_t *state) {
	uint64_t z = (*state += 0x9e3779b97f4a7c15);
	z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
	z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
	return z ^ (z >> 31);
}

And xoshiro256**

static inline uint64_t rotl(const uint64_t x, int k) {
	return (x << k) | (x >> (64 - k));
}

static uint64_t s[4];

uint64_t next(void) {
	const uint64_t result = rotl(s[1] * 5, 7) * 9;

	const uint64_t t = s[1] << 17;

	s[2] ^= s[0];
	s[3] ^= s[1];
	s[1] ^= s[2];
	s[0] ^= s[3];

	s[2] ^= t;

	s[3] = rotl(s[3], 45);

	return result;
}

There are plenty other potential options too.

[sbc100]

Unless we have a compelling reason I think we should just call the existing emscripten JS function rather than inventing more than one way to do this.

[kripken]

I think the JS function is documented as pointing to Math.random, so it has that behavior. But std::random_device according to the spec doesn't need those requirements, and implementing a fast compact PRNG in C would be more efficient (avoiding calls to JS).

I'd be in favor of the most compact of the reasonable C PRNGs.

[ad8e]

My cultural understanding of std::random_device is that its major purpose is to act as a seed sequence, and that its fallback to determinism is seen as a regretful spec mistake. (Even without this problem, it has other critical flaws.) "return 0;" can be considered for a deterministic std::random_device. This is because no deterministic PRNG satisfies the main purpose of providing a seed sequence, so an obviously failing sequence has some advantages over a "secretly" failing sequence.

Fine C PRNGs are:

http://prng.di.unimi.it/xoshiro128plusplus.c
https://en.wikipedia.org/wiki/Permuted_congruential_generator#Example_code
https://github.com/svaarala/duktape/blob/master/misc/splitmix64.c

They are all reasonably small and behave reasonably well. The performance and quality difference between them is marginal for reasonable uses of std::random_device. Other PRNGs, sorted by most recent first, may also be fine, but there's little point in testing them.

[peteroupc]

My cultural understanding of std::random_device is that its major purpose is to act as a seed sequence, and that its fallback to determinism is seen as a regretful spec mistake. (Even without this problem, it has other critical flaws.) "return 0;" can be considered for a deterministic std::random_device. This is because no deterministic PRNG satisfies the main purpose of providing a seed sequence, so an obviously failing sequence has some advantages over a "secretly" failing sequence.

And in fact, the situation with random_device in this respect may get much worse: cplusplus/papers#786 . Here, it seems that the direction is to "bring a proposal for deprecating std::random_device::entropy", which is the only way, in theory, to determine whether random_device is implemented as a deterministic engine. With such a change, random_device could eventually go from "falling back to a random engine without much warning" to "falling back to a random engine without any warning at all". As this Stack Overflow question shows, this problem is not merely theoretical.