lib/random_r.c

   1 /*
   2    Copyright (C) 1995-2021 Free Software Foundation, Inc.
   3
   4    The GNU C Library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Lesser General Public
   6    License as published by the Free Software Foundation; either
   7    version 2.1 of the License, or (at your option) any later version.
   8
   9    The GNU C Library is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public
  15    License along with the GNU C Library; if not, see
  16    <https://www.gnu.org/licenses/>.  */
  17
  18 /*
  19    Copyright (C) 1983 Regents of the University of California.
  20    All rights reserved.
  21
  22    Redistribution and use in source and binary forms, with or without
  23    modification, are permitted provided that the following conditions
  24    are met:
  25
  26    1. Redistributions of source code must retain the above copyright
  27       notice, this list of conditions and the following disclaimer.
  28    2. Redistributions in binary form must reproduce the above copyright
  29       notice, this list of conditions and the following disclaimer in the
  30       documentation and/or other materials provided with the distribution.
  31    4. Neither the name of the University nor the names of its contributors
  32       may be used to endorse or promote products derived from this software
  33       without specific prior written permission.
  34
  35    THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND
  36    ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  37    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  38    ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  39    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  40    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  41    OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  42    HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  43    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  44    OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  45    SUCH DAMAGE.*/
  46
  47 /*
  48  * This is derived from the Berkeley source:
  49  *      @(#)random.c    5.5 (Berkeley) 7/6/88
  50  * It was reworked for the GNU C Library by Roland McGrath.
  51  * Rewritten to be reentrant by Ulrich Drepper, 1995
  52  */
  53
  54 #ifndef _LIBC
  55 /* Don't use __attribute__ __nonnull__ in this compilation unit.  Otherwise gcc
  56    optimizes away the buf == NULL, arg_state == NULL, result == NULL tests
  57    below.  */
  58 # define _GL_ARG_NONNULL(params)
  59
  60 # include <libc-config.h>
  61 # define __srandom_r srandom_r
  62 # define __initstate_r initstate_r
  63 # define __setstate_r setstate_r
  64 # define __random_r random_r
  65 #endif
  66
  67 /* Specification.  */
  68 #include <stdlib.h>
  69
  70 #include <errno.h>
  71 #include <stddef.h>
  72 #include <string.h>
  73
  74
  75 /* An improved random number generation package.  In addition to the standard
  76    rand()/srand() like interface, this package also has a special state info
  77    interface.  The initstate() routine is called with a seed, an array of
  78    bytes, and a count of how many bytes are being passed in; this array is
  79    then initialized to contain information for random number generation with
  80    that much state information.  Good sizes for the amount of state
  81    information are 32, 64, 128, and 256 bytes.  The state can be switched by
  82    calling the setstate() function with the same array as was initialized
  83    with initstate().  By default, the package runs with 128 bytes of state
  84    information and generates far better random numbers than a linear
  85    congruential generator.  If the amount of state information is less than
  86    32 bytes, a simple linear congruential R.N.G. is used.  Internally, the
  87    state information is treated as an array of longs; the zeroth element of
  88    the array is the type of R.N.G. being used (small integer); the remainder
  89    of the array is the state information for the R.N.G.  Thus, 32 bytes of
  90    state information will give 7 longs worth of state information, which will
  91    allow a degree seven polynomial.  (Note: The zeroth word of state
  92    information also has some other information stored in it; see setstate
  93    for details).  The random number generation technique is a linear feedback
  94    shift register approach, employing trinomials (since there are fewer terms
  95    to sum up that way).  In this approach, the least significant bit of all
  96    the numbers in the state table will act as a linear feedback shift register,
  97    and will have period 2^deg - 1 (where deg is the degree of the polynomial
  98    being used, assuming that the polynomial is irreducible and primitive).
  99    The higher order bits will have longer periods, since their values are
 100    also influenced by pseudo-random carries out of the lower bits.  The
 101    total period of the generator is approximately deg*(2**deg - 1); thus
 102    doubling the amount of state information has a vast influence on the
 103    period of the generator.  Note: The deg*(2**deg - 1) is an approximation
 104    only good for large deg, when the period of the shift register is the
 105    dominant factor.  With deg equal to seven, the period is actually much
 106    longer than the 7*(2**7 - 1) predicted by this formula.  */
 107
 108
 109
 110 /* For each of the currently supported random number generators, we have a
 111    break value on the amount of state information (you need at least this many
 112    bytes of state info to support this random number generator), a degree for
 113    the polynomial (actually a trinomial) that the R.N.G. is based on, and
 114    separation between the two lower order coefficients of the trinomial.  */
 115
 116 /* Linear congruential.  */
 117 #define TYPE_0          0
 118 #define BREAK_0         8
 119 #define DEG_0           0
 120 #define SEP_0           0
 121
 122 /* x**7 + x**3 + 1.  */
 123 #define TYPE_1          1
 124 #define BREAK_1         32
 125 #define DEG_1           7
 126 #define SEP_1           3
 127
 128 /* x**15 + x + 1.  */
 129 #define TYPE_2          2
 130 #define BREAK_2         64
 131 #define DEG_2           15
 132 #define SEP_2           1
 133
 134 /* x**31 + x**3 + 1.  */
 135 #define TYPE_3          3
 136 #define BREAK_3         128
 137 #define DEG_3           31
 138 #define SEP_3           3
 139
 140 /* x**63 + x + 1.  */
 141 #define TYPE_4          4
 142 #define BREAK_4         256
 143 #define DEG_4           63
 144 #define SEP_4           1
 145
 146
 147 /* Array versions of the above information to make code run faster.
 148    Relies on fact that TYPE_i == i.  */
 149
 150 #define MAX_TYPES       5       /* Max number of types above.  */
 151
 152 struct random_poly_info
 153 {
 154   int seps[MAX_TYPES];
 155   int degrees[MAX_TYPES];
 156 };
 157
 158 static const struct random_poly_info random_poly_info =
 159 {
 160   { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 },
 161   { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }
 162 };
 163
 164 static int32_t
 165 get_int32 (void *p)
 166 {
 167   int32_t v;
 168   memcpy (&v, p, sizeof v);
 169   return v;
 170 }
 171
 172 static void
 173 set_int32 (void *p, int32_t v)
 174 {
 175   memcpy (p, &v, sizeof v);
 176 }
 177
 178 \f
 179 /* Initialize the random number generator based on the given seed.  If the
 180    type is the trivial no-state-information type, just remember the seed.
 181    Otherwise, initializes state[] based on the given "seed" via a linear
 182    congruential generator.  Then, the pointers are set to known locations
 183    that are exactly rand_sep places apart.  Lastly, it cycles the state
 184    information a given number of times to get rid of any initial dependencies
 185    introduced by the L.C.R.N.G.  Note that the initialization of randtbl[]
 186    for default usage relies on values produced by this routine.  */
 187 int
 188 __srandom_r (unsigned int seed, struct random_data *buf)
 189 {
 190   int type;
 191   int32_t *state;
 192   long int i;
 193   int32_t word;
 194   int32_t *dst;
 195   int kc;
 196
 197   if (buf == NULL)
 198     goto fail;
 199   type = buf->rand_type;
 200   if ((unsigned int) type >= MAX_TYPES)
 201     goto fail;
 202
 203   state = buf->state;
 204   /* We must make sure the seed is not 0.  Take arbitrarily 1 in this case.  */
 205   if (seed == 0)
 206     seed = 1;
 207   set_int32 (&state[0], seed);
 208   if (type == TYPE_0)
 209     goto done;
 210
 211   dst = state;
 212   word = seed;
 213   kc = buf->rand_deg;
 214   for (i = 1; i < kc; ++i)
 215     {
 216       /* This does:
 217            state[i] = (16807 * state[i - 1]) % 2147483647;
 218          but avoids overflowing 31 bits.  */
 219       long int hi = word / 127773;
 220       long int lo = word % 127773;
 221       word = 16807 * lo - 2836 * hi;
 222       if (word < 0)
 223         word += 2147483647;
 224       set_int32 (++dst, word);
 225     }
 226
 227   buf->fptr = &state[buf->rand_sep];
 228   buf->rptr = &state[0];
 229   kc *= 10;
 230   while (--kc >= 0)
 231     {
 232       int32_t discard;
 233       (void) __random_r (buf, &discard);
 234     }
 235
 236  done:
 237   return 0;
 238
 239  fail:
 240   return -1;
 241 }
 242
 243 weak_alias (__srandom_r, srandom_r)
 244 \f
 245 /* Initialize the state information in the given array of N bytes for
 246    future random number generation.  Based on the number of bytes we
 247    are given, and the break values for the different R.N.G.'s, we choose
 248    the best (largest) one we can and set things up for it.  srandom is
 249    then called to initialize the state information.  Note that on return
 250    from srandom, we set state[-1] to be the type multiplexed with the current
 251    value of the rear pointer; this is so successive calls to initstate won't
 252    lose this information and will be able to restart with setstate.
 253    Note: The first thing we do is save the current state, if any, just like
 254    setstate so that it doesn't matter when initstate is called.
 255    Returns 0 on success, non-zero on failure.  */
 256 int
 257 __initstate_r (unsigned int seed, char *arg_state, size_t n,
 258                struct random_data *buf)
 259 {
 260   if (buf == NULL)
 261     goto fail;
 262
 263   int32_t *old_state = buf->state;
 264   if (old_state != NULL)
 265     {
 266       int old_type = buf->rand_type;
 267       set_int32 (&old_state[-1],
 268                  (old_type == TYPE_0
 269                   ? TYPE_0
 270                   : (MAX_TYPES * (buf->rptr - old_state)) + old_type));
 271     }
 272
 273   int type;
 274   if (n >= BREAK_3)
 275     type = n < BREAK_4 ? TYPE_3 : TYPE_4;
 276   else if (n < BREAK_1)
 277     {
 278       if (n < BREAK_0)
 279         goto fail;
 280
 281       type = TYPE_0;
 282     }
 283   else
 284     type = n < BREAK_2 ? TYPE_1 : TYPE_2;
 285
 286   int degree = random_poly_info.degrees[type];
 287   int separation = random_poly_info.seps[type];
 288
 289   buf->rand_type = type;
 290   buf->rand_sep = separation;
 291   buf->rand_deg = degree;
 292   int32_t *state = &((int32_t *) arg_state)[1]; /* First location.  */
 293   /* Must set END_PTR before srandom.  */
 294   buf->end_ptr = &state[degree];
 295
 296   buf->state = state;
 297
 298   __srandom_r (seed, buf);
 299
 300   set_int32 (&state[-1],
 301              type == TYPE_0 ? TYPE_0 : (buf->rptr - state) * MAX_TYPES + type);
 302
 303   return 0;
 304
 305  fail:
 306   __set_errno (EINVAL);
 307   return -1;
 308 }
 309
 310 weak_alias (__initstate_r, initstate_r)
 311 \f
 312 /* Restore the state from the given state array.
 313    Note: It is important that we also remember the locations of the pointers
 314    in the current state information, and restore the locations of the pointers
 315    from the old state information.  This is done by multiplexing the pointer
 316    location into the zeroth word of the state information. Note that due
 317    to the order in which things are done, it is OK to call setstate with the
 318    same state as the current state
 319    Returns 0 on success, non-zero on failure.  */
 320 int
 321 __setstate_r (char *arg_state, struct random_data *buf)
 322 {
 323   int32_t *new_state = 1 + (int32_t *) arg_state;
 324   int type;
 325   int old_type;
 326   int32_t *old_state;
 327   int degree;
 328   int separation;
 329
 330   if (arg_state == NULL || buf == NULL)
 331     goto fail;
 332
 333   old_type = buf->rand_type;
 334   old_state = buf->state;
 335   set_int32 (&old_state[-1],
 336              (old_type == TYPE_0
 337               ? TYPE_0
 338               : (MAX_TYPES * (buf->rptr - old_state)) + old_type));
 339
 340   type = get_int32 (&new_state[-1]) % MAX_TYPES;
 341   if (type < TYPE_0 || type > TYPE_4)
 342     goto fail;
 343
 344   buf->rand_deg = degree = random_poly_info.degrees[type];
 345   buf->rand_sep = separation = random_poly_info.seps[type];
 346   buf->rand_type = type;
 347
 348   if (type != TYPE_0)
 349     {
 350       int rear = get_int32 (&new_state[-1]) / MAX_TYPES;
 351       buf->rptr = &new_state[rear];
 352       buf->fptr = &new_state[(rear + separation) % degree];
 353     }
 354   buf->state = new_state;
 355   /* Set end_ptr too.  */
 356   buf->end_ptr = &new_state[degree];
 357
 358   return 0;
 359
 360  fail:
 361   __set_errno (EINVAL);
 362   return -1;
 363 }
 364
 365 weak_alias (__setstate_r, setstate_r)
 366 \f
 367 /* If we are using the trivial TYPE_0 R.N.G., just do the old linear
 368    congruential bit.  Otherwise, we do our fancy trinomial stuff, which is the
 369    same in all the other cases due to all the global variables that have been
 370    set up.  The basic operation is to add the number at the rear pointer into
 371    the one at the front pointer.  Then both pointers are advanced to the next
 372    location cyclically in the table.  The value returned is the sum generated,
 373    reduced to 31 bits by throwing away the "least random" low bit.
 374    Note: The code takes advantage of the fact that both the front and
 375    rear pointers can't wrap on the same call by not testing the rear
 376    pointer if the front one has wrapped.  Returns a 31-bit random number.  */
 377
 378 int
 379 __random_r (struct random_data *buf, int32_t *result)
 380 {
 381   int32_t *state;
 382
 383   if (buf == NULL || result == NULL)
 384     goto fail;
 385
 386   state = buf->state;
 387
 388   if (buf->rand_type == TYPE_0)
 389     {
 390       int32_t val = (((get_int32 (&state[0]) * 1103515245U) + 12345U)
 391                      & 0x7fffffff);
 392       set_int32 (&state[0], val);
 393       *result = val;
 394     }
 395   else
 396     {
 397       int32_t *fptr = buf->fptr;
 398       int32_t *rptr = buf->rptr;
 399       int32_t *end_ptr = buf->end_ptr;
 400       /* F and R are unsigned int, not uint32_t, to avoid undefined
 401          overflow behavior on platforms where INT_MAX == UINT32_MAX.  */
 402       unsigned int f = get_int32 (fptr);
 403       unsigned int r = get_int32 (rptr);
 404       uint32_t val = f + r;
 405       set_int32 (fptr, val);
 406       /* Chucking least random bit.  */
 407       *result = val >> 1;
 408       ++fptr;
 409       if (fptr >= end_ptr)
 410         {
 411           fptr = state;
 412           ++rptr;
 413         }
 414       else
 415         {
 416           ++rptr;
 417           if (rptr >= end_ptr)
 418             rptr = state;
 419         }
 420       buf->fptr = fptr;
 421       buf->rptr = rptr;
 422     }
 423   return 0;
 424
 425  fail:
 426   __set_errno (EINVAL);
 427   return -1;
 428 }
 429
 430 weak_alias (__random_r, random_r)