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