LXR busybox/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 source tree.
   8 */
   9#include "libbb.h"
  10#include "random.h"
  11
  12uint32_t FAST_FUNC
  13next_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        if (UNINITED_RANDOM_T(rnd)) {
  24                /* Can use monotonic_ns() for better randomness but for now
  25                 * it is not used anywhere else in busybox... so avoid bloat
  26                 */
  27                INIT_RANDOM_T(rnd, getpid(), monotonic_us());
  28        }
  29
  30        /* LCG has period of 2^32 and alternating lowest bit */
  31        rnd->LCG = 1664525 * rnd->LCG + 1013904223;
  32        /* Galois LFSR has period of 2^32-1 = 3 * 5 * 17 * 257 * 65537 */
  33        t = (rnd->galois_LFSR << 1);
  34        if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */
  35                t ^= MASK;
  36        rnd->galois_LFSR = t;
  37        /* Both are weak, combining them gives better randomness
  38         * and ~2^64 period. & 0x7fff is probably bash compat
  39         * for $RANDOM range. Combining with subtraction is
  40         * just for fun. + and ^ would work equally well. */
  41        t = (t - rnd->LCG) & 0x7fff;
  42
  43        return t;
  44}
  45