]>
Commit | Line | Data |
---|---|---|
fcc3501c | 1 | /* |
581c785b | 2 | Copyright (C) 1995-2022 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 | 15 | License along with the GNU C Library; if not, see |
5a82c748 | 16 | <https://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 | |
9d46370c | 161 | __srandom_r (unsigned int seed, struct random_data *buf) |
60478656 | 162 | { |
3e300ca1 UD |
163 | int type; |
164 | int32_t *state; | |
6958e78d | 165 | long int i; |
fe12c798 | 166 | int32_t word; |
6958e78d UD |
167 | int32_t *dst; |
168 | int kc; | |
3e300ca1 UD |
169 | |
170 | if (buf == NULL) | |
171 | goto fail; | |
172 | type = buf->rand_type; | |
6958e78d | 173 | if ((unsigned int) type >= MAX_TYPES) |
3e300ca1 | 174 | goto fail; |
60478656 | 175 | |
3e300ca1 | 176 | state = buf->state; |
6958e78d | 177 | /* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */ |
3e300ca1 UD |
178 | if (seed == 0) |
179 | seed = 1; | |
180 | state[0] = seed; | |
181 | if (type == TYPE_0) | |
182 | goto done; | |
183 | ||
6958e78d UD |
184 | dst = state; |
185 | word = seed; | |
186 | kc = buf->rand_deg; | |
187 | for (i = 1; i < kc; ++i) | |
60478656 | 188 | { |
6958e78d UD |
189 | /* This does: |
190 | state[i] = (16807 * state[i - 1]) % 2147483647; | |
191 | but avoids overflowing 31 bits. */ | |
192 | long int hi = word / 127773; | |
193 | long int lo = word % 127773; | |
194 | word = 16807 * lo - 2836 * hi; | |
195 | if (word < 0) | |
196 | word += 2147483647; | |
197 | *++dst = word; | |
60478656 | 198 | } |
3e300ca1 | 199 | |
6958e78d UD |
200 | buf->fptr = &state[buf->rand_sep]; |
201 | buf->rptr = &state[0]; | |
202 | kc *= 10; | |
203 | while (--kc >= 0) | |
204 | { | |
205 | int32_t discard; | |
206 | (void) __random_r (buf, &discard); | |
207 | } | |
60478656 | 208 | |
3e300ca1 | 209 | done: |
60478656 | 210 | return 0; |
6958e78d UD |
211 | |
212 | fail: | |
213 | return -1; | |
60478656 RM |
214 | } |
215 | ||
216 | weak_alias (__srandom_r, srandom_r) | |
60478656 RM |
217 | \f |
218 | /* Initialize the state information in the given array of N bytes for | |
219 | future random number generation. Based on the number of bytes we | |
220 | are given, and the break values for the different R.N.G.'s, we choose | |
221 | the best (largest) one we can and set things up for it. srandom is | |
222 | then called to initialize the state information. Note that on return | |
223 | from srandom, we set state[-1] to be the type multiplexed with the current | |
224 | value of the rear pointer; this is so successive calls to initstate won't | |
225 | lose this information and will be able to restart with setstate. | |
226 | Note: The first thing we do is save the current state, if any, just like | |
227 | setstate so that it doesn't matter when initstate is called. | |
c53f6228 | 228 | Returns 0 on success, non-zero on failure. */ |
60478656 | 229 | int |
f63f2bfd JM |
230 | __initstate_r (unsigned int seed, char *arg_state, size_t n, |
231 | struct random_data *buf) | |
60478656 RM |
232 | { |
233 | if (buf == NULL) | |
3e300ca1 | 234 | goto fail; |
60478656 | 235 | |
fcc3501c UD |
236 | int32_t *old_state = buf->state; |
237 | if (old_state != NULL) | |
238 | { | |
239 | int old_type = buf->rand_type; | |
240 | if (old_type == TYPE_0) | |
241 | old_state[-1] = TYPE_0; | |
242 | else | |
243 | old_state[-1] = (MAX_TYPES * (buf->rptr - old_state)) + old_type; | |
244 | } | |
f17c2202 | 245 | |
fcc3501c | 246 | int type; |
3e300ca1 UD |
247 | if (n >= BREAK_3) |
248 | type = n < BREAK_4 ? TYPE_3 : TYPE_4; | |
249 | else if (n < BREAK_1) | |
60478656 RM |
250 | { |
251 | if (n < BREAK_0) | |
1abedcda UD |
252 | goto fail; |
253 | ||
3e300ca1 | 254 | type = TYPE_0; |
60478656 RM |
255 | } |
256 | else | |
3e300ca1 UD |
257 | type = n < BREAK_2 ? TYPE_1 : TYPE_2; |
258 | ||
fcc3501c UD |
259 | int degree = random_poly_info.degrees[type]; |
260 | int separation = random_poly_info.seps[type]; | |
60478656 | 261 | |
6958e78d UD |
262 | buf->rand_type = type; |
263 | buf->rand_sep = separation; | |
264 | buf->rand_deg = degree; | |
fcc3501c | 265 | int32_t *state = &((int32_t *) arg_state)[1]; /* First location. */ |
60478656 | 266 | /* Must set END_PTR before srandom. */ |
3e300ca1 | 267 | buf->end_ptr = &state[degree]; |
60478656 | 268 | |
6958e78d | 269 | buf->state = state; |
3e300ca1 UD |
270 | |
271 | __srandom_r (seed, buf); | |
60478656 | 272 | |
6958e78d UD |
273 | state[-1] = TYPE_0; |
274 | if (type != TYPE_0) | |
275 | state[-1] = (buf->rptr - state) * MAX_TYPES + type; | |
276 | ||
60478656 | 277 | return 0; |
3e300ca1 UD |
278 | |
279 | fail: | |
faa57563 | 280 | __set_errno (EINVAL); |
3e300ca1 | 281 | return -1; |
60478656 RM |
282 | } |
283 | ||
284 | weak_alias (__initstate_r, initstate_r) | |
285 | \f | |
286 | /* Restore the state from the given state array. | |
287 | Note: It is important that we also remember the locations of the pointers | |
288 | in the current state information, and restore the locations of the pointers | |
289 | from the old state information. This is done by multiplexing the pointer | |
6d52618b | 290 | location into the zeroth word of the state information. Note that due |
60478656 RM |
291 | to the order in which things are done, it is OK to call setstate with the |
292 | same state as the current state | |
c53f6228 | 293 | Returns 0 on success, non-zero on failure. */ |
60478656 | 294 | int |
9d46370c | 295 | __setstate_r (char *arg_state, struct random_data *buf) |
60478656 | 296 | { |
ea83223c | 297 | int32_t *new_state = 1 + (int32_t *) arg_state; |
26afaa63 | 298 | int type; |
6958e78d | 299 | int old_type; |
3e300ca1 | 300 | int32_t *old_state; |
3e300ca1 UD |
301 | int degree; |
302 | int separation; | |
60478656 | 303 | |
faa57563 | 304 | if (arg_state == NULL || buf == NULL) |
6958e78d | 305 | goto fail; |
60478656 | 306 | |
3e300ca1 UD |
307 | old_type = buf->rand_type; |
308 | old_state = buf->state; | |
6958e78d UD |
309 | if (old_type == TYPE_0) |
310 | old_state[-1] = TYPE_0; | |
311 | else | |
312 | old_state[-1] = (MAX_TYPES * (buf->rptr - old_state)) + old_type; | |
313 | ||
ea83223c | 314 | type = new_state[-1] % MAX_TYPES; |
4fcddf8e | 315 | if (type < TYPE_0 || type > TYPE_4) |
26afaa63 UD |
316 | goto fail; |
317 | ||
6958e78d UD |
318 | buf->rand_deg = degree = random_poly_info.degrees[type]; |
319 | buf->rand_sep = separation = random_poly_info.seps[type]; | |
320 | buf->rand_type = type; | |
3e300ca1 | 321 | |
3e300ca1 | 322 | if (type != TYPE_0) |
60478656 | 323 | { |
ea83223c UD |
324 | int rear = new_state[-1] / MAX_TYPES; |
325 | buf->rptr = &new_state[rear]; | |
326 | buf->fptr = &new_state[(rear + separation) % degree]; | |
60478656 | 327 | } |
ea83223c | 328 | buf->state = new_state; |
6958e78d | 329 | /* Set end_ptr too. */ |
ea83223c | 330 | buf->end_ptr = &new_state[degree]; |
60478656 RM |
331 | |
332 | return 0; | |
3e300ca1 UD |
333 | |
334 | fail: | |
6958e78d | 335 | __set_errno (EINVAL); |
3e300ca1 | 336 | return -1; |
60478656 RM |
337 | } |
338 | ||
339 | weak_alias (__setstate_r, setstate_r) | |
340 | \f | |
341 | /* If we are using the trivial TYPE_0 R.N.G., just do the old linear | |
342 | congruential bit. Otherwise, we do our fancy trinomial stuff, which is the | |
6d52618b | 343 | same in all the other cases due to all the global variables that have been |
60478656 RM |
344 | set up. The basic operation is to add the number at the rear pointer into |
345 | the one at the front pointer. Then both pointers are advanced to the next | |
346 | location cyclically in the table. The value returned is the sum generated, | |
347 | reduced to 31 bits by throwing away the "least random" low bit. | |
6958e78d UD |
348 | Note: The code takes advantage of the fact that both the front and |
349 | rear pointers can't wrap on the same call by not testing the rear | |
350 | pointer if the front one has wrapped. Returns a 31-bit random number. */ | |
60478656 RM |
351 | |
352 | int | |
9d46370c | 353 | __random_r (struct random_data *buf, int32_t *result) |
60478656 | 354 | { |
6958e78d | 355 | int32_t *state; |
3e300ca1 | 356 | |
6958e78d | 357 | if (buf == NULL || result == NULL) |
3e300ca1 UD |
358 | goto fail; |
359 | ||
6958e78d UD |
360 | state = buf->state; |
361 | ||
362 | if (buf->rand_type == TYPE_0) | |
363 | { | |
8a07b0c4 | 364 | int32_t val = ((state[0] * 1103515245U) + 12345U) & 0x7fffffff; |
6958e78d UD |
365 | state[0] = val; |
366 | *result = val; | |
367 | } | |
368 | else | |
369 | { | |
370 | int32_t *fptr = buf->fptr; | |
371 | int32_t *rptr = buf->rptr; | |
372 | int32_t *end_ptr = buf->end_ptr; | |
8a07b0c4 | 373 | uint32_t val; |
6958e78d | 374 | |
8a07b0c4 | 375 | val = *fptr += (uint32_t) *rptr; |
6958e78d | 376 | /* Chucking least random bit. */ |
8a07b0c4 | 377 | *result = val >> 1; |
6958e78d UD |
378 | ++fptr; |
379 | if (fptr >= end_ptr) | |
380 | { | |
381 | fptr = state; | |
382 | ++rptr; | |
383 | } | |
384 | else | |
385 | { | |
386 | ++rptr; | |
387 | if (rptr >= end_ptr) | |
388 | rptr = state; | |
389 | } | |
390 | buf->fptr = fptr; | |
391 | buf->rptr = rptr; | |
392 | } | |
393 | return 0; | |
3e300ca1 UD |
394 | |
395 | fail: | |
faa57563 | 396 | __set_errno (EINVAL); |
3e300ca1 | 397 | return -1; |
60478656 RM |
398 | } |
399 | ||
400 | weak_alias (__random_r, random_r) |