pd.if.org Git - nbds/blob - runtime/random.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <pthread.h>
   5 #include <unistd.h>
   6 #include <fcntl.h>
   7
   8 #include "common.h"
   9 #include "runtime.h"
  10
  11 DECLARE_THREAD_LOCAL(rx_, uint32_t);
  12 DECLARE_THREAD_LOCAL(ry_, uint32_t);
  13 DECLARE_THREAD_LOCAL(rz_, uint32_t);
  14 DECLARE_THREAD_LOCAL(rc_, uint32_t);
  15
  16 void rnd_init (void) {
  17     INIT_THREAD_LOCAL(rx_);
  18     INIT_THREAD_LOCAL(ry_);
  19     INIT_THREAD_LOCAL(rz_);
  20     INIT_THREAD_LOCAL(rc_);
  21 }
  22
  23 // TODO: put a lock around this so that multiple threads being initialize concurrently don't read
  24 //       the same values from /dev/urandom
  25 void rnd_thread_init (void) {
  26     int fd = open("/dev/urandom", O_RDONLY);
  27     if (fd == -1) {
  28         perror("Error opening /dev/urandom");
  29         exit(1);
  30     }
  31
  32     char buf[16];
  33
  34     int n = read(fd, buf, sizeof(buf));
  35     if (n != 16) {
  36         if (n == -1) {
  37             perror("Error reading from /dev/urandom");
  38         }
  39         fprintf(stderr, "Could not read enough bytes from /dev/urandom");
  40         exit(1);
  41     }
  42
  43     uint32_t x, y, z, c;
  44     memcpy(&x, buf +  0, 4);
  45     memcpy(&y, buf +  4, 4);
  46     memcpy(&z, buf +  8, 4);
  47     memcpy(&c, buf + 12, 4);
  48
  49     SET_THREAD_LOCAL(rx_, x);
  50     SET_THREAD_LOCAL(ry_, y);
  51     SET_THREAD_LOCAL(rz_, z);
  52     SET_THREAD_LOCAL(rc_, z);
  53 }
  54
  55 // George Marsaglia's KISS generator
  56 //
  57 // Even though this returns 64 bits, this algorithm was only designed to generate 32 bits.
  58 // The upper 32 bits is going to be highly correlated with the lower 32 bits of the next call.
  59 uint64_t nbd_rand (void) {
  60     LOCALIZE_THREAD_LOCAL(rx_, unsigned);
  61     LOCALIZE_THREAD_LOCAL(ry_, unsigned);
  62     LOCALIZE_THREAD_LOCAL(rz_, unsigned);
  63     LOCALIZE_THREAD_LOCAL(rc_, unsigned);
  64
  65     uint32_t rx = 69069 * rx_ + 12345;
  66     uint32_t ry = ry_;
  67     ry ^= (ry << 13);
  68     ry ^= (ry >> 17);
  69     ry ^= (ry <<  5);
  70     uint64_t t = rz_ * 698769069LL + rc_;
  71     uint64_t r = rx + ry + t;
  72
  73     SET_THREAD_LOCAL(rx_, rx);
  74     SET_THREAD_LOCAL(ry_, ry);
  75     SET_THREAD_LOCAL(rz_, t);
  76     SET_THREAD_LOCAL(rc_, t >> 32);
  77
  78     return r;
  79 }