Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 1 | /* vi: set sw=4 ts=4: */ |
| 2 | /* |
| 3 | * $RANDOM support. |
| 4 | * |
Denys Vlasenko | e3c6e19 | 2009-10-09 23:35:30 +0200 | [diff] [blame] | 5 | * Copyright (C) 2009 Denys Vlasenko |
Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 6 | * |
Denys Vlasenko | 0ef64bd | 2010-08-16 20:14:46 +0200 | [diff] [blame] | 7 | * Licensed under GPLv2, see file LICENSE in this source tree. |
Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 8 | */ |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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> |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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" |
Denys Vlasenko | f931875 | 2014-03-13 13:03:27 +0100 | [diff] [blame] | 32 | # define RAND_BASH_MASK 0xffffffff /* off */ |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 33 | #endif |
Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 34 | |
| 35 | uint32_t FAST_FUNC |
| 36 | next_random(random_t *rnd) |
| 37 | { |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 38 | /* Galois LFSR parameter: |
| 39 | * Taps at 32 31 29 1: |
| 40 | */ |
Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 41 | enum { MASK = 0x8000000b }; |
| 42 | /* Another example - taps at 32 31 30 10: */ |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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 | }; |
Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 54 | |
| 55 | uint32_t t; |
| 56 | |
Denys Vlasenko | 76ace25 | 2009-10-12 15:25:01 +0200 | [diff] [blame] | 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 | |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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 | */ |
Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 70 | rnd->LCG = 1664525 * rnd->LCG + 1013904223; |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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 | */ |
Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 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; |
Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 81 | |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 82 | /* http://en.wikipedia.org/wiki/Xorshift |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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 | */ |
Denys Vlasenko | ac03a40 | 2014-03-15 09:25:46 +0100 | [diff] [blame] | 104 | again: |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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); |
Denys Vlasenko | ac03a40 | 2014-03-15 09:25:46 +0100 | [diff] [blame] | 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; |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 115 | |
Denys Vlasenko | ac03a40 | 2014-03-15 09:25:46 +0100 | [diff] [blame] | 116 | /* Combined LCG + Galois LFSR rng has 2^32 * 2^32-1 period. |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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 |
Denys Vlasenko | ac03a40 | 2014-03-15 09:25:46 +0100 | [diff] [blame] | 128 | * 2^32 * 2^32-1 * 2^64-3 |
| 129 | * which is about 2^128, or in base 10 ~3.40*10^38. |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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; |
Denys Vlasenko | 3ea2e82 | 2009-10-09 20:59:04 +0200 | [diff] [blame] | 140 | } |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 141 | |
| 142 | #ifdef RANDTEST |
| 143 | static random_t rnd; |
| 144 | |
| 145 | int main(int argc, char **argv) |
| 146 | { |
| 147 | int i; |
Denys Vlasenko | f931875 | 2014-03-13 13:03:27 +0100 | [diff] [blame] | 148 | uint32_t buf[4096]; |
Denys Vlasenko | fb18307 | 2014-03-13 12:52:43 +0100 | [diff] [blame] | 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 |