random.c

   1 /**********************************************************************
   2
   3   random.c -
   4
   5   $Author$
   6   created at: Fri Dec 24 16:39:21 JST 1993
   7
   8   Copyright (C) 1993-2007 Yukihiro Matsumoto
   9
  10 **********************************************************************/
  11
  12 #include "ruby/internal/config.h"
  13
  14 #include <errno.h>
  15 #include <limits.h>
  16 #include <math.h>
  17 #include <float.h>
  18 #include <time.h>
  19
  20 #ifdef HAVE_UNISTD_H
  21 # include <unistd.h>
  22 #endif
  23
  24 #include <sys/types.h>
  25 #include <sys/stat.h>
  26
  27 #ifdef HAVE_FCNTL_H
  28 # include <fcntl.h>
  29 #endif
  30
  31 #if defined(HAVE_SYS_TIME_H)
  32 # include <sys/time.h>
  33 #endif
  34
  35 #ifdef HAVE_SYSCALL_H
  36 # include <syscall.h>
  37 #elif defined HAVE_SYS_SYSCALL_H
  38 # include <sys/syscall.h>
  39 #endif
  40
  41 #ifdef _WIN32
  42 # include <winsock2.h>
  43 # include <windows.h>
  44 # include <wincrypt.h>
  45 # include <bcrypt.h>
  46 #endif
  47
  48 #if defined(__OpenBSD__) || defined(__FreeBSD__) || defined(__NetBSD__)
  49 /* to define OpenBSD and FreeBSD for version check */
  50 # include <sys/param.h>
  51 #endif
  52
  53 #if defined HAVE_GETRANDOM || defined HAVE_GETENTROPY
  54 # if defined(HAVE_SYS_RANDOM_H)
  55 #  include <sys/random.h>
  56 # endif
  57 #elif defined __linux__ && defined __NR_getrandom
  58 # include <linux/random.h>
  59 #endif
  60
  61 #if defined __APPLE__
  62 # include <AvailabilityMacros.h>
  63 #endif
  64
  65 #include "internal.h"
  66 #include "internal/array.h"
  67 #include "internal/compilers.h"
  68 #include "internal/numeric.h"
  69 #include "internal/random.h"
  70 #include "internal/sanitizers.h"
  71 #include "internal/variable.h"
  72 #include "ruby_atomic.h"
  73 #include "ruby/random.h"
  74 #include "ruby/ractor.h"
  75
  76 STATIC_ASSERT(int_must_be_32bit_at_least, sizeof(int) * CHAR_BIT >= 32);
  77
  78 #include "missing/mt19937.c"
  79
  80 /* generates a random number on [0,1) with 53-bit resolution*/
  81 static double int_pair_to_real_exclusive(uint32_t a, uint32_t b);
  82 static double
  83 genrand_real(struct MT *mt)
  84 {
  85     /* mt must be initialized */
  86     unsigned int a = genrand_int32(mt), b = genrand_int32(mt);
  87     return int_pair_to_real_exclusive(a, b);
  88 }
  89
  90 static const double dbl_reduce_scale = /* 2**(-DBL_MANT_DIG) */
  91     (1.0
  92      / (double)(DBL_MANT_DIG > 2*31 ? (1ul<<31) : 1.0)
  93      / (double)(DBL_MANT_DIG > 1*31 ? (1ul<<31) : 1.0)
  94      / (double)(1ul<<(DBL_MANT_DIG%31)));
  95
  96 static double
  97 int_pair_to_real_exclusive(uint32_t a, uint32_t b)
  98 {
  99     static const int a_shift = DBL_MANT_DIG < 64 ?
 100         (64-DBL_MANT_DIG)/2 : 0;
 101     static const int b_shift = DBL_MANT_DIG < 64 ?
 102         (65-DBL_MANT_DIG)/2 : 0;
 103     a >>= a_shift;
 104     b >>= b_shift;
 105     return (a*(double)(1ul<<(32-b_shift))+b)*dbl_reduce_scale;
 106 }
 107
 108 /* generates a random number on [0,1] with 53-bit resolution*/
 109 static double int_pair_to_real_inclusive(uint32_t a, uint32_t b);
 110 #if 0
 111 static double
 112 genrand_real2(struct MT *mt)
 113 {
 114     /* mt must be initialized */
 115     uint32_t a = genrand_int32(mt), b = genrand_int32(mt);
 116     return int_pair_to_real_inclusive(a, b);
 117 }
 118 #endif
 119
 120 /* These real versions are due to Isaku Wada, 2002/01/09 added */
 121
 122 #undef N
 123 #undef M
 124
 125 typedef struct {
 126     rb_random_t base;
 127     struct MT mt;
 128 } rb_random_mt_t;
 129
 130 #define DEFAULT_SEED_CNT 4
 131
 132 static VALUE rand_init(const rb_random_interface_t *, rb_random_t *, VALUE);
 133 static VALUE random_seed(VALUE);
 134 static void fill_random_seed(uint32_t *seed, size_t cnt, bool try_bytes);
 135 static VALUE make_seed_value(uint32_t *ptr, size_t len);
 136 #define fill_random_bytes ruby_fill_random_bytes
 137
 138 RB_RANDOM_INTERFACE_DECLARE(rand_mt);
 139 static const rb_random_interface_t random_mt_if = {
 140     DEFAULT_SEED_CNT * 32,
 141     RB_RANDOM_INTERFACE_DEFINE(rand_mt)
 142 };
 143
 144 static rb_random_mt_t *
 145 rand_mt_start(rb_random_mt_t *r)
 146 {
 147     if (!genrand_initialized(&r->mt)) {
 148         r->base.seed = rand_init(&random_mt_if, &r->base, random_seed(Qundef));
 149     }
 150     return r;
 151 }
 152
 153 static rb_random_t *
 154 rand_start(rb_random_mt_t *r)
 155 {
 156     return &rand_mt_start(r)->base;
 157 }
 158
 159 static rb_ractor_local_key_t default_rand_key;
 160
 161 void
 162 rb_free_default_rand_key(void)
 163 {
 164     xfree(default_rand_key);
 165 }
 166
 167 static void
 168 default_rand_mark(void *ptr)
 169 {
 170     rb_random_mt_t *rnd = (rb_random_mt_t *)ptr;
 171     rb_gc_mark(rnd->base.seed);
 172 }
 173
 174 static const struct rb_ractor_local_storage_type default_rand_key_storage_type = {
 175     default_rand_mark,
 176     ruby_xfree,
 177 };
 178
 179 static rb_random_mt_t *
 180 default_rand(void)
 181 {
 182     rb_random_mt_t *rnd;
 183
 184     if ((rnd = rb_ractor_local_storage_ptr(default_rand_key)) == NULL) {
 185         rnd = ZALLOC(rb_random_mt_t);
 186         rb_ractor_local_storage_ptr_set(default_rand_key, rnd);
 187     }
 188
 189     return rnd;
 190 }
 191
 192 static rb_random_mt_t *
 193 default_mt(void)
 194 {
 195     return rand_mt_start(default_rand());
 196 }
 197
 198 unsigned int
 199 rb_genrand_int32(void)
 200 {
 201     struct MT *mt = &default_mt()->mt;
 202     return genrand_int32(mt);
 203 }
 204
 205 double
 206 rb_genrand_real(void)
 207 {
 208     struct MT *mt = &default_mt()->mt;
 209     return genrand_real(mt);
 210 }
 211
 212 #define SIZEOF_INT32 (31/CHAR_BIT + 1)
 213
 214 static double
 215 int_pair_to_real_inclusive(uint32_t a, uint32_t b)
 216 {
 217     double r;
 218     enum {dig = DBL_MANT_DIG};
 219     enum {dig_u = dig-32, dig_r64 = 64-dig, bmask = ~(~0u<<(dig_r64))};
 220 #if defined HAVE_UINT128_T
 221     const uint128_t m = ((uint128_t)1 << dig) | 1;
 222     uint128_t x = ((uint128_t)a << 32) | b;
 223     r = (double)(uint64_t)((x * m) >> 64);
 224 #elif defined HAVE_UINT64_T && !MSC_VERSION_BEFORE(1300)
 225     uint64_t x = ((uint64_t)a << dig_u) +
 226         (((uint64_t)b + (a >> dig_u)) >> dig_r64);
 227     r = (double)x;
 228 #else
 229     /* shift then add to get rid of overflow */
 230     b = (b >> dig_r64) + (((a >> dig_u) + (b & bmask)) >> dig_r64);
 231     r = (double)a * (1 << dig_u) + b;
 232 #endif
 233     return r * dbl_reduce_scale;
 234 }
 235
 236 VALUE rb_cRandom;
 237 #define id_minus '-'
 238 #define id_plus  '+'
 239 static ID id_rand, id_bytes;
 240 NORETURN(static void domain_error(void));
 241
 242 /* :nodoc: */
 243 #define random_mark rb_random_mark
 244
 245 void
 246 random_mark(void *ptr)
 247 {
 248     rb_gc_mark(((rb_random_t *)ptr)->seed);
 249 }
 250
 251 #define random_free RUBY_TYPED_DEFAULT_FREE
 252
 253 static size_t
 254 random_memsize(const void *ptr)
 255 {
 256     return sizeof(rb_random_t);
 257 }
 258
 259 const rb_data_type_t rb_random_data_type = {
 260     "random",
 261     {
 262         random_mark,
 263         random_free,
 264         random_memsize,
 265     },
 266     0, 0, RUBY_TYPED_FREE_IMMEDIATELY
 267 };
 268
 269 #define random_mt_mark rb_random_mark
 270 #define random_mt_free RUBY_TYPED_DEFAULT_FREE
 271
 272 static size_t
 273 random_mt_memsize(const void *ptr)
 274 {
 275     return sizeof(rb_random_mt_t);
 276 }
 277
 278 static const rb_data_type_t random_mt_type = {
 279     "random/MT",
 280     {
 281         random_mt_mark,
 282         random_mt_free,
 283         random_mt_memsize,
 284     },
 285     &rb_random_data_type,
 286     (void *)&random_mt_if,
 287     RUBY_TYPED_FREE_IMMEDIATELY
 288 };
 289
 290 static rb_random_t *
 291 get_rnd(VALUE obj)
 292 {
 293     rb_random_t *ptr;
 294     TypedData_Get_Struct(obj, rb_random_t, &rb_random_data_type, ptr);
 295     if (RTYPEDDATA_TYPE(obj) == &random_mt_type)
 296         return rand_start((rb_random_mt_t *)ptr);
 297     return ptr;
 298 }
 299
 300 static rb_random_mt_t *
 301 get_rnd_mt(VALUE obj)
 302 {
 303     rb_random_mt_t *ptr;
 304     TypedData_Get_Struct(obj, rb_random_mt_t, &random_mt_type, ptr);
 305     return ptr;
 306 }
 307
 308 static rb_random_t *
 309 try_get_rnd(VALUE obj)
 310 {
 311     if (obj == rb_cRandom) {
 312         return rand_start(default_rand());
 313     }
 314     if (!rb_typeddata_is_kind_of(obj, &rb_random_data_type)) return NULL;
 315     if (RTYPEDDATA_TYPE(obj) == &random_mt_type)
 316         return rand_start(DATA_PTR(obj));
 317     rb_random_t *rnd = DATA_PTR(obj);
 318     if (!rnd) {
 319         rb_raise(rb_eArgError, "uninitialized random: %s",
 320                  RTYPEDDATA_TYPE(obj)->wrap_struct_name);
 321     }
 322     return rnd;
 323 }
 324
 325 static const rb_random_interface_t *
 326 try_rand_if(VALUE obj, rb_random_t *rnd)
 327 {
 328     if (rnd == &default_rand()->base) {
 329         return &random_mt_if;
 330     }
 331     return rb_rand_if(obj);
 332 }
 333
 334 /* :nodoc: */
 335 void
 336 rb_random_base_init(rb_random_t *rnd)
 337 {
 338     rnd->seed = INT2FIX(0);
 339 }
 340
 341 /* :nodoc: */
 342 static VALUE
 343 random_alloc(VALUE klass)
 344 {
 345     rb_random_mt_t *rnd;
 346     VALUE obj = TypedData_Make_Struct(klass, rb_random_mt_t, &random_mt_type, rnd);
 347     rb_random_base_init(&rnd->base);
 348     return obj;
 349 }
 350
 351 static VALUE
 352 rand_init_default(const rb_random_interface_t *rng, rb_random_t *rnd)
 353 {
 354     VALUE seed, buf0 = 0;
 355     size_t len = roomof(rng->default_seed_bits, 32);
 356     uint32_t *buf = ALLOCV_N(uint32_t, buf0, len+1);
 357
 358     fill_random_seed(buf, len, true);
 359     rng->init(rnd, buf, len);
 360     seed = make_seed_value(buf, len);
 361     explicit_bzero(buf, len * sizeof(*buf));
 362     ALLOCV_END(buf0);
 363     return seed;
 364 }
 365
 366 static VALUE
 367 rand_init(const rb_random_interface_t *rng, rb_random_t *rnd, VALUE seed)
 368 {
 369     uint32_t *buf;
 370     VALUE buf0 = 0;
 371     size_t len;
 372     int sign;
 373
 374     len = rb_absint_numwords(seed, 32, NULL);
 375     if (len == 0) len = 1;
 376     buf = ALLOCV_N(uint32_t, buf0, len);
 377     sign = rb_integer_pack(seed, buf, len, sizeof(uint32_t), 0,
 378         INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER);
 379     if (sign < 0)
 380         sign = -sign;
 381     if (len <= 1) {
 382         rng->init_int32(rnd, len ? buf[0] : 0);
 383     }
 384     else {
 385         if (sign != 2 && buf[len-1] == 1) /* remove leading-zero-guard */
 386             len--;
 387         rng->init(rnd, buf, len);
 388     }
 389     explicit_bzero(buf, len * sizeof(*buf));
 390     ALLOCV_END(buf0);
 391     return seed;
 392 }
 393
 394 /*
 395  * call-seq:
 396  *   Random.new(seed = Random.new_seed) -> prng
 397  *
 398  * Creates a new PRNG using +seed+ to set the initial state. If +seed+ is
 399  * omitted, the generator is initialized with Random.new_seed.
 400  *
 401  * See Random.srand for more information on the use of seed values.
 402  */
 403 static VALUE
 404 random_init(int argc, VALUE *argv, VALUE obj)
 405 {
 406     rb_random_t *rnd = try_get_rnd(obj);
 407     const rb_random_interface_t *rng = rb_rand_if(obj);
 408
 409     if (!rng) {
 410         rb_raise(rb_eTypeError, "undefined random interface: %s",
 411                  RTYPEDDATA_TYPE(obj)->wrap_struct_name);
 412     }
 413
 414     unsigned int major = rng->version.major;
 415     unsigned int minor = rng->version.minor;
 416     if (major != RUBY_RANDOM_INTERFACE_VERSION_MAJOR) {
 417         rb_raise(rb_eTypeError, "Random interface version "
 418                  STRINGIZE(RUBY_RANDOM_INTERFACE_VERSION_MAJOR) "."
 419                  STRINGIZE(RUBY_RANDOM_INTERFACE_VERSION_MINOR) " "
 420                  "expected: %d.%d", major, minor);
 421     }
 422     argc = rb_check_arity(argc, 0, 1);
 423     rb_check_frozen(obj);
 424     if (argc == 0) {
 425         rnd->seed = rand_init_default(rng, rnd);
 426     }
 427     else {
 428         rnd->seed = rand_init(rng, rnd, rb_to_int(argv[0]));
 429     }
 430     return obj;
 431 }
 432
 433 #define DEFAULT_SEED_LEN (DEFAULT_SEED_CNT * (int)sizeof(int32_t))
 434
 435 #if defined(S_ISCHR) && !defined(DOSISH)
 436 # define USE_DEV_URANDOM 1
 437 #else
 438 # define USE_DEV_URANDOM 0
 439 #endif
 440
 441 #ifdef HAVE_GETENTROPY
 442 # define MAX_SEED_LEN_PER_READ 256
 443 static int
 444 fill_random_bytes_urandom(void *seed, size_t size)
 445 {
 446      unsigned char *p = (unsigned char *)seed;
 447      while (size) {
 448         size_t len = size < MAX_SEED_LEN_PER_READ ? size : MAX_SEED_LEN_PER_READ;
 449         if (getentropy(p, len) != 0) {
 450             return -1;
 451         }
 452         p += len;
 453         size -= len;
 454      }
 455      return 0;
 456 }
 457 #elif USE_DEV_URANDOM
 458 static int
 459 fill_random_bytes_urandom(void *seed, size_t size)
 460 {
 461     /*
 462       O_NONBLOCK and O_NOCTTY is meaningless if /dev/urandom correctly points
 463       to a urandom device. But it protects from several strange hazard if
 464       /dev/urandom is not a urandom device.
 465     */
 466     int fd = rb_cloexec_open("/dev/urandom",
 467 # ifdef O_NONBLOCK
 468                              O_NONBLOCK|
 469 # endif
 470 # ifdef O_NOCTTY
 471                              O_NOCTTY|
 472 # endif
 473                              O_RDONLY, 0);
 474     struct stat statbuf;
 475     ssize_t ret = 0;
 476     size_t offset = 0;
 477
 478     if (fd < 0) return -1;
 479     rb_update_max_fd(fd);
 480     if (fstat(fd, &statbuf) == 0 && S_ISCHR(statbuf.st_mode)) {
 481         do {
 482             ret = read(fd, ((char*)seed) + offset, size - offset);
 483             if (ret < 0) {
 484                 close(fd);
 485                 return -1;
 486             }
 487             offset += (size_t)ret;
 488         } while (offset < size);
 489     }
 490     close(fd);
 491     return 0;
 492 }
 493 #else
 494 # define fill_random_bytes_urandom(seed, size) -1
 495 #endif
 496
 497 #if ! defined HAVE_GETRANDOM && defined __linux__ && defined __NR_getrandom
 498 # ifndef GRND_NONBLOCK
 499 #   define GRND_NONBLOCK 0x0001 /* not defined in musl libc */
 500 # endif
 501 # define getrandom(ptr, size, flags) \
 502     (ssize_t)syscall(__NR_getrandom, (ptr), (size), (flags))
 503 # define HAVE_GETRANDOM 1
 504 #endif
 505
 506 #if 0
 507 #elif defined MAC_OS_X_VERSION_10_7 && MAC_OS_X_VERSION_MIN_REQUIRED >= MAC_OS_X_VERSION_10_7
 508
 509 # if defined(USE_COMMON_RANDOM)
 510 # elif defined MAC_OS_X_VERSION_10_10 && MAC_OS_X_VERSION_MIN_REQUIRED >= MAC_OS_X_VERSION_10_10
 511 #   define USE_COMMON_RANDOM 1
 512 # else
 513 #   define USE_COMMON_RANDOM 0
 514 # endif
 515 # if USE_COMMON_RANDOM
 516 #   include <CommonCrypto/CommonCryptoError.h> /* for old Xcode */
 517 #   include <CommonCrypto/CommonRandom.h>
 518 # else
 519 #   include <Security/SecRandom.h>
 520 # endif
 521
 522 static int
 523 fill_random_bytes_syscall(void *seed, size_t size, int unused)
 524 {
 525 #if USE_COMMON_RANDOM
 526     CCRNGStatus status = CCRandomGenerateBytes(seed, size);
 527     int failed = status != kCCSuccess;
 528 #else
 529     int status = SecRandomCopyBytes(kSecRandomDefault, size, seed);
 530     int failed = status != errSecSuccess;
 531 #endif
 532
 533     if (failed) {
 534 # if 0
 535 # if USE_COMMON_RANDOM
 536         /* How to get the error message? */
 537         fprintf(stderr, "CCRandomGenerateBytes failed: %d\n", status);
 538 # else
 539         CFStringRef s = SecCopyErrorMessageString(status, NULL);
 540         const char *m = s ? CFStringGetCStringPtr(s, kCFStringEncodingUTF8) : NULL;
 541         fprintf(stderr, "SecRandomCopyBytes failed: %d: %s\n", status,
 542                 m ? m : "unknown");
 543         if (s) CFRelease(s);
 544 # endif
 545 # endif
 546         return -1;
 547     }
 548     return 0;
 549 }
 550 #elif defined(HAVE_ARC4RANDOM_BUF)
 551 static int
 552 fill_random_bytes_syscall(void *buf, size_t size, int unused)
 553 {
 554 #if (defined(__OpenBSD__) && OpenBSD >= 201411) || \
 555     (defined(__NetBSD__)  && __NetBSD_Version__ >= 700000000) || \
 556     (defined(__FreeBSD__) && __FreeBSD_version >= 1200079)
 557     arc4random_buf(buf, size);
 558     return 0;
 559 #else
 560     return -1;
 561 #endif
 562 }
 563 #elif defined(_WIN32)
 564
 565 #ifndef DWORD_MAX
 566 # define DWORD_MAX (~(DWORD)0UL)
 567 #endif
 568
 569 # if defined(CRYPT_VERIFYCONTEXT)
 570 /* Although HCRYPTPROV is not a HANDLE, it looks like
 571  * INVALID_HANDLE_VALUE is not a valid value */
 572 static const HCRYPTPROV INVALID_HCRYPTPROV = (HCRYPTPROV)INVALID_HANDLE_VALUE;
 573
 574 static void
 575 release_crypt(void *p)
 576 {
 577     HCRYPTPROV *ptr = p;
 578     HCRYPTPROV prov = (HCRYPTPROV)ATOMIC_PTR_EXCHANGE(*ptr, INVALID_HCRYPTPROV);
 579     if (prov && prov != INVALID_HCRYPTPROV) {
 580         CryptReleaseContext(prov, 0);
 581     }
 582 }
 583
 584 static const rb_data_type_t crypt_prov_type = {
 585     "HCRYPTPROV",
 586     {0, release_crypt,},
 587     0, 0, RUBY_TYPED_FREE_IMMEDIATELY | RUBY_TYPED_EMBEDDABLE
 588 };
 589
 590 static int
 591 fill_random_bytes_crypt(void *seed, size_t size)
 592 {
 593     static HCRYPTPROV perm_prov;
 594     HCRYPTPROV prov = perm_prov, old_prov;
 595     if (!prov) {
 596         VALUE wrapper = TypedData_Wrap_Struct(0, &crypt_prov_type, 0);
 597         if (!CryptAcquireContext(&prov, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) {
 598             prov = INVALID_HCRYPTPROV;
 599         }
 600         old_prov = (HCRYPTPROV)ATOMIC_PTR_CAS(perm_prov, 0, prov);
 601         if (LIKELY(!old_prov)) { /* no other threads acquired */
 602             if (prov != INVALID_HCRYPTPROV) {
 603                 DATA_PTR(wrapper) = (void *)prov;
 604                 rb_vm_register_global_object(wrapper);
 605             }
 606         }
 607         else {                  /* another thread acquired */
 608             if (prov != INVALID_HCRYPTPROV) {
 609                 CryptReleaseContext(prov, 0);
 610             }
 611             prov = old_prov;
 612         }
 613     }
 614     if (prov == INVALID_HCRYPTPROV) return -1;
 615     while (size > 0) {
 616         DWORD n = (size > (size_t)DWORD_MAX) ? DWORD_MAX : (DWORD)size;
 617         if (!CryptGenRandom(prov, n, seed)) return -1;
 618         seed = (char *)seed + n;
 619         size -= n;
 620     }
 621     return 0;
 622 }
 623 # else
 624 #   define fill_random_bytes_crypt(seed, size) -1
 625 # endif
 626
 627 static int
 628 fill_random_bytes_bcrypt(void *seed, size_t size)
 629 {
 630     while (size > 0) {
 631         ULONG n = (size > (size_t)ULONG_MAX) ? LONG_MAX : (ULONG)size;
 632         if (BCryptGenRandom(NULL, seed, n, BCRYPT_USE_SYSTEM_PREFERRED_RNG))
 633             return -1;
 634         seed = (char *)seed + n;
 635         size -= n;
 636     }
 637     return 0;
 638 }
 639
 640 static int
 641 fill_random_bytes_syscall(void *seed, size_t size, int unused)
 642 {
 643     if (fill_random_bytes_bcrypt(seed, size) == 0) return 0;
 644     return fill_random_bytes_crypt(seed, size);
 645 }
 646 #elif defined HAVE_GETRANDOM
 647 static int
 648 fill_random_bytes_syscall(void *seed, size_t size, int need_secure)
 649 {
 650     static rb_atomic_t try_syscall = 1;
 651     if (try_syscall) {
 652         size_t offset = 0;
 653         int flags = 0;
 654         if (!need_secure)
 655             flags = GRND_NONBLOCK;
 656         do {
 657             errno = 0;
 658             ssize_t ret = getrandom(((char*)seed) + offset, size - offset, flags);
 659             if (ret == -1) {
 660                 ATOMIC_SET(try_syscall, 0);
 661                 return -1;
 662             }
 663             offset += (size_t)ret;
 664         } while (offset < size);
 665         return 0;
 666     }
 667     return -1;
 668 }
 669 #else
 670 # define fill_random_bytes_syscall(seed, size, need_secure) -1
 671 #endif
 672
 673 int
 674 ruby_fill_random_bytes(void *seed, size_t size, int need_secure)
 675 {
 676     int ret = fill_random_bytes_syscall(seed, size, need_secure);
 677     if (ret == 0) return ret;
 678     return fill_random_bytes_urandom(seed, size);
 679 }
 680
 681 /* cnt must be 4 or more */
 682 static void
 683 fill_random_seed(uint32_t *seed, size_t cnt, bool try_bytes)
 684 {
 685     static rb_atomic_t n = 0;
 686 #if defined HAVE_CLOCK_GETTIME
 687     struct timespec tv;
 688 #elif defined HAVE_GETTIMEOFDAY
 689     struct timeval tv;
 690 #endif
 691     size_t len = cnt * sizeof(*seed);
 692
 693     if (try_bytes) {
 694         fill_random_bytes(seed, len, FALSE);
 695         return;
 696     }
 697
 698     memset(seed, 0, len);
 699 #if defined HAVE_CLOCK_GETTIME
 700     clock_gettime(CLOCK_REALTIME, &tv);
 701     seed[0] ^= tv.tv_nsec;
 702 #elif defined HAVE_GETTIMEOFDAY
 703     gettimeofday(&tv, 0);
 704     seed[0] ^= tv.tv_usec;
 705 #endif
 706     seed[1] ^= (uint32_t)tv.tv_sec;
 707 #if SIZEOF_TIME_T > SIZEOF_INT
 708     seed[0] ^= (uint32_t)((time_t)tv.tv_sec >> SIZEOF_INT * CHAR_BIT);
 709 #endif
 710     seed[2] ^= getpid() ^ (ATOMIC_FETCH_ADD(n, 1) << 16);
 711     seed[3] ^= (uint32_t)(VALUE)&seed;
 712 #if SIZEOF_VOIDP > SIZEOF_INT
 713     seed[2] ^= (uint32_t)((VALUE)&seed >> SIZEOF_INT * CHAR_BIT);
 714 #endif
 715 }
 716
 717 static VALUE
 718 make_seed_value(uint32_t *ptr, size_t len)
 719 {
 720     VALUE seed;
 721
 722     if (ptr[len-1] <= 1) {
 723         /* set leading-zero-guard */
 724         ptr[len++] = 1;
 725     }
 726
 727     seed = rb_integer_unpack(ptr, len, sizeof(uint32_t), 0,
 728         INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER);
 729
 730     return seed;
 731 }
 732
 733 #define with_random_seed(size, add, try_bytes) \
 734     for (uint32_t seedbuf[(size)+(add)], loop = (fill_random_seed(seedbuf, (size), try_bytes), 1); \
 735          loop; explicit_bzero(seedbuf, (size)*sizeof(seedbuf[0])), loop = 0)
 736
 737 /*
 738  * call-seq: Random.new_seed -> integer
 739  *
 740  * Returns an arbitrary seed value. This is used by Random.new
 741  * when no seed value is specified as an argument.
 742  *
 743  *   Random.new_seed  #=> 115032730400174366788466674494640623225
 744  */
 745 static VALUE
 746 random_seed(VALUE _)
 747 {
 748     VALUE v;
 749     with_random_seed(DEFAULT_SEED_CNT, 1, true) {
 750         v = make_seed_value(seedbuf, DEFAULT_SEED_CNT);
 751     }
 752     return v;
 753 }
 754
 755 /*
 756  * call-seq: Random.urandom(size) -> string
 757  *
 758  * Returns a string, using platform providing features.
 759  * Returned value is expected to be a cryptographically secure
 760  * pseudo-random number in binary form.
 761  * This method raises a RuntimeError if the feature provided by platform
 762  * failed to prepare the result.
 763  *
 764  * In 2017, Linux manpage random(7) writes that "no cryptographic
 765  * primitive available today can hope to promise more than 256 bits of
 766  * security".  So it might be questionable to pass size > 32 to this
 767  * method.
 768  *
 769  *   Random.urandom(8)  #=> "\x78\x41\xBA\xAF\x7D\xEA\xD8\xEA"
 770  */
 771 static VALUE
 772 random_raw_seed(VALUE self, VALUE size)
 773 {
 774     long n = NUM2ULONG(size);
 775     VALUE buf = rb_str_new(0, n);
 776     if (n == 0) return buf;
 777     if (fill_random_bytes(RSTRING_PTR(buf), n, TRUE))
 778         rb_raise(rb_eRuntimeError, "failed to get urandom");
 779     return buf;
 780 }
 781
 782 /*
 783  * call-seq: prng.seed -> integer
 784  *
 785  * Returns the seed value used to initialize the generator. This may be used to
 786  * initialize another generator with the same state at a later time, causing it
 787  * to produce the same sequence of numbers.
 788  *
 789  *   prng1 = Random.new(1234)
 790  *   prng1.seed       #=> 1234
 791  *   prng1.rand(100)  #=> 47
 792  *
 793  *   prng2 = Random.new(prng1.seed)
 794  *   prng2.rand(100)  #=> 47
 795  */
 796 static VALUE
 797 random_get_seed(VALUE obj)
 798 {
 799     return get_rnd(obj)->seed;
 800 }
 801
 802 /* :nodoc: */
 803 static VALUE
 804 rand_mt_copy(VALUE obj, VALUE orig)
 805 {
 806     rb_random_mt_t *rnd1, *rnd2;
 807     struct MT *mt;
 808
 809     if (!OBJ_INIT_COPY(obj, orig)) return obj;
 810
 811     rnd1 = get_rnd_mt(obj);
 812     rnd2 = get_rnd_mt(orig);
 813     mt = &rnd1->mt;
 814
 815     *rnd1 = *rnd2;
 816     mt->next = mt->state + numberof(mt->state) - mt->left + 1;
 817     return obj;
 818 }
 819
 820 static VALUE
 821 mt_state(const struct MT *mt)
 822 {
 823     return rb_integer_unpack(mt->state, numberof(mt->state),
 824         sizeof(*mt->state), 0,
 825         INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER);
 826 }
 827
 828 /* :nodoc: */
 829 static VALUE
 830 rand_mt_state(VALUE obj)
 831 {
 832     rb_random_mt_t *rnd = get_rnd_mt(obj);
 833     return mt_state(&rnd->mt);
 834 }
 835
 836 /* :nodoc: */
 837 static VALUE
 838 random_s_state(VALUE klass)
 839 {
 840     return mt_state(&default_rand()->mt);
 841 }
 842
 843 /* :nodoc: */
 844 static VALUE
 845 rand_mt_left(VALUE obj)
 846 {
 847     rb_random_mt_t *rnd = get_rnd_mt(obj);
 848     return INT2FIX(rnd->mt.left);
 849 }
 850
 851 /* :nodoc: */
 852 static VALUE
 853 random_s_left(VALUE klass)
 854 {
 855     return INT2FIX(default_rand()->mt.left);
 856 }
 857
 858 /* :nodoc: */
 859 static VALUE
 860 rand_mt_dump(VALUE obj)
 861 {
 862     rb_random_mt_t *rnd = rb_check_typeddata(obj, &random_mt_type);
 863     VALUE dump = rb_ary_new2(3);
 864
 865     rb_ary_push(dump, mt_state(&rnd->mt));
 866     rb_ary_push(dump, INT2FIX(rnd->mt.left));
 867     rb_ary_push(dump, rnd->base.seed);
 868
 869     return dump;
 870 }
 871
 872 /* :nodoc: */
 873 static VALUE
 874 rand_mt_load(VALUE obj, VALUE dump)
 875 {
 876     rb_random_mt_t *rnd = rb_check_typeddata(obj, &random_mt_type);
 877     struct MT *mt = &rnd->mt;
 878     VALUE state, left = INT2FIX(1), seed = INT2FIX(0);
 879     unsigned long x;
 880
 881     rb_check_copyable(obj, dump);
 882     Check_Type(dump, T_ARRAY);
 883     switch (RARRAY_LEN(dump)) {
 884       case 3:
 885         seed = RARRAY_AREF(dump, 2);
 886       case 2:
 887         left = RARRAY_AREF(dump, 1);
 888       case 1:
 889         state = RARRAY_AREF(dump, 0);
 890         break;
 891       default:
 892         rb_raise(rb_eArgError, "wrong dump data");
 893     }
 894     rb_integer_pack(state, mt->state, numberof(mt->state),
 895         sizeof(*mt->state), 0,
 896         INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER);
 897     x = NUM2ULONG(left);
 898     if (x > numberof(mt->state)) {
 899         rb_raise(rb_eArgError, "wrong value");
 900     }
 901     mt->left = (unsigned int)x;
 902     mt->next = mt->state + numberof(mt->state) - x + 1;
 903     rnd->base.seed = rb_to_int(seed);
 904
 905     return obj;
 906 }
 907
 908 static void
 909 rand_mt_init_int32(rb_random_t *rnd, uint32_t data)
 910 {
 911     struct MT *mt = &((rb_random_mt_t *)rnd)->mt;
 912     init_genrand(mt, data);
 913 }
 914
 915 static void
 916 rand_mt_init(rb_random_t *rnd, const uint32_t *buf, size_t len)
 917 {
 918     struct MT *mt = &((rb_random_mt_t *)rnd)->mt;
 919     init_by_array(mt, buf, (int)len);
 920 }
 921
 922 static unsigned int
 923 rand_mt_get_int32(rb_random_t *rnd)
 924 {
 925     struct MT *mt = &((rb_random_mt_t *)rnd)->mt;
 926     return genrand_int32(mt);
 927 }
 928
 929 static void
 930 rand_mt_get_bytes(rb_random_t *rnd, void *ptr, size_t n)
 931 {
 932     rb_rand_bytes_int32(rand_mt_get_int32, rnd, ptr, n);
 933 }
 934
 935 /*
 936  * call-seq:
 937  *   srand(number = Random.new_seed) -> old_seed
 938  *
 939  * Seeds the system pseudo-random number generator, with +number+.
 940  * The previous seed value is returned.
 941  *
 942  * If +number+ is omitted, seeds the generator using a source of entropy
 943  * provided by the operating system, if available (/dev/urandom on Unix systems
 944  * or the RSA cryptographic provider on Windows), which is then combined with
 945  * the time, the process id, and a sequence number.
 946  *
 947  * srand may be used to ensure repeatable sequences of pseudo-random numbers
 948  * between different runs of the program. By setting the seed to a known value,
 949  * programs can be made deterministic during testing.
 950  *
 951  *   srand 1234               # => 268519324636777531569100071560086917274
 952  *   [ rand, rand ]           # => [0.1915194503788923, 0.6221087710398319]
 953  *   [ rand(10), rand(1000) ] # => [4, 664]
 954  *   srand 1234               # => 1234
 955  *   [ rand, rand ]           # => [0.1915194503788923, 0.6221087710398319]
 956  */
 957
 958 static VALUE
 959 rb_f_srand(int argc, VALUE *argv, VALUE obj)
 960 {
 961     VALUE seed, old;
 962     rb_random_mt_t *r = rand_mt_start(default_rand());
 963
 964     if (rb_check_arity(argc, 0, 1) == 0) {
 965         seed = random_seed(obj);
 966     }
 967     else {
 968         seed = rb_to_int(argv[0]);
 969     }
 970     old = r->base.seed;
 971     rand_init(&random_mt_if, &r->base, seed);
 972     r->base.seed = seed;
 973
 974     return old;
 975 }
 976
 977 static unsigned long
 978 make_mask(unsigned long x)
 979 {
 980     x = x | x >> 1;
 981     x = x | x >> 2;
 982     x = x | x >> 4;
 983     x = x | x >> 8;
 984     x = x | x >> 16;
 985 #if 4 < SIZEOF_LONG
 986     x = x | x >> 32;
 987 #endif
 988     return x;
 989 }
 990
 991 static unsigned long
 992 limited_rand(const rb_random_interface_t *rng, rb_random_t *rnd, unsigned long limit)
 993 {
 994     /* mt must be initialized */
 995     unsigned long val, mask;
 996
 997     if (!limit) return 0;
 998     mask = make_mask(limit);
 999
1000 #if 4 < SIZEOF_LONG
1001     if (0xffffffff < limit) {
1002         int i;
1003       retry:
1004         val = 0;
1005         for (i = SIZEOF_LONG/SIZEOF_INT32-1; 0 <= i; i--) {
1006             if ((mask >> (i * 32)) & 0xffffffff) {
1007                 val |= (unsigned long)rng->get_int32(rnd) << (i * 32);
1008                 val &= mask;
1009                 if (limit < val)
1010                     goto retry;
1011             }
1012         }
1013         return val;
1014     }
1015 #endif
1016
1017     do {
1018         val = rng->get_int32(rnd) & mask;
1019     } while (limit < val);
1020     return val;
1021 }
1022
1023 static VALUE
1024 limited_big_rand(const rb_random_interface_t *rng, rb_random_t *rnd, VALUE limit)
1025 {
1026     /* mt must be initialized */
1027
1028     uint32_t mask;
1029     long i;
1030     int boundary;
1031
1032     size_t len;
1033     uint32_t *tmp, *lim_array, *rnd_array;
1034     VALUE vtmp;
1035     VALUE val;
1036
1037     len = rb_absint_numwords(limit, 32, NULL);
1038     tmp = ALLOCV_N(uint32_t, vtmp, len*2);
1039     lim_array = tmp;
1040     rnd_array = tmp + len;
1041     rb_integer_pack(limit, lim_array, len, sizeof(uint32_t), 0,
1042         INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER);
1043
1044   retry:
1045     mask = 0;
1046     boundary = 1;
1047     for (i = len-1; 0 <= i; i--) {
1048         uint32_t r = 0;
1049         uint32_t lim = lim_array[i];
1050         mask = mask ? 0xffffffff : (uint32_t)make_mask(lim);
1051         if (mask) {
1052             r = rng->get_int32(rnd) & mask;
1053             if (boundary) {
1054                 if (lim < r)
1055                     goto retry;
1056                 if (r < lim)
1057                     boundary = 0;
1058             }
1059         }
1060         rnd_array[i] = r;
1061     }
1062     val = rb_integer_unpack(rnd_array, len, sizeof(uint32_t), 0,
1063         INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER);
1064     ALLOCV_END(vtmp);
1065
1066     return val;
1067 }
1068
1069 /*
1070  * Returns random unsigned long value in [0, +limit+].
1071  *
1072  * Note that +limit+ is included, and the range of the argument and the
1073  * return value depends on environments.
1074  */
1075 unsigned long
1076 rb_genrand_ulong_limited(unsigned long limit)
1077 {
1078     rb_random_mt_t *mt = default_mt();
1079     return limited_rand(&random_mt_if, &mt->base, limit);
1080 }
1081
1082 static VALUE
1083 obj_random_bytes(VALUE obj, void *p, long n)
1084 {
1085     VALUE len = LONG2NUM(n);
1086     VALUE v = rb_funcallv_public(obj, id_bytes, 1, &len);
1087     long l;
1088     Check_Type(v, T_STRING);
1089     l = RSTRING_LEN(v);
1090     if (l < n)
1091         rb_raise(rb_eRangeError, "random data too short %ld", l);
1092     else if (l > n)
1093         rb_raise(rb_eRangeError, "random data too long %ld", l);
1094     if (p) memcpy(p, RSTRING_PTR(v), n);
1095     return v;
1096 }
1097
1098 static unsigned int
1099 random_int32(const rb_random_interface_t *rng, rb_random_t *rnd)
1100 {
1101     return rng->get_int32(rnd);
1102 }
1103
1104 unsigned int
1105 rb_random_int32(VALUE obj)
1106 {
1107     rb_random_t *rnd = try_get_rnd(obj);
1108     if (!rnd) {
1109         uint32_t x;
1110         obj_random_bytes(obj, &x, sizeof(x));
1111         return (unsigned int)x;
1112     }
1113     return random_int32(try_rand_if(obj, rnd), rnd);
1114 }
1115
1116 static double
1117 random_real(VALUE obj, rb_random_t *rnd, int excl)
1118 {
1119     uint32_t a, b;
1120
1121     if (!rnd) {
1122         uint32_t x[2] = {0, 0};
1123         obj_random_bytes(obj, x, sizeof(x));
1124         a = x[0];
1125         b = x[1];
1126     }
1127     else {
1128         const rb_random_interface_t *rng = try_rand_if(obj, rnd);
1129         if (rng->get_real) return rng->get_real(rnd, excl);
1130         a = random_int32(rng, rnd);
1131         b = random_int32(rng, rnd);
1132     }
1133     return rb_int_pair_to_real(a, b, excl);
1134 }
1135
1136 double
1137 rb_int_pair_to_real(uint32_t a, uint32_t b, int excl)
1138 {
1139     if (excl) {
1140         return int_pair_to_real_exclusive(a, b);
1141     }
1142     else {
1143         return int_pair_to_real_inclusive(a, b);
1144     }
1145 }
1146
1147 double
1148 rb_random_real(VALUE obj)
1149 {
1150     rb_random_t *rnd = try_get_rnd(obj);
1151     if (!rnd) {
1152         VALUE v = rb_funcallv(obj, id_rand, 0, 0);
1153         double d = NUM2DBL(v);
1154         if (d < 0.0) {
1155             rb_raise(rb_eRangeError, "random number too small %g", d);
1156         }
1157         else if (d >= 1.0) {
1158             rb_raise(rb_eRangeError, "random number too big %g", d);
1159         }
1160         return d;
1161     }
1162     return random_real(obj, rnd, TRUE);
1163 }
1164
1165 static inline VALUE
1166 ulong_to_num_plus_1(unsigned long n)
1167 {
1168 #if HAVE_LONG_LONG
1169     return ULL2NUM((LONG_LONG)n+1);
1170 #else
1171     if (n >= ULONG_MAX) {
1172         return rb_big_plus(ULONG2NUM(n), INT2FIX(1));
1173     }
1174     return ULONG2NUM(n+1);
1175 #endif
1176 }
1177
1178 static unsigned long
1179 random_ulong_limited(VALUE obj, rb_random_t *rnd, unsigned long limit)
1180 {
1181     if (!limit) return 0;
1182     if (!rnd) {
1183         const int w = sizeof(limit) * CHAR_BIT - nlz_long(limit);
1184         const int n = w > 32 ? sizeof(unsigned long) : sizeof(uint32_t);
1185         const unsigned long mask = ~(~0UL << w);
1186         const unsigned long full =
1187             (size_t)n >= sizeof(unsigned long) ? ~0UL :
1188             ~(~0UL << n * CHAR_BIT);
1189         unsigned long val, bits = 0, rest = 0;
1190         do {
1191             if (mask & ~rest) {
1192                 union {uint32_t u32; unsigned long ul;} buf;
1193                 obj_random_bytes(obj, &buf, n);
1194                 rest = full;
1195                 bits = (n == sizeof(uint32_t)) ? buf.u32 : buf.ul;
1196             }
1197             val = bits;
1198             bits >>= w;
1199             rest >>= w;
1200             val &= mask;
1201         } while (limit < val);
1202         return val;
1203     }
1204     return limited_rand(try_rand_if(obj, rnd), rnd, limit);
1205 }
1206
1207 unsigned long
1208 rb_random_ulong_limited(VALUE obj, unsigned long limit)
1209 {
1210     rb_random_t *rnd = try_get_rnd(obj);
1211     if (!rnd) {
1212         VALUE lim = ulong_to_num_plus_1(limit);
1213         VALUE v = rb_to_int(rb_funcallv_public(obj, id_rand, 1, &lim));
1214         unsigned long r = NUM2ULONG(v);
1215         if (rb_num_negative_p(v)) {
1216             rb_raise(rb_eRangeError, "random number too small %ld", r);
1217         }
1218         if (r > limit) {
1219             rb_raise(rb_eRangeError, "random number too big %ld", r);
1220         }
1221         return r;
1222     }
1223     return limited_rand(try_rand_if(obj, rnd), rnd, limit);
1224 }
1225
1226 static VALUE
1227 random_ulong_limited_big(VALUE obj, rb_random_t *rnd, VALUE vmax)
1228 {
1229     if (!rnd) {
1230         VALUE v, vtmp;
1231         size_t i, nlz, len = rb_absint_numwords(vmax, 32, &nlz);
1232         uint32_t *tmp = ALLOCV_N(uint32_t, vtmp, len * 2);
1233         uint32_t mask = (uint32_t)~0 >> nlz;
1234         uint32_t *lim_array = tmp;
1235         uint32_t *rnd_array = tmp + len;
1236         int flag = INTEGER_PACK_MSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER;
1237         rb_integer_pack(vmax, lim_array, len, sizeof(uint32_t), 0, flag);
1238
1239       retry:
1240         obj_random_bytes(obj, rnd_array, len * sizeof(uint32_t));
1241         rnd_array[0] &= mask;
1242         for (i = 0; i < len; ++i) {
1243             if (lim_array[i] < rnd_array[i])
1244                 goto retry;
1245             if (rnd_array[i] < lim_array[i])
1246                 break;
1247         }
1248         v = rb_integer_unpack(rnd_array, len, sizeof(uint32_t), 0, flag);
1249         ALLOCV_END(vtmp);
1250         return v;
1251     }
1252     return limited_big_rand(try_rand_if(obj, rnd), rnd, vmax);
1253 }
1254
1255 static VALUE
1256 rand_bytes(const rb_random_interface_t *rng, rb_random_t *rnd, long n)
1257 {
1258     VALUE bytes;
1259     char *ptr;
1260
1261     bytes = rb_str_new(0, n);
1262     ptr = RSTRING_PTR(bytes);
1263     rng->get_bytes(rnd, ptr, n);
1264     return bytes;
1265 }
1266
1267 /*
1268  * call-seq: prng.bytes(size) -> string
1269  *
1270  * Returns a random binary string containing +size+ bytes.
1271  *
1272  *   random_string = Random.new.bytes(10) # => "\xD7:R\xAB?\x83\xCE\xFAkO"
1273  *   random_string.size                   # => 10
1274  */
1275 static VALUE
1276 random_bytes(VALUE obj, VALUE len)
1277 {
1278     rb_random_t *rnd = try_get_rnd(obj);
1279     return rand_bytes(rb_rand_if(obj), rnd, NUM2LONG(rb_to_int(len)));
1280 }
1281
1282 void
1283 rb_rand_bytes_int32(rb_random_get_int32_func *get_int32,
1284                     rb_random_t *rnd, void *p, size_t n)
1285 {
1286     char *ptr = p;
1287     unsigned int r, i;
1288     for (; n >= SIZEOF_INT32; n -= SIZEOF_INT32) {
1289         r = get_int32(rnd);
1290         i = SIZEOF_INT32;
1291         do {
1292             *ptr++ = (char)r;
1293             r >>= CHAR_BIT;
1294         } while (--i);
1295     }
1296     if (n > 0) {
1297         r = get_int32(rnd);
1298         do {
1299             *ptr++ = (char)r;
1300             r >>= CHAR_BIT;
1301         } while (--n);
1302     }
1303 }
1304
1305 VALUE
1306 rb_random_bytes(VALUE obj, long n)
1307 {
1308     rb_random_t *rnd = try_get_rnd(obj);
1309     if (!rnd) {
1310         return obj_random_bytes(obj, NULL, n);
1311     }
1312     return rand_bytes(try_rand_if(obj, rnd), rnd, n);
1313 }
1314
1315 /*
1316  * call-seq: Random.bytes(size) -> string
1317  *
1318  * Returns a random binary string.
1319  * The argument +size+ specifies the length of the returned string.
1320  */
1321 static VALUE
1322 random_s_bytes(VALUE obj, VALUE len)
1323 {
1324     rb_random_t *rnd = rand_start(default_rand());
1325     return rand_bytes(&random_mt_if, rnd, NUM2LONG(rb_to_int(len)));
1326 }
1327
1328 /*
1329  * call-seq: Random.seed -> integer
1330  *
1331  * Returns the seed value used to initialize the Ruby system PRNG.
1332  * This may be used to initialize another generator with the same
1333  * state at a later time, causing it to produce the same sequence of
1334  * numbers.
1335  *
1336  *   Random.seed      #=> 1234
1337  *   prng1 = Random.new(Random.seed)
1338  *   prng1.seed       #=> 1234
1339  *   prng1.rand(100)  #=> 47
1340  *   Random.seed      #=> 1234
1341  *   Random.rand(100) #=> 47
1342  */
1343 static VALUE
1344 random_s_seed(VALUE obj)
1345 {
1346     rb_random_mt_t *rnd = rand_mt_start(default_rand());
1347     return rnd->base.seed;
1348 }
1349
1350 static VALUE
1351 range_values(VALUE vmax, VALUE *begp, VALUE *endp, int *exclp)
1352 {
1353     VALUE beg, end;
1354
1355     if (!rb_range_values(vmax, &beg, &end, exclp)) return Qfalse;
1356     if (begp) *begp = beg;
1357     if (NIL_P(beg)) return Qnil;
1358     if (endp) *endp = end;
1359     if (NIL_P(end)) return Qnil;
1360     return rb_check_funcall_default(end, id_minus, 1, begp, Qfalse);
1361 }
1362
1363 static VALUE
1364 rand_int(VALUE obj, rb_random_t *rnd, VALUE vmax, int restrictive)
1365 {
1366     /* mt must be initialized */
1367     unsigned long r;
1368
1369     if (FIXNUM_P(vmax)) {
1370         long max = FIX2LONG(vmax);
1371         if (!max) return Qnil;
1372         if (max < 0) {
1373             if (restrictive) return Qnil;
1374             max = -max;
1375         }
1376         r = random_ulong_limited(obj, rnd, (unsigned long)max - 1);
1377         return ULONG2NUM(r);
1378     }
1379     else {
1380         VALUE ret;
1381         if (rb_bigzero_p(vmax)) return Qnil;
1382         if (!BIGNUM_SIGN(vmax)) {
1383             if (restrictive) return Qnil;
1384             vmax = rb_big_uminus(vmax);
1385         }
1386         vmax = rb_big_minus(vmax, INT2FIX(1));
1387         if (FIXNUM_P(vmax)) {
1388             long max = FIX2LONG(vmax);
1389             if (max == -1) return Qnil;
1390             r = random_ulong_limited(obj, rnd, max);
1391             return LONG2NUM(r);
1392         }
1393         ret = random_ulong_limited_big(obj, rnd, vmax);
1394         RB_GC_GUARD(vmax);
1395         return ret;
1396     }
1397 }
1398
1399 static void
1400 domain_error(void)
1401 {
1402     VALUE error = INT2FIX(EDOM);
1403     rb_exc_raise(rb_class_new_instance(1, &error, rb_eSystemCallError));
1404 }
1405
1406 NORETURN(static void invalid_argument(VALUE));
1407 static void
1408 invalid_argument(VALUE arg0)
1409 {
1410     rb_raise(rb_eArgError, "invalid argument - %"PRIsVALUE, arg0);
1411 }
1412
1413 static VALUE
1414 check_random_number(VALUE v, const VALUE *argv)
1415 {
1416     switch (v) {
1417       case Qfalse:
1418         (void)NUM2LONG(argv[0]);
1419         break;
1420       case Qnil:
1421         invalid_argument(argv[0]);
1422     }
1423     return v;
1424 }
1425
1426 static inline double
1427 float_value(VALUE v)
1428 {
1429     double x = RFLOAT_VALUE(v);
1430     if (!isfinite(x)) {
1431         domain_error();
1432     }
1433     return x;
1434 }
1435
1436 static inline VALUE
1437 rand_range(VALUE obj, rb_random_t* rnd, VALUE range)
1438 {
1439     VALUE beg = Qundef, end = Qundef, vmax, v;
1440     int excl = 0;
1441
1442     if ((v = vmax = range_values(range, &beg, &end, &excl)) == Qfalse)
1443         return Qfalse;
1444     if (NIL_P(v)) domain_error();
1445     if (!RB_FLOAT_TYPE_P(vmax) && (v = rb_check_to_int(vmax), !NIL_P(v))) {
1446         long max;
1447         vmax = v;
1448         v = Qnil;
1449       fixnum:
1450         if (FIXNUM_P(vmax)) {
1451             if ((max = FIX2LONG(vmax) - excl) >= 0) {
1452                 unsigned long r = random_ulong_limited(obj, rnd, (unsigned long)max);
1453                 v = ULONG2NUM(r);
1454             }
1455         }
1456         else if (BUILTIN_TYPE(vmax) == T_BIGNUM && BIGNUM_SIGN(vmax) && !rb_bigzero_p(vmax)) {
1457             vmax = excl ? rb_big_minus(vmax, INT2FIX(1)) : rb_big_norm(vmax);
1458             if (FIXNUM_P(vmax)) {
1459                 excl = 0;
1460                 goto fixnum;
1461             }
1462             v = random_ulong_limited_big(obj, rnd, vmax);
1463         }
1464     }
1465     else if (v = rb_check_to_float(vmax), !NIL_P(v)) {
1466         int scale = 1;
1467         double max = RFLOAT_VALUE(v), mid = 0.5, r;
1468         if (isinf(max)) {
1469             double min = float_value(rb_to_float(beg)) / 2.0;
1470             max = float_value(rb_to_float(end)) / 2.0;
1471             scale = 2;
1472             mid = max + min;
1473             max -= min;
1474         }
1475         else if (isnan(max)) {
1476             domain_error();
1477         }
1478         v = Qnil;
1479         if (max > 0.0) {
1480             r = random_real(obj, rnd, excl);
1481             if (scale > 1) {
1482                 return rb_float_new(+(+(+(r - 0.5) * max) * scale) + mid);
1483             }
1484             v = rb_float_new(r * max);
1485         }
1486         else if (max == 0.0 && !excl) {
1487             v = rb_float_new(0.0);
1488         }
1489     }
1490
1491     if (FIXNUM_P(beg) && FIXNUM_P(v)) {
1492         long x = FIX2LONG(beg) + FIX2LONG(v);
1493         return LONG2NUM(x);
1494     }
1495     switch (TYPE(v)) {
1496       case T_NIL:
1497         break;
1498       case T_BIGNUM:
1499         return rb_big_plus(v, beg);
1500       case T_FLOAT: {
1501         VALUE f = rb_check_to_float(beg);
1502         if (!NIL_P(f)) {
1503             return DBL2NUM(RFLOAT_VALUE(v) + RFLOAT_VALUE(f));
1504         }
1505       }
1506       default:
1507         return rb_funcallv(beg, id_plus, 1, &v);
1508     }
1509
1510     return v;
1511 }
1512
1513 static VALUE rand_random(int argc, VALUE *argv, VALUE obj, rb_random_t *rnd);
1514
1515 /*
1516  * call-seq:
1517  *   prng.rand -> float
1518  *   prng.rand(max) -> number
1519  *   prng.rand(range) -> number
1520  *
1521  * When +max+ is an Integer, +rand+ returns a random integer greater than
1522  * or equal to zero and less than +max+. Unlike Kernel.rand, when +max+
1523  * is a negative integer or zero, +rand+ raises an ArgumentError.
1524  *
1525  *   prng = Random.new
1526  *   prng.rand(100)       # => 42
1527  *
1528  * When +max+ is a Float, +rand+ returns a random floating point number
1529  * between 0.0 and +max+, including 0.0 and excluding +max+.
1530  *
1531  *   prng.rand(1.5)       # => 1.4600282860034115
1532  *
1533  * When +range+ is a Range, +rand+ returns a random number where
1534  * <code>range.member?(number) == true</code>.
1535  *
1536  *   prng.rand(5..9)      # => one of [5, 6, 7, 8, 9]
1537  *   prng.rand(5...9)     # => one of [5, 6, 7, 8]
1538  *   prng.rand(5.0..9.0)  # => between 5.0 and 9.0, including 9.0
1539  *   prng.rand(5.0...9.0) # => between 5.0 and 9.0, excluding 9.0
1540  *
1541  * Both the beginning and ending values of the range must respond to subtract
1542  * (<tt>-</tt>) and add (<tt>+</tt>)methods, or rand will raise an
1543  * ArgumentError.
1544  */
1545 static VALUE
1546 random_rand(int argc, VALUE *argv, VALUE obj)
1547 {
1548     VALUE v = rand_random(argc, argv, obj, try_get_rnd(obj));
1549     check_random_number(v, argv);
1550     return v;
1551 }
1552
1553 static VALUE
1554 rand_random(int argc, VALUE *argv, VALUE obj, rb_random_t *rnd)
1555 {
1556     VALUE vmax, v;
1557
1558     if (rb_check_arity(argc, 0, 1) == 0) {
1559         return rb_float_new(random_real(obj, rnd, TRUE));
1560     }
1561     vmax = argv[0];
1562     if (NIL_P(vmax)) return Qnil;
1563     if (!RB_FLOAT_TYPE_P(vmax)) {
1564         v = rb_check_to_int(vmax);
1565         if (!NIL_P(v)) return rand_int(obj, rnd, v, 1);
1566     }
1567     v = rb_check_to_float(vmax);
1568     if (!NIL_P(v)) {
1569         const double max = float_value(v);
1570         if (max < 0.0) {
1571             return Qnil;
1572         }
1573         else {
1574             double r = random_real(obj, rnd, TRUE);
1575             if (max > 0.0) r *= max;
1576             return rb_float_new(r);
1577         }
1578     }
1579     return rand_range(obj, rnd, vmax);
1580 }
1581
1582 /*
1583  * call-seq:
1584  *   prng.random_number        -> float
1585  *   prng.random_number(max)   -> number
1586  *   prng.random_number(range) -> number
1587  *   prng.rand                 -> float
1588  *   prng.rand(max)            -> number
1589  *   prng.rand(range)          -> number
1590  *
1591  * Generates formatted random number from raw random bytes.
1592  * See Random#rand.
1593  */
1594 static VALUE
1595 rand_random_number(int argc, VALUE *argv, VALUE obj)
1596 {
1597     rb_random_t *rnd = try_get_rnd(obj);
1598     VALUE v = rand_random(argc, argv, obj, rnd);
1599     if (NIL_P(v)) v = rand_random(0, 0, obj, rnd);
1600     else if (!v) invalid_argument(argv[0]);
1601     return v;
1602 }
1603
1604 /*
1605  * call-seq:
1606  *   prng1 == prng2 -> true or false
1607  *
1608  * Returns true if the two generators have the same internal state, otherwise
1609  * false.  Equivalent generators will return the same sequence of
1610  * pseudo-random numbers.  Two generators will generally have the same state
1611  * only if they were initialized with the same seed
1612  *
1613  *   Random.new == Random.new             # => false
1614  *   Random.new(1234) == Random.new(1234) # => true
1615  *
1616  * and have the same invocation history.
1617  *
1618  *   prng1 = Random.new(1234)
1619  *   prng2 = Random.new(1234)
1620  *   prng1 == prng2 # => true
1621  *
1622  *   prng1.rand     # => 0.1915194503788923
1623  *   prng1 == prng2 # => false
1624  *
1625  *   prng2.rand     # => 0.1915194503788923
1626  *   prng1 == prng2 # => true
1627  */
1628 static VALUE
1629 rand_mt_equal(VALUE self, VALUE other)
1630 {
1631     rb_random_mt_t *r1, *r2;
1632     if (rb_obj_class(self) != rb_obj_class(other)) return Qfalse;
1633     r1 = get_rnd_mt(self);
1634     r2 = get_rnd_mt(other);
1635     if (memcmp(r1->mt.state, r2->mt.state, sizeof(r1->mt.state))) return Qfalse;
1636     if ((r1->mt.next - r1->mt.state) != (r2->mt.next - r2->mt.state)) return Qfalse;
1637     if (r1->mt.left != r2->mt.left) return Qfalse;
1638     return rb_equal(r1->base.seed, r2->base.seed);
1639 }
1640
1641 /*
1642  * call-seq:
1643  *   rand(max=0)    -> number
1644  *
1645  * If called without an argument, or if <tt>max.to_i.abs == 0</tt>, rand
1646  * returns a pseudo-random floating point number between 0.0 and 1.0,
1647  * including 0.0 and excluding 1.0.
1648  *
1649  *   rand        #=> 0.2725926052826416
1650  *
1651  * When +max.abs+ is greater than or equal to 1, +rand+ returns a pseudo-random
1652  * integer greater than or equal to 0 and less than +max.to_i.abs+.
1653  *
1654  *   rand(100)   #=> 12
1655  *
1656  * When +max+ is a Range, +rand+ returns a random number where
1657  * <code>range.member?(number) == true</code>.
1658  *
1659  * Negative or floating point values for +max+ are allowed, but may give
1660  * surprising results.
1661  *
1662  *   rand(-100) # => 87
1663  *   rand(-0.5) # => 0.8130921818028143
1664  *   rand(1.9)  # equivalent to rand(1), which is always 0
1665  *
1666  * Kernel.srand may be used to ensure that sequences of random numbers are
1667  * reproducible between different runs of a program.
1668  *
1669  * See also Random.rand.
1670  */
1671
1672 static VALUE
1673 rb_f_rand(int argc, VALUE *argv, VALUE obj)
1674 {
1675     VALUE vmax;
1676     rb_random_t *rnd = rand_start(default_rand());
1677
1678     if (rb_check_arity(argc, 0, 1) && !NIL_P(vmax = argv[0])) {
1679         VALUE v = rand_range(obj, rnd, vmax);
1680         if (v != Qfalse) return v;
1681         vmax = rb_to_int(vmax);
1682         if (vmax != INT2FIX(0)) {
1683             v = rand_int(obj, rnd, vmax, 0);
1684             if (!NIL_P(v)) return v;
1685         }
1686     }
1687     return DBL2NUM(random_real(obj, rnd, TRUE));
1688 }
1689
1690 /*
1691  * call-seq:
1692  *   Random.rand -> float
1693  *   Random.rand(max) -> number
1694  *   Random.rand(range) -> number
1695  *
1696  * Returns a random number using the Ruby system PRNG.
1697  *
1698  * See also Random#rand.
1699  */
1700 static VALUE
1701 random_s_rand(int argc, VALUE *argv, VALUE obj)
1702 {
1703     VALUE v = rand_random(argc, argv, Qnil, rand_start(default_rand()));
1704     check_random_number(v, argv);
1705     return v;
1706 }
1707
1708 #define SIP_HASH_STREAMING 0
1709 #define sip_hash13 ruby_sip_hash13
1710 #if !defined _WIN32 && !defined BYTE_ORDER
1711 # ifdef WORDS_BIGENDIAN
1712 #   define BYTE_ORDER BIG_ENDIAN
1713 # else
1714 #   define BYTE_ORDER LITTLE_ENDIAN
1715 # endif
1716 # ifndef LITTLE_ENDIAN
1717 #   define LITTLE_ENDIAN 1234
1718 # endif
1719 # ifndef BIG_ENDIAN
1720 #   define BIG_ENDIAN    4321
1721 # endif
1722 #endif
1723 #include "siphash.c"
1724
1725 typedef struct {
1726     st_index_t hash;
1727     uint8_t sip[16];
1728 } hash_salt_t;
1729
1730 static union {
1731     hash_salt_t key;
1732     uint32_t u32[type_roomof(hash_salt_t, uint32_t)];
1733 } hash_salt;
1734
1735 static void
1736 init_hash_salt(struct MT *mt)
1737 {
1738     int i;
1739
1740     for (i = 0; i < numberof(hash_salt.u32); ++i)
1741         hash_salt.u32[i] = genrand_int32(mt);
1742 }
1743
1744 NO_SANITIZE("unsigned-integer-overflow", extern st_index_t rb_hash_start(st_index_t h));
1745 st_index_t
1746 rb_hash_start(st_index_t h)
1747 {
1748     return st_hash_start(hash_salt.key.hash + h);
1749 }
1750
1751 st_index_t
1752 rb_memhash(const void *ptr, long len)
1753 {
1754     sip_uint64_t h = sip_hash13(hash_salt.key.sip, ptr, len);
1755 #ifdef HAVE_UINT64_T
1756     return (st_index_t)h;
1757 #else
1758     return (st_index_t)(h.u32[0] ^ h.u32[1]);
1759 #endif
1760 }
1761
1762 /* Initialize Ruby internal seeds. This function is called at very early stage
1763  * of Ruby startup. Thus, you can't use Ruby's object. */
1764 void
1765 Init_RandomSeedCore(void)
1766 {
1767     if (!fill_random_bytes(&hash_salt, sizeof(hash_salt), FALSE)) return;
1768
1769     /*
1770       If failed to fill siphash's salt with random data, expand less random
1771       data with MT.
1772
1773       Don't reuse this MT for default_rand(). default_rand()::seed shouldn't
1774       provide a hint that an attacker guess siphash's seed.
1775     */
1776     struct MT mt;
1777
1778     with_random_seed(DEFAULT_SEED_CNT, 0, false) {
1779         init_by_array(&mt, seedbuf, DEFAULT_SEED_CNT);
1780     }
1781
1782     init_hash_salt(&mt);
1783     explicit_bzero(&mt, sizeof(mt));
1784 }
1785
1786 void
1787 rb_reset_random_seed(void)
1788 {
1789     rb_random_mt_t *r = default_rand();
1790     uninit_genrand(&r->mt);
1791     r->base.seed = INT2FIX(0);
1792 }
1793
1794 /*
1795  * Document-class: Random
1796  *
1797  * Random provides an interface to Ruby's pseudo-random number generator, or
1798  * PRNG.  The PRNG produces a deterministic sequence of bits which approximate
1799  * true randomness. The sequence may be represented by integers, floats, or
1800  * binary strings.
1801  *
1802  * The generator may be initialized with either a system-generated or
1803  * user-supplied seed value by using Random.srand.
1804  *
1805  * The class method Random.rand provides the base functionality of Kernel.rand
1806  * along with better handling of floating point values. These are both
1807  * interfaces to the Ruby system PRNG.
1808  *
1809  * Random.new will create a new PRNG with a state independent of the Ruby
1810  * system PRNG, allowing multiple generators with different seed values or
1811  * sequence positions to exist simultaneously. Random objects can be
1812  * marshaled, allowing sequences to be saved and resumed.
1813  *
1814  * PRNGs are currently implemented as a modified Mersenne Twister with a period
1815  * of 2**19937-1.  As this algorithm is _not_ for cryptographical use, you must
1816  * use SecureRandom for security purpose, instead of this PRNG.
1817  *
1818  * See also Random::Formatter module that adds convenience methods to generate
1819  * various forms of random data.
1820  */
1821
1822 void
1823 InitVM_Random(void)
1824 {
1825     VALUE base;
1826     ID id_base = rb_intern_const("Base");
1827
1828     rb_define_global_function("srand", rb_f_srand, -1);
1829     rb_define_global_function("rand", rb_f_rand, -1);
1830
1831     base = rb_define_class_id(id_base, rb_cObject);
1832     rb_undef_alloc_func(base);
1833     rb_cRandom = rb_define_class("Random", base);
1834     rb_const_set(rb_cRandom, id_base, base);
1835     rb_define_alloc_func(rb_cRandom, random_alloc);
1836     rb_define_method(base, "initialize", random_init, -1);
1837     rb_define_method(base, "rand", random_rand, -1);
1838     rb_define_method(base, "bytes", random_bytes, 1);
1839     rb_define_method(base, "seed", random_get_seed, 0);
1840     rb_define_method(rb_cRandom, "initialize_copy", rand_mt_copy, 1);
1841     rb_define_private_method(rb_cRandom, "marshal_dump", rand_mt_dump, 0);
1842     rb_define_private_method(rb_cRandom, "marshal_load", rand_mt_load, 1);
1843     rb_define_private_method(rb_cRandom, "state", rand_mt_state, 0);
1844     rb_define_private_method(rb_cRandom, "left", rand_mt_left, 0);
1845     rb_define_method(rb_cRandom, "==", rand_mt_equal, 1);
1846
1847 #if 0 /* for RDoc: it can't handle unnamed base class */
1848     rb_define_method(rb_cRandom, "initialize", random_init, -1);
1849     rb_define_method(rb_cRandom, "rand", random_rand, -1);
1850     rb_define_method(rb_cRandom, "bytes", random_bytes, 1);
1851     rb_define_method(rb_cRandom, "seed", random_get_seed, 0);
1852 #endif
1853
1854     rb_define_singleton_method(rb_cRandom, "srand", rb_f_srand, -1);
1855     rb_define_singleton_method(rb_cRandom, "rand", random_s_rand, -1);
1856     rb_define_singleton_method(rb_cRandom, "bytes", random_s_bytes, 1);
1857     rb_define_singleton_method(rb_cRandom, "seed", random_s_seed, 0);
1858     rb_define_singleton_method(rb_cRandom, "new_seed", random_seed, 0);
1859     rb_define_singleton_method(rb_cRandom, "urandom", random_raw_seed, 1);
1860     rb_define_private_method(CLASS_OF(rb_cRandom), "state", random_s_state, 0);
1861     rb_define_private_method(CLASS_OF(rb_cRandom), "left", random_s_left, 0);
1862
1863     {
1864         /*
1865          * Generate a random number in the given range as Random does
1866          *
1867          *   prng.random_number       #=> 0.5816771641321361
1868          *   prng.random_number(1000) #=> 485
1869          *   prng.random_number(1..6) #=> 3
1870          *   prng.rand                #=> 0.5816771641321361
1871          *   prng.rand(1000)          #=> 485
1872          *   prng.rand(1..6)          #=> 3
1873          */
1874         VALUE m = rb_define_module_under(rb_cRandom, "Formatter");
1875         rb_include_module(base, m);
1876         rb_extend_object(base, m);
1877         rb_define_method(m, "random_number", rand_random_number, -1);
1878         rb_define_method(m, "rand", rand_random_number, -1);
1879     }
1880
1881     default_rand_key = rb_ractor_local_storage_ptr_newkey(&default_rand_key_storage_type);
1882 }
1883
1884 #undef rb_intern
1885 void
1886 Init_Random(void)
1887 {
1888     id_rand = rb_intern("rand");
1889     id_bytes = rb_intern("bytes");
1890
1891     InitVM(Random);
1892 }