Merge GH #1734 Refactor BigInt data model, add sig_words cache

3 files changed, 253 insertions, 107 deletions

diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
index bd107f33a..5352ac04e 100644
--- a/src/lib/math/bigint/big_ops2.cpp
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -20,7 +20,7 @@ BigInt& BigInt::add(const word y[], size_t y_sw, Sign y_sign)
       {
       const size_t reg_size = std::max(x_sw, y_sw) + 1;
 
-      if(m_reg.size() < reg_size)
+      if(size() < reg_size)
          grow_to(reg_size);
 
       bigint_add2(mutable_data(), reg_size - 1, y, y_sw);
@@ -38,7 +38,7 @@ BigInt& BigInt::add(const word y[], size_t y_sw, Sign y_sign)
          }
       else if(relative_size == 0)
          {
-         zeroise(m_reg);
+         this->clear();
          set_sign(Positive);
          }
       else if(relative_size > 0)
@@ -126,37 +126,48 @@ BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>&
    if(this->is_negative() || s.is_negative() || mod.is_negative())
       throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive");
 
-   const size_t t_sw = sig_words();
-   const size_t s_sw = s.sig_words();
    const size_t mod_sw = mod.sig_words();
 
-   if(t_sw > mod_sw || s_sw > mod_sw)
-      throw Invalid_Argument("BigInt::mod_sub args larger than modulus");
-
    BOTAN_DEBUG_ASSERT(*this < mod);
    BOTAN_DEBUG_ASSERT(s < mod);
 
-   int32_t relative_size = bigint_cmp(data(), t_sw, s.data(), s_sw);
+   // We are assuming here that *this and s are no more than mod_sw words long
+   const size_t t_w = std::min(mod_sw, size());
+   const size_t s_w = std::min(mod_sw, s.size());
+
+   /*
+   TODO make this const time
+   */
+
+   int32_t relative_size = bigint_cmp(data(), t_w, s.data(), s_w);
 
    if(relative_size >= 0)
       {
-      // this >= s in which case just subtract
-      bigint_sub2(mutable_data(), t_sw, s.data(), s_sw);
+      /*
+      this >= s in which case just subtract
+
+      Here s_w might be > t_w because these values are just based on
+      the size of the buffer. But we know that because *this < s, then
+      this->sig_words() must be <= s.sig_words() so set the size of s
+      to the minimum of t and s words.
+      */
+      BOTAN_DEBUG_ASSERT(sig_words() <= s.sig_words());
+      bigint_sub2(mutable_data(), t_w, s.data(), std::min(t_w, s_w));
       }
    else
       {
-      // Otherwise we must sub s and then add p (or add (p - s) as here)
+       // Otherwise we must sub s and then add p (or add (p - s) as here)
 
       if(ws.size() < mod_sw)
          ws.resize(mod_sw);
 
-      word borrow = bigint_sub3(ws.data(), mod.data(), mod_sw, s.data(), s_sw);
+      word borrow = bigint_sub3(ws.data(), mod.data(), mod_sw, s.data(), s_w);
       BOTAN_ASSERT_NOMSG(borrow == 0);
 
-      if(m_reg.size() < mod_sw)
+      if(size() < mod_sw)
          grow_to(mod_sw);
 
-      word carry = bigint_add2_nc(mutable_data(), m_reg.size(), ws.data(), mod_sw);
+      word carry = bigint_add2_nc(mutable_data(), size(), ws.data(), mod_sw);
       BOTAN_ASSERT_NOMSG(carry == 0);
       }
 
@@ -193,7 +204,7 @@ BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws)
       bigint_sub3(ws.data(), y, y_sw, this->data(), x_sw);
       }
 
-   m_reg.swap(ws);
+   this->swap_reg(ws);
 
    return (*this);
    }
@@ -239,7 +250,7 @@ BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws)
                  y.data(), y.size(), y_sw,
                  ws.data(), ws.size());
 
