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