blob: 5d3620516a329fad26e45227138f6cb775464fbf [file] [log] [blame]
Denys Vlasenko3ea2e822009-10-09 20:59:04 +02001/* vi: set sw=4 ts=4: */
2/*
3 * $RANDOM support.
4 *
Denys Vlasenkoe3c6e192009-10-09 23:35:30 +02005 * Copyright (C) 2009 Denys Vlasenko
Denys Vlasenko3ea2e822009-10-09 20:59:04 +02006 *
Denys Vlasenko0ef64bd2010-08-16 20:14:46 +02007 * Licensed under GPLv2, see file LICENSE in this source tree.
Denys Vlasenko3ea2e822009-10-09 20:59:04 +02008 */
Denys Vlasenkofb183072014-03-13 12:52:43 +01009
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>
Denys Vlasenkofb183072014-03-13 12:52:43 +010027# 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"
Denys Vlasenkof9318752014-03-13 13:03:27 +010032# define RAND_BASH_MASK 0xffffffff /* off */
Denys Vlasenkofb183072014-03-13 12:52:43 +010033#endif
Denys Vlasenko3ea2e822009-10-09 20:59:04 +020034
35uint32_t FAST_FUNC
36next_random(random_t *rnd)
37{
Denys Vlasenkofb183072014-03-13 12:52:43 +010038 /* Galois LFSR parameter:
39 * Taps at 32 31 29 1:
40 */
Denys Vlasenko3ea2e822009-10-09 20:59:04 +020041 enum { MASK = 0x8000000b };
42 /* Another example - taps at 32 31 30 10: */
Denys Vlasenkofb183072014-03-13 12:52:43 +010043 /* 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 };
Denys Vlasenko3ea2e822009-10-09 20:59:04 +020054
55 uint32_t t;
56
Denys Vlasenko76ace252009-10-12 15:25:01 +020057 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
Denys Vlasenkofb183072014-03-13 12:52:43 +010064 /* 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 */
Denys Vlasenko3ea2e822009-10-09 20:59:04 +020070 rnd->LCG = 1664525 * rnd->LCG + 1013904223;
Denys Vlasenkofb183072014-03-13 12:52:43 +010071
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 */
Denys Vlasenko3ea2e822009-10-09 20:59:04 +020077 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;
Denys Vlasenko3ea2e822009-10-09 20:59:04 +020081
Denys Vlasenkofb183072014-03-13 12:52:43 +010082 /* http://en.wikipedia.org/wiki/Xorshift
Denys Vlasenkofb183072014-03-13 12:52:43 +010083 * 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 */
Denys Vlasenkoac03a402014-03-15 09:25:46 +0100104 again:
Denys Vlasenkofb183072014-03-13 12:52:43 +0100105 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);
Denys Vlasenkoac03a402014-03-15 09:25:46 +0100108 /*
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;
Denys Vlasenkofb183072014-03-13 12:52:43 +0100115
Denys Vlasenkoac03a402014-03-15 09:25:46 +0100116 /* Combined LCG + Galois LFSR rng has 2^32 * 2^32-1 period.
Denys Vlasenkofb183072014-03-13 12:52:43 +0100117 * 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
Denys Vlasenkoac03a402014-03-15 09:25:46 +0100128 * 2^32 * 2^32-1 * 2^64-3
129 * which is about 2^128, or in base 10 ~3.40*10^38.
Denys Vlasenkofb183072014-03-13 12:52:43 +0100130 * 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;
Denys Vlasenko3ea2e822009-10-09 20:59:04 +0200140}
Denys Vlasenkofb183072014-03-13 12:52:43 +0100141
142#ifdef RANDTEST
143static random_t rnd;
144
145int main(int argc, char **argv)
146{
147 int i;
Denys Vlasenkof9318752014-03-13 13:03:27 +0100148 uint32_t buf[4096];
Denys Vlasenkofb183072014-03-13 12:52:43 +0100149
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