ruby-changes:29147
From: akr <ko1@a...>
Date: Mon, 10 Jun 2013 01:09:06 +0900 (JST)
Subject: [ruby-changes:29147] akr:r41199 (trunk): * bignum.c (absint_numwords_bytes): New function.
akr 2013-06-10 01:08:54 +0900 (Mon, 10 Jun 2013) New Revision: 41199 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=41199 Log: * bignum.c (absint_numwords_bytes): New function. (absint_numwords_generic): Extracted from rb_absint_numwords. (rb_absint_numwords): Use absint_numwords_bytes if possible. Modified files: trunk/ChangeLog trunk/bignum.c Index: ChangeLog =================================================================== --- ChangeLog (revision 41198) +++ ChangeLog (revision 41199) @@ -1,3 +1,9 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Mon Jun 10 01:07:57 2013 Tanaka Akira <akr@f...> + + * bignum.c (absint_numwords_bytes): New function. + (absint_numwords_generic): Extracted from rb_absint_numwords. + (rb_absint_numwords): Use absint_numwords_bytes if possible. + Sun Jun 9 21:33:15 2013 Tanaka Akira <akr@f...> * bignum.c (rb_absint_numwords): Return (size_t)-1 when overflow. Index: bignum.c =================================================================== --- bignum.c (revision 41198) +++ bignum.c (revision 41199) @@ -516,38 +516,63 @@ rb_absint_size(VALUE val, int *nlz_bits_ https://github.com/ruby/ruby/blob/trunk/bignum.c#L516 return (de - dp) * SIZEOF_BDIGITS - num_leading_zeros / CHAR_BIT; } -/* - * Calculate a number of words to be required to represent - * the absolute value of the integer given as _val_. - * - * [val] an integer. - * [word_numbits] number of bits in a word. - * [nlz_bits_ret] number of leading zero bits in the most significant word is returned if not NULL. - * - * This function returns ((val_numbits * CHAR_BIT + word_numbits - 1) / word_numbits) - * where val_numbits is the number of bits of abs(val). - * If it overflows, (size_t)-1 is returned. - * - * If nlz_bits_ret is not NULL and overflow is not occur, - * (return_value * word_numbits - val_numbits) is stored in *nlz_bits_ret. - * In this case, 0 <= *nlz_bits_ret < word_numbits. - * - */ size_t -rb_absint_numwords(VALUE val, size_t word_numbits, size_t *nlz_bits_ret) +absint_numwords_bytes(size_t numbytes, int nlz_bits_in_msbyte, size_t word_numbits, size_t *nlz_bits_ret) { - size_t numbytes; + /* + * word_numbytes = word_numbits / CHAR_BIT + * div, mod = val_numbits.divmod(word_numbits) + * + * q, r = numbytes.divmod(word_numbytes) + * s = q if r * CHAR_BIT >= nlz_bits_in_msbyte + * = q - 1 if otherwise + * t = r * CHAR_BIT - nlz_bits_in_msbyte if r * CHAR_BIT >= nlz_bits_in_msbyte + * = word_numbits + r * CHAR_BIT - nlz_bits_in_msbyte if otherwise + * + * div = (numbytes * CHAR_BIT - nlz_bits_in_msbyte) / word_numbits + * = ((q * word_numbytes + r) * CHAR_BIT - nlz_bits_in_msbyte) / word_numbits + * = (q * word_numbytes * CHAR_BIT + r * CHAR_BIT - nlz_bits_in_msbyte) / word_numbits + * = q + (r * CHAR_BIT - nlz_bits_in_msbyte) / word_numbits if r * CHAR_BIT >= nlz_bits_in_msbyte + * q - 1 + (word_numbits + r * CHAR_BIT - nlz_bits_in_msbyte) / word_numbits if r * CHAR_BIT < nlz_bits_in_msbyte + * = s + t / word_numbits + * mod = (r * CHAR_BIT - nlz_bits_in_msbyte) % word_numbits if r * CHAR_BIT >= nlz_bits_in_msbyte + * (word_numbits + r * CHAR_BIT - nlz_bits_in_msbyte) % word_numbits if r * CHAR_BIT < nlz_bits_in_msbyte + * = t % word_numbits + * + * numwords = mod == 0 ? div : div + 1 + * nlz_bits = mod == 0 ? 0 : word_numbits - mod + */ + size_t word_numbytes = word_numbits / CHAR_BIT; + size_t q = numbytes / word_numbytes; + size_t r = numbytes % word_numbytes; + size_t s, t; + size_t div, mod; size_t numwords; size_t nlz_bits; - int nlz_bits_in_msbyte; + if (r * CHAR_BIT >= (size_t)nlz_bits_in_msbyte) { + s = q; + t = r * CHAR_BIT - nlz_bits_in_msbyte; + } + else { + s = q - 1; + t = word_numbits + r * CHAR_BIT - nlz_bits_in_msbyte; + } + div = s + t / word_numbits; + mod = t % word_numbits; + numwords = mod == 0 ? div : div + 1; + nlz_bits = mod == 0 ? 0 : word_numbits - mod; + *nlz_bits_ret = nlz_bits; + return numwords; +} + +size_t +absint_numwords_generic(size_t numbytes, int nlz_bits_in_msbyte, size_t word_numbits, size_t *nlz_bits_ret) +{ VALUE val_numbits, word_numbits_v; VALUE div_mod, div, mod; int sign; - - if (word_numbits == 0) - return (size_t)-1; - - numbytes = rb_absint_size(val, &nlz_bits_in_msbyte); + size_t numwords; + size_t nlz_bits; /* * val_numbits = numbytes * CHAR_BIT - nlz_bits_in_msbyte @@ -555,6 +580,7 @@ rb_absint_numwords(VALUE val, size_t wor https://github.com/ruby/ruby/blob/trunk/bignum.c#L580 * numwords = mod == 0 ? div : div + 1 * nlz_bits = mod == 0 ? 0 : word_numbits - mod */ + val_numbits = SIZET2NUM(numbytes); val_numbits = rb_funcall(val_numbits, '*', 1, LONG2FIX(CHAR_BIT)); if (nlz_bits_in_msbyte) @@ -574,8 +600,58 @@ rb_absint_numwords(VALUE val, size_t wor https://github.com/ruby/ruby/blob/trunk/bignum.c#L600 INTEGER_PACK_MSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER); if (sign == 2) return (size_t)-1; + *nlz_bits_ret = nlz_bits; + return numwords; +} + +/* + * Calculate a number of words to be required to represent + * the absolute value of the integer given as _val_. + * + * [val] an integer. + * [word_numbits] number of bits in a word. + * [nlz_bits_ret] number of leading zero bits in the most significant word is returned if not NULL. + * + * This function returns ((val_numbits * CHAR_BIT + word_numbits - 1) / word_numbits) + * where val_numbits is the number of bits of abs(val). + * If it overflows, (size_t)-1 is returned. + * + * If nlz_bits_ret is not NULL and overflow is not occur, + * (return_value * word_numbits - val_numbits) is stored in *nlz_bits_ret. + * In this case, 0 <= *nlz_bits_ret < word_numbits. + * + */ +size_t +rb_absint_numwords(VALUE val, size_t word_numbits, size_t *nlz_bits_ret) +{ + size_t numbytes; + int nlz_bits_in_msbyte; + size_t numwords; + size_t nlz_bits; + + if (word_numbits == 0) + return (size_t)-1; + + numbytes = rb_absint_size(val, &nlz_bits_in_msbyte); + + if (word_numbits % CHAR_BIT == 0) { + numwords = absint_numwords_bytes(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits); +#if 0 + 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); +#endif + } + else { + numwords = absint_numwords_generic(numbytes, nlz_bits_in_msbyte, word_numbits, &nlz_bits); + } + if (numwords == (size_t)-1) + return numwords; + if (nlz_bits_ret) *nlz_bits_ret = nlz_bits; + return numwords; } -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/