3
0

random.c 4.0 KB

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