From 3ea2e82dc7b32703f5043c3b30b049905a0d07aa Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Fri, 9 Oct 2009 20:59:04 +0200 Subject: ash: factor out $RANDOM support function old new delta next_random - 46 +46 ash_main 1361 1356 -5 change_random 132 97 -35 ------------------------------------------------------------------------------ (add/remove: 1/0 grow/shrink: 0/2 up/down: 46/-40) Total: 6 bytes Signed-off-by: Denys Vlasenko --- shell/random.c | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100644 shell/random.c (limited to 'shell/random.c') diff --git a/shell/random.c b/shell/random.c new file mode 100644 index 000000000..a4dce846d --- /dev/null +++ b/shell/random.c @@ -0,0 +1,37 @@ +/* vi: set sw=4 ts=4: */ +/* + * $RANDOM support. + * + * Copyright (C) 2008 Denys Vlasenko + * + * Licensed under GPLv2, see file LICENSE in this tarball for details. + */ +#include "libbb.h" +#include "random.h" + +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: */ + /* MASK = 0x00400007 */ + + uint32_t t; + + /* LCG has period of 2^32 and alternating lowest bit */ + rnd->LCG = 1664525 * rnd->LCG + 1013904223; + /* Galois LFSR has period of 2^32-1 = 3 * 5 * 17 * 257 * 65537 */ + t = (rnd->galois_LFSR << 1); + if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */ + t ^= MASK; + rnd->galois_LFSR = t; + /* Both are weak, combining them gives better randomness + * and ~2^64 period. & 0x7fff is probably bash compat + * for $RANDOM range. Combining with subtraction is + * just for fun. + and ^ would work equally well. */ + t = (t - rnd->LCG) & 0x7fff; + + return t; +} -- cgit v1.2.3