/* 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 |