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