-      z_reg.swap(m_reg);
+      this->swap_reg(z_reg);
       }
 
    return (*this);
@@ -309,25 +320,22 @@ word BigInt::operator%=(word mod)
 
    if(is_power_of_2(mod))
        {
-       word result = (word_at(0) & (mod - 1));
-       clear();
-       grow_to(2);
-       m_reg[0] = result;
-       return result;
+       const word remainder = (word_at(0) & (mod - 1));
+       m_data.set_to_zero();
+       m_data.set_word_at(0, remainder);
+       return remainder;
        }
 
    word remainder = 0;
 
    for(size_t j = sig_words(); j > 0; --j)
       remainder = bigint_modop(remainder, word_at(j-1), mod);
-   clear();
-   grow_to(2);
 
    if(remainder && sign() == BigInt::Negative)
-      m_reg[0] = mod - remainder;
-   else
-      m_reg[0] = remainder;
+      remainder = mod - remainder;
 
+   m_data.set_to_zero();
+   m_data.set_word_at(0, remainder);
    set_sign(BigInt::Positive);
 
    return word_at(0);
@@ -351,10 +359,9 @@ BigInt& BigInt::operator<<=(size_t shift)
       */
       const size_t needed_size = words + shift_words + (shift_bits ? 1 : 0);
 
-      if(m_reg.size() < needed_size)
-         grow_to(needed_size);
+      m_data.grow_to(needed_size);
 
-      bigint_shl1(mutable_data(), words, shift_words, shift_bits);
+      bigint_shl1(m_data.mutable_data(), words, shift_words, shift_bits);
       }
 
    return (*this);
@@ -370,7 +377,8 @@ BigInt& BigInt::operator>>=(size_t shift)
       const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
                    shift_bits  = shift % BOTAN_MP_WORD_BITS;
 
-      bigint_shr1(mutable_data(), sig_words(), shift_words, shift_bits);
+      const size_t sw = sig_words();
+      bigint_shr1(m_data.mutable_data(), sw, shift_words, shift_bits);
 
       if(is_zero())
          set_sign(Positive);
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 36f1d2883..bd89be7fb 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -15,7 +15,7 @@ namespace Botan {
 
 BigInt::BigInt(const word words[], size_t length)
    {
-   m_reg.assign(words, words + length);
+   m_data.set_words(words, length);
    }
 
 /*
@@ -23,14 +23,16 @@ BigInt::BigInt(const word words[], size_t length)
 */
 BigInt::BigInt(uint64_t n)
    {
-   if(n == 0)
-      return;
-
-   const size_t limbs_needed = sizeof(uint64_t) / sizeof(word);
+   if(n > 0)
+      {
+#if BOTAN_MP_WORD_BITS == 32
+      m_data.set_word_at(0, static_cast<word>(n));
+      m_data.set_word_at(1, static_cast<word>(n >> 32));
+#else
+      m_data.set_word_at(0, n);
+#endif
+      }
 
-   m_reg.resize(limbs_needed);
-   for(size_t i = 0; i != limbs_needed; ++i)
-      m_reg[i] = ((n >> (i*BOTAN_MP_WORD_BITS)) & MP_WORD_MASK);
    }
 
 /*
@@ -38,20 +40,11 @@ BigInt::BigInt(uint64_t n)
 */
 BigInt::BigInt(Sign s, size_t size)
    {
-   m_reg.resize(round_up(size, 8));
+   m_data.set_size(size);
    m_signedness = s;
    }
 
 /*
-* Copy constructor
-*/
-BigInt::BigInt(const BigInt& other)
-   {
-   m_reg = other.m_reg;
-   m_signedness = other.m_signedness;
-   }
-
-/*
 * Construct a BigInt from a string
 */
 BigInt::BigInt(const std::string& str)
@@ -158,6 +151,32 @@ void BigInt::encode_words(word out[], size_t size) const
    copy_mem(out, data(), words);
    }
 
