GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libc/stdlib/random.c Lines: 0 76 0.0 %
Date: 2017-11-13 Branches: 0 52 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: random.c,v 1.30 2016/04/05 04:29:21 guenther 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
116
static int degrees[MAX_TYPES] =	{ DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
117
static 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
133
static 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
 */
157
static int32_t *fptr = &randtbl[SEP_3 + 1];
158
static 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
 */
170
static int32_t *state = &randtbl[1];
171
static int32_t *end_ptr = &randtbl[DEG_3 + 1];
172
static int rand_type = TYPE_3;
173
static int rand_deg = DEG_3;
174
static int rand_sep = SEP_3;
175
176
static int random_deterministic;
177
178
static void *random_mutex;
179
static 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
 */
196
static void
197
srandom_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
228
void
229
srandom(unsigned int x)
230
{
231
	random_deterministic = 0;
232
}
233
234
void
235
srandomdev(void)
236
{
237
	random_deterministic = 0;	/* back to the default */
238
}
239
240
void
241
srandom_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
 */
267
char *
268
initstate(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
 */
329
char *
330
setstate(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
 */
384
static long
385
random_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
406
long
407
random(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
    "warning: random() may return deterministic values, is that what you want?");
419
#endif