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