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          * Moderately good statistical properties:
  84          * fails the following "dieharder -g 200 -a" tests:
  85          *       diehard_operm5|   0
  86          *         diehard_oqso|   0
  87          * diehard_count_1s_byt|   0
  88          *     diehard_3dsphere|   3
  89          *      diehard_squeeze|   0
  90          *         diehard_runs|   0
  91          *         diehard_runs|   0
  92          *        diehard_craps|   0
  93          *        diehard_craps|   0
  94          * rgb_minimum_distance|   3
  95          * rgb_minimum_distance|   4
  96          * rgb_minimum_distance|   5
  97          *     rgb_permutations|   3
  98          *     rgb_permutations|   4
  99          *     rgb_permutations|   5
 100          *         dab_filltree|  32
 101          *         dab_filltree|  32
 102          *         dab_monobit2|  12
 103          */
 104  again:
 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          * Period 2^64-1 = 2^32+1 * 2^32-1 has a common divisor with Galois LFSR.
 110          * By skipping two possible states (0x1 and 0x2) we reduce period to
 111          * 2^64-3 = 13 * 3889 * 364870227143809 which has no common divisors:
 112          */
 113         if (rnd->xs64_y == 0 && rnd->xs64_x <= 2)
 114                 goto again;
 115
 116         /* Combined LCG + Galois LFSR rng has 2^32 * 2^32-1 period.
 117          * Strength:
 118          * individually, both are extremely weak cryptographycally;
 119          * when combined, they fail the following "dieharder -g 200 -a" tests:
 120          *     diehard_rank_6x8|   0
 121          *         diehard_oqso|   0
 122          *          diehard_dna|   0
 123          * diehard_count_1s_byt|   0
 124          *          rgb_bitdist|   2
 125          *         dab_monobit2|  12
 126          *
 127          * Combining them with xorshift-64 increases period to
 128          * 2^32 * 2^32-1 * 2^64-3
 129          * which is about 2^128, or in base 10 ~3.40*10^38.
 130          * Strength of the combination:
 131          * passes all "dieharder -g 200 -a" tests.
 132          *
 133          * Combining with subtraction and addition is just for fun.
 134          * It does not add meaningful strength, could use xor operation instead.
 135          */
 136         t = rnd->galois_LFSR - rnd->LCG + rnd->xs64_y;
 137
 138         /* bash compat $RANDOM range: */
 139         return t & RAND_BASH_MASK;
 140 }
 141
 142 #ifdef RANDTEST
 143 static random_t rnd;
 144
 145 int main(int argc, char **argv)
 146 {
 147         int i;
 148         uint32_t buf[4096];
 149
 150         for (;;) {
 151                 for (i = 0; i < sizeof(buf) / sizeof(buf[0]); i++) {
 152                         buf[i] = next_random(&rnd);
 153                 }
 154                 write(1, buf, sizeof(buf));
 155         }
 156
 157         return 0;
 158 }
 159
 160 #endif