From fcbf63e62c627deae76c1b8cb8c0876c536ed811 Mon Sep 17 00:00:00 2001 From: Jari Vetoniemi Date: Mon, 16 Mar 2020 18:49:26 +0900 Subject: Fresh start --- jni/ruby/random.c | 1395 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1395 insertions(+) create mode 100644 jni/ruby/random.c (limited to 'jni/ruby/random.c') diff --git a/jni/ruby/random.c b/jni/ruby/random.c new file mode 100644 index 0000000..1053555 --- /dev/null +++ b/jni/ruby/random.c @@ -0,0 +1,1395 @@ +/********************************************************************** + + random.c - + + $Author: nobu $ + created at: Fri Dec 24 16:39:21 JST 1993 + + Copyright (C) 1993-2007 Yukihiro Matsumoto + +**********************************************************************/ + +/* +This is based on trimmed version of MT19937. To get the original version, +contact . + +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(mt, seed) + or init_by_array(mt, 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 +*/ + +#include "internal.h" + +#include +#ifdef HAVE_UNISTD_H +#include +#endif +#include +#include +#include +#ifdef HAVE_FCNTL_H +#include +#endif +#include +#include +#if defined(HAVE_SYS_TIME_H) +#include +#endif + +#ifdef _WIN32 +# if !defined(_WIN32_WINNT) || _WIN32_WINNT < 0x0400 +# undef _WIN32_WINNT +# define _WIN32_WINNT 0x400 +# undef __WINCRYPT_H__ +# endif +#include +#endif + +typedef int int_must_be_32bit_at_least[sizeof(int) * CHAR_BIT < 32 ? -1 : 1]; + +/* Period parameters */ +#define N 624 +#define M 397 +#define MATRIX_A 0x9908b0dfU /* constant vector a */ +#define UMASK 0x80000000U /* most significant w-r bits */ +#define LMASK 0x7fffffffU /* least significant r bits */ +#define MIXBITS(u,v) ( ((u) & UMASK) | ((v) & LMASK) ) +#define TWIST(u,v) ((MIXBITS((u),(v)) >> 1) ^ ((v)&1U ? MATRIX_A : 0U)) + +enum {MT_MAX_STATE = N}; + +struct MT { + /* assume int is enough to store 32bits */ + unsigned int state[N]; /* the array for the state vector */ + unsigned int *next; + int left; +}; + +#define genrand_initialized(mt) ((mt)->next != 0) +#define uninit_genrand(mt) ((mt)->next = 0) + +/* initializes state[N] with a seed */ +static void +init_genrand(struct MT *mt, unsigned int s) +{ + int j; + mt->state[0] = s & 0xffffffffU; + for (j=1; jstate[j] = (1812433253U * (mt->state[j-1] ^ (mt->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 */ + mt->state[j] &= 0xffffffff; /* for >32 bit machines */ + } + mt->left = 1; + mt->next = mt->state + N; +} + +/* 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(struct MT *mt, unsigned int init_key[], int key_length) +{ + int i, j, k; + init_genrand(mt, 19650218U); + i=1; j=0; + k = (N>key_length ? N : key_length); + for (; k; k--) { + mt->state[i] = (mt->state[i] ^ ((mt->state[i-1] ^ (mt->state[i-1] >> 30)) * 1664525U)) + + init_key[j] + j; /* non linear */ + mt->state[i] &= 0xffffffffU; /* for WORDSIZE > 32 machines */ + i++; j++; + if (i>=N) { mt->state[0] = mt->state[N-1]; i=1; } + if (j>=key_length) j=0; + } + for (k=N-1; k; k--) { + mt->state[i] = (mt->state[i] ^ ((mt->state[i-1] ^ (mt->state[i-1] >> 30)) * 1566083941U)) + - i; /* non linear */ + mt->state[i] &= 0xffffffffU; /* for WORDSIZE > 32 machines */ + i++; + if (i>=N) { mt->state[0] = mt->state[N-1]; i=1; } + } + + mt->state[0] = 0x80000000U; /* MSB is 1; assuring non-zero initial array */ +} + +static void +next_state(struct MT *mt) +{ + unsigned int *p = mt->state; + int j; + + mt->left = N; + mt->next = mt->state; + + for (j=N-M+1; --j; p++) + *p = p[M] ^ TWIST(p[0], p[1]); + + for (j=M; --j; p++) + *p = p[M-N] ^ TWIST(p[0], p[1]); + + *p = p[M-N] ^ TWIST(p[0], mt->state[0]); +} + +/* generates a random number on [0,0xffffffff]-interval */ +static unsigned int +genrand_int32(struct MT *mt) +{ + /* mt must be initialized */ + unsigned int y; + + if (--mt->left <= 0) next_state(mt); + y = *mt->next++; + + /* Tempering */ + y ^= (y >> 11); + y ^= (y << 7) & 0x9d2c5680; + y ^= (y << 15) & 0xefc60000; + y ^= (y >> 18); + + return y; +} + +/* generates a random number on [0,1) with 53-bit resolution*/ +static double +genrand_real(struct MT *mt) +{ + /* mt must be initialized */ + unsigned int a = genrand_int32(mt)>>5, b = genrand_int32(mt)>>6; + return(a*67108864.0+b)*(1.0/9007199254740992.0); +} + +/* generates a random number on [0,1] with 53-bit resolution*/ +static double int_pair_to_real_inclusive(uint32_t a, uint32_t b); +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); +} + +/* These real versions are due to Isaku Wada, 2002/01/09 added */ + +#undef N +#undef M + +typedef struct { + VALUE seed; + struct MT mt; +} rb_random_t; + +#define DEFAULT_SEED_CNT 4 + +static rb_random_t default_rand; + +static VALUE rand_init(struct MT *mt, VALUE vseed); +static VALUE random_seed(void); + +static rb_random_t * +rand_start(rb_random_t *r) +{ + struct MT *mt = &r->mt; + if (!genrand_initialized(mt)) { + r->seed = rand_init(mt, random_seed()); + } + return r; +} + +static struct MT * +default_mt(void) +{ + return &rand_start(&default_rand)->mt; +} + +unsigned int +rb_genrand_int32(void) +{ + struct MT *mt = default_mt(); + return genrand_int32(mt); +} + +double +rb_genrand_real(void) +{ + struct MT *mt = default_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) +{ + VALUE x; + VALUE m; + uint32_t xary[2], mary[2]; + double r; + + /* (a << 32) | b */ + xary[0] = a; + xary[1] = b; + x = rb_integer_unpack(xary, 2, sizeof(uint32_t), 0, + INTEGER_PACK_MSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER| + INTEGER_PACK_FORCE_BIGNUM); + + /* (1 << 53) | 1 */ + mary[0] = 0x00200000; + mary[1] = 0x00000001; + m = rb_integer_unpack(mary, 2, sizeof(uint32_t), 0, + INTEGER_PACK_MSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER| + INTEGER_PACK_FORCE_BIGNUM); + + x = rb_big_mul(x, m); + if (FIXNUM_P(x)) { +#if CHAR_BIT * SIZEOF_LONG > 64 + r = (double)(FIX2ULONG(x) >> 64); +#else + return 0.0; +#endif + } + else { + uint32_t uary[4]; + rb_integer_pack(x, uary, numberof(uary), sizeof(uint32_t), 0, + INTEGER_PACK_MSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); + /* r = x >> 64 */ + r = (double)uary[0] * (0x10000 * (double)0x10000) + (double)uary[1]; + } + return ldexp(r, -53); +} + +VALUE rb_cRandom; +#define id_minus '-' +#define id_plus '+' +static ID id_rand, id_bytes; + +/* :nodoc: */ +static void +random_mark(void *ptr) +{ + rb_gc_mark(((rb_random_t *)ptr)->seed); +} + +static void +random_free(void *ptr) +{ + if (ptr != &default_rand) + xfree(ptr); +} + +static size_t +random_memsize(const void *ptr) +{ + return ptr ? sizeof(rb_random_t) : 0; +} + +static const rb_data_type_t random_data_type = { + "random", + { + random_mark, + random_free, + random_memsize, + }, + 0, 0, RUBY_TYPED_FREE_IMMEDIATELY +}; + +static rb_random_t * +get_rnd(VALUE obj) +{ + rb_random_t *ptr; + TypedData_Get_Struct(obj, rb_random_t, &random_data_type, ptr); + return ptr; +} + +static rb_random_t * +try_get_rnd(VALUE obj) +{ + if (obj == rb_cRandom) { + return rand_start(&default_rand); + } + if (!rb_typeddata_is_kind_of(obj, &random_data_type)) return NULL; + return DATA_PTR(obj); +} + +/* :nodoc: */ +static VALUE +random_alloc(VALUE klass) +{ + rb_random_t *rnd; + VALUE obj = TypedData_Make_Struct(klass, rb_random_t, &random_data_type, rnd); + rnd->seed = INT2FIX(0); + return obj; +} + +static VALUE +rand_init(struct MT *mt, VALUE vseed) +{ + volatile VALUE seed; + uint32_t buf0[SIZEOF_LONG / SIZEOF_INT32 * 4], *buf = buf0; + size_t len; + int sign; + + seed = rb_to_int(vseed); + + len = rb_absint_numwords(seed, 32, NULL); + if (len > numberof(buf0)) + buf = ALLOC_N(unsigned int, 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 == 0) { + buf[0] = 0; + len = 1; + } + if (len <= 1) { + init_genrand(mt, buf[0]); + } + else { + if (sign != 2 && buf[len-1] == 1) /* remove leading-zero-guard */ + len--; + init_by_array(mt, buf, (int)len); + } + if (buf != buf0) xfree(buf); + 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) +{ + VALUE vseed; + rb_random_t *rnd = get_rnd(obj); + + if (argc == 0) { + rb_check_frozen(obj); + vseed = random_seed(); + } + else { + rb_scan_args(argc, argv, "01", &vseed); + rb_check_copyable(obj, vseed); + } + rnd->seed = rand_init(&rnd->mt, vseed); + return obj; +} + +#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 + +static void +fill_random_seed(uint32_t seed[DEFAULT_SEED_CNT]) +{ + static int n = 0; + struct timeval tv; +#if USE_DEV_URANDOM + int fd; + struct stat statbuf; +#elif defined(_WIN32) + HCRYPTPROV prov; +#endif + + memset(seed, 0, DEFAULT_SEED_LEN); + +#if USE_DEV_URANDOM + if ((fd = rb_cloexec_open("/dev/urandom", O_RDONLY +#ifdef O_NONBLOCK + |O_NONBLOCK +#endif +#ifdef O_NOCTTY + |O_NOCTTY +#endif + , 0)) >= 0) { + rb_update_max_fd(fd); + if (fstat(fd, &statbuf) == 0 && S_ISCHR(statbuf.st_mode)) { + if (read(fd, seed, DEFAULT_SEED_LEN) < DEFAULT_SEED_LEN) { + /* abandon */; + } + } + close(fd); + } +#elif defined(_WIN32) + if (CryptAcquireContext(&prov, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) { + CryptGenRandom(prov, DEFAULT_SEED_LEN, (void *)seed); + CryptReleaseContext(prov, 0); + } +#endif + + gettimeofday(&tv, 0); + seed[0] ^= tv.tv_usec; + 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() ^ (n++ << 16); + seed[3] ^= (uint32_t)(VALUE)&seed; +#if SIZEOF_VOIDP > SIZEOF_INT + seed[2] ^= (uint32_t)((VALUE)&seed >> SIZEOF_INT * CHAR_BIT); +#endif +} + +static VALUE +make_seed_value(const uint32_t *ptr) +{ + VALUE seed; + size_t len; + uint32_t buf[DEFAULT_SEED_CNT+1]; + + if (ptr[DEFAULT_SEED_CNT-1] <= 1) { + /* set leading-zero-guard */ + MEMCPY(buf, ptr, uint32_t, DEFAULT_SEED_CNT); + buf[DEFAULT_SEED_CNT] = 1; + ptr = buf; + len = DEFAULT_SEED_CNT+1; + } + else { + len = DEFAULT_SEED_CNT; + } + + seed = rb_integer_unpack(ptr, len, sizeof(uint32_t), 0, + INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); + + return seed; +} + +/* + * 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(void) +{ + uint32_t buf[DEFAULT_SEED_CNT]; + fill_random_seed(buf); + return make_seed_value(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 +random_copy(VALUE obj, VALUE orig) +{ + rb_random_t *rnd1, *rnd2; + struct MT *mt; + + if (!OBJ_INIT_COPY(obj, orig)) return obj; + + rnd1 = get_rnd(obj); + rnd2 = get_rnd(orig); + mt = &rnd1->mt; + + *rnd1 = *rnd2; + 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 +random_state(VALUE obj) +{ + rb_random_t *rnd = get_rnd(obj); + return mt_state(&rnd->mt); +} + +/* :nodoc: */ +static VALUE +random_s_state(VALUE klass) +{ + return mt_state(&default_rand.mt); +} + +/* :nodoc: */ +static VALUE +random_left(VALUE obj) +{ + rb_random_t *rnd = get_rnd(obj); + return INT2FIX(rnd->mt.left); +} + +/* :nodoc: */ +static VALUE +random_s_left(VALUE klass) +{ + return INT2FIX(default_rand.mt.left); +} + +/* :nodoc: */ +static VALUE +random_dump(VALUE obj) +{ + rb_random_t *rnd = get_rnd(obj); + 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->seed); + + return dump; +} + +/* :nodoc: */ +static VALUE +random_load(VALUE obj, VALUE dump) +{ + rb_random_t *rnd = get_rnd(obj); + struct MT *mt = &rnd->mt; + VALUE state, left = INT2FIX(1), seed = INT2FIX(0); + const VALUE *ary; + unsigned long x; + + rb_check_copyable(obj, dump); + Check_Type(dump, T_ARRAY); + ary = RARRAY_CONST_PTR(dump); + switch (RARRAY_LEN(dump)) { + case 3: + seed = ary[2]; + case 2: + left = ary[1]; + case 1: + state = ary[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)) { + rb_raise(rb_eArgError, "wrong value"); + } + mt->left = (unsigned int)x; + mt->next = mt->state + numberof(mt->state) - x + 1; + rnd->seed = rb_to_int(seed); + + return obj; +} + +/* + * call-seq: + * srand(number = Random.new_seed) -> old_seed + * + * Seeds the system pseudo-random number generator, Random::DEFAULT, 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_t *r = &default_rand; + + if (argc == 0) { + seed = random_seed(); + } + else { + rb_scan_args(argc, argv, "01", &seed); + } + old = r->seed; + r->seed = rand_init(&r->mt, seed); + + return old; +} + +static unsigned long +make_mask(unsigned long x) +{ + x = x | x >> 1; + x = x | x >> 2; + x = x | x >> 4; + x = x | x >> 8; + x = x | x >> 16; +#if 4 < SIZEOF_LONG + x = x | x >> 32; +#endif + return x; +} + +static unsigned long +limited_rand(struct MT *mt, unsigned long limit) +{ + /* mt must be initialized */ + int i; + unsigned long val, mask; + + if (!limit) return 0; + mask = make_mask(limit); + retry: + val = 0; + for (i = SIZEOF_LONG/SIZEOF_INT32-1; 0 <= i; i--) { + if ((mask >> (i * 32)) & 0xffffffff) { + val |= (unsigned long)genrand_int32(mt) << (i * 32); + val &= mask; + if (limit < val) + goto retry; + } + } + return val; +} + +static VALUE +limited_big_rand(struct MT *mt, VALUE limit) +{ + /* 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); + + retry: + mask = 0; + boundary = 1; + for (i = len-1; 0 <= i; i--) { + uint32_t rnd; + uint32_t lim = lim_array[i]; + mask = mask ? 0xffffffff : (uint32_t)make_mask(lim); + if (mask) { + rnd = genrand_int32(mt) & mask; + if (boundary) { + if (lim < rnd) + goto retry; + if (rnd < lim) + boundary = 0; + } + } + else { + rnd = 0; + } + rnd_array[i] = rnd; + } + 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) +{ + return limited_rand(default_mt(), limit); +} + +unsigned int +rb_random_int32(VALUE obj) +{ + rb_random_t *rnd = try_get_rnd(obj); + if (!rnd) { +#if SIZEOF_LONG * CHAR_BIT > 32 + VALUE lim = ULONG2NUM(0x100000000UL); +#elif defined HAVE_LONG_LONG + VALUE lim = ULL2NUM((LONG_LONG)0xffffffff+1); +#else + VALUE lim = rb_big_plus(ULONG2NUM(0xffffffff), INT2FIX(1)); +#endif + return (unsigned int)NUM2ULONG(rb_funcall2(obj, id_rand, 1, &lim)); + } + return genrand_int32(&rnd->mt); +} + +double +rb_random_real(VALUE obj) +{ + rb_random_t *rnd = try_get_rnd(obj); + if (!rnd) { + VALUE v = rb_funcall2(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); + } + return d; + } + return genrand_real(&rnd->mt); +} + +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 +} + +unsigned long +rb_random_ulong_limited(VALUE obj, unsigned long limit) +{ + rb_random_t *rnd = try_get_rnd(obj); + if (!rnd) { + extern int rb_num_negative_p(VALUE); + VALUE lim = ulong_to_num_plus_1(limit); + VALUE v = rb_to_int(rb_funcall2(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(&rnd->mt, limit); +} + +/* + * call-seq: prng.bytes(size) -> a_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) +{ + return rb_random_bytes(obj, NUM2LONG(rb_to_int(len))); +} + +VALUE +rb_random_bytes(VALUE obj, long n) +{ + rb_random_t *rnd = try_get_rnd(obj); + VALUE bytes; + char *ptr; + unsigned int r, i; + + if (!rnd) { + VALUE len = LONG2NUM(n); + return rb_funcall2(obj, id_bytes, 1, &len); + } + bytes = rb_str_new(0, n); + ptr = RSTRING_PTR(bytes); + for (; n >= SIZEOF_INT32; n -= SIZEOF_INT32) { + r = genrand_int32(&rnd->mt); + i = SIZEOF_INT32; + do { + *ptr++ = (char)r; + r >>= CHAR_BIT; + } while (--i); + } + if (n > 0) { + r = genrand_int32(&rnd->mt); + do { + *ptr++ = (char)r; + r >>= CHAR_BIT; + } while (--n); + } + return bytes; +} + +static VALUE +range_values(VALUE vmax, VALUE *begp, VALUE *endp, int *exclp) +{ + VALUE end, r; + + if (!rb_range_values(vmax, begp, &end, exclp)) return Qfalse; + if (endp) *endp = end; + if (!rb_respond_to(end, id_minus)) return Qfalse; + r = rb_funcall2(end, id_minus, 1, begp); + if (NIL_P(r)) return Qfalse; + return r; +} + +static VALUE +rand_int(struct MT *mt, VALUE vmax, int restrictive) +{ + /* mt must be initialized */ + long max; + unsigned long r; + + if (FIXNUM_P(vmax)) { + max = FIX2LONG(vmax); + if (!max) return Qnil; + if (max < 0) { + if (restrictive) return Qnil; + max = -max; + } + r = limited_rand(mt, (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)) { + max = FIX2LONG(vmax); + if (max == -1) return Qnil; + r = limited_rand(mt, max); + return LONG2NUM(r); + } + ret = limited_big_rand(mt, vmax); + RB_GC_GUARD(vmax); + return ret; + } +} + +static inline double +float_value(VALUE v) +{ + double x = RFLOAT_VALUE(v); + if (isinf(x) || isnan(x)) { + VALUE error = INT2FIX(EDOM); + rb_exc_raise(rb_class_new_instance(1, &error, rb_eSystemCallError)); + } + return x; +} + +static inline VALUE +rand_range(struct MT* mt, 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 (!RB_TYPE_P(vmax, T_FLOAT) && (v = rb_check_to_integer(vmax, "to_int"), !NIL_P(v))) { + long max; + vmax = v; + v = Qnil; + if (FIXNUM_P(vmax)) { + fixnum: + if ((max = FIX2LONG(vmax) - excl) >= 0) { + unsigned long r = limited_rand(mt, (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; + } + v = limited_big_rand(mt, 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 { + float_value(v); + } + v = Qnil; + if (max > 0.0) { + if (excl) { + r = genrand_real(mt); + } + else { + r = genrand_real2(mt); + } + if (scale > 1) { + return rb_float_new(+(+(+(r - 0.5) * max) * scale) + mid); + } + 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: + 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: + return rb_funcall2(beg, id_plus, 1, &v); + } + + return v; +} + +static VALUE rand_random(int argc, VALUE *argv, rb_random_t *rnd); + +/* + * call-seq: + * prng.rand -> float + * prng.rand(max) -> 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+. + * + * prng.rand(1.5) # => 1.4600282860034115 + * + * When +max+ is a Range, +rand+ returns a random number where + * range.member?(number) == true. + * + * 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 + * (-) and add (+)methods, or rand will raise an + * ArgumentError. + */ +static VALUE +random_rand(int argc, VALUE *argv, VALUE obj) +{ + return rand_random(argc, argv, get_rnd(obj)); +} + +static VALUE +rand_random(int argc, VALUE *argv, rb_random_t *rnd) +{ + VALUE vmax, v; + + if (argc == 0) { + return rb_float_new(genrand_real(&rnd->mt)); + } + else { + rb_check_arity(argc, 0, 1); + } + vmax = argv[0]; + if (NIL_P(vmax)) { + v = Qnil; + } + else if (!RB_TYPE_P(vmax, T_FLOAT) && (v = rb_check_to_integer(vmax, "to_int"), !NIL_P(v))) { + v = rand_int(&rnd->mt, v, 1); + } + else if (v = rb_check_to_float(vmax), !NIL_P(v)) { + double max = float_value(v); + if (max > 0.0) + v = rb_float_new(max * genrand_real(&rnd->mt)); + else + v = Qnil; + } + else if ((v = rand_range(&rnd->mt, vmax)) != Qfalse) { + /* nothing to do */ + } + else { + v = Qnil; + (void)NUM2LONG(vmax); + } + if (NIL_P(v)) { + VALUE mesg = rb_str_new_cstr("invalid argument - "); + rb_str_append(mesg, rb_obj_as_string(argv[0])); + rb_exc_raise(rb_exc_new3(rb_eArgError, mesg)); + } + + 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 +random_equal(VALUE self, VALUE other) +{ + rb_random_t *r1, *r2; + if (rb_obj_class(self) != rb_obj_class(other)) return Qfalse; + r1 = get_rnd(self); + r2 = get_rnd(other); + if (!RTEST(rb_funcall2(r1->seed, rb_intern("=="), 1, &r2->seed))) return Qfalse; + 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 Qtrue; +} + +/* + * call-seq: + * rand(max=0) -> number + * + * If called without an argument, or if max.to_i.abs == 0, 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 + * range.member?(number) == true. + * + * 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. + * + * See also Random.rand. + */ + +static VALUE +rb_f_rand(int argc, VALUE *argv, VALUE obj) +{ + VALUE v, vmax, r; + struct MT *mt = default_mt(); + + if (argc == 0) goto zero_arg; + rb_scan_args(argc, argv, "01", &vmax); + if (NIL_P(vmax)) goto zero_arg; + if ((v = rand_range(mt, vmax)) != Qfalse) { + return v; + } + vmax = rb_to_int(vmax); + if (vmax == INT2FIX(0) || NIL_P(r = rand_int(mt, vmax, 0))) { + zero_arg: + return DBL2NUM(genrand_real(mt)); + } + return r; +} + +/* + * call-seq: + * Random.rand -> float + * Random.rand(max) -> number + * + * Alias of Random::DEFAULT.rand. + */ + +static VALUE +random_s_rand(int argc, VALUE *argv, VALUE obj) +{ + return rand_random(argc, argv, rand_start(&default_rand)); +} + +#define SIP_HASH_STREAMING 0 +#define sip_hash24 ruby_sip_hash24 +#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" + +static st_index_t hashseed; +static union { + uint8_t key[16]; + uint32_t u32[(16 * sizeof(uint8_t) - 1) / sizeof(uint32_t)]; +} sipseed; + +static VALUE +init_randomseed(struct MT *mt, uint32_t initial[DEFAULT_SEED_CNT]) +{ + VALUE seed; + fill_random_seed(initial); + init_by_array(mt, initial, DEFAULT_SEED_CNT); + seed = make_seed_value(initial); + memset(initial, 0, DEFAULT_SEED_LEN); + return seed; +} + +void +Init_RandomSeed(void) +{ + rb_random_t *r = &default_rand; + uint32_t initial[DEFAULT_SEED_CNT]; + struct MT *mt = &r->mt; + VALUE seed = init_randomseed(mt, initial); + int i; + + hashseed = genrand_int32(mt); +#if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8 + hashseed <<= 32; + hashseed |= genrand_int32(mt); +#endif +#if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8 + hashseed <<= 32; + hashseed |= genrand_int32(mt); +#endif +#if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8 + hashseed <<= 32; + hashseed |= genrand_int32(mt); +#endif + + for (i = 0; i < numberof(sipseed.u32); ++i) + sipseed.u32[i] = genrand_int32(mt); + + rb_global_variable(&r->seed); + r->seed = seed; +} + +st_index_t +rb_hash_start(st_index_t h) +{ + return st_hash_start(hashseed + h); +} + +st_index_t +rb_memhash(const void *ptr, long len) +{ + sip_uint64_t h = sip_hash24(sipseed.key, ptr, len); +#ifdef HAVE_UINT64_T + return (st_index_t)h; +#else + return (st_index_t)(h.u32[0] ^ h.u32[1]); +#endif +} + +static void +Init_RandomSeed2(void) +{ + VALUE seed = default_rand.seed; + + if (RB_TYPE_P(seed, T_BIGNUM)) { + rb_obj_reveal(seed, rb_cBignum); + } +} + +void +rb_reset_random_seed(void) +{ + rb_random_t *r = &default_rand; + uninit_genrand(&r->mt); + r->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 Random::DEFAULT, the Ruby system PRNG. + * + * Random.new will create a new PRNG with a state independent of + * Random::DEFAULT, 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. + */ + +void +InitVM_Random(void) +{ + Init_RandomSeed2(); + rb_define_global_function("srand", rb_f_srand, -1); + rb_define_global_function("rand", rb_f_rand, -1); + + rb_cRandom = rb_define_class("Random", rb_cObject); + rb_define_alloc_func(rb_cRandom, random_alloc); + 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); + rb_define_method(rb_cRandom, "initialize_copy", random_copy, 1); + rb_define_private_method(rb_cRandom, "marshal_dump", random_dump, 0); + rb_define_private_method(rb_cRandom, "marshal_load", random_load, 1); + rb_define_private_method(rb_cRandom, "state", random_state, 0); + rb_define_private_method(rb_cRandom, "left", random_left, 0); + rb_define_method(rb_cRandom, "==", random_equal, 1); + + { + VALUE rand_default = TypedData_Wrap_Struct(rb_cRandom, &random_data_type, &default_rand); + rb_gc_register_mark_object(rand_default); + /* Direct access to Ruby's Pseudorandom number generator (PRNG). */ + rb_define_const(rb_cRandom, "DEFAULT", rand_default); + } + + 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, "new_seed", random_seed, 0); + 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); +} + +#undef rb_intern +void +Init_Random(void) +{ + id_rand = rb_intern("rand"); + id_bytes = rb_intern("bytes"); + + InitVM(Random); +} -- cgit v1.2.3