libc/stdlib/random_r.c

   1 /*
   2  * Copyright (c) 1983 Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms are permitted
   6  * provided that the above copyright notice and this paragraph are
   7  * duplicated in all such forms and that any documentation,
   8  * advertising materials, and other materials related to such
   9  * distribution and use acknowledge that the software was developed
  10  * by the University of California, Berkeley.  The name of the
  11  * University may not be used to endorse or promote products derived
  12  * from this software without specific prior written permission.
  13  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  14  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  15  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  16  */
  17
  18 /*
  19  * This is derived from the Berkeley source:
  20  *      @(#)random.c    5.5 (Berkeley) 7/6/88
  21  * It was reworked for the GNU C Library by Roland McGrath.
  22  * Rewritten to be reentrant by Ulrich Drepper, 1995
  23  */
  24
  25 #include <features.h>
  26 #include <errno.h>
  27 #include <limits.h>
  28 #include <stddef.h>
  29 #include <stdlib.h>
  30 #include <unistd.h>
  31
  32 /* An improved random number generation package.  In addition to the standard
  33    rand()/srand() like interface, this package also has a special state info
  34    interface.  The initstate() routine is called with a seed, an array of
  35    bytes, and a count of how many bytes are being passed in; this array is
  36    then initialized to contain information for random number generation with
  37    that much state information.  Good sizes for the amount of state
  38    information are 32, 64, 128, and 256 bytes.  The state can be switched by
  39    calling the setstate() function with the same array as was initialized
  40    with initstate().  By default, the package runs with 128 bytes of state
  41    information and generates far better random numbers than a linear
  42    congruential generator.  If the amount of state information is less than
  43    32 bytes, a simple linear congruential R.N.G. is used.  Internally, the
  44    state information is treated as an array of longs; the zeroth element of
  45    the array is the type of R.N.G. being used (small integer); the remainder
  46    of the array is the state information for the R.N.G.  Thus, 32 bytes of
  47    state information will give 7 longs worth of state information, which will
  48    allow a degree seven polynomial.  (Note: The zeroth word of state
  49    information also has some other information stored in it; see setstate
  50    for details).  The random number generation technique is a linear feedback
  51    shift register approach, employing trinomials (since there are fewer terms
  52    to sum up that way).  In this approach, the least significant bit of all
  53    the numbers in the state table will act as a linear feedback shift register,
  54    and will have period 2^deg - 1 (where deg is the degree of the polynomial
  55    being used, assuming that the polynomial is irreducible and primitive).
  56    The higher order bits will have longer periods, since their values are
  57    also influenced by pseudo-random carries out of the lower bits.  The
  58    total period of the generator is approximately deg*(2**deg - 1); thus
  59    doubling the amount of state information has a vast influence on the
  60    period of the generator.  Note: The deg*(2**deg - 1) is an approximation
  61    only good for large deg, when the period of the shift register is the
  62    dominant factor.  With deg equal to seven, the period is actually much
  63    longer than the 7*(2**7 - 1) predicted by this formula.  */
  64
  65
  66
  67 /* For each of the currently supported random number generators, we have a
  68    break value on the amount of state information (you need at least this many
  69    bytes of state info to support this random number generator), a degree for
  70    the polynomial (actually a trinomial) that the R.N.G. is based on, and
  71    separation between the two lower order coefficients of the trinomial.  */
  72
  73 /* Linear congruential.  */
  74 #define TYPE_0          0
  75 #define BREAK_0         8
  76 #define DEG_0           0
  77 #define SEP_0           0
  78
  79 /* x**7 + x**3 + 1.  */
  80 #define TYPE_1          1
  81 #define BREAK_1         32
  82 #define DEG_1           7
  83 #define SEP_1           3
  84
  85 /* x**15 + x + 1.  */
  86 #define TYPE_2          2
  87 #define BREAK_2         64
  88 #define DEG_2           15
  89 #define SEP_2           1
  90
  91 /* x**31 + x**3 + 1.  */
  92 #define TYPE_3          3
  93 #define BREAK_3         128
  94 #define DEG_3           31
  95 #define SEP_3           3
  96
  97 /* x**63 + x + 1.  */
  98 #define TYPE_4          4
  99 #define BREAK_4         256
 100 #define DEG_4           63
 101 #define SEP_4           1
 102
 103
 104 /* Array versions of the above information to make code run faster.
 105    Relies on fact that TYPE_i == i.  */
 106
 107 #define MAX_TYPES       5       /* Max number of types above.  */
 108
 109 struct random_poly_info
 110 {
 111     smallint seps[MAX_TYPES];
 112     smallint degrees[MAX_TYPES];
 113 };
 114
 115 static const struct random_poly_info random_poly_info =
 116 {
 117     { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 },
 118     { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }
 119 };
 120
 121
 122
 123 /* If we are using the trivial TYPE_0 R.N.G., just do the old linear
 124    congruential bit.  Otherwise, we do our fancy trinomial stuff, which is the
 125    same in all the other cases due to all the global variables that have been
 126    set up.  The basic operation is to add the number at the rear pointer into
 127    the one at the front pointer.  Then both pointers are advanced to the next
 128    location cyclically in the table.  The value returned is the sum generated,
 129    reduced to 31 bits by throwing away the "least random" low bit.
 130    Note: The code takes advantage of the fact that both the front and
 131    rear pointers can't wrap on the same call by not testing the rear
 132    pointer if the front one has wrapped.  Returns a 31-bit random number.  */
 133
 134 int random_r(struct random_data *buf, int32_t *result)
 135 {
 136     int32_t *state;
 137
 138     if (buf == NULL || result == NULL)
 139         goto fail;
 140
 141     state = buf->state;
 142
 143     if (buf->rand_type == TYPE_0)
 144     {
 145         int32_t val = state[0];
 146         val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
 147         state[0] = val;
 148         *result = val;
 149     }
 150     else
 151     {
 152         int32_t *fptr = buf->fptr;
 153         int32_t *rptr = buf->rptr;
 154         int32_t *end_ptr = buf->end_ptr;
 155         int32_t val;
 156
 157         val = *fptr += *rptr;
 158         /* Chucking least random bit.  */
 159         *result = (val >> 1) & 0x7fffffff;
 160         ++fptr;
 161         if (fptr >= end_ptr)
 162         {
 163             fptr = state;
 164             ++rptr;
 165         }
 166         else
 167         {
 168             ++rptr;
 169             if (rptr >= end_ptr)
 170                 rptr = state;
 171         }
 172         buf->fptr = fptr;
 173         buf->rptr = rptr;
 174     }
 175     return 0;
 176
 177 fail:
 178     __set_errno (EINVAL);
 179     return -1;
 180 }
 181 libc_hidden_def(random_r)
 182
 183 /* Initialize the random number generator based on the given seed.  If the
 184    type is the trivial no-state-information type, just remember the seed.
 185    Otherwise, initializes state[] based on the given "seed" via a linear
 186    congruential generator.  Then, the pointers are set to known locations
 187    that are exactly rand_sep places apart.  Lastly, it cycles the state
 188    information a given number of times to get rid of any initial dependencies
 189    introduced by the L.C.R.N.G.  Note that the initialization of randtbl[]
 190    for default usage relies on values produced by this routine.  */
 191 int srandom_r (unsigned int seed, struct random_data *buf)
 192 {
 193     int type;
 194     int32_t *state;
 195     long int i;
 196     long int word;
 197     int32_t *dst;
 198     int kc;
 199
 200     if (buf == NULL)
 201         goto fail;
 202     type = buf->rand_type;
 203     if ((unsigned int) type >= MAX_TYPES)
 204         goto fail;
 205
 206     state = buf->state;
 207     /* We must make sure the seed is not 0.  Take arbitrarily 1 in this case.  */
 208     if (seed == 0)
 209         seed = 1;
 210     state[0] = seed;
 211     if (type == TYPE_0)
 212         goto done;
 213
 214     dst = state;
 215     word = seed;
 216     kc = buf->rand_deg;
 217     for (i = 1; i < kc; ++i)
 218     {
 219         /* This does:
 220            state[i] = (16807 * state[i - 1]) % 2147483647;
 221            but avoids overflowing 31 bits.  */
 222         long int hi = word / 127773;
 223         long int lo = word % 127773;
 224         word = 16807 * lo - 2836 * hi;
 225         if (word < 0)
 226             word += 2147483647;
 227         *++dst = word;
 228     }
 229
 230     buf->fptr = &state[buf->rand_sep];
 231     buf->rptr = &state[0];
 232     kc *= 10;
 233     while (--kc >= 0)
 234     {
 235         int32_t discard;
 236         (void) random_r (buf, &discard);
 237     }
 238
 239 done:
 240     return 0;
 241
 242 fail:
 243     return -1;
 244 }
 245 libc_hidden_def(srandom_r)
 246
 247 /* Initialize the state information in the given array of N bytes for
 248    future random number generation.  Based on the number of bytes we
 249    are given, and the break values for the different R.N.G.'s, we choose
 250    the best (largest) one we can and set things up for it.  srandom is
 251    then called to initialize the state information.  Note that on return
 252    from srandom, we set state[-1] to be the type multiplexed with the current
 253    value of the rear pointer; this is so successive calls to initstate won't
 254    lose this information and will be able to restart with setstate.
 255    Note: The first thing we do is save the current state, if any, just like
 256    setstate so that it doesn't matter when initstate is called.
 257    Returns a pointer to the old state.  */
 258 int initstate_r (unsigned int seed, char *arg_state, size_t n, struct random_data *buf)
 259 {
 260     int type;
 261     int degree;
 262     int separation;
 263     int32_t *state;
 264
 265     if (buf == NULL)
 266         goto fail;
 267
 268     if (n >= BREAK_3)
 269         type = n < BREAK_4 ? TYPE_3 : TYPE_4;
 270     else if (n < BREAK_1)
 271     {
 272         if (n < BREAK_0)
 273         {
 274             __set_errno (EINVAL);
 275             goto fail;
 276         }
 277         type = TYPE_0;
 278     }
 279     else
 280         type = n < BREAK_2 ? TYPE_1 : TYPE_2;
 281
 282     degree = random_poly_info.degrees[type];
 283     separation = random_poly_info.seps[type];
 284
 285     buf->rand_type = type;
 286     buf->rand_sep = separation;
 287     buf->rand_deg = degree;
 288     state = &((int32_t *) arg_state)[1];        /* First location.  */
 289     /* Must set END_PTR before srandom.  */
 290     buf->end_ptr = &state[degree];
 291
 292     buf->state = state;
 293
 294     srandom_r (seed, buf);
 295
 296     state[-1] = TYPE_0;
 297     if (type != TYPE_0)
 298         state[-1] = (buf->rptr - state) * MAX_TYPES + type;
 299
 300     return 0;
 301
 302 fail:
 303     __set_errno (EINVAL);
 304     return -1;
 305 }
 306 libc_hidden_def(initstate_r)
 307
 308 /* Restore the state from the given state array.
 309    Note: It is important that we also remember the locations of the pointers
 310    in the current state information, and restore the locations of the pointers
 311    from the old state information.  This is done by multiplexing the pointer
 312    location into the zeroth word of the state information. Note that due
 313    to the order in which things are done, it is OK to call setstate with the
 314    same state as the current state
 315    Returns a pointer to the old state information.  */
 316 int setstate_r (char *arg_state, struct random_data *buf)
 317 {
 318     int32_t *new_state = 1 + (int32_t *) arg_state;
 319     int type;
 320     int old_type;
 321     int32_t *old_state;
 322     int degree;
 323     int separation;
 324
 325     if (arg_state == NULL || buf == NULL)
 326         goto fail;
 327
 328     old_type = buf->rand_type;
 329     old_state = buf->state;
 330     if (old_type == TYPE_0)
 331         old_state[-1] = TYPE_0;
 332     else
 333         old_state[-1] = (MAX_TYPES * (buf->rptr - old_state)) + old_type;
 334
 335     type = new_state[-1] % MAX_TYPES;
 336     if (type < TYPE_0 || type > TYPE_4)
 337         goto fail;
 338
 339     buf->rand_deg = degree = random_poly_info.degrees[type];
 340     buf->rand_sep = separation = random_poly_info.seps[type];
 341     buf->rand_type = type;
 342
 343     if (type != TYPE_0)
 344     {
 345         int rear = new_state[-1] / MAX_TYPES;
 346         buf->rptr = &new_state[rear];
 347         buf->fptr = &new_state[(rear + separation) % degree];
 348     }
 349     buf->state = new_state;
 350     /* Set end_ptr too.  */
 351     buf->end_ptr = &new_state[degree];
 352
 353     return 0;
 354
 355 fail:
 356     __set_errno (EINVAL);
 357     return -1;
 358 }
 359 libc_hidden_def(setstate_r)