Remove remaining running pointers in BN_div
Expressing everything in terms of i makes it at lot easier to tell what
words are being written to where, and convince oneself that everything
stays in bounds. I kept a wnum variable in there since it's used so
frequently but added a note about the bounds. In a higher-level
language, wnum would be a slice of width div_n + 1.
Bug: 358687140
Change-Id: Iae39b1915f80008ab5ed91e1e7fc5cd1349e8c1e
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/70227
Reviewed-by: Bob Beck <bbe@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/crypto/fipsmodule/bn/div.c b/crypto/fipsmodule/bn/div.c
index f1588c1..aa2e2e5 100644
--- a/crypto/fipsmodule/bn/div.c
+++ b/crypto/fipsmodule/bn/div.c
@@ -236,15 +236,6 @@
}
int loop = num_n - div_n;
- // Lets setup a 'window' into snum
- // This is the part that corresponds to the current
- // 'area' being divided
- BIGNUM wnum;
- wnum.neg = 0;
- wnum.d = &(snum->d[loop]);
- wnum.width = div_n;
- // only needed when BN_ucmp messes up the values between width and max
- wnum.dmax = snum->dmax - loop; // so we don't step out of bounds
// Get the top 2 words of sdiv.
const BN_ULONG d0 = sdiv->d[div_n - 1];
@@ -253,9 +244,6 @@
// The normalization step ensures that |sdiv|'s MSB is one.
assert(d0 & (((BN_ULONG)1) << (BN_BITS2 - 1)));
- // pointer to the 'top' of snum
- BN_ULONG *wnump = &(snum->d[num_n - 1]);
-
// Setup |res|. |numerator| and |res| may alias, so we save |numerator->neg|
// for later.
const int numerator_neg = numerator->neg;
@@ -273,19 +261,19 @@
// division. Note that Knuth indexes words from most to least significant, so
// our index is reversed. Each loop iteration computes res->d[i] of the
// quotient and updates snum with the running remainder. Before each loop
- // iteration, wnum <= sdiv.
- for (int i = loop - 1; i >= 0; i--, wnump--) {
- // TODO(crbug.com/358687140): Remove these running pointers.
- wnum.d--;
- assert(wnum.d == snum->d + i);
- assert(wnump == wnum.d + div_n);
-
- // Knuth step D3: Compute q', an estimate of q = floor(wnum / sdiv) by
- // looking at the top words. We must estimate such that q' = q or
- // q' = q + 1.
+ // iteration, the div_n words beginning at snum->d[i+1] must be less than
+ // snum.
+ for (int i = loop - 1; i >= 0; i--) {
+ // The next word of the quotient, q, is floor(wnum / sdiv), where wnum is
+ // the div_n + 1 words beginning at snum->d[i]. i starts at
+ // num_n - div_n - 1, so there are at least div_n + 1 words available.
+ //
+ // Knuth step D3: Compute q', an estimate of q by looking at the top words
+ // of wnum and sdiv. We must estimate such that q' = q or q' = q + 1.
BN_ULONG q, rm = 0;
- BN_ULONG n0 = wnump[0];
- BN_ULONG n1 = wnump[-1];
+ BN_ULONG *wnum = snum->d + i;
+ BN_ULONG n0 = wnum[div_n];
+ BN_ULONG n1 = wnum[div_n - 1];
if (n0 == d0) {
// Estimate q' = b - 1, where b is the base.
q = BN_MASK2;
@@ -325,10 +313,11 @@
// q + 1, Knuth uses a loop. A loop will often also correct q + 1 to q,
// saving the slightly more expensive underflow handling below.
if (div_n > 1) {
+ BN_ULONG n2 = wnum[div_n - 2];
#ifdef BN_ULLONG
BN_ULLONG t2 = (BN_ULLONG)d1 * q;
for (;;) {
- if (t2 <= ((((BN_ULLONG)rm) << BN_BITS2) | wnump[-2])) {
+ if (t2 <= ((((BN_ULLONG)rm) << BN_BITS2) | n2)) {
break;
}
q--;
@@ -344,7 +333,7 @@
BN_ULONG t2l, t2h;
BN_UMULT_LOHI(t2l, t2h, d1, q);
for (;;) {
- if (t2h < rm || (t2h == rm && t2l <= wnump[-2])) {
+ if (t2h < rm || (t2h == rm && t2l <= n2)) {
break;
}
q--;
@@ -367,10 +356,10 @@
// -sdiv < wnum - sdiv * q < sdiv. If q' = q + 1, the subtraction will
// underflow, and we fix it up below.
tmp->d[div_n] = bn_mul_words(tmp->d, sdiv->d, div_n, q);
- if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) {
+ if (bn_sub_words(wnum, wnum, tmp->d, div_n + 1)) {
q--;
// The final addition is expected to overflow, canceling the underflow.
- wnum.d[div_n] += bn_add_words(wnum.d, wnum.d, sdiv->d, div_n);
+ wnum[div_n] += bn_add_words(wnum, wnum, sdiv->d, div_n);
}
// q is now correct, and wnum has been updated to the running remainder.
