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
  10 /* For testing against dieharder, you need only random.{c,h}
  11  * Howto:
  12  * gcc -O2 -Wall -DRANDTEST random.c -o random
  13  * ./random | dieharder -g 200 -a
  14  */
  15
  16 #if !defined RANDTEST
  17
  18 # include "libbb.h"
  19 # include "random.h"
  20 # define RAND_BASH_MASK 0x7fff
  21
  22 #else
  23 # include <stdint.h>
  24 # include <unistd.h>
  25 # include <stdio.h>
  26 # include <time.h>
  27 # define FAST_FUNC /* nothing */
  28 # define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */
  29 # define POP_SAVED_FUNCTION_VISIBILITY /* nothing */
  30 # define monotonic_us() time(NULL)
  31 # include "random.h"
  32 # define RAND_BASH_MASK 0xffffffff /* off */
  33 #endif
  34
  35 uint32_t FAST_FUNC
  36 next_random(random_t *rnd)
  37 {
  38         /* Galois LFSR parameter:
  39          * Taps at 32 31 29 1:
  40          */
  41         enum { MASK = 0x8000000b };
  42         /* Another example - taps at 32 31 30 10: */
  43         /* enum { MASK = 0x00400007 }; */
  44
  45         /* Xorshift parameters:
  46          * Choices for a,b,c: 10,13,10; 8,9,22; 2,7,3; 23,3,24
  47          * (given by algorithm author)
  48          */
  49         enum {
  50                 a = 2,
  51                 b = 7,
  52                 c = 3,
  53         };
  54
  55         uint32_t t;
  56
  57         if (UNINITED_RANDOM_T(rnd)) {
  58                 /* Can use monotonic_ns() for better randomness but for now
  59                  * it is not used anywhere else in busybox... so avoid bloat
  60                  */
  61                 INIT_RANDOM_T(rnd, getpid(), monotonic_us());
  62         }
  63
  64         /* LCG: period of 2^32, but quite weak:
  65          * bit 0 alternates beetween 0 and 1 (pattern of length 2)
  66          * bit 1 has a repeating pattern of length 4
  67          * bit 2 has a repeating pattern of length 8
  68          * etc...
  69          */
  70         rnd->LCG = 1664525 * rnd->LCG + 1013904223;
  71
  72         /* Galois LFSR:
  73          * period of 2^32-1 = 3 * 5 * 17 * 257 * 65537.
  74          * Successive values are right-shifted one bit
  75          * and possibly xored with a sparse constant.
  76          */
  77         t = (rnd->galois_LFSR << 1);
  78         if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */
  79                 t ^= MASK;
  80         rnd->galois_LFSR = t;
  81
  82         /* http://en.wikipedia.org/wiki/Xorshift
  83          * Period 2^64-1 = 3 * 715827883 * 2147483647
  84          * Moderately good statistical properties:
  85          * fails the following "dieharder -g 200 -a" tests:
  86          *       diehard_operm5|   0
  87          *         diehard_oqso|   0
  88          * diehard_count_1s_byt|   0
  89          *     diehard_3dsphere|   3
  90          *      diehard_squeeze|   0
  91          *         diehard_runs|   0
  92          *         diehard_runs|   0
  93          *        diehard_craps|   0
  94          *        diehard_craps|   0
  95          * rgb_minimum_distance|   3
  96          * rgb_minimum_distance|   4
  97          * rgb_minimum_distance|   5
  98          *     rgb_permutations|   3
  99          *     rgb_permutations|   4
 100          *     rgb_permutations|   5
 101          *         dab_filltree|  32
 102          *         dab_filltree|  32
 103          *         dab_monobit2|  12
 104          */
 105         t = rnd->xs64_x ^ (rnd->xs64_x << a);
 106         rnd->xs64_x = rnd->xs64_y;
 107         rnd->xs64_y = rnd->xs64_y ^ (rnd->xs64_y >> c) ^ t ^ (t >> b);
 108
 109         /* Combined LCG + Galois LFSR have 2^32 * 2^32-1 period.
 110          * Strength:
 111          * individually, both are extremely weak cryptographycally;
 112          * when combined, they fail the following "dieharder -g 200 -a" tests:
 113          *     diehard_rank_6x8|   0
 114          *         diehard_oqso|   0
 115          *          diehard_dna|   0
 116          * diehard_count_1s_byt|   0
 117          *          rgb_bitdist|   2
 118          *         dab_monobit2|  12
 119          *
 120          * Combining them with xorshift-64 increases period to
 121          * 2^32 * 2^32-1 * 2^64-1 / 3
 122          * (2^32-1 and 2^64-1 have one common divisor 3, hence "/ 3" part),
 123          * which is about 2^128 / 3, or in base 10 ~1.13*10^38.
 124          * Strength of the combination:
 125          * passes all "dieharder -g 200 -a" tests.
 126          *
 127          * Combining with subtraction and addition is just for fun.
 128          * It does not add meaningful strength, could use xor operation instead.
 129          */
 130         t = rnd->galois_LFSR - rnd->LCG + rnd->xs64_y;
 131
 132         /* bash compat $RANDOM range: */
 133         return t & RAND_BASH_MASK;
 134 }
 135
 136 #ifdef RANDTEST
 137 static random_t rnd;
 138
 139 int main(int argc, char **argv)
 140 {
 141         int i;
 142         uint32_t buf[4096];
 143
 144         for (;;) {
 145                 for (i = 0; i < sizeof(buf) / sizeof(buf[0]); i++) {
 146                         buf[i] = next_random(&rnd);
 147                 }
 148                 write(1, buf, sizeof(buf));
 149         }
 150
 151         return 0;
 152 }
 153
 154 #endif