1169695Skan/* 2169695Skan * Copyright (c) 1983 Regents of the University of California. 3169695Skan * All rights reserved. 4169695Skan * 5169695Skan * Redistribution and use in source and binary forms, with or without 6169695Skan * modification, are permitted provided that the following conditions 7169695Skan * are met: 8169695Skan * 1. Redistributions of source code must retain the above copyright 9169695Skan * notice, this list of conditions and the following disclaimer. 10169695Skan * 2. Redistributions in binary form must reproduce the above copyright 11169695Skan * notice, this list of conditions and the following disclaimer in the 12169695Skan * documentation and/or other materials provided with the distribution. 13169695Skan * 3. [rescinded 22 July 1999] 14169695Skan * 4. Neither the name of the University nor the names of its contributors 15169695Skan * may be used to endorse or promote products derived from this software 16169695Skan * without specific prior written permission. 17169695Skan * 18169695Skan * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 19169695Skan * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20169695Skan * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21169695Skan * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 22169695Skan * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23169695Skan * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24169695Skan * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25169695Skan * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26169695Skan * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27169695Skan * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28169695Skan * SUCH DAMAGE. 29169695Skan */ 30169695Skan 31169695Skan/* 32169695Skan * This is derived from the Berkeley source: 33169695Skan * @(#)random.c 5.5 (Berkeley) 7/6/88 34169695Skan * It was reworked for the GNU C Library by Roland McGrath. 35169695Skan */ 36169695Skan 37169695Skan/* 38169695Skan 39169695Skan@deftypefn Supplement {long int} random (void) 40169695Skan@deftypefnx Supplement void srandom (unsigned int @var{seed}) 41169695Skan@deftypefnx Supplement void* initstate (unsigned int @var{seed}, void *@var{arg_state}, unsigned long @var{n}) 42169695Skan@deftypefnx Supplement void* setstate (void *@var{arg_state}) 43169695Skan 44169695SkanRandom number functions. @code{random} returns a random number in the 45169695Skanrange 0 to @code{LONG_MAX}. @code{srandom} initializes the random 46169695Skannumber generator to some starting point determined by @var{seed} 47169695Skan(else, the values returned by @code{random} are always the same for each 48169695Skanrun of the program). @code{initstate} and @code{setstate} allow fine-grained 49169695Skancontrol over the state of the random number generator. 50169695Skan 51169695Skan@end deftypefn 52169695Skan 53169695Skan*/ 54169695Skan 55169695Skan#include <errno.h> 56169695Skan 57169695Skan#if 0 58169695Skan 59169695Skan#include <ansidecl.h> 60169695Skan#include <limits.h> 61169695Skan#include <stddef.h> 62169695Skan#include <stdlib.h> 63169695Skan 64169695Skan#else 65169695Skan 66169695Skan#define ULONG_MAX ((unsigned long)(~0L)) /* 0xFFFFFFFF for 32-bits */ 67169695Skan#define LONG_MAX ((long)(ULONG_MAX >> 1)) /* 0x7FFFFFFF for 32-bits*/ 68169695Skan 69169695Skan#ifdef __STDC__ 70169695Skan# define PTR void * 71169695Skan# ifndef NULL 72169695Skan# define NULL (void *) 0 73169695Skan# endif 74169695Skan#else 75169695Skan# define PTR char * 76169695Skan# ifndef NULL 77169695Skan# define NULL (void *) 0 78169695Skan# endif 79169695Skan#endif 80169695Skan 81169695Skan#endif 82169695Skan 83169695Skanlong int random (void); 84169695Skan 85169695Skan/* An improved random number generation package. In addition to the standard 86169695Skan rand()/srand() like interface, this package also has a special state info 87169695Skan interface. The initstate() routine is called with a seed, an array of 88169695Skan bytes, and a count of how many bytes are being passed in; this array is 89169695Skan then initialized to contain information for random number generation with 90169695Skan that much state information. Good sizes for the amount of state 91169695Skan information are 32, 64, 128, and 256 bytes. The state can be switched by 92169695Skan calling the setstate() function with the same array as was initiallized 93169695Skan with initstate(). By default, the package runs with 128 bytes of state 94169695Skan information and generates far better random numbers than a linear 95169695Skan congruential generator. If the amount of state information is less than 96169695Skan 32 bytes, a simple linear congruential R.N.G. is used. Internally, the 97169695Skan state information is treated as an array of longs; the zeroeth element of 98169695Skan the array is the type of R.N.G. being used (small integer); the remainder 99169695Skan of the array is the state information for the R.N.G. Thus, 32 bytes of 100169695Skan state information will give 7 longs worth of state information, which will 101169695Skan allow a degree seven polynomial. (Note: The zeroeth word of state 102169695Skan information also has some other information stored in it; see setstate 103169695Skan for details). The random number generation technique is a linear feedback 104169695Skan shift register approach, employing trinomials (since there are fewer terms 105169695Skan to sum up that way). In this approach, the least significant bit of all 106169695Skan the numbers in the state table will act as a linear feedback shift register, 107169695Skan and will have period 2^deg - 1 (where deg is the degree of the polynomial 108169695Skan being used, assuming that the polynomial is irreducible and primitive). 109169695Skan The higher order bits will have longer periods, since their values are 110169695Skan also influenced by pseudo-random carries out of the lower bits. The 111169695Skan total period of the generator is approximately deg*(2**deg - 1); thus 112169695Skan doubling the amount of state information has a vast influence on the 113169695Skan period of the generator. Note: The deg*(2**deg - 1) is an approximation 114169695Skan only good for large deg, when the period of the shift register is the 115169695Skan dominant factor. With deg equal to seven, the period is actually much 116169695Skan longer than the 7*(2**7 - 1) predicted by this formula. */ 117169695Skan 118169695Skan 119169695Skan 120169695Skan/* For each of the currently supported random number generators, we have a 121169695Skan break value on the amount of state information (you need at least thi 122169695Skan bytes of state info to support this random number generator), a degree for 123169695Skan the polynomial (actually a trinomial) that the R.N.G. is based on, and 124169695Skan separation between the two lower order coefficients of the trinomial. */ 125169695Skan 126169695Skan/* Linear congruential. */ 127169695Skan#define TYPE_0 0 128169695Skan#define BREAK_0 8 129169695Skan#define DEG_0 0 130169695Skan#define SEP_0 0 131169695Skan 132169695Skan/* x**7 + x**3 + 1. */ 133169695Skan#define TYPE_1 1 134169695Skan#define BREAK_1 32 135169695Skan#define DEG_1 7 136169695Skan#define SEP_1 3 137169695Skan 138169695Skan/* x**15 + x + 1. */ 139169695Skan#define TYPE_2 2 140169695Skan#define BREAK_2 64 141169695Skan#define DEG_2 15 142169695Skan#define SEP_2 1 143169695Skan 144169695Skan/* x**31 + x**3 + 1. */ 145169695Skan#define TYPE_3 3 146169695Skan#define BREAK_3 128 147169695Skan#define DEG_3 31 148169695Skan#define SEP_3 3 149169695Skan 150169695Skan/* x**63 + x + 1. */ 151169695Skan#define TYPE_4 4 152169695Skan#define BREAK_4 256 153169695Skan#define DEG_4 63 154169695Skan#define SEP_4 1 155169695Skan 156169695Skan 157169695Skan/* Array versions of the above information to make code run faster. 158169695Skan Relies on fact that TYPE_i == i. */ 159169695Skan 160169695Skan#define MAX_TYPES 5 /* Max number of types above. */ 161169695Skan 162169695Skanstatic int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; 163169695Skanstatic int seps[MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; 164169695Skan 165169695Skan 166169695Skan 167169695Skan/* Initially, everything is set up as if from: 168169695Skan initstate(1, randtbl, 128); 169169695Skan Note that this initialization takes advantage of the fact that srandom 170169695Skan advances the front and rear pointers 10*rand_deg times, and hence the 171169695Skan rear pointer which starts at 0 will also end up at zero; thus the zeroeth 172169695Skan element of the state information, which contains info about the current 173169695Skan position of the rear pointer is just 174169695Skan (MAX_TYPES * (rptr - state)) + TYPE_3 == TYPE_3. */ 175169695Skan 176169695Skanstatic long int randtbl[DEG_3 + 1] = 177169695Skan { TYPE_3, 178169695Skan 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 179169695Skan 0xde3b81e0, 0xdf0a6fb5, 0xf103bc02, 0x48f340fb, 180169695Skan 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd, 181169695Skan 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, 182169695Skan 0xda672e2a, 0x1588ca88, 0xe369735d, 0x904f35f7, 183169695Skan 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc, 184169695Skan 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 185169695Skan 0xf5ad9d0e, 0x8999220b, 0x27fb47b9 186169695Skan }; 187169695Skan 188169695Skan/* FPTR and RPTR are two pointers into the state info, a front and a rear 189169695Skan pointer. These two pointers are always rand_sep places aparts, as they 190169695Skan cycle through the state information. (Yes, this does mean we could get 191169695Skan away with just one pointer, but the code for random is more efficient 192169695Skan this way). The pointers are left positioned as they would be from the call: 193169695Skan initstate(1, randtbl, 128); 194169695Skan (The position of the rear pointer, rptr, is really 0 (as explained above 195169695Skan in the initialization of randtbl) because the state table pointer is set 196169695Skan to point to randtbl[1] (as explained below).) */ 197169695Skan 198169695Skanstatic long int *fptr = &randtbl[SEP_3 + 1]; 199169695Skanstatic long int *rptr = &randtbl[1]; 200169695Skan 201169695Skan 202169695Skan 203169695Skan/* The following things are the pointer to the state information table, 204169695Skan the type of the current generator, the degree of the current polynomial 205169695Skan being used, and the separation between the two pointers. 206169695Skan Note that for efficiency of random, we remember the first location of 207169695Skan the state information, not the zeroeth. Hence it is valid to access 208169695Skan state[-1], which is used to store the type of the R.N.G. 209169695Skan Also, we remember the last location, since this is more efficient than 210169695Skan indexing every time to find the address of the last element to see if 211169695Skan the front and rear pointers have wrapped. */ 212169695Skan 213169695Skanstatic long int *state = &randtbl[1]; 214169695Skan 215169695Skanstatic int rand_type = TYPE_3; 216169695Skanstatic int rand_deg = DEG_3; 217169695Skanstatic int rand_sep = SEP_3; 218169695Skan 219169695Skanstatic long int *end_ptr = &randtbl[sizeof(randtbl) / sizeof(randtbl[0])]; 220169695Skan 221169695Skan/* Initialize the random number generator based on the given seed. If the 222169695Skan type is the trivial no-state-information type, just remember the seed. 223169695Skan Otherwise, initializes state[] based on the given "seed" via a linear 224169695Skan congruential generator. Then, the pointers are set to known locations 225169695Skan that are exactly rand_sep places apart. Lastly, it cycles the state 226169695Skan information a given number of times to get rid of any initial dependencies 227169695Skan introduced by the L.C.R.N.G. Note that the initialization of randtbl[] 228169695Skan for default usage relies on values produced by this routine. */ 229169695Skanvoid 230169695Skansrandom (unsigned int x) 231169695Skan{ 232169695Skan state[0] = x; 233169695Skan if (rand_type != TYPE_0) 234169695Skan { 235169695Skan register long int i; 236169695Skan for (i = 1; i < rand_deg; ++i) 237169695Skan state[i] = (1103515145 * state[i - 1]) + 12345; 238169695Skan fptr = &state[rand_sep]; 239169695Skan rptr = &state[0]; 240169695Skan for (i = 0; i < 10 * rand_deg; ++i) 241169695Skan random(); 242169695Skan } 243169695Skan} 244169695Skan 245169695Skan/* Initialize the state information in the given array of N bytes for 246169695Skan future random number generation. Based on the number of bytes we 247169695Skan are given, and the break values for the different R.N.G.'s, we choose 248169695Skan the best (largest) one we can and set things up for it. srandom is 249169695Skan then called to initialize the state information. Note that on return 250169695Skan from srandom, we set state[-1] to be the type multiplexed with the current 251169695Skan value of the rear pointer; this is so successive calls to initstate won't 252169695Skan lose this information and will be able to restart with setstate. 253169695Skan Note: The first thing we do is save the current state, if any, just like 254169695Skan setstate so that it doesn't matter when initstate is called. 255169695Skan Returns a pointer to the old state. */ 256169695SkanPTR 257169695Skaninitstate (unsigned int seed, PTR arg_state, unsigned long n) 258169695Skan{ 259169695Skan PTR ostate = (PTR) &state[-1]; 260169695Skan 261169695Skan if (rand_type == TYPE_0) 262169695Skan state[-1] = rand_type; 263169695Skan else 264169695Skan state[-1] = (MAX_TYPES * (rptr - state)) + rand_type; 265169695Skan if (n < BREAK_1) 266169695Skan { 267169695Skan if (n < BREAK_0) 268169695Skan { 269169695Skan errno = EINVAL; 270169695Skan return NULL; 271169695Skan } 272169695Skan rand_type = TYPE_0; 273169695Skan rand_deg = DEG_0; 274169695Skan rand_sep = SEP_0; 275169695Skan } 276169695Skan else if (n < BREAK_2) 277169695Skan { 278169695Skan rand_type = TYPE_1; 279169695Skan rand_deg = DEG_1; 280169695Skan rand_sep = SEP_1; 281169695Skan } 282169695Skan else if (n < BREAK_3) 283169695Skan { 284169695Skan rand_type = TYPE_2; 285169695Skan rand_deg = DEG_2; 286169695Skan rand_sep = SEP_2; 287169695Skan } 288169695Skan else if (n < BREAK_4) 289169695Skan { 290169695Skan rand_type = TYPE_3; 291169695Skan rand_deg = DEG_3; 292169695Skan rand_sep = SEP_3; 293169695Skan } 294169695Skan else 295169695Skan { 296169695Skan rand_type = TYPE_4; 297169695Skan rand_deg = DEG_4; 298169695Skan rand_sep = SEP_4; 299169695Skan } 300169695Skan 301169695Skan state = &((long int *) arg_state)[1]; /* First location. */ 302169695Skan /* Must set END_PTR before srandom. */ 303169695Skan end_ptr = &state[rand_deg]; 304169695Skan srandom(seed); 305169695Skan if (rand_type == TYPE_0) 306169695Skan state[-1] = rand_type; 307169695Skan else 308169695Skan state[-1] = (MAX_TYPES * (rptr - state)) + rand_type; 309169695Skan 310169695Skan return ostate; 311169695Skan} 312169695Skan 313169695Skan/* Restore the state from the given state array. 314169695Skan Note: It is important that we also remember the locations of the pointers 315169695Skan in the current state information, and restore the locations of the pointers 316169695Skan from the old state information. This is done by multiplexing the pointer 317169695Skan location into the zeroeth word of the state information. Note that due 318169695Skan to the order in which things are done, it is OK to call setstate with the 319169695Skan same state as the current state 320169695Skan Returns a pointer to the old state information. */ 321169695Skan 322169695SkanPTR 323169695Skansetstate (PTR arg_state) 324169695Skan{ 325169695Skan register long int *new_state = (long int *) arg_state; 326169695Skan register int type = new_state[0] % MAX_TYPES; 327169695Skan register int rear = new_state[0] / MAX_TYPES; 328169695Skan PTR ostate = (PTR) &state[-1]; 329169695Skan 330169695Skan if (rand_type == TYPE_0) 331169695Skan state[-1] = rand_type; 332169695Skan else 333169695Skan state[-1] = (MAX_TYPES * (rptr - state)) + rand_type; 334169695Skan 335169695Skan switch (type) 336169695Skan { 337169695Skan case TYPE_0: 338169695Skan case TYPE_1: 339169695Skan case TYPE_2: 340169695Skan case TYPE_3: 341169695Skan case TYPE_4: 342169695Skan rand_type = type; 343169695Skan rand_deg = degrees[type]; 344169695Skan rand_sep = seps[type]; 345169695Skan break; 346169695Skan default: 347169695Skan /* State info munged. */ 348169695Skan errno = EINVAL; 349169695Skan return NULL; 350169695Skan } 351169695Skan 352169695Skan state = &new_state[1]; 353169695Skan if (rand_type != TYPE_0) 354169695Skan { 355169695Skan rptr = &state[rear]; 356169695Skan fptr = &state[(rear + rand_sep) % rand_deg]; 357169695Skan } 358169695Skan /* Set end_ptr too. */ 359169695Skan end_ptr = &state[rand_deg]; 360169695Skan 361169695Skan return ostate; 362169695Skan} 363169695Skan 364169695Skan/* If we are using the trivial TYPE_0 R.N.G., just do the old linear 365169695Skan congruential bit. Otherwise, we do our fancy trinomial stuff, which is the 366169695Skan same in all ther other cases due to all the global variables that have been 367169695Skan set up. The basic operation is to add the number at the rear pointer into 368169695Skan the one at the front pointer. Then both pointers are advanced to the next 369169695Skan location cyclically in the table. The value returned is the sum generated, 370169695Skan reduced to 31 bits by throwing away the "least random" low bit. 371169695Skan Note: The code takes advantage of the fact that both the front and 372169695Skan rear pointers can't wrap on the same call by not testing the rear 373169695Skan pointer if the front one has wrapped. Returns a 31-bit random number. */ 374169695Skan 375169695Skanlong int 376169695Skanrandom (void) 377169695Skan{ 378169695Skan if (rand_type == TYPE_0) 379169695Skan { 380169695Skan state[0] = ((state[0] * 1103515245) + 12345) & LONG_MAX; 381169695Skan return state[0]; 382169695Skan } 383169695Skan else 384169695Skan { 385169695Skan long int i; 386169695Skan *fptr += *rptr; 387169695Skan /* Chucking least random bit. */ 388169695Skan i = (*fptr >> 1) & LONG_MAX; 389169695Skan ++fptr; 390169695Skan if (fptr >= end_ptr) 391169695Skan { 392169695Skan fptr = state; 393169695Skan ++rptr; 394169695Skan } 395169695Skan else 396169695Skan { 397169695Skan ++rptr; 398169695Skan if (rptr >= end_ptr) 399169695Skan rptr = state; 400169695Skan } 401169695Skan return i; 402169695Skan } 403169695Skan} 404