Purpose

A better random number generator by using an entropy pool.

Overview

(Stock RNG sucks) The stock random number generator (RNG) provided in Q3A uses a cyclic PRNG (pseudo-random number generator) function. In effect, such a PRNG marches through a very long and predetermined (predictable) list of pseudo-random numbers; where the PRNG starts marching down is determined by the seed value. There are many way of mixing up the manner in which a PRNG marches down its list, but many of them tends to involve deterministic mechanisms, that is, using another function to predictably alter the way another function predictably works.

(How RNG can be improved) Among the better ways of mixing up a PRNG is to sample sources of nondeterministic (unpredictable) numbers as seed values. Common nondeterministic sources include TV/radio static, user's mouse movements, background noise (aural, atmospheric, cosmic), the radiation from a small amount of radioactive isotope, and the time it takes for MS-Windows to crash. Within the confines of the Q3VM, there are few choices of nondeterministic numbers. These choices include the initial random number seed provided to G_InitGame(), usercmds, and some structs associated with non-bot players.

(The entropy pool) An entropy pool holds a large number of ordered bits (this implementation uses 2048 bits), nominally a random collection of bits (0's and 1's scattered randomly). Samples from a nondeterministic source are mixed into the pool by using a stirring function. This stirring is a way of spreading out the bits from the source throughout the pool, instead of pushed into one little corner. Though the stirring function itself is inherently deterministic, the nondeterministism of the source value "taints" the predictability of the stirring function -- that is, though "how" the function works is predictable, the "what" it uses and makes is not -- aka Garbage-In-Garbage-Out (GIGO). Ideally, a random number can be pulled from anywhere in the pool. The first 32 bits ought to be just as good as the last 32 bits.

Usage

Create an instance of a noiz_t struct in g_main.c:
noiz_t noiz;

Make the instance globally visible in g_local.h:
extern noiz_t noiz;

Initialize the entropy pool in G_InitGame() (in g_main.c):
noiz_init(&noiz);

(optional) Deinitalize the entropy pool in G_ShutdownGame() (in g_main.c):
noiz_destroy(&noiz);

(optional) Call noiz_alarm() to enable autosaving of pool state in G_RunFrame() (g_main.c):
noiz_alarm(&noiz);

Stir the pool with noiz_stir() (anywhere...):
noiz_stir(&noiz, (unsigned char*)&somestruct, sizeof(somestruct));
Or use the NOIZ_STIR macro, which assumes "noiz" and "sizeof(somestruct)":
NOIZ_STIR(somestruct); /* no & needed */

Retrieve a random number by storing the return value of noiz_stir(); use NULL for the source if nothing else is adequate, or the macro NOIZ_RAND (use in place of rand() or Q_rand()):
int randomval = noiz_stir(&noiz, (unsigned char*)&somestruct, sizeof(somestruct));
int randomval = NOIZ_STIR(somestruct);
int randomval = noiz_stir(&noiz, NULL, 0);
int randomval = NOIZ_RAND();

Limitations

The quality of random numbers depends on the sampled sources of entropy. Bad sources result in bad randomness.

The randomness of this RNG has not been tested, though it is certainly more nondeterministic than the stock Q3A PRNG (if the noiz_stir() calls are used properly...).

Programming Notes

The RNG is based on noiz-0.5.

When noiz_stir() is given a NULL or zero-length source ("retrieve-only without stirring"), the function starts stepping through each 32 bits in the pool without actually stirring. After a sufficient number of NULL stirs, the function stirs with a NULL source anyway. Doing so introduces determinism, but it avoids recycling bit sequences.

The entropy pool state is saved in an encoded format into cvar "g_noiz", marked for Archive (written to q3config.cfg). The format is a hex digit for each nibble. With 256 bytes in the pool state, the format (513 bytes) exceeds the Q3VM (but not the Q3 engine's!) limit for a cvar string value (256 bytes). Using a vmCvar_t is not possible without changing the conversion format.

Storing the pool into an archived cvar means the pool state can be persistently restored on next server (re)start. This helps maintain the nondeterminancy across server (and game) sessions, instead of starting over with the same initial pool all the time.

The stirring function is the RSA Message Digest 5 (MD5) algorithm. The implementation used was written by Ron Rivest, and priorly tested for equivalence to RSA's implementation (the code comments say it's equivalent).


Files provided as-is:
qnoiz.c
qnoiz.h
qmd5.c
qmd5.h

ChangeLog:
2002.10.26
Update to qnoiz.c, fixed logic error where noiz_stir didn't read entropy source at all.
2002.10.12
Initial release

-- PhaethonH (phaethon@linux.ucla.edu)