[git commit] ash,hush: fix a thinko about 2^64-1 factorization

[Denys Vlasenko]

commit: http://git.busybox.net/busybox/commit/?id=ac03a40cbac4545909b6529d358c253f8a6d3b45
branch: http://git.busybox.net/busybox/commit/?id=refs/heads/master

function                                             old     new   delta
next_random                                          113     119      +6

Signed-off-by: Denys Vlasenko <vda.linux at googlemail.com>
---
 shell/random.c |   16 +++++++++++-----
 1 files changed, 11 insertions(+), 5 deletions(-)

diff --git a/shell/random.c b/shell/random.c
index fc2dfc2..5d36205 100644
--- a/shell/random.c
+++ b/shell/random.c
@@ -80,7 +80,6 @@ next_random(random_t *rnd)
 	rnd->galois_LFSR = t;
 
 	/* http://en.wikipedia.org/wiki/Xorshift
-	 * Period 2^64-1 = 3 * 715827883 * 2147483647
 	 * Moderately good statistical properties:
 	 * fails the following "dieharder -g 200 -a" tests:
 	 *       diehard_operm5|   0
@@ -102,11 +101,19 @@ next_random(random_t *rnd)
 	 *         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 have 2^32 * 2^32-1 period.
+	/* 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:
@@ -118,9 +125,8 @@ next_random(random_t *rnd)
 	 *         dab_monobit2|  12
 	 *
 	 * Combining them with xorshift-64 increases period to
-	 * 2^32 * 2^32-1 * 2^64-1 / 3
-	 * (2^32-1 and 2^64-1 have one common divisor 3, hence "/ 3" part),
-	 * which is about 2^128 / 3, or in base 10 ~1.13*10^38.
+	 * 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.
 	 *