1 | /* vi: set sw=4 ts=4: */
|
---|
2 | /*
|
---|
3 | * $RANDOM support.
|
---|
4 | *
|
---|
5 | * Copyright (C) 2009 Denys Vlasenko
|
---|
6 | *
|
---|
7 | * Licensed under GPLv2, see file LICENSE in this source tree.
|
---|
8 | */
|
---|
9 |
|
---|
10 | /* For testing against dieharder, you need only random.{c,h}
|
---|
11 | * Howto:
|
---|
12 | * gcc -O2 -Wall -DRANDTEST random.c -o random
|
---|
13 | * ./random | dieharder -g 200 -a
|
---|
14 | */
|
---|
15 |
|
---|
16 | #if !defined RANDTEST
|
---|
17 |
|
---|
18 | # include "libbb.h"
|
---|
19 | # include "random.h"
|
---|
20 | # define RAND_BASH_MASK 0x7fff
|
---|
21 |
|
---|
22 | #else
|
---|
23 | # include <stdint.h>
|
---|
24 | # include <unistd.h>
|
---|
25 | # include <stdio.h>
|
---|
26 | # include <time.h>
|
---|
27 | # define FAST_FUNC /* nothing */
|
---|
28 | # define PUSH_AND_SET_FUNCTION_VISIBILITY_TO_HIDDEN /* nothing */
|
---|
29 | # define POP_SAVED_FUNCTION_VISIBILITY /* nothing */
|
---|
30 | # define monotonic_us() time(NULL)
|
---|
31 | # include "random.h"
|
---|
32 | # define RAND_BASH_MASK 0xffffffff /* off */
|
---|
33 | #endif
|
---|
34 |
|
---|
35 | uint32_t FAST_FUNC
|
---|
36 | next_random(random_t *rnd)
|
---|
37 | {
|
---|
38 | /* Galois LFSR parameter:
|
---|
39 | * Taps at 32 31 29 1:
|
---|
40 | */
|
---|
41 | enum { MASK = 0x8000000b };
|
---|
42 | /* Another example - taps at 32 31 30 10: */
|
---|
43 | /* enum { MASK = 0x00400007 }; */
|
---|
44 |
|
---|
45 | /* Xorshift parameters:
|
---|
46 | * Choices for a,b,c: 10,13,10; 8,9,22; 2,7,3; 23,3,24
|
---|
47 | * (given by algorithm author)
|
---|
48 | */
|
---|
49 | enum {
|
---|
50 | a = 2,
|
---|
51 | b = 7,
|
---|
52 | c = 3,
|
---|
53 | };
|
---|
54 |
|
---|
55 | uint32_t t;
|
---|
56 |
|
---|
57 | if (UNINITED_RANDOM_T(rnd)) {
|
---|
58 | /* Can use monotonic_ns() for better randomness but for now
|
---|
59 | * it is not used anywhere else in busybox... so avoid bloat
|
---|
60 | */
|
---|
61 | INIT_RANDOM_T(rnd, getpid(), monotonic_us());
|
---|
62 | }
|
---|
63 |
|
---|
64 | /* LCG: period of 2^32, but quite weak:
|
---|
65 | * bit 0 alternates beetween 0 and 1 (pattern of length 2)
|
---|
66 | * bit 1 has a repeating pattern of length 4
|
---|
67 | * bit 2 has a repeating pattern of length 8
|
---|
68 | * etc...
|
---|
69 | */
|
---|
70 | rnd->LCG = 1664525 * rnd->LCG + 1013904223;
|
---|
71 |
|
---|
72 | /* Galois LFSR:
|
---|
73 | * period of 2^32-1 = 3 * 5 * 17 * 257 * 65537.
|
---|
74 | * Successive values are right-shifted one bit
|
---|
75 | * and possibly xored with a sparse constant.
|
---|
76 | */
|
---|
77 | t = (rnd->galois_LFSR << 1);
|
---|
78 | if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */
|
---|
79 | t ^= MASK;
|
---|
80 | rnd->galois_LFSR = t;
|
---|
81 |
|
---|
82 | /* http://en.wikipedia.org/wiki/Xorshift
|
---|
83 | * Moderately good statistical properties:
|
---|
84 | * fails the following "dieharder -g 200 -a" tests:
|
---|
85 | * diehard_operm5| 0
|
---|
86 | * diehard_oqso| 0
|
---|
87 | * diehard_count_1s_byt| 0
|
---|
88 | * diehard_3dsphere| 3
|
---|
89 | * diehard_squeeze| 0
|
---|
90 | * diehard_runs| 0
|
---|
91 | * diehard_runs| 0
|
---|
92 | * diehard_craps| 0
|
---|
93 | * diehard_craps| 0
|
---|
94 | * rgb_minimum_distance| 3
|
---|
95 | * rgb_minimum_distance| 4
|
---|
96 | * rgb_minimum_distance| 5
|
---|
97 | * rgb_permutations| 3
|
---|
98 | * rgb_permutations| 4
|
---|
99 | * rgb_permutations| 5
|
---|
100 | * dab_filltree| 32
|
---|
101 | * dab_filltree| 32
|
---|
102 | * dab_monobit2| 12
|
---|
103 | */
|
---|
104 | again:
|
---|
105 | t = rnd->xs64_x ^ (rnd->xs64_x << a);
|
---|
106 | rnd->xs64_x = rnd->xs64_y;
|
---|
107 | rnd->xs64_y = rnd->xs64_y ^ (rnd->xs64_y >> c) ^ t ^ (t >> b);
|
---|
108 | /*
|
---|
109 | * Period 2^64-1 = 2^32+1 * 2^32-1 has a common divisor with Galois LFSR.
|
---|
110 | * By skipping two possible states (0x1 and 0x2) we reduce period to
|
---|
111 | * 2^64-3 = 13 * 3889 * 364870227143809 which has no common divisors:
|
---|
112 | */
|
---|
113 | if (rnd->xs64_y == 0 && rnd->xs64_x <= 2)
|
---|
114 | goto again;
|
---|
115 |
|
---|
116 | /* Combined LCG + Galois LFSR rng has 2^32 * 2^32-1 period.
|
---|
117 | * Strength:
|
---|
118 | * individually, both are extremely weak cryptographycally;
|
---|
119 | * when combined, they fail the following "dieharder -g 200 -a" tests:
|
---|
120 | * diehard_rank_6x8| 0
|
---|
121 | * diehard_oqso| 0
|
---|
122 | * diehard_dna| 0
|
---|
123 | * diehard_count_1s_byt| 0
|
---|
124 | * rgb_bitdist| 2
|
---|
125 | * dab_monobit2| 12
|
---|
126 | *
|
---|
127 | * Combining them with xorshift-64 increases period to
|
---|
128 | * 2^32 * 2^32-1 * 2^64-3
|
---|
129 | * which is about 2^128, or in base 10 ~3.40*10^38.
|
---|
130 | * Strength of the combination:
|
---|
131 | * passes all "dieharder -g 200 -a" tests.
|
---|
132 | *
|
---|
133 | * Combining with subtraction and addition is just for fun.
|
---|
134 | * It does not add meaningful strength, could use xor operation instead.
|
---|
135 | */
|
---|
136 | t = rnd->galois_LFSR - rnd->LCG + rnd->xs64_y;
|
---|
137 |
|
---|
138 | /* bash compat $RANDOM range: */
|
---|
139 | return t & RAND_BASH_MASK;
|
---|
140 | }
|
---|
141 |
|
---|
142 | #ifdef RANDTEST
|
---|
143 | static random_t rnd;
|
---|
144 |
|
---|
145 | int main(int argc, char **argv)
|
---|
146 | {
|
---|
147 | int i;
|
---|
148 | uint32_t buf[4096];
|
---|
149 |
|
---|
150 | for (;;) {
|
---|
151 | for (i = 0; i < sizeof(buf) / sizeof(buf[0]); i++) {
|
---|
152 | buf[i] = next_random(&rnd);
|
---|
153 | }
|
---|
154 | write(1, buf, sizeof(buf));
|
---|
155 | }
|
---|
156 |
|
---|
157 | return 0;
|
---|
158 | }
|
---|
159 |
|
---|
160 | #endif
|
---|