aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/lib/math/bigint/big_ops2.cpp35
-rw-r--r--src/lib/math/bigint/big_ops3.cpp9
-rw-r--r--src/lib/math/bigint/bigint.cpp27
-rw-r--r--src/lib/math/bigint/bigint.h7
-rw-r--r--src/lib/math/bigint/divide.cpp3
-rw-r--r--src/lib/math/mp/mp_core.h100
6 files changed, 83 insertions, 98 deletions
diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp
index 0dc3c7715..c42bf16e9 100644
--- a/src/lib/math/bigint/big_ops2.cpp
+++ b/src/lib/math/bigint/big_ops2.cpp
@@ -318,23 +318,17 @@ word BigInt::operator%=(word mod)
*/
BigInt& BigInt::operator<<=(size_t shift)
{
- if(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 shift_words = shift / BOTAN_MP_WORD_BITS;
+ const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
+ 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();
- m_data.grow_to(needed_size);
+ const size_t new_size = size + shift_words + (bits_free < shift);
- bigint_shl1(m_data.mutable_data(), words, shift_words, shift_bits);
- }
+ m_data.grow_to(new_size);
+
+ bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
return (*this);
}
@@ -344,16 +338,13 @@ BigInt& BigInt::operator<<=(size_t shift)
*/
BigInt& BigInt::operator>>=(size_t shift)
{
- if(shift)
- {
- const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
- const size_t 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;
- bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
+ bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
- if(is_negative() && is_zero())
- set_sign(Positive);
- }
+ if(is_negative() && is_zero())
+ set_sign(Positive);
return (*this);
}
diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp
index e6c745dca..30b27c87b 100644
--- a/src/lib/math/bigint/big_ops3.cpp
+++ b/src/lib/math/bigint/big_ops3.cpp
@@ -152,9 +152,6 @@ word operator%(const BigInt& n, word mod)
*/
BigInt operator<<(const BigInt& x, size_t shift)
{
- if(shift == 0)
- return x;
-
const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
shift_bits = shift % BOTAN_MP_WORD_BITS;
@@ -170,16 +167,10 @@ BigInt operator<<(const BigInt& x, size_t shift)
*/
BigInt operator>>(const BigInt& x, size_t shift)
{
- if(shift == 0)
- return x;
-
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);
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 73212b6b0..d8861fe65 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -274,9 +274,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();
@@ -284,12 +295,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 a987fffda..387bbe8f9 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -604,6 +604,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 f586285bd..1ac6f7173 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -408,92 +408,78 @@ 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)
{
- if(word_shift)
- {
- copy_mem(x + word_shift, x, x_size);
- clear_mem(x, word_shift);
- }
+ copy_mem(x + word_shift, x, x_words);
+ clear_mem(x, word_shift);
- if(bit_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; ++i)
{
- word carry = 0;
- for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
- {
- word temp = x[j];
- x[j] = (temp << bit_shift) | carry;
- carry = (temp >> (BOTAN_MP_WORD_BITS - bit_shift));
- }
+ const word w = x[i];
+ x[i] = (w << bit_shift) | carry;
+ carry = carry_mask.if_set_return(w >> carry_shift);
}
}
inline void bigint_shr1(word x[], size_t x_size,
size_t word_shift, size_t bit_shift)
{
- if(x_size < word_shift)
- {
- clear_mem(x, x_size);
- return;
- }
-
- if(word_shift)
- {
- copy_mem(x, x + word_shift, x_size - word_shift);
- clear_mem(x + x_size - word_shift, word_shift);
- }
+ const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
- if(bit_shift)
- {
- word carry = 0;
+ copy_mem(x, x + word_shift, top);
+ clear_mem(x + top, std::min(word_shift, x_size));
- size_t top = x_size - 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);
- while(top)
- {
- word w = x[top-1];
- x[top-1] = (w >> bit_shift) | carry;
- carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
+ word carry = 0;
- top--;
- }
+ for(size_t i = 0; i != top; ++i)
+ {
+ const word w = x[top - i - 1];
+ x[top-i-1] = (w >> bit_shift) | carry;
+ carry = carry_mask.if_set_return(w << carry_shift);
}
}
inline void bigint_shl2(word y[], const word x[], size_t x_size,
size_t word_shift, size_t bit_shift)
{
- for(size_t j = 0; j != x_size; ++j)
- y[j + word_shift] = x[j];
- if(bit_shift)
+ copy_mem(y + word_shift, x, x_size);
+
+ 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)
{
- word carry = 0;
- for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
- {
- word w = y[j];
- y[j] = (w << bit_shift) | carry;
- carry = (w >> (BOTAN_MP_WORD_BITS - bit_shift));
- }
+ const word w = y[i];
+ y[i] = (w << bit_shift) | carry;
+ carry = carry_mask.if_set_return(w >> carry_shift);
}
}
inline void bigint_shr2(word y[], const word x[], size_t x_size,
size_t word_shift, size_t bit_shift)
{
- if(x_size < word_shift) return;
+ const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
+
+ copy_mem(y, x + word_shift, new_size);
+
+ 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);
- for(size_t j = 0; j != x_size - word_shift; ++j)
- y[j] = x[j + word_shift];
- if(bit_shift)
+ word carry = 0;
+ for(size_t i = new_size; i > 0; --i)
{
- word carry = 0;
- for(size_t j = x_size - word_shift; j > 0; --j)
- {
- word w = y[j-1];
- y[j-1] = (w >> bit_shift) | carry;
- carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
- }
+ word w = y[i-1];
+ y[i-1] = (w >> bit_shift) | carry;
+ carry = carry_mask.if_set_return(w << carry_shift);
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-23 23:59:45 +0000