Add a constant time divide variant for dividing by uint8_t

Originally wrote it for div-by-word but that ends up requiring a dword
type which we don't always have. And uint8_t covers the most important
cases of n = 10 and n = 58 (whenever I get around to writing base58).
We could portably support up to div-by-uint32, but I don't think we need it.

Nicely for n = 10, this is actually faster than the variable time division.

3 files changed, 59 insertions, 7 deletions

diff --git a/src/lib/math/bigint/big_code.cpp b/src/lib/math/bigint/big_code.cpp
index 8fd528a14..6d8c61fd5 100644
--- a/src/lib/math/bigint/big_code.cpp
+++ b/src/lib/math/bigint/big_code.cpp
@@ -17,13 +17,13 @@ std::string BigInt::to_dec_string() const
    BigInt copy = *this;
    copy.set_sign(Positive);
 
-   BigInt remainder;
+   uint8_t remainder;
    std::vector<uint8_t> digits;
 
    while(copy > 0)
       {
-      divide(copy, 10, copy, remainder);
-      digits.push_back(static_cast<uint8_t>(remainder.word_at(0)));
+      ct_divide_u8(copy, 10, copy, remainder);
+      digits.push_back(remainder);
       }
 
    std::string s;
@@ -68,14 +68,13 @@ void BigInt::encode(uint8_t output[], const BigInt& n, Base base)
    else if(base == Decimal)
       {
       BigInt copy = n;
-      BigInt remainder;
+      uint8_t remainder;
       copy.set_sign(Positive);
       const size_t output_size = n.encoded_size(Decimal);
       for(size_t j = 0; j != output_size; ++j)
          {
-         divide(copy, 10, copy, remainder);
-         output[output_size - 1 - j] =
-            Charset::digit2char(static_cast<uint8_t>(remainder.word_at(0)));
+         ct_divide_u8(copy, 10, copy, remainder);
+         output[output_size - 1 - j] = Charset::digit2char(remainder);
          if(copy.is_zero())
             break;
          }
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index 64d1537ba..c2e89a724 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -83,6 +83,43 @@ 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)
+   {
+   const size_t x_words = x.sig_words();
+   const size_t x_bits = x.bits();
+   const size_t y_words = 1;
+
+   BigInt q(BigInt::Positive, x_words);
+   uint32_t 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);
+
+      r *= 2;
+      r += x_b;
+
+      const auto r_gte_y = CT::Mask<uint32_t>::is_gte(r, y);
+
+      q.conditionally_set_bit(b, r_gte_y.is_set());
+      r = r_gte_y.select(r - y, r);
+      }
+
+   if(x.sign() == BigInt::Negative)
+      {
+      q.flip_sign();
+      if(r != 0)
+         {
+         --q;
+         r = y - r;
+         }
+      }
+
+   r_out = static_cast<uint8_t>(r);
+   q_out = q;
+   }
+
 /*
 * Solve x = q * y + r
 */
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index d7d72e200..d83f4b695 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -40,6 +40,22 @@ void BOTAN_PUBLIC_API(2,9) ct_divide(const BigInt& x,
                                      BigInt& q,
                                      BigInt& r);
 
+/**
+* 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.
+*
+* @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
+*/
+void BOTAN_PUBLIC_API(2,9) ct_divide_u8(const BigInt& x,
+                                        uint8_t y,
+                                        BigInt& q,
+                                        uint8_t& r);
+
 }
 
 #endif