summaryrefslogtreecommitdiff
path: root/src/lib/libc/stdlib/random.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libc/stdlib/random.c')
-rw-r--r--src/lib/libc/stdlib/random.c419
1 files changed, 0 insertions, 419 deletions
diff --git a/src/lib/libc/stdlib/random.c b/src/lib/libc/stdlib/random.c
deleted file mode 100644
index 62a0c24bdb..0000000000
--- a/src/lib/libc/stdlib/random.c
+++ /dev/null
@@ -1,419 +0,0 @@
1/* $OpenBSD: random.c,v 1.31 2017/11/28 06:55:49 tb Exp $ */
2/*
3 * Copyright (c) 1983 Regents of the University of California.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the University nor the names of its contributors
15 * may be used to endorse or promote products derived from this software
16 * without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31#include <fcntl.h>
32#include <stdio.h>
33#include <stdlib.h>
34#include <unistd.h>
35
36#include "thread_private.h"
37
38/*
39 * random.c:
40 *
41 * An improved random number generation package. In addition to the standard
42 * rand()/srand() like interface, this package also has a special state info
43 * interface. The initstate() routine is called with a seed, an array of
44 * bytes, and a count of how many bytes are being passed in; this array is
45 * then initialized to contain information for random number generation with
46 * that much state information. Good sizes for the amount of state
47 * information are 32, 64, 128, and 256 bytes. The state can be switched by
48 * calling the setstate() routine with the same array as was initiallized
49 * with initstate(). By default, the package runs with 128 bytes of state
50 * information and generates far better random numbers than a linear
51 * congruential generator. If the amount of state information is less than
52 * 32 bytes, a simple linear congruential R.N.G. is used.
53 *
54 * Internally, the state information is treated as an array of int32_t; the
55 * zeroeth element of the array is the type of R.N.G. being used (small
56 * integer); the remainder of the array is the state information for the
57 * R.N.G. Thus, 32 bytes of state information will give 7 int32_ts worth of
58 * state information, which will allow a degree seven polynomial. (Note:
59 * the zeroeth word of state information also has some other information
60 * stored in it -- see setstate() for details).
61 *
62 * The random number generation technique is a linear feedback shift register
63 * approach, employing trinomials (since there are fewer terms to sum up that
64 * way). In this approach, the least significant bit of all the numbers in
65 * the state table will act as a linear feedback shift register, and will
66 * have period 2^deg - 1 (where deg is the degree of the polynomial being
67 * used, assuming that the polynomial is irreducible and primitive). The
68 * higher order bits will have longer periods, since their values are also
69 * influenced by pseudo-random carries out of the lower bits. The total
70 * period of the generator is approximately deg*(2**deg - 1); thus doubling
71 * the amount of state information has a vast influence on the period of the
72 * generator. Note: the deg*(2**deg - 1) is an approximation only good for
73 * large deg, when the period of the shift register is the dominant factor.
74 * With deg equal to seven, the period is actually much longer than the
75 * 7*(2**7 - 1) predicted by this formula.
76 */
77
78/*
79 * For each of the currently supported random number generators, we have a
80 * break value on the amount of state information (you need at least this
81 * many bytes of state info to support this random number generator), a degree
82 * for the polynomial (actually a trinomial) that the R.N.G. is based on, and
83 * the separation between the two lower order coefficients of the trinomial.
84 */
85#define TYPE_0 0 /* linear congruential */
86#define BREAK_0 8
87#define DEG_0 0
88#define SEP_0 0
89
90#define TYPE_1 1 /* x**7 + x**3 + 1 */
91#define BREAK_1 32
92#define DEG_1 7
93#define SEP_1 3
94
95#define TYPE_2 2 /* x**15 + x + 1 */
96#define BREAK_2 64
97#define DEG_2 15
98#define SEP_2 1
99
100#define TYPE_3 3 /* x**31 + x**3 + 1 */
101#define BREAK_3 128
102#define DEG_3 31
103#define SEP_3 3
104
105#define TYPE_4 4 /* x**63 + x + 1 */
106#define BREAK_4 256
107#define DEG_4 63
108#define SEP_4 1
109
110/*
111 * Array versions of the above information to make code run faster --
112 * relies on fact that TYPE_i == i.
113 */
114#define MAX_TYPES 5 /* max number of types above */
115
116static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
117static int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
118
119/*
120 * Initially, everything is set up as if from:
121 *
122 * initstate(1, &randtbl, 128);
123 *
124 * Note that this initialization takes advantage of the fact that srandom()
125 * advances the front and rear pointers 10*rand_deg times, and hence the
126 * rear pointer which starts at 0 will also end up at zero; thus the zeroeth
127 * element of the state information, which contains info about the current
128 * position of the rear pointer is just
129 *
130 * MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3.
131 */
132
133static int32_t randtbl[DEG_3 + 1] = {
134 TYPE_3,
135 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05,
136 0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454,
137 0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471,
138 0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1,
139 0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41,
140 0xf3bec5da,
141};
142
143/*
144 * fptr and rptr are two pointers into the state info, a front and a rear
145 * pointer. These two pointers are always rand_sep places aparts, as they
146 * cycle cyclically through the state information. (Yes, this does mean we
147 * could get away with just one pointer, but the code for random() is more
148 * efficient this way). The pointers are left positioned as they would be
149 * from the call
150 *
151 * initstate(1, randtbl, 128);
152 *
153 * (The position of the rear pointer, rptr, is really 0 (as explained above
154 * in the initialization of randtbl) because the state table pointer is set
155 * to point to randtbl[1] (as explained below).
156 */
157static int32_t *fptr = &randtbl[SEP_3 + 1];
158static int32_t *rptr = &randtbl[1];
159
160/*
161 * The following things are the pointer to the state information table, the
162 * type of the current generator, the degree of the current polynomial being
163 * used, and the separation between the two pointers. Note that for efficiency
164 * of random(), we remember the first location of the state information, not
165 * the zeroeth. Hence it is valid to access state[-1], which is used to
166 * store the type of the R.N.G. Also, we remember the last location, since
167 * this is more efficient than indexing every time to find the address of
168 * the last element to see if the front and rear pointers have wrapped.
169 */
170static int32_t *state = &randtbl[1];
171static int32_t *end_ptr = &randtbl[DEG_3 + 1];
172static int rand_type = TYPE_3;
173static int rand_deg = DEG_3;
174static int rand_sep = SEP_3;
175
176static int random_deterministic;
177
178static void *random_mutex;
179static long random_l(void);
180
181#define LOCK() _MUTEX_LOCK(&random_mutex)
182#define UNLOCK() _MUTEX_UNLOCK(&random_mutex)
183
184/*
185 * srandom:
186 *
187 * Initialize the random number generator based on the given seed. If the
188 * type is the trivial no-state-information type, just remember the seed.
189 * Otherwise, initializes state[] based on the given "seed" via a linear
190 * congruential generator. Then, the pointers are set to known locations
191 * that are exactly rand_sep places apart. Lastly, it cycles the state
192 * information a given number of times to get rid of any initial dependencies
193 * introduced by the L.C.R.N.G. Note that the initialization of randtbl[]
194 * for default usage relies on values produced by this routine.
195 */
196static void
197srandom_l(unsigned int x)
198{
199 int i;
200 int32_t test;
201 div_t val;
202
203 random_deterministic = 1;
204 if (rand_type == TYPE_0)
205 state[0] = x;
206 else {
207 /* A seed of 0 would result in state[] always being zero. */
208 state[0] = x ? x : 1;
209 for (i = 1; i < rand_deg; i++) {
210 /*
211 * Implement the following, without overflowing 31 bits:
212 *
213 * state[i] = (16807 * state[i - 1]) % 2147483647;
214 *
215 * 2^31-1 (prime) = 2147483647 = 127773*16807+2836
216 */
217 val = div(state[i-1], 127773);
218 test = 16807 * val.rem - 2836 * val.quot;
219 state[i] = test + (test < 0 ? 2147483647 : 0);
220 }
221 fptr = &state[rand_sep];
222 rptr = &state[0];
223 for (i = 0; i < 10 * rand_deg; i++)
224 (void)random_l();
225 }
226}
227
228void
229srandom(unsigned int x)
230{
231 random_deterministic = 0;
232}
233
234void
235srandomdev(void)
236{
237 random_deterministic = 0; /* back to the default */
238}
239
240void
241srandom_deterministic(unsigned int x)
242{
243 LOCK();
244 srandom_l(x);
245 UNLOCK();
246}
247
248/*
249 * initstate:
250 *
251 * Initialize the state information in the given array of n bytes for future
252 * random number generation. Based on the number of bytes we are given, and
253 * the break values for the different R.N.G.'s, we choose the best (largest)
254 * one we can and set things up for it. srandom() is then called to
255 * initialize the state information.
256 *
257 * Note that on return from srandom(), we set state[-1] to be the type
258 * multiplexed with the current value of the rear pointer; this is so
259 * successive calls to initstate() won't lose this information and will be
260 * able to restart with setstate().
261 *
262 * Note: the first thing we do is save the current state, if any, just like
263 * setstate() so that it doesn't matter when initstate is called.
264 *
265 * Returns a pointer to the old state.
266 */
267char *
268initstate(u_int seed, char *arg_state, size_t n)
269{
270 char *ostate = (char *)(&state[-1]);
271
272 LOCK();
273 random_deterministic = 1;
274 if (rand_type == TYPE_0)
275 state[-1] = rand_type;
276 else
277 state[-1] = MAX_TYPES * (rptr - state) + rand_type;
278 if (n < BREAK_0) {
279 UNLOCK();
280 return(NULL);
281 }
282 if (n < BREAK_1) {
283 rand_type = TYPE_0;
284 rand_deg = DEG_0;
285 rand_sep = SEP_0;
286 } else if (n < BREAK_2) {
287 rand_type = TYPE_1;
288 rand_deg = DEG_1;
289 rand_sep = SEP_1;
290 } else if (n < BREAK_3) {
291 rand_type = TYPE_2;
292 rand_deg = DEG_2;
293 rand_sep = SEP_2;
294 } else if (n < BREAK_4) {
295 rand_type = TYPE_3;
296 rand_deg = DEG_3;
297 rand_sep = SEP_3;
298 } else {
299 rand_type = TYPE_4;
300 rand_deg = DEG_4;
301 rand_sep = SEP_4;
302 }
303 state = &(((int32_t *)arg_state)[1]); /* first location */
304 end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */
305 srandom_l(seed);
306 if (rand_type == TYPE_0)
307 state[-1] = rand_type;
308 else
309 state[-1] = MAX_TYPES*(rptr - state) + rand_type;
310 UNLOCK();
311 return(ostate);
312}
313
314/*
315 * setstate:
316 *
317 * Restore the state from the given state array.
318 *
319 * Note: it is important that we also remember the locations of the pointers
320 * in the current state information, and restore the locations of the pointers
321 * from the old state information. This is done by multiplexing the pointer
322 * location into the zeroeth word of the state information.
323 *
324 * Note that due to the order in which things are done, it is OK to call
325 * setstate() with the same state as the current state.
326 *
327 * Returns a pointer to the old state information.
328 */
329char *
330setstate(char *arg_state)
331{
332 int32_t *new_state = (int32_t *)arg_state;
333 int32_t type = new_state[0] % MAX_TYPES;
334 int32_t rear = new_state[0] / MAX_TYPES;
335 char *ostate = (char *)(&state[-1]);
336
337 LOCK();
338 random_deterministic = 1;
339 if (rand_type == TYPE_0)
340 state[-1] = rand_type;
341 else
342 state[-1] = MAX_TYPES * (rptr - state) + rand_type;
343 switch(type) {
344 case TYPE_0:
345 case TYPE_1:
346 case TYPE_2:
347 case TYPE_3:
348 case TYPE_4:
349 rand_type = type;
350 rand_deg = degrees[type];
351 rand_sep = seps[type];
352 break;
353 default:
354 UNLOCK();
355 return(NULL);
356 }
357 state = &new_state[1];
358 if (rand_type != TYPE_0) {
359 rptr = &state[rear];
360 fptr = &state[(rear + rand_sep) % rand_deg];
361 }
362 end_ptr = &state[rand_deg]; /* set end_ptr too */
363 UNLOCK();
364 return(ostate);
365}
366
367/*
368 * random:
369 *
370 * If we are using the trivial TYPE_0 R.N.G., just do the old linear
371 * congruential bit. Otherwise, we do our fancy trinomial stuff, which is
372 * the same in all the other cases due to all the global variables that have
373 * been set up. The basic operation is to add the number at the rear pointer
374 * into the one at the front pointer. Then both pointers are advanced to
375 * the next location cyclically in the table. The value returned is the sum
376 * generated, reduced to 31 bits by throwing away the "least random" low bit.
377 *
378 * Note: the code takes advantage of the fact that both the front and
379 * rear pointers can't wrap on the same call by not testing the rear
380 * pointer if the front one has wrapped.
381 *
382 * Returns a 31-bit random number.
383 */
384static long
385random_l(void)
386{
387 int32_t i;
388
389 if (random_deterministic == 0)
390 return arc4random() & 0x7fffffff;
391
392 if (rand_type == TYPE_0)
393 i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff;
394 else {
395 *fptr += *rptr;
396 i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */
397 if (++fptr >= end_ptr) {
398 fptr = state;
399 ++rptr;
400 } else if (++rptr >= end_ptr)
401 rptr = state;
402 }
403 return((long)i);
404}
405
406long
407random(void)
408{
409 long r;
410 LOCK();
411 r = random_l();
412 UNLOCK();
413 return r;
414}
415
416#if defined(APIWARN)
417__warn_references(random,
418 "random() may return deterministic values, is that what you want?");
419#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-04-26 20:00:35 +0000