From 9bf8a375721ab809c3ad80407068ca6fad534c42 Mon Sep 17 00:00:00 2001 From: nobu Date: Thu, 19 Jul 2007 05:38:48 +0000 Subject: * bignum.c (rb_big_lshift, rb_big_rshift): separated functions to get rid of infinite recursion. fixed calculation in edge cases. [ruby-dev:31244] * numeric.c (rb_fix_lshift, rb_fix_rshift): ditto. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_1_8@12814 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- ChangeLog | 8 +++++ bignum.c | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++------ intern.h | 1 + numeric.c | 43 ++++++++++++++++++-------- version.h | 6 ++-- 5 files changed, 136 insertions(+), 24 deletions(-) diff --git a/ChangeLog b/ChangeLog index 1363cf2118..51f3e49a24 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +Thu Jul 19 14:38:45 2007 Nobuyoshi Nakada + + * bignum.c (rb_big_lshift, rb_big_rshift): separated functions + to get rid of infinite recursion. fixed calculation in edge + cases. [ruby-dev:31244] + + * numeric.c (rb_fix_lshift, rb_fix_rshift): ditto. + Wed Jul 18 16:57:41 2007 Nobuyoshi Nakada * bignum.c (rb_big_pow): refine overflow check. [ruby-dev:31242] diff --git a/bignum.c b/bignum.c index 16fbe86527..f5a47871d3 100644 --- a/bignum.c +++ b/bignum.c @@ -1577,7 +1577,19 @@ bdigbitsize(BDIGIT x) return size; } -static VALUE rb_big_rshift _((VALUE,VALUE)); +static VALUE big_lshift _((VALUE, unsigned int)); +static VALUE big_rshift _((VALUE, unsigned int)); + +static VALUE big_shift(x, n) + VALUE x; + int n; +{ + if (n < 0) + return big_lshift(x, (unsigned int)n); + else if (n > 0) + return big_rshift(x, (unsigned int)n); + return x; +} /* * call-seq: @@ -1636,7 +1648,7 @@ rb_big_quo(x, y) ex = (RBIGNUM(bigtrunc(x))->len - 1) * BITSPERDIG; ex += bdigbitsize(BDIGITS(x)[RBIGNUM(x)->len - 1]); ex -= 2 * DBL_BIGDIG * BITSPERDIG; - if (ex) x = rb_big_rshift(x, INT2FIX(ex)); + if (ex) x = big_shift(x, ex); switch (TYPE(y)) { case T_FIXNUM: @@ -1645,7 +1657,7 @@ rb_big_quo(x, y) ey = (RBIGNUM(bigtrunc(y))->len - 1) * BITSPERDIG; ey += bdigbitsize(BDIGITS(y)[RBIGNUM(y)->len - 1]); ey -= DBL_BIGDIG * BITSPERDIG; - if (ey) y = rb_big_rshift(y, INT2FIX(ey)); + if (ey) y = big_shift(y, ey); bignum: bigdivrem(x, y, &z, 0); return rb_float_new(ldexp(big2dbl(z), ex - ey)); @@ -1953,6 +1965,16 @@ rb_big_xor(xx, yy) return bignorm(z); } +static VALUE +check_shiftdown(VALUE y, VALUE x) +{ + if (!RBIGNUM(x)->len) return INT2FIX(0); + if (RBIGNUM(y)->len > SIZEOF_LONG / SIZEOF_BDIGITS) { + return RBIGNUM(x)->sign ? INT2FIX(0) : INT2FIX(-1); + } + return Qnil; +} + /* * call-seq: * big << numeric => integer @@ -1963,16 +1985,46 @@ rb_big_xor(xx, yy) VALUE rb_big_lshift(x, y) VALUE x, y; +{ + int shift, neg = 0; + + for (;;) { + if (FIXNUM_P(y)) { + shift = FIX2INT(y); + if (shift < 0) { + neg = 1; + shift = -shift; + } + break; + } + else if (TYPE(y) == T_BIGNUM) { + if (!RBIGNUM(y)->sign) { + VALUE t = check_shiftdown(y, x); + if (!NIL_P(t)) return t; + neg = 1; + } + shift = big2ulong(y, "long", Qtrue); + break; + } + y = rb_to_int(y); + } + + if (neg) return big_rshift(x, shift); + return big_lshift(x, shift); +} + +static VALUE +big_lshift(x, shift) + VALUE x; + unsigned int shift; { BDIGIT *xds, *zds; - int shift = NUM2INT(y); int s1 = shift/BITSPERDIG; int s2 = shift%BITSPERDIG; VALUE z; BDIGIT_DBL num = 0; long len, i; - if (shift < 0) return rb_big_rshift(x, INT2FIX(-shift)); len = RBIGNUM(x)->len; z = bignew(len+s1+1, RBIGNUM(x)->sign); zds = BDIGITS(z); @@ -1996,12 +2048,46 @@ rb_big_lshift(x, y) * Shifts big right _numeric_ positions (left if _numeric_ is negative). */ -static VALUE +VALUE rb_big_rshift(x, y) VALUE x, y; +{ + int shift; + int neg = 0; + + for (;;) { + if (FIXNUM_P(y)) { + shift = FIX2INT(y); + if (shift < 0) { + neg = 1; + shift = -shift; + } + break; + } + else if (TYPE(y) == T_BIGNUM) { + if (RBIGNUM(y)->sign) { + VALUE t = check_shiftdown(y, x); + if (!NIL_P(t)) return t; + } + else { + neg = 1; + } + shift = big2ulong(y, "long", Qtrue); + break; + } + y = rb_to_int(y); + } + + if (neg) return big_lshift(x, shift); + return big_rshift(x, shift); +} + +static VALUE +big_rshift(x, shift) + VALUE x; + unsigned int shift; { BDIGIT *xds, *zds; - int shift = NUM2INT(y); long s1 = shift/BITSPERDIG; long s2 = shift%BITSPERDIG; VALUE z; @@ -2009,8 +2095,6 @@ rb_big_rshift(x, y) long i, j; volatile VALUE save_x; - if (shift < 0) return rb_big_lshift(x, INT2FIX(-shift)); - if (s1 > RBIGNUM(x)->len) { if (RBIGNUM(x)->sign) return INT2FIX(0); diff --git a/intern.h b/intern.h index 65c916328c..0dc3bffe55 100644 --- a/intern.h +++ b/intern.h @@ -114,6 +114,7 @@ VALUE rb_mod_ancestors _((VALUE)); VALUE rb_class_instance_methods _((int, VALUE*, VALUE)); VALUE rb_class_public_instance_methods _((int, VALUE*, VALUE)); VALUE rb_class_protected_instance_methods _((int, VALUE*, VALUE)); +VALUE rb_big_rshift(VALUE, VALUE); VALUE rb_class_private_instance_methods _((int, VALUE*, VALUE)); VALUE rb_obj_singleton_methods _((int, VALUE*, VALUE)); void rb_define_method_id _((VALUE, ID, VALUE (*)(ANYARGS), int)); diff --git a/numeric.c b/numeric.c index 0665314592..07eca3e04e 100644 --- a/numeric.c +++ b/numeric.c @@ -2498,7 +2498,8 @@ fix_xor(x, y) return LONG2NUM(val); } -static VALUE fix_rshift _((VALUE, VALUE)); +static VALUE fix_lshift _((long, unsigned long)); +static VALUE fix_rshift _((long, unsigned long)); /* * call-seq: @@ -2508,18 +2509,28 @@ static VALUE fix_rshift _((VALUE, VALUE)); */ static VALUE -fix_lshift(x, y) +rb_fix_lshift(x, y) VALUE x, y; { long val, width; val = NUM2LONG(x); - width = NUM2LONG(y); + if (!FIXNUM_P(y)) + return rb_big_lshift(rb_int2big(val), y); + width = FIX2LONG(y); if (width < 0) - return fix_rshift(x, LONG2FIX(-width)); + return fix_rshift(val, (unsigned long)-width); + return fix_lshift(val, width); +} + +static VALUE +fix_lshift(val, width) + long val; + unsigned long width; +{ if (width > (sizeof(VALUE)*CHAR_BIT-1) || ((unsigned long)val)>>(sizeof(VALUE)*CHAR_BIT-1-width) > 0) { - return rb_big_lshift(rb_int2big(val), y); + return rb_big_lshift(rb_int2big(val), ULONG2NUM(width)); } val = val << width; return LONG2NUM(val); @@ -2533,16 +2544,24 @@ fix_lshift(x, y) */ static VALUE -fix_rshift(x, y) +rb_fix_rshift(x, y) VALUE x, y; { long i, val; - i = NUM2LONG(y); - if (i < 0) - return fix_lshift(x, LONG2FIX(-i)); - if (i == 0) return x; val = FIX2LONG(x); + if (!FIXNUM_P(y)) + return rb_big_rshift(rb_int2big(val), y); + i = FIX2LONG(y); + if (i == 0) return x; + if (i < 0) + return fix_lshift(val, (unsigned long)-i); + return fix_rshift(val, i); +} + +static VALUE +fix_rshift(long val, unsigned long i) +{ if (i >= sizeof(long)*CHAR_BIT-1) { if (val < 0) return INT2FIX(-1); return INT2FIX(0); @@ -2945,8 +2964,8 @@ Init_Numeric() rb_define_method(rb_cFixnum, "^", fix_xor, 1); rb_define_method(rb_cFixnum, "[]", fix_aref, 1); - rb_define_method(rb_cFixnum, "<<", fix_lshift, 1); - rb_define_method(rb_cFixnum, ">>", fix_rshift, 1); + rb_define_method(rb_cFixnum, "<<", rb_fix_lshift, 1); + rb_define_method(rb_cFixnum, ">>", rb_fix_rshift, 1); rb_define_method(rb_cFixnum, "to_f", fix_to_f, 0); rb_define_method(rb_cFixnum, "size", fix_size, 0); diff --git a/version.h b/version.h index 1b622755c1..9d6f2489cb 100644 --- a/version.h +++ b/version.h @@ -1,7 +1,7 @@ #define RUBY_VERSION "1.8.6" -#define RUBY_RELEASE_DATE "2007-07-18" +#define RUBY_RELEASE_DATE "2007-07-19" #define RUBY_VERSION_CODE 186 -#define RUBY_RELEASE_CODE 20070718 +#define RUBY_RELEASE_CODE 20070719 #define RUBY_PATCHLEVEL 5000 #define RUBY_VERSION_MAJOR 1 @@ -9,7 +9,7 @@ #define RUBY_VERSION_TEENY 6 #define RUBY_RELEASE_YEAR 2007 #define RUBY_RELEASE_MONTH 7 -#define RUBY_RELEASE_DAY 18 +#define RUBY_RELEASE_DAY 19 #ifdef RUBY_EXTERN RUBY_EXTERN const char ruby_version[]; -- cgit v1.2.3