1 #include "FEATURE/uwin" 2 3 #if !_UWIN || _lib_random 4 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. */ 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. */ 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. */ 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 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