Repository: randombit/botan
Pull request #2768 (2021-06-30 21:29:31)

Improve BigInt::to_dec_string performance
On 64-bit platforms this is 8-10x faster than before. Not coincidentally, we are converting 19 digits per division now, vs 2 before, and 19/2 = 9.5x


Patch:
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index 55e544b26..b52597fa5 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -1423,7 +1423,7 @@ class Speed final : public Command
 
             const auto ten = Botan::BigInt::from_word(10);
             Botan::BigInt q1, r1, q2;
-            uint8_t r2;
+            Botan::word r2;
 
             while(ct_div_timer->under(runtime_per_size))
                {
@@ -1434,7 +1434,7 @@ class Speed final : public Command
                div_timer->stop();
 
                ct_div_timer->start();
-               Botan::ct_divide_u8(x, 10, q2, r2);
+               Botan::ct_divide_word(x, 10, q2, r2);
                ct_div_timer->stop();
 
                BOTAN_ASSERT_EQUAL(q1, q2, "Quotient ok");
diff --git a/src/fuzzer/divide.cpp b/src/fuzzer/divide.cpp
index 2281af108..e1a41eff2 100644
--- a/src/fuzzer/divide.cpp
+++ b/src/fuzzer/divide.cpp
@@ -1,5 +1,5 @@
 /*
-* (C) 2015,2016,2018 Jack Lloyd
+* (C) 2015,2016,2018,2021 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -8,14 +8,14 @@
 
 void fuzz(const uint8_t in[], size_t len)
    {
-   if(len % 2 == 1 || len > 2*4096/8)
+   if(len > 2*4096/8)
       return;
 
    // Save on allocations by making these static
    static Botan::BigInt x, y, q, r, ct_q, ct_r, z;
 
    x = Botan::BigInt::decode(in, len / 2);
-   y = Botan::BigInt::decode(in + len / 2, len / 2);
+   y = Botan::BigInt::decode(in + len / 2, len - (len / 2));
 
    if(y == 0)
       return;
@@ -33,20 +33,22 @@ void fuzz(const uint8_t in[], size_t len)
    FUZZER_ASSERT_EQUAL(q, ct_q);
    FUZZER_ASSERT_EQUAL(r, ct_r);
 
-   // Now divide by just low byte of y
+   // Now divide by just low word of y
 
-   y = y.byte_at(0);
+   y = y.word_at(0);
    if(y == 0)
-      y = 251;
+      return;
+
    Botan::vartime_divide(x, y, q, r);
 
+   FUZZER_ASSERT_TRUE(r < y);
    z = q*y + r;
    FUZZER_ASSERT_EQUAL(z, x);
 
-   uint8_t r8;
-   Botan::ct_divide_u8(x, y.byte_at(0), ct_q, r8);
+   Botan::word rw;
+   Botan::ct_divide_word(x, y.word_at(0), ct_q, rw);
    FUZZER_ASSERT_EQUAL(ct_q, q);
-   FUZZER_ASSERT_EQUAL(r8, r.byte_at(0));
+   FUZZER_ASSERT_EQUAL(rw, r.word_at(0));
 
    }
 
diff --git a/src/lib/codec/base58/base58.cpp b/src/lib/codec/base58/base58.cpp
index 5cce30014..8e5aec3d6 100644
--- a/src/lib/codec/base58/base58.cpp
+++ b/src/lib/codec/base58/base58.cpp
@@ -62,16 +62,16 @@ char lookup_base58_char(uint8_t x)
 
 std::string base58_encode(BigInt v, size_t leading_zeros)
    {
-   const uint8_t radix = 58;
+   const word radix = 58;
 
    std::string result;
    BigInt q;
 
    while(v.is_nonzero())
       {
-      uint8_t r;
-      ct_divide_u8(v, radix, q, r);
-      result.push_back(lookup_base58_char(r));
+      word r;
+      ct_divide_word(v, radix, q, r);
+      result.push_back(lookup_base58_char(static_cast<uint8_t>(r)));
       v.swap(q);
       }
 
diff --git a/src/lib/math/bigint/big_code.cpp b/src/lib/math/bigint/big_code.cpp
index ee4aaef0e..f908e92ab 100644
--- a/src/lib/math/bigint/big_code.cpp
+++ b/src/lib/math/bigint/big_code.cpp
@@ -1,6 +1,6 @@
 /*
 * BigInt Encoding/Decoding
-* (C) 1999-2010,2012,2019 Jack Lloyd
+* (C) 1999-2010,2012,2019,2021 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -13,35 +13,70 @@ namespace Botan {
 
 std::string BigInt::to_dec_string() const
    {
-   BigInt copy = *this;
-   copy.set_sign(Positive);
+   // Use the largest power of 10 that fits in a word
+#if (BOTAN_MP_WORD_BITS == 64)
+   const word conversion_radix = 10000000000000000000U;
+   const word radix_digits = 19;
+#else
+   const word conversion_radix = 1000000000U;
+   const word radix_digits = 9;
+#endif
 
-   uint8_t remainder;
-   secure_vector<uint8_t> digits;
+   // (over-)estimate of the number of digits needed; log2(10) ~ 3.3219
+   const size_t digit_estimate = static_cast<size_t>(1 + (this->bits() / 3.32));
 
-   // (over-)estimate of the number of digits, log2(10) ~= 3.32
-   digits.reserve(static_cast<size_t>(3.4 * this->bits()));
+   // (over-)estimate of db such that conversion_radix^db > *this
+   const size_t digit_blocks = (digit_estimate + radix_digits - 1) / radix_digits;
 
-   while(copy > 0)
+   BigInt value = *this;
+   value.set_sign(Positive);
+
+   // Extract groups of digits into words
+   std::vector<word> digit_groups(digit_blocks);
+
+   for(size_t i = 0; i != digit_blocks; ++i)
       {
-      ct_divide_u8(copy, 100, copy, remainder);
+      word remainder = 0;
+      ct_divide_word(value, conversion_radix, value, remainder);
+      digit_groups[i] = remainder;
+      }
 
-      const uint8_t ld = remainder % 10;
-      const uint8_t td = (remainder - ld) / 10;
-      digits.push_back(ld);
+   BOTAN_ASSERT_NOMSG(value.is_zero());
 
-      if(copy > 0 || td > 0)
-         digits.push_back(td);
+   // Extract digits from the groups
+   std::vector<uint8_t> digits(digit_blocks * radix_digits);
+
+   for(size_t i = 0; i != digit_blocks; ++i)
+      {
+      word remainder = digit_groups[i];
+      for(size_t j = 0; j != radix_digits; ++j)
+         {
+         // Compiler should convert div/mod by 10 into mul by magic constant
+         const word digit = remainder % 10;
+         remainder /= 10;
+         digits[radix_digits*i + j] = static_cast<uint8_t>(digit);
+         }
       }
 
+   // remove leading zeros
+   while(digits.size() > 0 && digits.back() == 0)
+      {
+      digits.pop_back();
+      }
+
+   BOTAN_ASSERT_NOMSG(digit_estimate >= digits.size());
+
+   // Reverse the digits to big-endian and format to text
    std::string s;
+   s.reserve(1 + digits.size());
 
    if(is_negative())
       s += "-";
 
+   // Reverse and convert to textual digits
    for(auto i = digits.rbegin(); i != digits.rend(); ++i)
       {
-      s.push_back(*i + '0');
+      s.push_back(*i + '0'); // assumes ASCII
       }
 
    if(s.empty())
@@ -136,6 +171,7 @@ BigInt BigInt::decode(const uint8_t buf[], size_t length, Base base)
       }
    else if(base == Decimal)
       {
+      // This could be made faster using the same trick as to_dec_string
       for(size_t i = 0; i != length; ++i)
          {
          const char c = buf[i];
diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp
index 43a722ee8..3cb6f0d7e 100644
--- a/src/lib/math/bigint/big_ops3.cpp
+++ b/src/lib/math/bigint/big_ops3.cpp
@@ -111,20 +111,10 @@ BigInt operator/(const BigInt& x, word y)
    {
    if(y == 0)
       throw Invalid_Argument("BigInt::operator/ divide by zero");
-   else if(y == 1)
-      return x;
-   else if(y == 2)
-      return (x >> 1);
-   else if(y <= 255)
-      {
-      BigInt q;
-      uint8_t r;
-      ct_divide_u8(x, static_cast<uint8_t>(y), q, r);
-      return q;
-      }
 
-   BigInt q, r;
-   vartime_divide_word(x, y, q, r);
+   BigInt q;
+   word r;
+   ct_divide_word(x, y, q, r);
    return q;
    }
 
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 3856ac1fe..510a3db4a 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -277,16 +277,6 @@ uint32_t BigInt::to_u32bit() const
    return out;
    }
 
-/*
-* Set bit number n
-*/
-void BigInt::conditionally_set_bit(size_t n, bool set_it)
-   {
-   const size_t which = n / BOTAN_MP_WORD_BITS;
-   const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
-   m_data.set_word_at(which, word_at(which) | mask);
-   }
-
 /*
 * Clear bit number n
 */
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 352a4a0d0..cd7195e73 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -449,7 +449,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * @param n bit position to set
      * @param set_it if the bit should be set
      */
-     void conditionally_set_bit(size_t n, bool set_it);
+     void conditionally_set_bit(size_t n, bool set_it)
+        {
+        const size_t which = n / BOTAN_MP_WORD_BITS;
+        const word mask = static_cast<word>(set_it) << (n % BOTAN_MP_WORD_BITS);
+        m_data.set_word_at(which, word_at(which) | mask);
+        }
 
      /**
      * Clear bit at specified position
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index 7b7184c0b..0611b9ba0 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -1,6 +1,6 @@
 /*
-* Division Algorithm
-* (C) 1999-2007,2012,2018 Jack Lloyd
+* Division Algorithms
+* (C) 1999-2007,2012,2018,2021 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -50,6 +50,9 @@ inline bool division_check(word q, word y2, word y1,
 
 void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
    {
+   if(y.is_zero())
+      throw Invalid_Argument("ct_divide: cannot divide by zero");
+
    const size_t x_words = x.sig_words();
    const size_t y_words = y.sig_words();
 
@@ -78,24 +81,28 @@ void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out)
    q_out = q;
    }
 
-void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
+void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out)
    {
+   if(y == 0)
+      throw Invalid_Argument("ct_divide_word: cannot divide by zero");
+
    const size_t x_words = x.sig_words();
    const size_t x_bits = x.bits();
 
    BigInt q = BigInt::with_capacity(x_words);
-   uint32_t r = 0;
+   word r = 0;
 
    for(size_t i = 0; i != x_bits; ++i)
       {
       const size_t b = x_bits - 1 - i;
       const bool x_b = x.get_bit(b);
 
+      const auto r_carry = CT::Mask<word>::expand(r >> (BOTAN_MP_WORD_BITS - 1));
+
       r *= 2;
       r += x_b;
 
-      const auto r_gte_y = CT::Mask<uint32_t>::is_gte(r, y);
-
+      const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry;
       q.conditionally_set_bit(b, r_gte_y.is_set());
       r = r_gte_y.select(r - y, r);
       }
@@ -110,7 +117,7 @@ void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out)
          }
       }
 
-   r_out = static_cast<uint8_t>(r);
+   r_out = r;
    q_out = q;
    }
 
@@ -150,17 +157,6 @@ BigInt ct_modulo(const BigInt& x, const BigInt& y)
    return r;
    }
 
-void vartime_divide_word(const BigInt& x, const word y, BigInt& q_out, BigInt& r_out)
-   {
-   if(y == 0)
-      throw Invalid_Argument("vartime_divide_word: cannot divide by zero");
-
-   // It might be worthwhile to specialize vartime_divide for y with 1 word
-
-   // until then:
-   vartime_divide(x, BigInt::from_word(y), q_out, r_out);
-   }
-
 /*
 * Solve x = q * y + r
 *
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index 26468bda1..1b6dcdfb8 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -25,19 +25,6 @@ void vartime_divide(const BigInt& x,
                     BigInt& q,
                     BigInt& r);
 
-/**
-* BigInt/word Division
-* @param x an integer
-* @param y a non-zero integer
-* @param q will be set to x / y
-* @param r will be set to x % y
-*/
-BOTAN_TEST_API
-void vartime_divide_word(const BigInt& x,
-                         word y,
-                         BigInt& q,
-                         BigInt& r);
-
 /**
 * BigInt division, const time variant
 *
@@ -76,7 +63,7 @@ inline BigInt ct_divide(const BigInt& x, const BigInt& y)
 * BigInt division, const time variant
 *
 * This runs with control flow independent of the values of x/y.
-* Warning: the loop bounds still leak the sizes of x and y.
+* Warning: the loop bounds still leaks the size of x.
 *
 * @param x an integer
 * @param y a non-zero integer
@@ -84,10 +71,10 @@ inline BigInt ct_divide(const BigInt& x, const BigInt& y)
 * @param r will be set to x % y
 */
 BOTAN_TEST_API
-void ct_divide_u8(const BigInt& x,
-                  uint8_t y,
-                  BigInt& q,
-                  uint8_t& r);
+void ct_divide_word(const BigInt& x,
+                    word y,
+                    BigInt& q,
+                    word& r);
 
 /**
 * BigInt modulo, const time variant


Test patch:
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 459263b47..fc04ce3fa 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -390,19 +390,22 @@ class BigInt_Div_Test final : public Text_Based_Test
          e /= b;
          result.test_eq("a /= b", e, c);
 
-         if(b.bytes() == 1)
+         if(b.sig_words() == 1)
             {
-            const uint8_t b8 = b.byte_at(0);
+            const Botan::word bw = b.word_at(0);
+            result.test_eq("bw ok", Botan::BigInt::from_word(bw), b);
 
             Botan::BigInt ct_q;
-            uint8_t ct_r;
-            Botan::ct_divide_u8(a, b8, ct_q, ct_r);
-            result.test_eq("ct_divide_u8 q", ct_q, c);
+            Botan::word ct_r;
+            Botan::ct_divide_word(a, bw, ct_q, ct_r);
+            result.test_eq("ct_divide_word q", ct_q, c);
+            result.test_eq("ct_divide_word r", ct_q * b + ct_r, a);
             }
 
          Botan::BigInt ct_q, ct_r;
          Botan::ct_divide(a, b, ct_q, ct_r);
          result.test_eq("ct_divide q", ct_q, c);
+         result.test_eq("ct_divide r", ct_q * b + ct_r, a);
 
          return result;
          }
@@ -442,13 +445,10 @@ class BigInt_Mod_Test final : public Text_Based_Test
             result.test_eq("a %= b (as word)", e, expected);
 
             result.test_eq("a % b (as word)", a % b_word, expected);
-            }
 
-         if(b.bytes() == 1)
-            {
             Botan::BigInt ct_q;
-            Botan::uint8_t ct_r;
-            Botan::ct_divide_u8(a, b.byte_at(0), ct_q, ct_r);
+            Botan::word ct_r;
+            Botan::ct_divide_word(a, b.word_at(0), ct_q, ct_r);
             result.test_eq("ct_divide_u8 r", ct_r, expected);
             }