+size_t BigInt::Data::calc_sig_words() const
+   {
+   size_t sig = m_reg.size();
+
+#if 0
+   // Const time, but slower ...
+
+   word seen_only_zeros = MP_WORD_MASK;
+   word sub = 1;
+
+   for(size_t i = 0; i != m_reg.size(); ++i)
+      {
+      const word w = m_reg[m_reg.size() - i - 1];
+      seen_only_zeros &= CT::is_zero(w);
+      sub &= seen_only_zeros;
+
+      sig -= sub;
+      }
+
+#else
+   while(sig && (m_reg[sig-1] == 0))
+      sig--;
+#endif
+   return sig;
+   }
+
 /*
 * Return bits {offset...offset+length}
 */
@@ -204,7 +223,8 @@ void BigInt::set_bit(size_t n)
    const size_t which = n / BOTAN_MP_WORD_BITS;
    const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
    if(which >= size()) grow_to(which + 1);
-   m_reg[which] |= mask;
+
+   m_data.set_word_at(which, m_data.get_word_at(which) | mask);
    }
 
 /*
@@ -213,9 +233,9 @@ void BigInt::set_bit(size_t n)
 void BigInt::clear_bit(size_t n)
    {
    const size_t which = n / BOTAN_MP_WORD_BITS;
-   const word mask = static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS);
+   const word mask = ~(static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS));
    if(which < size())
-      m_reg[which] &= ~mask;
+      m_data.set_word_at(which, m_data.get_word_at(which) & mask);
    }
 
 size_t BigInt::bytes() const
@@ -286,7 +306,7 @@ void BigInt::reduce_below(const BigInt& p, secure_vector<word>& ws)
       if(borrow)
          break;
 
-      m_reg.swap(ws);
+      swap_reg(ws);
       }
    }
 
@@ -300,17 +320,6 @@ BigInt BigInt::abs() const
    return x;
    }
 
-void BigInt::grow_to(size_t n)
-   {
-   if(n > size())
-      {
-      if(n <= m_reg.capacity())
-         m_reg.resize(m_reg.capacity());
-      else
-         m_reg.resize(round_up(n, 8));
-      }
-   }
-
 /*
 * Encode this number into bytes
 */
@@ -329,17 +338,20 @@ void BigInt::binary_decode(const uint8_t buf[], size_t length)
    const size_t WORD_BYTES = sizeof(word);
 
    clear();
-   m_reg.resize(round_up((length / WORD_BYTES) + 1, 8));
+   secure_vector<word> reg((round_up((length / WORD_BYTES) + 1, 8)));
 
+   // TODO can load a word at a time here
    for(size_t i = 0; i != length / WORD_BYTES; ++i)
       {
       const size_t top = length - WORD_BYTES*i;
       for(size_t j = WORD_BYTES; j > 0; --j)
-         m_reg[i] = (m_reg[i] << 8) | buf[top - j];
+         reg[i] = (reg[i] << 8) | buf[top - j];
       }
 
    for(size_t i = 0; i != length % WORD_BYTES; ++i)
-      m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
+      reg[length / WORD_BYTES] = (reg[length / WORD_BYTES] << 8) | buf[i];
+
+   m_data.swap(reg);
    }
 
 void BigInt::ct_cond_assign(bool predicate, BigInt& other)
@@ -360,12 +372,12 @@ void BigInt::ct_cond_assign(bool predicate, BigInt& other)
 #if defined(BOTAN_HAS_VALGRIND)
 void BigInt::const_time_poison() const
    {
-   CT::poison(m_reg.data(), m_reg.size());
+   CT::poison(m_data.const_data(), m_data.size());
    }
 
 void BigInt::const_time_unpoison() const
    {
-   CT::unpoison(m_reg.data(), m_reg.size());
+   CT::unpoison(m_data.const_data(), m_data.size());
    }
 #endif
 
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index aa2701fa4..530fd5ecf 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -59,7 +59,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * Copy Constructor
      * @param other the BigInt to copy
      */
