Simplify BigInt addition and subtraction

Addition already has to handle negative numbers so make it do
double duty for subtraction.

6 files changed, 175 insertions, 187 deletions

diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
index 68baf3200..6ce14f8f1 100644
--- a/src/lib/math/bigint/big_ops2.cpp
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -12,103 +12,41 @@
 
 namespace Botan {
 
-BigInt& BigInt::add(const word y[], size_t y_sw, Sign y_sign)
+BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign)
    {
    const size_t x_sw = sig_words();
 
+   grow_to(std::max(x_sw, y_words) + 1);
+
    if(sign() == y_sign)
       {
-      const size_t reg_size = std::max(x_sw, y_sw) + 1;
-
-      if(size() < reg_size)
-         grow_to(reg_size);
-
-      bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
+      bigint_add2(mutable_data(), size() - 1, y, y_words);
       }
    else
       {
-      const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw);
+      const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words);
 
-      if(relative_size < 0)
+      if(relative_size >= 0)
          {
-         const size_t reg_size = std::max(x_sw, y_sw);
-         grow_to(reg_size);
-         bigint_sub2_rev(mutable_data(), y, y_sw);
-         set_sign(y_sign);
-         }
-      else if(relative_size == 0)
-         {
-         this->clear();
-         set_sign(Positive);
+         // *this >= y
+         bigint_sub2(mutable_data(), x_sw, y, y_words);
          }
-      else if(relative_size > 0)
+      else
          {
-         bigint_sub2(mutable_data(), x_sw, y, y_sw);
+         // *this < y
+         bigint_sub2_rev(mutable_data(), y, y_words);
          }
-      }
-
-   return (*this);
-   }
-
-BigInt& BigInt::operator+=(const BigInt& y)
-   {
-   return add(y.data(), y.sig_words(), y.sign());
-   }
 
-BigInt& BigInt::operator+=(word y)
-   {
-   return add(&y, 1, Positive);
-   }
-
-BigInt& BigInt::sub(const word y[], size_t y_sw, Sign y_sign)
-   {
-   const size_t x_sw = sig_words();
-
-   int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw);
-
-   const size_t reg_size = std::max(x_sw, y_sw) + 1;
-   grow_to(reg_size);
-
-   if(relative_size < 0)
-      {
-      if(sign() == y_sign)
-         bigint_sub2_rev(mutable_data(), y, y_sw);
-      else
-         bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
-
-      set_sign(y_sign == Positive ? Negative : Positive);
-      }
-   else if(relative_size == 0)
-      {
-      if(sign() == y_sign)
-         {
-         clear();
+      //this->sign_fixup(relative_size, y_sign);
+      if(relative_size < 0)
+         set_sign(y_sign);
+      else if(relative_size == 0)
          set_sign(Positive);
-         }
-      else
-         bigint_shl1(mutable_data(), x_sw, 0, 1);
-      }
-   else if(relative_size > 0)
-      {
-      if(sign() == y_sign)
-         bigint_sub2(mutable_data(), x_sw, y, y_sw);
-      else
-         bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
       }
 
    return (*this);
    }
 
