diff options
| -rw-r--r-- | ChangeLog | 16 | ||||
| -rw-r--r-- | bignum.c | 183 | ||||
| -rw-r--r-- | ext/-test-/bignum/pack.c | 19 | ||||
| -rw-r--r-- | internal.h | 1 | ||||
| -rw-r--r-- | sprintf.c | 219 | ||||
| -rw-r--r-- | test/-ext-/bignum/test_pack.rb | 44 |
6 files changed, 326 insertions, 156 deletions
@@ -1,3 +1,19 @@ +Tue Jun 11 20:52:43 2013 Tanaka Akira <akr@fsij.org> + + * bignum.c (rb_integer_pack_internal): Renamed from rb_integer_pack + and overflow_2comp argument added. + (rb_integer_pack): Just call rb_integer_pack_internal. + (rb_integer_pack_2comp): New function. + + * internal.h (rb_integer_pack_2comp): Declared. + + * sprintf.c (rb_str_format): Use rb_integer_pack and + rb_integer_pack_2comp to format binary/octal/hexadecimal integers. + (ruby_digitmap): Declared. + (remove_sign_bits): Removed. + (BITSPERDIG): Ditto. + (EXTENDSIGN): Ditto. + Tue Jun 11 16:15:03 2013 Nobuyoshi Nakada <nobu@ruby-lang.org> * array.c (ary_shrink_capa): shrink the capacity so it fits just with @@ -842,37 +842,11 @@ integer_pack_take_lowbits(int n, BDIGIT_DBL *ddp, int *numbits_in_dd_p) return ret; } -/* - * Export an integer into a buffer. - * - * This function fills the buffer specified by _words_ and _numwords_ as - * abs(val) in the format specified by _wordsize_, _nails_ and _flags_. - * - * [val] Fixnum, Bignum or another integer like object which has to_int method. - * [words] buffer to export abs(val). - * [numwords] the size of given buffer as number of words. - * [wordsize] the size of word as number of bytes. - * [nails] number of padding bits in a word. - * Most significant nails bits of each word are filled by zero. - * [flags] bitwise or of constants which name starts "INTEGER_PACK_". - * It specifies word order and byte order. - * - * This function returns the signedness and overflow condition as follows: - * -2 : negative overflow. val <= -2**(numwords*(wordsize*CHAR_BIT-nails)) - * -1 : negative without overflow. -2**(numwords*(wordsize*CHAR_BIT-nails)) < val < 0 - * 0 : zero. val == 0 - * 1 : positive without overflow. 0 < val < 2**(numwords*(wordsize*CHAR_BIT-nails)) - * 2 : positive overflow. 2**(numwords*(wordsize*CHAR_BIT-nails)) <= val - * - * The least significant words of abs(val) are filled in the buffer when overflow occur. - */ - -int -rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t nails, int flags) +static int +rb_integer_pack_internal(VALUE val, void *words, size_t numwords, size_t wordsize, size_t nails, int flags, int overflow_2comp) { int sign; - BDIGIT *dp; - BDIGIT *de; + BDIGIT *ds, *dp, *de; BDIGIT fixbuf[(sizeof(long) + SIZEOF_BDIGITS - 1) / SIZEOF_BDIGITS]; unsigned char *buf, *bufend; @@ -902,12 +876,12 @@ rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t } } #endif - dp = fixbuf; + ds = dp = fixbuf; de = fixbuf + numberof(fixbuf); } else { sign = RBIGNUM_POSITIVE_P(val) ? 1 : -1; - dp = BDIGITS(val); + ds = dp = BDIGITS(val); de = dp + RBIGNUM_LEN(val); } while (dp < de && de[-1] == 0) @@ -920,7 +894,15 @@ rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t bufend = buf + numwords * wordsize; if (buf == bufend) { - sign *= 2; /* overflow if non-zero*/ + /* overflow if non-zero*/ + if (!overflow_2comp || 0 <= sign) + sign *= 2; + else { + if (de - dp == 1 && dp[0] == 1) + sign = -1; /* val == -1 == -2**(numwords*(wordsize*CHAR_BIT-nails)) */ + else + sign = -2; /* val < -1 == -2**(numwords*(wordsize*CHAR_BIT-nails)) */ + } } else if (dp == de) { memset(buf, '\0', bufend - buf); @@ -979,8 +961,28 @@ rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t wordp += word_step; } - if (dp != de || dd) - sign *= 2; /* overflow */ + FILL_DD; + /* overflow tests */ + if (dp != de || 1 < dd) { + /* 2**(numwords*(wordsize*CHAR_BIT-nails)+1) <= abs(val) */ + sign *= 2; + } + else if (dd == 1) { + /* 2**(numwords*(wordsize*CHAR_BIT-nails)) <= abs(val) < 2**(numwords*(wordsize*CHAR_BIT-nails)+1) */ + if (!overflow_2comp || 0 <= sign) + sign *= 2; + else { /* overflow_2comp && sign == -1 */ + /* test lower bits are all zero. */ + dp = ds; + while (dp < de && *dp == 0) + dp++; + if (de - dp == 1 && /* only one non-zero word. */ + (*dp & (*dp-1)) == 0) /* *dp contains only one bit set. */ + sign = -1; /* val == -2**(numwords*(wordsize*CHAR_BIT-nails)) */ + else + sign = -2; /* val < -2**(numwords*(wordsize*CHAR_BIT-nails)) */ + } + } } return sign; @@ -988,6 +990,119 @@ rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t #undef TAKE_LOWBITS } +/* + * Export an integer into a buffer. + * + * This function fills the buffer specified by _words_ and _numwords_ as + * abs(val) in the format specified by _wordsize_, _nails_ and _flags_. + * + * [val] Fixnum, Bignum or another integer like object which has to_int method. + * [words] buffer to export abs(val). + * [numwords] the size of given buffer as number of words. + * [wordsize] the size of word as number of bytes. + * [nails] number of padding bits in a word. + * Most significant nails bits of each word are filled by zero. + * [flags] bitwise or of constants which name starts "INTEGER_PACK_". + * It specifies word order and byte order. + * + * This function returns the signedness and overflow condition as follows: + * -2 : negative overflow. val <= -2**(numwords*(wordsize*CHAR_BIT-nails)) + * -1 : negative without overflow. -2**(numwords*(wordsize*CHAR_BIT-nails)) < val < 0 + * 0 : zero. val == 0 + * 1 : positive without overflow. 0 < val < 2**(numwords*(wordsize*CHAR_BIT-nails)) + * 2 : positive overflow. 2**(numwords*(wordsize*CHAR_BIT-nails)) <= val + * + * The least significant words of abs(val) are filled in the buffer when overflow occur. + */ + +int +rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t nails, int flags) +{ + return rb_integer_pack_internal(val, words, numwords, wordsize, nails, flags, 0); +} + +/* + * Export an integer into a buffer in 2's comlement representation. + * + * This function is similar to rb_integer_pack_2comp but + * the number is filled as 2's comlement representation and + * return value is bit different (because overflow condition + * is differnt between absolute value and 2's comlement). + * + * This function returns the signedness and overflow condition as follows: + * -2 : negative overflow. val < -2**(numwords*(wordsize*CHAR_BIT-nails)) + * -1 : negative without overflow. -2**(numwords*(wordsize*CHAR_BIT-nails)) <= val < 0 + * 0 : zero. val == 0 + * 1 : positive without overflow. 0 < val < 2**(numwords*(wordsize*CHAR_BIT-nails)) + * 2 : positive overflow. 2**(numwords*(wordsize*CHAR_BIT-nails)) <= val + * + * rb_integer_pack_2comp returns -1 for val == -2**(numwords*(wordsize*CHAR_BIT-nails)) but + * rb_integer_pack returns -2. + * + */ + +int +rb_integer_pack_2comp(VALUE val, void *words, size_t numwords, size_t wordsize, size_t nails, int flags) +{ + int sign; + + sign = rb_integer_pack_internal(val, words, numwords, wordsize, nails, flags, 1); + + if (sign < 0 && numwords != 0) { + unsigned char *buf; + + int word_num_partialbits; + size_t word_num_fullbytes; + + ssize_t word_step; + size_t byte_start; + int byte_step; + + size_t word_start, word_last; + unsigned char *wordp, *last_wordp; + + unsigned int partialbits_mask; + int carry; + + integer_pack_loop_setup(numwords, wordsize, nails, flags, + &word_num_fullbytes, &word_num_partialbits, + &word_start, &word_step, &word_last, &byte_start, &byte_step); + + partialbits_mask = (1 << word_num_partialbits) - 1; + + buf = words; + wordp = buf + word_start; + last_wordp = buf + word_last; + + carry = 1; + while (1) { + size_t index_in_word = 0; + unsigned char *bytep = wordp + byte_start; + while (index_in_word < word_num_fullbytes) { + carry += (unsigned char)~*bytep; + *bytep = (unsigned char)carry; + carry >>= CHAR_BIT; + bytep += byte_step; + index_in_word++; + } + if (word_num_partialbits) { + carry += (*bytep & partialbits_mask) ^ partialbits_mask; + *bytep = carry & partialbits_mask; + carry >>= word_num_partialbits; + bytep += byte_step; + index_in_word++; + } + + if (wordp == last_wordp) + break; + + wordp += word_step; + } + } + + return sign; +} + static size_t integer_unpack_num_bdigits_small(size_t numwords, size_t wordsize, size_t nails) { diff --git a/ext/-test-/bignum/pack.c b/ext/-test-/bignum/pack.c index 62f8f62c2d..6d646368d4 100644 --- a/ext/-test-/bignum/pack.c +++ b/ext/-test-/bignum/pack.c @@ -19,6 +19,24 @@ rb_integer_pack_m(VALUE val, VALUE buf, VALUE wordsize_arg, VALUE nails, VALUE f } static VALUE +rb_integer_pack_2comp_m(VALUE val, VALUE numwords_arg, VALUE wordsize_arg, VALUE nails, VALUE flags) +{ + int sign; + size_t numwords = NUM2SIZET(numwords_arg); + size_t wordsize = NUM2SIZET(wordsize_arg); + VALUE buf; + + if (numwords != 0 && wordsize != 0 && LONG_MAX / wordsize < numwords) + rb_raise(rb_eArgError, "too big numwords * wordsize"); + buf = rb_str_new(NULL, numwords * wordsize); + sign = rb_integer_pack_2comp(val, + RSTRING_PTR(buf), numwords, + wordsize, NUM2SIZET(nails), NUM2INT(flags)); + + return rb_assoc_new(INT2NUM(sign), buf); +} + +static VALUE rb_integer_unpack_m(VALUE klass, VALUE sign, VALUE buf, VALUE wordcount, VALUE wordsize, VALUE nails, VALUE flags) { StringValue(buf); @@ -32,6 +50,7 @@ void Init_pack(VALUE klass) { rb_define_method(rb_cInteger, "test_pack", rb_integer_pack_m, 4); + rb_define_method(rb_cInteger, "test_pack_2comp", rb_integer_pack_2comp_m, 4); rb_define_singleton_method(rb_cInteger, "test_unpack", rb_integer_unpack_m, 6); rb_define_const(rb_cInteger, "INTEGER_PACK_MSWORD_FIRST", INT2NUM(INTEGER_PACK_MSWORD_FIRST)); rb_define_const(rb_cInteger, "INTEGER_PACK_LSWORD_FIRST", INT2NUM(INTEGER_PACK_LSWORD_FIRST)); diff --git a/internal.h b/internal.h index 0a79802bc6..bcc6c58a31 100644 --- a/internal.h +++ b/internal.h @@ -449,6 +449,7 @@ VALUE rb_thread_io_blocking_region(rb_blocking_function_t *func, void *data1, in /* bignum.c */ int rb_integer_pack(VALUE val, void *words, size_t numwords, size_t wordsize, size_t nails, int flags); VALUE rb_integer_unpack(int sign, const void *words, size_t numwords, size_t wordsize, size_t nails, int flags); +int rb_integer_pack_2comp(VALUE val, void *words, size_t numwords, size_t wordsize, size_t nails, int flags); /* io.c */ void rb_maygvl_fd_fix_cloexec(int fd); @@ -23,35 +23,10 @@ #endif #define BIT_DIGITS(N) (((N)*146)/485 + 1) /* log2(10) =~ 146/485 */ -#define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT) -#define EXTENDSIGN(n, l) (((~0 << (n)) >> (((n)*(l)) % BITSPERDIG)) & ~(~0 << (n))) -static void fmt_setup(char*,size_t,int,int,int,int); - -static char* -remove_sign_bits(char *str, int base) -{ - char *t = str; - - if (base == 16) { - while (*t == 'f') { - t++; - } - } - else if (base == 8) { - *t |= EXTENDSIGN(3, strlen(t)); - while (*t == '7') { - t++; - } - } - else if (base == 2) { - while (*t == '1') { - t++; - } - } +extern const char ruby_digitmap[]; - return t; -} +static void fmt_setup(char*,size_t,int,int,int,int); static char sign_bits(int base, const char *p) @@ -758,6 +733,7 @@ rb_str_format(int argc, const VALUE *argv, VALUE fmt) case 'u': { volatile VALUE val = GETARG(); + int valsign; char fbuf[32], nbuf[64], *s; const char *prefix = 0; int sign = 0, dots = 0; @@ -835,96 +811,101 @@ rb_str_format(int argc, const VALUE *argv, VALUE fmt) base = 10; break; } - if (!bignum) { - if (base == 2) { - val = rb_int2big(v); - goto bin_retry; - } - if (sign) { - char c = *p; - if (c == 'i') c = 'd'; /* %d and %i are identical */ - if (v < 0) { - v = -v; - sc = '-'; - width--; - } - else if (flags & FPLUS) { - sc = '+'; - width--; - } - else if (flags & FSPACE) { - sc = ' '; - width--; - } - snprintf(fbuf, sizeof(fbuf), "%%l%c", c); - snprintf(nbuf, sizeof(nbuf), fbuf, v); - s = nbuf; - } - else { - s = nbuf; - if (v < 0) { - dots = 1; - } - snprintf(fbuf, sizeof(fbuf), "%%l%c", *p == 'X' ? 'x' : *p); - snprintf(++s, sizeof(nbuf) - 1, fbuf, v); - if (v < 0) { - char d = 0; - - s = remove_sign_bits(s, base); - switch (base) { - case 16: - d = 'f'; break; - case 8: - d = '7'; break; - } - if (d && *s != d) { - *--s = d; - } - } - } + if (base != 10) { + int numbits = ffs(base)-1; + size_t abs_nlz_bits; + size_t numdigits = rb_absint_numwords(val, numbits, &abs_nlz_bits); + long i; + if (INT_MAX-1 < numdigits) /* INT_MAX is used because rb_long2int is used later. */ + rb_raise(rb_eArgError, "size too big"); + if (sign) { + if (numdigits == 0) + numdigits = 1; + tmp = rb_str_new(NULL, numdigits); + valsign = rb_integer_pack(val, RSTRING_PTR(tmp), RSTRING_LEN(tmp), + 1, CHAR_BIT-numbits, INTEGER_PACK_BIG_ENDIAN); + for (i = 0; i < RSTRING_LEN(tmp); i++) + RSTRING_PTR(tmp)[i] = ruby_digitmap[((unsigned char *)RSTRING_PTR(tmp))[i]]; + s = RSTRING_PTR(tmp); + if (valsign < 0) { + sc = '-'; + width--; + } + else if (flags & FPLUS) { + sc = '+'; + width--; + } + else if (flags & FSPACE) { + sc = ' '; + width--; + } + } + else { + /* Following conditional "numdigits++" guarantees the + * most significant digit as + * - '1'(bin), '7'(oct) or 'f'(hex) for negative numbers + * - '0' for zero + * - not '0' for positive numbers. + * + * It also guarantees the most significant two + * digits will not be '11'(bin), '77'(oct), 'ff'(hex) + * or '00'. */ + if (numdigits == 0 || + ((abs_nlz_bits != (size_t)(numbits-1) || + !rb_absint_singlebit_p(val)) && + (!bignum ? v < 0 : RBIGNUM_NEGATIVE_P(val)))) + numdigits++; + tmp = rb_str_new(NULL, numdigits); + valsign = rb_integer_pack_2comp(val, RSTRING_PTR(tmp), RSTRING_LEN(tmp), + 1, CHAR_BIT-numbits, INTEGER_PACK_BIG_ENDIAN); + for (i = 0; i < RSTRING_LEN(tmp); i++) + RSTRING_PTR(tmp)[i] = ruby_digitmap[((unsigned char *)RSTRING_PTR(tmp))[i]]; + s = RSTRING_PTR(tmp); + dots = valsign < 0; + } + len = rb_long2int(RSTRING_END(tmp) - s); + } + else if (!bignum) { + char c = *p; + if (c == 'i') c = 'd'; /* %d and %i are identical */ + valsign = 1; + if (v < 0) { + v = -v; + sc = '-'; + width--; + valsign = -1; + } + else if (flags & FPLUS) { + sc = '+'; + width--; + } + else if (flags & FSPACE) { + sc = ' '; + width--; + } + snprintf(fbuf, sizeof(fbuf), "%%l%c", c); + snprintf(nbuf, sizeof(nbuf), fbuf, v); + s = nbuf; len = (int)strlen(s); } else { - if (sign) { - tmp = rb_big2str(val, base); - s = RSTRING_PTR(tmp); - if (s[0] == '-') { - s++; - sc = '-'; - width--; - } - else if (flags & FPLUS) { - sc = '+'; - width--; - } - else if (flags & FSPACE) { - sc = ' '; - width--; - } - } - else { - if (!RBIGNUM_SIGN(val)) { - val = rb_big_clone(val); - rb_big_2comp(val); - } - tmp = rb_big2str0(val, base, RBIGNUM_SIGN(val)); - s = RSTRING_PTR(tmp); - if (*s == '-') { - dots = 1; - if (base == 10) { - rb_warning("negative number for %%u specifier"); - } - s = remove_sign_bits(++s, base); - switch (base) { - case 16: - if (s[0] != 'f') *--s = 'f'; break; - case 8: - if (s[0] != '7') *--s = '7'; break; - case 2: - if (s[0] != '1') *--s = '1'; break; - } - } - } + tmp = rb_big2str(val, base); + s = RSTRING_PTR(tmp); + valsign = 1; + if (s[0] == '-') { + s++; + sc = '-'; + width--; + valsign = -1; + } + else if (flags & FPLUS) { + sc = '+'; + width--; + } + else if (flags & FSPACE) { + sc = ' '; + width--; + } len = rb_long2int(RSTRING_END(tmp) - s); } @@ -983,21 +964,15 @@ rb_str_format(int argc, const VALUE *argv, VALUE fmt) } CHECK(prec - len); if (dots) PUSH("..", 2); - if (!bignum && v < 0) { + if (!sign && valsign < 0) { char c = sign_bits(base, p); while (len < prec--) { buf[blen++] = c; } } else if ((flags & (FMINUS|FPREC)) != FMINUS) { - char c; - - if (!sign && bignum && !RBIGNUM_SIGN(val)) - c = sign_bits(base, p); - else - c = '0'; while (len < prec--) { - buf[blen++] = c; + buf[blen++] = '0'; } } PUSH(s, len); diff --git a/test/-ext-/bignum/test_pack.rb b/test/-ext-/bignum/test_pack.rb index 8b4f60d24d..32b891c84c 100644 --- a/test/-ext-/bignum/test_pack.rb +++ b/test/-ext-/bignum/test_pack.rb @@ -72,6 +72,50 @@ class TestBignum < Test::Unit::TestCase assert_equal([-1, "\x80\x70\x60\x50\x40\x30\x20\x10", 8], (-0x8070605040302010).test_pack("xxxxxxxx", 1, 0, BIG_ENDIAN)) end + def test_pack2comp_zero + assert_equal([0, ""], 0.test_pack_2comp(0, 1, 0, BIG_ENDIAN)) + end + + def test_pack2comp_emptybuf + assert_equal([-2, ""], (-3).test_pack_2comp(0, 1, 0, BIG_ENDIAN)) + assert_equal([-2, ""], (-2).test_pack_2comp(0, 1, 0, BIG_ENDIAN)) + assert_equal([-1, ""], (-1).test_pack_2comp(0, 1, 0, BIG_ENDIAN)) + assert_equal([ 0, ""], 0.test_pack_2comp(0, 1, 0, BIG_ENDIAN)) + assert_equal([+2, ""], 1.test_pack_2comp(0, 1, 0, BIG_ENDIAN)) + assert_equal([+2, ""], 2.test_pack_2comp(0, 1, 0, BIG_ENDIAN)) + end + + def test_pack2comp_nearly_zero + assert_equal([-1, "\xFE"], (-2).test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + assert_equal([-1, "\xFF"], (-1).test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + assert_equal([ 0, "\x00"], 0.test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + assert_equal([+1, "\x01"], 1.test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + assert_equal([+1, "\x02"], 2.test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + end + + def test_pack2comp_overflow + assert_equal([-2, "\xF"], (-0x11).test_pack_2comp(1, 1, 4, BIG_ENDIAN)) + assert_equal([-1, "\x0"], (-0x10).test_pack_2comp(1, 1, 4, BIG_ENDIAN)) + assert_equal([-1, "\x1"], (-0x0F).test_pack_2comp(1, 1, 4, BIG_ENDIAN)) + assert_equal([+1, "\xF"], (+0x0F).test_pack_2comp(1, 1, 4, BIG_ENDIAN)) + assert_equal([+2, "\x0"], (+0x10).test_pack_2comp(1, 1, 4, BIG_ENDIAN)) + assert_equal([+2, "\x1"], (+0x11).test_pack_2comp(1, 1, 4, BIG_ENDIAN)) + + assert_equal([-2, "\xFF"], (-0x101).test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + assert_equal([-1, "\x00"], (-0x100).test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + assert_equal([-1, "\x01"], (-0x0FF).test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + assert_equal([+1, "\xFF"], (+0x0FF).test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + assert_equal([+2, "\x00"], (+0x100).test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + assert_equal([+2, "\x01"], (+0x101).test_pack_2comp(1, 1, 0, BIG_ENDIAN)) + + assert_equal([-2, "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"], (-0x10000000000000001).test_pack_2comp(2, 4, 0, BIG_ENDIAN)) + assert_equal([-1, "\x00\x00\x00\x00\x00\x00\x00\x00"], (-0x10000000000000000).test_pack_2comp(2, 4, 0, BIG_ENDIAN)) + assert_equal([-1, "\x00\x00\x00\x00\x00\x00\x00\x01"], (-0x0FFFFFFFFFFFFFFFF).test_pack_2comp(2, 4, 0, BIG_ENDIAN)) + assert_equal([+1, "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"], (+0x0FFFFFFFFFFFFFFFF).test_pack_2comp(2, 4, 0, BIG_ENDIAN)) + assert_equal([+2, "\x00\x00\x00\x00\x00\x00\x00\x00"], (+0x10000000000000000).test_pack_2comp(2, 4, 0, BIG_ENDIAN)) + assert_equal([+2, "\x00\x00\x00\x00\x00\x00\x00\x01"], (+0x10000000000000001).test_pack_2comp(2, 4, 0, BIG_ENDIAN)) + end + def test_unpack_zero assert_equal(0, Integer.test_unpack(0, "", 0, 1, 0, BIG_ENDIAN)) end |