random.c

   1 /*
   2  * Routines to get randomness.
   3  */
   4 #include <syslog.h>
   5 #include <unistd.h>
   6 #include <stdlib.h>
   7 #include <sys/types.h>
   8 #include <limits.h>
   9 #include "pids.h"
  10 #include "random.h"
  11 #include "sanitise.h"   // interesting_numbers
  12 #include "types.h"
  13
  14 unsigned int rand_bool(void)
  15 {
  16         return rand() % 2;
  17 }
  18
  19 static unsigned int rand_single_bit(unsigned char size)
  20 {
  21         return (1L << (rand() % size));
  22 }
  23
  24 /*
  25  * set N bits, where N= rand(0 - WORDSIZE/2)
  26  */
  27 static unsigned long randbits(int limit)
  28 {
  29         unsigned int num = rand() % limit / 2;
  30         unsigned int i;
  31         unsigned long r = 0;
  32
  33         for (i = 0; i < num; i++)
  34                 r |= (1 << (rand() % (limit - 1)));
  35
  36         return r;
  37 }
  38
  39 /*
  40  * Based on very similar routine stolen from iknowthis. Thanks Tavis.
  41  */
  42 static unsigned long taviso(void)
  43 {
  44         unsigned long r = 0;
  45         unsigned long temp;
  46
  47         switch (rand() % 4) {
  48         case 0: r = rand() & rand();
  49 #if __WORDSIZE == 64
  50                 r <<= 32;
  51                 r |= rand() & rand();
  52 #endif
  53                 break;
  54
  55         case 1: temp = rand();
  56                 r = rand();
  57                 if (temp) r %= temp;
  58 #if __WORDSIZE == 64
  59                 r <<= 32;
  60
  61                 temp = rand();
  62                 if (temp) r |= rand() % temp;
  63 #endif
  64                 break;
  65
  66         case 2: r = rand() | rand();
  67 #if __WORDSIZE == 64
  68                 r <<= 32;
  69                 r |= rand() | rand();
  70 #endif
  71                 break;
  72
  73         case 3: r = rand();
  74 #if __WORDSIZE == 64
  75                 r <<= 32;
  76                 r |= rand();
  77 #endif
  78                 break;
  79         }
  80
  81         return r;
  82 }
  83
  84 /*
  85  * Pick 8 random bytes, and concatenate them into a long.
  86  */
  87 static unsigned long rand8x8(void)
  88 {
  89         unsigned long r = 0UL;
  90         unsigned int i;
  91
  92         for (i = (rand() % 7) + 1; i > 0; --i)
  93                 r = (r << 8) | rand() % 256;
  94
  95         return r;
  96 }
  97
  98 /*
  99  * Pick 1 random byte, and repeat it through a long.
 100  */
 101 static unsigned long rept8(unsigned int num)
 102 {
 103         unsigned long r = 0UL;
 104         unsigned int i;
 105         unsigned char c;
 106
 107         c = rand() % 256;
 108         for (i = rand() % (num - 1) ; i > 0; --i)
 109                 r = (r << 8) | c;
 110
 111         return r;
 112 }
 113
 114 /*
 115  * "selector" function for 32bit random.
 116  * only called from rand32()
 117  */
 118 static unsigned int __rand32(void)
 119 {
 120         unsigned long r = 0;
 121
 122         switch (rand() % 7) {
 123         case 0: r = rand_single_bit(32);
 124                 break;
 125         case 1: r = randbits(32);
 126                 break;
 127         case 2: r = rand();
 128                 break;
 129         case 3: r = taviso();
 130                 break;
 131         case 4: r = rand8x8();
 132                 break;
 133         case 5: r = rept8(4);
 134                 break;
 135         case 6: return get_interesting_32bit_value();
 136         }
 137
 138         return r;
 139 }
 140
 141 /*
 142  * Generate, and munge a 32bit number.
 143  */
 144 unsigned int rand32(void)
 145 {
 146         unsigned long r = 0;
 147
 148         r = __rand32();
 149
 150         if (rand_bool()) {
 151                 unsigned int i;
 152                 unsigned int rounds;
 153
 154                 /* mangle it. */
 155                 rounds = rand() % 3;
 156                 for (i = 0; i < rounds; i++) {
 157                         if (rand_bool())
 158                                 r |= __rand32();
 159                         else
 160                                 r ^= __rand32();
 161                 }
 162         }
 163
 164         /* Sometimes deduct it from INT_MAX */
 165         if (rand_bool())
 166                 r = INT_MAX - r;
 167
 168         /* Sometimes flip sign */
 169         if (rand_bool())
 170                 r |= (1L << 31);
 171
 172         /* we might get lucky if something is counting ints/longs etc. */
 173         if (rand() % 100 < 25) {
 174                 int _div = 1 << ((rand() % 4) + 1);     /* 2,4,8 or 16 */
 175                 r /= _div;
 176         }
 177
 178         /* limit the size */
 179         switch (rand() % 4) {
 180         case 0: r &= 0xff;
 181                 break;
 182         case 1: r &= 0xffff;
 183                 break;
 184         case 2: r &= 0xffffff;
 185                 break;
 186         }
 187
 188         return r;
 189 }
 190
 191 /*
 192  * Generate and munge a 64bit number.
 193  */
 194 u64 rand64(void)
 195 {
 196         unsigned long r = 0;
 197
 198         if (rand_bool()) {
 199                 /* 32-bit ranges. */
 200                 r = rand32();
 201
 202         } else {
 203                 /* 33:64-bit ranges. */
 204                 switch (rand() % 7) {
 205                 case 0: r = rand_single_bit(64);
 206                         break;
 207                 case 1: r = randbits(64);
 208                         break;
 209                 case 2: r = rand32() | rand32() << 31;
 210                         break;
 211                 case 3: r = taviso();
 212                         break;
 213                 case 4: r = rand8x8();
 214                         break;
 215                 case 5: r = rept8(8);
 216                         break;
 217                 /* Sometimes pick a not-so-random number. */
 218                 case 6: return get_interesting_value();
 219                 }
 220
 221                 /* limit the size */
 222                 switch (rand() % 4) {
 223                 case 0: r &= 0x000000ffffffffffULL;
 224                         break;
 225                 case 1: r &= 0x0000ffffffffffffULL;
 226                         break;
 227                 case 2: r &= 0x00ffffffffffffffULL;
 228                         break;
 229                 }
 230         }
 231
 232         /* Sometimes invert the generated number. */
 233         if (rand_bool())
 234                 r = ~r;
 235
 236         /* increase distribution in MSB */
 237         if ((rand() % 10)) {
 238                 unsigned int i;
 239                 unsigned int rounds;
 240
 241                 rounds = rand() % 4;
 242                 for (i = 0; i < rounds; i++)
 243                         r |= (1L << ((__WORDSIZE - 1) - (rand() % 8)));
 244         }
 245
 246         /* randomly flip sign bit. */
 247         if (rand_bool())
 248                 r |= (1L << (__WORDSIZE - 1));
 249
 250         return r;
 251 }