2 Copyright (C) 1995, 2005, 2008 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 3 of the License, or
7 (at your option) any later version.
9 This program 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
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
18 Copyright (C) 1983 Regents of the University of California.
21 Redistribution and use in source and binary forms, with or without
22 modification, are permitted provided that the following conditions
25 1. Redistributions of source code must retain the above copyright
26 notice, this list of conditions and the following disclaimer.
27 2. Redistributions in binary form must reproduce the above copyright
28 notice, this list of conditions and the following disclaimer in the
29 documentation and/or other materials provided with the distribution.
30 4. Neither the name of the University nor the names of its contributors
31 may be used to endorse or promote products derived from this software
32 without specific prior written permission.
34 THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47 * This is derived from the Berkeley source:
48 * @(#)random.c 5.5 (Berkeley) 7/6/88
49 * It was reworked for the GNU C Library by Roland McGrath.
50 * Rewritten to be reentrant by Ulrich Drepper, 1995
62 /* An improved random number generation package. In addition to the standard
63 rand()/srand() like interface, this package also has a special state info
64 interface. The initstate() routine is called with a seed, an array of
65 bytes, and a count of how many bytes are being passed in; this array is
66 then initialized to contain information for random number generation with
67 that much state information. Good sizes for the amount of state
68 information are 32, 64, 128, and 256 bytes. The state can be switched by
69 calling the setstate() function with the same array as was initialized
70 with initstate(). By default, the package runs with 128 bytes of state
71 information and generates far better random numbers than a linear
72 congruential generator. If the amount of state information is less than
73 32 bytes, a simple linear congruential R.N.G. is used. Internally, the
74 state information is treated as an array of longs; the zeroth element of
75 the array is the type of R.N.G. being used (small integer); the remainder
76 of the array is the state information for the R.N.G. Thus, 32 bytes of
77 state information will give 7 longs worth of state information, which will
78 allow a degree seven polynomial. (Note: The zeroth word of state
79 information also has some other information stored in it; see setstate
80 for details). The random number generation technique is a linear feedback
81 shift register approach, employing trinomials (since there are fewer terms
82 to sum up that way). In this approach, the least significant bit of all
83 the numbers in the state table will act as a linear feedback shift register,
84 and will have period 2^deg - 1 (where deg is the degree of the polynomial
85 being used, assuming that the polynomial is irreducible and primitive).
86 The higher order bits will have longer periods, since their values are
87 also influenced by pseudo-random carries out of the lower bits. The
88 total period of the generator is approximately deg*(2**deg - 1); thus
89 doubling the amount of state information has a vast influence on the
90 period of the generator. Note: The deg*(2**deg - 1) is an approximation
91 only good for large deg, when the period of the shift register is the
92 dominant factor. With deg equal to seven, the period is actually much
93 longer than the 7*(2**7 - 1) predicted by this formula. */
97 /* For each of the currently supported random number generators, we have a
98 break value on the amount of state information (you need at least this many
99 bytes of state info to support this random number generator), a degree for
100 the polynomial (actually a trinomial) that the R.N.G. is based on, and
101 separation between the two lower order coefficients of the trinomial. */
103 /* Linear congruential. */
109 /* x**7 + x**3 + 1. */
121 /* x**31 + x**3 + 1. */
134 /* Array versions of the above information to make code run faster.
135 Relies on fact that TYPE_i == i. */
137 #define MAX_TYPES 5 /* Max number of types above. */
139 struct random_poly_info
142 int degrees[MAX_TYPES];
145 static const struct random_poly_info random_poly_info =
147 { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 },
148 { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }
152 # define weak_alias(local, symbol)
153 # define __set_errno(e) errno = (e)
154 # define __srandom_r srandom_r
155 # define __initstate_r initstate_r
156 # define __setstate_r setstate_r
157 # define __random_r random_r
162 /* Initialize the random number generator based on the given seed. If the
163 type is the trivial no-state-information type, just remember the seed.
164 Otherwise, initializes state[] based on the given "seed" via a linear
165 congruential generator. Then, the pointers are set to known locations
166 that are exactly rand_sep places apart. Lastly, it cycles the state
167 information a given number of times to get rid of any initial dependencies
168 introduced by the L.C.R.N.G. Note that the initialization of randtbl[]
169 for default usage relies on values produced by this routine. */
171 __srandom_r (unsigned int seed, struct random_data *buf)
182 type = buf->rand_type;
183 if ((unsigned int) type >= MAX_TYPES)
187 /* We must make sure the seed is not 0. Take arbitrarily 1 in this case. */
197 for (i = 1; i < kc; ++i)
200 state[i] = (16807 * state[i - 1]) % 2147483647;
201 but avoids overflowing 31 bits. */
202 long int hi = word / 127773;
203 long int lo = word % 127773;
204 word = 16807 * lo - 2836 * hi;
210 buf->fptr = &state[buf->rand_sep];
211 buf->rptr = &state[0];
216 (void) __random_r (buf, &discard);
226 weak_alias (__srandom_r, srandom_r)
228 /* Initialize the state information in the given array of N bytes for
229 future random number generation. Based on the number of bytes we
230 are given, and the break values for the different R.N.G.'s, we choose
231 the best (largest) one we can and set things up for it. srandom is
232 then called to initialize the state information. Note that on return
233 from srandom, we set state[-1] to be the type multiplexed with the current
234 value of the rear pointer; this is so successive calls to initstate won't
235 lose this information and will be able to restart with setstate.
236 Note: The first thing we do is save the current state, if any, just like
237 setstate so that it doesn't matter when initstate is called.
238 Returns a pointer to the old state. */
240 __initstate_r (unsigned int seed, char *arg_state, size_t n,
241 struct random_data *buf)
252 old_state = buf->state;
253 if (old_state != NULL)
255 int old_type = buf->rand_type;
256 if (old_type == TYPE_0)
257 old_state[-1] = TYPE_0;
259 old_state[-1] = (MAX_TYPES * (buf->rptr - old_state)) + old_type;
263 type = n < BREAK_4 ? TYPE_3 : TYPE_4;
264 else if (n < BREAK_1)
268 __set_errno (EINVAL);
274 type = n < BREAK_2 ? TYPE_1 : TYPE_2;
276 degree = random_poly_info.degrees[type];
277 separation = random_poly_info.seps[type];
279 buf->rand_type = type;
280 buf->rand_sep = separation;
281 buf->rand_deg = degree;
282 state = &((int32_t *) arg_state)[1]; /* First location. */
283 /* Must set END_PTR before srandom. */
284 buf->end_ptr = &state[degree];
288 __srandom_r (seed, buf);
292 state[-1] = (buf->rptr - state) * MAX_TYPES + type;
297 __set_errno (EINVAL);
301 weak_alias (__initstate_r, initstate_r)
303 /* Restore the state from the given state array.
304 Note: It is important that we also remember the locations of the pointers
305 in the current state information, and restore the locations of the pointers
306 from the old state information. This is done by multiplexing the pointer
307 location into the zeroth word of the state information. Note that due
308 to the order in which things are done, it is OK to call setstate with the
309 same state as the current state
310 Returns a pointer to the old state information. */
312 __setstate_r (char *arg_state, struct random_data *buf)
314 int32_t *new_state = 1 + (int32_t *) arg_state;
321 if (arg_state == NULL || buf == NULL)
324 old_type = buf->rand_type;
325 old_state = buf->state;
326 if (old_type == TYPE_0)
327 old_state[-1] = TYPE_0;
329 old_state[-1] = (MAX_TYPES * (buf->rptr - old_state)) + old_type;
331 type = new_state[-1] % MAX_TYPES;
332 if (type < TYPE_0 || type > TYPE_4)
335 buf->rand_deg = degree = random_poly_info.degrees[type];
336 buf->rand_sep = separation = random_poly_info.seps[type];
337 buf->rand_type = type;
341 int rear = new_state[-1] / MAX_TYPES;
342 buf->rptr = &new_state[rear];
343 buf->fptr = &new_state[(rear + separation) % degree];
345 buf->state = new_state;
346 /* Set end_ptr too. */
347 buf->end_ptr = &new_state[degree];
352 __set_errno (EINVAL);
356 weak_alias (__setstate_r, setstate_r)
358 /* If we are using the trivial TYPE_0 R.N.G., just do the old linear
359 congruential bit. Otherwise, we do our fancy trinomial stuff, which is the
360 same in all the other cases due to all the global variables that have been
361 set up. The basic operation is to add the number at the rear pointer into
362 the one at the front pointer. Then both pointers are advanced to the next
363 location cyclically in the table. The value returned is the sum generated,
364 reduced to 31 bits by throwing away the "least random" low bit.
365 Note: The code takes advantage of the fact that both the front and
366 rear pointers can't wrap on the same call by not testing the rear
367 pointer if the front one has wrapped. Returns a 31-bit random number. */
370 __random_r (struct random_data *buf, int32_t *result)
374 if (buf == NULL || result == NULL)
379 if (buf->rand_type == TYPE_0)
381 int32_t val = state[0];
382 val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
388 int32_t *fptr = buf->fptr;
389 int32_t *rptr = buf->rptr;
390 int32_t *end_ptr = buf->end_ptr;
393 val = *fptr += *rptr;
394 /* Chucking least random bit. */
395 *result = (val >> 1) & 0x7fffffff;
414 __set_errno (EINVAL);
418 weak_alias (__random_r, random_r)