author | Jon Tibble <meths@btinternet.com> |
Thu, 09 Dec 2010 22:32:39 +0100 | |
changeset 13255 | 4afa820d78b9 |
parent 6812 | febeba71273d |
permissions | -rw-r--r-- |
0 | 1 |
/* |
2 |
* CDDL HEADER START |
|
3 |
* |
|
4 |
* The contents of this file are subject to the terms of the |
|
6812 | 5 |
* Common Development and Distribution License (the "License"). |
6 |
* You may not use this file except in compliance with the License. |
|
0 | 7 |
* |
8 |
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE |
|
9 |
* or http://www.opensolaris.org/os/licensing. |
|
10 |
* See the License for the specific language governing permissions |
|
11 |
* and limitations under the License. |
|
12 |
* |
|
13 |
* When distributing Covered Code, include this CDDL HEADER in each |
|
14 |
* file and include the License file at usr/src/OPENSOLARIS.LICENSE. |
|
15 |
* If applicable, add the following below this CDDL HEADER, with the |
|
16 |
* fields enclosed by brackets "[]" replaced with your own identifying |
|
17 |
* information: Portions Copyright [yyyy] [name of copyright owner] |
|
18 |
* |
|
19 |
* CDDL HEADER END |
|
20 |
*/ |
|
1111
e2bd9f81a79d
6362144 gcc breaks libc by turning structure assignments into calls to memcpy()
raf
parents:
0
diff
changeset
|
21 |
|
0 | 22 |
/* |
6812 | 23 |
* Copyright 2008 Sun Microsystems, Inc. All rights reserved. |
0 | 24 |
* Use is subject to license terms. |
25 |
*/ |
|
26 |
||
27 |
/* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ |
|
28 |
/* All Rights Reserved */ |
|
29 |
||
30 |
/* |
|
31 |
* University Copyright- Copyright (c) 1982, 1986, 1988 |
|
32 |
* The Regents of the University of California |
|
33 |
* All Rights Reserved |
|
34 |
* |
|
35 |
* University Acknowledgment- Portions of this document are derived from |
|
36 |
* software developed by the University of California, Berkeley, and its |
|
37 |
* contributors. |
|
38 |
*/ |
|
39 |
||
40 |
#pragma ident "%Z%%M% %I% %E% SMI" |
|
41 |
||
6812 | 42 |
#include "lint.h" |
0 | 43 |
#include <stdio.h> |
44 |
#include <stdlib.h> |
|
1111
e2bd9f81a79d
6362144 gcc breaks libc by turning structure assignments into calls to memcpy()
raf
parents:
0
diff
changeset
|
45 |
#include <string.h> |
0 | 46 |
#include <sys/types.h> |
47 |
#include <limits.h> |
|
48 |
||
49 |
/* |
|
50 |
* random.c: |
|
51 |
* An improved random number generation package. In addition to the standard |
|
52 |
* rand()/srand() like interface, this package also has a special state info |
|
53 |
* interface. The initstate() routine is called with a seed, an array of |
|
54 |
* bytes, and a count of how many bytes are being passed in; this array is then |
|
55 |
* initialized to contain information for random number generation with that |
|
56 |
* much state information. Good sizes for the amount of state information are |
|
57 |
* 32, 64, 128, and 256 bytes. The state can be switched by calling the |
|
58 |
* setstate() routine with the same array as was initiallized with initstate(). |
|
59 |
* By default, the package runs with 128 bytes of state information and |
|
60 |
* generates far better random numbers than a linear congruential generator. |
|
61 |
* If the amount of state information is less than 32 bytes, a simple linear |
|
62 |
* congruential R.N.G. is used. |
|
63 |
* Internally, the state information is treated as an array of ints; the |
|
64 |
* zeroeth element of the array is the type of R.N.G. being used (small |
|
65 |
* integer); the remainder of the array is the state information for the |
|
66 |
* R.N.G. Thus, 32 bytes of state information will give 7 ints worth of |
|
67 |
* state information, which will allow a degree seven polynomial. (Note: the |
|
68 |
* zeroeth word of state information also has some other information stored |
|
69 |
* in it -- see setstate() for details). |
|
70 |
* The random number generation technique is a linear feedback shift register |
|
71 |
* approach, employing trinomials (since there are fewer terms to sum up that |
|
72 |
* way). In this approach, the least significant bit of all the numbers in |
|
73 |
* the state table will act as a linear feedback shift register, and will have |
|
74 |
* period 2^deg - 1 (where deg is the degree of the polynomial being used, |
|
75 |
* assuming that the polynomial is irreducible and primitive). The higher |
|
76 |
* order bits will have longer periods, since their values are also influenced |
|
77 |
* by pseudo-random carries out of the lower bits. The total period of the |
|
78 |
* generator is approximately deg*(2**deg - 1); thus doubling the amount of |
|
79 |
* state information has a vast influence on the period of the generator. |
|
80 |
* Note: the deg*(2**deg - 1) is an approximation only good for large deg, |
|
81 |
* when the period of the shift register is the dominant factor. With deg |
|
82 |
* equal to seven, the period is actually much longer than the 7*(2**7 - 1) |
|
83 |
* predicted by this formula. |
|
84 |
*/ |
|
85 |
||
86 |
||
87 |
||
88 |
/* |
|
89 |
* For each of the currently supported random number generators, we have a |
|
90 |
* break value on the amount of state information (you need at least this |
|
91 |
* many bytes of state info to support this random number generator), a degree |
|
92 |
* for the polynomial (actually a trinomial) that the R.N.G. is based on, and |
|
93 |
* the separation between the two lower order coefficients of the trinomial. |
|
94 |
*/ |
|
95 |
||
96 |
#define TYPE_0 0 /* linear congruential */ |
|
97 |
#define BREAK_0 8 |
|
98 |
#define DEG_0 0 |
|
99 |
#define SEP_0 0 |
|
100 |
||
101 |
#define TYPE_1 1 /* x**7 + x**3 + 1 */ |
|
102 |
#define BREAK_1 32 |
|
103 |
#define DEG_1 7 |
|
104 |
#define SEP_1 3 |
|
105 |
||
106 |
#define TYPE_2 2 /* x**15 + x + 1 */ |
|
107 |
#define BREAK_2 64 |
|
108 |
#define DEG_2 15 |
|
109 |
#define SEP_2 1 |
|
110 |
||
111 |
#define TYPE_3 3 /* x**31 + x**3 + 1 */ |
|
112 |
#define BREAK_3 128 |
|
113 |
#define DEG_3 31 |
|
114 |
#define SEP_3 3 |
|
115 |
||
116 |
#define TYPE_4 4 /* x**63 + x + 1 */ |
|
117 |
#define BREAK_4 256 |
|
118 |
#define DEG_4 63 |
|
119 |
#define SEP_4 1 |
|
120 |
||
121 |
||
122 |
/* |
|
123 |
* Array versions of the above information to make code run faster -- relies |
|
124 |
* on fact that TYPE_i == i. |
|
125 |
*/ |
|
126 |
||
127 |
#define MAX_TYPES 5 /* max number of types above */ |
|
128 |
||
129 |
static struct _randomjunk { |
|
130 |
unsigned int degrees[MAX_TYPES]; |
|
131 |
unsigned int seps[MAX_TYPES]; |
|
132 |
unsigned int randtbl[ DEG_3 + 1 ]; |
|
133 |
/* |
|
134 |
* fptr and rptr are two pointers into the state info, a front and a rear |
|
135 |
* pointer. These two pointers are always rand_sep places aparts, as they cycle |
|
136 |
* cyclically through the state information. (Yes, this does mean we could get |
|
137 |
* away with just one pointer, but the code for random() is more efficient this |
|
138 |
* way). The pointers are left positioned as they would be from the call |
|
139 |
* initstate( 1, randtbl, 128 ) |
|
140 |
* (The position of the rear pointer, rptr, is really 0 (as explained above |
|
141 |
* in the initialization of randtbl) because the state table pointer is set |
|
142 |
* to point to randtbl[1] (as explained below). |
|
143 |
*/ |
|
144 |
unsigned int *fptr, *rptr; |
|
145 |
/* |
|
146 |
* The following things are the pointer to the state information table, |
|
147 |
* the type of the current generator, the degree of the current polynomial |
|
148 |
* being used, and the separation between the two pointers. |
|
149 |
* Note that for efficiency of random(), we remember the first location of |
|
150 |
* the state information, not the zeroeth. Hence it is valid to access |
|
151 |
* state[-1], which is used to store the type of the R.N.G. |
|
152 |
* Also, we remember the last location, since this is more efficient than |
|
153 |
* indexing every time to find the address of the last element to see if |
|
154 |
* the front and rear pointers have wrapped. |
|
155 |
*/ |
|
156 |
unsigned int *state; |
|
157 |
unsigned int rand_type, rand_deg, rand_sep; |
|
158 |
unsigned int *end_ptr; |
|
159 |
} *__randomjunk, *_randomjunk(void), _randominit = { |
|
160 |
/* |
|
161 |
* Initially, everything is set up as if from : |
|
162 |
* initstate( 1, &randtbl, 128 ); |
|
163 |
* Note that this initialization takes advantage of the fact |
|
164 |
* that srandom() advances the front and rear pointers 10*rand_deg |
|
165 |
* times, and hence the rear pointer which starts at 0 will also |
|
166 |
* end up at zero; thus the zeroeth element of the state |
|
167 |
* information, which contains info about the current |
|
168 |
* position of the rear pointer is just |
|
169 |
* MAX_TYPES*(rptr - state) + TYPE_3 == TYPE_3. |
|
170 |
*/ |
|
171 |
{ DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }, |
|
172 |
{ SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }, |
|
173 |
{ TYPE_3, |
|
174 |
0x9a319039U, 0x32d9c024U, 0x9b663182U, 0x5da1f342U, |
|
175 |
0xde3b81e0U, 0xdf0a6fb5U, 0xf103bc02U, 0x48f340fbU, |
|
176 |
0x7449e56bU, 0xbeb1dbb0U, 0xab5c5918U, 0x946554fdU, |
|
177 |
0x8c2e680fU, 0xeb3d799fU, 0xb11ee0b7U, 0x2d436b86U, |
|
178 |
0xda672e2aU, 0x1588ca88U, 0xe369735dU, 0x904f35f7U, |
|
179 |
0xd7158fd6U, 0x6fa6f051U, 0x616e6b96U, 0xac94efdcU, |
|
180 |
0x36413f93U, 0xc622c298U, 0xf5a42ab8U, 0x8a88d77bU, |
|
181 |
0xf5ad9d0eU, 0x8999220bU, 0x27fb47b9U }, |
|
182 |
&_randominit.randtbl[ SEP_3 + 1 ], |
|
183 |
&_randominit.randtbl[ 1 ], |
|
184 |
&_randominit.randtbl[ 1 ], |
|
185 |
TYPE_3, DEG_3, SEP_3, |
|
186 |
&_randominit.randtbl[ DEG_3 + 1] |
|
187 |
}; |
|
188 |
||
189 |
static struct _randomjunk * |
|
190 |
_randomjunk(void) |
|
191 |
{ |
|
192 |
struct _randomjunk *rp = __randomjunk; |
|
193 |
||
194 |
if (rp == NULL) { |
|
195 |
rp = (struct _randomjunk *)malloc(sizeof (*rp)); |
|
196 |
if (rp == NULL) |
|
197 |
return (NULL); |
|
1111
e2bd9f81a79d
6362144 gcc breaks libc by turning structure assignments into calls to memcpy()
raf
parents:
0
diff
changeset
|
198 |
(void) memcpy(rp, &_randominit, sizeof (*rp)); |
0 | 199 |
__randomjunk = rp; |
200 |
} |
|
201 |
return (rp); |
|
202 |
} |
|
203 |
||
204 |
||
205 |
/* |
|
206 |
* initstate: |
|
207 |
* Initialize the state information in the given array of n bytes for |
|
208 |
* future random number generation. Based on the number of bytes we |
|
209 |
* are given, and the break values for the different R.N.G.'s, we choose |
|
210 |
* the best (largest) one we can and set things up for it. srandom() is |
|
211 |
* then called to initialize the state information. |
|
212 |
* Note that on return from srandom(), we set state[-1] to be the type |
|
213 |
* multiplexed with the current value of the rear pointer; this is so |
|
214 |
* successive calls to initstate() won't lose this information and will |
|
215 |
* be able to restart with setstate(). |
|
216 |
* Note: the first thing we do is save the current state, if any, just like |
|
217 |
* setstate() so that it doesn't matter when initstate is called. |
|
218 |
* Returns a pointer to the old state. |
|
219 |
*/ |
|
220 |
||
221 |
char * |
|
222 |
initstate( |
|
223 |
unsigned int seed, /* seed for R. N. G. */ |
|
224 |
char *arg_state, /* pointer to state array */ |
|
225 |
size_t size) /* # bytes of state info */ |
|
226 |
{ |
|
227 |
unsigned int n; |
|
228 |
struct _randomjunk *rp = _randomjunk(); |
|
229 |
char *ostate; |
|
230 |
||
231 |
if (size > UINT_MAX) |
|
232 |
n = UINT_MAX; |
|
233 |
else |
|
234 |
n = (unsigned int)size; |
|
235 |
||
236 |
if (rp == NULL) |
|
237 |
return (NULL); |
|
238 |
ostate = (char *)(&rp->state[ -1 ]); |
|
239 |
||
240 |
if (rp->rand_type == TYPE_0) rp->state[ -1 ] = rp->rand_type; |
|
241 |
else rp->state[ -1 ] = |
|
242 |
(unsigned int)(MAX_TYPES*(rp->rptr - rp->state) + rp->rand_type); |
|
243 |
if (n < BREAK_1) { |
|
244 |
if (n < BREAK_0) { |
|
245 |
return (NULL); |
|
246 |
} |
|
247 |
rp->rand_type = TYPE_0; |
|
248 |
rp->rand_deg = DEG_0; |
|
249 |
rp->rand_sep = SEP_0; |
|
250 |
} else { |
|
251 |
if (n < BREAK_2) { |
|
252 |
rp->rand_type = TYPE_1; |
|
253 |
rp->rand_deg = DEG_1; |
|
254 |
rp->rand_sep = SEP_1; |
|
255 |
} else { |
|
256 |
if (n < BREAK_3) { |
|
257 |
rp->rand_type = TYPE_2; |
|
258 |
rp->rand_deg = DEG_2; |
|
259 |
rp->rand_sep = SEP_2; |
|
260 |
} else { |
|
261 |
if (n < BREAK_4) { |
|
262 |
rp->rand_type = TYPE_3; |
|
263 |
rp->rand_deg = DEG_3; |
|
264 |
rp->rand_sep = SEP_3; |
|
265 |
} else { |
|
266 |
rp->rand_type = TYPE_4; |
|
267 |
rp->rand_deg = DEG_4; |
|
268 |
rp->rand_sep = SEP_4; |
|
269 |
} |
|
270 |
} |
|
271 |
} |
|
272 |
} |
|
273 |
/* first location */ |
|
274 |
rp->state = &(((unsigned int *)(uintptr_t)arg_state)[1]); |
|
275 |
/* must set end_ptr before srandom */ |
|
276 |
rp->end_ptr = &rp->state[rp->rand_deg]; |
|
277 |
srandom(seed); |
|
278 |
if (rp->rand_type == TYPE_0) rp->state[ -1 ] = rp->rand_type; |
|
279 |
else |
|
280 |
rp->state[-1] = (unsigned int)(MAX_TYPES* |
|
281 |
(rp->rptr - rp->state) + rp->rand_type); |
|
282 |
return (ostate); |
|
283 |
} |
|
284 |
||
285 |
||
286 |
||
287 |
/* |
|
288 |
* setstate: |
|
289 |
* Restore the state from the given state array. |
|
290 |
* Note: it is important that we also remember the locations of the pointers |
|
291 |
* in the current state information, and restore the locations of the pointers |
|
292 |
* from the old state information. This is done by multiplexing the pointer |
|
293 |
* location into the zeroeth word of the state information. |
|
294 |
* Note that due to the order in which things are done, it is OK to call |
|
295 |
* setstate() with the same state as the current state. |
|
296 |
* Returns a pointer to the old state information. |
|
297 |
*/ |
|
298 |
||
299 |
char * |
|
300 |
setstate(const char *arg_state) |
|
301 |
{ |
|
302 |
struct _randomjunk *rp = _randomjunk(); |
|
303 |
unsigned int *new_state; |
|
304 |
unsigned int type; |
|
305 |
unsigned int rear; |
|
306 |
char *ostate; |
|
307 |
||
308 |
if (rp == NULL) |
|
309 |
return (NULL); |
|
310 |
new_state = (unsigned int *)(uintptr_t)arg_state; |
|
311 |
type = new_state[0]%MAX_TYPES; |
|
312 |
rear = new_state[0]/MAX_TYPES; |
|
313 |
ostate = (char *)(&rp->state[ -1 ]); |
|
314 |
||
315 |
if (rp->rand_type == TYPE_0) rp->state[ -1 ] = rp->rand_type; |
|
316 |
else |
|
317 |
rp->state[-1] = (unsigned int)(MAX_TYPES* |
|
318 |
(rp->rptr - rp->state) + rp->rand_type); |
|
319 |
switch (type) { |
|
320 |
case TYPE_0: |
|
321 |
case TYPE_1: |
|
322 |
case TYPE_2: |
|
323 |
case TYPE_3: |
|
324 |
case TYPE_4: |
|
325 |
rp->rand_type = type; |
|
326 |
rp->rand_deg = rp->degrees[ type ]; |
|
327 |
rp->rand_sep = rp->seps[ type ]; |
|
328 |
break; |
|
329 |
||
330 |
default: |
|
331 |
return (NULL); |
|
332 |
} |
|
333 |
rp->state = &new_state[ 1 ]; |
|
334 |
if (rp->rand_type != TYPE_0) { |
|
335 |
rp->rptr = &rp->state[ rear ]; |
|
336 |
rp->fptr = &rp->state[ (rear + rp->rand_sep)%rp->rand_deg ]; |
|
337 |
} |
|
338 |
rp->end_ptr = &rp->state[ rp->rand_deg ]; /* set end_ptr too */ |
|
339 |
return (ostate); |
|
340 |
} |
|
341 |
||
342 |
||
343 |
||
344 |
/* |
|
345 |
* random: |
|
346 |
* If we are using the trivial TYPE_0 R.N.G., just do the old linear |
|
347 |
* congruential bit. Otherwise, we do our fancy trinomial stuff, which is the |
|
348 |
* same in all ther other cases due to all the global variables that have been |
|
349 |
* set up. The basic operation is to add the number at the rear pointer into |
|
350 |
* the one at the front pointer. Then both pointers are advanced to the next |
|
351 |
* location cyclically in the table. The value returned is the sum generated, |
|
352 |
* reduced to 31 bits by throwing away the "least random" low bit. |
|
353 |
* Note: the code takes advantage of the fact that both the front and |
|
354 |
* rear pointers can't wrap on the same call by not testing the rear |
|
355 |
* pointer if the front one has wrapped. |
|
356 |
* Returns a 31-bit random number. |
|
357 |
*/ |
|
358 |
||
359 |
long |
|
360 |
random(void) |
|
361 |
{ |
|
362 |
struct _randomjunk *rp = _randomjunk(); |
|
363 |
unsigned int i; |
|
364 |
||
365 |
if (rp == NULL) |
|
366 |
return (0L); |
|
367 |
if (rp->rand_type == TYPE_0) { |
|
368 |
i = rp->state[0] = (rp->state[0]*1103515245 + 12345)&0x7fffffff; |
|
369 |
} else { |
|
370 |
*rp->fptr += *rp->rptr; |
|
371 |
i = (*rp->fptr >> 1)&0x7fffffff; /* chucking least random bit */ |
|
372 |
if (++rp->fptr >= rp->end_ptr) { |
|
373 |
rp->fptr = rp->state; |
|
374 |
++rp->rptr; |
|
375 |
} else { |
|
376 |
if (++rp->rptr >= rp->end_ptr) rp->rptr = rp->state; |
|
377 |
} |
|
378 |
} |
|
379 |
return ((long)i); |
|
380 |
} |
|
381 |
||
382 |
/* |
|
383 |
* srandom: |
|
384 |
* Initialize the random number generator based on the given seed. If the |
|
385 |
* type is the trivial no-state-information type, just remember the seed. |
|
386 |
* Otherwise, initializes state[] based on the given "seed" via a linear |
|
387 |
* congruential generator. Then, the pointers are set to known locations |
|
388 |
* that are exactly rand_sep places apart. Lastly, it cycles the state |
|
389 |
* information a given number of times to get rid of any initial dependencies |
|
390 |
* introduced by the L.C.R.N.G. |
|
391 |
* Note that the initialization of randtbl[] for default usage relies on |
|
392 |
* values produced by this routine. |
|
393 |
*/ |
|
394 |
||
395 |
void |
|
396 |
srandom(unsigned int x) |
|
397 |
{ |
|
398 |
struct _randomjunk *rp = _randomjunk(); |
|
399 |
unsigned int i; |
|
400 |
||
401 |
if (rp == NULL) |
|
402 |
return; |
|
403 |
if (rp->rand_type == TYPE_0) { |
|
404 |
rp->state[ 0 ] = x; |
|
405 |
} else { |
|
406 |
rp->state[ 0 ] = x; |
|
407 |
for (i = 1; i < rp->rand_deg; i++) { |
|
408 |
rp->state[i] = 1103515245*rp->state[i - 1] + 12345; |
|
409 |
} |
|
410 |
rp->fptr = &rp->state[ rp->rand_sep ]; |
|
411 |
rp->rptr = &rp->state[ 0 ]; |
|
412 |
for (i = 0; i < 10*rp->rand_deg; i++) (void)random(); |
|
413 |
} |
|
414 |
} |