hexedit: fixes to "goto address" code

[oweals/busybox.git] / shell / random.c

diff --git a/shell/random.c b/shell/random.c
index 9a64f54b0d54b3642eee496172930246a97f1670..5d3620516a329fad26e45227138f6cb775464fbf 100644 (file)
--- 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++) {