Differential D23289 Diff 67234 head/lib/libc/stdlib/random.c

Changeset View

Standalone View

head/lib/libc/stdlib/random.c

	Show All 32 Lines
	static char sccsid[] = "@(#)random.c 8.2 (Berkeley) 5/19/95";			static char sccsid[] = "@(#)random.c 8.2 (Berkeley) 5/19/95";
	#endif /* LIBC_SCCS and not lint */			#endif /* LIBC_SCCS and not lint */
	#include <sys/cdefs.h>			#include <sys/cdefs.h>
	__FBSDID("$FreeBSD$");			__FBSDID("$FreeBSD$");

	#include "namespace.h"			#include "namespace.h"
	#include <sys/param.h>			#include <sys/param.h>
	#include <sys/sysctl.h>			#include <sys/sysctl.h>
				#include <errno.h>
	#include <stdint.h>			#include <stdint.h>
	#include <stdlib.h>			#include <stdlib.h>
	#include "un-namespace.h"			#include "un-namespace.h"

				#include "random.h"

	/*			/*
	* random.c:			* random.c:
	*			*
	* An improved random number generation package. In addition to the standard			* An improved random number generation package. In addition to the standard
	* rand()/srand() like interface, this package also has a special state info			* rand()/srand() like interface, this package also has a special state info
	* interface. The initstate() routine is called with a seed, an array of			* interface. The initstate() routine is called with a seed, an array of
	* bytes, and a count of how many bytes are being passed in; this array is			* bytes, and a count of how many bytes are being passed in; this array is
	* then initialized to contain information for random number generation with			* then initialized to contain information for random number generation with
	▲ Show 20 Lines • Show All 86 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 struct __random_state implicit = {
	.rst_randtbl = {			.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
	▲ Show 20 Lines • Show All 70 Lines • ▼ Show 20 Lines
	* Otherwise, initializes state[] based on the given "seed" via a linear			* Otherwise, initializes state[] based on the given "seed" via a linear
	* congruential generator. Then, the pointers are set to known locations			* congruential generator. Then, the pointers are set to known locations
	* that are exactly rand_sep places apart. Lastly, it cycles the state			* that are exactly rand_sep places apart. Lastly, it cycles the state
	* information a given number of times to get rid of any initial dependencies			* information a given number of times to get rid of any initial dependencies
	* 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_r(struct __random_state *estate, unsigned x)
	{			{
	int i, lim;			int i, lim;

	implicit.rst_state[0] = (uint32_t)x;			estate->rst_state[0] = (uint32_t)x;
	if (implicit.rst_type == TYPE_0)			if (estate->rst_type == TYPE_0)
	lim = NSHUFF;			lim = NSHUFF;
	else {			else {
	for (i = 1; i < implicit.rst_deg; i++)			for (i = 1; i < estate->rst_deg; i++)
	implicit.rst_state[i] =			estate->rst_state[i] =
	parkmiller32(implicit.rst_state[i - 1]);			parkmiller32(estate->rst_state[i - 1]);
	implicit.rst_fptr = &implicit.rst_state[implicit.rst_sep];			estate->rst_fptr = &estate->rst_state[estate->rst_sep];
	implicit.rst_rptr = &implicit.rst_state[0];			estate->rst_rptr = &estate->rst_state[0];
	lim = 10 * implicit.rst_deg;			lim = 10 * estate->rst_deg;
	}			}
	for (i = 0; i < lim; i++)			for (i = 0; i < lim; i++)
	(void)random();			(void)random_r(estate);
	}			}

				void
				srandom(unsigned x)
				{
				srandom_r(&implicit, x);
				}

	/*			/*
	* 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_r(struct __random_state *estate)
	{			{
	int mib[2];			int mib[2];
	size_t expected, len;			size_t expected, len;

	if (implicit.rst_type == TYPE_0)			if (estate->rst_type == TYPE_0)
	len = sizeof(implicit.rst_state[0]);			len = sizeof(estate->rst_state[0]);
	else			else
	len = implicit.rst_deg * sizeof(implicit.rst_state[0]);			len = estate->rst_deg * sizeof(estate->rst_state[0]);
	expected = len;			expected = len;

	mib[0] = CTL_KERN;			mib[0] = CTL_KERN;
	mib[1] = KERN_ARND;			mib[1] = KERN_ARND;
	if (sysctl(mib, 2, implicit.rst_state, &len, NULL, 0) == -1 \|\|			if (sysctl(mib, 2, estate->rst_state, &len, NULL, 0) == -1 \|\|
	len != expected) {			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 (implicit.rst_type != TYPE_0) {			if (estate->rst_type != TYPE_0) {
	implicit.rst_fptr = &implicit.rst_state[implicit.rst_sep];			estate->rst_fptr = &estate->rst_state[estate->rst_sep];
	implicit.rst_rptr = &implicit.rst_state[0];			estate->rst_rptr = &estate->rst_state[0];
	}			}
	}			}

				void
				srandomdev(void)
				{
				srandomdev_r(&implicit);
				}

	/*			/*
	* initstate:			* initstate_r:
	*			*
	* 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
	* the break values for the different R.N.G.'s, we choose the best (largest)			* the break values for the different R.N.G.'s, we choose the best (largest)
	* one we can and set things up for it. srandom() is then called to			* one we can and set things up for it. srandom() is then called to
	* initialize the state information.			* initialize the state information.
	*			*
	* Note that on return from srandom(), we set state[-1] to be the type			* Returns zero on success, or an error number on failure.
	* multiplexed with the current value of the rear pointer; this is so
	* successive calls to initstate() won't lose this information and will be
	* able to restart with setstate().
	*			*
				* Note: There is no need for a setstate_r(); just use a new context.
				*/
				int
				initstate_r(struct __random_state estate, unsigned seed, uint32_t arg_state,
				size_t sz)
				{
				if (sz < BREAK_0)
				return (EINVAL);

				if (sz < BREAK_1) {
				estate->rst_type = TYPE_0;
				estate->rst_deg = DEG_0;
				estate->rst_sep = SEP_0;
				} else if (sz < BREAK_2) {
				estate->rst_type = TYPE_1;
				estate->rst_deg = DEG_1;
				estate->rst_sep = SEP_1;
				} else if (sz < BREAK_3) {
				estate->rst_type = TYPE_2;
				estate->rst_deg = DEG_2;
				estate->rst_sep = SEP_2;
				} else if (sz < BREAK_4) {
				estate->rst_type = TYPE_3;
				estate->rst_deg = DEG_3;
				estate->rst_sep = SEP_3;
				} else {
				estate->rst_type = TYPE_4;
				estate->rst_deg = DEG_4;
				estate->rst_sep = SEP_4;
				}
				estate->rst_state = arg_state + 1;
				estate->rst_end_ptr = &estate->rst_state[estate->rst_deg];
				srandom_r(estate, seed);
				return (0);
				}

				/*
				* initstate:
				*
	* Note: the first thing we do is save the current state, if any, just like			* Note: the first thing we do is save the current state, if any, just like
	* setstate() so that it doesn't matter when initstate is called.			* setstate() so that it doesn't matter when initstate is called.
	*			*
				* Note that on return from initstate_r(), we set state[-1] to be the type
				* multiplexed with the current value of the rear pointer; this is so
				* successive calls to initstate() won't lose this information and will be able
				* to restart with setstate().
				*
	* Returns a pointer to the old state.			* Returns a pointer to the old state.
	*			*
	* Note: The Sparc platform requires that arg_state begin on an int			* Despite the misleading "char *" type, arg_state must alias an array of
	* word boundary; otherwise a bus error will occur. Even so, lint will			* 32-bit unsigned integer values. Naturally, such an array is 32-bit aligned.
	* complain about mis-alignment, but you should disregard these messages.			* Usually objects are naturally aligned to at least 32-bits on all platforms,
				* but if you treat the provided 'state' as char* you may inadvertently
				* misalign it. Don't do that.
	*/			*/
	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 )(&implicit.rst_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;
				int error;

	if (n < BREAK_0)			/*
	return (NULL);			* Persist rptr offset and rst_type in the first word of the prior
				* state we are replacing.
				*/
	if (implicit.rst_type == TYPE_0)			if (implicit.rst_type == TYPE_0)
	implicit.rst_state[-1] = implicit.rst_type;			implicit.rst_state[-1] = implicit.rst_type;
	else			else
	implicit.rst_state[-1] = MAX_TYPES *			implicit.rst_state[-1] = MAX_TYPES *
	(implicit.rst_rptr - implicit.rst_state) +			(implicit.rst_rptr - implicit.rst_state) +
	implicit.rst_type;			implicit.rst_type;
	if (n < BREAK_1) {
	implicit.rst_type = TYPE_0;			error = initstate_r(&implicit, seed, int_arg_state, n);
	implicit.rst_deg = DEG_0;			if (error != 0)
	implicit.rst_sep = SEP_0;			return (NULL);
	} else if (n < BREAK_2) {
	implicit.rst_type = TYPE_1;			/*
	implicit.rst_deg = DEG_1;			* Persist rptr offset and rst_type of the new state in its first word.
	implicit.rst_sep = SEP_1;			*/
	} else if (n < BREAK_3) {
	implicit.rst_type = TYPE_2;
	implicit.rst_deg = DEG_2;
	implicit.rst_sep = SEP_2;
	} else if (n < BREAK_4) {
	implicit.rst_type = TYPE_3;
	implicit.rst_deg = DEG_3;
	implicit.rst_sep = SEP_3;
	} else {
	implicit.rst_type = TYPE_4;
	implicit.rst_deg = DEG_4;
	implicit.rst_sep = SEP_4;
	}
	implicit.rst_state = int_arg_state + 1; /* first location */
	/* must set end_ptr before srandom */
	implicit.rst_end_ptr = &implicit.rst_state[implicit.rst_deg];
	srandom(seed);
	if (implicit.rst_type == TYPE_0)			if (implicit.rst_type == TYPE_0)
	int_arg_state[0] = implicit.rst_type;			int_arg_state[0] = implicit.rst_type;
	else			else
	int_arg_state[0] = MAX_TYPES *			int_arg_state[0] = MAX_TYPES *
	(implicit.rst_rptr - implicit.rst_state) +			(implicit.rst_rptr - implicit.rst_state) +
	implicit.rst_type;			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 20 Lines • Show All 53 Lines • ▼ Show 20 Lines
	*			*
	* Note: the code takes advantage of the fact that both the front and			* Note: the code takes advantage of the fact that both the front and
	* rear pointers can't wrap on the same call by not testing the rear			* rear pointers can't wrap on the same call by not testing the rear
	* pointer if the front one has wrapped.			* pointer if the front one has wrapped.
	*			*
	* Returns a 31-bit random number.			* Returns a 31-bit random number.
	*/			*/
	long			long
	random(void)			random_r(struct __random_state *estate)
	{			{
	uint32_t i;			uint32_t i;
	uint32_t f, r;			uint32_t f, r;

	if (implicit.rst_type == TYPE_0) {			if (estate->rst_type == TYPE_0) {
	i = implicit.rst_state[0];			i = estate->rst_state[0];
	i = parkmiller32(i);			i = parkmiller32(i);
	implicit.rst_state[0] = i;			estate->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 = implicit.rst_fptr;			f = estate->rst_fptr;
	r = implicit.rst_rptr;			r = estate->rst_rptr;
	f += r;			f += r;
	i = f >> 1; / chucking least random bit */			i = f >> 1; / chucking least random bit */
	if (++f >= implicit.rst_end_ptr) {			if (++f >= estate->rst_end_ptr) {
	f = implicit.rst_state;			f = estate->rst_state;
	++r;			++r;
	}			}
	else if (++r >= implicit.rst_end_ptr) {			else if (++r >= estate->rst_end_ptr) {
	r = implicit.rst_state;			r = estate->rst_state;
	}			}

	implicit.rst_fptr = f;			estate->rst_fptr = f;
	implicit.rst_rptr = r;			estate->rst_rptr = r;
	}			}
	return ((long)i);			return ((long)i);
				}

				long
				random(void)
				{
				return (random_r(&implicit));
	}			}