1da2e3ebdSchin #include "FEATURE/uwin"
2da2e3ebdSchin
3da2e3ebdSchin #if !_UWIN || _lib_random
4da2e3ebdSchin
_STUB_random()5da2e3ebdSchin void _STUB_random(){}
6da2e3ebdSchin
7da2e3ebdSchin #else
8da2e3ebdSchin
9da2e3ebdSchin /*
10da2e3ebdSchin * Copyright (c) 1983
11da2e3ebdSchin * The Regents of the University of California. All rights reserved.
12da2e3ebdSchin *
13da2e3ebdSchin * Redistribution and use in source and binary forms, with or without
14da2e3ebdSchin * modification, are permitted provided that the following conditions
15da2e3ebdSchin * are met:
16da2e3ebdSchin * 1. Redistributions of source code must retain the above copyright
17da2e3ebdSchin * notice, this list of conditions and the following disclaimer.
18da2e3ebdSchin * 2. Redistributions in binary form must reproduce the above copyright
19da2e3ebdSchin * notice, this list of conditions and the following disclaimer in the
20da2e3ebdSchin * documentation and/or other materials provided with the distribution.
21da2e3ebdSchin * 3. Neither the name of the University nor the names of its contributors
22da2e3ebdSchin * may be used to endorse or promote products derived from this software
23da2e3ebdSchin * without specific prior written permission.
24da2e3ebdSchin *
25da2e3ebdSchin * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26da2e3ebdSchin * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27da2e3ebdSchin * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28da2e3ebdSchin * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29da2e3ebdSchin * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30da2e3ebdSchin * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31da2e3ebdSchin * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32da2e3ebdSchin * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33da2e3ebdSchin * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34da2e3ebdSchin * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35da2e3ebdSchin * SUCH DAMAGE.
36da2e3ebdSchin */
37da2e3ebdSchin
38da2e3ebdSchin /*
39da2e3ebdSchin * This is derived from the Berkeley source:
40da2e3ebdSchin * @(#)random.c 5.5 (Berkeley) 7/6/88
41da2e3ebdSchin * It was reworked for the GNU C Library by Roland McGrath.
42da2e3ebdSchin */
43da2e3ebdSchin
44da2e3ebdSchin #define initstate ______initstate
45da2e3ebdSchin #define random ______random
46da2e3ebdSchin #define setstate ______setstate
47da2e3ebdSchin #define srandom ______srandom
48da2e3ebdSchin
49da2e3ebdSchin #include <errno.h>
50da2e3ebdSchin #include <limits.h>
51da2e3ebdSchin #include <stddef.h>
52da2e3ebdSchin #include <stdlib.h>
53da2e3ebdSchin
54da2e3ebdSchin #undef initstate
55da2e3ebdSchin #undef random
56da2e3ebdSchin #undef setstate
57da2e3ebdSchin #undef srandom
58da2e3ebdSchin
59da2e3ebdSchin #if defined(__EXPORT__)
60da2e3ebdSchin #define extern __EXPORT__
61da2e3ebdSchin #endif
62da2e3ebdSchin
63da2e3ebdSchin extern long int random();
64da2e3ebdSchin
65da2e3ebdSchin #define PTR char*
66da2e3ebdSchin
67da2e3ebdSchin /* An improved random number generation package. In addition to the standard
68da2e3ebdSchin rand()/srand() like interface, this package also has a special state info
69da2e3ebdSchin interface. The initstate() routine is called with a seed, an array of
70da2e3ebdSchin bytes, and a count of how many bytes are being passed in; this array is
71da2e3ebdSchin then initialized to contain information for random number generation with
72da2e3ebdSchin that much state information. Good sizes for the amount of state
73da2e3ebdSchin information are 32, 64, 128, and 256 bytes. The state can be switched by
74da2e3ebdSchin calling the setstate() function with the same array as was initiallized
75da2e3ebdSchin with initstate(). By default, the package runs with 128 bytes of state
76da2e3ebdSchin information and generates far better random numbers than a linear
77da2e3ebdSchin congruential generator. If the amount of state information is less than
78da2e3ebdSchin 32 bytes, a simple linear congruential R.N.G. is used. Internally, the
79da2e3ebdSchin state information is treated as an array of longs; the zeroeth element of
80da2e3ebdSchin the array is the type of R.N.G. being used (small integer); the remainder
81da2e3ebdSchin of the array is the state information for the R.N.G. Thus, 32 bytes of
82da2e3ebdSchin state information will give 7 longs worth of state information, which will
83da2e3ebdSchin allow a degree seven polynomial. (Note: The zeroeth word of state
84da2e3ebdSchin information also has some other information stored in it; see setstate
85da2e3ebdSchin for details). The random number generation technique is a linear feedback
86da2e3ebdSchin shift register approach, employing trinomials (since there are fewer terms
87da2e3ebdSchin to sum up that way). In this approach, the least significant bit of all
88da2e3ebdSchin the numbers in the state table will act as a linear feedback shift register,
89da2e3ebdSchin and will have period 2^deg - 1 (where deg is the degree of the polynomial
90da2e3ebdSchin being used, assuming that the polynomial is irreducible and primitive).
91da2e3ebdSchin The higher order bits will have longer periods, since their values are
92da2e3ebdSchin also influenced by pseudo-random carries out of the lower bits. The
93da2e3ebdSchin total period of the generator is approximately deg*(2**deg - 1); thus
94da2e3ebdSchin doubling the amount of state information has a vast influence on the
95da2e3ebdSchin period of the generator. Note: The deg*(2**deg - 1) is an approximation
96da2e3ebdSchin only good for large deg, when the period of the shift register is the
97da2e3ebdSchin dominant factor. With deg equal to seven, the period is actually much
98da2e3ebdSchin longer than the 7*(2**7 - 1) predicted by this formula. */
99da2e3ebdSchin
100da2e3ebdSchin
101da2e3ebdSchin
102da2e3ebdSchin /* For each of the currently supported random number generators, we have a
103da2e3ebdSchin break value on the amount of state information (you need at least thi
104da2e3ebdSchin bytes of state info to support this random number generator), a degree for
105da2e3ebdSchin the polynomial (actually a trinomial) that the R.N.G. is based on, and
106da2e3ebdSchin separation between the two lower order coefficients of the trinomial. */
107da2e3ebdSchin
108da2e3ebdSchin /* Linear congruential. */
109da2e3ebdSchin #define TYPE_0 0
110da2e3ebdSchin #define BREAK_0 8
111da2e3ebdSchin #define DEG_0 0
112da2e3ebdSchin #define SEP_0 0
113da2e3ebdSchin
114da2e3ebdSchin /* x**7 + x**3 + 1. */
115da2e3ebdSchin #define TYPE_1 1
116da2e3ebdSchin #define BREAK_1 32
117da2e3ebdSchin #define DEG_1 7
118da2e3ebdSchin #define SEP_1 3
119da2e3ebdSchin
120da2e3ebdSchin /* x**15 + x + 1. */
121da2e3ebdSchin #define TYPE_2 2
122da2e3ebdSchin #define BREAK_2 64
123da2e3ebdSchin #define DEG_2 15
124da2e3ebdSchin #define SEP_2 1
125da2e3ebdSchin
126da2e3ebdSchin /* x**31 + x**3 + 1. */
127da2e3ebdSchin #define TYPE_3 3
128da2e3ebdSchin #define BREAK_3 128
129da2e3ebdSchin #define DEG_3 31
130da2e3ebdSchin #define SEP_3 3
131da2e3ebdSchin
132da2e3ebdSchin /* x**63 + x + 1. */
133da2e3ebdSchin #define TYPE_4 4
134da2e3ebdSchin #define BREAK_4 256
135da2e3ebdSchin #define DEG_4 63
136da2e3ebdSchin #define SEP_4 1
137da2e3ebdSchin
138da2e3ebdSchin
139da2e3ebdSchin /* Array versions of the above information to make code run faster.
140da2e3ebdSchin Relies on fact that TYPE_i == i. */
141da2e3ebdSchin
142da2e3ebdSchin #define MAX_TYPES 5 /* Max number of types above. */
143da2e3ebdSchin
144da2e3ebdSchin static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
145da2e3ebdSchin static int seps[MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
146da2e3ebdSchin
147da2e3ebdSchin
148da2e3ebdSchin
149da2e3ebdSchin /* Initially, everything is set up as if from:
150da2e3ebdSchin initstate(1, randtbl, 128);
151da2e3ebdSchin Note that this initialization takes advantage of the fact that srandom
152da2e3ebdSchin advances the front and rear pointers 10*rand_deg times, and hence the
153da2e3ebdSchin rear pointer which starts at 0 will also end up at zero; thus the zeroeth
154da2e3ebdSchin element of the state information, which contains info about the current
155da2e3ebdSchin position of the rear pointer is just
156da2e3ebdSchin (MAX_TYPES * (rptr - state)) + TYPE_3 == TYPE_3. */
157da2e3ebdSchin
158da2e3ebdSchin static long int randtbl[DEG_3 + 1] =
159da2e3ebdSchin {
160da2e3ebdSchin TYPE_3,
161da2e3ebdSchin -851904987, -43806228, -2029755270, 1390239686, -1912102820,
162da2e3ebdSchin -485608943, 1969813258, -1590463333, -1944053249, 455935928, 508023712,
163da2e3ebdSchin -1714531963, 1800685987, -2015299881, 654595283, -1149023258,
164da2e3ebdSchin -1470005550, -1143256056, -1325577603, -1568001885, 1275120390,
165da2e3ebdSchin -607508183, -205999574, -1696891592, 1492211999, -1528267240,
166da2e3ebdSchin -952028296, -189082757, 362343714, 1424981831, 2039449641,
167da2e3ebdSchin };
168da2e3ebdSchin
169da2e3ebdSchin /* FPTR and RPTR are two pointers into the state info, a front and a rear
170da2e3ebdSchin pointer. These two pointers are always rand_sep places aparts, as they
171da2e3ebdSchin cycle through the state information. (Yes, this does mean we could get
172da2e3ebdSchin away with just one pointer, but the code for random is more efficient
173da2e3ebdSchin this way). The pointers are left positioned as they would be from the call:
174da2e3ebdSchin initstate(1, randtbl, 128);
175da2e3ebdSchin (The position of the rear pointer, rptr, is really 0 (as explained above
176da2e3ebdSchin in the initialization of randtbl) because the state table pointer is set
177da2e3ebdSchin to point to randtbl[1] (as explained below).) */
178da2e3ebdSchin
179da2e3ebdSchin static long int *fptr = &randtbl[SEP_3 + 1];
180da2e3ebdSchin static long int *rptr = &randtbl[1];
181da2e3ebdSchin
182da2e3ebdSchin
183da2e3ebdSchin
184da2e3ebdSchin /* The following things are the pointer to the state information table,
185da2e3ebdSchin the type of the current generator, the degree of the current polynomial
186da2e3ebdSchin being used, and the separation between the two pointers.
187da2e3ebdSchin Note that for efficiency of random, we remember the first location of
188da2e3ebdSchin the state information, not the zeroeth. Hence it is valid to access
189da2e3ebdSchin state[-1], which is used to store the type of the R.N.G.
190da2e3ebdSchin Also, we remember the last location, since this is more efficient than
191da2e3ebdSchin indexing every time to find the address of the last element to see if
192da2e3ebdSchin the front and rear pointers have wrapped. */
193da2e3ebdSchin
194da2e3ebdSchin static long int *state = &randtbl[1];
195da2e3ebdSchin
196da2e3ebdSchin static int rand_type = TYPE_3;
197da2e3ebdSchin static int rand_deg = DEG_3;
198da2e3ebdSchin static int rand_sep = SEP_3;
199da2e3ebdSchin
200da2e3ebdSchin static long int *end_ptr = &randtbl[sizeof(randtbl) / sizeof(randtbl[0])];
201da2e3ebdSchin
202da2e3ebdSchin /* Initialize the random number generator based on the given seed. If the
203da2e3ebdSchin type is the trivial no-state-information type, just remember the seed.
204da2e3ebdSchin Otherwise, initializes state[] based on the given "seed" via a linear
205da2e3ebdSchin congruential generator. Then, the pointers are set to known locations
206da2e3ebdSchin that are exactly rand_sep places apart. Lastly, it cycles the state
207da2e3ebdSchin information a given number of times to get rid of any initial dependencies
208da2e3ebdSchin introduced by the L.C.R.N.G. Note that the initialization of randtbl[]
209da2e3ebdSchin for default usage relies on values produced by this routine. */
srandom(unsigned int x)210da2e3ebdSchin extern void srandom(unsigned int x)
211da2e3ebdSchin {
212da2e3ebdSchin state[0] = x;
213da2e3ebdSchin if (rand_type != TYPE_0)
214da2e3ebdSchin {
215da2e3ebdSchin register long int i;
216da2e3ebdSchin for (i = 1; i < rand_deg; ++i)
217da2e3ebdSchin state[i] = (1103515145 * state[i - 1]) + 12345;
218da2e3ebdSchin fptr = &state[rand_sep];
219da2e3ebdSchin rptr = &state[0];
220da2e3ebdSchin for (i = 0; i < 10 * rand_deg; ++i)
221da2e3ebdSchin (void) random();
222da2e3ebdSchin }
223da2e3ebdSchin }
224da2e3ebdSchin
225da2e3ebdSchin /* Initialize the state information in the given array of N bytes for
226da2e3ebdSchin future random number generation. Based on the number of bytes we
227da2e3ebdSchin are given, and the break values for the different R.N.G.'s, we choose
228da2e3ebdSchin the best (largest) one we can and set things up for it. srandom is
229da2e3ebdSchin then called to initialize the state information. Note that on return
230da2e3ebdSchin from srandom, we set state[-1] to be the type multiplexed with the current
231da2e3ebdSchin value of the rear pointer; this is so successive calls to initstate won't
232da2e3ebdSchin lose this information and will be able to restart with setstate.
233da2e3ebdSchin Note: The first thing we do is save the current state, if any, just like
234da2e3ebdSchin setstate so that it doesn't matter when initstate is called.
235da2e3ebdSchin Returns a pointer to the old state. */
initstate(unsigned int seed,char * arg_state,size_t n)236da2e3ebdSchin extern char* initstate(unsigned int seed, char* arg_state, size_t n)
237da2e3ebdSchin {
238da2e3ebdSchin PTR ostate = (PTR) &state[-1];
239da2e3ebdSchin
240da2e3ebdSchin if (rand_type == TYPE_0)
241da2e3ebdSchin state[-1] = rand_type;
242da2e3ebdSchin else
243da2e3ebdSchin state[-1] = (MAX_TYPES * (rptr - state)) + rand_type;
244da2e3ebdSchin if (n < BREAK_1)
245da2e3ebdSchin {
246da2e3ebdSchin if (n < BREAK_0)
247da2e3ebdSchin {
248da2e3ebdSchin errno = EINVAL;
249da2e3ebdSchin return NULL;
250da2e3ebdSchin }
251da2e3ebdSchin rand_type = TYPE_0;
252da2e3ebdSchin rand_deg = DEG_0;
253da2e3ebdSchin rand_sep = SEP_0;
254da2e3ebdSchin }
255da2e3ebdSchin else if (n < BREAK_2)
256da2e3ebdSchin {
257da2e3ebdSchin rand_type = TYPE_1;
258da2e3ebdSchin rand_deg = DEG_1;
259da2e3ebdSchin rand_sep = SEP_1;
260da2e3ebdSchin }
261da2e3ebdSchin else if (n < BREAK_3)
262da2e3ebdSchin {
263da2e3ebdSchin rand_type = TYPE_2;
264da2e3ebdSchin rand_deg = DEG_2;
265da2e3ebdSchin rand_sep = SEP_2;
266da2e3ebdSchin }
267da2e3ebdSchin else if (n < BREAK_4)
268da2e3ebdSchin {
269da2e3ebdSchin rand_type = TYPE_3;
270da2e3ebdSchin rand_deg = DEG_3;
271da2e3ebdSchin rand_sep = SEP_3;
272da2e3ebdSchin }
273da2e3ebdSchin else
274da2e3ebdSchin {
275da2e3ebdSchin rand_type = TYPE_4;
276da2e3ebdSchin rand_deg = DEG_4;
277da2e3ebdSchin rand_sep = SEP_4;
278da2e3ebdSchin }
279da2e3ebdSchin
280da2e3ebdSchin state = &((long int *) arg_state)[1]; /* First location. */
281da2e3ebdSchin /* Must set END_PTR before srandom. */
282da2e3ebdSchin end_ptr = &state[rand_deg];
283da2e3ebdSchin srandom(seed);
284da2e3ebdSchin if (rand_type == TYPE_0)
285da2e3ebdSchin state[-1] = rand_type;
286da2e3ebdSchin else
287da2e3ebdSchin state[-1] = (MAX_TYPES * (rptr - state)) + rand_type;
288da2e3ebdSchin
289da2e3ebdSchin return ostate;
290da2e3ebdSchin }
291da2e3ebdSchin
292da2e3ebdSchin /* Restore the state from the given state array.
293da2e3ebdSchin Note: It is important that we also remember the locations of the pointers
294da2e3ebdSchin in the current state information, and restore the locations of the pointers
295da2e3ebdSchin from the old state information. This is done by multiplexing the pointer
296da2e3ebdSchin location into the zeroeth word of the state information. Note that due
297da2e3ebdSchin to the order in which things are done, it is OK to call setstate with the
298da2e3ebdSchin same state as the current state
299da2e3ebdSchin Returns a pointer to the old state information. */
setstate(const char * arg_state)300da2e3ebdSchin extern char *setstate(const char *arg_state)
301da2e3ebdSchin {
302da2e3ebdSchin register long int *new_state = (long int *) arg_state;
303da2e3ebdSchin register int type = new_state[0] % MAX_TYPES;
304da2e3ebdSchin register int rear = new_state[0] / MAX_TYPES;
305da2e3ebdSchin PTR ostate = (PTR) &state[-1];
306da2e3ebdSchin
307da2e3ebdSchin if (rand_type == TYPE_0)
308da2e3ebdSchin state[-1] = rand_type;
309da2e3ebdSchin else
310da2e3ebdSchin state[-1] = (MAX_TYPES * (rptr - state)) + rand_type;
311da2e3ebdSchin
312da2e3ebdSchin switch (type)
313da2e3ebdSchin {
314da2e3ebdSchin case TYPE_0:
315da2e3ebdSchin case TYPE_1:
316da2e3ebdSchin case TYPE_2:
317da2e3ebdSchin case TYPE_3:
318da2e3ebdSchin case TYPE_4:
319da2e3ebdSchin rand_type = type;
320da2e3ebdSchin rand_deg = degrees[type];
321da2e3ebdSchin rand_sep = seps[type];
322da2e3ebdSchin break;
323da2e3ebdSchin default:
324da2e3ebdSchin /* State info munged. */
325da2e3ebdSchin errno = EINVAL;
326da2e3ebdSchin return NULL;
327da2e3ebdSchin }
328da2e3ebdSchin
329da2e3ebdSchin state = &new_state[1];
330da2e3ebdSchin if (rand_type != TYPE_0)
331da2e3ebdSchin {
332da2e3ebdSchin rptr = &state[rear];
333da2e3ebdSchin fptr = &state[(rear + rand_sep) % rand_deg];
334da2e3ebdSchin }
335da2e3ebdSchin /* Set end_ptr too. */
336da2e3ebdSchin end_ptr = &state[rand_deg];
337da2e3ebdSchin
338da2e3ebdSchin return ostate;
339da2e3ebdSchin }
340da2e3ebdSchin
341da2e3ebdSchin /* If we are using the trivial TYPE_0 R.N.G., just do the old linear
342da2e3ebdSchin congruential bit. Otherwise, we do our fancy trinomial stuff, which is the
343da2e3ebdSchin same in all ther other cases due to all the global variables that have been
344da2e3ebdSchin set up. The basic operation is to add the number at the rear pointer into
345da2e3ebdSchin the one at the front pointer. Then both pointers are advanced to the next
346da2e3ebdSchin location cyclically in the table. The value returned is the sum generated,
347da2e3ebdSchin reduced to 31 bits by throwing away the "least random" low bit.
348da2e3ebdSchin Note: The code takes advantage of the fact that both the front and
349da2e3ebdSchin rear pointers can't wrap on the same call by not testing the rear
350da2e3ebdSchin pointer if the front one has wrapped. Returns a 31-bit random number. */
351da2e3ebdSchin
random()352da2e3ebdSchin extern long int random()
353da2e3ebdSchin {
354da2e3ebdSchin if (rand_type == TYPE_0)
355da2e3ebdSchin {
356da2e3ebdSchin state[0] = ((state[0] * 1103515245) + 12345) & LONG_MAX;
357da2e3ebdSchin return state[0];
358da2e3ebdSchin }
359da2e3ebdSchin else
360da2e3ebdSchin {
361da2e3ebdSchin long int i;
362da2e3ebdSchin *fptr += *rptr;
363da2e3ebdSchin /* Chucking least random bit. */
364da2e3ebdSchin i = (*fptr >> 1) & LONG_MAX;
365da2e3ebdSchin ++fptr;
366da2e3ebdSchin if (fptr >= end_ptr)
367da2e3ebdSchin {
368da2e3ebdSchin fptr = state;
369da2e3ebdSchin ++rptr;
370da2e3ebdSchin }
371da2e3ebdSchin else
372da2e3ebdSchin {
373da2e3ebdSchin ++rptr;
374da2e3ebdSchin if (rptr >= end_ptr)
375da2e3ebdSchin rptr = state;
376da2e3ebdSchin }
377da2e3ebdSchin return i;
378da2e3ebdSchin }
379da2e3ebdSchin }
380da2e3ebdSchin
381da2e3ebdSchin #endif
382