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