-BigInt& BigInt::operator-=(const BigInt& y)
-   {
-   return sub(y.data(), y.sig_words(), y.sign());
-   }
-
-BigInt& BigInt::operator-=(word y)
-   {
-   return sub(&y, 1, Positive);
-   }
-
 BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws)
    {
    if(this->is_negative() || s.is_negative() || mod.is_negative())
@@ -170,45 +108,54 @@ BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>&
    if(ws.size() < mod_sw)
       ws.resize(mod_sw);
 
+#if 0
+   //Faster but not const time:
+
+   // Compute t - s
+   word borrow = bigint_sub3(ws.data(), data(), mod_sw, s.data(), mod_sw);
+
+   if(borrow)
+      {
+      // If t < s, instead compute p - (s - t)
+      bigint_sub2_rev(mutable_data(), s.data(), mod_sw);
+      bigint_sub2_rev(mutable_data(), mod.data(), mod_sw);
+      }
+   else
+      {
+      // No borrow so we already have the result we need
+      swap_reg(ws);
+      }
+#else
    // is t < s or not?
    const auto is_lt = bigint_ct_is_lt(data(), mod_sw, s.data(), mod_sw);
 
    // ws = p - s
-   word borrow = bigint_sub3(ws.data(), mod.data(), mod_sw, s.data(), mod_sw);
-   CT::unpoison(borrow);
-   BOTAN_ASSERT_NOMSG(borrow == 0);
+   const word borrow = bigint_sub3(ws.data(), mod.data(), mod_sw, s.data(), mod_sw);
 
    // Compute either (t - s) or (t + (p - s)) depending on mask
-   word carry = bigint_cnd_addsub(is_lt, mutable_data(), ws.data(), s.data(), mod_sw);
-   CT::unpoison(carry);
-   BOTAN_ASSERT_NOMSG(carry == 0);
+   const word carry = bigint_cnd_addsub(is_lt, mutable_data(), ws.data(), s.data(), mod_sw);
+
+   BOTAN_DEBUG_ASSERT(borrow == 0 && carry == 0);
+   BOTAN_UNUSED(carry, borrow);
+#endif
 
    return (*this);
    }
 
 BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws)
    {
-   /*
-   *this = BigInt(y, y_sw) - *this;
-   return *this;
-   */
    if(this->sign() != BigInt::Positive)
       throw Invalid_State("BigInt::sub_rev requires this is positive");
 
    const size_t x_sw = this->sig_words();
 
-   // TODO use bigint_sub_abs or a new variant of it
-
-   ws.resize(std::max(y_sw, x_sw) + 1);
+   ws.resize(std::max(x_sw, y_sw));
    clear_mem(ws.data(), ws.size());
 
-   word borrow = bigint_sub3(ws.data(), y, y_sw, this->data(), x_sw);
+   const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);
 
-   if(borrow)
-      {
-      bigint_sub3(ws.data(), this->data(), x_sw, y, y_sw);
+   if(relative_size > 0)
       this->flip_sign();
-      }
 
    this->swap_reg(ws);
 
