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