-     BigInt(const BigInt& other);
+     BigInt(const BigInt& other) = default;
 
      /**
      * Create BigInt from a string. If the string starts with 0x the
@@ -156,13 +156,14 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      void swap(BigInt& other)
         {
-        m_reg.swap(other.m_reg);
+        m_data.swap(other.m_data);
         std::swap(m_signedness, other.m_signedness);
         }
 
      void swap_reg(secure_vector<word>& reg)
         {
-        m_reg.swap(reg);
+        m_data.swap(reg);
+        // sign left unchanged
         }
 
      /**
@@ -318,7 +319,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * Zeroize the BigInt. The size of the underlying register is not
      * modified.
      */
-     void clear() { zeroise(m_reg); }
+     void clear() { m_data.set_to_zero(); }
 
      /**
      * Compare this to another BigInt
@@ -382,20 +383,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      void mask_bits(size_t n)
         {
-        if(n == 0) { clear(); return; }
-
-        const size_t top_word = n / BOTAN_MP_WORD_BITS;
-        const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
-
-        if(top_word < size())
-           {
-           const size_t len = size() - (top_word + 1);
-           if (len > 0)
-              {
-              clear_mem(&m_reg[top_word+1], len);
-              }
-           m_reg[top_word] &= mask;
-           }
+        m_data.mask_bits(n);
         }
 
      /**
@@ -451,19 +439,18 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * @return value at position n
      */
      word word_at(size_t n) const
-        { return ((n < size()) ? m_reg[n] : 0); }
+        {
+        return m_data.get_word_at(n);
+        }
 
      void set_word_at(size_t i, word w)
         {
-        if(i >= m_reg.size())
-           grow_to(i + 1);
-        m_reg[i] = w;
+        m_data.set_word_at(i, w);
         }
 
      void set_words(const word w[], size_t len)
         {
-        m_reg.resize(len);
-        copy_mem(mutable_data(), w, len);
+        m_data.set_words(w, len);
         }
 
      /**
@@ -523,7 +510,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * Give size of internal register
      * @result size of internal register in words
      */
-     size_t size() const { return m_reg.size(); }
+     size_t size() const { return m_data.size(); }
 
      /**
      * Return how many words we need to hold this value
@@ -531,12 +518,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      size_t sig_words() const
         {
-        const word* x = m_reg.data();
-        size_t sig = m_reg.size();
-
-        while(sig && (x[sig-1] == 0))
-           sig--;
-        return sig;
+        return m_data.sig_words();
         }
 
      /**
@@ -555,22 +537,29 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      * Return a mutable pointer to the register
      * @result a pointer to the start of the internal register
      */
-     word* mutable_data() { return m_reg.data(); }
+     word* mutable_data() { return m_data.mutable_data(); }
 
      /**
      * Return a const pointer to the register
      * @result a pointer to the start of the internal register
      */
-     const word* data() const { return m_reg.data(); }
+     const word* data() const { return m_data.const_data(); }
 
-     secure_vector<word>& get_word_vector() { return m_reg; }
-     const secure_vector<word>& get_word_vector() const { return m_reg; }
+     /**
+     * Don't use this function in application code
+     */
+     secure_vector<word>& get_word_vector() { return m_data.mutable_vector(); }
+
+     /**
+     * Don't use this function in application code
+     */
+     const secure_vector<word>& get_word_vector() const { return m_data.const_vector(); }
 
      /**
      * Increase internal register buffer to at least n words
      * @param n new size of register
      */
