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