/* vi: set sw=4 ts=4: */ /* * $RANDOM support. * * Copyright (C) 2009 Denys Vlasenko * * Licensed under GPLv2, see file LICENSE in this source tree. */ /* For testing against dieharder, you need only random.{c,h} * Howto: * gcc -O2 -Wall -DRANDTEST random.c -o random * ./random | dieharder -g 200 -a */ #if !defined RANDTEST # include "libbb.h" # include "random.h" # define RAND_BASH_MASK 0x7fff #else # include <stdint.h> # include <unistd.h> # include <stdio.h> # include <time.h> # define FAST_FUNC /* nothing */ # define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */ # define POP_SAVED_FUNCTION_VISIBILITY /* nothing */ # define monotonic_us() time(NULL) # include "random.h" # define RAND_BASH_MASK 0xffffffff /* off */ #endif uint32_t FAST_FUNC next_random(random_t *rnd) { /* Galois LFSR parameter: * Taps at 32 31 29 1: */ enum { MASK = 0x8000000b }; /* Another example - taps at 32 31 30 10: */ /* enum { MASK = 0x00400007 }; */ /* Xorshift parameters: * Choices for a,b,c: 10,13,10; 8,9,22; 2,7,3; 23,3,24 * (given by algorithm author) */ enum { a = 2, b = 7, c = 3, }; uint32_t t; if (UNINITED_RANDOM_T(rnd)) { /* Can use monotonic_ns() for better randomness but for now * it is not used anywhere else in busybox... so avoid bloat */ INIT_RANDOM_T(rnd, getpid(), monotonic_us()); } /* LCG: period of 2^32, but quite weak: * bit 0 alternates beetween 0 and 1 (pattern of length 2) * bit 1 has a repeating pattern of length 4 * bit 2 has a repeating pattern of length 8 * etc... */ rnd->LCG = 1664525 * rnd->LCG + 1013904223; /* Galois LFSR: * period of 2^32-1 = 3 * 5 * 17 * 257 * 65537. * Successive values are right-shifted one bit * and possibly xored with a sparse constant. */ t = (rnd->galois_LFSR << 1); if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */ t ^= MASK; rnd->galois_LFSR = t; /* http://en.wikipedia.org/wiki/Xorshift * Moderately good statistical properties: * fails the following "dieharder -g 200 -a" tests: * diehard_operm5| 0 * diehard_oqso| 0 * diehard_count_1s_byt| 0 * diehard_3dsphere| 3 * diehard_squeeze| 0 * diehard_runs| 0 * diehard_runs| 0 * diehard_craps| 0 * diehard_craps| 0 * rgb_minimum_distance| 3 * rgb_minimum_distance| 4 * rgb_minimum_distance| 5 * rgb_permutations| 3 * rgb_permutations| 4 * rgb_permutations| 5 * dab_filltree| 32 * dab_filltree| 32 * dab_monobit2| 12 */ again: t = rnd->xs64_x ^ (rnd->xs64_x << a); rnd->xs64_x = rnd->xs64_y; rnd->xs64_y = rnd->xs64_y ^ (rnd->xs64_y >> c) ^ t ^ (t >> b); /* * Period 2^64-1 = 2^32+1 * 2^32-1 has a common divisor with Galois LFSR. * By skipping two possible states (0x1 and 0x2) we reduce period to * 2^64-3 = 13 * 3889 * 364870227143809 which has no common divisors: */ if (rnd->xs64_y == 0 && rnd->xs64_x <= 2) goto again; /* Combined LCG + Galois LFSR rng has 2^32 * 2^32-1 period. * Strength: * individually, both are extremely weak cryptographycally; * when combined, they fail the following "dieharder -g 200 -a" tests: * diehard_rank_6x8| 0 * diehard_oqso| 0 * diehard_dna| 0 * diehard_count_1s_byt| 0 * rgb_bitdist| 2 * dab_monobit2| 12 * * Combining them with xorshift-64 increases period to * 2^32 * 2^32-1 * 2^64-3 * which is about 2^128, or in base 10 ~3.40*10^38. * Strength of the combination: * passes all "dieharder -g 200 -a" tests. * * Combining with subtraction and addition is just for fun. * It does not add meaningful strength, could use xor operation instead. */ t = rnd->galois_LFSR - rnd->LCG + rnd->xs64_y; /* bash compat $RANDOM range: */ return t & RAND_BASH_MASK; } #ifdef RANDTEST static random_t rnd; int main(int argc, char **argv) { int i; uint32_t buf[4096]; for (;;) { for (i = 0; i < sizeof(buf) / sizeof(buf[0]); i++) { buf[i] = next_random(&rnd); } write(1, buf, sizeof(buf)); } return 0; } #endif