1a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*	$NetBSD: random.c,v 1.4 2014/06/12 20:59:46 christos Exp $	*/
2a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
3a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
4a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Copyright (c) 1983, 1993
5a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *	The Regents of the University of California.  All rights reserved.
6a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
7a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Redistribution and use in source and binary forms, with or without
8a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * modification, are permitted provided that the following conditions
9a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * are met:
10a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * 1. Redistributions of source code must retain the above copyright
11a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *    notice, this list of conditions and the following disclaimer.
12a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * 2. Redistributions in binary form must reproduce the above copyright
13a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *    notice, this list of conditions and the following disclaimer in the
14a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *    documentation and/or other materials provided with the distribution.
15a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * 3. Neither the name of the University nor the names of its contributors
16a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *    may be used to endorse or promote products derived from this software
17a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *    without specific prior written permission.
18a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
19a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * SUCH DAMAGE.
30a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
31a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
32a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#if !defined(_KERNEL) && !defined(_STANDALONE)
33a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#include <sys/cdefs.h>
34a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#if defined(LIBC_SCCS) && !defined(lint)
35a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#if 0
36a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic char sccsid[] = "@(#)random.c	8.2 (Berkeley) 5/19/95";
37a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#else
38a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes__RCSID("$NetBSD: random.c,v 1.4 2014/06/12 20:59:46 christos Exp $");
39a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#endif
40a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#endif /* LIBC_SCCS and not lint */
41a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
42a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#include "namespace.h"
43a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
44a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#include <assert.h>
45a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#include <errno.h>
46a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#include <stdlib.h>
47a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#include "reentrant.h"
48a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
49a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#ifdef __weak_alias
50a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes__weak_alias(initstate,_initstate)
51a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes__weak_alias(random,_random)
52a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes__weak_alias(setstate,_setstate)
53a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes__weak_alias(srandom,_srandom)
54a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#endif
55a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
56a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
57a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#ifdef _REENTRANT
58a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic mutex_t random_mutex = MUTEX_INITIALIZER;
59a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#endif
60a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#else
61a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#include <lib/libkern/libkern.h>
62a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define mutex_lock(a)	(void)0
63a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define mutex_unlock(a) (void)0
64a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#endif
65a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
66a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#ifndef SMALL_RANDOM
67a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic void srandom_unlocked(unsigned int);
68a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic long random_unlocked(void);
69a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
70a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define USE_BETTER_RANDOM
71a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
72a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
73a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * random.c:
74a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
75a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * An improved random number generation package.  In addition to the standard
76a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * rand()/srand() like interface, this package also has a special state info
77a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * interface.  The initstate() routine is called with a seed, an array of
78a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * bytes, and a count of how many bytes are being passed in; this array is
79a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * then initialized to contain information for random number generation with
80a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * that much state information.  Good sizes for the amount of state
81a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * information are 32, 64, 128, and 256 bytes.  The state can be switched by
82a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * calling the setstate() routine with the same array as was initiallized
83a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * with initstate().  By default, the package runs with 128 bytes of state
84a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * information and generates far better random numbers than a linear
85a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * congruential generator.  If the amount of state information is less than
86a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * 32 bytes, a simple linear congruential R.N.G. is used.
87a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
88a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Internally, the state information is treated as an array of ints; the
89a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * zeroeth element of the array is the type of R.N.G. being used (small
90a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * integer); the remainder of the array is the state information for the
91a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * R.N.G.  Thus, 32 bytes of state information will give 7 ints worth of
92a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * state information, which will allow a degree seven polynomial.  (Note:
93a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the zeroeth word of state information also has some other information
94a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * stored in it -- see setstate() for details).
95a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
96a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * The random number generation technique is a linear feedback shift register
97a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * approach, employing trinomials (since there are fewer terms to sum up that
98a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * way).  In this approach, the least significant bit of all the numbers in
99a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the state table will act as a linear feedback shift register, and will
100a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * have period 2^deg - 1 (where deg is the degree of the polynomial being
101a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * used, assuming that the polynomial is irreducible and primitive).  The
102a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * higher order bits will have longer periods, since their values are also
103a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * influenced by pseudo-random carries out of the lower bits.  The total
104a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * period of the generator is approximately deg*(2**deg - 1); thus doubling
105a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the amount of state information has a vast influence on the period of the
106a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * generator.  Note: the deg*(2**deg - 1) is an approximation only good for
107a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * large deg, when the period of the shift register is the dominant factor.
108a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * With deg equal to seven, the period is actually much longer than the
109a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * 7*(2**7 - 1) predicted by this formula.
110a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
111a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Modified 28 December 1994 by Jacob S. Rosenberg.
112a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * The following changes have been made:
113a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * All references to the type u_int have been changed to unsigned long.
114a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * All references to type int have been changed to type long.  Other
115a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * cleanups have been made as well.  A warning for both initstate and
116a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * setstate has been inserted to the effect that on Sparc platforms
117a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the 'arg_state' variable must be forced to begin on word boundaries.
118a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * This can be easily done by casting a long integer array to char *.
119a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * The overall logic has been left STRICTLY alone.  This software was
120a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * tested on both a VAX and Sun SpacsStation with exactly the same
121a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * results.  The new version and the original give IDENTICAL results.
122a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * The new version is somewhat faster than the original.  As the
123a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * documentation says:  "By default, the package runs with 128 bytes of
124a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * state information and generates far better random numbers than a linear
125a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * congruential generator.  If the amount of state information is less than
126a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * 32 bytes, a simple linear congruential R.N.G. is used."  For a buffer of
127a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * 128 bytes, this new version runs about 19 percent faster and for a 16
128a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * byte buffer it is about 5 percent faster.
129a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
130a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Modified 07 January 2002 by Jason R. Thorpe.
131a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * The following changes have been made:
132a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * All the references to "long" have been changed back to "int".  This
133a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * fixes memory corruption problems on LP64 platforms.
134a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
135a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
136a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
137a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * For each of the currently supported random number generators, we have a
138a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * break value on the amount of state information (you need at least this
139a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * many bytes of state info to support this random number generator), a degree
140a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * for the polynomial (actually a trinomial) that the R.N.G. is based on, and
141a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the separation between the two lower order coefficients of the trinomial.
142a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
143a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	TYPE_0		0		/* linear congruential */
144a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	BREAK_0		8
145a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	DEG_0		0
146a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	SEP_0		0
147a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
148a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	TYPE_1		1		/* x**7 + x**3 + 1 */
149a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	BREAK_1		32
150a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	DEG_1		7
151a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	SEP_1		3
152a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
153a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	TYPE_2		2		/* x**15 + x + 1 */
154a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	BREAK_2		64
155a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	DEG_2		15
156a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	SEP_2		1
157a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
158a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	TYPE_3		3		/* x**31 + x**3 + 1 */
159a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	BREAK_3		128
160a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	DEG_3		31
161a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	SEP_3		3
162a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
163a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	TYPE_4		4		/* x**63 + x + 1 */
164a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	BREAK_4		256
165a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	DEG_4		63
166a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	SEP_4		1
167a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
168a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
169a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Array versions of the above information to make code run faster --
170a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * relies on fact that TYPE_i == i.
171a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
172a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#define	MAX_TYPES	5		/* max number of types above */
173a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
174a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic const int degrees[MAX_TYPES] =	{ DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
175a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic const int seps[MAX_TYPES] =	{ SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
176a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
177a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
178a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Initially, everything is set up as if from:
179a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
180a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *	initstate(1, &randtbl, 128);
181a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
182a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Note that this initialization takes advantage of the fact that srandom()
183a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * advances the front and rear pointers 10*rand_deg times, and hence the
184a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * rear pointer which starts at 0 will also end up at zero; thus the zeroeth
185a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * element of the state information, which contains info about the current
186a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * position of the rear pointer is just
187a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
188a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *	MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3.
189a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
190a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
191a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/* LINTED */
192a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic int randtbl[DEG_3 + 1] = {
193a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	TYPE_3,
194a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#ifdef USE_BETTER_RANDOM
195a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x991539b1, 0x16a5bce3, 0x6774a4cd,
196a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x3e01511e, 0x4e508aaa, 0x61048c05,
197a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0xf5500617, 0x846b7115, 0x6a19892c,
198a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x896a97af, 0xdb48f936, 0x14898454,
199a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x37ffd106, 0xb58bff9c, 0x59e17104,
200a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0xcf918a49, 0x09378c83, 0x52c7a471,
201a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x8d293ea9, 0x1f4fc301, 0xc3db71be,
202a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1,
203a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x19edc328, 0x87bf4bdd, 0xc9b240e5,
204a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0xe9ee4b1b, 0x4382aee7, 0x535b6b41,
205a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0xf3bec5da,
206a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#else
207a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x9a319039, 0x32d9c024, 0x9b663182,
208a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x5da1f342, 0xde3b81e0, 0xdf0a6fb5,
209a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0xf103bc02, 0x48f340fb, 0x7449e56b,
210a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0xbeb1dbb0, 0xab5c5918, 0x946554fd,
211a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x8c2e680f, 0xeb3d799f, 0xb11ee0b7,
212a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x2d436b86, 0xda672e2a, 0x1588ca88,
213a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0xe369735d, 0x904f35f7, 0xd7158fd6,
214a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x6fa6f051, 0x616e6b96, 0xac94efdc,
215a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x36413f93, 0xc622c298, 0xf5a42ab8,
216a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x8a88d77b, 0xf5ad9d0e, 0x8999220b,
217a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	0x27fb47b9,
218a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#endif /* USE_BETTER_RANDOM */
219a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes};
220a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
221a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
222a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * fptr and rptr are two pointers into the state info, a front and a rear
223a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * pointer.  These two pointers are always rand_sep places aparts, as they
224a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * cycle cyclically through the state information.  (Yes, this does mean we
225a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * could get away with just one pointer, but the code for random() is more
226a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * efficient this way).  The pointers are left positioned as they would be
227a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * from the call
228a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
229a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *	initstate(1, randtbl, 128);
230a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
231a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * (The position of the rear pointer, rptr, is really 0 (as explained above
232a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * in the initialization of randtbl) because the state table pointer is set
233a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * to point to randtbl[1] (as explained below).
234a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
235a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic int *fptr = &randtbl[SEP_3 + 1];
236a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic int *rptr = &randtbl[1];
237a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
238a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
239a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * The following things are the pointer to the state information table, the
240a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * type of the current generator, the degree of the current polynomial being
241a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * used, and the separation between the two pointers.  Note that for efficiency
242a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * of random(), we remember the first location of the state information, not
243a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the zeroeth.  Hence it is valid to access state[-1], which is used to
244a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * store the type of the R.N.G.  Also, we remember the last location, since
245a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * this is more efficient than indexing every time to find the address of
246a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the last element to see if the front and rear pointers have wrapped.
247a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
248a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic int *state = &randtbl[1];
249a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic int rand_type = TYPE_3;
250a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic int rand_deg = DEG_3;
251a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic int rand_sep = SEP_3;
252a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic int *end_ptr = &randtbl[DEG_3 + 1];
253a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
254a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
255a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * srandom:
256a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
257a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Initialize the random number generator based on the given seed.  If the
258a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * type is the trivial no-state-information type, just remember the seed.
259a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Otherwise, initializes state[] based on the given "seed" via a linear
260a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * congruential generator.  Then, the pointers are set to known locations
261a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * that are exactly rand_sep places apart.  Lastly, it cycles the state
262a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * information a given number of times to get rid of any initial dependencies
263a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * introduced by the L.C.R.N.G.  Note that the initialization of randtbl[]
264a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * for default usage relies on values produced by this routine.
265a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
266a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic void
267a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughessrandom_unlocked(unsigned int x)
268a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes{
269a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	int i;
270a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
271a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	if (rand_type == TYPE_0)
272a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		state[0] = x;
273a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	else {
274a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		state[0] = x;
275a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		for (i = 1; i < rand_deg; i++) {
276a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#ifdef USE_BETTER_RANDOM
277a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			int x1, hi, lo, t;
278a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
279a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			/*
280a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			 * Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
281a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			 * From "Random number generators: good ones are hard
282a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			 * to find", Park and Miller, Communications of the ACM,
283a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			 * vol. 31, no. 10,
284a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			 * October 1988, p. 1195.
285a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			 */
286a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			x1 = state[i - 1];
287a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			hi = x1 / 127773;
288a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			lo = x1 % 127773;
289a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			t = 16807 * lo - 2836 * hi;
290a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			if (t <= 0)
291a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes				t += 0x7fffffff;
292a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			state[i] = t;
293a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#else
294a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			state[i] = 1103515245 * state[i - 1] + 12345;
295a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#endif /* USE_BETTER_RANDOM */
296a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		}
297a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		fptr = &state[rand_sep];
298a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rptr = &state[0];
299a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		for (i = 0; i < 10 * rand_deg; i++)
300a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			(void)random_unlocked();
301a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	}
302a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes}
303a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
304a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesvoid
305a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughessrandom(unsigned int x)
306a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes{
307a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
308a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	mutex_lock(&random_mutex);
309a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	srandom_unlocked(x);
310a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	mutex_unlock(&random_mutex);
311a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes}
312a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
313a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
314a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * initstate:
315a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
316a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Initialize the state information in the given array of n bytes for future
317a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * random number generation.  Based on the number of bytes we are given, and
318a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the break values for the different R.N.G.'s, we choose the best (largest)
319a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * one we can and set things up for it.  srandom() is then called to
320a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * initialize the state information.
321a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
322a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Note that on return from srandom(), we set state[-1] to be the type
323a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * multiplexed with the current value of the rear pointer; this is so
324a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * successive calls to initstate() won't lose this information and will be
325a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * able to restart with setstate().
326a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
327a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Note: the first thing we do is save the current state, if any, just like
328a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * setstate() so that it doesn't matter when initstate is called.
329a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
330a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Returns a pointer to the old state.
331a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
332a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Note: The Sparc platform requires that arg_state begin on an int
333a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * word boundary; otherwise a bus error will occur. Even so, lint will
334a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * complain about mis-alignment, but you should disregard these messages.
335a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
336a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hugheschar *
337a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesinitstate(
338a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	unsigned int seed,		/* seed for R.N.G. */
339a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	char *arg_state,		/* pointer to state array */
340a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	size_t n)			/* # bytes of state info */
341a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes{
342a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	void *ostate = (void *)(&state[-1]);
343a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	int *int_arg_state;
344a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
345a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	_DIAGASSERT(arg_state != NULL);
346a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
347a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	int_arg_state = (int *)(void *)arg_state;
348a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
349a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	mutex_lock(&random_mutex);
350a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	if (rand_type == TYPE_0)
351a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		state[-1] = rand_type;
352a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	else
353a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		state[-1] = MAX_TYPES * (int)(rptr - state) + rand_type;
354a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	if (n < BREAK_0) {
355a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		mutex_unlock(&random_mutex);
356a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		return (NULL);
357a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	} else if (n < BREAK_1) {
358a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_type = TYPE_0;
359a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_deg = DEG_0;
360a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_sep = SEP_0;
361a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	} else if (n < BREAK_2) {
362a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_type = TYPE_1;
363a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_deg = DEG_1;
364a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_sep = SEP_1;
365a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	} else if (n < BREAK_3) {
366a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_type = TYPE_2;
367a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_deg = DEG_2;
368a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_sep = SEP_2;
369a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	} else if (n < BREAK_4) {
370a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_type = TYPE_3;
371a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_deg = DEG_3;
372a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_sep = SEP_3;
373a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	} else {
374a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_type = TYPE_4;
375a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_deg = DEG_4;
376a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_sep = SEP_4;
377a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	}
378a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	state = (int *) (int_arg_state + 1); /* first location */
379a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	end_ptr = &state[rand_deg];	/* must set end_ptr before srandom */
380a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	srandom_unlocked(seed);
381a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	if (rand_type == TYPE_0)
382a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		int_arg_state[0] = rand_type;
383a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	else
384a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		int_arg_state[0] = MAX_TYPES * (int)(rptr - state) + rand_type;
385a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	mutex_unlock(&random_mutex);
386a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	return((char *)ostate);
387a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes}
388a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
389a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
390a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * setstate:
391a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
392a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Restore the state from the given state array.
393a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
394a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Note: it is important that we also remember the locations of the pointers
395a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * in the current state information, and restore the locations of the pointers
396a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * from the old state information.  This is done by multiplexing the pointer
397a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * location into the zeroeth word of the state information.
398a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
399a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Note that due to the order in which things are done, it is OK to call
400a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * setstate() with the same state as the current state.
401a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
402a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Returns a pointer to the old state information.
403a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
404a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Note: The Sparc platform requires that arg_state begin on a long
405a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * word boundary; otherwise a bus error will occur. Even so, lint will
406a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * complain about mis-alignment, but you should disregard these messages.
407a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
408a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hugheschar *
409a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughessetstate(char *arg_state)		/* pointer to state array */
410a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes{
411a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	int *new_state;
412a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	int type;
413a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	int rear;
414a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	void *ostate = (void *)(&state[-1]);
415a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
416a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	_DIAGASSERT(arg_state != NULL);
417a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
418a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	new_state = (int *)(void *)arg_state;
419a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	type = (int)(new_state[0] % MAX_TYPES);
420a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	rear = (int)(new_state[0] / MAX_TYPES);
421a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
422a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	mutex_lock(&random_mutex);
423a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	if (rand_type == TYPE_0)
424a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		state[-1] = rand_type;
425a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	else
426a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		state[-1] = MAX_TYPES * (int)(rptr - state) + rand_type;
427a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	switch(type) {
428a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	case TYPE_0:
429a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	case TYPE_1:
430a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	case TYPE_2:
431a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	case TYPE_3:
432a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	case TYPE_4:
433a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_type = type;
434a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_deg = degrees[type];
435a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rand_sep = seps[type];
436a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		break;
437a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	default:
438a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		mutex_unlock(&random_mutex);
439a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		return (NULL);
440a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	}
441a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	state = (int *) (new_state + 1);
442a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	if (rand_type != TYPE_0) {
443a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		rptr = &state[rear];
444a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		fptr = &state[(rear + rand_sep) % rand_deg];
445a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	}
446a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	end_ptr = &state[rand_deg];		/* set end_ptr too */
447a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	mutex_unlock(&random_mutex);
448a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	return((char *)ostate);
449a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes}
450a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
451a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes/*
452a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * random:
453a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
454a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * If we are using the trivial TYPE_0 R.N.G., just do the old linear
455a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * congruential bit.  Otherwise, we do our fancy trinomial stuff, which is
456a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the same in all the other cases due to all the global variables that have
457a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * been set up.  The basic operation is to add the number at the rear pointer
458a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * into the one at the front pointer.  Then both pointers are advanced to
459a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * the next location cyclically in the table.  The value returned is the sum
460a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * generated, reduced to 31 bits by throwing away the "least random" low bit.
461a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
462a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Note: the code takes advantage of the fact that both the front and
463a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * rear pointers can't wrap on the same call by not testing the rear
464a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * pointer if the front one has wrapped.
465a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes *
466a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes * Returns a 31-bit random number.
467a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes */
468a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesstatic long
469a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesrandom_unlocked(void)
470a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes{
471a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	int i;
472a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	int *f, *r;
473a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
474a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	if (rand_type == TYPE_0) {
475a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		i = state[0];
476a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		state[0] = i = (i * 1103515245 + 12345) & 0x7fffffff;
477a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	} else {
478a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		/*
479a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		 * Use local variables rather than static variables for speed.
480a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		 */
481a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		f = fptr; r = rptr;
482a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		*f += *r;
483a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		/* chucking least random bit */
484a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		i = ((unsigned int)*f >> 1) & 0x7fffffff;
485a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		if (++f >= end_ptr) {
486a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			f = state;
487a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			++r;
488a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		}
489a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		else if (++r >= end_ptr) {
490a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes			r = state;
491a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		}
492a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
493a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		fptr = f; rptr = r;
494a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	}
495a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	return(i);
496a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes}
497a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
498a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hugheslong
499a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesrandom(void)
500a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes{
501a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	long r;
502a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
503a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	mutex_lock(&random_mutex);
504a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	r = random_unlocked();
505a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	mutex_unlock(&random_mutex);
506a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	return (r);
507a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes}
508a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#else
509a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hugheslong
510a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughesrandom(void)
511a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes{
512a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	static u_long randseed = 1;
513a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	long x, hi, lo, t;
514a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes
515a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	/*
516a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	 * Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
517a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	 * From "Random number generators: good ones are hard to find",
518a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
519a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	 * October 1988, p. 1195.
520a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	 */
521a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	x = randseed;
522a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	hi = x / 127773;
523a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	lo = x % 127773;
524a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	t = 16807 * lo - 2836 * hi;
525a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	if (t <= 0)
526a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes		t += 0x7fffffff;
527a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	randseed = t;
528a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes	return (t);
529a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes}
530a0beeeabbc8735bc830544cbbb1d920122b8d958Elliott Hughes#endif /* SMALL_RANDOM */
531