* 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

1 files changed, 101 insertions, 25 deletions

diff --git a/bignum.c b/bignum.c
index cbdfa3a6a2..3824efadb5 100644
--- a/bignum.c
+++ b/bignum.c
@@ -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;
 }