From ebb73b99a8ca14c45d64de2619ab0cf6b89b860e Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Thu, 26 Apr 2018 11:40:50 -0400 Subject: Add BigInt functions for adding, subtracting and comparing with words Avoids needless allocations for expressions like x - 1 or y <= 4. --- src/lib/math/bigint/big_ops2.cpp | 64 ++++++++++++++++++++-------------- src/lib/math/bigint/big_ops3.cpp | 75 ++++++++++++++++++++++++++-------------- src/lib/math/bigint/bigint.cpp | 12 +++++++ src/lib/math/bigint/bigint.h | 42 ++++++++++++++++++++++ 4 files changed, 142 insertions(+), 51 deletions(-) diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp index 242635257..39f985566 100644 --- a/src/lib/math/bigint/big_ops2.cpp +++ b/src/lib/math/bigint/big_ops2.cpp @@ -12,32 +12,29 @@ namespace Botan { -/* -* Addition Operator -*/ -BigInt& BigInt::operator+=(const BigInt& y) +BigInt& BigInt::add(const word y[], size_t y_sw, Sign y_sign) { - const size_t x_sw = sig_words(), y_sw = y.sig_words(); + const size_t x_sw = sig_words(); - if(sign() == y.sign()) + if(sign() == y_sign) { const size_t reg_size = std::max(x_sw, y_sw) + 1; if(m_reg.size() < reg_size) grow_to(reg_size); - bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw); + bigint_add2(mutable_data(), reg_size - 1, y, y_sw); } else { - const int32_t relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw); + const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_sw); 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.data(), y_sw); - set_sign(y.sign()); + bigint_sub2_rev(mutable_data(), y, y_sw); + set_sign(y_sign); } else if(relative_size == 0) { @@ -46,37 +43,44 @@ BigInt& BigInt::operator+=(const BigInt& y) } else if(relative_size > 0) { - bigint_sub2(mutable_data(), x_sw, y.data(), y_sw); + bigint_sub2(mutable_data(), x_sw, y, y_sw); } } return (*this); } -/* -* Subtraction Operator -*/ -BigInt& BigInt::operator-=(const BigInt& y) +BigInt& BigInt::operator+=(const BigInt& y) + { + return add(y.data(), y.sig_words(), y.sign()); + } + +BigInt& BigInt::operator+=(word y) { - const size_t x_sw = sig_words(), y_sw = y.sig_words(); + 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.data(), y_sw); + 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.data(), y_sw); + if(sign() == y_sign) + bigint_sub2_rev(mutable_data(), y, y_sw); else - bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw); + bigint_add2(mutable_data(), reg_size - 1, y, y_sw); - set_sign(y.reverse_sign()); + set_sign(y_sign == Positive ? Negative : Positive); } else if(relative_size == 0) { - if(sign() == y.sign()) + if(sign() == y_sign) { clear(); set_sign(Positive); @@ -86,15 +90,25 @@ BigInt& BigInt::operator-=(const BigInt& y) } else if(relative_size > 0) { - if(sign() == y.sign()) - bigint_sub2(mutable_data(), x_sw, y.data(), y_sw); + if(sign() == y_sign) + bigint_sub2(mutable_data(), x_sw, y, y_sw); else - bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw); + 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& ws) { if(this->is_negative() || s.is_negative() || mod.is_negative()) diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp index ce9047b15..4f0ba5364 100644 --- a/src/lib/math/bigint/big_ops3.cpp +++ b/src/lib/math/bigint/big_ops3.cpp @@ -14,71 +14,94 @@ namespace Botan { -/* -* Addition Operator -*/ -BigInt operator+(const BigInt& x, const BigInt& y) +namespace { + +BigInt bigint_add(const BigInt& x, const word y[], size_t y_sw, BigInt::Sign y_sign) { - const size_t x_sw = x.sig_words(), y_sw = y.sig_words(); + const size_t x_sw = x.sig_words(); BigInt z(x.sign(), std::max(x_sw, y_sw) + 1); - if(x.sign() == y.sign()) - bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); + if(x.sign() == y_sign) + bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_sw); else { - int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw); + int32_t relative_size = bigint_cmp(x.data(), x_sw, y, y_sw); if(relative_size < 0) { - bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw); - z.set_sign(y.sign()); + 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.data(), y_sw); + bigint_sub3(z.mutable_data(), x.data(), x_sw, y, y_sw); } return z; } -/* -* Subtraction Operator -*/ -BigInt operator-(const BigInt& x, const BigInt& y) +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(), y_sw = y.sig_words(); + const size_t x_sw = x.sig_words(); - int32_t relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw); + 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.data(), y_sw, x.data(), x_sw); + 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.data(), y_sw); - z.set_sign(y.reverse_sign()); + 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()) + if(x.sign() != y_sign) bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1); - z.set_sign(y.reverse_sign()); + 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.data(), y_sw); + 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.data(), y_sw); + 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+(word y, const BigInt& x) + { + 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 */ diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp index 8874195af..39cff666c 100644 --- a/src/lib/math/bigint/bigint.cpp +++ b/src/lib/math/bigint/bigint.cpp @@ -113,6 +113,18 @@ BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit) randomize(rng, bits, set_high_bit); } +int32_t BigInt::cmp_word(word other) const + { + if(is_negative()) + return -1; // other is positive ... + + const size_t sw = this->sig_words(); + if(sw > 1) + return 1; // must be larger since other is just one word ... + + return bigint_cmp(this->data(), sw, &other, 1); + } + /* * Comparison Function */ diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index bb7a69541..33a1252ab 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -164,12 +164,24 @@ class BOTAN_PUBLIC_API(2,0) BigInt final */ BigInt& operator+=(const BigInt& y); + /** + * += operator + * @param y the word to add to this + */ + BigInt& operator+=(word y); + /** * -= operator * @param y the BigInt to subtract from this */ BigInt& operator-=(const BigInt& y); + /** + * -= operator + * @param y the word to subtract from this + */ + BigInt& operator-=(word y); + /** * *= operator * @param y the BigInt to multiply with this @@ -305,6 +317,14 @@ class BOTAN_PUBLIC_API(2,0) BigInt final */ int32_t cmp(const BigInt& n, bool check_signs = true) const; + /** + * Compare this to an integer + * @param n the value to compare with + * @result if (thisn) return 1, if both + * values are identical return 0 [like Perl's <=> operator] + */ + int32_t cmp_word(word n) const; + /** * Test if the integer has an even value * @result true if the integer is even, false otherwise @@ -700,6 +720,10 @@ class BOTAN_PUBLIC_API(2,0) BigInt final size_t idx); private: + + BigInt& add(const word y[], size_t y_words, Sign sign); + BigInt& sub(const word y[], size_t y_words, Sign sign); + secure_vector m_reg; Sign m_signedness = Positive; }; @@ -708,7 +732,12 @@ 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); +BigInt BOTAN_PUBLIC_API(2,7) operator+(word x, const BigInt& y); + 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); + BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y); BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d); BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m); @@ -732,6 +761,19 @@ inline bool operator<(const BigInt& a, const BigInt& b) inline bool operator>(const BigInt& a, const BigInt& b) { return (a.cmp(b) > 0); } +inline bool operator==(const BigInt& a, word b) + { return (a.cmp_word(b) == 0); } +inline bool operator!=(const BigInt& a, word b) + { return (a.cmp_word(b) != 0); } +inline bool operator<=(const BigInt& a, word b) + { return (a.cmp_word(b) <= 0); } +inline bool operator>=(const BigInt& a, word b) + { return (a.cmp_word(b) >= 0); } +inline bool operator<(const BigInt& a, word b) + { return (a.cmp_word(b) < 0); } +inline bool operator>(const BigInt& a, word b) + { return (a.cmp_word(b) > 0); } + /* * I/O Operators */ -- cgit v1.2.3