Back to index

kdeartwork  4.3.2
vm_random.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 1983 Regents of the University of California.
00003  * All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms are permitted
00006  * provided that the above copyright notice and this paragraph are
00007  * duplicated in all such forms and that any documentation,
00008  * advertising materials, and other materials related to such
00009  * distribution and use acknowledge that the software was developed
00010  * by the University of California, Berkeley.  The name of the
00011  * University may not be used to endorse or promote products derived
00012  * from this software without specific prior written permission.
00013  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
00014  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
00015  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00016  */
00017 
00018 /*
00019  * Please note that as of July 22, 1999, the licensees and distributors
00020  * are no longer required to include the above mentioned acknowledgement
00021  * within advertising materials. For full details see
00022  * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
00023  */
00024 
00025 /*
00026  * This is derived from the Berkeley source:
00027  *     @(#)random.c  5.5 (Berkeley) 7/6/88
00028  * It was reworked for the GNU C Library by Roland McGrath.
00029  * Rewritten to be reentrant by Ulrich Drepper, 1995
00030  */
00031 
00032 #include <limits.h>
00033 #include <stdlib.h>
00034 #include "vm_random.h"
00035 
00036 /* An improved random number generation package.  In addition to the standard
00037    rand()/srand() like interface, this package also has a special state info
00038    interface.  The initstate() routine is called with a seed, an array of
00039    bytes, and a count of how many bytes are being passed in; this array is
00040    then initialized to contain information for random number generation with
00041    that much state information.  Good sizes for the amount of state
00042    information are 32, 64, 128, and 256 bytes.  The state can be switched by
00043    calling the setstate() function with the same array as was initialized
00044    with initstate().  By default, the package runs with 128 bytes of state
00045    information and generates far better random numbers than a linear
00046    congruential generator.  If the amount of state information is less than
00047    32 bytes, a simple linear congruential R.N.G. is used.  Internally, the
00048    state information is treated as an array of longs; the zeroth element of
00049    the array is the type of R.N.G. being used (small integer); the remainder
00050    of the array is the state information for the R.N.G.  Thus, 32 bytes of
00051    state information will give 7 longs worth of state information, which will
00052    allow a degree seven polynomial.  (Note: The zeroth word of state
00053    information also has some other information stored in it; see setstate
00054    for details).  The random number generation technique is a linear feedback
00055    shift register approach, employing trinomials (since there are fewer terms
00056    to sum up that way).  In this approach, the least significant bit of all
00057    the numbers in the state table will act as a linear feedback shift register,
00058    and will have period 2^deg - 1 (where deg is the degree of the polynomial
00059    being used, assuming that the polynomial is irreducible and primitive).
00060    The higher order bits will have longer periods, since their values are
00061    also influenced by pseudo-random carries out of the lower bits.  The
00062    total period of the generator is approximately deg*(2**deg - 1); thus
00063    doubling the amount of state information has a vast influence on the
00064    period of the generator.  Note: The deg*(2**deg - 1) is an approximation
00065    only good for large deg, when the period of the shift register is the
00066    dominant factor.  With deg equal to seven, the period is actually much
00067    longer than the 7*(2**7 - 1) predicted by this formula.  */
00068 
00069 
00070 
00071 /* For each of the currently supported random number generators, we have a
00072    break value on the amount of state information (you need at least this many
00073    bytes of state info to support this random number generator), a degree for
00074    the polynomial (actually a trinomial) that the R.N.G. is based on, and
00075    separation between the two lower order coefficients of the trinomial.  */
00076 
00077 /* Linear congruential.  */
00078 #define       TYPE_0        0
00079 #define       BREAK_0              8
00080 #define       DEG_0         0
00081 #define       SEP_0         0
00082 
00083 /* x**7 + x**3 + 1.  */
00084 #define       TYPE_1        1
00085 #define       BREAK_1              32
00086 #define       DEG_1         7
00087 #define       SEP_1         3
00088 
00089 /* x**15 + x + 1.  */
00090 #define       TYPE_2        2
00091 #define       BREAK_2              64
00092 #define       DEG_2         15
00093 #define       SEP_2         1
00094 
00095 /* x**31 + x**3 + 1.  */
00096 #define       TYPE_3        3
00097 #define       BREAK_3              128
00098 #define       DEG_3         31
00099 #define       SEP_3         3
00100 
00101 /* x**63 + x + 1.  */
00102 #define       TYPE_4        4
00103 #define       BREAK_4              256
00104 #define       DEG_4         63
00105 #define       SEP_4         1
00106 
00107 
00108 /* Array versions of the above information to make code run faster.
00109    Relies on fact that TYPE_i == i.  */
00110 
00111 #define       MAX_TYPES     5      /* Max number of types above.  */
00112 
00113 struct vm_random_poly_info
00114 {
00115   int seps[MAX_TYPES];
00116   int degrees[MAX_TYPES];
00117 };
00118 
00119 static struct vm_random_poly_info vm_random_poly_info =
00120 {
00121   { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 },
00122   { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }
00123 };
00124 
00125 static int32_t vm_randtbl[DEG_3 + 1] =
00126   {
00127       TYPE_3,
00128       
00129       -1726662223, 379960547, 1735697613, 1040273694, 1313901226,
00130       1627687941, -179304937, -2073333483, 1780058412, -1989503057,
00131       -615974602, 344556628, 939512070, -1249116260, 1507946756,
00132       -812545463, 154635395, 1388815473, -1926676823, 525320961,
00133       -1009028674, 968117788, -123449607, 1284210865, 435012392,
00134       -2017506339, -911064859, -370259173, 1132637927, 1398500161,
00135       -205601318,
00136   };
00137                                     
00138 /* Initialize the random number generator based on the given seed.  If the
00139    type is the trivial no-state-information type, just remember the seed.
00140    Otherwise, initializes state[] based on the given "seed" via a linear
00141    congruential generator.  Then, the pointers are set to known locations
00142    that are exactly rand_sep places apart.  Lastly, it cycles the state
00143    information a given number of times to get rid of any initial dependencies
00144    introduced by the L.C.R.N.G.  Note that the initialization of randtbl[]
00145    for default usage relies on values produced by this routine.  */
00146 int vm_srandom (unsigned int seed, 
00147                 struct vm_random_data* buf)
00148 {
00149   int type;
00150   int32_t *state;
00151   long int i;
00152   long int word;
00153   int32_t *dst;
00154   int kc;
00155 
00156   if (buf == NULL)
00157     goto fail;
00158   type = buf->vm_rand_type;
00159   if ((unsigned int) type >= MAX_TYPES)
00160     goto fail;
00161 
00162   state = buf->state;
00163   /* We must make sure the seed is not 0.  Take arbitrarily 1 in this case.  */
00164   if (seed == 0)
00165     seed = 1;
00166   state[0] = seed;
00167   if (type == TYPE_0)
00168     goto done;
00169 
00170   dst = state;
00171   word = seed;
00172   kc = buf->vm_rand_deg;
00173   for (i = 1; i < kc; ++i)
00174     {
00175       /* This does:
00176           state[i] = (16807 * state[i - 1]) % 2147483647;
00177         but avoids overflowing 31 bits.  */
00178       long int hi = word / 127773;
00179       long int lo = word % 127773;
00180       word = 16807 * lo - 2836 * hi;
00181       if (word < 0)
00182        word += 2147483647;
00183       *++dst = word;
00184     }
00185 
00186   buf->fptr = &state[buf->vm_rand_sep];
00187   buf->rptr = &state[0];
00188   kc *= 10;
00189   while (--kc >= 0)
00190     {
00191       vm_random (buf);
00192     }
00193 
00194  done:
00195   return 0;
00196 
00197  fail:
00198   return -1;
00199 }
00200 
00201 /* Initialize the state information in the given array of N bytes for
00202    future random number generation.  Based on the number of bytes we
00203    are given, and the break values for the different R.N.G.'s, we choose
00204    the best (largest) one we can and set things up for it.  srandom is
00205    then called to initialize the state information.  Note that on return
00206    from srandom, we set state[-1] to be the type multiplexed with the current
00207    value of the rear pointer; this is so successive calls to initstate won't
00208    lose this information and will be able to restart with setstate.
00209    Note: The first thing we do is save the current state, if any, just like
00210    setstate so that it doesn't matter when initstate is called.
00211    Returns a pointer to the old state.  */
00212 int vm_initstate (unsigned int seed, 
00213                   void* arg_state, 
00214                   size_t n, 
00215                   struct vm_random_data* buf)
00216 {
00217   int type;
00218   int degree;
00219   int separation;
00220   int32_t *state;
00221 
00222   if (buf == NULL)
00223     goto fail;
00224 
00225   if (n >= BREAK_3)
00226     type = n < BREAK_4 ? TYPE_3 : TYPE_4;
00227   else if (n < BREAK_1)
00228     {
00229       if (n < BREAK_0)
00230        {
00231          goto fail;
00232        }
00233       type = TYPE_0;
00234     }
00235   else
00236     type = n < BREAK_2 ? TYPE_1 : TYPE_2;
00237 
00238   degree = vm_random_poly_info.degrees[type];
00239   separation = vm_random_poly_info.seps[type];
00240 
00241   buf->vm_rand_type = type;
00242   buf->vm_rand_sep = separation;
00243   buf->vm_rand_deg = degree;
00244   state = &((int32_t *) arg_state)[1];    /* First location.  */
00245   /* Must set END_PTR before srandom.  */
00246   buf->end_ptr = &state[degree];
00247 
00248   buf->state = state;
00249 
00250   vm_srandom (seed, buf);
00251 
00252   state[-1] = TYPE_0;
00253   if (type != TYPE_0)
00254     state[-1] = (buf->rptr - state) * MAX_TYPES + type;
00255 
00256   return 0;
00257 
00258  fail:
00259   return -1;
00260 }
00261 
00262 /* Restore the state from the given state array.
00263    Note: It is important that we also remember the locations of the pointers
00264    in the current state information, and restore the locations of the pointers
00265    from the old state information.  This is done by multiplexing the pointer
00266    location into the zeroth word of the state information. Note that due
00267    to the order in which things are done, it is OK to call setstate with the
00268    same state as the current state
00269    Returns a pointer to the old state information.  */
00270 int vm_setstate (void* arg_state, 
00271                  struct vm_random_data* buf)
00272 {
00273   int32_t *new_state = (int32_t *) arg_state;
00274   int type;
00275   int old_type;
00276   int32_t *old_state;
00277   int degree;
00278   int separation;
00279 
00280   if (buf == NULL)
00281     goto fail;
00282 
00283   old_type = buf->vm_rand_type;
00284   old_state = buf->state;
00285   if (old_type == TYPE_0)
00286     old_state[-1] = TYPE_0;
00287   else
00288     old_state[-1] = (MAX_TYPES * (buf->rptr - old_state)) + old_type;
00289 
00290   type = new_state[0] % MAX_TYPES;
00291   if (type < TYPE_0 || type >= TYPE_4)
00292     goto fail;
00293 
00294   buf->vm_rand_deg = degree = vm_random_poly_info.degrees[type];
00295   buf->vm_rand_sep = separation = vm_random_poly_info.seps[type];
00296   buf->vm_rand_type = type;
00297 
00298   if (type != TYPE_0)
00299     {
00300       int rear = new_state[0] / MAX_TYPES;
00301       buf->rptr = &new_state[rear];
00302       buf->fptr = &new_state[(rear + separation) % degree];
00303     }
00304   buf->state = &new_state[1];
00305   /* Set end_ptr too.  */
00306   buf->end_ptr = &new_state[degree];
00307 
00308   return 0;
00309 
00310  fail:
00311   return -1;
00312 }
00313 
00314 /* If we are using the trivial TYPE_0 R.N.G., just do the old linear
00315    congruential bit.  Otherwise, we do our fancy trinomial stuff, which is the
00316    same in all the other cases due to all the global variables that have been
00317    set up.  The basic operation is to add the number at the rear pointer into
00318    the one at the front pointer.  Then both pointers are advanced to the next
00319    location cyclically in the table.  The value returned is the sum generated,
00320    reduced to 31 bits by throwing away the "least random" low bit.
00321    Note: The code takes advantage of the fact that both the front and
00322    rear pointers can't wrap on the same call by not testing the rear
00323    pointer if the front one has wrapped.  Returns a 31-bit random number.  */
00324 
00325 int32_t vm_random (struct vm_random_data* buf)
00326 {
00327   int32_t *state;
00328   int32_t result;
00329 
00330   if (buf == NULL)
00331     goto fail;
00332 
00333   state = buf->state;
00334 
00335   if (buf->vm_rand_type == TYPE_0)
00336     {
00337       int32_t val = state[0];
00338       val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
00339       state[0] = val;
00340       result = val;
00341     }
00342   else
00343     {
00344       int32_t *fptr = buf->fptr;
00345       int32_t *rptr = buf->rptr;
00346       int32_t *end_ptr = buf->end_ptr;
00347       int32_t val;
00348 
00349       val = *fptr += *rptr;
00350       /* Chucking least random bit.  */
00351       result = (val >> 1) & 0x7fffffff;
00352       ++fptr;
00353       if (fptr >= end_ptr)
00354        {
00355          fptr = state;
00356          ++rptr;
00357        }
00358       else
00359        {
00360          ++rptr;
00361          if (rptr >= end_ptr)
00362            rptr = state;
00363        }
00364       buf->fptr = fptr;
00365       buf->rptr = rptr;
00366     }
00367   return result;
00368 
00369  fail:
00370   return -1;
00371 }
00372 
00373 void vm_default_initstate( int seed,
00374                            struct vm_random_data* buf ) {
00375  vm_initstate( seed,
00376                vm_randtbl,
00377                128,
00378                buf );
00379 }