From 968e13cbbda2e9fc8a7e8d91cd35d4ac93c695b9 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Thu, 8 Mar 2018 06:31:51 -0800 Subject: bugfix: broken single-digit bignum multiplication. * mpi/mpi.c (s_mp_mul_d): The test used for deciding whether or not the multiplication will carry, and possibly needs another digit of space, is broken. There are situations in which a carry occurs (k > 0) in spite of the test being negative. We code this the way it should have been done in the first place: resize the object when carry actually occurs. This still avoids calling s_mp_pad unless absolutely necessary, as the removed comment says. Also, in the carry case, we need not try to clamp away leading zeros. --- mpi/mpi.c | 27 +++++++++------------------ 1 file changed, 9 insertions(+), 18 deletions(-) (limited to 'mpi/mpi.c') diff --git a/mpi/mpi.c b/mpi/mpi.c index eaa724b3..84308e8a 100644 --- a/mpi/mpi.c +++ b/mpi/mpi.c @@ -3302,20 +3302,7 @@ mp_err s_mp_mul_d(mp_int *a, mp_digit d) mp_err res; mp_digit *dp = DIGITS(a); - /* Single-digit multiplication will increase the precision of the - * output by at most one digit. However, we can detect when this - * will happen -- if the high-order digit of a, times d, gives a - * two-digit result, then the precision of the result will increase; - * otherwise it won't. We use this fact to avoid calling s_mp_pad() - * unless absolutely necessary. - */ max = USED(a); - w = dp[max - 1] * convert(mp_word, d); - if (CARRYOUT(w) != 0) { - if ((res = s_mp_pad(a, max + 1)) != MP_OKAY) - return res; - dp = DIGITS(a); - } for (ix = 0; ix < max; ix++) { w = dp[ix] * convert(mp_word, d) + k; @@ -3323,16 +3310,20 @@ mp_err s_mp_mul_d(mp_int *a, mp_digit d) k = CARRYOUT(w); } - /* If there is a precision increase, take care of it here; the above - * test guarantees we have enough storage to do this safely. + /* If there is a carry out, we must ensure + * we have enough storage for the extra digit. + * If there is carry, there are no leading zeros + * don't waste time calling s_mp_clamp. */ if (k) { - dp[max] = k; + if ((res = s_mp_pad(a, max + 1)) != MP_OKAY) + return res; + DIGIT(a, max) = k; USED(a) = max + 1; + } else { + s_mp_clamp(a); } - s_mp_clamp(a); - return MP_OKAY; } -- cgit v1.2.3