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