Bug 1190248: Compute a guess for the next quotient digit correctly in
 author Wan-Teh Chang Tue, 25 Aug 2015 10:21:11 -0700 changeset 11557 a555bf0fc23a981f22ed8ea6da89ef8d0c5ecf56 parent 11556 a73ae1f6ac11c8338e675c8f803c34a145cba944 child 11558 608645309ab97aff5f6bf5bb71ddf13cc8a820f5 push id 717 push user wtc@google.com push date Tue, 25 Aug 2015 17:21:20 +0000 bugs 1190248
Bug 1190248: Compute a guess for the next quotient digit correctly in s_mp_div. r=rrelyea.
 lib/freebl/mpi/mpi.c file | annotate | diff | comparison | revisions
```--- a/lib/freebl/mpi/mpi.c
+++ b/lib/freebl/mpi/mpi.c
@@ -4202,49 +4202,61 @@ mp_err   s_mp_div(mp_int *rem, 	/* i: di
/* Perform the division itself...woo!   */
MP_USED(quot) = MP_ALLOC(quot);

/* Find a partial substring of rem which is at least div */
/* If we didn't find one, we're finished dividing    */
while (MP_USED(rem) > MP_USED(div) || s_mp_cmp(rem, div) >= 0) {
int i;
int unusedRem;
+    int partExtended = 0;  /* set to true if we need to extend part */

unusedRem = MP_USED(rem) - MP_USED(div);
MP_DIGITS(&part) = MP_DIGITS(rem) + unusedRem;
MP_ALLOC(&part)  = MP_ALLOC(rem)  - unusedRem;
MP_USED(&part)   = MP_USED(div);
+
+    /* We have now truncated the part of the remainder to the same length as
+     * the divisor. If part is smaller than div, extend part by one digit. */
if (s_mp_cmp(&part, div) < 0) {
-- unusedRem;
#if MP_ARGCHK == 2
assert(unusedRem >= 0);
#endif
-- MP_DIGITS(&part);
++ MP_USED(&part);
++ MP_ALLOC(&part);
+      partExtended = 1;
}

/* Compute a guess for the next quotient digit       */
q_msd = MP_DIGIT(&part, MP_USED(&part) - 1);
div_msd = MP_DIGIT(div, MP_USED(div) - 1);
-    if (q_msd >= div_msd) {
+    if (!partExtended) {
+      /* In this case, q_msd /= div_msd is always 1. First, since div_msd is
+       * normalized to have the high bit set, 2*div_msd > MP_DIGIT_MAX. Since
+       * we didn't extend part, q_msd >= div_msd. Therefore we know that
+       * div_msd <= q_msd <= MP_DIGIT_MAX < 2*div_msd. Dividing by div_msd we
+       * get 1 <= q_msd/div_msd < 2. So q_msd /= div_msd must be 1. */
q_msd = 1;
-    } else if (MP_USED(&part) > 1) {
+    } else {
#if !defined(MP_NO_MP_WORD) && !defined(MP_NO_DIV_WORD)
q_msd = (q_msd << MP_DIGIT_BIT) | MP_DIGIT(&part, MP_USED(&part) - 2);
q_msd /= div_msd;
--q_msd;
#else
-      mp_digit r;
-      MP_CHECKOK( s_mpv_div_2dx1d(q_msd, MP_DIGIT(&part, MP_USED(&part) - 2),
-				  div_msd, &q_msd, &r) );
+      if (q_msd == div_msd) {
+        q_msd = MP_DIGIT_MAX;
+      } else {
+        mp_digit r;
+        MP_CHECKOK( s_mpv_div_2dx1d(q_msd, MP_DIGIT(&part, MP_USED(&part) - 2),
+				    div_msd, &q_msd, &r) );
+      }
#endif
-    } else {
-      q_msd = 0;
}
#if MP_ARGCHK == 2
assert(q_msd > 0); /* This case should never occur any more. */
#endif
if (q_msd <= 0)
break;

/* See what that multiplies out to                   */```