1/* 2 * Copyright (c) 1983, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34/* This is a stripped-down version of random.c distributed with 35 FreeBSD 2.2 */ 36 37/* 38 * random.c: 39 * 40 * An improved random number generation package. In addition to the standard 41 * rand()/srand() like interface, this package also has a special state info 42 * interface. The initstate() routine is called with a seed, an array of 43 * bytes, and a count of how many bytes are being passed in; this array is 44 * then initialized to contain information for random number generation with 45 * that much state information. Good sizes for the amount of state 46 * information are 32, 64, 128, and 256 bytes. The state can be switched by 47 * calling the setstate() routine with the same array as was initiallized 48 * with initstate(). By default, the package runs with 128 bytes of state 49 * information and generates far better random numbers than a linear 50 * congruential generator. If the amount of state information is less than 51 * 32 bytes, a simple linear congruential R.N.G. is used. 52 * 53 * Internally, the state information is treated as an array of longs; the 54 * zeroeth element of the array is the type of R.N.G. being used (small 55 * integer); the remainder of the array is the state information for the 56 * R.N.G. Thus, 32 bytes of state information will give 7 longs worth of 57 * state information, which will allow a degree seven polynomial. (Note: 58 * the zeroeth word of state information also has some other information 59 * stored in it -- see setstate() for details). 60 * 61 * The random number generation technique is a linear feedback shift register 62 * approach, employing trinomials (since there are fewer terms to sum up that 63 * way). In this approach, the least significant bit of all the numbers in 64 * the state table will act as a linear feedback shift register, and will 65 * have period 2^deg - 1 (where deg is the degree of the polynomial being 66 * used, assuming that the polynomial is irreducible and primitive). The 67 * higher order bits will have longer periods, since their values are also 68 * influenced by pseudo-random carries out of the lower bits. The total 69 * period of the generator is approximately deg*(2**deg - 1); thus doubling 70 * the amount of state information has a vast influence on the period of the 71 * generator. Note: the deg*(2**deg - 1) is an approximation only good for 72 * large deg, when the period of the shift register is the dominant factor. 73 * With deg equal to seven, the period is actually much longer than the 74 * 7*(2**7 - 1) predicted by this formula. 75 */ 76 77/* 78 * For each of the currently supported random number generators, we have a 79 * break value on the amount of state information (you need at least this 80 * many bytes of state info to support this random number generator), a degree 81 * for the polynomial (actually a trinomial) that the R.N.G. is based on, and 82 * the separation between the two lower order coefficients of the trinomial. 83 */ 84/* x**31 + x**3 + 1 */ 85#define DEG MZ_RANDOM_STATE_DEG 86#define SEP 3 87 88/* 89 * fpos and rpos are two pointers into the state info, a front and a rear 90 * pointer. These two pointers are always SEP places aparts, as they 91 * cycle cyclically through the state information. (Yes, this does mean we 92 * could get away with just one pointer, but the code for random() is more 93 * efficient this way). The pointers are left positioned as they would be 94 * from the call 95 * 96 * initstate(1, randtbl, 128); 97 * 98 * (The position of the rear pointer, rptr, is really 0 (as explained above 99 * in the initialization of randtbl) because the state table pointer is set 100 * to point to randtbl[1] (as explained below). 101 */ 102#if 0 103/* In schpriv.h: */ 104typedef struct { 105 Scheme_Type type; 106 short fpos, rpos; 107 long state[DEG]; 108} Scheme_Random_State; 109#endif 110 111/* 112 * sch_rand: 113 * 114 * The basic operation is to add the number at the rear pointer 115 * into the one at the front pointer. Then both pointers are advanced to 116 * the next location cyclically in the table. The value returned is the sum 117 * generated, reduced to 31 bits by throwing away the "least random" low bit. 118 * 119 * Note: the code takes advantage of the fact that both the front and 120 * rear pointers can't wrap on the same call by not testing the rear 121 * pointer if the front one has wrapped. 122 * 123 * Returns a 31-bit random number. 124 */ 125long scheme_rand(unsigned long n, Scheme_Random_State *rs) 126{ 127 long i; 128 129 rs->state[rs->fpos] += rs->state[rs->rpos]; 130 i = (rs->state[rs->fpos] >> 1) & 0x7fffffff; /* chucking least random bit */ 131 if (++(rs->fpos) >= DEG) { 132 rs->fpos = 0; 133 rs->rpos++; 134 } else if (++(rs->rpos) >= DEG) 135 rs->rpos = 0; 136 137 return i % n; 138} 139 140/* 141 * sch_srand: 142 * 143 * Initialize the random number generator based on the given seed. If the 144 * type is the trivial no-state-information type, just remember the seed. 145 * Otherwise, initializes state[] based on the given "seed" via a linear 146 * congruential generator. Then, the pointers are set to known locations 147 * that are exactly SEP places apart. Lastly, it cycles the state 148 * information a given number of times to get rid of any initial dependencies 149 * introduced by the L.C.R.N.G. Note that the initialization of randtbl[] 150 * for default usage relies on values produced by this routine. 151 */ 152static void sch_srand(long x, Scheme_Random_State *rs, int reset) 153{ 154 register int i; 155 long *state = rs->state; 156 157 state[0] = x & 0x7fffffff; 158 for (i = 1; i < DEG; i++) { 159 /* 160 * Compute v = (7^5 * v) mod (2^31 - 1) 161 * wihout overflowing 31 bits: 162 * (2^31 - 1) = 127773 * (7^5) + 2836 163 * From "Random number generators: good ones are hard to find", 164 * Park and Miller, Communications of the ACM, vol. 31, no. 10, 165 * October 1988, p. 1195. 166 */ 167 register long hi, lo, v; 168 169 v = state[i - 1]; 170 hi = v / 127773; 171 lo = v % 127773; 172 v = 16807 * lo - 2836 * hi; 173 if (v <= 0) 174 v += 0x7fffffff; 175 state[i] = v; 176 } 177 rs->fpos = SEP; 178 rs->rpos = 0; 179 for (i = 0; i < 10 * DEG; i++) { 180 (void)scheme_rand(rs); 181} 182} 183 184Scheme_Object *scheme_make_random_state(long seed) 185{ 186 Scheme_Random_State *rs; 187 188 rs = MALLOC_ONE_TAGGED(Scheme_Random_State); 189 rs->so.type = scheme_random_state_type; 190 191 sch_srand(seed, rs); 192 193 return (Scheme_Object *)rs; 194} 195