Commit | Line | Data |
---|---|---|
6e5c1d39 KB |
1 | /* |
2 | * Copyright (c) 1986 Regents of the University of California. | |
3 | * All rights reserved. The Berkeley software License Agreement | |
4 | * specifies the terms and conditions for redistribution. | |
5 | */ | |
6 | ||
7 | #ifndef lint | |
8 | static char sccsid[] = "@(#)rnd.c 5.1 (Berkeley) %G%"; | |
9 | #endif not lint | |
10 | ||
11 | /* | |
12 | * code for when the good (berkeley) random number generator is around | |
13 | */ | |
14 | ||
15 | rnd(num) | |
16 | { | |
17 | return (random() % num); | |
18 | } | |
19 | ||
20 | srnd(num) | |
21 | { | |
22 | srandom(num); | |
23 | } | |
24 | ||
25 | #ifdef NO_RANDOM | |
26 | ||
27 | #ifndef lint | |
28 | static char sccsid[] = "@(#)random.c 4.2 (Berkeley) 83/01/02"; | |
29 | #endif | |
30 | ||
31 | #include <stdio.h> | |
32 | ||
33 | /* | |
34 | * random.c: | |
35 | * An improved random number generation package. In addition to the standard | |
36 | * rand()/srand() like interface, this package also has a special state info | |
37 | * interface. The initstate() routine is called with a seed, an array of | |
38 | * bytes, and a count of how many bytes are being passed in; this array is then | |
39 | * initialized to contain information for random number generation with that | |
40 | * much state information. Good sizes for the amount of state information are | |
41 | * 32, 64, 128, and 256 bytes. The state can be switched by calling the | |
42 | * setstate() routine with the same array as was initiallized with initstate(). | |
43 | * By default, the package runs with 128 bytes of state information and | |
44 | * generates far better random numbers than a linear congruential generator. | |
45 | * If the amount of state information is less than 32 bytes, a simple linear | |
46 | * congruential R.N.G. is used. | |
47 | * Internally, the state information is treated as an array of longs; the | |
48 | * zeroeth element of the array is the type of R.N.G. being used (small | |
49 | * integer); the remainder of the array is the state information for the | |
50 | * R.N.G. Thus, 32 bytes of state information will give 7 longs worth of | |
51 | * state information, which will allow a degree seven polynomial. (Note: the | |
52 | * zeroeth word of state information also has some other information stored | |
53 | * in it -- see setstate() for details). | |
54 | * The random number generation technique is a linear feedback shift register | |
55 | * approach, employing trinomials (since there are fewer terms to sum up that | |
56 | * way). In this approach, the least significant bit of all the numbers in | |
57 | * the state table will act as a linear feedback shift register, and will have | |
58 | * period 2^deg - 1 (where deg is the degree of the polynomial being used, | |
59 | * assuming that the polynomial is irreducible and primitive). The higher | |
60 | * order bits will have longer periods, since their values are also influenced | |
61 | * by pseudo-random carries out of the lower bits. The total period of the | |
62 | * generator is approximately deg*(2**deg - 1); thus doubling the amount of | |
63 | * state information has a vast influence on the period of the generator. | |
64 | * Note: the deg*(2**deg - 1) is an approximation only good for large deg, | |
65 | * when the period of the shift register is the dominant factor. With deg | |
66 | * equal to seven, the period is actually much longer than the 7*(2**7 - 1) | |
67 | * predicted by this formula. | |
68 | */ | |
69 | ||
70 | ||
71 | ||
72 | /* | |
73 | * For each of the currently supported random number generators, we have a | |
74 | * break value on the amount of state information (you need at least this | |
75 | * many bytes of state info to support this random number generator), a degree | |
76 | * for the polynomial (actually a trinomial) that the R.N.G. is based on, and | |
77 | * the separation between the two lower order coefficients of the trinomial. | |
78 | */ | |
79 | ||
80 | #define TYPE_0 0 /* linear congruential */ | |
81 | #define BREAK_0 8 | |
82 | #define DEG_0 0 | |
83 | #define SEP_0 0 | |
84 | ||
85 | #define TYPE_1 1 /* x**7 + x**3 + 1 */ | |
86 | #define BREAK_1 32 | |
87 | #define DEG_1 7 | |
88 | #define SEP_1 3 | |
89 | ||
90 | #define TYPE_2 2 /* x**15 + x + 1 */ | |
91 | #define BREAK_2 64 | |
92 | #define DEG_2 15 | |
93 | #define SEP_2 1 | |
94 | ||
95 | #define TYPE_3 3 /* x**31 + x**3 + 1 */ | |
96 | #define BREAK_3 128 | |
97 | #define DEG_3 31 | |
98 | #define SEP_3 3 | |
99 | ||
100 | #define TYPE_4 4 /* x**63 + x + 1 */ | |
101 | #define BREAK_4 256 | |
102 | #define DEG_4 63 | |
103 | #define SEP_4 1 | |
104 | ||
105 | ||
106 | /* | |
107 | * Array versions of the above information to make code run faster -- relies | |
108 | * on fact that TYPE_i == i. | |
109 | */ | |
110 | ||
111 | #define MAX_TYPES 5 /* max number of types above */ | |
112 | ||
113 | static int degrees[ MAX_TYPES ] = { DEG_0, DEG_1, DEG_2, | |
114 | DEG_3, DEG_4 }; | |
115 | ||
116 | static int seps[ MAX_TYPES ] = { SEP_0, SEP_1, SEP_2, | |
117 | SEP_3, SEP_4 }; | |
118 | ||
119 | ||
120 | ||
121 | /* | |
122 | * Initially, everything is set up as if from : | |
123 | * initstate( 1, &randtbl, 128 ); | |
124 | * Note that this initialization takes advantage of the fact that srandom() | |
125 | * advances the front and rear pointers 10*rand_deg times, and hence the | |
126 | * rear pointer which starts at 0 will also end up at zero; thus the zeroeth | |
127 | * element of the state information, which contains info about the current | |
128 | * position of the rear pointer is just | |
129 | * MAX_TYPES*(rptr - state) + TYPE_3 == TYPE_3. | |
130 | */ | |
131 | ||
132 | static long randtbl[ DEG_3 + 1 ] = { TYPE_3, | |
133 | 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, | |
134 | 0xde3b81e0, 0xdf0a6fb5, 0xf103bc02, 0x48f340fb, | |
135 | 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd, | |
136 | 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, | |
137 | 0xda672e2a, 0x1588ca88, 0xe369735d, 0x904f35f7, | |
138 | 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc, | |
139 | 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, | |
140 | 0xf5ad9d0e, 0x8999220b, 0x27fb47b9 }; | |
141 | ||
142 | /* | |
143 | * fptr and rptr are two pointers into the state info, a front and a rear | |
144 | * pointer. These two pointers are always rand_sep places aparts, as they cycle | |
145 | * cyclically through the state information. (Yes, this does mean we could get | |
146 | * away with just one pointer, but the code for random() is more efficient this | |
147 | * way). The pointers are left positioned as they would be from the call | |
148 | * initstate( 1, randtbl, 128 ) | |
149 | * (The position of the rear pointer, rptr, is really 0 (as explained above | |
150 | * in the initialization of randtbl) because the state table pointer is set | |
151 | * to point to randtbl[1] (as explained below). | |
152 | */ | |
153 | ||
154 | static long *fptr = &randtbl[ SEP_3 + 1 ]; | |
155 | static long *rptr = &randtbl[ 1 ]; | |
156 | ||
157 | ||
158 | ||
159 | /* | |
160 | * The following things are the pointer to the state information table, | |
161 | * the type of the current generator, the degree of the current polynomial | |
162 | * being used, and the separation between the two pointers. | |
163 | * Note that for efficiency of random(), we remember the first location of | |
164 | * the state information, not the zeroeth. Hence it is valid to access | |
165 | * state[-1], which is used to store the type of the R.N.G. | |
166 | * Also, we remember the last location, since this is more efficient than | |
167 | * indexing every time to find the address of the last element to see if | |
168 | * the front and rear pointers have wrapped. | |
169 | */ | |
170 | ||
171 | static long *state = &randtbl[ 1 ]; | |
172 | ||
173 | static int rand_type = TYPE_3; | |
174 | static int rand_deg = DEG_3; | |
175 | static int rand_sep = SEP_3; | |
176 | ||
177 | static long *end_ptr = &randtbl[ DEG_3 + 1 ]; | |
178 | ||
179 | ||
180 | ||
181 | /* | |
182 | * srandom: | |
183 | * Initialize the random number generator based on the given seed. If the | |
184 | * type is the trivial no-state-information type, just remember the seed. | |
185 | * Otherwise, initializes state[] based on the given "seed" via a linear | |
186 | * congruential generator. Then, the pointers are set to known locations | |
187 | * that are exactly rand_sep places apart. Lastly, it cycles the state | |
188 | * information a given number of times to get rid of any initial dependencies | |
189 | * introduced by the L.C.R.N.G. | |
190 | * Note that the initialization of randtbl[] for default usage relies on | |
191 | * values produced by this routine. | |
192 | */ | |
193 | ||
194 | srandom( x ) | |
195 | ||
196 | unsigned x; | |
197 | { | |
198 | register int i, j; | |
199 | ||
200 | if( rand_type == TYPE_0 ) { | |
201 | state[ 0 ] = x; | |
202 | } | |
203 | else { | |
204 | j = 1; | |
205 | state[ 0 ] = x; | |
206 | for( i = 1; i < rand_deg; i++ ) { | |
207 | state[i] = 1103515245*state[i - 1] + 12345; | |
208 | } | |
209 | fptr = &state[ rand_sep ]; | |
210 | rptr = &state[ 0 ]; | |
211 | for( i = 0; i < 10*rand_deg; i++ ) random(); | |
212 | } | |
213 | } | |
214 | ||
215 | ||
216 | ||
217 | /* | |
218 | * initstate: | |
219 | * Initialize the state information in the given array of n bytes for | |
220 | * future random number generation. Based on the number of bytes we | |
221 | * are given, and the break values for the different R.N.G.'s, we choose | |
222 | * the best (largest) one we can and set things up for it. srandom() is | |
223 | * then called to initialize the state information. | |
224 | * Note that on return from srandom(), we set state[-1] to be the type | |
225 | * multiplexed with the current value of the rear pointer; this is so | |
226 | * successive calls to initstate() won't lose this information and will | |
227 | * be able to restart with setstate(). | |
228 | * Note: the first thing we do is save the current state, if any, just like | |
229 | * setstate() so that it doesn't matter when initstate is called. | |
230 | * Returns a pointer to the old state. | |
231 | */ | |
232 | ||
233 | char * | |
234 | initstate( seed, arg_state, n ) | |
235 | ||
236 | unsigned seed; /* seed for R. N. G. */ | |
237 | char *arg_state; /* pointer to state array */ | |
238 | int n; /* # bytes of state info */ | |
239 | { | |
240 | register char *ostate = (char *)( &state[ -1 ] ); | |
241 | ||
242 | if( rand_type == TYPE_0 ) state[ -1 ] = rand_type; | |
243 | else state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type; | |
244 | if( n < BREAK_1 ) { | |
245 | if( n < BREAK_0 ) { | |
246 | fprintf( stderr, "initstate: not enough state (%d bytes) with which to do jack; ignored.\n" ); | |
247 | return; | |
248 | } | |
249 | rand_type = TYPE_0; | |
250 | rand_deg = DEG_0; | |
251 | rand_sep = SEP_0; | |
252 | } | |
253 | else { | |
254 | if( n < BREAK_2 ) { | |
255 | rand_type = TYPE_1; | |
256 | rand_deg = DEG_1; | |
257 | rand_sep = SEP_1; | |
258 | } | |
259 | else { | |
260 | if( n < BREAK_3 ) { | |
261 | rand_type = TYPE_2; | |
262 | rand_deg = DEG_2; | |
263 | rand_sep = SEP_2; | |
264 | } | |
265 | else { | |
266 | if( n < BREAK_4 ) { | |
267 | rand_type = TYPE_3; | |
268 | rand_deg = DEG_3; | |
269 | rand_sep = SEP_3; | |
270 | } | |
271 | else { | |
272 | rand_type = TYPE_4; | |
273 | rand_deg = DEG_4; | |
274 | rand_sep = SEP_4; | |
275 | } | |
276 | } | |
277 | } | |
278 | } | |
279 | state = &( ( (long *)arg_state )[1] ); /* first location */ | |
280 | end_ptr = &state[ rand_deg ]; /* must set end_ptr before srandom */ | |
281 | srandom( seed ); | |
282 | if( rand_type == TYPE_0 ) state[ -1 ] = rand_type; | |
283 | else state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type; | |
284 | return( ostate ); | |
285 | } | |
286 | ||
287 | ||
288 | ||
289 | /* | |
290 | * setstate: | |
291 | * Restore the state from the given state array. | |
292 | * Note: it is important that we also remember the locations of the pointers | |
293 | * in the current state information, and restore the locations of the pointers | |
294 | * from the old state information. This is done by multiplexing the pointer | |
295 | * location into the zeroeth word of the state information. | |
296 | * Note that due to the order in which things are done, it is OK to call | |
297 | * setstate() with the same state as the current state. | |
298 | * Returns a pointer to the old state information. | |
299 | */ | |
300 | ||
301 | char * | |
302 | setstate( arg_state ) | |
303 | ||
304 | char *arg_state; | |
305 | { | |
306 | register long *new_state = (long *)arg_state; | |
307 | register int type = new_state[0]%MAX_TYPES; | |
308 | register int rear = new_state[0]/MAX_TYPES; | |
309 | char *ostate = (char *)( &state[ -1 ] ); | |
310 | ||
311 | if( rand_type == TYPE_0 ) state[ -1 ] = rand_type; | |
312 | else state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type; | |
313 | switch( type ) { | |
314 | case TYPE_0: | |
315 | case TYPE_1: | |
316 | case TYPE_2: | |
317 | case TYPE_3: | |
318 | case TYPE_4: | |
319 | rand_type = type; | |
320 | rand_deg = degrees[ type ]; | |
321 | rand_sep = seps[ type ]; | |
322 | break; | |
323 | ||
324 | default: | |
325 | fprintf( stderr, "setstate: state info has been munged; not changed.\n" ); | |
326 | } | |
327 | state = &new_state[ 1 ]; | |
328 | if( rand_type != TYPE_0 ) { | |
329 | rptr = &state[ rear ]; | |
330 | fptr = &state[ (rear + rand_sep)%rand_deg ]; | |
331 | } | |
332 | end_ptr = &state[ rand_deg ]; /* set end_ptr too */ | |
333 | return( ostate ); | |
334 | } | |
335 | ||
336 | ||
337 | ||
338 | /* | |
339 | * random: | |
340 | * If we are using the trivial TYPE_0 R.N.G., just do the old linear | |
341 | * congruential bit. Otherwise, we do our fancy trinomial stuff, which is the | |
342 | * same in all ther other cases due to all the global variables that have been | |
343 | * set up. The basic operation is to add the number at the rear pointer into | |
344 | * the one at the front pointer. Then both pointers are advanced to the next | |
345 | * location cyclically in the table. The value returned is the sum generated, | |
346 | * reduced to 31 bits by throwing away the "least random" low bit. | |
347 | * Note: the code takes advantage of the fact that both the front and | |
348 | * rear pointers can't wrap on the same call by not testing the rear | |
349 | * pointer if the front one has wrapped. | |
350 | * Returns a 31-bit random number. | |
351 | */ | |
352 | ||
353 | long | |
354 | random() | |
355 | { | |
356 | long i; | |
357 | ||
358 | if( rand_type == TYPE_0 ) { | |
359 | i = state[0] = ( state[0]*1103515245 + 12345 )&0x7fffffff; | |
360 | } | |
361 | else { | |
362 | *fptr += *rptr; | |
363 | i = (*fptr >> 1)&0x7fffffff; /* chucking least random bit */ | |
364 | if( ++fptr >= end_ptr ) { | |
365 | fptr = state; | |
366 | ++rptr; | |
367 | } | |
368 | else { | |
369 | if( ++rptr >= end_ptr ) rptr = state; | |
370 | } | |
371 | } | |
372 | return( i ); | |
373 | } | |
374 | ||
375 | #endif NO_RANDOM |