diff options
author | akr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-06-09 16:08:54 +0000 |
---|---|---|
committer | akr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-06-09 16:08:54 +0000 |
commit | f30d662c24a7f799b67cc5f99470ce9da39b89cf (patch) | |
tree | b01e8d186fda40b266571c1f8bb4fcc2d1994fc1 /bignum.c | |
parent | d395be138c0661c38f903017c365a30c561c8548 (diff) | |
download | ruby-f30d662c24a7f799b67cc5f99470ce9da39b89cf.tar.gz |
* bignum.c (absint_numwords_bytes): New function.
(absint_numwords_generic): Extracted from rb_absint_numwords.
(rb_absint_numwords): Use absint_numwords_bytes if possible.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@41199 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'bignum.c')
-rw-r--r-- | bignum.c | 126 |
1 files changed, 101 insertions, 25 deletions
@@ -516,38 +516,63 @@ rb_absint_size(VALUE val, int *nlz_bits_ret) 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 word_numbits, size_t *nlz_bits_ret) * 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 word_numbits, size_t *nlz_bits_ret) 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; } |