random.c raw

   1  #include <stdlib.h>
   2  #include <stdint.h>
   3  #include "lock.h"
   4  #include "fork_impl.h"
   5  
   6  /*
   7  this code uses the same lagged fibonacci generator as the
   8  original bsd random implementation except for the seeding
   9  which was broken in the original
  10  */
  11  
  12  static uint32_t init[] = {
  13  0x00000000,0x5851f42d,0xc0b18ccf,0xcbb5f646,
  14  0xc7033129,0x30705b04,0x20fd5db4,0x9a8b7f78,
  15  0x502959d8,0xab894868,0x6c0356a7,0x88cdb7ff,
  16  0xb477d43f,0x70a3a52b,0xa8e4baf1,0xfd8341fc,
  17  0x8ae16fd9,0x742d2f7a,0x0d1f0796,0x76035e09,
  18  0x40f7702c,0x6fa72ca5,0xaaa84157,0x58a0df74,
  19  0xc74a0364,0xae533cc4,0x04185faf,0x6de3b115,
  20  0x0cab8628,0xf043bfa4,0x398150e9,0x37521657};
  21  
  22  static int n = 31;
  23  static int i = 3;
  24  static int j = 0;
  25  static uint32_t *x = init+1;
  26  static volatile int lock[1];
  27  volatile int *const __random_lockptr = lock;
  28  
  29  static uint32_t lcg31(uint32_t x) {
  30  	return (1103515245*x + 12345) & 0x7fffffff;
  31  }
  32  
  33  static uint64_t lcg64(uint64_t x) {
  34  	return 6364136223846793005ull*x + 1;
  35  }
  36  
  37  static void *savestate() {
  38  	x[-1] = (n<<16)|(i<<8)|j;
  39  	return x-1;
  40  }
  41  
  42  static void loadstate(uint32_t *state) {
  43  	x = state+1;
  44  	n = x[-1]>>16;
  45  	i = (x[-1]>>8)&0xff;
  46  	j = x[-1]&0xff;
  47  }
  48  
  49  static void __srandom(unsigned seed) {
  50  	int k;
  51  	uint64_t s = seed;
  52  
  53  	if (n == 0) {
  54  		x[0] = s;
  55  		return;
  56  	}
  57  	i = n == 31 || n == 7 ? 3 : 1;
  58  	j = 0;
  59  	for (k = 0; k < n; k++) {
  60  		s = lcg64(s);
  61  		x[k] = s>>32;
  62  	}
  63  	/* make sure x contains at least one odd number */
  64  	x[0] |= 1;
  65  }
  66  
  67  void srandom(unsigned seed) {
  68  	LOCK(lock);
  69  	__srandom(seed);
  70  	UNLOCK(lock);
  71  }
  72  
  73  char *initstate(unsigned seed, char *state, size_t size) {
  74  	void *old;
  75  
  76  	if (size < 8)
  77  		return 0;
  78  	LOCK(lock);
  79  	old = savestate();
  80  	if (size < 32)
  81  		n = 0;
  82  	else if (size < 64)
  83  		n = 7;
  84  	else if (size < 128)
  85  		n = 15;
  86  	else if (size < 256)
  87  		n = 31;
  88  	else
  89  		n = 63;
  90  	x = (uint32_t*)state + 1;
  91  	__srandom(seed);
  92  	savestate();
  93  	UNLOCK(lock);
  94  	return old;
  95  }
  96  
  97  char *setstate(char *state) {
  98  	void *old;
  99  
 100  	LOCK(lock);
 101  	old = savestate();
 102  	loadstate((uint32_t*)state);
 103  	UNLOCK(lock);
 104  	return old;
 105  }
 106  
 107  long random(void) {
 108  	long k;
 109  
 110  	LOCK(lock);
 111  	if (n == 0) {
 112  		k = x[0] = lcg31(x[0]);
 113  		goto end;
 114  	}
 115  	x[i] += x[j];
 116  	k = x[i]>>1;
 117  	if (++i == n)
 118  		i = 0;
 119  	if (++j == n)
 120  		j = 0;
 121  end:
 122  	UNLOCK(lock);
 123  	return k;
 124  }
 125