1 /*
2 Copyright (C) 1995-2023 Free Software Foundation, Inc.
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
15 License along with the GNU C Library; if not, see
16 <https://www.gnu.org/licenses/>. */
17
18 /*
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.
34
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.*/
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.
51 * Rewritten to be reentrant by Ulrich Drepper, 1995
52 */
53
54 #ifndef _LIBC
55 /* Don't use __attribute__ __nonnull__ in this compilation unit. Otherwise gcc
56 optimizes away the buf == NULL, arg_state == NULL, result == NULL tests
57 below. */
58 # define _GL_ARG_NONNULL(params)
59
60 # include <libc-config.h>
61 # define __srandom_r srandom_r
62 # define __initstate_r initstate_r
63 # define __setstate_r setstate_r
64 # define __random_r random_r
65 #endif
66
67 /* Specification. */
68 #include <stdlib.h>
69
70 #include <errno.h>
71 #include <stddef.h>
72 #include <string.h>
73
74
75 /* An improved random number generation package. In addition to the standard
76 rand()/srand() like interface, this package also has a special state info
77 interface. The initstate() routine is called with a seed, an array of
78 bytes, and a count of how many bytes are being passed in; this array is
79 then initialized to contain information for random number generation with
80 that much state information. Good sizes for the amount of state
81 information are 32, 64, 128, and 256 bytes. The state can be switched by
82 calling the setstate() function with the same array as was initialized
83 with initstate(). By default, the package runs with 128 bytes of state
84 information and generates far better random numbers than a linear
85 congruential generator. If the amount of state information is less than
86 32 bytes, a simple linear congruential R.N.G. is used. Internally, the
87 state information is treated as an array of longs; the zeroth element of
88 the array is the type of R.N.G. being used (small integer); the remainder
89 of the array is the state information for the R.N.G. Thus, 32 bytes of
90 state information will give 7 longs worth of state information, which will
91 allow a degree seven polynomial. (Note: The zeroth word of state
92 information also has some other information stored in it; see setstate
93 for details). The random number generation technique is a linear feedback
94 shift register approach, employing trinomials (since there are fewer terms
95 to sum up that way). In this approach, the least significant bit of all
96 the numbers in the state table will act as a linear feedback shift register,
97 and will have period 2^deg - 1 (where deg is the degree of the polynomial
98 being used, assuming that the polynomial is irreducible and primitive).
99 The higher order bits will have longer periods, since their values are
100 also influenced by pseudo-random carries out of the lower bits. The
101 total period of the generator is approximately deg*(2**deg - 1); thus
102 doubling the amount of state information has a vast influence on the
103 period of the generator. Note: The deg*(2**deg - 1) is an approximation
104 only good for large deg, when the period of the shift register is the
105 dominant factor. With deg equal to seven, the period is actually much
106 longer than the 7*(2**7 - 1) predicted by this formula. */
107
108
109
110 /* For each of the currently supported random number generators, we have a
111 break value on the amount of state information (you need at least this many
112 bytes of state info to support this random number generator), a degree for
113 the polynomial (actually a trinomial) that the R.N.G. is based on, and
114 separation between the two lower order coefficients of the trinomial. */
115
116 /* Linear congruential. */
117 #define TYPE_0 0
118 #define BREAK_0 8
119 #define DEG_0 0
120 #define SEP_0 0
121
122 /* x**7 + x**3 + 1. */
123 #define TYPE_1 1
124 #define BREAK_1 32
125 #define DEG_1 7
126 #define SEP_1 3
127
128 /* x**15 + x + 1. */
129 #define TYPE_2 2
130 #define BREAK_2 64
131 #define DEG_2 15
132 #define SEP_2 1
133
134 /* x**31 + x**3 + 1. */
135 #define TYPE_3 3
136 #define BREAK_3 128
137 #define DEG_3 31
138 #define SEP_3 3
139
140 /* x**63 + x + 1. */
141 #define TYPE_4 4
142 #define BREAK_4 256
143 #define DEG_4 63
144 #define SEP_4 1
145
146
147 /* Array versions of the above information to make code run faster.
148 Relies on fact that TYPE_i == i. */
149
150 #define MAX_TYPES 5 /* Max number of types above. */
151
152 struct random_poly_info
153 {
154 int seps[MAX_TYPES];
155 int degrees[MAX_TYPES];
156 };
157
158 static const struct random_poly_info random_poly_info =
159 {
160 { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 },
161 { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }
162 };
163
164 static int32_t
165 get_int32 (void *p)
166 {
167 int32_t v;
168 memcpy (&v, p, sizeof v);
169 return v;
170 }
171
172 static void
173 set_int32 (void *p, int32_t v)
174 {
175 memcpy (p, &v, sizeof v);
176 }
177
178
179 /* Initialize the random number generator based on the given seed. If the
180 type is the trivial no-state-information type, just remember the seed.
181 Otherwise, initializes state[] based on the given "seed" via a linear
182 congruential generator. Then, the pointers are set to known locations
183 that are exactly rand_sep places apart. Lastly, it cycles the state
184 information a given number of times to get rid of any initial dependencies
185 introduced by the L.C.R.N.G. Note that the initialization of randtbl[]
186 for default usage relies on values produced by this routine. */
187 int
188 __srandom_r (unsigned int seed, struct random_data *buf)
189 {
190 int type;
191 int32_t *state;
192 long int i;
193 int32_t word;
194 int32_t *dst;
195 int kc;
196
197 if (buf == NULL)
198 goto fail;
199 type = buf->rand_type;
200 if ((unsigned int) type >= MAX_TYPES)
201 goto fail;
202
203 state = buf->state;
204 /* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */
205 if (seed == 0)
206 seed = 1;
207 set_int32 (&state[0], seed);
208 if (type == TYPE_0)
209 goto done;
210
211 dst = state;
212 word = seed;
213 kc = buf->rand_deg;
214 for (i = 1; i < kc; ++i)
215 {
216 /* This does:
217 state[i] = (16807 * state[i - 1]) % 2147483647;
218 but avoids overflowing 31 bits. */
219 long int hi = word / 127773;
220 long int lo = word % 127773;
221 word = 16807 * lo - 2836 * hi;
222 if (word < 0)
223 word += 2147483647;
224 set_int32 (++dst, word);
225 }
226
227 buf->fptr = &state[buf->rand_sep];
228 buf->rptr = &state[0];
229 kc *= 10;
230 while (--kc >= 0)
231 {
232 int32_t discard;
233 (void) __random_r (buf, &discard);
234 }
235
236 done:
237 return 0;
238
239 fail:
240 return -1;
241 }
242
243 weak_alias (__srandom_r, srandom_r)
244
245 /* Initialize the state information in the given array of N bytes for
246 future random number generation. Based on the number of bytes we
247 are given, and the break values for the different R.N.G.'s, we choose
248 the best (largest) one we can and set things up for it. srandom is
249 then called to initialize the state information. Note that on return
250 from srandom, we set state[-1] to be the type multiplexed with the current
251 value of the rear pointer; this is so successive calls to initstate won't
252 lose this information and will be able to restart with setstate.
253 Note: The first thing we do is save the current state, if any, just like
254 setstate so that it doesn't matter when initstate is called.
255 Returns 0 on success, non-zero on failure. */
256 int
257 __initstate_r (unsigned int seed, char *arg_state, size_t n,
258 struct random_data *buf)
259 {
260 if (buf == NULL)
261 goto fail;
262
263 int32_t *old_state = buf->state;
264 if (old_state != NULL)
265 {
266 int old_type = buf->rand_type;
267 set_int32 (&old_state[-1],
268 (old_type == TYPE_0
269 ? TYPE_0
270 : (MAX_TYPES * (buf->rptr - old_state)) + old_type));
271 }
272
273 int type;
274 if (n >= BREAK_3)
275 type = n < BREAK_4 ? TYPE_3 : TYPE_4;
276 else if (n < BREAK_1)
277 {
278 if (n < BREAK_0)
279 goto fail;
280
281 type = TYPE_0;
282 }
283 else
284 type = n < BREAK_2 ? TYPE_1 : TYPE_2;
285
286 int degree = random_poly_info.degrees[type];
287 int separation = random_poly_info.seps[type];
288
289 buf->rand_type = type;
290 buf->rand_sep = separation;
291 buf->rand_deg = degree;
292 int32_t *state = &((int32_t *) arg_state)[1]; /* First location. */
293 /* Must set END_PTR before srandom. */
294 buf->end_ptr = &state[degree];
295
296 buf->state = state;
297
298 __srandom_r (seed, buf);
299
300 set_int32 (&state[-1],
301 type == TYPE_0 ? TYPE_0 : (buf->rptr - state) * MAX_TYPES + type);
302
303 return 0;
304
305 fail:
306 __set_errno (EINVAL);
307 return -1;
308 }
309
310 weak_alias (__initstate_r, initstate_r)
311
312 /* Restore the state from the given state array.
313 Note: It is important that we also remember the locations of the pointers
314 in the current state information, and restore the locations of the pointers
315 from the old state information. This is done by multiplexing the pointer
316 location into the zeroth word of the state information. Note that due
317 to the order in which things are done, it is OK to call setstate with the
318 same state as the current state
319 Returns 0 on success, non-zero on failure. */
320 int
321 __setstate_r (char *arg_state, struct random_data *buf)
322 {
323 int32_t *new_state = 1 + (int32_t *) arg_state;
324 int type;
325 int old_type;
326 int32_t *old_state;
327 int degree;
328 int separation;
329
330 if (arg_state == NULL || buf == NULL)
331 goto fail;
332
333 old_type = buf->rand_type;
334 old_state = buf->state;
335 set_int32 (&old_state[-1],
336 (old_type == TYPE_0
337 ? TYPE_0
338 : (MAX_TYPES * (buf->rptr - old_state)) + old_type));
339
340 type = get_int32 (&new_state[-1]) % MAX_TYPES;
341 if (type < TYPE_0 || type > TYPE_4)
342 goto fail;
343
344 buf->rand_deg = degree = random_poly_info.degrees[type];
345 buf->rand_sep = separation = random_poly_info.seps[type];
346 buf->rand_type = type;
347
348 if (type != TYPE_0)
349 {
350 int rear = get_int32 (&new_state[-1]) / MAX_TYPES;
351 buf->rptr = &new_state[rear];
352 buf->fptr = &new_state[(rear + separation) % degree];
353 }
354 buf->state = new_state;
355 /* Set end_ptr too. */
356 buf->end_ptr = &new_state[degree];
357
358 return 0;
359
360 fail:
361 __set_errno (EINVAL);
362 return -1;
363 }
364
365 weak_alias (__setstate_r, setstate_r)
366
367 /* If we are using the trivial TYPE_0 R.N.G., just do the old linear
368 congruential bit. Otherwise, we do our fancy trinomial stuff, which is the
369 same in all the other cases due to all the global variables that have been
370 set up. The basic operation is to add the number at the rear pointer into
371 the one at the front pointer. Then both pointers are advanced to the next
372 location cyclically in the table. The value returned is the sum generated,
373 reduced to 31 bits by throwing away the "least random" low bit.
374 Note: The code takes advantage of the fact that both the front and
375 rear pointers can't wrap on the same call by not testing the rear
376 pointer if the front one has wrapped. Returns a 31-bit random number. */
377
378 int
379 __random_r (struct random_data *buf, int32_t *result)
380 {
381 int32_t *state;
382
383 if (buf == NULL || result == NULL)
384 goto fail;
385
386 state = buf->state;
387
388 if (buf->rand_type == TYPE_0)
389 {
390 int32_t val = (((get_int32 (&state[0]) * 1103515245U) + 12345U)
391 & 0x7fffffff);
392 set_int32 (&state[0], val);
393 *result = val;
394 }
395 else
396 {
397 int32_t *fptr = buf->fptr;
398 int32_t *rptr = buf->rptr;
399 int32_t *end_ptr = buf->end_ptr;
400 /* F and R are unsigned int, not uint32_t, to avoid undefined
401 overflow behavior on platforms where INT_MAX == UINT32_MAX. */
402 unsigned int f = get_int32 (fptr);
403 unsigned int r = get_int32 (rptr);
404 uint32_t val = f + r;
405 set_int32 (fptr, val);
406 /* Chucking least random bit. */
407 *result = val >> 1;
408 ++fptr;
409 if (fptr >= end_ptr)
410 {
411 fptr = state;
412 ++rptr;
413 }
414 else
415 {
416 ++rptr;
417 if (rptr >= end_ptr)
418 rptr = state;
419 }
420 buf->fptr = fptr;
421 buf->rptr = rptr;
422 }
423 return 0;
424
425 fail:
426 __set_errno (EINVAL);
427 return -1;
428 }
429
430 weak_alias (__random_r, random_r)