I made a couple new versions of a new kind of arc4random_uniform-like function and some example functions which use them. Instead of having a sufficiently large random number greater than the modulus, I pick a random number using arc4random() from a bitfield where the length of the bitfield is just below or slightly beyond the value of the modulus and returns the bitfield it if it is less than the value of the modulus.
In both versions, I retrieve a bitfield from a static uint64_t which is
refreshed from periodic arc4random() calls. The functions demand a bit
length. but I provide a convenient bitsize search function:
arc4random_uniform_fast_bitsearch()
in the first version, if the chosen return value isn't less than the
modulus, the entire bitfield is trashed and a completely new bitfield is
refreshed from the cache. This can be very inefficient and for certain
upperbounds where the functions demand that all returned values less than
the upperbound are possible. This can perform worse than
arc4random_uniform() even with more random number generation churn.
in the second version, if the chosen return value isn't less than the
modulus, the bitfield is shifted right, losing the least significant bit
and a new random-value bit from the least significant bit of the cache is
put into the most significant bit of the bitfield and it tries again. For
significant expenditures of effort, this version is always more efficient
than arc4random_uniform() and slightly to much more efficient than my first
version.
The performance boost comes from less pseudorandom number generation by not
trashing perfectly good random data and preserving it so that rekeying is
performed less.
I suspect that the first version may be secure, but I'm now sure what you
think of the second version, for being secure. Is there a way to test how
well distributed and secure it is?!
Perhaps it's even better than the typical use case of arc4random_uniform
since it feeds it a bitstream instead of performing a modulous operation on
it!
I pledge("stdio") and unveil(NULL, NULL) at the beginning, so you know it
doesn't do anything but malloc() an array, do stuff on the array and print
stuff; if you don't profile, anyway.
What do you think of having such a thing in OpenBSD?
newdata() generates random a-z characters performing arc4random_uniform(26);
newdataTypableFilename() generates random filename typable characters
performing arc4random_uniform(92);
I perform other tests including presumed worst-cases on large numbers and
numbers which will have a lot of misses.
-Luke
arc4random_uniform_fast.c
Description: Binary data
