Split BN_uadd into a bn_uadd_fixed.

This is to be used in constant-time RSA CRT.

Bug: 233
Change-Id: Ibade5792324dc6aba38cab6971d255d41fb5eb91
Reviewed-on: https://boringssl-review.googlesource.com/25286
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/add.c b/crypto/fipsmodule/bn/add.c
index cc74510..ece7867 100644
--- a/crypto/fipsmodule/bn/add.c
+++ b/crypto/fipsmodule/bn/add.c
@@ -100,61 +100,38 @@
   return ret;
 }
 
-int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
-  int max, min, dif;
-  BN_ULONG *ap, *bp, *rp, carry, t1, t2;
-  const BIGNUM *tmp;
-
+int bn_uadd_fixed(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
+  // Widths are public, so we normalize to make |a| the larger one.
   if (a->width < b->width) {
-    tmp = a;
+    const BIGNUM *tmp = a;
     a = b;
     b = tmp;
   }
-  max = a->width;
-  min = b->width;
-  dif = max - min;
 
+  int max = a->width;
+  int min = b->width;
   if (!bn_wexpand(r, max + 1)) {
     return 0;
   }
+  r->width = max + 1;
 
-  r->width = max;
-
-  ap = a->d;
-  bp = b->d;
-  rp = r->d;
-
-  carry = bn_add_words(rp, ap, bp, min);
-  rp += min;
-  ap += min;
-  bp += min;
-
-  if (carry) {
-    while (dif) {
-      dif--;
-      t1 = *(ap++);
-      t2 = t1 + 1;
-      *(rp++) = t2;
-      if (t2) {
-        carry = 0;
-        break;
-      }
-    }
-    if (carry) {
-      // carry != 0 => dif == 0
-      *rp = 1;
-      r->width++;
-    }
+  BN_ULONG carry = bn_add_words(r->d, a->d, b->d, min);
+  for (int i = min; i < max; i++) {
+    // |r| and |a| may alias, so use a temporary.
+    BN_ULONG tmp = carry + a->d[i];
+    carry = tmp < a->d[i];
+    r->d[i] = tmp;
   }
 
-  if (dif && rp != ap) {
-    while (dif--) {
-      // copy remaining words if ap != rp
-      *(rp++) = *(ap++);
-    }
-  }
+  r->d[max] = carry;
+  return 1;
+}
 
-  r->neg = 0;
+int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) {
+  if (!bn_uadd_fixed(r, a, b)) {
+    return 0;
+  }
+  bn_set_minimal_width(r);
   return 1;
 }
 
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index b09388a..a8baf4c 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -367,6 +367,10 @@
 // to increase without bound. The corresponding public API functions minimize
 // their outputs to avoid regressing calculator consumers.
 
+// bn_uadd_fixed behaves like |BN_uadd|, but it pessimally sets
+// |r->width| = |a->width| + |b->width| + 1.
+int bn_uadd_fixed(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);
+
 // bn_mul_fixed behaves like |BN_mul|, but it rejects negative inputs and
 // pessimally sets |r->width| to |a->width| + |b->width|, to avoid leaking
 // information about |a| and |b|.