shell/random.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * $RANDOM support.
   4  *
   5  * Copyright (C) 2009 Denys Vlasenko
   6  *
   7  * Licensed under GPLv2, see file LICENSE in this tarball for details.
   8  */
   9 #include "libbb.h"
  10 #include "random.h"
  11
  12 uint32_t FAST_FUNC
  13 next_random(random_t *rnd)
  14 {
  15         /* Galois LFSR parameter */
  16         /* Taps at 32 31 29 1: */
  17         enum { MASK = 0x8000000b };
  18         /* Another example - taps at 32 31 30 10: */
  19         /* MASK = 0x00400007 */
  20
  21         uint32_t t;
  22
  23         /* LCG has period of 2^32 and alternating lowest bit */
  24         rnd->LCG = 1664525 * rnd->LCG + 1013904223;
  25         /* Galois LFSR has period of 2^32-1 = 3 * 5 * 17 * 257 * 65537 */
  26         t = (rnd->galois_LFSR << 1);
  27         if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */
  28                 t ^= MASK;
  29         rnd->galois_LFSR = t;
  30         /* Both are weak, combining them gives better randomness
  31          * and ~2^64 period. & 0x7fff is probably bash compat
  32          * for $RANDOM range. Combining with subtraction is
  33          * just for fun. + and ^ would work equally well. */
  34         t = (t - rnd->LCG) & 0x7fff;
  35
  36         return t;
  37 }