Fix bug and avoid allocations in left shift

5 files changed, 36 insertions, 22 deletions

diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
index 6b8be1238..c42bf16e9 100644
--- a/src/lib/math/bigint/big_ops2.cpp
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -320,18 +320,15 @@ BigInt& BigInt::operator<<=(size_t shift)
    {
    const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
    const size_t shift_bits  = shift % BOTAN_MP_WORD_BITS;
-   const size_t words = sig_words();
+   const size_t size = sig_words();
 
-   /*
-   * FIXME - if shift_words == 0 && the top shift_bits of the top word
-   * are zero then we know that no additional word is needed and can
-   * skip the allocation.
-   */
-   const size_t needed_size = words + shift_words + (shift_bits ? 1 : 0);
+   const size_t bits_free = top_bits_free();
+
+   const size_t new_size = size + shift_words + (bits_free < shift);
 
-   m_data.grow_to(needed_size);
+   m_data.grow_to(new_size);
 
-   bigint_shl1(m_data.mutable_data(), words, shift_words, shift_bits);
+   bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
 
    return (*this);
    }
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index dd5ee6ac3..37a0fd0d4 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -273,9 +273,20 @@ size_t BigInt::bytes() const
    return round_up(bits(), 8) / 8;
    }
 
-/*
-* Count how many bits are being used
-*/
+size_t BigInt::top_bits_free() const
+   {
+   const size_t words = sig_words();
+
+   const word top_word = word_at(words - 1);
+
+   // Need to unpoison due to high_bit not being const time
+   CT::unpoison(top_word);
+
+   const size_t bits_used = high_bit(top_word);
+
+   return BOTAN_MP_WORD_BITS - bits_used;
+   }
+
 size_t BigInt::bits() const
    {
    const size_t words = sig_words();
@@ -283,12 +294,10 @@ size_t BigInt::bits() const
    if(words == 0)
       return 0;
 
-   const size_t full_words = words - 1;
-   const word top_word = word_at(full_words);
-   // Need to unpoison due to high_bit not being const time
-   CT::unpoison(top_word);
-   const size_t bits = (full_words * BOTAN_MP_WORD_BITS + high_bit(top_word));
-   return bits;
+   const size_t full_words = (words - 1) * BOTAN_MP_WORD_BITS;
+   const size_t top_bits = BOTAN_MP_WORD_BITS - top_bits_free();
+
+   return full_words + top_bits;
    }
 
 /*
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 31eee4c3c..ade70ba68 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -592,6 +592,13 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      size_t bits() const;
 
      /**
+     * Get the number of high bits unset in the top (allocated) word
+     * of this integer. Returns BOTAN_MP_WORD_BITS only iff *this is
+     * zero. Ignores sign.
+     */
+     size_t top_bits_free() const;
+
+     /**
      * Return a mutable pointer to the register
      * @result a pointer to the start of the internal register
      */
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index be47c6b5d..fdb920241 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -175,7 +175,7 @@ void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out)
    y.set_sign(BigInt::Positive);
 
    // Calculate shifts needed to normalize y with high bit set
-   const size_t shifts = BOTAN_MP_WORD_BITS - high_bit(y.word_at(y_words-1));
+   const size_t shifts = y.top_bits_free();
 
    y <<= shifts;
    r <<= shifts;
@@ -197,6 +197,7 @@ void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out)
 
    const word y_t0  = y.word_at(t);
    const word y_t1  = y.word_at(t-1);
+   BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS-1)) == 1);
 
    for(size_t j = n; j != t; --j)
       {
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 0d9c6a6a3..9caacf9fb 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -408,17 +408,17 @@ bigint_sub_abs(word z[],
 /*
 * Shift Operations
 */
-inline void bigint_shl1(word x[], size_t x_size,
+inline void bigint_shl1(word x[], size_t x_size, size_t x_words,
                         size_t word_shift, size_t bit_shift)
    {
-   copy_mem(x + word_shift, x, x_size);
+   copy_mem(x + word_shift, x, x_words);
    clear_mem(x, word_shift);
 
    const auto carry_mask = CT::Mask<word>::expand(bit_shift);
    const size_t carry_shift = carry_mask.if_set_return(BOTAN_MP_WORD_BITS - bit_shift);
 
    word carry = 0;
-   for(size_t i = word_shift; i != x_size + word_shift + 1; ++i)
+   for(size_t i = word_shift; i != x_size; ++i)
       {
       const word w = x[i];
       x[i] = (w << bit_shift) | carry;