diff options
Diffstat (limited to 'src/lib')
| -rw-r--r-- | src/lib/math/bigint/divide.cpp | 76 |
1 files changed, 37 insertions, 39 deletions
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp index ed9a12112..98df233e3 100644 --- a/src/lib/math/bigint/divide.cpp +++ b/src/lib/math/bigint/divide.cpp @@ -164,6 +164,8 @@ void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) const size_t y_words = y_arg.sig_words(); + BOTAN_ASSERT_NOMSG(y_words > 0); + BigInt y = y_arg; BigInt r = x; @@ -173,62 +175,58 @@ void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) r.set_sign(BigInt::Positive); y.set_sign(BigInt::Positive); - if(r.is_nonzero()) - { - // 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)); - - y <<= shifts; - r <<= shifts; - - // we know y has not changed size, since we only shifted up to set high bit - const size_t t = y_words - 1; - const size_t n = std::max(t, r.sig_words() - 1); // r may have changed size however + // 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)); - BOTAN_ASSERT_NOMSG(n >= t); + y <<= shifts; + r <<= shifts; - q.grow_to(n - t + 1); + // we know y has not changed size, since we only shifted up to set high bit + const size_t t = y_words - 1; + const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however - word* q_words = q.mutable_data(); + BOTAN_ASSERT_NOMSG(n >= t); - BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n-t)); + q.grow_to(n - t + 1); - // Set q_{n-t} to number of times r > shifted_y - q_words[n-t] = r.reduce_below(shifted_y, ws); + word* q_words = q.mutable_data(); - const word y_t0 = y.word_at(t); - const word y_t1 = y.word_at(t-1); + BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n-t)); - for(size_t j = n; j != t; --j) - { - const word x_j0 = r.word_at(j); - const word x_j1 = r.word_at(j-1); - const word x_j2 = r.word_at(j-2); + // Set q_{n-t} to number of times r > shifted_y + q_words[n-t] = r.reduce_below(shifted_y, ws); - word qjt = bigint_divop(x_j0, x_j1, y_t0); + const word y_t0 = y.word_at(t); + const word y_t1 = y.word_at(t-1); - qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt); + for(size_t j = n; j != t; --j) + { + const word x_j0 = r.word_at(j); + const word x_j1 = r.word_at(j-1); + const word x_j2 = r.word_at(j-2); - // Per HAC 14.23, this operation is required at most twice - qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); - qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); - BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false); + word qjt = bigint_divop(x_j0, x_j1, y_t0); - shifted_y >>= BOTAN_MP_WORD_BITS; - // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1)) + qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt); - r -= qjt * shifted_y; + // Per HAC 14.23, this operation is required at most twice + qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); + qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); + BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false); - // TODO this could be better - qjt -= r.is_negative(); - r += static_cast<word>(r.is_negative()) * shifted_y; + shifted_y >>= BOTAN_MP_WORD_BITS; + // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1)) - q_words[j-t-1] = qjt; - } + // TODO this sequence could be better + r -= qjt * shifted_y; + qjt -= r.is_negative(); + r += static_cast<word>(r.is_negative()) * shifted_y; - r >>= shifts; + q_words[j-t-1] = qjt; } + r >>= shifts; + sign_fixup(x, y_arg, q, r); r_out = r; |