X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=shell%2Frandom.c;h=5d3620516a329fad26e45227138f6cb775464fbf;hb=f3fa86525850620d31e48a742a25fd4965b1dba2;hp=9a64f54b0d54b3642eee496172930246a97f1670;hpb=fb183076a3a6580a4aba435c53ce033ef89e7fe6;p=oweals%2Fbusybox.git

diff --git a/shell/random.c b/shell/random.c
index 9a64f54b0..5d3620516 100644
--- a/shell/random.c
+++ b/shell/random.c
@@ -24,12 +24,12 @@
 # include <unistd.h>
 # include <stdio.h>
 # include <time.h>
-# define RAND_BASH_MASK 0xffffffff /* off */
 # 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
@@ -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.
 	 *
@@ -139,7 +145,7 @@ static random_t rnd;
 int main(int argc, char **argv)
 {
 	int i;
-	int buf[4096];
+	uint32_t buf[4096];
 
 	for (;;) {
 		for (i = 0; i < sizeof(buf) / sizeof(buf[0]); i++) {