diff options
Diffstat (limited to 'random.c')
| -rw-r--r-- | random.c | 2134 |
1 files changed, 1783 insertions, 351 deletions
@@ -3,333 +3,997 @@ random.c - $Author$ - $Date$ created at: Fri Dec 24 16:39:21 JST 1993 - Copyright (C) 1993-2003 Yukihiro Matsumoto + Copyright (C) 1993-2007 Yukihiro Matsumoto **********************************************************************/ -/* -This is based on trimmed version of MT19937. To get the original version, -contact <http://www.math.keio.ac.jp/~matumoto/emt.html>. - -The original copyright notice follows. - - A C-program for MT19937, with initialization improved 2002/2/10. - Coded by Takuji Nishimura and Makoto Matsumoto. - This is a faster version by taking Shawn Cokus's optimization, - Matthe Bellew's simplification, Isaku Wada's real version. - - Before using, initialize the state by using init_genrand(seed) - or init_by_array(init_key, key_length). - - Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, - All rights reserved. - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions - are met: - - 1. Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - - 2. Redistributions in binary form must reproduce the above copyright - notice, this list of conditions and the following disclaimer in the - documentation and/or other materials provided with the distribution. - - 3. The names of its contributors may not be used to endorse or promote - products derived from this software without specific prior written - permission. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - - - Any feedback is very welcome. - http://www.math.keio.ac.jp/matumoto/emt.html - email: matumoto@math.keio.ac.jp -*/ - -/* Period parameters */ -#define N 624 -#define M 397 -#define MATRIX_A 0x9908b0dfUL /* constant vector a */ -#define UMASK 0x80000000UL /* most significant w-r bits */ -#define LMASK 0x7fffffffUL /* least significant r bits */ -#define MIXBITS(u,v) ( ((u) & UMASK) | ((v) & LMASK) ) -#define TWIST(u,v) ((MIXBITS(u,v) >> 1) ^ ((v)&1UL ? MATRIX_A : 0UL)) - -static unsigned long state[N]; /* the array for the state vector */ -static int left = 1; -static int initf = 0; -static unsigned long *next; - -/* initializes state[N] with a seed */ -static void -init_genrand(unsigned long s) +#include "ruby/internal/config.h" + +#include <errno.h> +#include <limits.h> +#include <math.h> +#include <float.h> +#include <time.h> + +#ifdef HAVE_UNISTD_H +# include <unistd.h> +#endif + +#include <sys/types.h> +#include <sys/stat.h> + +#ifdef HAVE_FCNTL_H +# include <fcntl.h> +#endif + +#if defined(HAVE_SYS_TIME_H) +# include <sys/time.h> +#endif + +#ifdef HAVE_SYSCALL_H +# include <syscall.h> +#elif defined HAVE_SYS_SYSCALL_H +# include <sys/syscall.h> +#endif + +#ifdef _WIN32 +# include <winsock2.h> +# include <windows.h> +# include <wincrypt.h> +# include <bcrypt.h> +#endif + +#if defined(__OpenBSD__) || defined(__FreeBSD__) || defined(__NetBSD__) +/* to define OpenBSD and FreeBSD for version check */ +# include <sys/param.h> +#endif + +#if defined HAVE_GETRANDOM || defined HAVE_GETENTROPY +# if defined(HAVE_SYS_RANDOM_H) +# include <sys/random.h> +# endif +#elif defined __linux__ && defined __NR_getrandom +# include <linux/random.h> +#endif + +#if defined __APPLE__ +# include <AvailabilityMacros.h> +#endif + +#include "internal.h" +#include "internal/array.h" +#include "internal/compilers.h" +#include "internal/numeric.h" +#include "internal/random.h" +#include "internal/sanitizers.h" +#include "internal/variable.h" +#include "ruby_atomic.h" +#include "ruby/random.h" +#include "ruby/ractor.h" + +STATIC_ASSERT(int_must_be_32bit_at_least, sizeof(int) * CHAR_BIT >= 32); + +#include "missing/mt19937.c" + +/* generates a random number on [0,1) with 53-bit resolution*/ +static double int_pair_to_real_exclusive(uint32_t a, uint32_t b); +static double +genrand_real(struct MT *mt) +{ + /* mt must be initialized */ + unsigned int a = genrand_int32(mt), b = genrand_int32(mt); + return int_pair_to_real_exclusive(a, b); +} + +static const double dbl_reduce_scale = /* 2**(-DBL_MANT_DIG) */ + (1.0 + / (double)(DBL_MANT_DIG > 2*31 ? (1ul<<31) : 1.0) + / (double)(DBL_MANT_DIG > 1*31 ? (1ul<<31) : 1.0) + / (double)(1ul<<(DBL_MANT_DIG%31))); + +static double +int_pair_to_real_exclusive(uint32_t a, uint32_t b) { - int j; - state[0]= s & 0xffffffffUL; - for (j=1; j<N; j++) { - state[j] = (1812433253UL * (state[j-1] ^ (state[j-1] >> 30)) + j); - /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ - /* In the previous versions, MSBs of the seed affect */ - /* only MSBs of the array state[]. */ - /* 2002/01/09 modified by Makoto Matsumoto */ - state[j] &= 0xffffffffUL; /* for >32 bit machines */ + static const int a_shift = DBL_MANT_DIG < 64 ? + (64-DBL_MANT_DIG)/2 : 0; + static const int b_shift = DBL_MANT_DIG < 64 ? + (65-DBL_MANT_DIG)/2 : 0; + a >>= a_shift; + b >>= b_shift; + return (a*(double)(1ul<<(32-b_shift))+b)*dbl_reduce_scale; +} + +/* generates a random number on [0,1] with 53-bit resolution*/ +static double int_pair_to_real_inclusive(uint32_t a, uint32_t b); +#if 0 +static double +genrand_real2(struct MT *mt) +{ + /* mt must be initialized */ + uint32_t a = genrand_int32(mt), b = genrand_int32(mt); + return int_pair_to_real_inclusive(a, b); +} +#endif + +/* These real versions are due to Isaku Wada, 2002/01/09 added */ + +#undef N +#undef M + +typedef struct { + rb_random_t base; + struct MT mt; +} rb_random_mt_t; + +#define DEFAULT_SEED_CNT 4 + +static VALUE rand_init(const rb_random_interface_t *, rb_random_t *, VALUE); +static VALUE random_seed(VALUE); +static void fill_random_seed(uint32_t *seed, size_t cnt, bool try_bytes); +static VALUE make_seed_value(uint32_t *ptr, size_t len); +#define fill_random_bytes ruby_fill_random_bytes + +RB_RANDOM_INTERFACE_DECLARE(rand_mt); +static const rb_random_interface_t random_mt_if = { + DEFAULT_SEED_CNT * 32, + RB_RANDOM_INTERFACE_DEFINE(rand_mt) +}; + +static rb_random_mt_t * +rand_mt_start(rb_random_mt_t *r, VALUE obj) +{ + if (!genrand_initialized(&r->mt)) { + r->base.seed = rand_init(&random_mt_if, &r->base, random_seed(Qundef)); + if (obj) { + RB_OBJ_WRITTEN(obj, Qundef, r->base.seed); + } } - left = 1; initf = 1; + return r; +} + +static rb_random_t * +rand_start(rb_random_mt_t *r, VALUE obj) +{ + return &rand_mt_start(r, obj)->base; +} + +static rb_ractor_local_key_t default_rand_key; + +void +rb_free_default_rand_key(void) +{ + xfree(default_rand_key); } -/* initialize by an array with array-length */ -/* init_key is the array for initializing keys */ -/* key_length is its length */ -/* slight change for C++, 2004/2/26 */ static void -init_by_array(unsigned long init_key[], int key_length) +default_rand_mark(void *ptr) { - int i, j, k; - init_genrand(19650218UL); - i=1; j=0; - k = (N>key_length ? N : key_length); - for (; k; k--) { - state[i] = (state[i] ^ ((state[i-1] ^ (state[i-1] >> 30)) * 1664525UL)) - + init_key[j] + j; /* non linear */ - state[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ - i++; j++; - if (i>=N) { state[0] = state[N-1]; i=1; } - if (j>=key_length) j=0; - } - for (k=N-1; k; k--) { - state[i] = (state[i] ^ ((state[i-1] ^ (state[i-1] >> 30)) * 1566083941UL)) - - i; /* non linear */ - state[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */ - i++; - if (i>=N) { state[0] = state[N-1]; i=1; } + rb_random_mt_t *rnd = (rb_random_mt_t *)ptr; + rb_gc_mark(rnd->base.seed); +} + +static const struct rb_ractor_local_storage_type default_rand_key_storage_type = { + default_rand_mark, + ruby_xfree, +}; + +static rb_random_mt_t * +default_rand(void) +{ + rb_random_mt_t *rnd; + + if ((rnd = rb_ractor_local_storage_ptr(default_rand_key)) == NULL) { + rnd = ZALLOC(rb_random_mt_t); + rb_ractor_local_storage_ptr_set(default_rand_key, rnd); } - state[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */ - left = 1; initf = 1; + return rnd; } -static void -next_state(void) +static rb_random_mt_t * +default_mt(void) +{ + return rand_mt_start(default_rand(), Qfalse); +} + +static rb_random_t * +default_rand_start(void) +{ + return &default_mt()->base; +} + +unsigned int +rb_genrand_int32(void) { - unsigned long *p=state; - int j; + struct MT *mt = &default_mt()->mt; + return genrand_int32(mt); +} - /* if init_genrand() has not been called, */ - /* a default initial seed is used */ - if (initf==0) init_genrand(5489UL); +double +rb_genrand_real(void) +{ + struct MT *mt = &default_mt()->mt; + return genrand_real(mt); +} + +#define SIZEOF_INT32 (31/CHAR_BIT + 1) + +static double +int_pair_to_real_inclusive(uint32_t a, uint32_t b) +{ + double r; + enum {dig = DBL_MANT_DIG}; + enum {dig_u = dig-32, dig_r64 = 64-dig, bmask = ~(~0u<<(dig_r64))}; +#if defined HAVE_UINT128_T + const uint128_t m = ((uint128_t)1 << dig) | 1; + uint128_t x = ((uint128_t)a << 32) | b; + r = (double)(uint64_t)((x * m) >> 64); +#elif defined HAVE_UINT64_T + uint64_t x = ((uint64_t)a << dig_u) + + (((uint64_t)b + (a >> dig_u)) >> dig_r64); + r = (double)x; +#else + /* shift then add to get rid of overflow */ + b = (b >> dig_r64) + (((a >> dig_u) + (b & bmask)) >> dig_r64); + r = (double)a * (1 << dig_u) + b; +#endif + return r * dbl_reduce_scale; +} - left = N; - next = state; - - for (j=N-M+1; --j; p++) - *p = p[M] ^ TWIST(p[0], p[1]); +VALUE rb_cRandom; +#define id_minus '-' +#define id_plus '+' +static ID id_rand, id_bytes; +NORETURN(static void domain_error(void)); - for (j=M; --j; p++) - *p = p[M-N] ^ TWIST(p[0], p[1]); +/* :nodoc: */ +#define random_mark rb_random_mark - *p = p[M-N] ^ TWIST(p[0], state[0]); +void +random_mark(void *ptr) +{ + rb_gc_mark(((rb_random_t *)ptr)->seed); } -/* generates a random number on [0,0xffffffff]-interval */ -unsigned long -genrand_int32(void) +#define random_free RUBY_TYPED_DEFAULT_FREE + +static size_t +random_memsize(const void *ptr) { - unsigned long y; + return sizeof(rb_random_t); +} - if (--left == 0) next_state(); - y = *next++; +const rb_data_type_t rb_random_data_type = { + "random", + { + random_mark, + random_free, + random_memsize, + }, + 0, 0, RUBY_TYPED_FREE_IMMEDIATELY | RUBY_TYPED_WB_PROTECTED +}; - /* Tempering */ - y ^= (y >> 11); - y ^= (y << 7) & 0x9d2c5680UL; - y ^= (y << 15) & 0xefc60000UL; - y ^= (y >> 18); +#define random_mt_mark rb_random_mark +#define random_mt_free RUBY_TYPED_DEFAULT_FREE - return y; +static size_t +random_mt_memsize(const void *ptr) +{ + return sizeof(rb_random_mt_t); } -/* generates a random number on [0,1) with 53-bit resolution*/ -double -genrand_real(void) -{ - unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6; - return(a*67108864.0+b)*(1.0/9007199254740992.0); -} -/* These real versions are due to Isaku Wada, 2002/01/09 added */ +static const rb_data_type_t random_mt_type = { + "random/MT", + { + random_mt_mark, + random_mt_free, + random_mt_memsize, + }, + &rb_random_data_type, + (void *)&random_mt_if, + RUBY_TYPED_FREE_IMMEDIATELY | RUBY_TYPED_WB_PROTECTED +}; -#undef N -#undef M +static rb_random_t * +get_rnd(VALUE obj) +{ + rb_random_t *ptr; + TypedData_Get_Struct(obj, rb_random_t, &rb_random_data_type, ptr); + if (RTYPEDDATA_TYPE(obj) == &random_mt_type) + return rand_start((rb_random_mt_t *)ptr, obj); + return ptr; +} -/* These real versions are due to Isaku Wada, 2002/01/09 added */ +static rb_random_mt_t * +get_rnd_mt(VALUE obj) +{ + rb_random_mt_t *ptr; + TypedData_Get_Struct(obj, rb_random_mt_t, &random_mt_type, ptr); + return ptr; +} -#include "ruby.h" +static rb_random_t * +try_get_rnd(VALUE obj, const rb_random_interface_t **rng_p) +{ + if (obj == rb_cRandom) { + *rng_p = &random_mt_if; + return default_rand_start(); + } + if (!rb_typeddata_is_kind_of(obj, &rb_random_data_type)) return NULL; + const struct rb_data_type_struct *type = RTYPEDDATA_TYPE(obj); + *rng_p = type->data; + void *rnd = DATA_PTR(obj); + if (!rnd) { + rb_raise(rb_eArgError, "uninitialized random: %s", + RTYPEDDATA_TYPE(obj)->wrap_struct_name); + } + if (type == &random_mt_type) rnd = rand_start(rnd, obj); + return rnd; +} -#ifdef HAVE_UNISTD_H -#include <unistd.h> -#endif -#include <time.h> -#include <sys/types.h> -#include <sys/stat.h> -#ifdef HAVE_FCNTL_H -#include <fcntl.h> -#endif +/* :nodoc: */ +void +rb_random_base_init(rb_random_t *rnd) +{ + rnd->seed = INT2FIX(0); +} -static VALUE saved_seed = INT2FIX(0); +/* :nodoc: */ +static VALUE +random_alloc(VALUE klass) +{ + rb_random_mt_t *rnd; + VALUE obj = TypedData_Make_Struct(klass, rb_random_mt_t, &random_mt_type, rnd); + rb_random_base_init(&rnd->base); + return obj; +} static VALUE -rand_init(VALUE vseed) +rand_init_default(const rb_random_interface_t *rng, rb_random_t *rnd) { - volatile VALUE seed; - VALUE old; - long len; - unsigned long *buf; + VALUE seed, buf0 = 0; + size_t len = roomof(rng->default_seed_bits, 32); + uint32_t *buf = ALLOCV_N(uint32_t, buf0, len+1); - seed = rb_to_int(vseed); - switch (TYPE(seed)) { - case T_FIXNUM: - len = sizeof(VALUE); - break; - case T_BIGNUM: - len = RBIGNUM(seed)->len * SIZEOF_BDIGITS; - if (len == 0) - len = 4; - break; - default: - rb_raise(rb_eTypeError, "failed to convert %s into Integer", - rb_obj_classname(vseed)); - } - len = (len + 3) / 4; /* number of 32bit words */ - buf = ALLOC_N(unsigned long, len); /* allocate longs for init_by_array */ - memset(buf, 0, len * sizeof(long)); - if (FIXNUM_P(seed)) { - buf[0] = FIX2ULONG(seed) & 0xffffffff; -#if SIZEOF_LONG > 4 - buf[1] = FIX2ULONG(seed) >> 32; -#endif + fill_random_seed(buf, len, true); + rng->init(rnd, buf, len); + seed = make_seed_value(buf, len); + explicit_bzero(buf, len * sizeof(*buf)); + ALLOCV_END(buf0); + return seed; +} + +static VALUE +rand_init(const rb_random_interface_t *rng, rb_random_t *rnd, VALUE seed) +{ + uint32_t *buf; + VALUE buf0 = 0; + size_t len; + int sign; + + len = rb_absint_numwords(seed, 32, NULL); + if (len == 0) len = 1; + buf = ALLOCV_N(uint32_t, buf0, len); + sign = rb_integer_pack(seed, buf, len, sizeof(uint32_t), 0, + INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); + if (sign < 0) + sign = -sign; + if (len == 1) { + rng->init_int32(rnd, buf[0]); } else { - int i, j; - for (i = RBIGNUM(seed)->len-1; 0 <= i; i--) { - j = i * SIZEOF_BDIGITS / 4; -#if SIZEOF_BDIGITS < 4 - buf[j] <<= SIZEOF_BDIGITS * 8; -#endif - buf[j] |= ((BDIGIT *)RBIGNUM(seed)->digits)[i]; - } + if (sign != 2 && buf[len-1] == 1) /* remove leading-zero-guard */ + len--; + rng->init(rnd, buf, len); } - while (1 < len && buf[len-1] == 0) { - len--; + explicit_bzero(buf, len * sizeof(*buf)); + ALLOCV_END(buf0); + return seed; +} + +/* + * call-seq: + * Random.new(seed = Random.new_seed) -> prng + * + * Creates a new PRNG using +seed+ to set the initial state. If +seed+ is + * omitted, the generator is initialized with Random.new_seed. + * + * See Random.srand for more information on the use of seed values. + */ +static VALUE +random_init(int argc, VALUE *argv, VALUE obj) +{ + const rb_random_interface_t *rng = NULL; + rb_random_t *rnd = try_get_rnd(obj, &rng); + + if (!rng) { + rb_raise(rb_eTypeError, "undefined random interface: %s", + RTYPEDDATA_TYPE(obj)->wrap_struct_name); + } + + unsigned int major = rng->version.major; + unsigned int minor = rng->version.minor; + if (major != RUBY_RANDOM_INTERFACE_VERSION_MAJOR) { + rb_raise(rb_eTypeError, "Random interface version " + STRINGIZE(RUBY_RANDOM_INTERFACE_VERSION_MAJOR) "." + STRINGIZE(RUBY_RANDOM_INTERFACE_VERSION_MINOR) " " + "expected: %d.%d", major, minor); } - if (len <= 1) { - init_genrand(buf[0]); + argc = rb_check_arity(argc, 0, 1); + rb_check_frozen(obj); + if (argc == 0) { + RB_OBJ_WRITE(obj, &rnd->seed, rand_init_default(rng, rnd)); } else { - if (buf[len-1] == 1) /* remove leading-zero-guard */ - len--; - init_by_array(buf, len); + RB_OBJ_WRITE(obj, &rnd->seed, rand_init(rng, rnd, rb_to_int(argv[0]))); } - old = saved_seed; - saved_seed = seed; - free(buf); - return old; + return obj; } -static VALUE -random_seed(void) +#define DEFAULT_SEED_LEN (DEFAULT_SEED_CNT * (int)sizeof(int32_t)) + +#if defined(S_ISCHR) && !defined(DOSISH) +# define USE_DEV_URANDOM 1 +#else +# define USE_DEV_URANDOM 0 +#endif + +#if ! defined HAVE_GETRANDOM && defined __linux__ && defined __NR_getrandom +# ifndef GRND_NONBLOCK +# define GRND_NONBLOCK 0x0001 /* not defined in musl libc */ +# endif +# define getrandom(ptr, size, flags) \ + (ssize_t)syscall(__NR_getrandom, (ptr), (size), (flags)) +# define HAVE_GETRANDOM 1 +#endif + +/* fill random bytes by reading random device directly */ +#if USE_DEV_URANDOM +static int +fill_random_bytes_urandom(void *seed, size_t size) { - static int n = 0; - struct timeval tv; - int fd; + /* + O_NONBLOCK and O_NOCTTY is meaningless if /dev/urandom correctly points + to a urandom device. But it protects from several strange hazard if + /dev/urandom is not a urandom device. + */ + int fd = rb_cloexec_open("/dev/urandom", +# ifdef O_NONBLOCK + O_NONBLOCK| +# endif +# ifdef O_NOCTTY + O_NOCTTY| +# endif + O_RDONLY, 0); struct stat statbuf; + ssize_t ret = 0; + size_t offset = 0; - int seed_len; - BDIGIT *digits; - unsigned long *seed; - NEWOBJ(big, struct RBignum); - OBJSETUP(big, rb_cBignum, T_BIGNUM); + if (fd < 0) return -1; + rb_update_max_fd(fd); + if (fstat(fd, &statbuf) == 0 && S_ISCHR(statbuf.st_mode)) { + do { + ret = read(fd, ((char*)seed) + offset, size - offset); + if (ret < 0) { + close(fd); + return -1; + } + offset += (size_t)ret; + } while (offset < size); + } + close(fd); + return 0; +} +#else +# define fill_random_bytes_urandom(seed, size) -1 +#endif - seed_len = 4 * sizeof(long); - big->sign = 1; - big->len = seed_len / SIZEOF_BDIGITS + 1; - digits = big->digits = ALLOC_N(BDIGIT, big->len); - seed = (unsigned long *)big->digits; +/* fill random bytes by library */ +#if 0 +#elif defined MAC_OS_X_VERSION_10_7 && MAC_OS_X_VERSION_MIN_REQUIRED >= MAC_OS_X_VERSION_10_7 - memset(digits, 0, big->len * SIZEOF_BDIGITS); +# if defined(USE_COMMON_RANDOM) +# elif defined MAC_OS_X_VERSION_10_10 && MAC_OS_X_VERSION_MIN_REQUIRED >= MAC_OS_X_VERSION_10_10 +# define USE_COMMON_RANDOM 1 +# else +# define USE_COMMON_RANDOM 0 +# endif +# if USE_COMMON_RANDOM +# include <CommonCrypto/CommonCryptoError.h> /* for old Xcode */ +# include <CommonCrypto/CommonRandom.h> +# else +# include <Security/SecRandom.h> +# endif -#ifdef S_ISCHR - if ((fd = open("/dev/urandom", O_RDONLY -#ifdef O_NONBLOCK - |O_NONBLOCK +static int +fill_random_bytes_lib(void *seed, size_t size) +{ +#if USE_COMMON_RANDOM + CCRNGStatus status = CCRandomGenerateBytes(seed, size); + int failed = status != kCCSuccess; +#else + int status = SecRandomCopyBytes(kSecRandomDefault, size, seed); + int failed = status != errSecSuccess; #endif -#ifdef O_NOCTTY - |O_NOCTTY + + if (failed) { +# if 0 +# if USE_COMMON_RANDOM + /* How to get the error message? */ + fprintf(stderr, "CCRandomGenerateBytes failed: %d\n", status); +# else + CFStringRef s = SecCopyErrorMessageString(status, NULL); + const char *m = s ? CFStringGetCStringPtr(s, kCFStringEncodingUTF8) : NULL; + fprintf(stderr, "SecRandomCopyBytes failed: %d: %s\n", status, + m ? m : "unknown"); + if (s) CFRelease(s); +# endif +# endif + return -1; + } + return 0; +} +#elif defined(HAVE_ARC4RANDOM_BUF) && \ + ((defined(__OpenBSD__) && OpenBSD >= 201411) || \ + (defined(__NetBSD__) && __NetBSD_Version__ >= 700000000) || \ + (defined(__FreeBSD__) && __FreeBSD_version >= 1200079)) +// [Bug #15039] arc4random_buf(3) should used only if we know it is fork-safe +static int +fill_random_bytes_lib(void *buf, size_t size) +{ + arc4random_buf(buf, size); + return 0; +} +#elif defined(_WIN32) + +#ifndef DWORD_MAX +# define DWORD_MAX (~(DWORD)0UL) #endif -#ifdef O_NOFOLLOW - |O_NOFOLLOW + +# if defined(CRYPT_VERIFYCONTEXT) +/* Although HCRYPTPROV is not a HANDLE, it looks like + * INVALID_HANDLE_VALUE is not a valid value */ +static const HCRYPTPROV INVALID_HCRYPTPROV = (HCRYPTPROV)INVALID_HANDLE_VALUE; + +static void +release_crypt(void *p) +{ + HCRYPTPROV *ptr = p; + HCRYPTPROV prov = (HCRYPTPROV)ATOMIC_PTR_EXCHANGE(*ptr, INVALID_HCRYPTPROV); + if (prov && prov != INVALID_HCRYPTPROV) { + CryptReleaseContext(prov, 0); + } +} + +static const rb_data_type_t crypt_prov_type = { + "HCRYPTPROV", + {0, release_crypt,}, + 0, 0, RUBY_TYPED_FREE_IMMEDIATELY | RUBY_TYPED_EMBEDDABLE +}; + +static int +fill_random_bytes_crypt(void *seed, size_t size) +{ + static HCRYPTPROV perm_prov; + HCRYPTPROV prov = perm_prov, old_prov; + if (!prov) { + VALUE wrapper = TypedData_Wrap_Struct(0, &crypt_prov_type, 0); + if (!CryptAcquireContext(&prov, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) { + prov = INVALID_HCRYPTPROV; + } + old_prov = (HCRYPTPROV)ATOMIC_PTR_CAS(perm_prov, 0, prov); + if (LIKELY(!old_prov)) { /* no other threads acquired */ + if (prov != INVALID_HCRYPTPROV) { + DATA_PTR(wrapper) = (void *)prov; + rb_vm_register_global_object(wrapper); + } + } + else { /* another thread acquired */ + if (prov != INVALID_HCRYPTPROV) { + CryptReleaseContext(prov, 0); + } + prov = old_prov; + } + } + if (prov == INVALID_HCRYPTPROV) return -1; + while (size > 0) { + DWORD n = (size > (size_t)DWORD_MAX) ? DWORD_MAX : (DWORD)size; + if (!CryptGenRandom(prov, n, seed)) return -1; + seed = (char *)seed + n; + size -= n; + } + return 0; +} +# else +# define fill_random_bytes_crypt(seed, size) -1 +# endif + +static int +fill_random_bytes_bcrypt(void *seed, size_t size) +{ + while (size > 0) { + ULONG n = (size > (size_t)ULONG_MAX) ? LONG_MAX : (ULONG)size; + if (BCryptGenRandom(NULL, seed, n, BCRYPT_USE_SYSTEM_PREFERRED_RNG)) + return -1; + seed = (char *)seed + n; + size -= n; + } + return 0; +} + +static int +fill_random_bytes_lib(void *seed, size_t size) +{ + if (fill_random_bytes_bcrypt(seed, size) == 0) return 0; + return fill_random_bytes_crypt(seed, size); +} +#else +# define fill_random_bytes_lib(seed, size) -1 +#endif + +/* fill random bytes by dedicated syscall */ +#if 0 +#elif defined HAVE_GETRANDOM +static int +fill_random_bytes_syscall(void *seed, size_t size, int need_secure) +{ + static rb_atomic_t try_syscall = 1; + if (try_syscall) { + size_t offset = 0; + int flags = 0; + if (!need_secure) + flags = GRND_NONBLOCK; + do { + errno = 0; + ssize_t ret = getrandom(((char*)seed) + offset, size - offset, flags); + if (ret == -1) { + ATOMIC_SET(try_syscall, 0); + return -1; + } + offset += (size_t)ret; + } while (offset < size); + return 0; + } + return -1; +} +#elif defined(HAVE_GETENTROPY) +/* + * The Open Group Base Specifications Issue 8 - IEEE Std 1003.1-2024 + * https://pubs.opengroup.org/onlinepubs/9799919799/functions/getentropy.html + * + * NOTE: `getentropy`(3) on Linux is implemented using `getrandom`(2), + * prefer the latter over this if both are defined. + */ +#ifndef GETENTROPY_MAX +# define GETENTROPY_MAX 256 #endif - )) >= 0) { - if (fstat(fd, &statbuf) == 0 && S_ISCHR(statbuf.st_mode)) { - read(fd, seed, seed_len); +static int +fill_random_bytes_syscall(void *seed, size_t size, int need_secure) +{ + unsigned char *p = (unsigned char *)seed; + while (size) { + size_t len = size < GETENTROPY_MAX ? size : GETENTROPY_MAX; + if (getentropy(p, len) != 0) { + return -1; } - close(fd); + p += len; + size -= len; } + return 0; +} +#else +# define fill_random_bytes_syscall(seed, size, need_secure) -1 #endif +int +ruby_fill_random_bytes(void *seed, size_t size, int need_secure) +{ + int ret = fill_random_bytes_syscall(seed, size, need_secure); + if (ret == 0) return ret; + if (fill_random_bytes_lib(seed, size) == 0) return 0; + return fill_random_bytes_urandom(seed, size); +} + +/* cnt must be 4 or more */ +static void +fill_random_seed(uint32_t *seed, size_t cnt, bool try_bytes) +{ + static rb_atomic_t n = 0; +#if defined HAVE_CLOCK_GETTIME + struct timespec tv; +#elif defined HAVE_GETTIMEOFDAY + struct timeval tv; +#endif + size_t len = cnt * sizeof(*seed); + + if (try_bytes) { + fill_random_bytes(seed, len, FALSE); + return; + } + + memset(seed, 0, len); +#if defined HAVE_CLOCK_GETTIME + clock_gettime(CLOCK_REALTIME, &tv); + seed[0] ^= tv.tv_nsec; +#elif defined HAVE_GETTIMEOFDAY gettimeofday(&tv, 0); seed[0] ^= tv.tv_usec; - seed[1] ^= tv.tv_sec; - seed[2] ^= getpid() ^ (n++ << 16); - seed[3] ^= (unsigned long)&seed; +#endif + seed[1] ^= (uint32_t)tv.tv_sec; +#if SIZEOF_TIME_T > SIZEOF_INT + seed[0] ^= (uint32_t)((time_t)tv.tv_sec >> SIZEOF_INT * CHAR_BIT); +#endif + seed[2] ^= getpid() ^ (ATOMIC_FETCH_ADD(n, 1) << 16); + seed[3] ^= (uint32_t)(VALUE)&seed; +#if SIZEOF_VOIDP > SIZEOF_INT + seed[2] ^= (uint32_t)((VALUE)&seed >> SIZEOF_INT * CHAR_BIT); +#endif +} - /* set leading-zero-guard if need. */ - digits[big->len-1] = digits[big->len-2] <= 1 ? 1 : 0; +static VALUE +make_seed_value(uint32_t *ptr, size_t len) +{ + VALUE seed; + + if (ptr[len-1] <= 1) { + /* set leading-zero-guard */ + ptr[len++] = 1; + } + + seed = rb_integer_unpack(ptr, len, sizeof(uint32_t), 0, + INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); - return rb_big_norm((VALUE)big); + return seed; +} + +#define with_random_seed(size, add, try_bytes) \ + for (uint32_t seedbuf[(size)+(add)], loop = (fill_random_seed(seedbuf, (size), try_bytes), 1); \ + loop; explicit_bzero(seedbuf, (size)*sizeof(seedbuf[0])), loop = 0) + +/* + * call-seq: Random.new_seed -> integer + * + * Returns an arbitrary seed value. This is used by Random.new + * when no seed value is specified as an argument. + * + * Random.new_seed #=> 115032730400174366788466674494640623225 + */ +static VALUE +random_seed(VALUE _) +{ + VALUE v; + with_random_seed(DEFAULT_SEED_CNT, 1, true) { + v = make_seed_value(seedbuf, DEFAULT_SEED_CNT); + } + return v; } /* - * call-seq: - * srand(number=0) => old_seed - * - * Seeds the pseudorandom number generator to the value of - * <i>number</i>.<code>to_i.abs</code>. If <i>number</i> is omitted - * or zero, seeds the generator using a combination of the time, the - * process id, and a sequence number. (This is also the behavior if - * <code>Kernel::rand</code> is called without previously calling - * <code>srand</code>, but without the sequence.) By setting the seed - * to a known value, scripts can be made deterministic during testing. - * The previous seed value is returned. Also see <code>Kernel::rand</code>. + * call-seq: Random.urandom(size) -> string + * + * Returns a string, using platform providing features. + * Returned value is expected to be a cryptographically secure + * pseudo-random number in binary form. + * This method raises a RuntimeError if the feature provided by platform + * failed to prepare the result. + * + * In 2017, Linux manpage random(7) writes that "no cryptographic + * primitive available today can hope to promise more than 256 bits of + * security". So it might be questionable to pass size > 32 to this + * method. + * + * Random.urandom(8) #=> "\x78\x41\xBA\xAF\x7D\xEA\xD8\xEA" + */ +static VALUE +random_raw_seed(VALUE self, VALUE size) +{ + long n = NUM2ULONG(size); + VALUE buf = rb_str_new(0, n); + if (n == 0) return buf; + if (fill_random_bytes(RSTRING_PTR(buf), n, TRUE)) + rb_raise(rb_eRuntimeError, "failed to get urandom"); + return buf; +} + +/* + * call-seq: prng.seed -> integer + * + * Returns the seed value used to initialize the generator. This may be used to + * initialize another generator with the same state at a later time, causing it + * to produce the same sequence of numbers. + * + * prng1 = Random.new(1234) + * prng1.seed #=> 1234 + * prng1.rand(100) #=> 47 + * + * prng2 = Random.new(prng1.seed) + * prng2.rand(100) #=> 47 + */ +static VALUE +random_get_seed(VALUE obj) +{ + return get_rnd(obj)->seed; +} + +/* :nodoc: */ +static VALUE +rand_mt_copy(VALUE obj, VALUE orig) +{ + rb_random_mt_t *rnd1, *rnd2; + struct MT *mt; + + if (!OBJ_INIT_COPY(obj, orig)) return obj; + + rnd1 = get_rnd_mt(obj); + rnd2 = get_rnd_mt(orig); + mt = &rnd1->mt; + + *rnd1 = *rnd2; + RB_OBJ_WRITTEN(obj, Qundef, rnd1->base.seed); + mt->next = mt->state + numberof(mt->state) - mt->left + 1; + return obj; +} + +static VALUE +mt_state(const struct MT *mt) +{ + return rb_integer_unpack(mt->state, numberof(mt->state), + sizeof(*mt->state), 0, + INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); +} + +/* :nodoc: */ +static VALUE +rand_mt_state(VALUE obj) +{ + rb_random_mt_t *rnd = get_rnd_mt(obj); + return mt_state(&rnd->mt); +} + +/* :nodoc: */ +static VALUE +random_s_state(VALUE klass) +{ + return mt_state(&default_rand()->mt); +} + +/* :nodoc: */ +static VALUE +rand_mt_left(VALUE obj) +{ + rb_random_mt_t *rnd = get_rnd_mt(obj); + return INT2FIX(rnd->mt.left); +} + +/* :nodoc: */ +static VALUE +random_s_left(VALUE klass) +{ + return INT2FIX(default_rand()->mt.left); +} + +/* :nodoc: */ +static VALUE +rand_mt_dump(VALUE obj) +{ + rb_random_mt_t *rnd = rb_check_typeddata(obj, &random_mt_type); + VALUE dump = rb_ary_new2(3); + + rb_ary_push(dump, mt_state(&rnd->mt)); + rb_ary_push(dump, INT2FIX(rnd->mt.left)); + rb_ary_push(dump, rnd->base.seed); + + return dump; +} + +/* :nodoc: */ +static VALUE +rand_mt_load(VALUE obj, VALUE dump) +{ + rb_random_mt_t *rnd = rb_check_typeddata(obj, &random_mt_type); + struct MT *mt = &rnd->mt; + VALUE state, left = INT2FIX(1), seed = INT2FIX(0); + unsigned long x; + + rb_check_copyable(obj, dump); + Check_Type(dump, T_ARRAY); + switch (RARRAY_LEN(dump)) { + case 3: + seed = RARRAY_AREF(dump, 2); + case 2: + left = RARRAY_AREF(dump, 1); + case 1: + state = RARRAY_AREF(dump, 0); + break; + default: + rb_raise(rb_eArgError, "wrong dump data"); + } + rb_integer_pack(state, mt->state, numberof(mt->state), + sizeof(*mt->state), 0, + INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); + x = NUM2ULONG(left); + if (x > numberof(mt->state) || x == 0) { + rb_raise(rb_eArgError, "wrong value"); + } + mt->left = (unsigned int)x; + mt->next = mt->state + numberof(mt->state) - x + 1; + RB_OBJ_WRITE(obj, &rnd->base.seed, rb_to_int(seed)); + + return obj; +} + +static void +rand_mt_init_int32(rb_random_t *rnd, uint32_t data) +{ + struct MT *mt = &((rb_random_mt_t *)rnd)->mt; + init_genrand(mt, data); +} + +static void +rand_mt_init(rb_random_t *rnd, const uint32_t *buf, size_t len) +{ + struct MT *mt = &((rb_random_mt_t *)rnd)->mt; + init_by_array(mt, buf, (int)len); +} + +static unsigned int +rand_mt_get_int32(rb_random_t *rnd) +{ + struct MT *mt = &((rb_random_mt_t *)rnd)->mt; + return genrand_int32(mt); +} + +static void +rand_mt_get_bytes(rb_random_t *rnd, void *ptr, size_t n) +{ + rb_rand_bytes_int32(rand_mt_get_int32, rnd, ptr, n); +} + +/* + * call-seq: + * srand(number = Random.new_seed) -> old_seed + * + * Seeds the system pseudo-random number generator, with +number+. + * The previous seed value is returned. + * + * If +number+ is omitted, seeds the generator using a source of entropy + * provided by the operating system, if available (/dev/urandom on Unix systems + * or the RSA cryptographic provider on Windows), which is then combined with + * the time, the process id, and a sequence number. + * + * srand may be used to ensure repeatable sequences of pseudo-random numbers + * between different runs of the program. By setting the seed to a known value, + * programs can be made deterministic during testing. + * + * srand 1234 # => 268519324636777531569100071560086917274 + * [ rand, rand ] # => [0.1915194503788923, 0.6221087710398319] + * [ rand(10), rand(1000) ] # => [4, 664] + * srand 1234 # => 1234 + * [ rand, rand ] # => [0.1915194503788923, 0.6221087710398319] */ static VALUE rb_f_srand(int argc, VALUE *argv, VALUE obj) { VALUE seed, old; + rb_random_mt_t *r = default_mt(); - rb_secure(4); - if (rb_scan_args(argc, argv, "01", &seed) == 0) { - seed = random_seed(); + if (rb_check_arity(argc, 0, 1) == 0) { + seed = random_seed(obj); } - old = rand_init(seed); + else { + seed = rb_to_int(argv[0]); + } + old = r->base.seed; + rand_init(&random_mt_if, &r->base, seed); + r->base.seed = seed; return old; } -static unsigned long +static unsigned long make_mask(unsigned long x) { x = x | x >> 1; @@ -344,148 +1008,916 @@ make_mask(unsigned long x) } static unsigned long -limited_rand(unsigned long limit) +limited_rand(const rb_random_interface_t *rng, rb_random_t *rnd, unsigned long limit) { - unsigned long mask = make_mask(limit); - int i; - unsigned long val; + /* mt must be initialized */ + unsigned long val, mask; - retry: - val = 0; - for (i = SIZEOF_LONG/4-1; 0 <= i; i--) { - if (mask >> (i * 32)) { - val |= genrand_int32() << (i * 32); - val &= mask; - if (limit < val) - goto retry; + if (!limit) return 0; + mask = make_mask(limit); + +#if 4 < SIZEOF_LONG + if (0xffffffff < limit) { + int i; + retry: + val = 0; + for (i = SIZEOF_LONG/SIZEOF_INT32-1; 0 <= i; i--) { + if ((mask >> (i * 32)) & 0xffffffff) { + val |= (unsigned long)rng->get_int32(rnd) << (i * 32); + val &= mask; + if (limit < val) + goto retry; + } } + return val; } +#endif + + do { + val = rng->get_int32(rnd) & mask; + } while (limit < val); return val; } static VALUE -limited_big_rand(struct RBignum *limit) +limited_big_rand(const rb_random_interface_t *rng, rb_random_t *rnd, VALUE limit) { - unsigned long mask, lim, rnd; - struct RBignum *val; - int i, len, boundary; + /* mt must be initialized */ + + uint32_t mask; + long i; + int boundary; + + size_t len; + uint32_t *tmp, *lim_array, *rnd_array; + VALUE vtmp; + VALUE val; + + len = rb_absint_numwords(limit, 32, NULL); + tmp = ALLOCV_N(uint32_t, vtmp, len*2); + lim_array = tmp; + rnd_array = tmp + len; + rb_integer_pack(limit, lim_array, len, sizeof(uint32_t), 0, + INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); - len = (limit->len * SIZEOF_BDIGITS + 3) / 4; - val = (struct RBignum *)rb_big_clone((VALUE)limit); - val->sign = 1; -#if SIZEOF_BDIGITS == 2 -# define BIG_GET32(big,i) (((BDIGIT *)(big)->digits)[(i)*2] | \ - ((i)*2+1 < (big)->len ? (((BDIGIT *)(big)->digits)[(i)*2+1] << 16) \ - : 0)) -# define BIG_SET32(big,i,d) ((((BDIGIT *)(big)->digits)[(i)*2] = (d) & 0xffff), \ - ((i)*2+1 < (big)->len ? (((BDIGIT *)(big)->digits)[(i)*2+1] = (d) >> 16) \ - : 0)) -#else - /* SIZEOF_BDIGITS == 4 */ -# define BIG_GET32(big,i) (((BDIGIT *)(big)->digits)[i]) -# define BIG_SET32(big,i,d) (((BDIGIT *)(big)->digits)[i] = (d)) -#endif retry: mask = 0; boundary = 1; for (i = len-1; 0 <= i; i--) { - lim = BIG_GET32(limit, i); - mask = mask ? 0xffffffff : make_mask(lim); + uint32_t r = 0; + uint32_t lim = lim_array[i]; + mask = mask ? 0xffffffff : (uint32_t)make_mask(lim); if (mask) { - rnd = genrand_int32() & mask; + r = rng->get_int32(rnd) & mask; if (boundary) { - if (lim < rnd) + if (lim < r) goto retry; - if (rnd < lim) + if (r < lim) boundary = 0; } } - else { - rnd = 0; + rnd_array[i] = r; + } + val = rb_integer_unpack(rnd_array, len, sizeof(uint32_t), 0, + INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); + ALLOCV_END(vtmp); + + return val; +} + +/* + * Returns random unsigned long value in [0, +limit+]. + * + * Note that +limit+ is included, and the range of the argument and the + * return value depends on environments. + */ +unsigned long +rb_genrand_ulong_limited(unsigned long limit) +{ + rb_random_mt_t *mt = default_mt(); + return limited_rand(&random_mt_if, &mt->base, limit); +} + +static VALUE +obj_random_bytes(VALUE obj, void *p, long n) +{ + VALUE len = LONG2NUM(n); + VALUE v = rb_funcallv_public(obj, id_bytes, 1, &len); + long l; + Check_Type(v, T_STRING); + l = RSTRING_LEN(v); + if (l < n) + rb_raise(rb_eRangeError, "random data too short %ld", l); + else if (l > n) + rb_raise(rb_eRangeError, "random data too long %ld", l); + if (p) memcpy(p, RSTRING_PTR(v), n); + return v; +} + +static unsigned int +random_int32(const rb_random_interface_t *rng, rb_random_t *rnd) +{ + return rng->get_int32(rnd); +} + +unsigned int +rb_random_int32(VALUE obj) +{ + const rb_random_interface_t *rng; + rb_random_t *rnd = try_get_rnd(obj, &rng); + if (!rnd) { + uint32_t x; + obj_random_bytes(obj, &x, sizeof(x)); + return (unsigned int)x; + } + return random_int32(rng, rnd); +} + +static double +random_real(VALUE obj, const rb_random_interface_t *rng, rb_random_t *rnd, int excl) +{ + uint32_t a, b; + + if (!rnd) { + uint32_t x[2] = {0, 0}; + obj_random_bytes(obj, x, sizeof(x)); + a = x[0]; + b = x[1]; + } + else { + if (rng->get_real) return rng->get_real(rnd, excl); + a = random_int32(rng, rnd); + b = random_int32(rng, rnd); + } + return rb_int_pair_to_real(a, b, excl); +} + +double +rb_int_pair_to_real(uint32_t a, uint32_t b, int excl) +{ + if (excl) { + return int_pair_to_real_exclusive(a, b); + } + else { + return int_pair_to_real_inclusive(a, b); + } +} + +double +rb_random_real(VALUE obj) +{ + const rb_random_interface_t *rng; + rb_random_t *rnd = try_get_rnd(obj, &rng); + if (!rnd) { + VALUE v = rb_funcallv(obj, id_rand, 0, 0); + double d = NUM2DBL(v); + if (d < 0.0) { + rb_raise(rb_eRangeError, "random number too small %g", d); + } + else if (d >= 1.0) { + rb_raise(rb_eRangeError, "random number too big %g", d); } - BIG_SET32(val, i, rnd); + return d; + } + return random_real(obj, rng, rnd, TRUE); +} + +static inline VALUE +ulong_to_num_plus_1(unsigned long n) +{ +#if HAVE_LONG_LONG + return ULL2NUM((LONG_LONG)n+1); +#else + if (n >= ULONG_MAX) { + return rb_big_plus(ULONG2NUM(n), INT2FIX(1)); + } + return ULONG2NUM(n+1); +#endif +} + +static unsigned long +random_ulong_limited(VALUE obj, const rb_random_interface_t *rng, rb_random_t *rnd, unsigned long limit) +{ + if (!limit) return 0; + if (!rnd) { + const int w = sizeof(limit) * CHAR_BIT - nlz_long(limit); + const int n = w > 32 ? sizeof(unsigned long) : sizeof(uint32_t); + const unsigned long mask = ~(~0UL << w); + const unsigned long full = + (size_t)n >= sizeof(unsigned long) ? ~0UL : + ~(~0UL << n * CHAR_BIT); + unsigned long val, bits = 0, rest = 0; + do { + if (mask & ~rest) { + union {uint32_t u32; unsigned long ul;} buf; + obj_random_bytes(obj, &buf, n); + rest = full; + bits = (n == sizeof(uint32_t)) ? buf.u32 : buf.ul; + } + val = bits; + bits >>= w; + rest >>= w; + val &= mask; + } while (limit < val); + return val; } - return rb_big_norm((VALUE)val); + return limited_rand(rng, rnd, limit); +} + +unsigned long +rb_random_ulong_limited(VALUE obj, unsigned long limit) +{ + const rb_random_interface_t *rng; + rb_random_t *rnd = try_get_rnd(obj, &rng); + if (!rnd) { + VALUE lim = ulong_to_num_plus_1(limit); + VALUE v = rb_to_int(rb_funcallv_public(obj, id_rand, 1, &lim)); + unsigned long r = NUM2ULONG(v); + if (rb_num_negative_p(v)) { + rb_raise(rb_eRangeError, "random number too small %ld", r); + } + if (r > limit) { + rb_raise(rb_eRangeError, "random number too big %ld", r); + } + return r; + } + return limited_rand(rng, rnd, limit); +} + +static VALUE +random_ulong_limited_big(VALUE obj, const rb_random_interface_t *rng, rb_random_t *rnd, VALUE vmax) +{ + if (!rnd) { + VALUE v, vtmp; + size_t i, nlz, len = rb_absint_numwords(vmax, 32, &nlz); + uint32_t *tmp = ALLOCV_N(uint32_t, vtmp, len * 2); + uint32_t mask = (uint32_t)~0 >> nlz; + uint32_t *lim_array = tmp; + uint32_t *rnd_array = tmp + len; + int flag = INTEGER_PACK_MSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER; + rb_integer_pack(vmax, lim_array, len, sizeof(uint32_t), 0, flag); + + retry: + obj_random_bytes(obj, rnd_array, len * sizeof(uint32_t)); + rnd_array[0] &= mask; + for (i = 0; i < len; ++i) { + if (lim_array[i] < rnd_array[i]) + goto retry; + if (rnd_array[i] < lim_array[i]) + break; + } + v = rb_integer_unpack(rnd_array, len, sizeof(uint32_t), 0, flag); + ALLOCV_END(vtmp); + return v; + } + return limited_big_rand(rng, rnd, vmax); +} + +static VALUE +rand_bytes(const rb_random_interface_t *rng, rb_random_t *rnd, long n) +{ + VALUE bytes; + char *ptr; + + bytes = rb_str_new(0, n); + ptr = RSTRING_PTR(bytes); + rng->get_bytes(rnd, ptr, n); + return bytes; } /* - * call-seq: - * rand(max=0) => number - * - * Converts <i>max</i> to an integer using max1 = - * max<code>.to_i.abs</code>. If the result is zero, returns a - * pseudorandom floating point number greater than or equal to 0.0 and - * less than 1.0. Otherwise, returns a pseudorandom integer greater - * than or equal to zero and less than max1. <code>Kernel::srand</code> - * may be used to ensure repeatable sequences of random numbers between - * different runs of the program. Ruby currently uses a modified - * Mersenne Twister with a period of 2**19937-1. - * - * srand 1234 #=> 0 - * [ rand, rand ] #=> [0.191519450163469, 0.49766366626136] - * [ rand(10), rand(1000) ] #=> [6, 817] - * srand 1234 #=> 1234 - * [ rand, rand ] #=> [0.191519450163469, 0.49766366626136] + * call-seq: prng.bytes(size) -> string + * + * Returns a random binary string containing +size+ bytes. + * + * random_string = Random.new.bytes(10) # => "\xD7:R\xAB?\x83\xCE\xFAkO" + * random_string.size # => 10 */ +static VALUE +random_bytes(VALUE obj, VALUE len) +{ + const rb_random_interface_t *rng = NULL; + rb_random_t *rnd = try_get_rnd(obj, &rng); + return rand_bytes(rng, rnd, NUM2LONG(rb_to_int(len))); +} + +void +rb_rand_bytes_int32(rb_random_get_int32_func *get_int32, + rb_random_t *rnd, void *p, size_t n) +{ + char *ptr = p; + unsigned int r, i; + for (; n >= SIZEOF_INT32; n -= SIZEOF_INT32) { + r = get_int32(rnd); + i = SIZEOF_INT32; + do { + *ptr++ = (char)r; + r >>= CHAR_BIT; + } while (--i); + } + if (n > 0) { + r = get_int32(rnd); + do { + *ptr++ = (char)r; + r >>= CHAR_BIT; + } while (--n); + } +} +VALUE +rb_random_bytes(VALUE obj, long n) +{ + const rb_random_interface_t *rng; + rb_random_t *rnd = try_get_rnd(obj, &rng); + if (!rnd) { + return obj_random_bytes(obj, NULL, n); + } + return rand_bytes(rng, rnd, n); +} + +/* + * call-seq: Random.bytes(size) -> string + * + * Returns a random binary string. + * The argument +size+ specifies the length of the returned string. + */ static VALUE -rb_f_rand(int argc, VALUE *argv, VALUE obj) +random_s_bytes(VALUE obj, VALUE len) { - VALUE vmax; - long val, max; - - rb_scan_args(argc, argv, "01", &vmax); - switch (TYPE(vmax)) { - case T_FLOAT: - if (RFLOAT(vmax)->value <= LONG_MAX && RFLOAT(vmax)->value >= LONG_MIN) { - max = (long)RFLOAT(vmax)->value; - break; - } - if (RFLOAT(vmax)->value < 0) - vmax = rb_dbl2big(-RFLOAT(vmax)->value); - else - vmax = rb_dbl2big(RFLOAT(vmax)->value); - /* fall through */ - case T_BIGNUM: - bignum: - { - struct RBignum *limit = (struct RBignum *)vmax; - if (!limit->sign) { - limit = (struct RBignum *)rb_big_clone(vmax); - limit->sign = 1; + rb_random_t *rnd = default_rand_start(); + return rand_bytes(&random_mt_if, rnd, NUM2LONG(rb_to_int(len))); +} + +/* + * call-seq: Random.seed -> integer + * + * Returns the seed value used to initialize the Ruby system PRNG. + * This may be used to initialize another generator with the same + * state at a later time, causing it to produce the same sequence of + * numbers. + * + * Random.seed #=> 1234 + * prng1 = Random.new(Random.seed) + * prng1.seed #=> 1234 + * prng1.rand(100) #=> 47 + * Random.seed #=> 1234 + * Random.rand(100) #=> 47 + */ +static VALUE +random_s_seed(VALUE obj) +{ + rb_random_mt_t *rnd = default_mt(); + return rnd->base.seed; +} + +static VALUE +range_values(VALUE vmax, VALUE *begp, VALUE *endp, int *exclp) +{ + VALUE beg, end; + + if (!rb_range_values(vmax, &beg, &end, exclp)) return Qfalse; + if (begp) *begp = beg; + if (NIL_P(beg)) return Qnil; + if (endp) *endp = end; + if (NIL_P(end)) return Qnil; + return rb_check_funcall_default(end, id_minus, 1, begp, Qfalse); +} + +static VALUE +rand_int(VALUE obj, const rb_random_interface_t *rng, rb_random_t *rnd, VALUE vmax, int restrictive) +{ + /* mt must be initialized */ + unsigned long r; + + if (FIXNUM_P(vmax)) { + long max = FIX2LONG(vmax); + if (!max) return Qnil; + if (max < 0) { + if (restrictive) return Qnil; + max = -max; + } + r = random_ulong_limited(obj, rng, rnd, (unsigned long)max - 1); + return ULONG2NUM(r); + } + else { + VALUE ret; + if (rb_bigzero_p(vmax)) return Qnil; + if (!BIGNUM_SIGN(vmax)) { + if (restrictive) return Qnil; + vmax = rb_big_uminus(vmax); + } + vmax = rb_big_minus(vmax, INT2FIX(1)); + if (FIXNUM_P(vmax)) { + long max = FIX2LONG(vmax); + if (max == -1) return Qnil; + r = random_ulong_limited(obj, rng, rnd, max); + return LONG2NUM(r); + } + ret = random_ulong_limited_big(obj, rng, rnd, vmax); + RB_GC_GUARD(vmax); + return ret; + } +} + +static void +domain_error(void) +{ + VALUE error = INT2FIX(EDOM); + rb_exc_raise(rb_class_new_instance(1, &error, rb_eSystemCallError)); +} + +NORETURN(static void invalid_argument(VALUE)); +static void +invalid_argument(VALUE arg0) +{ + rb_raise(rb_eArgError, "invalid argument - %"PRIsVALUE, arg0); +} + +static VALUE +check_random_number(VALUE v, const VALUE *argv) +{ + switch (v) { + case Qfalse: + (void)NUM2LONG(argv[0]); + break; + case Qnil: + invalid_argument(argv[0]); + } + return v; +} + +static inline double +float_value(VALUE v) +{ + double x = RFLOAT_VALUE(v); + if (!isfinite(x)) { + domain_error(); + } + return x; +} + +static inline VALUE +rand_range(VALUE obj, const rb_random_interface_t *rng, rb_random_t* rnd, VALUE range) +{ + VALUE beg = Qundef, end = Qundef, vmax, v; + int excl = 0; + + if ((v = vmax = range_values(range, &beg, &end, &excl)) == Qfalse) + return Qfalse; + if (NIL_P(v)) domain_error(); + if (!RB_FLOAT_TYPE_P(vmax) && (v = rb_check_to_int(vmax), !NIL_P(v))) { + long max; + vmax = v; + v = Qnil; + fixnum: + if (FIXNUM_P(vmax)) { + if ((max = FIX2LONG(vmax) - excl) >= 0) { + unsigned long r = random_ulong_limited(obj, rng, rnd, (unsigned long)max); + v = ULONG2NUM(r); + } + } + else if (BUILTIN_TYPE(vmax) == T_BIGNUM && BIGNUM_SIGN(vmax) && !rb_bigzero_p(vmax)) { + vmax = excl ? rb_big_minus(vmax, INT2FIX(1)) : rb_big_norm(vmax); + if (FIXNUM_P(vmax)) { + excl = 0; + goto fixnum; } - limit = (struct RBignum *)rb_big_minus((VALUE)limit, INT2FIX(1)); - if (FIXNUM_P((VALUE)limit)) { - if (FIX2LONG((VALUE)limit) == -1) - return rb_float_new(genrand_real()); - return LONG2NUM(limited_rand(FIX2LONG((VALUE)limit))); + v = random_ulong_limited_big(obj, rng, rnd, vmax); + } + } + else if (v = rb_check_to_float(vmax), !NIL_P(v)) { + int scale = 1; + double max = RFLOAT_VALUE(v), mid = 0.5, r; + if (isinf(max)) { + double min = float_value(rb_to_float(beg)) / 2.0; + max = float_value(rb_to_float(end)) / 2.0; + scale = 2; + mid = max + min; + max -= min; + } + else if (isnan(max)) { + domain_error(); + } + v = Qnil; + if (max > 0.0) { + r = random_real(obj, rng, rnd, excl); + if (scale > 1) { + return rb_float_new(+(+(+(r - 0.5) * max) * scale) + mid); } - return limited_big_rand(limit); - } + v = rb_float_new(r * max); + } + else if (max == 0.0 && !excl) { + v = rb_float_new(0.0); + } + } + + if (FIXNUM_P(beg) && FIXNUM_P(v)) { + long x = FIX2LONG(beg) + FIX2LONG(v); + return LONG2NUM(x); + } + switch (TYPE(v)) { case T_NIL: - max = 0; - break; + break; + case T_BIGNUM: + return rb_big_plus(v, beg); + case T_FLOAT: { + VALUE f = rb_check_to_float(beg); + if (!NIL_P(f)) { + return DBL2NUM(RFLOAT_VALUE(v) + RFLOAT_VALUE(f)); + } + } default: - vmax = rb_Integer(vmax); - if (TYPE(vmax) == T_BIGNUM) goto bignum; - case T_FIXNUM: - max = FIX2LONG(vmax); - break; + return rb_funcallv(beg, id_plus, 1, &v); } - if (max == 0) { - return rb_float_new(genrand_real()); + return v; +} + +static VALUE rand_random(int argc, VALUE *argv, VALUE obj, const rb_random_interface_t *rng, rb_random_t *rnd); + +/* + * call-seq: + * prng.rand -> float + * prng.rand(max) -> number + * prng.rand(range) -> number + * + * When +max+ is an Integer, +rand+ returns a random integer greater than + * or equal to zero and less than +max+. Unlike Kernel.rand, when +max+ + * is a negative integer or zero, +rand+ raises an ArgumentError. + * + * prng = Random.new + * prng.rand(100) # => 42 + * + * When +max+ is a Float, +rand+ returns a random floating point number + * between 0.0 and +max+, including 0.0 and excluding +max+. Note that it + * behaves differently from Kernel.rand. + * + * prng.rand(1.5) # => 1.4600282860034115 + * rand(1.5) # => 0 + * + * When +range+ is a Range, +rand+ returns a random number where + * <code>range.member?(number) == true</code>. + * + * prng.rand(5..9) # => one of [5, 6, 7, 8, 9] + * prng.rand(5...9) # => one of [5, 6, 7, 8] + * prng.rand(5.0..9.0) # => between 5.0 and 9.0, including 9.0 + * prng.rand(5.0...9.0) # => between 5.0 and 9.0, excluding 9.0 + * + * Both the beginning and ending values of the range must respond to subtract + * (<tt>-</tt>) and add (<tt>+</tt>)methods, or rand will raise an + * ArgumentError. + */ +static VALUE +random_rand(int argc, VALUE *argv, VALUE obj) +{ + const rb_random_interface_t *rng = NULL; + rb_random_t *rnd = try_get_rnd(obj, &rng); + VALUE v = rand_random(argc, argv, obj, rng, rnd); + check_random_number(v, argv); + return v; +} + +static VALUE +rand_random(int argc, VALUE *argv, VALUE obj, const rb_random_interface_t *rng, rb_random_t *rnd) +{ + VALUE vmax, v; + + if (rb_check_arity(argc, 0, 1) == 0) { + return rb_float_new(random_real(obj, rng, rnd, TRUE)); + } + vmax = argv[0]; + if (NIL_P(vmax)) return Qnil; + if (!RB_FLOAT_TYPE_P(vmax)) { + v = rb_check_to_int(vmax); + if (!NIL_P(v)) return rand_int(obj, rng, rnd, v, 1); } - if (max < 0) max = -max; - val = limited_rand(max-1); - return LONG2NUM(val); + v = rb_check_to_float(vmax); + if (!NIL_P(v)) { + const double max = float_value(v); + if (max < 0.0) { + return Qnil; + } + else { + double r = random_real(obj, rng, rnd, TRUE); + if (max > 0.0) r *= max; + return rb_float_new(r); + } + } + return rand_range(obj, rng, rnd, vmax); } +/* + * call-seq: + * prng.random_number -> float + * prng.random_number(max) -> number + * prng.random_number(range) -> number + * prng.rand -> float + * prng.rand(max) -> number + * prng.rand(range) -> number + * + * Generates formatted random number from raw random bytes. + * See Random#rand. + */ +static VALUE +rand_random_number(int argc, VALUE *argv, VALUE obj) +{ + const rb_random_interface_t *rng = NULL; + rb_random_t *rnd = try_get_rnd(obj, &rng); + VALUE v = rand_random(argc, argv, obj, rng, rnd); + if (NIL_P(v)) v = rand_random(0, 0, obj, rng, rnd); + else if (!v) invalid_argument(argv[0]); + return v; +} + +/* + * call-seq: + * prng1 == prng2 -> true or false + * + * Returns true if the two generators have the same internal state, otherwise + * false. Equivalent generators will return the same sequence of + * pseudo-random numbers. Two generators will generally have the same state + * only if they were initialized with the same seed + * + * Random.new == Random.new # => false + * Random.new(1234) == Random.new(1234) # => true + * + * and have the same invocation history. + * + * prng1 = Random.new(1234) + * prng2 = Random.new(1234) + * prng1 == prng2 # => true + * + * prng1.rand # => 0.1915194503788923 + * prng1 == prng2 # => false + * + * prng2.rand # => 0.1915194503788923 + * prng1 == prng2 # => true + */ +static VALUE +rand_mt_equal(VALUE self, VALUE other) +{ + rb_random_mt_t *r1, *r2; + if (rb_obj_class(self) != rb_obj_class(other)) return Qfalse; + r1 = get_rnd_mt(self); + r2 = get_rnd_mt(other); + if (memcmp(r1->mt.state, r2->mt.state, sizeof(r1->mt.state))) return Qfalse; + if ((r1->mt.next - r1->mt.state) != (r2->mt.next - r2->mt.state)) return Qfalse; + if (r1->mt.left != r2->mt.left) return Qfalse; + return rb_equal(r1->base.seed, r2->base.seed); +} + +/* + * call-seq: + * rand(max=0) -> number + * + * If called without an argument, or if <tt>max.to_i.abs == 0</tt>, rand + * returns a pseudo-random floating point number between 0.0 and 1.0, + * including 0.0 and excluding 1.0. + * + * rand #=> 0.2725926052826416 + * + * When +max.abs+ is greater than or equal to 1, +rand+ returns a pseudo-random + * integer greater than or equal to 0 and less than +max.to_i.abs+. + * + * rand(100) #=> 12 + * + * When +max+ is a Range, +rand+ returns a random number where + * <code>range.member?(number) == true</code>. + * + * Negative or floating point values for +max+ are allowed, but may give + * surprising results. + * + * rand(-100) # => 87 + * rand(-0.5) # => 0.8130921818028143 + * rand(1.9) # equivalent to rand(1), which is always 0 + * + * Kernel.srand may be used to ensure that sequences of random numbers are + * reproducible between different runs of a program. + * + * Related: Random.rand. + * rand(100.0) # => 64 (Integer because max.to_i is 100) + * Random.rand(100.0) # => 30.315320967824523 + */ + +static VALUE +rb_f_rand(int argc, VALUE *argv, VALUE obj) +{ + VALUE vmax; + const rb_random_interface_t *rng = &random_mt_if; + rb_random_t *rnd = default_rand_start(); + + if (rb_check_arity(argc, 0, 1) && !NIL_P(vmax = argv[0])) { + VALUE v = rand_range(obj, rng, rnd, vmax); + if (v != Qfalse) return v; + vmax = rb_to_int(vmax); + if (vmax != INT2FIX(0)) { + v = rand_int(obj, rng, rnd, vmax, 0); + if (!NIL_P(v)) return v; + } + } + return DBL2NUM(random_real(obj, rng, rnd, TRUE)); +} + +/* + * call-seq: + * Random.rand -> float + * Random.rand(max) -> number + * Random.rand(range) -> number + * + * Returns a random number using the Ruby system PRNG. + * + * See also Random#rand. + */ +static VALUE +random_s_rand(int argc, VALUE *argv, VALUE obj) +{ + VALUE v = rand_random(argc, argv, Qnil, &random_mt_if, default_rand_start()); + check_random_number(v, argv); + return v; +} + +#define SIP_HASH_STREAMING 0 +#define sip_hash13 ruby_sip_hash13 +#if !defined _WIN32 && !defined BYTE_ORDER +# ifdef WORDS_BIGENDIAN +# define BYTE_ORDER BIG_ENDIAN +# else +# define BYTE_ORDER LITTLE_ENDIAN +# endif +# ifndef LITTLE_ENDIAN +# define LITTLE_ENDIAN 1234 +# endif +# ifndef BIG_ENDIAN +# define BIG_ENDIAN 4321 +# endif +#endif +#include "siphash.c" + +typedef struct { + st_index_t hash; + uint8_t sip[16]; +} hash_salt_t; + +static union { + hash_salt_t key; + uint32_t u32[type_roomof(hash_salt_t, uint32_t)]; +} hash_salt; + +static void +init_hash_salt(struct MT *mt) +{ + int i; + + for (i = 0; i < numberof(hash_salt.u32); ++i) + hash_salt.u32[i] = genrand_int32(mt); +} + +NO_SANITIZE("unsigned-integer-overflow", extern st_index_t rb_hash_start(st_index_t h)); +st_index_t +rb_hash_start(st_index_t h) +{ + return st_hash_start(hash_salt.key.hash + h); +} + +st_index_t +rb_memhash(const void *ptr, long len) +{ + sip_uint64_t h = sip_hash13(hash_salt.key.sip, ptr, len); +#ifdef HAVE_UINT64_T + return (st_index_t)h; +#else + return (st_index_t)(h.u32[0] ^ h.u32[1]); +#endif +} + +/* Initialize Ruby internal seeds. This function is called at very early stage + * of Ruby startup. Thus, you can't use Ruby's object. */ void -Init_Random(void) +Init_RandomSeedCore(void) +{ + if (!fill_random_bytes(&hash_salt, sizeof(hash_salt), FALSE)) return; + + /* + If failed to fill siphash's salt with random data, expand less random + data with MT. + + Don't reuse this MT for default_rand(). default_rand()::seed shouldn't + provide a hint that an attacker guess siphash's seed. + */ + struct MT mt; + + with_random_seed(DEFAULT_SEED_CNT, 0, false) { + init_by_array(&mt, seedbuf, DEFAULT_SEED_CNT); + } + + init_hash_salt(&mt); + explicit_bzero(&mt, sizeof(mt)); +} + +void +rb_reset_random_seed(void) +{ + rb_random_mt_t *r = default_rand(); + uninit_genrand(&r->mt); + r->base.seed = INT2FIX(0); +} + +/* + * Document-class: Random + * + * Random provides an interface to Ruby's pseudo-random number generator, or + * PRNG. The PRNG produces a deterministic sequence of bits which approximate + * true randomness. The sequence may be represented by integers, floats, or + * binary strings. + * + * The generator may be initialized with either a system-generated or + * user-supplied seed value by using Random.srand. + * + * The class method Random.rand provides the base functionality of Kernel.rand + * along with better handling of floating point values. These are both + * interfaces to the Ruby system PRNG. + * + * Random.new will create a new PRNG with a state independent of the Ruby + * system PRNG, allowing multiple generators with different seed values or + * sequence positions to exist simultaneously. Random objects can be + * marshaled, allowing sequences to be saved and resumed. + * + * PRNGs are currently implemented as a modified Mersenne Twister with a period + * of 2**19937-1. As this algorithm is _not_ for cryptographical use, you must + * use SecureRandom for security purpose, instead of this PRNG. + * + * See also Random::Formatter module that adds convenience methods to generate + * various forms of random data. + */ + +void +InitVM_Random(void) { - rand_init(random_seed()); + VALUE base; + ID id_base = rb_intern_const("Base"); + rb_define_global_function("srand", rb_f_srand, -1); rb_define_global_function("rand", rb_f_rand, -1); - rb_global_variable(&saved_seed); + + base = rb_define_class_id(id_base, rb_cObject); + rb_undef_alloc_func(base); + rb_cRandom = rb_define_class("Random", base); + rb_const_set(rb_cRandom, id_base, base); + rb_define_alloc_func(rb_cRandom, random_alloc); + rb_define_method(base, "initialize", random_init, -1); + rb_define_method(base, "rand", random_rand, -1); + rb_define_method(base, "bytes", random_bytes, 1); + rb_define_method(base, "seed", random_get_seed, 0); + rb_define_method(rb_cRandom, "initialize_copy", rand_mt_copy, 1); + rb_define_private_method(rb_cRandom, "marshal_dump", rand_mt_dump, 0); + rb_define_private_method(rb_cRandom, "marshal_load", rand_mt_load, 1); + rb_define_private_method(rb_cRandom, "state", rand_mt_state, 0); + rb_define_private_method(rb_cRandom, "left", rand_mt_left, 0); + rb_define_method(rb_cRandom, "==", rand_mt_equal, 1); + +#if 0 /* for RDoc: it can't handle unnamed base class */ + rb_define_method(rb_cRandom, "initialize", random_init, -1); + rb_define_method(rb_cRandom, "rand", random_rand, -1); + rb_define_method(rb_cRandom, "bytes", random_bytes, 1); + rb_define_method(rb_cRandom, "seed", random_get_seed, 0); +#endif + + rb_define_singleton_method(rb_cRandom, "srand", rb_f_srand, -1); + rb_define_singleton_method(rb_cRandom, "rand", random_s_rand, -1); + rb_define_singleton_method(rb_cRandom, "bytes", random_s_bytes, 1); + rb_define_singleton_method(rb_cRandom, "seed", random_s_seed, 0); + rb_define_singleton_method(rb_cRandom, "new_seed", random_seed, 0); + rb_define_singleton_method(rb_cRandom, "urandom", random_raw_seed, 1); + rb_define_private_method(CLASS_OF(rb_cRandom), "state", random_s_state, 0); + rb_define_private_method(CLASS_OF(rb_cRandom), "left", random_s_left, 0); + + { + /* + * Generate a random number in the given range as Random does + * + * prng.random_number #=> 0.5816771641321361 + * prng.random_number(1000) #=> 485 + * prng.random_number(1..6) #=> 3 + * prng.rand #=> 0.5816771641321361 + * prng.rand(1000) #=> 485 + * prng.rand(1..6) #=> 3 + */ + VALUE m = rb_define_module_under(rb_cRandom, "Formatter"); + rb_include_module(base, m); + rb_extend_object(base, m); + rb_define_method(m, "random_number", rand_random_number, -1); + rb_define_method(m, "rand", rand_random_number, -1); + } + + default_rand_key = rb_ractor_local_storage_ptr_newkey(&default_rand_key_storage_type); +} + +#undef rb_intern +void +Init_Random(void) +{ + id_rand = rb_intern("rand"); + id_bytes = rb_intern("bytes"); + + InitVM(Random); } |