Refactor BN_uadd() and BN_usub().

Unlike bn_add_words()/bn_sub_words(), the s2n-bignum bignum_add() and
bignum_sub() functions correctly handle inputs with differing word
lengths. This means that they can be called directly, without needing to
fix up any remaining words manually.

Split BN_uadd() in two - the default bn_add() implementation calls
bn_add_words(), before handling the carry for any remaining words.
Likewise split BN_usub() in two - the default bn_sub() implementation
calls bn_sub_words(), before handling the borrow for any remaining words.

On amd64, provide an implementation of bn_add() that calls s2n-bignum's
bignum_add() directly, similarly with an implementation of bn_sub() that
calls s2n-bignum's bignum_sub() directly.

ok tb@

3 files changed, 99 insertions, 39 deletions

diff --git a/lib/libcrypto/bn/arch/amd64/bn_arch.c b/lib/libcrypto/bn/arch/amd64/bn_arch.c
index aedefc76e22..dc3000fe8bd 100644
--- a/lib/libcrypto/bn/arch/amd64/bn_arch.c
+++ b/lib/libcrypto/bn/arch/amd64/bn_arch.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bn_arch.c,v 1.2 2023/01/29 14:00:41 jsing Exp $ */
+/*	$OpenBSD: bn_arch.c,v 1.3 2023/02/02 18:39:26 jsing Exp $ */
 /*
  * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
  *
@@ -21,6 +21,15 @@
 #include "bn_local.h"
 #include "s2n_bignum.h"
 
+#ifdef HAVE_BN_ADD
+BN_ULONG
+bn_add(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b)
+{
+	return bignum_add(rn, (uint64_t *)r->d, a->top, (uint64_t *)a->d,
+	    b->top, (uint64_t *)b->d);
+}
+#endif
+
 #ifdef HAVE_BN_ADD_WORDS
 BN_ULONG
 bn_add_words(BN_ULONG *rd, const BN_ULONG *ad, const BN_ULONG *bd, int n)
@@ -30,6 +39,15 @@ bn_add_words(BN_ULONG *rd, const BN_ULONG *ad, const BN_ULONG *bd, int n)
 }
 #endif
 
+#ifdef HAVE_BN_SUB
+BN_ULONG
+bn_sub(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b)
+{
+	return bignum_sub(rn, (uint64_t *)r->d, a->top, (uint64_t *)a->d,
+	    b->top, (uint64_t *)b->d);
+}
+#endif
+
 #ifdef HAVE_BN_SUB_WORDS
 BN_ULONG
 bn_sub_words(BN_ULONG *rd, const BN_ULONG *ad, const BN_ULONG *bd, int n)
diff --git a/lib/libcrypto/bn/arch/amd64/bn_arch.h b/lib/libcrypto/bn/arch/amd64/bn_arch.h
index 9e4b6b94426..c41a84409b6 100644
--- a/lib/libcrypto/bn/arch/amd64/bn_arch.h
+++ b/lib/libcrypto/bn/arch/amd64/bn_arch.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: bn_arch.h,v 1.9 2023/01/31 05:53:49 jsing Exp $ */
+/*	$OpenBSD: bn_arch.h,v 1.10 2023/02/02 18:39:26 jsing Exp $ */
 /*
  * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
  *
@@ -22,6 +22,7 @@
 
 #ifndef OPENSSL_NO_ASM
 
+#define HAVE_BN_ADD
 #define HAVE_BN_ADD_WORDS
 
 #define HAVE_BN_DIV_WORDS
@@ -36,6 +37,7 @@
 #define HAVE_BN_SQR_COMBA8
 #define HAVE_BN_SQR_WORDS
 
+#define HAVE_BN_SUB
 #define HAVE_BN_SUB_WORDS
 
 #if defined(__GNUC__)
diff --git a/lib/libcrypto/bn/bn_add.c b/lib/libcrypto/bn/bn_add.c
index cfc04fd0323..dc525db0840 100644
--- a/lib/libcrypto/bn/bn_add.c
+++ b/lib/libcrypto/bn/bn_add.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_add.c,v 1.20 2023/01/31 05:16:52 jsing Exp $ */
+/* $OpenBSD: bn_add.c,v 1.21 2023/02/02 18:39:26 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -57,6 +57,7 @@
  */
 
 #include <assert.h>
+#include <limits.h>
 #include <stdio.h>
 
 #include <openssl/err.h>
@@ -64,6 +65,9 @@
 #include "bn_arch.h"
 #include "bn_local.h"
 
