From: Nobuyoshi Nakada Date: 2007-07-19T00:42:03+09:00 Subject: [ruby-dev:31256] Re: shift なかだです。 At Wed, 18 Jul 2007 17:24:12 +0900, Tanaka Akira wrote in [ruby-dev:31249]: > でも、直ってないかんじ? たしかに。テストも追加しました。 Index: bignum.c =================================================================== --- bignum.c (revision 12813) +++ bignum.c (working copy) @@ -1530,5 +1530,15 @@ bdigbitsize(BDIGIT x) } -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(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; +} /* @@ -1559,5 +1569,5 @@ rb_big_quo(VALUE x, VALUE y) 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)) { @@ -1568,5 +1578,5 @@ rb_big_quo(VALUE x, VALUE y) 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); @@ -1873,4 +1883,14 @@ rb_big_xor(VALUE xx, VALUE yy) } +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: @@ -1883,6 +1903,35 @@ VALUE rb_big_lshift(VALUE x, VALUE 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(VALUE x, unsigned int shift) +{ BDIGIT *xds, *zds; - int shift = NUM2INT(y); int s1 = shift/BITSPERDIG; int s2 = shift%BITSPERDIG; @@ -1891,5 +1940,4 @@ rb_big_lshift(VALUE x, VALUE y) 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); @@ -1915,9 +1963,41 @@ rb_big_lshift(VALUE x, VALUE y) */ -static VALUE +VALUE rb_big_rshift(VALUE x, VALUE 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(VALUE x, unsigned int shift) +{ BDIGIT *xds, *zds; - int shift = NUM2INT(y); long s1 = shift/BITSPERDIG; long s2 = shift%BITSPERDIG; @@ -1927,6 +2007,4 @@ rb_big_rshift(VALUE x, VALUE y) volatile VALUE save_x; - if (shift < 0) return rb_big_lshift(x, INT2FIX(-shift)); - if (s1 > RBIGNUM(x)->len) { if (RBIGNUM(x)->sign) Index: numeric.c =================================================================== --- numeric.c (revision 12813) +++ numeric.c (working copy) @@ -2592,5 +2592,6 @@ fix_xor(VALUE x, VALUE y) } -static VALUE fix_rshift(VALUE, VALUE); +static VALUE fix_lshift(long, unsigned long); +static VALUE fix_rshift(long, unsigned long); /* @@ -2602,15 +2603,23 @@ static VALUE fix_rshift(VALUE, VALUE); static VALUE -fix_lshift(VALUE x, VALUE y) +rb_fix_lshift(VALUE x, VALUE 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(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), LONG2NUM(width)); } val = val << width; @@ -2626,13 +2635,21 @@ fix_lshift(VALUE x, VALUE y) static VALUE -fix_rshift(VALUE x, VALUE y) +rb_fix_rshift(VALUE x, VALUE 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); @@ -2886,6 +2903,4 @@ static VALUE int_dotimes(VALUE num) { - VALUE val; - RETURN_ENUMERATOR(num, 0, 0); @@ -3106,6 +3121,6 @@ Init_Numeric(void) 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); Index: include/ruby/intern.h =================================================================== --- include/ruby/intern.h (revision 12813) +++ include/ruby/intern.h (working copy) @@ -115,4 +115,5 @@ VALUE rb_big_or(VALUE, VALUE); VALUE rb_big_xor(VALUE, VALUE); VALUE rb_big_lshift(VALUE, VALUE); +VALUE rb_big_rshift(VALUE, VALUE); /* class.c */ VALUE rb_class_boot(VALUE); Index: test/ruby/test_integer.rb =================================================================== --- test/ruby/test_integer.rb (revision 12813) +++ test/ruby/test_integer.rb (working copy) @@ -94,4 +94,12 @@ class TestInteger < Test::Unit::TestCase #VS.map! {|v| 0x4000000000000000.coerce(v)[0] } + BDSIZE = 0x4000000000000000.coerce(0)[0].size + def self.bdsize(x) + ((x + 1) / 8 + BDSIZE) / BDSIZE * BDSIZE + end + def bdsize(x) + self.class.bdsize(x) + end + def test_aref VS.each {|a| @@ -234,4 +242,9 @@ class TestInteger < Test::Unit::TestCase } } + assert_equal(0, 1 << -0x40000000) + assert_equal(0, 1 << -0x40000001) + assert_equal(0, 1 << -0x80000000) + assert_equal(0, 1 << -0x80000001) + assert_equal(bdsize(0x80000000), (1 << 0x80000000).size) end @@ -249,4 +262,10 @@ class TestInteger < Test::Unit::TestCase } } + assert_equal(bdsize(0x40000001), (1 >> -0x40000001).size) + assert((1 >> 0x80000000).zero?) + assert((1 >> 0xffffffff).zero?) + assert((1 >> 0x100000000).zero?) + assert_equal((1 << 0x40000000), (1 >> -0x40000000)) + assert_equal((1 << 0x40000001), (1 >> -0x40000001)) end -- --- 僕の前にBugはない。 --- 僕の後ろにBugはできる。 中田 伸悦