Simplify and clarify the snum padding logic in BN_div
We can use bn_resize_words, which zeros the extra words and updates the
width in one step. Also clarify what this is achieving. It's to
establish a bunch of invariants that the loop cares about.
Bug: 358687140
Change-Id: Id78e81bc08a1ca506b5d6ef6b01936f860fddd86
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/70175
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Bob Beck <bbe@google.com>
diff --git a/crypto/fipsmodule/bn/div.c b/crypto/fipsmodule/bn/div.c
index 097c5eb..36e9658 100644
--- a/crypto/fipsmodule/bn/div.c
+++ b/crypto/fipsmodule/bn/div.c
@@ -231,27 +231,17 @@
bn_set_minimal_width(snum);
snum->neg = 0;
- // Since we don't want to have special-case logic for the case where snum is
- // larger than sdiv, we pad snum with enough zeroes without changing its
- // value.
- if (snum->width <= sdiv->width + 1) {
- if (!bn_wexpand(snum, sdiv->width + 2)) {
- goto err;
- }
- for (int i = snum->width; i < sdiv->width + 2; i++) {
- snum->d[i] = 0;
- }
- snum->width = sdiv->width + 2;
- } else {
- if (!bn_wexpand(snum, snum->width + 1)) {
- goto err;
- }
- snum->d[snum->width] = 0;
- snum->width++;
+ // Extend |snum| with zeros to satisfy the long division invariants:
+ // - |snum|, minus the extra word, must have at least |div_n| + 1 words.
+ // - |snum|'s most significant word must be zero to guarantee the first loop
+ // iteration works with a prefix greater than |sdiv|. (This is the extra u0
+ // digit in Knuth.)
+ int div_n = sdiv->width;
+ int num_n = snum->width <= div_n + 1 ? div_n + 2 : snum->width + 1;
+ if (!bn_resize_words(snum, num_n)) {
+ goto err;
}
- int div_n = sdiv->width;
- int num_n = snum->width;
int loop = num_n - div_n;
// Lets setup a 'window' into snum
// This is the part that corresponds to the current
