ruby-changes:29890
From: akr <ko1@a...>
Date: Sat, 13 Jul 2013 23:03:23 +0900 (JST)
Subject: [ruby-changes:29890] akr:r41942 (trunk): * bignum.c (big_shift3): New function.
akr 2013-07-13 23:03:13 +0900 (Sat, 13 Jul 2013) New Revision: 41942 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=41942 Log: * bignum.c (big_shift3): New function. big_lshift and big_rshift are merged. (big_shift2): New function. (big_lshift): Use big_shift3. (big_rshift): Ditto. (check_shiftdown): Removed. (rb_big_lshift): Use big_shift2 and big_shift3. (rb_big_rshift): Ditto. (big_lshift): Removed. (big_rshift): Ditto. Modified files: trunk/ChangeLog trunk/bignum.c trunk/test/ruby/test_bignum.rb Index: ChangeLog =================================================================== --- ChangeLog (revision 41941) +++ ChangeLog (revision 41942) @@ -1,3 +1,16 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Sat Jul 13 22:58:16 2013 Tanaka Akira <akr@f...> + + * bignum.c (big_shift3): New function. + big_lshift and big_rshift are merged. + (big_shift2): New function. + (big_lshift): Use big_shift3. + (big_rshift): Ditto. + (check_shiftdown): Removed. + (rb_big_lshift): Use big_shift2 and big_shift3. + (rb_big_rshift): Ditto. + (big_lshift): Removed. + (big_rshift): Ditto. + Sat Jul 13 15:51:38 2013 Tanaka Akira <akr@f...> * bignum.c (bary_small_lshift): Use size_t instead of long. Index: bignum.c =================================================================== --- bignum.c (revision 41941) +++ bignum.c (revision 41942) @@ -445,6 +445,7 @@ bary_small_lshift(BDIGIT *zds, BDIGIT *x https://github.com/ruby/ruby/blob/trunk/bignum.c#L445 { size_t i; BDIGIT_DBL num = 0; + assert(0 <= shift && shift < BITSPERDIG); for (i=0; i<n; i++) { num = num | (BDIGIT_DBL)*xds++ << shift; @@ -459,6 +460,9 @@ bary_small_rshift(BDIGIT *zds, BDIGIT *x https://github.com/ruby/ruby/blob/trunk/bignum.c#L460 { BDIGIT_DBL num = 0; BDIGIT x; + + assert(0 <= shift && shift < BITSPERDIG); + if (sign_bit) { num = (~(BDIGIT_DBL)0) << BITSPERDIG; } @@ -3187,6 +3191,104 @@ rb_str2inum(VALUE str, int base) https://github.com/ruby/ruby/blob/trunk/bignum.c#L3191 return rb_str_to_inum(str, base, base==0); } +static VALUE +big_shift3(VALUE x, int lshift_p, size_t shift_numdigits, int shift_numbits) +{ + BDIGIT *xds, *zds; + long s1; + int s2; + VALUE z; + long xn; + + if (LONG_MAX < shift_numdigits) { + rb_raise(rb_eArgError, "too big number"); + } + + s1 = shift_numdigits; + s2 = shift_numbits; + + if (lshift_p) { + xn = RBIGNUM_LEN(x); + z = bignew(xn+s1+1, RBIGNUM_SIGN(x)); + zds = BDIGITS(z); + MEMZERO(zds, BDIGIT, s1); + xds = BDIGITS(x); + zds[xn+s1] = bary_small_lshift(zds+s1, xds, xn, s2); + } + else { + long zn; + BDIGIT hibitsx; + if (s1 >= RBIGNUM_LEN(x)) { + if (RBIGNUM_POSITIVE_P(x) || + bary_zero_p(BDIGITS(x), RBIGNUM_LEN(x))) + return INT2FIX(0); + else + return INT2FIX(-1); + } + hibitsx = abs2twocomp(&x, &xn); + xds = BDIGITS(x); + if (xn <= s1) { + return hibitsx ? INT2FIX(-1) : INT2FIX(0); + } + zn = xn - s1; + z = bignew(zn, 0); + zds = BDIGITS(z); + bary_small_rshift(zds, xds+s1, zn, s2, hibitsx != 0); + twocomp2abs_bang(z, hibitsx != 0); + } + RB_GC_GUARD(x); + return z; +} + +static VALUE +big_shift2(VALUE x, int lshift_p, VALUE y) +{ + int sign; + size_t lens[2]; + size_t shift_numdigits; + int shift_numbits; + + assert(POW2_P(CHAR_BIT)); + assert(POW2_P(BITSPERDIG)); + + if (BIGZEROP(x)) + return INT2FIX(0); + sign = rb_integer_pack(y, lens, numberof(lens), sizeof(size_t), 0, + INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); + if (sign < 0) { + lshift_p = !lshift_p; + sign = -sign; + } + if (lshift_p) { + if (1 < sign || CHAR_BIT <= lens[1]) + rb_raise(rb_eRangeError, "shift width too big"); + } + else { + if (1 < sign || CHAR_BIT <= lens[1]) + return RBIGNUM_POSITIVE_P(x) ? INT2FIX(0) : INT2FIX(-1); + } + shift_numbits = lens[0] & (BITSPERDIG-1); + shift_numdigits = (lens[0] >> bitsize(BITSPERDIG-1)) | + (lens[1] << (CHAR_BIT*SIZEOF_SIZE_T - bitsize(BITSPERDIG-1))); + return big_shift3(x, lshift_p, shift_numdigits, shift_numbits); +} + +static VALUE +big_lshift(VALUE x, unsigned long shift) +{ + long s1 = shift/BITSPERDIG; + int s2 = (int)(shift%BITSPERDIG); + return big_shift3(x, 1, s1, s2); +} + +static VALUE +big_rshift(VALUE x, unsigned long shift) +{ + long s1 = shift/BITSPERDIG; + int s2 = (int)(shift%BITSPERDIG); + return big_shift3(x, 0, s1, s2); +} + static inline int ones(register unsigned long x) { @@ -4516,8 +4618,6 @@ big_split3(VALUE v, long n, volatile VAL https://github.com/ruby/ruby/blob/trunk/bignum.c#L4618 *p2 = bigtrunc(v2); } -static VALUE big_lshift(VALUE, unsigned long); -static VALUE big_rshift(VALUE, unsigned long); static VALUE bigdivrem(VALUE, VALUE, volatile VALUE*, volatile VALUE*); static VALUE @@ -5682,16 +5782,6 @@ rb_big_xor(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/bignum.c#L5782 return bignorm(z); } -static VALUE -check_shiftdown(VALUE y, VALUE x) -{ - if (!RBIGNUM_LEN(x)) return INT2FIX(0); - if (BIGSIZE(y) > SIZEOF_LONG) { - return RBIGNUM_SIGN(x) ? INT2FIX(0) : INT2FIX(-1); - } - return Qnil; -} - /* * call-seq: * big << numeric -> integer @@ -5702,56 +5792,33 @@ check_shiftdown(VALUE y, VALUE x) https://github.com/ruby/ruby/blob/trunk/bignum.c#L5792 VALUE rb_big_lshift(VALUE x, VALUE y) { - unsigned long shift; - int neg = 0; + int lshift_p; + size_t shift_numdigits; + int shift_numbits; for (;;) { if (FIXNUM_P(y)) { long l = FIX2LONG(y); + unsigned long shift; if (0 <= l) { + lshift_p = 1; shift = l; } else { - neg = 1; + lshift_p = 0; shift = 1+(unsigned long)(-(l+1)); } - break; + shift_numbits = shift & (BITSPERDIG-1); + shift_numdigits = shift >> bitsize(BITSPERDIG-1); + return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits)); } else if (RB_TYPE_P(y, T_BIGNUM)) { - if (!RBIGNUM_SIGN(y)) { - VALUE t = check_shiftdown(y, x); - if (!NIL_P(t)) return t; - neg = 1; - } - shift = big2ulong(y, "long"); - break; + return bignorm(big_shift2(x, 1, y)); } y = rb_to_int(y); } - - x = neg ? big_rshift(x, shift) : big_lshift(x, shift); - return bignorm(x); } -static VALUE -big_lshift(VALUE x, unsigned long shift) -{ - BDIGIT *xds, *zds; - long s1 = shift/BITSPERDIG; - int s2 = (int)(shift%BITSPERDIG); - VALUE z; - long len, i; - - len = RBIGNUM_LEN(x); - z = bignew(len+s1+1, RBIGNUM_SIGN(x)); - zds = BDIGITS(z); - for (i=0; i<s1; i++) { - *zds++ = 0; - } - xds = BDIGITS(x); - zds[len] = bary_small_lshift(zds, xds, len, s2); - return z; -} /* * call-seq: @@ -5763,69 +5830,31 @@ big_lshift(VALUE x, unsigned long shift) https://github.com/ruby/ruby/blob/trunk/bignum.c#L5830 VALUE rb_big_rshift(VALUE x, VALUE y) { - unsigned long shift; - int neg = 0; + int lshift_p; + size_t shift_numdigits; + int shift_numbits; for (;;) { if (FIXNUM_P(y)) { long l = FIX2LONG(y); + unsigned long shift; if (0 <= l) { + lshift_p = 0; shift = l; } else { - neg = 1; + lshift_p = 1; shift = 1+(unsigned long)(-(l+1)); } - break; + shift_numbits = shift & (BITSPERDIG-1); + shift_numdigits = shift >> bitsize(BITSPERDIG-1); + return bignorm(big_shift3(x, lshift_p, shift_numdigits, shift_numbits)); } else if (RB_TYPE_P(y, T_BIGNUM)) { - if (RBIGNUM_SIGN(y)) { - VALUE t = check_shiftdown(y, x); - if (!NIL_P(t)) return t; - } - else { - neg = 1; - } - shift = big2ulong(y, "long"); - break; + return bignorm(big_shift2(x, 0, y)); } y = rb_to_int(y); } - - x = neg ? big_lshift(x, shift) : big_rshift(x, shift); - return bignorm(x); -} - -static VALUE -big_rshift(VALUE x, unsigned long shift) -{ - BDIGIT *xds, *zds; - long s1 = shift/BITSPERDIG; - int s2 = (int)(shift%BITSPERDIG); - VALUE z; - long j; - long xl; - BDIGIT hibitsx; - - if (s1 > RBIGNUM_LEN(x)) { - if (RBIGNUM_POSITIVE_P(x) || bary_zero_p(BDIGITS(x), RBIGNUM_LEN(x))) - return INT2FIX(0); - else - return INT2FIX(-1); - } - hibitsx = abs2twocomp(&x, &xl); - xds = BDIGITS(x); - j = xl - s1; - if (j <= 0) { - if (!hibitsx) return INT2FIX(0); - else return INT2FIX(-1); - } - z = bignew(j, 0); - zds = BDIGITS(z); - bary_small_rshift(zds, xds+s1, j, s2, hibitsx != 0); - twocomp2abs_bang(z, hibitsx != 0); - RB_GC_GUARD(x); - return z; } /* Index: test/ruby/test_bignum.rb =================================================================== --- test/ruby/test_bignum.rb (revision 41941) +++ test/ruby/test_bignum.rb (revision 41942) @@ -533,6 +533,11 @@ class TestBignum < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_bignum.rb#L533 assert_equal(-1, -(2**31) >> 32) end + def test_shift_bigshift + big = 2**300 + assert_equal(2**65538 / (2**65537), 2**65538 >> big.coerce(65537).first) + end + def test_aref assert_equal(0, (2**32)[0]) assert_equal(0, (2**32)[2**32]) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/