diff options
Diffstat (limited to 'bignum.c')
| -rw-r--r-- | bignum.c | 1695 |
1 files changed, 919 insertions, 776 deletions
@@ -23,9 +23,12 @@ # include <ieeefp.h> #endif +#if !defined(USE_GMP) #if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H) -# define USE_GMP -# include <gmp.h> +# define USE_GMP 1 +#else +# define USE_GMP 0 +#endif #endif #include "id.h" @@ -36,17 +39,46 @@ #include "internal/numeric.h" #include "internal/object.h" #include "internal/sanitizers.h" -#include "internal/util.h" #include "internal/variable.h" #include "internal/warnings.h" #include "ruby/thread.h" #include "ruby/util.h" #include "ruby_assert.h" -#define RB_BIGNUM_TYPE_P(x) RB_TYPE_P((x), T_BIGNUM) +#if USE_GMP +RBIMPL_WARNING_PUSH() +# ifdef _MSC_VER +RBIMPL_WARNING_IGNORED(4146) /* for mpn_neg() */ +# endif +# include <gmp.h> +RBIMPL_WARNING_POP() +#endif + +static const bool debug_integer_pack = ( +#ifdef DEBUG_INTEGER_PACK + DEBUG_INTEGER_PACK+0 +#else + RUBY_DEBUG +#endif + ) != 0; const char ruby_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz"; +/* Two-digit decimal lookup table. Offset 2*n holds the ASCII pair for + * n in the range 0..99. Used by both rb_fix2str in numeric.c and + * big2str_2bdigits below to emit two base-10 digits per iteration. */ +const char ruby_decimal_digit_pairs[201] = + "00010203040506070809" + "10111213141516171819" + "20212223242526272829" + "30313233343536373839" + "40414243444546474849" + "50515253545556575859" + "60616263646566676869" + "70717273747576777879" + "80818283848586878889" + "90919293949596979899"; + #ifndef SIZEOF_BDIGIT_DBL # if SIZEOF_INT*2 <= SIZEOF_LONG_LONG # define SIZEOF_BDIGIT_DBL SIZEOF_LONG_LONG @@ -62,7 +94,6 @@ STATIC_ASSERT(sizeof_bdigit_and_dbl, SIZEOF_BDIGIT*2 <= SIZEOF_BDIGIT_DBL); STATIC_ASSERT(bdigit_signedness, 0 < (BDIGIT)-1); STATIC_ASSERT(bdigit_dbl_signedness, 0 < (BDIGIT_DBL)-1); STATIC_ASSERT(bdigit_dbl_signed_signedness, 0 > (BDIGIT_DBL_SIGNED)-1); -STATIC_ASSERT(rbignum_embed_len_max, BIGNUM_EMBED_LEN_MAX <= (BIGNUM_EMBED_LEN_MASK >> BIGNUM_EMBED_LEN_SHIFT)); #if SIZEOF_BDIGIT < SIZEOF_LONG STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_LONG % SIZEOF_BDIGIT == 0); @@ -102,8 +133,8 @@ STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_BDIGIT % SIZEOF_LONG == 0); #endif #define BIGZEROP(x) (BIGNUM_LEN(x) == 0 || \ - (BDIGITS(x)[0] == 0 && \ - (BIGNUM_LEN(x) == 1 || bigzero_p(x)))) + (BDIGITS(x)[0] == 0 && \ + (BIGNUM_LEN(x) == 1 || bigzero_p(x)))) #define BIGSIZE(x) (BIGNUM_LEN(x) == 0 ? (size_t)0 : \ BDIGITS(x)[BIGNUM_LEN(x)-1] ? \ (size_t)(BIGNUM_LEN(x)*SIZEOF_BDIGIT - nlz(BDIGITS(x)[BIGNUM_LEN(x)-1])/CHAR_BIT) : \ @@ -148,7 +179,7 @@ STATIC_ASSERT(sizeof_long_and_sizeof_bdigit, SIZEOF_BDIGIT % SIZEOF_LONG == 0); #define GMP_DIV_DIGITS 20 #define GMP_BIG2STR_DIGITS 20 #define GMP_STR2BIG_DIGITS 20 -#ifdef USE_GMP +#if USE_GMP # define NAIVE_MUL_DIGITS GMP_MUL_DIGITS #else # define NAIVE_MUL_DIGITS KARATSUBA_MUL_DIGITS @@ -159,15 +190,11 @@ typedef void (mulfunc_t)(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, c static mulfunc_t bary_mul_toom3_start; static mulfunc_t bary_mul_karatsuba_start; static BDIGIT bigdivrem_single(BDIGIT *qds, const BDIGIT *xds, size_t xn, BDIGIT y); -static void bary_divmod(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn); -static VALUE bigmul0(VALUE x, VALUE y); -static void bary_mul_toom3(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, BDIGIT *wds, size_t wn); static VALUE bignew_1(VALUE klass, size_t len, int sign); static inline VALUE bigtrunc(VALUE x); static VALUE bigsq(VALUE x); -static void bigdivmod(VALUE x, VALUE y, volatile VALUE *divp, volatile VALUE *modp); static inline VALUE power_cache_get_power(int base, int power_level, size_t *numdigits_ret); #if SIZEOF_BDIGIT <= SIZEOF_INT @@ -342,7 +369,7 @@ maxpow_in_bdigit_dbl(int base, int *exp_ret) BDIGIT_DBL maxpow; int exponent; - assert(2 <= base && base <= 36); + RUBY_ASSERT(2 <= base && base <= 36); { #if SIZEOF_BDIGIT_DBL == 2 @@ -374,7 +401,7 @@ maxpow_in_bdigit_dbl(int base, int *exp_ret) static inline BDIGIT_DBL bary2bdigitdbl(const BDIGIT *ds, size_t n) { - assert(n <= 2); + RUBY_ASSERT(n <= 2); if (n == 2) return ds[0] | BIGUP(ds[1]); @@ -386,7 +413,7 @@ bary2bdigitdbl(const BDIGIT *ds, size_t n) static inline void bdigitdbl2bary(BDIGIT *ds, size_t n, BDIGIT_DBL num) { - assert(n == 2); + RUBY_ASSERT(n == 2); ds[0] = BIGLO(num); ds[1] = (BDIGIT)BIGDN(num); @@ -417,12 +444,12 @@ bary_small_lshift(BDIGIT *zds, const BDIGIT *xds, size_t n, int shift) { size_t i; BDIGIT_DBL num = 0; - assert(0 <= shift && shift < BITSPERDIG); + RUBY_ASSERT(0 <= shift && shift < BITSPERDIG); for (i=0; i<n; i++) { - num = num | (BDIGIT_DBL)*xds++ << shift; - *zds++ = BIGLO(num); - num = BIGDN(num); + num = num | (BDIGIT_DBL)*xds++ << shift; + *zds++ = BIGLO(num); + num = BIGDN(num); } return BIGLO(num); } @@ -433,14 +460,14 @@ bary_small_rshift(BDIGIT *zds, const BDIGIT *xds, size_t n, int shift, BDIGIT hi size_t i; BDIGIT_DBL num = 0; - assert(0 <= shift && shift < BITSPERDIG); + RUBY_ASSERT(0 <= shift && shift < BITSPERDIG); num = BIGUP(higher_bdigit); for (i = 0; i < n; i++) { BDIGIT x = xds[n - i - 1]; - num = (num | x) >> shift; + num = (num | x) >> shift; zds[n - i - 1] = BIGLO(num); - num = BIGUP(x); + num = BIGUP(x); } } @@ -450,7 +477,7 @@ bary_zero_p(const BDIGIT *xds, size_t xn) if (xn == 0) return 1; do { - if (xds[--xn]) return 0; + if (xds[--xn]) return 0; } while (xn); return 1; } @@ -467,7 +494,6 @@ static int bary_2comp(BDIGIT *ds, size_t n) { size_t i; - i = 0; for (i = 0; i < n; i++) { if (ds[i] != 0) { goto non_zero; @@ -979,7 +1005,7 @@ integer_unpack_num_bdigits_small(size_t numwords, size_t wordsize, size_t nails, { /* nlp_bits stands for number of leading padding bits */ size_t num_bits = (wordsize * CHAR_BIT - nails) * numwords; - size_t num_bdigits = (num_bits + BITSPERDIG - 1) / BITSPERDIG; + size_t num_bdigits = roomof(num_bits, BITSPERDIG); *nlp_bits_ret = (int)(num_bdigits * BITSPERDIG - num_bits); return num_bdigits; } @@ -989,7 +1015,7 @@ integer_unpack_num_bdigits_generic(size_t numwords, size_t wordsize, size_t nail { /* BITSPERDIG = SIZEOF_BDIGIT * CHAR_BIT */ /* num_bits = (wordsize * CHAR_BIT - nails) * numwords */ - /* num_bdigits = (num_bits + BITSPERDIG - 1) / BITSPERDIG */ + /* num_bdigits = roomof(num_bits, BITSPERDIG) */ /* num_bits = CHAR_BIT * (wordsize * numwords) - nails * numwords = CHAR_BIT * num_bytes1 - nails * numwords */ size_t num_bytes1 = wordsize * numwords; @@ -1051,14 +1077,13 @@ integer_unpack_num_bdigits(size_t numwords, size_t wordsize, size_t nails, int * if (numwords <= (SIZE_MAX - (BITSPERDIG-1)) / CHAR_BIT / wordsize) { num_bdigits = integer_unpack_num_bdigits_small(numwords, wordsize, nails, nlp_bits_ret); -#ifdef DEBUG_INTEGER_PACK - { + if (debug_integer_pack) { int nlp_bits1; size_t num_bdigits1 = integer_unpack_num_bdigits_generic(numwords, wordsize, nails, &nlp_bits1); - assert(num_bdigits == num_bdigits1); - assert(*nlp_bits_ret == nlp_bits1); + RUBY_ASSERT(num_bdigits == num_bdigits1); + RUBY_ASSERT(*nlp_bits_ret == nlp_bits1); + (void)num_bdigits1; } -#endif } else { num_bdigits = integer_unpack_num_bdigits_generic(numwords, wordsize, nails, nlp_bits_ret); @@ -1266,7 +1291,7 @@ bary_unpack_internal(BDIGIT *bdigits, size_t num_bdigits, const void *words, siz } if (dd) *dp++ = (BDIGIT)dd; - assert(dp <= de); + RUBY_ASSERT(dp <= de); while (dp < de) *dp++ = 0; #undef PUSH_BITS @@ -1325,7 +1350,7 @@ bary_unpack(BDIGIT *bdigits, size_t num_bdigits, const void *words, size_t numwo num_bdigits0 = integer_unpack_num_bdigits(numwords, wordsize, nails, &nlp_bits); - assert(num_bdigits0 <= num_bdigits); + RUBY_ASSERT(num_bdigits0 <= num_bdigits); sign = bary_unpack_internal(bdigits, num_bdigits0, words, numwords, wordsize, nails, flags, nlp_bits); @@ -1344,16 +1369,16 @@ bary_subb(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yd size_t i; size_t sn; - assert(xn <= zn); - assert(yn <= zn); + RUBY_ASSERT(xn <= zn); + RUBY_ASSERT(yn <= zn); sn = xn < yn ? xn : yn; num = borrow ? -1 : 0; for (i = 0; i < sn; i++) { - num += (BDIGIT_DBL_SIGNED)xds[i] - yds[i]; - zds[i] = BIGLO(num); - num = BIGDN(num); + num += (BDIGIT_DBL_SIGNED)xds[i] - yds[i]; + zds[i] = BIGLO(num); + num = BIGDN(num); } if (yn <= xn) { for (; i < xn; i++) { @@ -1372,7 +1397,7 @@ bary_subb(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yd } if (num == 0) goto num_is_zero; for (; i < zn; i++) { - zds[i] = BDIGMAX; + zds[i] = BDIGMAX; } return 1; @@ -1380,10 +1405,10 @@ bary_subb(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yd if (xds == zds && xn == zn) return 0; for (; i < xn; i++) { - zds[i] = xds[i]; + zds[i] = xds[i]; } for (; i < zn; i++) { - zds[i] = 0; + zds[i] = 0; } return 0; } @@ -1406,31 +1431,31 @@ bary_addc(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yd BDIGIT_DBL num; size_t i; - assert(xn <= zn); - assert(yn <= zn); + RUBY_ASSERT(xn <= zn); + RUBY_ASSERT(yn <= zn); if (xn > yn) { - const BDIGIT *tds; - tds = xds; xds = yds; yds = tds; - i = xn; xn = yn; yn = i; + const BDIGIT *tds; + tds = xds; xds = yds; yds = tds; + i = xn; xn = yn; yn = i; } num = carry ? 1 : 0; for (i = 0; i < xn; i++) { - num += (BDIGIT_DBL)xds[i] + yds[i]; - zds[i] = BIGLO(num); - num = BIGDN(num); + num += (BDIGIT_DBL)xds[i] + yds[i]; + zds[i] = BIGLO(num); + num = BIGDN(num); } for (; i < yn; i++) { if (num == 0) goto num_is_zero; - num += yds[i]; - zds[i] = BIGLO(num); - num = BIGDN(num); + num += yds[i]; + zds[i] = BIGLO(num); + num = BIGDN(num); } for (; i < zn; i++) { if (num == 0) goto num_is_zero; - zds[i] = BIGLO(num); - num = BIGDN(num); + zds[i] = BIGLO(num); + num = BIGDN(num); } return num != 0; @@ -1438,10 +1463,10 @@ bary_addc(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yd if (yds == zds && yn == zn) return 0; for (; i < yn; i++) { - zds[i] = yds[i]; + zds[i] = yds[i]; } for (; i < zn; i++) { - zds[i] = 0; + zds[i] = 0; } return 0; } @@ -1471,7 +1496,7 @@ bary_mul_single(BDIGIT *zds, size_t zn, BDIGIT x, BDIGIT y) { BDIGIT_DBL n; - assert(2 <= zn); + RUBY_ASSERT(2 <= zn); n = (BDIGIT_DBL)x * y; bdigitdbl2bary(zds, 2, n); @@ -1485,7 +1510,7 @@ bary_muladd_1xN(BDIGIT *zds, size_t zn, BDIGIT x, const BDIGIT *yds, size_t yn) BDIGIT_DBL dd; size_t j; - assert(zn > yn); + RUBY_ASSERT(zn > yn); if (x == 0) return 0; @@ -1520,7 +1545,7 @@ bigdivrem_mulsub(BDIGIT *zds, size_t zn, BDIGIT x, const BDIGIT *yds, size_t yn) BDIGIT_DBL t2; BDIGIT_DBL_SIGNED num; - assert(zn == yn + 1); + RUBY_ASSERT(zn == yn + 1); num = 0; t2 = 0; @@ -1545,7 +1570,7 @@ bary_mulsub_1xN(BDIGIT *zds, size_t zn, BDIGIT x, const BDIGIT *yds, size_t yn) { BDIGIT_DBL_SIGNED num; - assert(zn == yn + 1); + RUBY_ASSERT(zn == yn + 1); num = bigdivrem_mulsub(zds, zn, x, yds, yn); zds[yn] = BIGLO(num); @@ -1559,7 +1584,7 @@ bary_mul_normal(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIG { size_t i; - assert(xn + yn <= zn); + RUBY_ASSERT(xn + yn <= zn); BDIGITS_ZERO(zds, zn); for (i = 0; i < xn; i++) { @@ -1580,7 +1605,7 @@ rb_big_mul_normal(VALUE x, VALUE y) /* efficient squaring (2 times faster than normal multiplication) * ref: Handbook of Applied Cryptography, Algorithm 14.16 - * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf + * https://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */ static void bary_sq_fast(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn) @@ -1590,7 +1615,7 @@ bary_sq_fast(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn) BDIGIT vl; int vh; - assert(xn * 2 <= zn); + RUBY_ASSERT(xn * 2 <= zn); BDIGITS_ZERO(zds, zn); @@ -1598,30 +1623,30 @@ bary_sq_fast(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn) return; for (i = 0; i < xn-1; i++) { - v = (BDIGIT_DBL)xds[i]; - if (!v) + v = (BDIGIT_DBL)xds[i]; + if (!v) continue; - c = (BDIGIT_DBL)zds[i + i] + v * v; - zds[i + i] = BIGLO(c); - c = BIGDN(c); - v *= 2; + c = (BDIGIT_DBL)zds[i + i] + v * v; + zds[i + i] = BIGLO(c); + c = BIGDN(c); + v *= 2; vl = BIGLO(v); vh = (int)BIGDN(v); - for (j = i + 1; j < xn; j++) { - w = (BDIGIT_DBL)xds[j]; - c += (BDIGIT_DBL)zds[i + j] + vl * w; - zds[i + j] = BIGLO(c); - c = BIGDN(c); - if (vh) + for (j = i + 1; j < xn; j++) { + w = (BDIGIT_DBL)xds[j]; + c += (BDIGIT_DBL)zds[i + j] + vl * w; + zds[i + j] = BIGLO(c); + c = BIGDN(c); + if (vh) c += w; - } - if (c) { - c += (BDIGIT_DBL)zds[i + xn]; - zds[i + xn] = BIGLO(c); - c = BIGDN(c); + } + if (c) { + c += (BDIGIT_DBL)zds[i + xn]; + zds[i + xn] = BIGLO(c); + c = BIGDN(c); if (c) zds[i + xn + 1] += (BDIGIT)c; - } + } } /* i == xn-1 */ @@ -1646,28 +1671,48 @@ rb_big_sq_fast(VALUE x) return z; } +static inline size_t +max_size(size_t a, size_t b) +{ + return (a > b ? a : b); +} + /* balancing multiplication by slicing larger argument */ static void -bary_mul_balance_with_mulfunc(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, BDIGIT *wds, size_t wn, mulfunc_t *mulfunc) +bary_mul_balance_with_mulfunc(BDIGIT *const zds, const size_t zn, + const BDIGIT *const xds, const size_t xn, + const BDIGIT *const yds, const size_t yn, + BDIGIT *wds, size_t wn, mulfunc_t *const mulfunc) { VALUE work = 0; - size_t yn0 = yn; - size_t r, n; + size_t n; - assert(xn + yn <= zn); - assert(xn <= yn); - assert(!KARATSUBA_BALANCED(xn, yn) || !TOOM3_BALANCED(xn, yn)); + RUBY_ASSERT(xn + yn <= zn); + RUBY_ASSERT(xn <= yn); + RUBY_ASSERT(!KARATSUBA_BALANCED(xn, yn) || !TOOM3_BALANCED(xn, yn)); BDIGITS_ZERO(zds, xn); + if (wn < xn) { + /* The condition when a new buffer is needed: + * 1. (2(xn+r) > zn-(yn-r)) => (2xn+r > zn-yn), at the last + * iteration (or r == 0) + * 2. (2(xn+xn) > zn-(yn-r-xn)) => (3xn-r > zn-yn), at the + * previous iteration. + */ + const size_t r = yn % xn; + if (2*xn + yn + max_size(xn-r, r) > zn) { + wn = xn; + wds = ALLOCV_N(BDIGIT, work, wn); + } + } + n = 0; - while (yn > 0) { - BDIGIT *tds; - size_t tn; - r = xn > yn ? yn : xn; - tn = xn + r; + while (yn > n) { + const size_t r = (xn > (yn - n) ? (yn - n) : xn); + const size_t tn = (xn + r); if (2 * (xn + r) <= zn - n) { - tds = zds + n + xn + r; + BDIGIT *const tds = zds + n + xn + r; mulfunc(tds, tn, xds, xn, yds + n, r, wds, wn); BDIGITS_ZERO(zds + n + xn, r); bary_add(zds + n, tn, @@ -1675,21 +1720,25 @@ bary_mul_balance_with_mulfunc(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t tds, tn); } else { + BDIGIT *const tds = zds + n; if (wn < xn) { + /* xn is invariant, only once here */ +#if 0 wn = xn; wds = ALLOCV_N(BDIGIT, work, wn); +#else + rb_bug("wds is not enough: %" PRIdSIZE " for %" PRIdSIZE, wn, xn); +#endif } - tds = zds + n; MEMCPY(wds, zds + n, BDIGIT, xn); mulfunc(tds, tn, xds, xn, yds + n, r, wds+xn, wn-xn); bary_add(zds + n, tn, zds + n, tn, wds, xn); } - yn -= r; - n += r; + n += r; } - BDIGITS_ZERO(zds+xn+yn0, zn - (xn+yn0)); + BDIGITS_ZERO(zds+xn+yn, zn - (xn+yn)); if (work) ALLOCV_END(work); @@ -1722,9 +1771,9 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const B const BDIGIT *xds0, *xds1, *yds0, *yds1; BDIGIT *zds0, *zds1, *zds2, *zds3; - assert(xn + yn <= zn); - assert(xn <= yn); - assert(yn < 2 * xn); + RUBY_ASSERT(xn + yn <= zn); + RUBY_ASSERT(xn <= yn); + RUBY_ASSERT(yn < 2 * xn); sq = xds == yds && xn == yn; @@ -1739,7 +1788,7 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const B n = yn / 2; - assert(n < xn); + RUBY_ASSERT(n < xn); if (wn < n) { /* This function itself needs only n BDIGITs for work area. @@ -1860,7 +1909,7 @@ bary_mul_karatsuba(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const B for (x = 0, i = xn-1; 0 <= i; i--) { x <<= SIZEOF_BDIGIT*CHAR_BIT; x |= xds[i]; } for (y = 0, i = yn-1; 0 <= i; i--) { y <<= SIZEOF_BDIGIT*CHAR_BIT; y |= yds[i]; } for (z = 0, i = zn-1; 0 <= i; i--) { z <<= SIZEOF_BDIGIT*CHAR_BIT; z |= zds[i]; } - assert(z == x * y); + RUBY_ASSERT(z == x * y); } */ @@ -1928,11 +1977,11 @@ bary_mul_toom3(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGI int sq = xds == yds && xn == yn; - assert(xn <= yn); /* assume y >= x */ - assert(xn + yn <= zn); + RUBY_ASSERT(xn <= yn); /* assume y >= x */ + RUBY_ASSERT(xn + yn <= zn); n = (yn + 2) / 3; - assert(2*n < xn); + RUBY_ASSERT(2*n < xn); wnc = 0; @@ -2079,21 +2128,21 @@ bary_mul_toom3(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGI v3n = u3n; v3ds = u3ds; v3p = u3p; } else { - /* v1 <- y0 + y2 */ + /* v1 <- y0 + y2 */ bary_add(v1ds, v1n, y0ds, y0n, y2ds, y2n); v1p = 1; - /* y(-1) : v2 <- v1 - y1 = y0 - y1 + y2 */ + /* y(-1) : v2 <- v1 - y1 = y0 - y1 + y2 */ v2p = 1; if (bary_sub(v2ds, v2n, v1ds, v1n, y1ds, y1n)) { bary_2comp(v2ds, v2n); v2p = 0; } - /* y(1) : v1 <- v1 + y1 = y0 + y1 + y2 */ + /* y(1) : v1 <- v1 + y1 = y0 + y1 + y2 */ bary_add(v1ds, v1n, v1ds, v1n, y1ds, y1n); - /* y(-2) : v3 <- 2 * (v2 + y2) - y0 = y0 - 2 * (y1 - 2 * y2) */ + /* y(-2) : v3 <- 2 * (v2 + y2) - y0 = y0 - 2 * (y1 - 2 * y2) */ v3p = 1; if (v2p) { bary_add(v3ds, v3n, v2ds, v2n, y2ds, y2n); @@ -2119,19 +2168,19 @@ bary_mul_toom3(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGI /* z(1) : t1 <- u1 * v1 */ bary_mul_toom3_start(t1ds, t1n, u1ds, u1n, v1ds, v1n, wds, wn); t1p = u1p == v1p; - assert(t1ds[t1n-1] == 0); + RUBY_ASSERT(t1ds[t1n-1] == 0); t1n--; /* z(-1) : t2 <- u2 * v2 */ bary_mul_toom3_start(t2ds, t2n, u2ds, u2n, v2ds, v2n, wds, wn); t2p = u2p == v2p; - assert(t2ds[t2n-1] == 0); + RUBY_ASSERT(t2ds[t2n-1] == 0); t2n--; /* z(-2) : t3 <- u3 * v3 */ bary_mul_toom3_start(t3ds, t3n, u3ds, u3n, v3ds, v3n, wds, wn); t3p = u3p == v3p; - assert(t3ds[t3n-1] == 0); + RUBY_ASSERT(t3ds[t3n-1] == 0); t3n--; /* z(inf) : t4 <- x2 * y2 */ @@ -2286,7 +2335,7 @@ rb_big_mul_toom3(VALUE x, VALUE y) return z; } -#ifdef USE_GMP +#if USE_GMP static inline void bdigits_to_mpz(mpz_t mp, const BDIGIT *digits, size_t len) { @@ -2307,7 +2356,7 @@ bary_mul_gmp(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT mpz_t x, y, z; size_t count; - assert(xn + yn <= zn); + RUBY_ASSERT(xn + yn <= zn); mpz_init(x); mpz_init(y); @@ -2342,7 +2391,7 @@ rb_big_mul_gmp(VALUE x, VALUE y) static void bary_short_mul(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) { - assert(xn + yn <= zn); + RUBY_ASSERT(xn + yn <= zn); if (xn == 1 && yn == 1) { bary_mul_single(zds, zn, xds[0], yds[0]); @@ -2378,7 +2427,7 @@ bary_mul_precheck(BDIGIT **zdsp, size_t *znp, const BDIGIT **xdsp, size_t *xnp, const BDIGIT *yds = *ydsp; size_t yn = *ynp; - assert(xn + yn <= zn); + RUBY_ASSERT(xn + yn <= zn); nlsz = 0; @@ -2424,10 +2473,10 @@ bary_mul_precheck(BDIGIT **zdsp, size_t *znp, const BDIGIT **xdsp, size_t *xnp, if (xn > yn) { const BDIGIT *tds; size_t tn; - tds = xds; xds = yds; yds = tds; - tn = xn; xn = yn; yn = tn; + tds = xds; xds = yds; yds = tds; + tn = xn; xn = yn; yn = tn; } - assert(xn <= yn); + RUBY_ASSERT(xn <= yn); if (xn <= 1) { if (xn == 0) { @@ -2551,7 +2600,7 @@ bary_mul(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds } } -#ifdef USE_GMP +#if USE_GMP bary_mul_gmp(zds, zn, xds, xn, yds, yn); #else bary_mul_toom3_start(zds, zn, xds, xn, yds, yn, NULL, 0); @@ -2575,26 +2624,26 @@ bigdivrem1(void *ptr) BDIGIT q; do { - if (bds->stop) { - bds->zn = zn; - return 0; + if (bds->stop) { + bds->zn = zn; + return 0; } - if (zds[zn-1] == yds[yn-1]) q = BDIGMAX; - else q = (BDIGIT)((BIGUP(zds[zn-1]) + zds[zn-2])/yds[yn-1]); - if (q) { + if (zds[zn-1] == yds[yn-1]) q = BDIGMAX; + else q = (BDIGIT)((BIGUP(zds[zn-1]) + zds[zn-2])/yds[yn-1]); + if (q) { num = bigdivrem_mulsub(zds+zn-(yn+1), yn+1, q, yds, yn); - while (num) { /* "add back" required */ - q--; + while (num) { /* "add back" required */ + q--; num = bary_add(zds+zn-(yn+1), yn, zds+zn-(yn+1), yn, yds, yn); num--; - } - } + } + } zn--; - zds[zn] = q; + zds[zn] = q; } while (zn > yn); return 0; } @@ -2610,8 +2659,8 @@ rb_big_stop(void *ptr) static BDIGIT bigdivrem_single1(BDIGIT *qds, const BDIGIT *xds, size_t xn, BDIGIT x_higher_bdigit, BDIGIT y) { - assert(0 < xn); - assert(x_higher_bdigit < y); + RUBY_ASSERT(0 < xn); + RUBY_ASSERT(x_higher_bdigit < y); if (POW2_P(y)) { BDIGIT r; r = xds[0] & (y-1); @@ -2643,9 +2692,9 @@ bigdivrem_restoring(BDIGIT *zds, size_t zn, BDIGIT *yds, size_t yn) struct big_div_struct bds; size_t ynzero; - assert(yn < zn); - assert(BDIGIT_MSB(yds[yn-1])); - assert(zds[zn-1] < yds[yn-1]); + RUBY_ASSERT(yn < zn); + RUBY_ASSERT(BDIGIT_MSB(yds[yn-1])); + RUBY_ASSERT(zds[zn-1] < yds[yn-1]); for (ynzero = 0; !yds[ynzero]; ynzero++); @@ -2663,16 +2712,16 @@ bigdivrem_restoring(BDIGIT *zds, size_t zn, BDIGIT *yds, size_t yn) bds.zn = zn - ynzero; if (bds.zn > 10000 || bds.yn > 10000) { retry: - bds.stop = Qfalse; - rb_nogvl(bigdivrem1, &bds, rb_big_stop, &bds, RB_NOGVL_UBF_ASYNC_SAFE); + bds.stop = Qfalse; + rb_nogvl(bigdivrem1, &bds, rb_big_stop, &bds, RB_NOGVL_UBF_ASYNC_SAFE | RB_NOGVL_OFFLOAD_SAFE); - if (bds.stop == Qtrue) { - /* execute trap handler, but exception was not raised. */ - goto retry; - } + if (bds.stop == Qtrue) { + /* execute trap handler, but exception was not raised. */ + goto retry; + } } else { - bigdivrem1(&bds); + bigdivrem1(&bds); } } @@ -2684,9 +2733,9 @@ bary_divmod_normal(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT size_t zn; VALUE tmpyz = 0; - assert(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1])); - assert(qds ? (xn - yn + 1) <= qn : 1); - assert(rds ? yn <= rn : 1); + RUBY_ASSERT(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1])); + RUBY_ASSERT(qds ? (xn - yn + 1) <= qn : 1); + RUBY_ASSERT(rds ? yn <= rn : 1); zn = xn + BIGDIVREM_EXTRA_WORDS; @@ -2771,17 +2820,17 @@ rb_big_divrem_normal(VALUE x, VALUE y) return rb_assoc_new(q, r); } -#ifdef USE_GMP +#if USE_GMP static void bary_divmod_gmp(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) { mpz_t x, y, q, r; size_t count; - assert(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1])); - assert(qds ? (xn - yn + 1) <= qn : 1); - assert(rds ? yn <= rn : 1); - assert(qds || rds); + RUBY_ASSERT(yn < xn || (xn == yn && yds[yn - 1] <= xds[xn - 1])); + RUBY_ASSERT(qds ? (xn - yn + 1) <= qn : 1); + RUBY_ASSERT(rds ? yn <= rn : 1); + RUBY_ASSERT(qds || rds); mpz_init(x); mpz_init(y); @@ -2855,7 +2904,7 @@ rb_big_divrem_gmp(VALUE x, VALUE y) static void bary_divmod_branch(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) { -#ifdef USE_GMP +#if USE_GMP if (GMP_DIV_DIGITS < xn) { bary_divmod_gmp(qds, qn, rds, rn, xds, xn, yds, yn); return; @@ -2867,8 +2916,8 @@ bary_divmod_branch(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT static void bary_divmod(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) { - assert(xn <= qn); - assert(yn <= rn); + RUBY_ASSERT(xn <= qn); + RUBY_ASSERT(yn <= rn); BARY_TRUNC(yds, yn); if (yn == 0) @@ -2909,11 +2958,6 @@ bary_divmod(BDIGIT *qds, size_t qn, BDIGIT *rds, size_t rn, const BDIGIT *xds, s } } - -#ifndef BIGNUM_DEBUG -# define BIGNUM_DEBUG (0+RUBY_DEBUG) -#endif - static int bigzero_p(VALUE x) { @@ -2930,7 +2974,7 @@ int rb_cmpint(VALUE val, VALUE a, VALUE b) { if (NIL_P(val)) { - rb_cmperr(a, b); + rb_cmperr_reason(a, b, "comparator returned nil"); } if (FIXNUM_P(val)) { long l = FIX2LONG(val); @@ -2939,9 +2983,9 @@ rb_cmpint(VALUE val, VALUE a, VALUE b) return 0; } if (RB_BIGNUM_TYPE_P(val)) { - if (BIGZEROP(val)) return 0; - if (BIGNUM_SIGN(val)) return 1; - return -1; + if (BIGZEROP(val)) return 0; + if (BIGNUM_SIGN(val)) return 1; + return -1; } if (RTEST(rb_funcall(val, '>', 1, INT2FIX(0)))) return 1; if (RTEST(rb_funcall(val, '<', 1, INT2FIX(0)))) return -1; @@ -2951,42 +2995,74 @@ rb_cmpint(VALUE val, VALUE a, VALUE b) #define BIGNUM_SET_LEN(b,l) \ (BIGNUM_EMBED_P(b) ? \ (void)(RBASIC(b)->flags = \ - (RBASIC(b)->flags & ~BIGNUM_EMBED_LEN_MASK) | \ - ((l) << BIGNUM_EMBED_LEN_SHIFT)) : \ + (RBASIC(b)->flags & ~BIGNUM_EMBED_LEN_MASK) | \ + ((l) << BIGNUM_EMBED_LEN_SHIFT)) : \ (void)(RBIGNUM(b)->as.heap.len = (l))) +static size_t +big_embed_capa(VALUE big) +{ + size_t size = rb_gc_obj_slot_size(big) - offsetof(struct RBignum, as.ary); + RUBY_ASSERT(size % sizeof(BDIGIT) == 0); + size_t capa = size / sizeof(BDIGIT); + RUBY_ASSERT(capa <= BIGNUM_EMBED_LEN_MAX); + return capa; +} + +static size_t +big_embed_size(size_t capa) +{ + size_t size = offsetof(struct RBignum, as.ary) + (sizeof(BDIGIT) * capa); + if (size < sizeof(struct RBignum)) { + size = sizeof(struct RBignum); + } + return size; +} + +static bool +big_embeddable_p(size_t capa) +{ + if (capa > BIGNUM_EMBED_LEN_MAX) { + return false; + } + return rb_gc_size_allocatable_p(big_embed_size(capa)); +} + static void rb_big_realloc(VALUE big, size_t len) { BDIGIT *ds; + size_t embed_capa = big_embed_capa(big); + if (BIGNUM_EMBED_P(big)) { - if (BIGNUM_EMBED_LEN_MAX < len) { - ds = ALLOC_N(BDIGIT, len); - MEMCPY(ds, RBIGNUM(big)->as.ary, BDIGIT, BIGNUM_EMBED_LEN_MAX); - RBIGNUM(big)->as.heap.len = BIGNUM_LEN(big); - RBIGNUM(big)->as.heap.digits = ds; + if (embed_capa < len) { + ds = ALLOC_N(BDIGIT, len); + MEMCPY(ds, RBIGNUM(big)->as.ary, BDIGIT, embed_capa); + RBIGNUM(big)->as.heap.len = BIGNUM_LEN(big); + RBIGNUM(big)->as.heap.digits = ds; FL_UNSET_RAW(big, BIGNUM_EMBED_FLAG); - } + } } else { - if (len <= BIGNUM_EMBED_LEN_MAX) { - ds = RBIGNUM(big)->as.heap.digits; + if (len <= embed_capa) { + ds = RBIGNUM(big)->as.heap.digits; + size_t old_len = RBIGNUM(big)->as.heap.len; FL_SET_RAW(big, BIGNUM_EMBED_FLAG); - BIGNUM_SET_LEN(big, len); - (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)RBIGNUM(big)->as.ary, sizeof(RBIGNUM(big)->as.ary)); - if (ds) { - MEMCPY(RBIGNUM(big)->as.ary, ds, BDIGIT, len); - xfree(ds); - } - } - else { - if (BIGNUM_LEN(big) == 0) { - RBIGNUM(big)->as.heap.digits = ALLOC_N(BDIGIT, len); - } - else { - REALLOC_N(RBIGNUM(big)->as.heap.digits, BDIGIT, len); - } - } + BIGNUM_SET_LEN(big, len); + (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)RBIGNUM(big)->as.ary, embed_capa * sizeof(BDIGIT)); + if (ds) { + MEMCPY(RBIGNUM(big)->as.ary, ds, BDIGIT, len); + SIZED_FREE_N(ds, old_len); + } + } + else { + if (BIGNUM_LEN(big) == 0) { + RBIGNUM(big)->as.heap.digits = ALLOC_N(BDIGIT, len); + } + else if (BIGNUM_LEN(big) != len) { + SIZED_REALLOC_N(RBIGNUM(big)->as.heap.digits, BDIGIT, len, BIGNUM_LEN(big)); + } + } } } @@ -3000,15 +3076,21 @@ rb_big_resize(VALUE big, size_t len) static VALUE bignew_1(VALUE klass, size_t len, int sign) { - NEWOBJ_OF(big, struct RBignum, klass, T_BIGNUM | (RGENGC_WB_PROTECTED_BIGNUM ? FL_WB_PROTECTED : 0)); - VALUE bigv = (VALUE)big; - BIGNUM_SET_SIGN(bigv, sign); - if (len <= BIGNUM_EMBED_LEN_MAX) { - FL_SET_RAW(bigv, BIGNUM_EMBED_FLAG); + VALUE bigv; + + if (big_embeddable_p(len)) { + size_t size = big_embed_size(len); + RUBY_ASSERT(rb_gc_size_allocatable_p(size)); + NEWOBJ_OF(big, struct RBignum, klass, T_BIGNUM | BIGNUM_EMBED_FLAG, size); + bigv = (VALUE)big; + BIGNUM_SET_SIGN(bigv, sign); BIGNUM_SET_LEN(bigv, len); - (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)big->as.ary, sizeof(big->as.ary)); + (void)VALGRIND_MAKE_MEM_UNDEFINED((void*)big->as.ary, len * sizeof(BDIGIT)); } else { + NEWOBJ_OF(big, struct RBignum, klass, T_BIGNUM, sizeof(struct RBignum)); + bigv = (VALUE)big; + BIGNUM_SET_SIGN(bigv, sign); big->as.heap.digits = ALLOC_N(BDIGIT, len); big->as.heap.len = len; } @@ -3019,7 +3101,9 @@ bignew_1(VALUE klass, size_t len, int sign) VALUE rb_big_new(size_t len, int sign) { - return bignew(len, sign != 0); + VALUE obj = bignew(len, sign != 0); + memset(BIGNUM_DIGITS(obj), 0, len * sizeof(BDIGIT)); + return obj; } VALUE @@ -3072,7 +3156,7 @@ abs2twocomp(VALUE *xp, long *n_ret) MEMCPY(BDIGITS(z), ds, BDIGIT, n); bary_2comp(BDIGITS(z), n); hibits = BDIGMAX; - *xp = z; + *xp = z; } *n_ret = n; return hibits; @@ -3096,7 +3180,7 @@ bigtrunc(VALUE x) if (len == 0) return x; while (--len && !ds[len]); if (BIGNUM_LEN(x) > len+1) { - rb_big_resize(x, len+1); + rb_big_resize(x, len+1); } return x; } @@ -3149,7 +3233,7 @@ static VALUE bignorm(VALUE x) { if (RB_BIGNUM_TYPE_P(x)) { - x = bigfixize(x); + x = bigfixize(x); } return x; } @@ -3171,8 +3255,8 @@ rb_uint2big(uintptr_t n) digits[0] = n; #else for (i = 0; i < bdigit_roomof(SIZEOF_VALUE); i++) { - digits[i] = BIGLO(n); - n = BIGDN(n); + digits[i] = BIGLO(n); + n = BIGDN(n); } #endif @@ -3191,14 +3275,14 @@ rb_int2big(intptr_t n) if (n < 0) { u = 1 + (VALUE)(-(n + 1)); /* u = -n avoiding overflow */ - neg = 1; + neg = 1; } else { u = n; } big = rb_uint2big(u); if (neg) { - BIGNUM_SET_NEGATIVE_SIGN(big); + BIGNUM_SET_NEGATIVE_SIGN(big); } return big; } @@ -3357,7 +3441,7 @@ absint_numwords_generic(size_t numbytes, int nlz_bits_in_msbyte, size_t word_num if (sign == 2) { #if defined __GNUC__ && (__GNUC__ == 4 && __GNUC_MINOR__ == 4) - *nlz_bits_ret = 0; + *nlz_bits_ret = 0; #endif return (size_t)-1; } @@ -3399,14 +3483,13 @@ rb_absint_numwords(VALUE val, size_t word_numbits, size_t *nlz_bits_ret) if (numbytes <= SIZE_MAX / CHAR_BIT) { numwords = absint_numwords_small(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits); -#ifdef DEBUG_INTEGER_PACK - { + if (debug_integer_pack) { size_t numwords0, nlz_bits0; numwords0 = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits0); - assert(numwords0 == numwords); - assert(nlz_bits0 == nlz_bits); + RUBY_ASSERT(numwords0 == numwords); + RUBY_ASSERT(nlz_bits0 == nlz_bits); + (void)numwords0; } -#endif } else { numwords = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits); @@ -3676,7 +3759,7 @@ rb_integer_unpack(const void *words, size_t numwords, size_t wordsize, size_t na } else if (num_bdigits == numberof(fixbuf)) { val = bignew((long)num_bdigits+1, 0); - MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits); + MEMCPY(BDIGITS(val), fixbuf, BDIGIT, num_bdigits); BDIGITS(val)[num_bdigits++] = 1; } else { @@ -3688,9 +3771,9 @@ rb_integer_unpack(const void *words, size_t numwords, size_t wordsize, size_t na BDIGIT_DBL u = fixbuf[0] + BIGUP(fixbuf[1]); if (u == 0) return LONG2FIX(0); - if (0 < sign && POSFIXABLE(u)) + if (0 < sign && POSFIXABLE(u)) return LONG2FIX((long)u); - if (sign < 0 && BDIGIT_MSB(fixbuf[1]) == 0 && + if (sign < 0 && BDIGIT_MSB(fixbuf[1]) == 0 && NEGFIXABLE(-(BDIGIT_DBL_SIGNED)u)) return LONG2FIX((long)-(BDIGIT_DBL_SIGNED)u); val = bignew((long)num_bdigits, 0 <= sign); @@ -3742,41 +3825,41 @@ str2big_scan_digits(const char *s, const char *str, int base, int badcheck, size int c; if (!len) { - *num_digits_p = 0; - *len_p = 0; - return TRUE; + *num_digits_p = 0; + *len_p = 0; + return TRUE; } if (badcheck && *str == '_') return FALSE; while ((c = *str++) != 0) { - if (c == '_') { - if (nondigit) { + if (c == '_') { + if (nondigit) { if (badcheck) return FALSE; - break; - } - nondigit = (char) c; - } - else if ((c = conv_digit(c)) < 0 || c >= base) { - break; - } - else { - nondigit = 0; - num_digits++; - digits_end = str; - } - if (len > 0 && !--len) break; + break; + } + nondigit = (char) c; + } + else if ((c = conv_digit(c)) < 0 || c >= base) { + break; + } + else { + nondigit = 0; + num_digits++; + digits_end = str; + } + if (len > 0 && !--len) break; } if (badcheck && nondigit) return FALSE; if (badcheck && len) { - str--; - while (*str && ISSPACE(*str)) { - str++; - if (len > 0 && !--len) break; - } - if (len && *str) { - return FALSE; - } + str--; + while (*str && ISSPACE(*str)) { + str++; + if (len > 0 && !--len) break; + } + if (len && *str) { + return FALSE; + } } *num_digits_p = num_digits; *len_p = digits_end - digits_start; @@ -3819,7 +3902,7 @@ str2big_poweroftwo( if (numbits) { *dp++ = BIGLO(dd); } - assert((size_t)(dp - BDIGITS(z)) == num_bdigits); + RUBY_ASSERT((size_t)(dp - BDIGITS(z)) == num_bdigits); return z; } @@ -3862,7 +3945,7 @@ str2big_normal( } break; } - assert(blen <= num_bdigits); + RUBY_ASSERT(blen <= num_bdigits); } return z; @@ -3920,7 +4003,7 @@ str2big_karatsuba( current_base = 1; } } - assert(i == num_bdigits); + RUBY_ASSERT(i == num_bdigits); for (unit = 2; unit < num_bdigits; unit *= 2) { for (i = 0; i < num_bdigits; i += unit*2) { if (2*unit <= num_bdigits - i) { @@ -3951,7 +4034,7 @@ str2big_karatsuba( return z; } -#ifdef USE_GMP +#if USE_GMP static VALUE str2big_gmp( int sign, @@ -4018,8 +4101,8 @@ rb_cstr_to_inum(const char *str, int base, int badcheck) char *end; VALUE ret = rb_cstr_parse_inum(str, -1, (badcheck ? NULL : &end), base); if (NIL_P(ret)) { - if (badcheck) rb_invalid_str(str, "Integer()"); - ret = INT2FIX(0); + if (badcheck) rb_invalid_str(str, "Integer()"); + ret = INT2FIX(0); } return ret; } @@ -4043,7 +4126,7 @@ rb_cstr_to_inum(const char *str, int base, int badcheck) VALUE rb_int_parse_cstr(const char *str, ssize_t len, char **endp, size_t *ndigits, - int base, int flags) + int base, int flags) { const char *const s = str; char sign = 1; @@ -4060,82 +4143,82 @@ rb_int_parse_cstr(const char *str, ssize_t len, char **endp, size_t *ndigits, const int badcheck = !endp; #define ADV(n) do {\ - if (len > 0 && len <= (n)) goto bad; \ - str += (n); \ - len -= (n); \ + if (len > 0 && len <= (n)) goto bad; \ + str += (n); \ + len -= (n); \ } while (0) #define ASSERT_LEN() do {\ - assert(len != 0); \ - if (len0 >= 0) assert(s + len0 == str + len); \ + RUBY_ASSERT(len != 0); \ + if (len0 >= 0) RUBY_ASSERT(s + len0 == str + len); \ } while (0) if (!str) { goto bad; } if (len && (flags & RB_INT_PARSE_SIGN)) { - while (ISSPACE(*str)) ADV(1); + while (ISSPACE(*str)) ADV(1); - if (str[0] == '+') { - ADV(1); - } - else if (str[0] == '-') { - ADV(1); - sign = 0; - } - ASSERT_LEN(); + if (str[0] == '+') { + ADV(1); + } + else if (str[0] == '-') { + ADV(1); + sign = 0; + } + ASSERT_LEN(); } if (base <= 0) { - if (str[0] == '0' && len > 1) { - switch (str[1]) { - case 'x': case 'X': - base = 16; - ADV(2); - break; - case 'b': case 'B': - base = 2; - ADV(2); - break; - case 'o': case 'O': - base = 8; - ADV(2); - break; - case 'd': case 'D': - base = 10; - ADV(2); - break; - default: - base = 8; - } - } - else if (base < -1) { - base = -base; - } - else { - base = 10; - } + if (str[0] == '0' && len > 1) { + switch (str[1]) { + case 'x': case 'X': + base = 16; + ADV(2); + break; + case 'b': case 'B': + base = 2; + ADV(2); + break; + case 'o': case 'O': + base = 8; + ADV(2); + break; + case 'd': case 'D': + base = 10; + ADV(2); + break; + default: + base = 8; + } + } + else if (base < -1) { + base = -base; + } + else { + base = 10; + } } else if (len == 1 || !(flags & RB_INT_PARSE_PREFIX)) { - /* no prefix */ + /* no prefix */ } else if (base == 2) { - if (str[0] == '0' && (str[1] == 'b'||str[1] == 'B')) { - ADV(2); - } + if (str[0] == '0' && (str[1] == 'b'||str[1] == 'B')) { + ADV(2); + } } else if (base == 8) { - if (str[0] == '0' && (str[1] == 'o'||str[1] == 'O')) { - ADV(2); - } + if (str[0] == '0' && (str[1] == 'o'||str[1] == 'O')) { + ADV(2); + } } else if (base == 10) { - if (str[0] == '0' && (str[1] == 'd'||str[1] == 'D')) { - ADV(2); - } + if (str[0] == '0' && (str[1] == 'd'||str[1] == 'D')) { + ADV(2); + } } else if (base == 16) { - if (str[0] == '0' && (str[1] == 'x'||str[1] == 'X')) { - ADV(2); - } + if (str[0] == '0' && (str[1] == 'x'||str[1] == 'X')) { + ADV(2); + } } if (!valid_radix_p(base)) { invalid_radix(base); @@ -4143,80 +4226,79 @@ rb_int_parse_cstr(const char *str, ssize_t len, char **endp, size_t *ndigits, if (!len) goto bad; num_digits = str - s; if (*str == '0' && len != 1) { /* squeeze preceding 0s */ - int us = 0; - const char *end = len < 0 ? NULL : str + len; - ++num_digits; - while ((c = *++str) == '0' || - ((flags & RB_INT_PARSE_UNDERSCORE) && c == '_')) { - if (c == '_') { - if (++us >= 2) - break; - } - else { - ++num_digits; - us = 0; - } - if (str == end) break; - } - if (!c || ISSPACE(c)) --str; - if (end) len = end - str; - ASSERT_LEN(); + int us = 0; + const char *end = len < 0 ? NULL : str + len; + ++num_digits; + while ((c = *++str) == '0' || + ((flags & RB_INT_PARSE_UNDERSCORE) && c == '_')) { + if (c == '_') { + if (++us >= 2) + break; + } + else { + ++num_digits; + us = 0; + } + if (str == end) break; + } + if (!c || ISSPACE(c)) --str; + if (end) len = end - str; } c = *str; c = conv_digit(c); if (c < 0 || c >= base) { - if (!badcheck && num_digits) z = INT2FIX(0); - goto bad; + if (!badcheck && num_digits) z = INT2FIX(0); + goto bad; } if (ndigits) *ndigits = num_digits; val = ruby_scan_digits(str, len, base, &num_digits, &ov); if (!ov) { - const char *end = &str[num_digits]; - if (num_digits > 0 && *end == '_' && (flags & RB_INT_PARSE_UNDERSCORE)) - goto bigparse; - if (endp) *endp = (char *)end; - if (ndigits) *ndigits += num_digits; - if (badcheck) { - if (num_digits == 0) return Qnil; /* no number */ - while (len < 0 ? *end : end < str + len) { - if (!ISSPACE(*end)) return Qnil; /* trailing garbage */ - end++; - } - } - - if (POSFIXABLE(val)) { - if (sign) return LONG2FIX(val); - else { - long result = -(long)val; - return LONG2FIX(result); - } - } - else { - VALUE big = rb_uint2big(val); - BIGNUM_SET_SIGN(big, sign); - return bignorm(big); - } + const char *end = &str[num_digits]; + if (num_digits > 0 && *end == '_' && (flags & RB_INT_PARSE_UNDERSCORE)) + goto bigparse; + if (endp) *endp = (char *)end; + if (ndigits) *ndigits += num_digits; + if (badcheck) { + if (num_digits == 0) return Qnil; /* no number */ + while (len < 0 ? *end : end < str + len) { + if (!ISSPACE(*end)) return Qnil; /* trailing garbage */ + end++; + } + } + + if (POSFIXABLE(val)) { + if (sign) return LONG2FIX(val); + else { + long result = -(long)val; + return LONG2FIX(result); + } + } + else { + VALUE big = rb_uint2big(val); + BIGNUM_SET_SIGN(big, sign); + return bignorm(big); + } } bigparse: digits_start = str; if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &len)) - goto bad; + goto bad; if (endp) *endp = (char *)(str + len); if (ndigits) *ndigits += num_digits; digits_end = digits_start + len; if (POW2_P(base)) { z = str2big_poweroftwo(sign, digits_start, digits_end, num_digits, - bit_length(base-1)); + bit_length(base-1)); } else { int digits_per_bdigits_dbl; maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl); num_bdigits = roomof(num_digits, digits_per_bdigits_dbl)*2; -#ifdef USE_GMP +#if USE_GMP if (GMP_STR2BIG_DIGITS < num_bdigits) { z = str2big_gmp(sign, digits_start, digits_end, num_digits, num_bdigits, base); @@ -4245,7 +4327,7 @@ static VALUE rb_cstr_parse_inum(const char *str, ssize_t len, char **endp, int base) { return rb_int_parse_cstr(str, len, endp, NULL, base, - RB_INT_PARSE_DEFAULT); + RB_INT_PARSE_DEFAULT); } VALUE @@ -4294,14 +4376,14 @@ rb_str2big_poweroftwo(VALUE arg, int base, int badcheck) s = str = StringValueCStr(arg); len = RSTRING_LEN(arg); if (*str == '-') { - len--; + len--; str++; positive_p = 0; } digits_start = str; if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &len)) - invalid_integer(arg); + invalid_integer(arg); digits_end = digits_start + len; z = str2big_poweroftwo(positive_p, digits_start, digits_end, num_digits, @@ -4333,14 +4415,14 @@ rb_str2big_normal(VALUE arg, int base, int badcheck) s = str = StringValuePtr(arg); len = RSTRING_LEN(arg); if (len > 0 && *str == '-') { - len--; + len--; str++; positive_p = 0; } digits_start = str; if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &len)) - invalid_integer(arg); + invalid_integer(arg); digits_end = digits_start + len; maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl); @@ -4375,14 +4457,14 @@ rb_str2big_karatsuba(VALUE arg, int base, int badcheck) s = str = StringValuePtr(arg); len = RSTRING_LEN(arg); if (len > 0 && *str == '-') { - len--; + len--; str++; positive_p = 0; } digits_start = str; if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &len)) - invalid_integer(arg); + invalid_integer(arg); digits_end = digits_start + len; maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl); @@ -4396,7 +4478,7 @@ rb_str2big_karatsuba(VALUE arg, int base, int badcheck) return bignorm(z); } -#ifdef USE_GMP +#if USE_GMP VALUE rb_str2big_gmp(VALUE arg, int base, int badcheck) { @@ -4418,14 +4500,14 @@ rb_str2big_gmp(VALUE arg, int base, int badcheck) s = str = StringValuePtr(arg); len = RSTRING_LEN(arg); if (len > 0 && *str == '-') { - len--; + len--; str++; positive_p = 0; } digits_start = str; if (!str2big_scan_digits(s, str, base, badcheck, &num_digits, &len)) - invalid_integer(arg); + invalid_integer(arg); digits_end = digits_start + len; maxpow_in_bdigit_dbl(base, &digits_per_bdigits_dbl); @@ -4441,7 +4523,7 @@ rb_str2big_gmp(VALUE arg, int base, int badcheck) #if HAVE_LONG_LONG -static VALUE +VALUE rb_ull2big(unsigned LONG_LONG n) { long i; @@ -4452,8 +4534,8 @@ rb_ull2big(unsigned LONG_LONG n) digits[0] = n; #else for (i = 0; i < bdigit_roomof(SIZEOF_LONG_LONG); i++) { - digits[i] = BIGLO(n); - n = BIGDN(n); + digits[i] = BIGLO(n); + n = BIGDN(n); } #endif @@ -4463,7 +4545,7 @@ rb_ull2big(unsigned LONG_LONG n) return big; } -static VALUE +VALUE rb_ll2big(LONG_LONG n) { long neg = 0; @@ -4472,14 +4554,14 @@ rb_ll2big(LONG_LONG n) if (n < 0) { u = 1 + (unsigned LONG_LONG)(-(n + 1)); /* u = -n avoiding overflow */ - neg = 1; + neg = 1; } else { u = n; } big = rb_ull2big(u); if (neg) { - BIGNUM_SET_NEGATIVE_SIGN(big); + BIGNUM_SET_NEGATIVE_SIGN(big); } return big; } @@ -4501,7 +4583,7 @@ rb_ll2inum(LONG_LONG n) #endif /* HAVE_LONG_LONG */ #ifdef HAVE_INT128_T -static VALUE +VALUE rb_uint128t2big(uint128_t n) { long i; @@ -4509,7 +4591,7 @@ rb_uint128t2big(uint128_t n) BDIGIT *digits = BDIGITS(big); for (i = 0; i < bdigit_roomof(SIZEOF_INT128_T); i++) { - digits[i] = BIGLO(RSHIFT(n ,BITSPERDIG*i)); + digits[i] = BIGLO(RSHIFT(n ,BITSPERDIG*i)); } i = bdigit_roomof(SIZEOF_INT128_T); @@ -4518,7 +4600,7 @@ rb_uint128t2big(uint128_t n) return big; } -MJIT_FUNC_EXPORTED VALUE +VALUE rb_int128t2big(int128_t n) { int neg = 0; @@ -4527,14 +4609,14 @@ rb_int128t2big(int128_t n) if (n < 0) { u = 1 + (uint128_t)(-(n + 1)); /* u = -n avoiding overflow */ - neg = 1; + neg = 1; } else { u = n; } big = rb_uint128t2big(u); if (neg) { - BIGNUM_SET_NEGATIVE_SIGN(big); + BIGNUM_SET_NEGATIVE_SIGN(big); } return big; } @@ -4563,11 +4645,14 @@ big_shift3(VALUE x, int lshift_p, size_t shift_numdigits, int shift_numbits) if (lshift_p) { if (LONG_MAX < shift_numdigits) { - rb_raise(rb_eArgError, "too big number"); + too_big: + rb_raise(rb_eRangeError, "shift width too big"); } s1 = shift_numdigits; s2 = shift_numbits; + if ((size_t)s1 != shift_numdigits) goto too_big; xn = BIGNUM_LEN(x); + if (LONG_MAX/SIZEOF_BDIGIT <= xn+s1) goto too_big; z = bignew(xn+s1+1, BIGNUM_SIGN(x)); zds = BDIGITS(z); BDIGITS_ZERO(zds, s1); @@ -4609,8 +4694,8 @@ big_shift2(VALUE x, int lshift_p, VALUE y) size_t shift_numdigits; int shift_numbits; - assert(POW2_P(CHAR_BIT)); - assert(POW2_P(BITSPERDIG)); + RUBY_ASSERT(POW2_P(CHAR_BIT)); + RUBY_ASSERT(POW2_P(BITSPERDIG)); if (BIGZEROP(x)) return INT2FIX(0); @@ -4697,7 +4782,7 @@ power_cache_get_power(int base, int power_level, size_t *numdigits_ret) rb_obj_hide(power); base36_power_cache[base - 2][power_level] = power; base36_numdigits_cache[base - 2][power_level] = numdigits; - rb_gc_register_mark_object(power); + rb_vm_register_global_object(power); } if (numdigits_ret) *numdigits_ret = base36_numdigits_cache[base - 2][power_level]; @@ -4733,7 +4818,7 @@ big2str_2bdigits(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t tail int beginning = !b2s->ptr; size_t len = 0; - assert(xn <= 2); + RUBY_ASSERT(xn <= 2); num = bary2bdigitdbl(xds, xn); if (beginning) { @@ -4741,23 +4826,74 @@ big2str_2bdigits(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t tail return; p = buf; j = sizeof(buf); - do { - BDIGIT_DBL idx = num % b2s->base; - num /= b2s->base; - p[--j] = ruby_digitmap[idx]; - } while (num); + if (b2s->base == 10) { + /* Emit two decimal digits per iteration from ruby_decimal_digit_pairs. + * See the comment on the table in bignum.c near ruby_digitmap. */ + while (num >= 100) { + BDIGIT_DBL idx = (num % 100) * 2; + num /= 100; + j -= 2; + p[j] = ruby_decimal_digit_pairs[idx]; + p[j + 1] = ruby_decimal_digit_pairs[idx + 1]; + } + if (num >= 10) { + BDIGIT_DBL idx = num * 2; + j -= 2; + p[j] = ruby_decimal_digit_pairs[idx]; + p[j + 1] = ruby_decimal_digit_pairs[idx + 1]; + } + else { + /* num is 1..9 here (0 was handled above) */ + p[--j] = (char)('0' + num); + } + } + else { + do { + BDIGIT_DBL idx = num % b2s->base; + num /= b2s->base; + p[--j] = ruby_digitmap[idx]; + } while (num); + } len = sizeof(buf) - j; big2str_alloc(b2s, len + taillen); - MEMCPY(b2s->ptr, buf + j, char, len); + MEMCPY(b2s->ptr, buf + j, char, len); } else { p = b2s->ptr; j = b2s->hbase2_numdigits; - do { - BDIGIT_DBL idx = num % b2s->base; - num /= b2s->base; - p[--j] = ruby_digitmap[idx]; - } while (j); + if (b2s->base == 10) { + /* Non-beginning chunks must emit EXACTLY hbase2_numdigits, + * zero-padded on the left. Consume num in 2-digit groups, + * handle the odd trailing digit, then memset remaining + * positions with '0'. */ + while (num >= 100) { + BDIGIT_DBL idx = (num % 100) * 2; + num /= 100; + j -= 2; + p[j] = ruby_decimal_digit_pairs[idx]; + p[j + 1] = ruby_decimal_digit_pairs[idx + 1]; + } + if (num >= 10) { + BDIGIT_DBL idx = num * 2; + j -= 2; + p[j] = ruby_decimal_digit_pairs[idx]; + p[j + 1] = ruby_decimal_digit_pairs[idx + 1]; + } + else if (num > 0) { + p[--j] = (char)('0' + num); + } + if (j > 0) { + memset(p, '0', j); + j = 0; + } + } + else { + do { + BDIGIT_DBL idx = num % b2s->base; + num /= b2s->base; + p[--j] = ruby_digitmap[idx]; + } while (j); + } len = b2s->hbase2_numdigits; } b2s->ptr += len; @@ -4765,7 +4901,7 @@ big2str_2bdigits(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t tail static void big2str_karatsuba(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t wn, - int power_level, size_t taillen) + int power_level, size_t taillen) { VALUE b; size_t half_numdigits, lower_numdigits; @@ -4795,17 +4931,17 @@ big2str_karatsuba(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t wn, */ if (xn == 0 || bary_zero_p(xds, xn)) { - if (b2s->ptr) { + if (b2s->ptr) { /* When x is zero, power_cache_get_power(base, power_level) should be cached already. */ power_cache_get_power(b2s->base, power_level, &len); - memset(b2s->ptr, '0', len); + memset(b2s->ptr, '0', len); b2s->ptr += len; - } + } return; } if (power_level == 0) { - big2str_2bdigits(b2s, xds, xn, taillen); + big2str_2bdigits(b2s, xds, xn, taillen); return; } @@ -4833,7 +4969,7 @@ big2str_karatsuba(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t wn, memset(b2s->ptr, '0', len); b2s->ptr += len; } - big2str_2bdigits(b2s, xds, xn, taillen); + big2str_2bdigits(b2s, xds, xn, taillen); } else { BDIGIT *qds, *rds; @@ -4861,7 +4997,7 @@ big2str_karatsuba(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t wn, /* bigdivrem_restoring will modify y. * So use temporary buffer. */ tds = xds + qn; - assert(qn + bn <= xn + wn); + RUBY_ASSERT(qn + bn <= xn + wn); bary_small_lshift(tds, bds, bn, shift); xds[xn] = bary_small_lshift(xds, xds, xn, shift); } @@ -4879,7 +5015,7 @@ big2str_karatsuba(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t wn, } BARY_TRUNC(qds, qn); - assert(qn <= bn); + RUBY_ASSERT(qn <= bn); big2str_karatsuba(b2s, qds, qn, xn+wn - (rn+qn), lower_power_level, lower_numdigits+taillen); BARY_TRUNC(rds, rn); big2str_karatsuba(b2s, rds, rn, xn+wn - rn, lower_power_level, taillen); @@ -4937,14 +5073,14 @@ big2str_generic(VALUE x, int base) BARY_TRUNC(xds, xn); if (xn == 0) { - return rb_usascii_str_new2("0"); + return rb_usascii_str_new2("0"); } if (!valid_radix_p(base)) - invalid_radix(base); + invalid_radix(base); if (xn >= LONG_MAX/BITSPERDIG) { - rb_raise(rb_eRangeError, "bignum too big to convert into `string'"); + rb_raise(rb_eRangeError, "bignum too big to convert into 'string'"); } power_level = 0; @@ -4954,7 +5090,7 @@ big2str_generic(VALUE x, int base) power_level++; power = power_cache_get_power(base, power_level, NULL); } - assert(power_level != MAX_BASE36_POWER_TABLE_ENTRIES); + RUBY_ASSERT(power_level != MAX_BASE36_POWER_TABLE_ENTRIES); if ((size_t)BIGNUM_LEN(power) <= xn) { /* @@ -4978,7 +5114,7 @@ big2str_generic(VALUE x, int base) b2s_data.ptr = NULL; if (power_level == 0) { - big2str_2bdigits(&b2s_data, xds, xn, 0); + big2str_2bdigits(&b2s_data, xds, xn, 0); } else { VALUE tmpw = 0; @@ -4987,7 +5123,7 @@ big2str_generic(VALUE x, int base) wn = power_level * BIGDIVREM_EXTRA_WORDS + BIGNUM_LEN(power); wds = ALLOCV_N(BDIGIT, tmpw, xn + wn); MEMCPY(wds, xds, BDIGIT, xn); - big2str_karatsuba(&b2s_data, wds, xn, wn, power_level, 0); + big2str_karatsuba(&b2s_data, wds, xn, wn, power_level, 0); if (tmpw) ALLOCV_END(tmpw); } @@ -5006,7 +5142,7 @@ rb_big2str_generic(VALUE x, int base) return big2str_generic(x, base); } -#ifdef USE_GMP +#if USE_GMP static VALUE big2str_gmp(VALUE x, int base) { @@ -5053,7 +5189,7 @@ rb_big2str1(VALUE x, int base) size_t xn; if (FIXNUM_P(x)) { - return rb_fix2str(x, base); + return rb_fix2str(x, base); } bigtrunc(x); @@ -5062,14 +5198,14 @@ rb_big2str1(VALUE x, int base) BARY_TRUNC(xds, xn); if (xn == 0) { - return rb_usascii_str_new2("0"); + return rb_usascii_str_new2("0"); } if (!valid_radix_p(base)) - invalid_radix(base); + invalid_radix(base); if (xn >= LONG_MAX/BITSPERDIG) { - rb_raise(rb_eRangeError, "bignum too big to convert into `string'"); + rb_raise(rb_eRangeError, "bignum too big to convert into 'string'"); } if (POW2_P(base)) { @@ -5077,7 +5213,7 @@ rb_big2str1(VALUE x, int base) return big2str_base_poweroftwo(x, base); } -#ifdef USE_GMP +#if USE_GMP if (GMP_BIG2STR_DIGITS < xn) { return big2str_gmp(x, base); } @@ -5105,7 +5241,7 @@ big2ulong(VALUE x, const char *type) if (len == 0) return 0; if (BIGSIZE(x) > sizeof(long)) { - rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type); + rb_raise(rb_eRangeError, "bignum too big to convert into '%s'", type); } ds = BDIGITS(x); #if SIZEOF_LONG <= SIZEOF_BDIGIT @@ -5113,7 +5249,7 @@ big2ulong(VALUE x, const char *type) #else num = 0; for (i = 0; i < len; i++) { - num <<= BITSPERDIG; + num <<= BITSPERDIG; num += (unsigned long)ds[len - i - 1]; /* overflow is already checked */ } #endif @@ -5148,7 +5284,7 @@ rb_big2long(VALUE x) if (num <= 1+(unsigned long)(-(LONG_MIN+1))) return -(long)(num-1)-1; } - rb_raise(rb_eRangeError, "bignum too big to convert into `long'"); + rb_raise(rb_eRangeError, "bignum too big to convert into 'long'"); } #if HAVE_LONG_LONG @@ -5166,13 +5302,13 @@ big2ull(VALUE x, const char *type) if (len == 0) return 0; if (BIGSIZE(x) > SIZEOF_LONG_LONG) - rb_raise(rb_eRangeError, "bignum too big to convert into `%s'", type); + rb_raise(rb_eRangeError, "bignum too big to convert into '%s'", type); #if SIZEOF_LONG_LONG <= SIZEOF_BDIGIT num = (unsigned LONG_LONG)ds[0]; #else num = 0; for (i = 0; i < len; i++) { - num = BIGUP(num); + num = BIGUP(num); num += ds[len - i - 1]; } #endif @@ -5207,7 +5343,7 @@ rb_big2ll(VALUE x) if (num <= 1+(unsigned LONG_LONG)(-(LLONG_MIN+1))) return -(LONG_LONG)(num-1)-1; } - rb_raise(rb_eRangeError, "bignum too big to convert into `long long'"); + rb_raise(rb_eRangeError, "bignum too big to convert into 'long long'"); } #endif /* HAVE_LONG_LONG */ @@ -5222,23 +5358,23 @@ dbl2big(double d) double u = (d < 0)?-d:d; if (isinf(d)) { - rb_raise(rb_eFloatDomainError, d < 0 ? "-Infinity" : "Infinity"); + rb_raise(rb_eFloatDomainError, d < 0 ? "-Infinity" : "Infinity"); } if (isnan(d)) { - rb_raise(rb_eFloatDomainError, "NaN"); + rb_raise(rb_eFloatDomainError, "NaN"); } while (1.0 <= u) { - u /= (double)(BIGRAD); - i++; + u /= (double)(BIGRAD); + i++; } z = bignew(i, d>=0); digits = BDIGITS(z); while (i--) { - u *= BIGRAD; - c = (BDIGIT)u; - u -= c; - digits[i] = c; + u *= BIGRAD; + c = (BDIGIT)u; + u -= c; + digits[i] = c; } return z; @@ -5258,28 +5394,28 @@ big2dbl(VALUE x) BDIGIT *ds = BDIGITS(x), dl; if (i) { - bits = i * BITSPERDIG - nlz(ds[i-1]); - if (bits > DBL_MANT_DIG+DBL_MAX_EXP) { - d = HUGE_VAL; - } - else { - if (bits > DBL_MANT_DIG+1) - lo = (bits -= DBL_MANT_DIG+1) / BITSPERDIG; - else - bits = 0; - while (--i > lo) { - d = ds[i] + BIGRAD*d; - } - dl = ds[i]; - if (bits && (dl & ((BDIGIT)1 << (bits %= BITSPERDIG)))) { - int carry = (dl & ~(BDIGMAX << bits)) != 0; - if (!carry) { - while (i-- > 0) { - carry = ds[i] != 0; - if (carry) break; - } - } - if (carry) { + bits = i * BITSPERDIG - nlz(ds[i-1]); + if (bits > DBL_MANT_DIG+DBL_MAX_EXP) { + d = HUGE_VAL; + } + else { + if (bits > DBL_MANT_DIG+1) + lo = (bits -= DBL_MANT_DIG+1) / BITSPERDIG; + else + bits = 0; + while (--i > lo) { + d = ds[i] + BIGRAD*d; + } + dl = ds[i]; + if (bits && (dl & ((BDIGIT)1 << (bits %= BITSPERDIG)))) { + int carry = (dl & ~(BDIGMAX << bits)) != 0; + if (!carry) { + while (i-- > 0) { + carry = ds[i] != 0; + if (carry) break; + } + } + if (carry) { BDIGIT mask = BDIGMAX; BDIGIT bit = 1; mask <<= bits; @@ -5287,19 +5423,19 @@ big2dbl(VALUE x) dl &= mask; dl += bit; dl = BIGLO(dl); - if (!dl) d += 1; - } - } - d = dl + BIGRAD*d; - if (lo) { - if (lo > INT_MAX / BITSPERDIG) - d = HUGE_VAL; - else if (lo < INT_MIN / BITSPERDIG) - d = 0.0; - else - d = ldexp(d, (int)(lo * BITSPERDIG)); - } - } + if (!dl) d += 1; + } + } + d = dl + BIGRAD*d; + if (lo) { + if (lo > INT_MAX / BITSPERDIG) + d = HUGE_VAL; + else if (lo < INT_MIN / BITSPERDIG) + d = 0.0; + else + d = ldexp(d, (int)(lo * BITSPERDIG)); + } + } } if (BIGNUM_NEGATIVE_P(x)) d = -d; return d; @@ -5311,11 +5447,11 @@ rb_big2dbl(VALUE x) double d = big2dbl(x); if (isinf(d)) { - rb_warning("Bignum out of Float range"); - if (d < 0.0) - d = -HUGE_VAL; - else - d = HUGE_VAL; + rb_warning("Integer out of Float range"); + if (d < 0.0) + d = -HUGE_VAL; + else + d = HUGE_VAL; } return d; } @@ -5385,7 +5521,7 @@ rb_integer_float_eq(VALUE x, VALUE y) double yd = RFLOAT_VALUE(y); double yi, yf; - if (isnan(yd) || isinf(yd)) + if (!isfinite(yd)) return Qfalse; yf = modf(yd, &yi); if (yf != 0) @@ -5393,18 +5529,14 @@ rb_integer_float_eq(VALUE x, VALUE y) if (FIXNUM_P(x)) { #if SIZEOF_LONG * CHAR_BIT < DBL_MANT_DIG /* assume FLT_RADIX == 2 */ double xd = (double)FIX2LONG(x); - if (xd != yd) - return Qfalse; - return Qtrue; + return RBOOL(xd == yd); #else long xn, yn; if (yi < LONG_MIN || LONG_MAX_as_double <= yi) return Qfalse; xn = FIX2LONG(x); yn = (long)yi; - if (xn != yn) - return Qfalse; - return Qtrue; + return RBOOL(xn == yn); #endif } y = rb_dbl2big(yi); @@ -5416,26 +5548,26 @@ VALUE rb_big_cmp(VALUE x, VALUE y) { if (FIXNUM_P(y)) { - x = bigfixize(x); + x = bigfixize(x); if (FIXNUM_P(x)) { - /* SIGNED_VALUE and Fixnum have same sign-bits, same - * order */ - SIGNED_VALUE sx = (SIGNED_VALUE)x, sy = (SIGNED_VALUE)y; - if (sx < sy) return INT2FIX(-1); - return INT2FIX(sx > sy); + /* SIGNED_VALUE and Fixnum have same sign-bits, same + * order */ + SIGNED_VALUE sx = (SIGNED_VALUE)x, sy = (SIGNED_VALUE)y; + if (sx < sy) return INT2FIX(-1); + return INT2FIX(sx > sy); } } else if (RB_BIGNUM_TYPE_P(y)) { - if (BIGNUM_SIGN(x) == BIGNUM_SIGN(y)) { - int cmp = bary_cmp(BDIGITS(x), BIGNUM_LEN(x), BDIGITS(y), BIGNUM_LEN(y)); - return INT2FIX(BIGNUM_SIGN(x) ? cmp : -cmp); - } + if (BIGNUM_SIGN(x) == BIGNUM_SIGN(y)) { + int cmp = bary_cmp(BDIGITS(x), BIGNUM_LEN(x), BDIGITS(y), BIGNUM_LEN(y)); + return INT2FIX(BIGNUM_SIGN(x) ? cmp : -cmp); + } } else if (RB_FLOAT_TYPE_P(y)) { return rb_integer_float_cmp(x, y); } else { - return rb_num_coerce_cmp(x, y, idCmp); + return rb_num_coerce_cmp(x, y, idCmp); } return INT2FIX(BIGNUM_SIGN(x) ? 1 : -1); } @@ -5454,30 +5586,30 @@ big_op(VALUE x, VALUE y, enum big_op_t op) int n; if (RB_INTEGER_TYPE_P(y)) { - rel = rb_big_cmp(x, y); + rel = rb_big_cmp(x, y); } else if (RB_FLOAT_TYPE_P(y)) { rel = rb_integer_float_cmp(x, y); } else { - ID id = 0; - switch (op) { - case big_op_gt: id = '>'; break; - case big_op_ge: id = idGE; break; - case big_op_lt: id = '<'; break; - case big_op_le: id = idLE; break; - } - return rb_num_coerce_relop(x, y, id); + ID id = 0; + switch (op) { + case big_op_gt: id = '>'; break; + case big_op_ge: id = idGE; break; + case big_op_lt: id = '<'; break; + case big_op_le: id = idLE; break; + } + return rb_num_coerce_relop(x, y, id); } if (NIL_P(rel)) return Qfalse; n = FIX2INT(rel); switch (op) { - case big_op_gt: return n > 0 ? Qtrue : Qfalse; - case big_op_ge: return n >= 0 ? Qtrue : Qfalse; - case big_op_lt: return n < 0 ? Qtrue : Qfalse; - case big_op_le: return n <= 0 ? Qtrue : Qfalse; + case big_op_gt: return RBOOL(n > 0); + case big_op_ge: return RBOOL(n >= 0); + case big_op_lt: return RBOOL(n < 0); + case big_op_le: return RBOOL(n <= 0); } return Qundef; } @@ -5521,7 +5653,7 @@ VALUE rb_big_eq(VALUE x, VALUE y) { if (FIXNUM_P(y)) { - return bignorm(x) == y ? Qtrue : Qfalse; + return RBOOL(bignorm(x) == y); } else if (RB_BIGNUM_TYPE_P(y)) { } @@ -5529,12 +5661,11 @@ rb_big_eq(VALUE x, VALUE y) return rb_integer_float_eq(x, y); } else { - return rb_equal(y, x); + return rb_equal(y, x); } if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y)) return Qfalse; if (BIGNUM_LEN(x) != BIGNUM_LEN(y)) return Qfalse; - if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) != 0) return Qfalse; - return Qtrue; + return RBOOL(MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0); } VALUE @@ -5543,8 +5674,7 @@ rb_big_eql(VALUE x, VALUE y) if (!RB_BIGNUM_TYPE_P(y)) return Qfalse; if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y)) return Qfalse; if (BIGNUM_LEN(x) != BIGNUM_LEN(y)) return Qfalse; - if (MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) != 0) return Qfalse; - return Qtrue; + return RBOOL(MEMCMP(BDIGITS(x),BDIGITS(y),BDIGIT,BIGNUM_LEN(y)) == 0); } VALUE @@ -5635,13 +5765,13 @@ bigsub_int(VALUE x, long y0) zds = BDIGITS(z); #if SIZEOF_BDIGIT >= SIZEOF_LONG - assert(xn == zn); + RUBY_ASSERT(xn == zn); num = (BDIGIT_DBL_SIGNED)xds[0] - y; if (xn == 1 && num < 0) { - BIGNUM_NEGATE(z); - zds[0] = (BDIGIT)-num; - RB_GC_GUARD(x); - return bignorm(z); + BIGNUM_NEGATE(z); + zds[0] = (BDIGIT)-num; + RB_GC_GUARD(x); + return bignorm(z); } zds[0] = BIGLO(num); num = BIGDN(num); @@ -5653,10 +5783,10 @@ bigsub_int(VALUE x, long y0) num = 0; for (i=0; i < xn; i++) { if (y == 0) goto y_is_zero_x; - num += (BDIGIT_DBL_SIGNED)xds[i] - BIGLO(y); - zds[i] = BIGLO(num); - num = BIGDN(num); - y = BIGDN(y); + num += (BDIGIT_DBL_SIGNED)xds[i] - BIGLO(y); + zds[i] = BIGLO(num); + num = BIGDN(num); + y = BIGDN(y); } for (; i < zn; i++) { if (y == 0) goto y_is_zero_z; @@ -5671,9 +5801,9 @@ bigsub_int(VALUE x, long y0) for (; i < xn; i++) { y_is_zero_x: if (num == 0) goto num_is_zero_x; - num += xds[i]; - zds[i] = BIGLO(num); - num = BIGDN(num); + num += xds[i]; + zds[i] = BIGLO(num); + num = BIGDN(num); } #if SIZEOF_BDIGIT < SIZEOF_LONG for (; i < zn; i++) { @@ -5687,7 +5817,7 @@ bigsub_int(VALUE x, long y0) for (; i < xn; i++) { num_is_zero_x: - zds[i] = xds[i]; + zds[i] = xds[i]; } #if SIZEOF_BDIGIT < SIZEOF_LONG for (; i < zn; i++) { @@ -5698,10 +5828,10 @@ bigsub_int(VALUE x, long y0) goto finish; finish: - assert(num == 0 || num == -1); + RUBY_ASSERT(num == 0 || num == -1); if (num < 0) { get2comp(z); - BIGNUM_NEGATE(z); + BIGNUM_NEGATE(z); } RB_GC_GUARD(x); return bignorm(z); @@ -5744,17 +5874,17 @@ bigadd_int(VALUE x, long y) num = 0; for (i=0; i < xn; i++) { if (y == 0) goto y_is_zero_x; - num += (BDIGIT_DBL)xds[i] + BIGLO(y); - zds[i] = BIGLO(num); - num = BIGDN(num); - y = BIGDN(y); + num += (BDIGIT_DBL)xds[i] + BIGLO(y); + zds[i] = BIGLO(num); + num = BIGDN(num); + y = BIGDN(y); } for (; i < zn; i++) { if (y == 0) goto y_is_zero_z; - num += BIGLO(y); - zds[i] = BIGLO(num); - num = BIGDN(num); - y = BIGDN(y); + num += BIGLO(y); + zds[i] = BIGLO(num); + num = BIGDN(num); + y = BIGDN(y); } goto finish; @@ -5763,25 +5893,25 @@ bigadd_int(VALUE x, long y) for (;i < xn; i++) { y_is_zero_x: if (num == 0) goto num_is_zero_x; - num += (BDIGIT_DBL)xds[i]; - zds[i] = BIGLO(num); - num = BIGDN(num); + num += (BDIGIT_DBL)xds[i]; + zds[i] = BIGLO(num); + num = BIGDN(num); } for (; i < zn; i++) { y_is_zero_z: if (num == 0) goto num_is_zero_z; - zds[i] = BIGLO(num); - num = BIGDN(num); + zds[i] = BIGLO(num); + num = BIGDN(num); } goto finish; for (;i < xn; i++) { num_is_zero_x: - zds[i] = xds[i]; + zds[i] = xds[i]; } for (; i < zn; i++) { num_is_zero_z: - zds[i] = 0; + zds[i] = 0; } goto finish; @@ -5798,15 +5928,15 @@ bigadd(VALUE x, VALUE y, int sign) sign = (sign == BIGNUM_SIGN(y)); if (BIGNUM_SIGN(x) != sign) { - if (sign) return bigsub(y, x); - return bigsub(x, y); + if (sign) return bigsub(y, x); + return bigsub(x, y); } if (BIGNUM_LEN(x) > BIGNUM_LEN(y)) { - len = BIGNUM_LEN(x) + 1; + len = BIGNUM_LEN(x) + 1; } else { - len = BIGNUM_LEN(y) + 1; + len = BIGNUM_LEN(y) + 1; } z = bignew(len, sign); @@ -5823,26 +5953,26 @@ rb_big_plus(VALUE x, VALUE y) long n; if (FIXNUM_P(y)) { - n = FIX2LONG(y); - if ((n > 0) != BIGNUM_SIGN(x)) { - if (n < 0) { - n = -n; - } - return bigsub_int(x, n); - } - if (n < 0) { - n = -n; - } - return bigadd_int(x, n); + n = FIX2LONG(y); + if ((n > 0) != BIGNUM_SIGN(x)) { + if (n < 0) { + n = -n; + } + return bigsub_int(x, n); + } + if (n < 0) { + n = -n; + } + return bigadd_int(x, n); } else if (RB_BIGNUM_TYPE_P(y)) { - return bignorm(bigadd(x, y, 1)); + return bignorm(bigadd(x, y, 1)); } else if (RB_FLOAT_TYPE_P(y)) { - return DBL2NUM(rb_big2dbl(x) + RFLOAT_VALUE(y)); + return DBL2NUM(rb_big2dbl(x) + RFLOAT_VALUE(y)); } else { - return rb_num_coerce_bin(x, y, '+'); + return rb_num_coerce_bin(x, y, '+'); } } @@ -5852,26 +5982,26 @@ rb_big_minus(VALUE x, VALUE y) long n; if (FIXNUM_P(y)) { - n = FIX2LONG(y); - if ((n > 0) != BIGNUM_SIGN(x)) { - if (n < 0) { - n = -n; - } - return bigadd_int(x, n); - } - if (n < 0) { - n = -n; - } - return bigsub_int(x, n); + n = FIX2LONG(y); + if ((n > 0) != BIGNUM_SIGN(x)) { + if (n < 0) { + n = -n; + } + return bigadd_int(x, n); + } + if (n < 0) { + n = -n; + } + return bigsub_int(x, n); } else if (RB_BIGNUM_TYPE_P(y)) { - return bignorm(bigadd(x, y, 0)); + return bignorm(bigadd(x, y, 0)); } else if (RB_FLOAT_TYPE_P(y)) { - return DBL2NUM(rb_big2dbl(x) - RFLOAT_VALUE(y)); + return DBL2NUM(rb_big2dbl(x) - RFLOAT_VALUE(y)); } else { - return rb_num_coerce_bin(x, y, '-'); + return rb_num_coerce_bin(x, y, '-'); } } @@ -5883,6 +6013,8 @@ bigsq(VALUE x) BDIGIT *xds, *zds; xn = BIGNUM_LEN(x); + if (MUL_OVERFLOW_LONG_P(2, xn)) + rb_raise(rb_eArgError, "square overflow"); zn = 2 * xn; z = bignew(zn, 1); @@ -5911,6 +6043,8 @@ bigmul0(VALUE x, VALUE y) xn = BIGNUM_LEN(x); yn = BIGNUM_LEN(y); + if (ADD_OVERFLOW_LONG_P(xn, yn)) + rb_raise(rb_eArgError, "multiplication overflow"); zn = xn + yn; z = bignew(zn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y)); @@ -5930,15 +6064,15 @@ VALUE rb_big_mul(VALUE x, VALUE y) { if (FIXNUM_P(y)) { - y = rb_int2big(FIX2LONG(y)); + y = rb_int2big(FIX2LONG(y)); } else if (RB_BIGNUM_TYPE_P(y)) { } else if (RB_FLOAT_TYPE_P(y)) { - return DBL2NUM(rb_big2dbl(x) * RFLOAT_VALUE(y)); + return DBL2NUM(rb_big2dbl(x) * RFLOAT_VALUE(y)); } else { - return rb_num_coerce_bin(x, y, '*'); + return rb_num_coerce_bin(x, y, '*'); } return bignorm(bigmul0(x, y)); @@ -5965,21 +6099,21 @@ bigdivrem(VALUE x, VALUE y, volatile VALUE *divp, volatile VALUE *modp) BARY_TRUNC(xds, xn); if (xn < yn || (xn == yn && xds[xn - 1] < yds[yn - 1])) { - if (divp) *divp = rb_int2big(0); - if (modp) *modp = x; - return Qnil; + if (divp) *divp = rb_int2big(0); + if (modp) *modp = x; + return Qnil; } if (yn == 1) { - dd = yds[0]; - z = bignew(xn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y)); - zds = BDIGITS(z); + dd = yds[0]; + z = bignew(xn, BIGNUM_SIGN(x)==BIGNUM_SIGN(y)); + zds = BDIGITS(z); dd = bigdivrem_single(zds, xds, xn, dd); - if (modp) { - *modp = rb_uint2big((uintptr_t)dd); - BIGNUM_SET_SIGN(*modp, BIGNUM_SIGN(x)); - } - if (divp) *divp = z; - return Qnil; + if (modp) { + *modp = rb_uint2big((uintptr_t)dd); + BIGNUM_SET_SIGN(*modp, BIGNUM_SIGN(x)); + } + if (divp) *divp = z; + return Qnil; } if (xn == 2 && yn == 2) { BDIGIT_DBL x0 = bary2bdigitdbl(xds, 2); @@ -6044,11 +6178,11 @@ bigdivmod(VALUE x, VALUE y, volatile VALUE *divp, volatile VALUE *modp) bigdivrem(x, y, divp, &mod); if (BIGNUM_SIGN(x) != BIGNUM_SIGN(y) && !BIGZEROP(mod)) { - if (divp) *divp = bigadd(*divp, rb_int2big(1), 0); - if (modp) *modp = bigadd(mod, y, 1); + if (divp) *divp = bigadd(*divp, rb_int2big(1), 0); + if (modp) *modp = bigadd(mod, y, 1); } else if (modp) { - *modp = mod; + *modp = mod; } } @@ -6059,25 +6193,25 @@ rb_big_divide(VALUE x, VALUE y, ID op) VALUE z; if (FIXNUM_P(y)) { - y = rb_int2big(FIX2LONG(y)); + y = rb_int2big(FIX2LONG(y)); } else if (RB_BIGNUM_TYPE_P(y)) { } else if (RB_FLOAT_TYPE_P(y)) { - if (op == '/') { + if (op == '/') { double dx = rb_big2dbl(x); return rb_flo_div_flo(DBL2NUM(dx), y); - } - else { + } + else { VALUE v; - double dy = RFLOAT_VALUE(y); - if (dy == 0.0) rb_num_zerodiv(); + double dy = RFLOAT_VALUE(y); + if (dy == 0.0) rb_num_zerodiv(); v = rb_big_divide(x, y, '/'); return rb_dbl2big(RFLOAT_VALUE(v)); - } + } } else { - return rb_num_coerce_bin(x, y, op); + return rb_num_coerce_bin(x, y, op); } bigdivmod(x, y, &z, 0); @@ -6102,10 +6236,10 @@ rb_big_modulo(VALUE x, VALUE y) VALUE z; if (FIXNUM_P(y)) { - y = rb_int2big(FIX2LONG(y)); + y = rb_int2big(FIX2LONG(y)); } else if (!RB_BIGNUM_TYPE_P(y)) { - return rb_num_coerce_bin(x, y, '%'); + return rb_num_coerce_bin(x, y, '%'); } bigdivmod(x, y, 0, &z); @@ -6118,10 +6252,10 @@ rb_big_remainder(VALUE x, VALUE y) VALUE z; if (FIXNUM_P(y)) { - y = rb_int2big(FIX2LONG(y)); + y = rb_int2big(FIX2LONG(y)); } else if (!RB_BIGNUM_TYPE_P(y)) { - return rb_num_coerce_bin(x, y, rb_intern("remainder")); + return rb_num_coerce_bin(x, y, rb_intern("remainder")); } bigdivrem(x, y, 0, &z); @@ -6134,7 +6268,7 @@ rb_big_divmod(VALUE x, VALUE y) VALUE div, mod; if (FIXNUM_P(y)) { - y = rb_int2big(FIX2LONG(y)); + y = rb_int2big(FIX2LONG(y)); } else if (!RB_BIGNUM_TYPE_P(y)) { return rb_num_coerce_bin(x, y, idDivmod); @@ -6148,9 +6282,9 @@ static VALUE big_shift(VALUE x, long n) { if (n < 0) - return big_lshift(x, 1+(unsigned long)(-(n+1))); + return big_lshift(x, 1+(unsigned long)(-(n+1))); else if (n > 0) - return big_rshift(x, (unsigned long)n); + return big_rshift(x, (unsigned long)n); return x; } @@ -6174,9 +6308,9 @@ big_fdiv(VALUE x, VALUE y, long ey) l = ex - ey; #if SIZEOF_LONG > SIZEOF_INT { - /* Visual C++ can't be here */ - if (l > INT_MAX) return HUGE_VAL; - if (l < INT_MIN) return 0.0; + /* Visual C++ can't be here */ + if (l > INT_MAX) return HUGE_VAL; + if (l < INT_MIN) return 0.0; } #endif return ldexp(big2dbl(z), (int)l); @@ -6210,19 +6344,19 @@ rb_big_fdiv_double(VALUE x, VALUE y) dx = big2dbl(x); if (FIXNUM_P(y)) { - dy = (double)FIX2LONG(y); - if (isinf(dx)) - return big_fdiv_int(x, rb_int2big(FIX2LONG(y))); + dy = (double)FIX2LONG(y); + if (isinf(dx)) + return big_fdiv_int(x, rb_int2big(FIX2LONG(y))); } else if (RB_BIGNUM_TYPE_P(y)) { - return big_fdiv_int(x, y); + return big_fdiv_int(x, y); } else if (RB_FLOAT_TYPE_P(y)) { - dy = RFLOAT_VALUE(y); - if (isnan(dy)) - return dy; - if (isinf(dx)) - return big_fdiv_float(x, y); + dy = RFLOAT_VALUE(y); + if (isnan(dy)) + return dy; + if (isinf(dx)) + return big_fdiv_float(x, y); } else { return NUM2DBL(rb_num_coerce_bin(x, y, idFdiv)); @@ -6247,20 +6381,19 @@ rb_big_pow(VALUE x, VALUE y) if (y == INT2FIX(0)) return INT2FIX(1); if (y == INT2FIX(1)) return x; if (RB_FLOAT_TYPE_P(y)) { - d = RFLOAT_VALUE(y); - if ((BIGNUM_NEGATIVE_P(x) && !BIGZEROP(x))) { + d = RFLOAT_VALUE(y); + if ((BIGNUM_NEGATIVE_P(x) && !BIGZEROP(x))) { return rb_dbl_complex_new_polar_pi(pow(-rb_big2dbl(x), d), d); - } + } } else if (RB_BIGNUM_TYPE_P(y)) { - y = bignorm(y); - if (FIXNUM_P(y)) - goto again; - rb_warn("in a**b, b may be too big"); - d = rb_big2dbl(y); + y = bignorm(y); + if (FIXNUM_P(y)) + goto again; + rb_raise(rb_eArgError, "exponent is too large"); } else if (FIXNUM_P(y)) { - yy = FIX2LONG(y); + yy = FIX2LONG(y); if (yy < 0) { x = rb_big_pow(x, LONG2NUM(-yy)); @@ -6269,31 +6402,35 @@ rb_big_pow(VALUE x, VALUE y) else return DBL2NUM(1.0 / NUM2DBL(x)); } - else { - VALUE z = 0; - SIGNED_VALUE mask; + else { + VALUE z = 0; + SIGNED_VALUE mask; const size_t xbits = rb_absint_numwords(x, 1, NULL); - const size_t BIGLEN_LIMIT = 32*1024*1024; +#if SIZEOF_SIZE_T == 4 + const size_t BIGLEN_LIMIT = 1ULL << 31; // 2 GB +#else // SIZEOF_SIZE_T == 8 + const size_t BIGLEN_LIMIT = 1ULL << 34; // 16 GB +#endif - if (xbits == (size_t)-1 || + if (xbits == (size_t)-1 || (xbits > BIGLEN_LIMIT) || + MUL_OVERFLOW_LONG_P(yy, xbits) || (xbits * yy > BIGLEN_LIMIT)) { - rb_warn("in a**b, b may be too big"); - d = (double)yy; - } - else { - for (mask = FIXNUM_MAX + 1; mask; mask >>= 1) { - if (z) z = bigsq(z); - if (yy & mask) { - z = z ? bigtrunc(bigmul0(z, x)) : x; - } - } - return bignorm(z); - } - } + rb_raise(rb_eArgError, "exponent is too large"); + } + else { + for (mask = FIXNUM_MAX + 1; mask; mask >>= 1) { + if (z) z = bigsq(z); + if (yy & mask) { + z = z ? bigtrunc(bigmul0(z, x)) : x; + } + } + return bignorm(z); + } + } } else { - return rb_num_coerce_bin(x, y, idPow); + return rb_num_coerce_bin(x, y, idPow); } return DBL2NUM(pow(rb_big2dbl(x), d)); } @@ -6308,13 +6445,13 @@ bigand_int(VALUE x, long xn, BDIGIT hibitsx, long y) BDIGIT hibitsy; if (y == 0) return INT2FIX(0); - if (xn == 0) return hibitsx ? LONG2NUM(y) : 0; + if (xn == 0) return hibitsx ? LONG2NUM(y) : INT2FIX(0); hibitsy = 0 <= y ? 0 : BDIGMAX; xds = BDIGITS(x); #if SIZEOF_BDIGIT >= SIZEOF_LONG if (!hibitsy) { - y &= xds[0]; - return LONG2NUM(y); + y &= xds[0]; + return LONG2NUM(y); } #endif @@ -6343,10 +6480,10 @@ bigand_int(VALUE x, long xn, BDIGIT hibitsx, long y) } #endif for (;i < xn; i++) { - zds[i] = xds[i] & hibitsy; + zds[i] = xds[i] & hibitsy; } for (;i < zn; i++) { - zds[i] = hibitsx & hibitsy; + zds[i] = hibitsx & hibitsy; } twocomp2abs_bang(z, hibitsx && hibitsy); RB_GC_GUARD(x); @@ -6366,12 +6503,12 @@ rb_big_and(VALUE x, VALUE y) long tmpn; if (!RB_INTEGER_TYPE_P(y)) { - return rb_num_coerce_bit(x, y, '&'); + return rb_num_coerce_bit(x, y, '&'); } hibitsx = abs2twocomp(&x, &xn); if (FIXNUM_P(y)) { - return bigand_int(x, xn, hibitsx, FIX2LONG(y)); + return bigand_int(x, xn, hibitsx, FIX2LONG(y)); } hibitsy = abs2twocomp(&y, &yn); if (xn > yn) { @@ -6393,10 +6530,10 @@ rb_big_and(VALUE x, VALUE y) zds = BDIGITS(z); for (i=0; i<n1; i++) { - zds[i] = ds1[i] & ds2[i]; + zds[i] = ds1[i] & ds2[i]; } for (; i<n2; i++) { - zds[i] = hibits1 & ds2[i]; + zds[i] = hibits1 & ds2[i]; } twocomp2abs_bang(z, hibits1 && hibits2); RB_GC_GUARD(x); @@ -6485,12 +6622,12 @@ rb_big_or(VALUE x, VALUE y) long tmpn; if (!RB_INTEGER_TYPE_P(y)) { - return rb_num_coerce_bit(x, y, '|'); + return rb_num_coerce_bit(x, y, '|'); } hibitsx = abs2twocomp(&x, &xn); if (FIXNUM_P(y)) { - return bigor_int(x, xn, hibitsx, FIX2LONG(y)); + return bigor_int(x, xn, hibitsx, FIX2LONG(y)); } hibitsy = abs2twocomp(&y, &yn); if (xn > yn) { @@ -6512,10 +6649,10 @@ rb_big_or(VALUE x, VALUE y) zds = BDIGITS(z); for (i=0; i<n1; i++) { - zds[i] = ds1[i] | ds2[i]; + zds[i] = ds1[i] | ds2[i]; } for (; i<n2; i++) { - zds[i] = hibits1 | ds2[i]; + zds[i] = hibits1 | ds2[i]; } twocomp2abs_bang(z, hibits1 || hibits2); RB_GC_GUARD(x); @@ -6579,12 +6716,12 @@ rb_big_xor(VALUE x, VALUE y) long tmpn; if (!RB_INTEGER_TYPE_P(y)) { - return rb_num_coerce_bit(x, y, '^'); + return rb_num_coerce_bit(x, y, '^'); } hibitsx = abs2twocomp(&x, &xn); if (FIXNUM_P(y)) { - return bigxor_int(x, xn, hibitsx, FIX2LONG(y)); + return bigxor_int(x, xn, hibitsx, FIX2LONG(y)); } hibitsy = abs2twocomp(&y, &yn); if (xn > yn) { @@ -6603,10 +6740,10 @@ rb_big_xor(VALUE x, VALUE y) zds = BDIGITS(z); for (i=0; i<n1; i++) { - zds[i] = ds1[i] ^ ds2[i]; + zds[i] = ds1[i] ^ ds2[i]; } for (; i<n2; i++) { - zds[i] = hibitsx ^ ds2[i]; + zds[i] = hibitsx ^ ds2[i]; } twocomp2abs_bang(z, (hibits1 ^ hibits2) != 0); RB_GC_GUARD(x); @@ -6622,25 +6759,25 @@ rb_big_lshift(VALUE x, VALUE y) int shift_numbits; for (;;) { - if (FIXNUM_P(y)) { - long l = FIX2LONG(y); + if (FIXNUM_P(y)) { + long l = FIX2LONG(y); unsigned long shift; - if (0 <= l) { - lshift_p = 1; + if (0 <= l) { + lshift_p = 1; shift = l; } else { - lshift_p = 0; - shift = 1+(unsigned long)(-(l+1)); - } + lshift_p = 0; + shift = 1+(unsigned long)(-(l+1)); + } shift_numbits = (int)(shift & (BITSPERDIG-1)); shift_numdigits = shift >> bit_length(BITSPERDIG-1); return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits)); - } - else if (RB_BIGNUM_TYPE_P(y)) { + } + else if (RB_BIGNUM_TYPE_P(y)) { return bignorm(big_shift2(x, 1, y)); - } - y = rb_to_int(y); + } + y = rb_to_int(y); } } @@ -6652,8 +6789,8 @@ rb_big_rshift(VALUE x, VALUE y) int shift_numbits; for (;;) { - if (FIXNUM_P(y)) { - long l = FIX2LONG(y); + if (FIXNUM_P(y)) { + long l = FIX2LONG(y); unsigned long shift; if (0 <= l) { lshift_p = 0; @@ -6661,16 +6798,16 @@ rb_big_rshift(VALUE x, VALUE y) } else { lshift_p = 1; - shift = 1+(unsigned long)(-(l+1)); - } + shift = 1+(unsigned long)(-(l+1)); + } shift_numbits = (int)(shift & (BITSPERDIG-1)); shift_numdigits = shift >> bit_length(BITSPERDIG-1); return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits)); - } - else if (RB_BIGNUM_TYPE_P(y)) { + } + else if (RB_BIGNUM_TYPE_P(y)) { return bignorm(big_shift2(x, 0, y)); - } - y = rb_to_int(y); + } + y = rb_to_int(y); } } @@ -6684,22 +6821,22 @@ rb_big_aref(VALUE x, VALUE y) BDIGIT bit; if (RB_BIGNUM_TYPE_P(y)) { - if (BIGNUM_NEGATIVE_P(y)) - return INT2FIX(0); - bigtrunc(y); - if (BIGSIZE(y) > sizeof(size_t)) { - return BIGNUM_SIGN(x) ? INT2FIX(0) : INT2FIX(1); - } + if (BIGNUM_NEGATIVE_P(y)) + return INT2FIX(0); + bigtrunc(y); + if (BIGSIZE(y) > sizeof(size_t)) { + return BIGNUM_SIGN(x) ? INT2FIX(0) : INT2FIX(1); + } #if SIZEOF_SIZE_T <= SIZEOF_LONG - shift = big2ulong(y, "long"); + shift = big2ulong(y, "long"); #else - shift = big2ull(y, "long long"); + shift = big2ull(y, "long long"); #endif } else { - l = NUM2LONG(y); - if (l < 0) return INT2FIX(0); - shift = (size_t)l; + l = NUM2LONG(y); + if (l < 0) return INT2FIX(0); + shift = (size_t)l; } s1 = shift/BITSPERDIG; s2 = shift%BITSPERDIG; @@ -6720,6 +6857,73 @@ rb_big_aref(VALUE x, VALUE y) } VALUE +rb_big_aref2(VALUE x, VALUE beg, VALUE len) +{ + BDIGIT *xds, *vds; + VALUE v; + size_t copy_begin, xn, shift; + ssize_t begin, length, end; + bool negative_add_one; + + beg = rb_to_int(beg); + len = rb_to_int(len); + length = NUM2SSIZET(len); + begin = NUM2SSIZET(beg); + end = NUM2SSIZET(rb_int_plus(beg, len)); + shift = begin < 0 ? -begin : 0; + xn = BIGNUM_LEN(x); + xds = BDIGITS(x); + + if (length < 0) return rb_big_rshift(x, beg); + if (length == 0 || end <= 0) return INT2FIX(0); + if (begin < 0) begin = 0; + + if ((size_t)(end - 1) / BITSPERDIG >= xn) { + /* end > xn * BITSPERDIG */ + end = xn * BITSPERDIG; + } + + if ((size_t)begin / BITSPERDIG < xn) { + /* begin < xn * BITSPERDIG */ + size_t shift_bits, copy_end; + copy_begin = begin / BITSPERDIG; + shift_bits = begin % BITSPERDIG; + copy_end = (end - 1) / BITSPERDIG + 1; + v = bignew(copy_end - copy_begin, 1); + vds = BDIGITS(v); + MEMCPY(vds, xds + copy_begin, BDIGIT, copy_end - copy_begin); + negative_add_one = (vds[0] & ((1 << shift_bits) - 1)) == 0; + v = bignorm(v); + if (shift_bits) v = rb_int_rshift(v, SIZET2NUM(shift_bits)); + } + else { + /* Out of range */ + v = INT2FIX(0); + negative_add_one = false; + copy_begin = begin = end = 0; + } + + if (BIGNUM_NEGATIVE_P(x)) { + size_t mask_size = length - shift; + VALUE mask = rb_int_minus(rb_int_lshift(INT2FIX(1), SIZET2NUM(mask_size)), INT2FIX(1)); + v = rb_int_xor(v, mask); + for (size_t i = 0; negative_add_one && i < copy_begin; i++) { + if (xds[i]) negative_add_one = false; + } + if (negative_add_one) v = rb_int_plus(v, INT2FIX(1)); + v = rb_int_and(v, mask); + } + else { + size_t mask_size = (size_t)end - begin; + VALUE mask = rb_int_minus(rb_int_lshift(INT2FIX(1), SIZET2NUM(mask_size)), INT2FIX(1)); + v = rb_int_and(v, mask); + } + RB_GC_GUARD(x); + if (shift) v = rb_int_lshift(v, SSIZET2NUM(shift)); + return v; +} + +VALUE rb_big_hash(VALUE x) { st_index_t hash; @@ -6730,14 +6934,15 @@ rb_big_hash(VALUE x) /* * call-seq: - * big.coerce(numeric) -> array + * int.coerce(numeric) -> array * - * Returns an array with both a +numeric+ and a +big+ represented as Bignum - * objects. + * Returns an array with both a +numeric+ and a +int+ represented as + * Integer objects or Float objects. * - * This is achieved by converting +numeric+ to a Bignum. + * This is achieved by converting +numeric+ to an Integer or a Float. * - * A TypeError is raised if the +numeric+ is not a Fixnum or Bignum type. + * A TypeError is raised if the +numeric+ is not an Integer or a Float + * type. * * (0x3FFFFFFFFFFFFFFF+1).coerce(42) #=> [42, 4611686018427387904] */ @@ -6759,8 +6964,8 @@ VALUE rb_big_abs(VALUE x) { if (BIGNUM_NEGATIVE_P(x)) { - x = rb_big_clone(x); - BIGNUM_SET_POSITIVE_SIGN(x); + x = rb_big_clone(x); + BIGNUM_SET_POSITIVE_SIGN(x); } return x; } @@ -6827,17 +7032,14 @@ rb_big_bit_length(VALUE big) VALUE rb_big_odd_p(VALUE num) { - if (BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1) { - return Qtrue; - } - return Qfalse; + return RBOOL(BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1); } VALUE rb_big_even_p(VALUE num) { if (BIGNUM_LEN(num) != 0 && BDIGITS(num)[0] & 1) { - return Qfalse; + return Qfalse; } return Qtrue; } @@ -6855,96 +7057,36 @@ BDIGIT rb_bdigit_dbl_isqrt(BDIGIT_DBL); # define BDIGIT_DBL_TO_DOUBLE(n) (double)(n) #endif -static BDIGIT * -estimate_initial_sqrt(VALUE *xp, const size_t xn, const BDIGIT *nds, size_t len) -{ - enum {dbl_per_bdig = roomof(DBL_MANT_DIG,BITSPERDIG)}; - const int zbits = nlz(nds[len-1]); - VALUE x = *xp = bignew_1(0, xn, 1); /* division may release the GVL */ - BDIGIT *xds = BDIGITS(x); - BDIGIT_DBL d = bary2bdigitdbl(nds+len-dbl_per_bdig, dbl_per_bdig); - BDIGIT lowbits = 1; - int rshift = (int)((BITSPERDIG*2-zbits+(len&BITSPERDIG&1) - DBL_MANT_DIG + 1) & ~1); - double f; - - if (rshift > 0) { - lowbits = (BDIGIT)d & ~(~(BDIGIT)1U << rshift); - d >>= rshift; - } - else if (rshift < 0) { - d <<= -rshift; - d |= nds[len-dbl_per_bdig-1] >> (BITSPERDIG+rshift); - } - f = sqrt(BDIGIT_DBL_TO_DOUBLE(d)); - d = (BDIGIT_DBL)ceil(f); - if (BDIGIT_DBL_TO_DOUBLE(d) == f) { - if (lowbits || (lowbits = !bary_zero_p(nds, len-dbl_per_bdig))) - ++d; - } - else { - lowbits = 1; - } - rshift /= 2; - rshift += (2-(len&1))*BITSPERDIG/2; - if (rshift >= 0) { - if (nlz((BDIGIT)d) + rshift >= BITSPERDIG) { - /* (d << rshift) does cause overflow. - * example: Integer.sqrt(0xffff_ffff_ffff_ffff ** 2) - */ - d = ~(BDIGIT_DBL)0; - } - else { - d <<= rshift; - } - } - BDIGITS_ZERO(xds, xn-2); - bdigitdbl2bary(&xds[xn-2], 2, d); - - if (!lowbits) return NULL; /* special case, exact result */ - return xds; -} - VALUE rb_big_isqrt(VALUE n) { BDIGIT *nds = BDIGITS(n); size_t len = BIGNUM_LEN(n); - size_t xn = (len+1) / 2; - VALUE x; - BDIGIT *xds; if (len <= 2) { - BDIGIT sq = rb_bdigit_dbl_isqrt(bary2bdigitdbl(nds, len)); + BDIGIT sq = rb_bdigit_dbl_isqrt(bary2bdigitdbl(nds, len)); #if SIZEOF_BDIGIT > SIZEOF_LONG - return ULL2NUM(sq); + return ULL2NUM(sq); #else - return ULONG2NUM(sq); + return ULONG2NUM(sq); #endif } - else if ((xds = estimate_initial_sqrt(&x, xn, nds, len)) != 0) { - size_t tn = xn + BIGDIVREM_EXTRA_WORDS; - VALUE t = bignew_1(0, tn, 1); - BDIGIT *tds = BDIGITS(t); - tn = BIGNUM_LEN(t); - - /* t = n/x */ - while (bary_divmod_branch(tds, tn, NULL, 0, nds, len, xds, xn), - bary_cmp(tds, tn, xds, xn) < 0) { - int carry; - BARY_TRUNC(tds, tn); - /* x = (x+t)/2 */ - carry = bary_add(xds, xn, xds, xn, tds, tn); - bary_small_rshift(xds, xds, xn, 1, carry); - tn = BIGNUM_LEN(t); - } - rb_big_realloc(t, 0); - rb_gc_force_recycle(t); - } - RBASIC_SET_CLASS_RAW(x, rb_cInteger); - return x; + else { + size_t shift = FIX2LONG(rb_big_bit_length(n)) / 4; + VALUE n2 = rb_int_rshift(n, SIZET2NUM(2 * shift)); + VALUE x = FIXNUM_P(n2) ? LONG2FIX(rb_ulong_isqrt(FIX2ULONG(n2))) : rb_big_isqrt(n2); + /* x = (x+n/x)/2 */ + x = rb_int_plus(rb_int_lshift(x, SIZET2NUM(shift - 1)), rb_int_idiv(rb_int_rshift(n, SIZET2NUM(shift + 1)), x)); + VALUE xx = rb_int_mul(x, x); + while (rb_int_gt(xx, n)) { + xx = rb_int_minus(xx, rb_int_minus(rb_int_plus(x, x), INT2FIX(1))); + x = rb_int_minus(x, INT2FIX(1)); + } + return x; + } } -#ifdef USE_GMP +#if USE_GMP static void bary_powm_gmp(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn, const BDIGIT *mds, size_t mn) { @@ -6970,7 +7112,7 @@ bary_powm_gmp(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT static VALUE int_pow_tmp3(VALUE x, VALUE y, VALUE m, int nega_flg) { -#ifdef USE_GMP +#if USE_GMP VALUE z; size_t xn, yn, mn, zn; @@ -6980,14 +7122,14 @@ int_pow_tmp3(VALUE x, VALUE y, VALUE m, int nega_flg) if (FIXNUM_P(y)) { y = rb_int2big(FIX2LONG(y)); } - assert(RB_BIGNUM_TYPE_P(m)); + RUBY_ASSERT(RB_BIGNUM_TYPE_P(m)); xn = BIGNUM_LEN(x); yn = BIGNUM_LEN(y); mn = BIGNUM_LEN(m); zn = mn; z = bignew(zn, 1); bary_powm_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn, BDIGITS(m), mn); - if (nega_flg & BIGNUM_POSITIVE_P(z)) { + if (nega_flg && BIGNUM_POSITIVE_P(z) && !BIGZEROP(z)) { z = rb_big_minus(z, m); } RB_GC_GUARD(x); @@ -7015,7 +7157,7 @@ int_pow_tmp3(VALUE x, VALUE y, VALUE m, int nega_flg) x = rb_int_modulo(x, m); } - if (nega_flg && rb_int_positive_p(tmp)) { + if (nega_flg && rb_int_positive_p(tmp) && !rb_int_zero_p(tmp)) { tmp = rb_int_minus(tmp, m); } return tmp; @@ -7127,6 +7269,11 @@ rb_int_powm(int const argc, VALUE * const argv, VALUE const num) rb_raise(rb_eTypeError, "Integer#pow() 2nd argument not allowed unless all arguments are integers"); } + if (rb_int_zero_p(a) && !rb_int_zero_p(b)) { + /* shortcut; 0**x => 0 except for x == 0 */ + return INT2FIX(0); + } + if (rb_int_negative_p(m)) { m = rb_int_uminus(m); nega_flg = 1; @@ -7146,7 +7293,7 @@ rb_int_powm(int const argc, VALUE * const argv, VALUE const num) } else { if (rb_bigzero_p(m)) rb_num_zerodiv(); - if (bignorm(m) == INT2FIX(1)) return INT2FIX(0); + if (bignorm(m) == INT2FIX(1)) return INT2FIX(0); return int_pow_tmp3(rb_int_modulo(a, m), b, m, nega_flg); } } @@ -7174,13 +7321,9 @@ rb_int_powm(int const argc, VALUE * const argv, VALUE const num) void Init_Bignum(void) { - /* An obsolete class, use Integer */ - rb_define_const(rb_cObject, "Bignum", rb_cInteger); - rb_deprecate_constant(rb_cObject, "Bignum"); - rb_define_method(rb_cInteger, "coerce", rb_int_coerce, 1); -#ifdef USE_GMP +#if USE_GMP /* The version of loaded GMP. */ rb_define_const(rb_cInteger, "GMP_VERSION", rb_sprintf("GMP %s", gmp_version)); #endif |