@@ -380,10 +327,10 @@ BigInt& BigInt::operator>>=(size_t shift)
    {
    if(shift)
       {
-      const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
-                   shift_bits  = shift % BOTAN_MP_WORD_BITS;
-
+      const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
+      const size_t shift_bits  = shift % BOTAN_MP_WORD_BITS;
       const size_t sw = sig_words();
+
       bigint_shr1(m_data.mutable_data(), sw, shift_words, shift_bits);
 
       if(is_negative() && is_zero())
diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp
index 3f34e0bf1..a38448050 100644
--- a/src/lib/math/bigint/big_ops3.cpp
+++ b/src/lib/math/bigint/big_ops3.cpp
@@ -1,6 +1,6 @@
 /*
 * BigInt Binary Operators
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2007,2018 Jack Lloyd
 *     2016 Matthias Gierlings
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -14,95 +14,38 @@
 
 namespace Botan {
 
-namespace {
-
-BigInt bigint_add(const BigInt& x, const word y[], size_t y_sw, BigInt::Sign y_sign)
+//static
+BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_words, BigInt::Sign y_sign)
    {
    const size_t x_sw = x.sig_words();
 
-   BigInt z(x.sign(), std::max(x_sw, y_sw) + 1);
+   BigInt z(x.sign(), std::max(x_sw, y_words) + 1);
 
    if(x.sign() == y_sign)
-      bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw);
+      {
+      bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);
+      }
    else
       {
-      int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_sw);
+      const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);
 
+      //z.sign_fixup(relative_size, y_sign);
       if(relative_size < 0)
-         {
-         bigint_sub3(z.mutable_data(), y, y_sw, x.data(), x_sw);
          z.set_sign(y_sign);
-         }
       else if(relative_size == 0)
          z.set_sign(BigInt::Positive);
-      else if(relative_size > 0)
-         bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_sw);
       }
 
    return z;
    }
 
-BigInt bigint_sub(const BigInt& x, const word y[], size_t y_sw, BigInt::Sign y_sign)
-   {
-   const size_t x_sw = x.sig_words();
-
-   int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_sw);
-
-   BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1);
-
-   if(relative_size < 0)
-      {
-      if(x.sign() == y_sign)
-         bigint_sub3(z.mutable_data(), y, y_sw, x.data(), x_sw);
-      else
-         bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw);
-      z.set_sign(y_sign == BigInt::Positive ? BigInt::Negative : BigInt::Positive);
-      }
-   else if(relative_size == 0)
-      {
-      if(x.sign() != y_sign)
-         bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1);
-      z.set_sign(y_sign == BigInt::Positive ? BigInt::Negative : BigInt::Positive);
-      }
-   else if(relative_size > 0)
-      {
-      if(x.sign() == y_sign)
-         bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_sw);
-      else
-         bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw);
-      z.set_sign(x.sign());
-      }
-   return z;
-   }
-
-}
-
-BigInt operator+(const BigInt& x, const BigInt& y)
-   {
-   return bigint_add(x, y.data(), y.sig_words(), y.sign());
-   }
-
-BigInt operator+(const BigInt& x, word y)
-   {
-   return bigint_add(x, &y, 1, BigInt::Positive);
-   }
-
-BigInt operator-(const BigInt& x, const BigInt& y)
-   {
-   return bigint_sub(x, y.data(), y.sig_words(), y.sign());
-   }
-
-BigInt operator-(const BigInt& x, word y)
-   {
-   return bigint_sub(x, &y, 1, BigInt::Positive);
-   }
-
 /*
 * Multiplication Operator
 */
 BigInt operator*(const BigInt& x, const BigInt& y)
    {
-   const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
+   const size_t x_sw = x.sig_words();
+   const size_t y_sw = y.sig_words();
 
    BigInt z(BigInt::Positive, x.size() + y.size());
 
@@ -222,15 +165,20 @@ BigInt operator>>(const BigInt& x, size_t shift)
    {
    if(shift == 0)
       return x;
-   if(x.bits() <= shift)
-      return 0;
 
-   const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
-                shift_bits  = shift % BOTAN_MP_WORD_BITS,
-                x_sw = x.sig_words();
+   const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
+   const size_t shift_bits  = shift % BOTAN_MP_WORD_BITS;
+   const size_t x_sw = x.sig_words();
+
+   if(shift_words >= x_sw)
+      return 0;
 
    BigInt y(x.sign(), x_sw - shift_words);
    bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
+
+   if(x.is_negative() && y.is_zero())
+      y.set_sign(BigInt::Positive);
+
    return y;
    }
 
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 1de3f7bc5..58c45dd67 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -1,6 +1,6 @@
 /*
 * BigInt
-* (C) 1999-2008,2012 Jack Lloyd
+* (C) 1999-2008,2012,2018 Jack Lloyd
 *     2007 FlexSecure
 *
 * Botan is released under the Simplified BSD License (see license.txt)
@@ -173,25 +173,37 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * += operator
      * @param y the BigInt to add to this
      */
-     BigInt& operator+=(const BigInt& y);
+     BigInt& operator+=(const BigInt& y)
+        {
+        return add(y.data(), y.sig_words(), y.sign());
+        }
 
      /**
      * += operator
      * @param y the word to add to this
      */
-     BigInt& operator+=(word y);
+     BigInt& operator+=(word y)
+        {
+        return add(&y, 1, Positive);
+        }
 
      /**
      * -= operator
      * @param y the BigInt to subtract from this
      */
-     BigInt& operator-=(const BigInt& y);
+     BigInt& operator-=(const BigInt& y)
+        {
+        return sub(y.data(), y.sig_words(), y.sign());
+        }
 
      /**
      * -= operator
      * @param y the word to subtract from this
      */
-     BigInt& operator-=(word y);
+     BigInt& operator-=(word y)
+        {
+        return sub(&y, 1, Positive);
+        }
 
      /**
      * *= operator
@@ -267,8 +279,14 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      bool operator !() const { return (!is_nonzero()); }
 
+     static BigInt add2(const BigInt& x, const word y[], size_t y_words, Sign y_sign);
+
      BigInt& add(const word y[], size_t y_words, Sign sign);
-     BigInt& sub(const word y[], size_t y_words, Sign sign);
+
+     BigInt& sub(const word y[], size_t y_words, Sign sign)
+        {
+        return add(y, y_words, sign == Positive ? Negative : Positive);
+        }
 
      /**
      * Multiply this with y
@@ -286,10 +304,10 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      /**
      * Set *this to y - *this
      * @param y the BigInt to subtract from as a sequence of words
-     * @param y_size length of y in words
+     * @param y_words length of y in words
      * @param ws a temp workspace
      */
-     BigInt& rev_sub(const word y[], size_t y_size, secure_vector<word>& ws);
+     BigInt& rev_sub(const word y[], size_t y_words, secure_vector<word>& ws);
 
      /**
      * Set *this to (*this + y) % mod
@@ -979,12 +997,30 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
 /*
 * Arithmetic Operators
 */
-BigInt BOTAN_PUBLIC_API(2,0) operator+(const BigInt& x, const BigInt& y);
-BigInt BOTAN_PUBLIC_API(2,7) operator+(const BigInt& x, word y);
-inline BigInt operator+(word x, const BigInt& y) { return y + x; }
+inline BigInt operator+(const BigInt& x, const BigInt& y)
+   {
+   return BigInt::add2(x, y.data(), y.sig_words(), y.sign());
+   }
+
+inline BigInt operator+(const BigInt& x, word y)
+   {
+   return BigInt::add2(x, &y, 1, BigInt::Positive);
+   }
+
+inline BigInt operator+(word x, const BigInt& y)
+   {
+   return y + x;
+   }
+
+inline BigInt operator-(const BigInt& x, const BigInt& y)
+   {
+   return BigInt::add2(x, y.data(), y.sig_words(), y.reverse_sign());
+   }
 
-BigInt BOTAN_PUBLIC_API(2,0) operator-(const BigInt& x, const BigInt& y);
-BigInt BOTAN_PUBLIC_API(2,7) operator-(const BigInt& x, word y);
+inline BigInt operator-(const BigInt& x, word y)
+   {
+   return BigInt::add2(x, &y, 1, BigInt::Negative);
+   }
 
 BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y);
 BigInt BOTAN_PUBLIC_API(2,8) operator*(const BigInt& x, word y);
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 4829ef6fc..6e2fba049 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -138,7 +138,7 @@ inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
 *
 * Mask must be either 0 or all 1 bits
 */
-inline void bigint_cnd_addsub(CT::Mask<word> mask, word x[], const word y[], size_t size)
+inline void bigint_cnd_add_or_sub(CT::Mask<word> mask, word x[], const word y[], size_t size)
    {
    const size_t blocks = size - (size % 8);
 
@@ -335,7 +335,7 @@ inline void bigint_sub2_rev(word x[], const word y[], size_t y_size)
    for(size_t i = blocks; i != y_size; ++i)
       x[i] = word_sub(y[i], x[i], &borrow);
 
-   BOTAN_ASSERT(!borrow, "y must be greater than x");
+   BOTAN_ASSERT(borrow == 0, "y must be greater than x");
    }
 
 /**
@@ -652,6 +652,39 @@ bigint_ct_is_eq(const word x[], size_t x_size,
    }
 
 /**
+* Set z to abs(x-y), ie if x >= y, then compute z = x - y
+* Otherwise compute z = y - x
+* No borrow is possible since the result is always >= 0
+*
+* Return the relative size of x vs y (-1, 0, 1)
+*
+* @param z output array of max(x_size,y_size) words
+* @param x input param
+* @param x_size length of x
+* @param y input param
+* @param y_size length of y
+* @param ws array of at least 2*max(x_size,y_size) words
+*/
+inline int32_t
+bigint_sub_abs(word z[],
+               const word x[], size_t x_size,
+               const word y[], size_t y_size)
+   {
+   const int32_t relative_size = bigint_cmp(x, x_size, y, y_size);
+
+   // FIXME should be a const time swap
+   if(relative_size < 0)
+      {
+      std::swap(x, y);
+      std::swap(x_size, y_size);
+      }
+
+   bigint_sub3(z, x, x_size, y, y_size);
+
+   return relative_size;
+   }
+
+/**
 * Compute ((n1<<bits) + n0) / d
 */
 inline word bigint_divop(word n1, word n0, word d)
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index 8bd7cf58d..15fcafa5b 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -144,7 +144,7 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N,
 
    clear_mem(workspace + N, N2);
 
-   bigint_cnd_addsub(neg_mask, z + N2, workspace, 2*N-N2);
+   bigint_cnd_add_or_sub(neg_mask, z + N2, workspace, 2*N-N2);
    }
 
 /*
diff --git a/src/tests/data/bn/sub.vec b/src/tests/data/bn/sub.vec
index a3cac4206..2bab86339 100644
--- a/src/tests/data/bn/sub.vec
+++ b/src/tests/data/bn/sub.vec
@@ -28,6 +28,10 @@ In2 = -1
 Output = 2
 
 In1 = 1
+In2 = 2
+Output = -1
+
+In1 = 1
 In2 = -2
 Output = 3
 
@@ -35,6 +39,26 @@ In1 = -1
 In2 = 2
 Output = -3
 
+In1 = -1
+In2 = -2
+Output = 1
+
+In1 = 2
+In2 = 1
+Output = 1
+
+In1 = 2
+In2 = -1
+Output = 3
+
+In1 = -2
+In2 = 1
+Output = -3
+
+In1 = -1
+In2 = -2
+Output = 1
+
 In1 = -3
 In2 = -1
 Output = -2