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
  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
  35uint32_t FAST_FUNC
  36next_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
 143static random_t rnd;
 144
 145int 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
 161