-     void grow_to(size_t n);
+     void grow_to(size_t n) { m_data.grow_to(n); }
 
      /**
      * Resize the vector to the minimum word size to hold the integer, or
@@ -578,8 +567,7 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      void shrink_to_fit(size_t min_size = 0)
         {
-        const size_t words = std::max(min_size, sig_words());
-        m_reg.resize(words);
+        m_data.shrink_to_fit(min_size);
         }
 
      /**
@@ -822,7 +810,145 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
         size_t idx);
 
    private:
-      secure_vector<word> m_reg;
+
+     class Data
+        {
+        public:
+           word* mutable_data()
+              {
+              invalidate_sig_words();
+              return m_reg.data();
+              }
+
+           const word* const_data() const
+              {
+              return m_reg.data();
+              }
+
+           secure_vector<word>& mutable_vector()
+              {
+              invalidate_sig_words();
+              return m_reg;
+              }
+
+           const secure_vector<word>& const_vector() const
+              {
+              return m_reg;
+              }
+
+           word get_word_at(size_t n) const
+              {
+              if(n < m_reg.size())
+                 return m_reg[n];
+              return 0;
+              }
+
+           void set_word_at(size_t i, word w)
+              {
+              invalidate_sig_words();
+              if(i >= m_reg.size())
+                 grow_to(i + 1);
+              m_reg[i] = w;
+              }
+
+           void set_words(const word w[], size_t len)
+              {
+              invalidate_sig_words();
+              m_reg.assign(w, w + len);
+              }
+
+           void set_to_zero()
+              {
+              m_reg.resize(m_reg.capacity());
+              clear_mem(m_reg.data(), m_reg.size());
+              m_sig_words = 0;
+              }
+
+           void set_size(size_t s)
+              {
+              invalidate_sig_words();
+              clear_mem(m_reg.data(), m_reg.size());
+              m_reg.resize(s + (8 - (s % 8)));
+              }
+
+           void mask_bits(size_t n)
+              {
+              if(n == 0) { return set_to_zero(); }
+
+              const size_t top_word = n / BOTAN_MP_WORD_BITS;
+
+              // if(top_word < sig_words()) ?
+              if(top_word < size())
+                 {
+                 const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
+                 const size_t len = size() - (top_word + 1);
+                 if (len > 0)
+                    {
+                    clear_mem(&m_reg[top_word+1], len);
+                    }
+                 m_reg[top_word] &= mask;
+                 invalidate_sig_words();
+                 }
+              }
+
+           void grow_to(size_t n)
+              {
+              if(n > size())
+                 {
+                 if(n <= m_reg.capacity())
+                    m_reg.resize(m_reg.capacity());
+                 else
+                    m_reg.resize(n + (8 - (n % 8)));
+                 }
+              }
+
+           size_t size() const { return m_reg.size(); }
+
+           void shrink_to_fit(size_t min_size = 0)
+              {
+              const size_t words = std::max(min_size, sig_words());
+              m_reg.resize(words);
+              }
+
+           void swap(Data& other)
+              {
+              m_reg.swap(other.m_reg);
+              std::swap(m_sig_words, other.m_sig_words);
+              }
+
+           void swap(secure_vector<word>& reg)
+              {
+              m_reg.swap(reg);
+              invalidate_sig_words();
+              }
+
+           void invalidate_sig_words() const
+              {
+              m_sig_words = sig_words_npos;
+              }
+
+           size_t sig_words() const
+              {
+              if(m_sig_words == sig_words_npos)
+                 {
+                 m_sig_words = calc_sig_words();
+                 }
+              else
+                 {
+                 BOTAN_DEBUG_ASSERT(m_sig_words == calc_sig_words());
+                 }
+              return m_sig_words;
+              }
+        private:
+           static const size_t sig_words_npos = static_cast<size_t>(-1);
+
+           size_t calc_sig_words() const;
+
+           secure_vector<word> m_reg;
+           mutable size_t m_sig_words = sig_words_npos;
+        };
+
+      Data m_data;
       Sign m_signedness = Positive;
    };