]>
Commit | Line | Data |
---|---|---|
fcc3501c | 1 | /* |
b168057a | 2 | Copyright (C) 1995-2015 Free Software Foundation, Inc. |
aeb25823 AJ |
3 | |
4 | The GNU C Library is free software; you can redistribute it and/or | |
5 | modify it under the terms of the GNU Lesser General Public | |
6 | License as published by the Free Software Foundation; either | |
7 | version 2.1 of the License, or (at your option) any later version. | |
8 | ||
9 | The GNU C Library is distributed in the hope that it will be useful, | |
10 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
12 | Lesser General Public License for more details. | |
13 | ||
14 | You should have received a copy of the GNU Lesser General Public | |
59ba27a6 PE |
15 | License along with the GNU C Library; if not, see |
16 | <http://www.gnu.org/licenses/>. */ | |
aeb25823 | 17 | |
60478656 | 18 | /* |
aeb25823 AJ |
19 | Copyright (C) 1983 Regents of the University of California. |
20 | All rights reserved. | |
21 | ||
22 | Redistribution and use in source and binary forms, with or without | |
23 | modification, are permitted provided that the following conditions | |
24 | are met: | |
25 | ||
26 | 1. Redistributions of source code must retain the above copyright | |
27 | notice, this list of conditions and the following disclaimer. | |
28 | 2. Redistributions in binary form must reproduce the above copyright | |
29 | notice, this list of conditions and the following disclaimer in the | |
30 | documentation and/or other materials provided with the distribution. | |
31 | 4. Neither the name of the University nor the names of its contributors | |
32 | may be used to endorse or promote products derived from this software | |
33 | without specific prior written permission. | |
fcc3501c | 34 | |
aeb25823 AJ |
35 | THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
36 | ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
37 | IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
38 | ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
39 | FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
40 | DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
41 | OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
42 | HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
43 | LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
44 | OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
45 | SUCH DAMAGE.*/ | |
60478656 RM |
46 | |
47 | /* | |
48 | * This is derived from the Berkeley source: | |
49 | * @(#)random.c 5.5 (Berkeley) 7/6/88 | |
50 | * It was reworked for the GNU C Library by Roland McGrath. | |
845dcb57 | 51 | * Rewritten to be reentrant by Ulrich Drepper, 1995 |
60478656 RM |
52 | */ |
53 | ||
54 | #include <errno.h> | |
55 | #include <limits.h> | |
56 | #include <stddef.h> | |
57 | #include <stdlib.h> | |
58 | ||
59 | ||
60 | /* An improved random number generation package. In addition to the standard | |
61 | rand()/srand() like interface, this package also has a special state info | |
62 | interface. The initstate() routine is called with a seed, an array of | |
63 | bytes, and a count of how many bytes are being passed in; this array is | |
64 | then initialized to contain information for random number generation with | |
65 | that much state information. Good sizes for the amount of state | |
66 | information are 32, 64, 128, and 256 bytes. The state can be switched by | |
6d52618b | 67 | calling the setstate() function with the same array as was initialized |
60478656 RM |
68 | with initstate(). By default, the package runs with 128 bytes of state |
69 | information and generates far better random numbers than a linear | |
70 | congruential generator. If the amount of state information is less than | |
71 | 32 bytes, a simple linear congruential R.N.G. is used. Internally, the | |
6d52618b | 72 | state information is treated as an array of longs; the zeroth element of |
60478656 RM |
73 | the array is the type of R.N.G. being used (small integer); the remainder |
74 | of the array is the state information for the R.N.G. Thus, 32 bytes of | |
75 | state information will give 7 longs worth of state information, which will | |
6d52618b | 76 | allow a degree seven polynomial. (Note: The zeroth word of state |
60478656 RM |
77 | information also has some other information stored in it; see setstate |
78 | for details). The random number generation technique is a linear feedback | |
79 | shift register approach, employing trinomials (since there are fewer terms | |
80 | to sum up that way). In this approach, the least significant bit of all | |
81 | the numbers in the state table will act as a linear feedback shift register, | |
82 | and will have period 2^deg - 1 (where deg is the degree of the polynomial | |
83 | being used, assuming that the polynomial is irreducible and primitive). | |
84 | The higher order bits will have longer periods, since their values are | |
85 | also influenced by pseudo-random carries out of the lower bits. The | |
86 | total period of the generator is approximately deg*(2**deg - 1); thus | |
87 | doubling the amount of state information has a vast influence on the | |
88 | period of the generator. Note: The deg*(2**deg - 1) is an approximation | |
89 | only good for large deg, when the period of the shift register is the | |
90 | dominant factor. With deg equal to seven, the period is actually much | |
91 | longer than the 7*(2**7 - 1) predicted by this formula. */ | |
92 | ||
93 | ||
94 | ||
95 | /* For each of the currently supported random number generators, we have a | |
6d52618b | 96 | break value on the amount of state information (you need at least this many |
60478656 RM |
97 | bytes of state info to support this random number generator), a degree for |
98 | the polynomial (actually a trinomial) that the R.N.G. is based on, and | |
99 | separation between the two lower order coefficients of the trinomial. */ | |
100 | ||
101 | /* Linear congruential. */ | |
102 | #define TYPE_0 0 | |
103 | #define BREAK_0 8 | |
104 | #define DEG_0 0 | |
105 | #define SEP_0 0 | |
106 | ||
107 | /* x**7 + x**3 + 1. */ | |
108 | #define TYPE_1 1 | |
109 | #define BREAK_1 32 | |
110 | #define DEG_1 7 | |
111 | #define SEP_1 3 | |
112 | ||
113 | /* x**15 + x + 1. */ | |
114 | #define TYPE_2 2 | |
115 | #define BREAK_2 64 | |
116 | #define DEG_2 15 | |
117 | #define SEP_2 1 | |
118 | ||
119 | /* x**31 + x**3 + 1. */ | |
120 | #define TYPE_3 3 | |
121 | #define BREAK_3 128 | |
122 | #define DEG_3 31 | |
123 | #define SEP_3 3 | |
124 | ||
125 | /* x**63 + x + 1. */ | |
126 | #define TYPE_4 4 | |
127 | #define BREAK_4 256 | |
128 | #define DEG_4 63 | |
129 | #define SEP_4 1 | |
130 | ||
131 | ||
132 | /* Array versions of the above information to make code run faster. | |
133 | Relies on fact that TYPE_i == i. */ | |
134 | ||
135 | #define MAX_TYPES 5 /* Max number of types above. */ | |
136 | ||
3e300ca1 UD |
137 | struct random_poly_info |
138 | { | |
6958e78d UD |
139 | int seps[MAX_TYPES]; |
140 | int degrees[MAX_TYPES]; | |
3e300ca1 | 141 | }; |
60478656 | 142 | |
3e300ca1 UD |
143 | static const struct random_poly_info random_poly_info = |
144 | { | |
6958e78d UD |
145 | { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }, |
146 | { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 } | |
3e300ca1 | 147 | }; |
60478656 RM |
148 | |
149 | ||
6958e78d | 150 | |
60478656 RM |
151 | \f |
152 | /* Initialize the random number generator based on the given seed. If the | |
153 | type is the trivial no-state-information type, just remember the seed. | |
154 | Otherwise, initializes state[] based on the given "seed" via a linear | |
155 | congruential generator. Then, the pointers are set to known locations | |
156 | that are exactly rand_sep places apart. Lastly, it cycles the state | |
157 | information a given number of times to get rid of any initial dependencies | |
158 | introduced by the L.C.R.N.G. Note that the initialization of randtbl[] | |
159 | for default usage relies on values produced by this routine. */ | |
160 | int | |
3e300ca1 UD |
161 | __srandom_r (seed, buf) |
162 | unsigned int seed; | |
60478656 RM |
163 | struct random_data *buf; |
164 | { | |
3e300ca1 UD |
165 | int type; |
166 | int32_t *state; | |
6958e78d | 167 | long int i; |
fe12c798 | 168 | int32_t word; |
6958e78d UD |
169 | int32_t *dst; |
170 | int kc; | |
3e300ca1 UD |
171 | |
172 | if (buf == NULL) | |
173 | goto fail; | |
174 | type = buf->rand_type; | |
6958e78d | 175 | if ((unsigned int) type >= MAX_TYPES) |
3e300ca1 | 176 | goto fail; |
60478656 | 177 | |
3e300ca1 | 178 | state = buf->state; |
6958e78d | 179 | /* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */ |
3e300ca1 UD |
180 | if (seed == 0) |
181 | seed = 1; | |
182 | state[0] = seed; | |
183 | if (type == TYPE_0) | |
184 | goto done; | |
185 | ||
6958e78d UD |
186 | dst = state; |
187 | word = seed; | |
188 | kc = buf->rand_deg; | |
189 | for (i = 1; i < kc; ++i) | |
60478656 | 190 | { |
6958e78d UD |
191 | /* This does: |
192 | state[i] = (16807 * state[i - 1]) % 2147483647; | |
193 | but avoids overflowing 31 bits. */ | |
194 | long int hi = word / 127773; | |
195 | long int lo = word % 127773; | |
196 | word = 16807 * lo - 2836 * hi; | |
197 | if (word < 0) | |
198 | word += 2147483647; | |
199 | *++dst = word; | |
60478656 | 200 | } |
3e300ca1 | 201 | |
6958e78d UD |
202 | buf->fptr = &state[buf->rand_sep]; |
203 | buf->rptr = &state[0]; | |
204 | kc *= 10; | |
205 | while (--kc >= 0) | |
206 | { | |
207 | int32_t discard; | |
208 | (void) __random_r (buf, &discard); | |
209 | } | |
60478656 | 210 | |
3e300ca1 | 211 | done: |
60478656 | 212 | return 0; |
6958e78d UD |
213 | |
214 | fail: | |
215 | return -1; | |
60478656 RM |
216 | } |
217 | ||
218 | weak_alias (__srandom_r, srandom_r) | |
60478656 RM |
219 | \f |
220 | /* Initialize the state information in the given array of N bytes for | |
221 | future random number generation. Based on the number of bytes we | |
222 | are given, and the break values for the different R.N.G.'s, we choose | |
223 | the best (largest) one we can and set things up for it. srandom is | |
224 | then called to initialize the state information. Note that on return | |
225 | from srandom, we set state[-1] to be the type multiplexed with the current | |
226 | value of the rear pointer; this is so successive calls to initstate won't | |
227 | lose this information and will 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. | |
c53f6228 | 230 | Returns 0 on success, non-zero on failure. */ |
60478656 RM |
231 | int |
232 | __initstate_r (seed, arg_state, n, buf) | |
233 | unsigned int seed; | |
4afa1485 | 234 | char *arg_state; |
60478656 RM |
235 | size_t n; |
236 | struct random_data *buf; | |
237 | { | |
238 | if (buf == NULL) | |
3e300ca1 | 239 | goto fail; |
60478656 | 240 | |
fcc3501c UD |
241 | int32_t *old_state = buf->state; |
242 | if (old_state != NULL) | |
243 | { | |
244 | int old_type = buf->rand_type; | |
245 | if (old_type == TYPE_0) | |
246 | old_state[-1] = TYPE_0; | |
247 | else | |
248 | old_state[-1] = (MAX_TYPES * (buf->rptr - old_state)) + old_type; | |
249 | } | |
f17c2202 | 250 | |
fcc3501c | 251 | int type; |
3e300ca1 UD |
252 | if (n >= BREAK_3) |
253 | type = n < BREAK_4 ? TYPE_3 : TYPE_4; | |
254 | else if (n < BREAK_1) | |
60478656 RM |
255 | { |
256 | if (n < BREAK_0) | |
1abedcda UD |
257 | goto fail; |
258 | ||
3e300ca1 | 259 | type = TYPE_0; |
60478656 RM |
260 | } |
261 | else | |
3e300ca1 UD |
262 | type = n < BREAK_2 ? TYPE_1 : TYPE_2; |
263 | ||
fcc3501c UD |
264 | int degree = random_poly_info.degrees[type]; |
265 | int separation = random_poly_info.seps[type]; | |
60478656 | 266 | |
6958e78d UD |
267 | buf->rand_type = type; |
268 | buf->rand_sep = separation; | |
269 | buf->rand_deg = degree; | |
fcc3501c | 270 | int32_t *state = &((int32_t *) arg_state)[1]; /* First location. */ |
60478656 | 271 | /* Must set END_PTR before srandom. */ |
3e300ca1 | 272 | buf->end_ptr = &state[degree]; |
60478656 | 273 | |
6958e78d | 274 | buf->state = state; |
3e300ca1 UD |
275 | |
276 | __srandom_r (seed, buf); | |
60478656 | 277 | |
6958e78d UD |
278 | state[-1] = TYPE_0; |
279 | if (type != TYPE_0) | |
280 | state[-1] = (buf->rptr - state) * MAX_TYPES + type; | |
281 | ||
60478656 | 282 | return 0; |
3e300ca1 UD |
283 | |
284 | fail: | |
faa57563 | 285 | __set_errno (EINVAL); |
3e300ca1 | 286 | return -1; |
60478656 RM |
287 | } |
288 | ||
289 | weak_alias (__initstate_r, initstate_r) | |
290 | \f | |
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 | |
6d52618b | 295 | location into the zeroth word of the state information. Note that due |
60478656 RM |
296 | to the order in which things are done, it is OK to call setstate with the |
297 | same state as the current state | |
c53f6228 | 298 | Returns 0 on success, non-zero on failure. */ |
60478656 RM |
299 | int |
300 | __setstate_r (arg_state, buf) | |
4afa1485 | 301 | char *arg_state; |
60478656 RM |
302 | struct random_data *buf; |
303 | { | |
ea83223c | 304 | int32_t *new_state = 1 + (int32_t *) arg_state; |
26afaa63 | 305 | int type; |
6958e78d | 306 | int old_type; |
3e300ca1 | 307 | int32_t *old_state; |
3e300ca1 UD |
308 | int degree; |
309 | int separation; | |
60478656 | 310 | |
faa57563 | 311 | if (arg_state == NULL || buf == NULL) |
6958e78d | 312 | goto fail; |
60478656 | 313 | |
3e300ca1 UD |
314 | old_type = buf->rand_type; |
315 | old_state = buf->state; | |
6958e78d UD |
316 | if (old_type == TYPE_0) |
317 | old_state[-1] = TYPE_0; | |
318 | else | |
319 | old_state[-1] = (MAX_TYPES * (buf->rptr - old_state)) + old_type; | |
320 | ||
ea83223c | 321 | type = new_state[-1] % MAX_TYPES; |
4fcddf8e | 322 | if (type < TYPE_0 || type > TYPE_4) |
26afaa63 UD |
323 | goto fail; |
324 | ||
6958e78d UD |
325 | buf->rand_deg = degree = random_poly_info.degrees[type]; |
326 | buf->rand_sep = separation = random_poly_info.seps[type]; | |
327 | buf->rand_type = type; | |
3e300ca1 | 328 | |
3e300ca1 | 329 | if (type != TYPE_0) |
60478656 | 330 | { |
ea83223c UD |
331 | int rear = new_state[-1] / MAX_TYPES; |
332 | buf->rptr = &new_state[rear]; | |
333 | buf->fptr = &new_state[(rear + separation) % degree]; | |
60478656 | 334 | } |
ea83223c | 335 | buf->state = new_state; |
6958e78d | 336 | /* Set end_ptr too. */ |
ea83223c | 337 | buf->end_ptr = &new_state[degree]; |
60478656 RM |
338 | |
339 | return 0; | |
3e300ca1 UD |
340 | |
341 | fail: | |
6958e78d | 342 | __set_errno (EINVAL); |
3e300ca1 | 343 | return -1; |
60478656 RM |
344 | } |
345 | ||
346 | weak_alias (__setstate_r, setstate_r) | |
347 | \f | |
348 | /* If we are using the trivial TYPE_0 R.N.G., just do the old linear | |
349 | congruential bit. Otherwise, we do our fancy trinomial stuff, which is the | |
6d52618b | 350 | same in all the other cases due to all the global variables that have been |
60478656 RM |
351 | set up. The basic operation is to add the number at the rear pointer into |
352 | the one at the front pointer. Then both pointers are advanced to the next | |
353 | location cyclically in the table. The value returned is the sum generated, | |
354 | reduced to 31 bits by throwing away the "least random" low bit. | |
6958e78d UD |
355 | Note: The code takes advantage of the fact that both the front and |
356 | rear pointers can't wrap on the same call by not testing the rear | |
357 | pointer if the front one has wrapped. Returns a 31-bit random number. */ | |
60478656 RM |
358 | |
359 | int | |
360 | __random_r (buf, result) | |
361 | struct random_data *buf; | |
b20e47cb | 362 | int32_t *result; |
60478656 | 363 | { |
6958e78d | 364 | int32_t *state; |
3e300ca1 | 365 | |
6958e78d | 366 | if (buf == NULL || result == NULL) |
3e300ca1 UD |
367 | goto fail; |
368 | ||
6958e78d UD |
369 | state = buf->state; |
370 | ||
371 | if (buf->rand_type == TYPE_0) | |
372 | { | |
373 | int32_t val = state[0]; | |
374 | val = ((state[0] * 1103515245) + 12345) & 0x7fffffff; | |
375 | state[0] = val; | |
376 | *result = val; | |
377 | } | |
378 | else | |
379 | { | |
380 | int32_t *fptr = buf->fptr; | |
381 | int32_t *rptr = buf->rptr; | |
382 | int32_t *end_ptr = buf->end_ptr; | |
383 | int32_t val; | |
384 | ||
385 | val = *fptr += *rptr; | |
386 | /* Chucking least random bit. */ | |
387 | *result = (val >> 1) & 0x7fffffff; | |
388 | ++fptr; | |
389 | if (fptr >= end_ptr) | |
390 | { | |
391 | fptr = state; | |
392 | ++rptr; | |
393 | } | |
394 | else | |
395 | { | |
396 | ++rptr; | |
397 | if (rptr >= end_ptr) | |
398 | rptr = state; | |
399 | } | |
400 | buf->fptr = fptr; | |
401 | buf->rptr = rptr; | |
402 | } | |
403 | return 0; | |
3e300ca1 UD |
404 | |
405 | fail: | |
faa57563 | 406 | __set_errno (EINVAL); |
3e300ca1 | 407 | return -1; |
60478656 RM |
408 | } |
409 | ||
410 | weak_alias (__random_r, random_r) |