+BN_ULONG bn_add(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b);
+BN_ULONG bn_sub(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b);
+
 #ifndef HAVE_BN_ADD_WORDS
 #ifdef BN_LLONG
 BN_ULONG
@@ -220,13 +224,18 @@ bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
 }
 #endif
 
-int
-BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
+#ifndef HAVE_BN_ADD
+/*
+ * bn_add() computes a + b, storing the result in r (which may be the same as a
+ * or b). The caller must ensure that r has been expanded to max(a->top, b->top)
+ * words. Any carry resulting from the addition is returned.
+ */
+BN_ULONG
+bn_add(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b)
 {
-	int max, min, dif;
-	const BN_ULONG *ap, *bp;
 	BN_ULONG *rp, carry, t1, t2;
-
+	const BN_ULONG *ap, *bp;
+	int max, min, dif;
 
 	if (a->top < b->top) {
 		const BIGNUM *tmp;
@@ -239,11 +248,6 @@ BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 	min = b->top;
 	dif = max - min;
 
-	if (!bn_wexpand(r, max + 1))
-		return 0;
-
-	r->top = max;
-
 	ap = a->d;
 	bp = b->d;
 	rp = r->d;
@@ -259,42 +263,34 @@ BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 		*(rp++) = t2;
 		carry &= (t2 == 0);
 	}
-	*rp = carry;
-	r->top += carry;
 
-	r->neg = 0;
-	return 1;
+	return carry;
 }
+#endif
 
-int
-BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
+#ifndef HAVE_BN_SUB
+/*
+ * bn_sub() computes a - b, storing the result in r (which may be the same as a
+ * or b). The caller must ensure that the number of words in a is greater than
+ * or equal to the number of words in b and that r has been expanded to
+ * a->top words. Any borrow resulting from the subtraction is returned.
+ */
+BN_ULONG
+bn_sub(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b)
 {
-	int max, min, dif;
-	const BN_ULONG *ap, *bp;
 	BN_ULONG t1, t2, borrow, *rp;
-
+	const BN_ULONG *ap, *bp;
+	int max, min, dif;
 
 	max = a->top;
 	min = b->top;
 	dif = max - min;
 
-	if (dif < 0) {
-		BNerror(BN_R_ARG2_LT_ARG3);
-		return 0;
-	}
-
-	if (!bn_wexpand(r, max))
-		return 0;
-
 	ap = a->d;
 	bp = b->d;
 	rp = r->d;
 
 	borrow = bn_sub_words(rp, ap, bp, min);
-	if (dif == 0 && borrow > 0) {
-		BNerror(BN_R_ARG2_LT_ARG3);
-		return 0;
-	}
 	ap += min;
 	rp += min;
 
@@ -306,12 +302,58 @@ BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 		borrow &= (t1 == 0);
 	}
 
-	while (max > 0 && *--rp == 0)
-		max--;
+	return borrow;
+}
+#endif
+
+int
+BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
+{
+	BN_ULONG carry;
+	int rn;
+
+	if ((rn = a->top) < b->top)
+		rn = b->top;
+	if (rn == INT_MAX)
+		return 0;
+	if (!bn_wexpand(r, rn + 1))
+		return 0;
+
+	carry = bn_add(r, rn, a, b);
+	r->d[rn] = carry;
+
+	r->top = rn + (carry & 1);
+	r->neg = 0;
+
+	return 1;
+}
+
+int
+BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
+{
+	BN_ULONG borrow;
+	int rn;
+
+	if (a->top < b->top) {
+		BNerror(BN_R_ARG2_LT_ARG3);
+		return 0;
+	}
+	rn = a->top;
+
+	if (!bn_wexpand(r, rn))
+		return 0;
 
-	r->top = max;
+	borrow = bn_sub(r, rn, a, b);
+	if (borrow > 0) {
+		BNerror(BN_R_ARG2_LT_ARG3);
+		return 0;
+	}
+
+	r->top = rn;
 	r->neg = 0;
+
 	bn_correct_top(r);
+
 	return 1;
 }
 
@@ -320,7 +362,6 @@ BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 {
 	int ret, r_neg;
 
-
 	if (a->neg == b->neg) {
 		r_neg = a->neg;
 		ret = BN_uadd(r, a, b);
@@ -349,7 +390,6 @@ BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 {
 	int ret, r_neg;
 
-
 	if (a->neg != b->neg) {
 		r_neg = a->neg;
 		ret = BN_uadd(r, a, b);