Page MenuHomeFreeBSD
Differential D23288 Diff 67233 head/lib/libc/stdlib/random.c

Changeset View

Standalone View

View Options

head/lib/libc/stdlib/random.c

Show First 20 Lines • Show All 138 Lines • ▼ Show 20 Lines
*/ */
#define MAX_TYPES 5 /* max number of types above */ #define MAX_TYPES 5 /* max number of types above */
#define NSHUFF 50 /* to drop some "seed -> 1st value" linearity */ #define NSHUFF 50 /* to drop some "seed -> 1st value" linearity */
static const int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; static const int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
static const int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; static const int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
/* A full instance of the random(3) generator. */
struct random_state {
uint32_t *rst_fptr;
uint32_t *rst_rptr;
uint32_t *rst_state;
int rst_type;
int rst_deg;
int rst_sep;
uint32_t *rst_end_ptr;
/* Flexible array member must be last. */
uint32_t rst_randtbl[];
};
/* /*
* Initially, everything is set up as if from: * Initially, everything is set up as if from:
* *
* initstate(1, randtbl, 128); * initstate(1, randtbl, 128);
* *
* Note that this initialization takes advantage of the fact that srandom() * Note that this initialization takes advantage of the fact that srandom()
* advances the front and rear pointers 10*rand_deg times, and hence the * advances the front and rear pointers 10*rand_deg times, and hence the
* rear pointer which starts at 0 will also end up at zero; thus the zeroeth * rear pointer which starts at 0 will also end up at zero; thus the zeroeth
* element of the state information, which contains info about the current * element of the state information, which contains info about the current
* position of the rear pointer is just * position of the rear pointer is just
* *
* MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3. * MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3.
*/ */
static struct random_state implicit = {
static uint32_t randtbl[DEG_3 + 1] = { .rst_randtbl = {
TYPE_3, TYPE_3,
0x2cf41758, 0x27bb3711, 0x4916d4d1, 0x7b02f59f, 0x9b8e28eb, 0xc0e80269, 0x2cf41758, 0x27bb3711, 0x4916d4d1, 0x7b02f59f, 0x9b8e28eb, 0xc0e80269,
0x696f5c16, 0x878f1ff5, 0x52d9c07f, 0x916a06cd, 0xb50b3a20, 0x2776970a, 0x696f5c16, 0x878f1ff5, 0x52d9c07f, 0x916a06cd, 0xb50b3a20, 0x2776970a,
0xee4eb2a6, 0xe94640ec, 0xb1d65612, 0x9d1ed968, 0x1043f6b7, 0xa3432a76, 0xee4eb2a6, 0xe94640ec, 0xb1d65612, 0x9d1ed968, 0x1043f6b7, 0xa3432a76,
0x17eacbb9, 0x3c09e2eb, 0x4f8c2b3, 0x708a1f57, 0xee341814, 0x95d0e4d2, 0x17eacbb9, 0x3c09e2eb, 0x4f8c2b3, 0x708a1f57, 0xee341814, 0x95d0e4d2,
0xb06f216c, 0x8bd2e72e, 0x8f7c38d7, 0xcfc6a8fc, 0x2a59495, 0xa20d2a69, 0xb06f216c, 0x8bd2e72e, 0x8f7c38d7, 0xcfc6a8fc, 0x2a59495, 0xa20d2a69,
0xe29d12d1 0xe29d12d1
}; },
/* /*
* fptr and rptr are two pointers into the state info, a front and a rear * fptr and rptr are two pointers into the state info, a front and a rear
* pointer. These two pointers are always rand_sep places aparts, as they * pointer. These two pointers are always rand_sep places aparts, as they
* cycle cyclically through the state information. (Yes, this does mean we * cycle cyclically through the state information. (Yes, this does mean we
* could get away with just one pointer, but the code for random() is more * could get away with just one pointer, but the code for random() is more
* efficient this way). The pointers are left positioned as they would be * efficient this way). The pointers are left positioned as they would be
* from the call * from the call
* *
* initstate(1, randtbl, 128); * initstate(1, randtbl, 128);
* *
* (The position of the rear pointer, rptr, is really 0 (as explained above * (The position of the rear pointer, rptr, is really 0 (as explained above
* in the initialization of randtbl) because the state table pointer is set * in the initialization of randtbl) because the state table pointer is set
* to point to randtbl[1] (as explained below). * to point to randtbl[1] (as explained below).
*/ */
static uint32_t *fptr = &randtbl[SEP_3 + 1]; .rst_fptr = &implicit.rst_randtbl[SEP_3 + 1],
static uint32_t *rptr = &randtbl[1]; .rst_rptr = &implicit.rst_randtbl[1],
/* /*
* The following things are the pointer to the state information table, the * The following things are the pointer to the state information table, the
* type of the current generator, the degree of the current polynomial being * type of the current generator, the degree of the current polynomial being
* used, and the separation between the two pointers. Note that for efficiency * used, and the separation between the two pointers. Note that for efficiency
* of random(), we remember the first location of the state information, not * of random(), we remember the first location of the state information, not
* the zeroeth. Hence it is valid to access state[-1], which is used to * the zeroeth. Hence it is valid to access state[-1], which is used to
* store the type of the R.N.G. Also, we remember the last location, since * store the type of the R.N.G. Also, we remember the last location, since
* this is more efficient than indexing every time to find the address of * this is more efficient than indexing every time to find the address of
* the last element to see if the front and rear pointers have wrapped. * the last element to see if the front and rear pointers have wrapped.
*/ */
static uint32_t *state = &randtbl[1]; .rst_state = &implicit.rst_randtbl[1],
static int rand_type = TYPE_3; .rst_type = TYPE_3,
static int rand_deg = DEG_3; .rst_deg = DEG_3,
static int rand_sep = SEP_3; .rst_sep = SEP_3,
static uint32_t *end_ptr = &randtbl[DEG_3 + 1]; .rst_end_ptr = &implicit.rst_randtbl[DEG_3 + 1],
};
/*
* This is the same low quality PRNG used in rand(3) in FreeBSD 12 and prior.
* It may be sufficient for distributing bits and expanding a small seed
* integer into a larger state.
*/
static inline uint32_t static inline uint32_t
good_rand(uint32_t ctx) parkmiller32(uint32_t ctx)
{ {
/* /*
* Compute x = (7^5 * x) mod (2^31 - 1) * Compute x = (7^5 * x) mod (2^31 - 1)
* wihout overflowing 31 bits: * wihout overflowing 31 bits:
* (2^31 - 1) = 127773 * (7^5) + 2836 * (2^31 - 1) = 127773 * (7^5) + 2836
* From "Random number generators: good ones are hard to find", * From "Random number generators: good ones are hard to find",
* Park and Miller, Communications of the ACM, vol. 31, no. 10, * Park and Miller, Communications of the ACM, vol. 31, no. 10,
* October 1988, p. 1195. * October 1988, p. 1195.
Show All 23 Lines
* introduced by the L.C.R.N.G. Note that the initialization of randtbl[] * introduced by the L.C.R.N.G. Note that the initialization of randtbl[]
* for default usage relies on values produced by this routine. * for default usage relies on values produced by this routine.
*/ */
void void
srandom(unsigned int x) srandom(unsigned int x)
{ {
int i, lim; int i, lim;
state[0] = (uint32_t)x; implicit.rst_state[0] = (uint32_t)x;
if (rand_type == TYPE_0) if (implicit.rst_type == TYPE_0)
lim = NSHUFF; lim = NSHUFF;
else { else {
for (i = 1; i < rand_deg; i++) for (i = 1; i < implicit.rst_deg; i++)
state[i] = good_rand(state[i - 1]); implicit.rst_state[i] =
fptr = &state[rand_sep]; parkmiller32(implicit.rst_state[i - 1]);
rptr = &state[0]; implicit.rst_fptr = &implicit.rst_state[implicit.rst_sep];
lim = 10 * rand_deg; implicit.rst_rptr = &implicit.rst_state[0];
lim = 10 * implicit.rst_deg;
} }
for (i = 0; i < lim; i++) for (i = 0; i < lim; i++)
(void)random(); (void)random();
} }
/* /*
* srandomdev: * srandomdev:
* *
* Many programs choose the seed value in a totally predictable manner. * Many programs choose the seed value in a totally predictable manner.
* This often causes problems. We seed the generator using pseudo-random * This often causes problems. We seed the generator using pseudo-random
* data from the kernel. * data from the kernel.
* *
* Note that this particular seeding procedure can generate states * Note that this particular seeding procedure can generate states
* which are impossible to reproduce by calling srandom() with any * which are impossible to reproduce by calling srandom() with any
* value, since the succeeding terms in the state buffer are no longer * value, since the succeeding terms in the state buffer are no longer
* derived from the LC algorithm applied to a fixed seed. * derived from the LC algorithm applied to a fixed seed.
*/ */
void void
srandomdev(void) srandomdev(void)
{ {
int mib[2]; int mib[2];
size_t expected, len; size_t expected, len;
if (rand_type == TYPE_0) if (implicit.rst_type == TYPE_0)
expected = len = sizeof(state[0]); len = sizeof(implicit.rst_state[0]);
else else
expected = len = rand_deg * sizeof(state[0]); len = implicit.rst_deg * sizeof(implicit.rst_state[0]);
expected = len;
mib[0] = CTL_KERN; mib[0] = CTL_KERN;
mib[1] = KERN_ARND; mib[1] = KERN_ARND;
if (sysctl(mib, 2, state, &len, NULL, 0) == -1 || len != expected) { if (sysctl(mib, 2, implicit.rst_state, &len, NULL, 0) == -1 ||
len != expected) {
/* /*
* The sysctl cannot fail. If it does fail on some FreeBSD * The sysctl cannot fail. If it does fail on some FreeBSD
* derivative or after some future change, just abort so that * derivative or after some future change, just abort so that
* the problem will be found and fixed. abort is not normally * the problem will be found and fixed. abort is not normally
* suitable for a library but makes sense here. * suitable for a library but makes sense here.
*/ */
abort(); abort();
} }
if (rand_type != TYPE_0) { if (implicit.rst_type != TYPE_0) {
fptr = &state[rand_sep]; implicit.rst_fptr = &implicit.rst_state[implicit.rst_sep];
rptr = &state[0]; implicit.rst_rptr = &implicit.rst_state[0];
} }
} }
/* /*
* initstate: * initstate:
* *
* Initialize the state information in the given array of n bytes for future * Initialize the state information in the given array of n bytes for future
* random number generation. Based on the number of bytes we are given, and * random number generation. Based on the number of bytes we are given, and
Show All 13 Lines
* *
* Note: The Sparc platform requires that arg_state begin on an int * Note: The Sparc platform requires that arg_state begin on an int
* word boundary; otherwise a bus error will occur. Even so, lint will * word boundary; otherwise a bus error will occur. Even so, lint will
* complain about mis-alignment, but you should disregard these messages. * complain about mis-alignment, but you should disregard these messages.
*/ */
char * char *
initstate(unsigned int seed, char *arg_state, size_t n) initstate(unsigned int seed, char *arg_state, size_t n)
{ {
char *ostate = (char *)(&state[-1]); char *ostate = (char *)(&implicit.rst_state[-1]);
uint32_t *int_arg_state = (uint32_t *)arg_state; uint32_t *int_arg_state = (uint32_t *)arg_state;
if (n < BREAK_0) if (n < BREAK_0)
return (NULL); return (NULL);
if (rand_type == TYPE_0) if (implicit.rst_type == TYPE_0)
state[-1] = rand_type; implicit.rst_state[-1] = implicit.rst_type;
else else
state[-1] = MAX_TYPES * (rptr - state) + rand_type; implicit.rst_state[-1] = MAX_TYPES *
(implicit.rst_rptr - implicit.rst_state) +
implicit.rst_type;
if (n < BREAK_1) { if (n < BREAK_1) {
rand_type = TYPE_0; implicit.rst_type = TYPE_0;
rand_deg = DEG_0; implicit.rst_deg = DEG_0;
rand_sep = SEP_0; implicit.rst_sep = SEP_0;
} else if (n < BREAK_2) { } else if (n < BREAK_2) {
rand_type = TYPE_1; implicit.rst_type = TYPE_1;
rand_deg = DEG_1; implicit.rst_deg = DEG_1;
rand_sep = SEP_1; implicit.rst_sep = SEP_1;
} else if (n < BREAK_3) { } else if (n < BREAK_3) {
rand_type = TYPE_2; implicit.rst_type = TYPE_2;
rand_deg = DEG_2; implicit.rst_deg = DEG_2;
rand_sep = SEP_2; implicit.rst_sep = SEP_2;
} else if (n < BREAK_4) { } else if (n < BREAK_4) {
rand_type = TYPE_3; implicit.rst_type = TYPE_3;
rand_deg = DEG_3; implicit.rst_deg = DEG_3;
rand_sep = SEP_3; implicit.rst_sep = SEP_3;
} else { } else {
rand_type = TYPE_4; implicit.rst_type = TYPE_4;
rand_deg = DEG_4; implicit.rst_deg = DEG_4;
rand_sep = SEP_4; implicit.rst_sep = SEP_4;
} }
state = int_arg_state + 1; /* first location */ implicit.rst_state = int_arg_state + 1; /* first location */
end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */ /* must set end_ptr before srandom */
implicit.rst_end_ptr = &implicit.rst_state[implicit.rst_deg];
srandom(seed); srandom(seed);
if (rand_type == TYPE_0) if (implicit.rst_type == TYPE_0)
int_arg_state[0] = rand_type; int_arg_state[0] = implicit.rst_type;
else else
int_arg_state[0] = MAX_TYPES * (rptr - state) + rand_type; int_arg_state[0] = MAX_TYPES *
(implicit.rst_rptr - implicit.rst_state) +
implicit.rst_type;
return (ostate); return (ostate);
} }
/* /*
* setstate: * setstate:
* *
* Restore the state from the given state array. * Restore the state from the given state array.
* *
Show All 12 Lines
* complain about mis-alignment, but you should disregard these messages. * complain about mis-alignment, but you should disregard these messages.
*/ */
char * char *
setstate(char *arg_state) setstate(char *arg_state)
{ {
uint32_t *new_state = (uint32_t *)arg_state; uint32_t *new_state = (uint32_t *)arg_state;
uint32_t type = new_state[0] % MAX_TYPES; uint32_t type = new_state[0] % MAX_TYPES;
uint32_t rear = new_state[0] / MAX_TYPES; uint32_t rear = new_state[0] / MAX_TYPES;
char *ostate = (char *)(&state[-1]); char *ostate = (char *)(&implicit.rst_state[-1]);
if (type != TYPE_0 && rear >= degrees[type]) if (type != TYPE_0 && rear >= degrees[type])
return (NULL); return (NULL);
if (rand_type == TYPE_0) if (implicit.rst_type == TYPE_0)
state[-1] = rand_type; implicit.rst_state[-1] = implicit.rst_type;
else else
state[-1] = MAX_TYPES * (rptr - state) + rand_type; implicit.rst_state[-1] = MAX_TYPES *
rand_type = type; (implicit.rst_rptr - implicit.rst_state) +
rand_deg = degrees[type]; implicit.rst_type;
rand_sep = seps[type]; implicit.rst_type = type;
state = new_state + 1; implicit.rst_deg = degrees[type];
if (rand_type != TYPE_0) { implicit.rst_sep = seps[type];
rptr = &state[rear]; implicit.rst_state = new_state + 1;
fptr = &state[(rear + rand_sep) % rand_deg]; if (implicit.rst_type != TYPE_0) {
implicit.rst_rptr = &implicit.rst_state[rear];
implicit.rst_fptr = &implicit.rst_state[
(rear + implicit.rst_sep) % implicit.rst_deg];
} }
end_ptr = &state[rand_deg]; /* set end_ptr too */ implicit.rst_end_ptr = &implicit.rst_state[implicit.rst_deg];
return (ostate); return (ostate);
} }
/* /*
* random: * random:
* *
* If we are using the trivial TYPE_0 R.N.G., just do the old linear * If we are using the trivial TYPE_0 R.N.G., just do the old linear
* congruential bit. Otherwise, we do our fancy trinomial stuff, which is * congruential bit. Otherwise, we do our fancy trinomial stuff, which is
Show All 10 Lines
* Returns a 31-bit random number. * Returns a 31-bit random number.
*/ */
long long
random(void) random(void)
{ {
uint32_t i; uint32_t i;
uint32_t *f, *r; uint32_t *f, *r;
if (rand_type == TYPE_0) { if (implicit.rst_type == TYPE_0) {
i = state[0]; i = implicit.rst_state[0];
state[0] = i = good_rand(i); i = parkmiller32(i);
implicit.rst_state[0] = i;
} else { } else {
/* /*
* Use local variables rather than static variables for speed. * Use local variables rather than static variables for speed.
*/ */
f = fptr; r = rptr; f = implicit.rst_fptr;
r = implicit.rst_rptr;
*f += *r; *f += *r;
i = *f >> 1; /* chucking least random bit */ i = *f >> 1; /* chucking least random bit */
if (++f >= end_ptr) { if (++f >= implicit.rst_end_ptr) {
f = state; f = implicit.rst_state;
++r; ++r;
} }
else if (++r >= end_ptr) { else if (++r >= implicit.rst_end_ptr) {
r = state; r = implicit.rst_state;
} }
fptr = f; rptr = r; implicit.rst_fptr = f;
implicit.rst_rptr = r;
} }
return ((long)i); return ((long)i);
} }