Reimplement bn_add_words() and bn_sub_words() using bignum primitives.

This removes the effectively duplicate BN_LLONG version of bn_add_words()
and simplifies the code considerably.

ok tb@

2 files changed, 88 insertions, 111 deletions

diff --git a/src/lib/libcrypto/bn/bn_add.c b/src/lib/libcrypto/bn/bn_add.c
index 8ae9bbe854..51b87104cf 100644
--- a/src/lib/libcrypto/bn/bn_add.c
+++ b/src/lib/libcrypto/bn/bn_add.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_add.c,v 1.22 2023/02/13 04:25:37 jsing Exp $ */
+/* $OpenBSD: bn_add.c,v 1.23 2023/02/16 04:42:20 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -64,89 +64,31 @@
 
 #include "bn_arch.h"
 #include "bn_local.h"
+#include "bn_internal.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);
 
+/*
+ * bn_add_words() computes (carry:r[i]) = a[i] + b[i] + carry, where a and b
+ * are both arrays of words. Any carry resulting from the addition is returned.
+ */
 #ifndef HAVE_BN_ADD_WORDS
-#ifdef BN_LLONG
 BN_ULONG
 bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
 {
-        BN_ULLONG ll = 0;
+        BN_ULONG carry = 0;
 
         assert(n >= 0);
         if (n <= 0)
-                return ((BN_ULONG)0);
-
-#ifndef OPENSSL_SMALL_FOOTPRINT
-        while (n & ~3) {
-                ll += (BN_ULLONG)a[0] + b[0];
-                r[0] = (BN_ULONG)ll & BN_MASK2;
-                ll >>= BN_BITS2;
-                ll += (BN_ULLONG)a[1] + b[1];
-                r[1] = (BN_ULONG)ll & BN_MASK2;
-                ll >>= BN_BITS2;
-                ll += (BN_ULLONG)a[2] + b[2];
-                r[2] = (BN_ULONG)ll & BN_MASK2;
-                ll >>= BN_BITS2;
-                ll += (BN_ULLONG)a[3] + b[3];
-                r[3] = (BN_ULONG)ll & BN_MASK2;
-                ll >>= BN_BITS2;
-                a += 4;
-                b += 4;
-                r += 4;
-                n -= 4;
-        }
-#endif
-        while (n) {
-                ll += (BN_ULLONG)a[0] + b[0];
-                r[0] = (BN_ULONG)ll & BN_MASK2;
-                ll >>= BN_BITS2;
-                a++;
-                b++;
-                r++;
-                n--;
-        }
-        return ((BN_ULONG)ll);
-}
-#else /* !BN_LLONG */
-BN_ULONG
-bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
-{
-        BN_ULONG c, l, t;
-
-        assert(n >= 0);
-        if (n <= 0)
-                return ((BN_ULONG)0);
+                return 0;
 
-        c = 0;
 #ifndef OPENSSL_SMALL_FOOTPRINT
         while (n & ~3) {
-                t = a[0];
-                t = (t + c) & BN_MASK2;
-                c = (t < c);
-                l = (t + b[0]) & BN_MASK2;
-                c += (l < t);
-                r[0] = l;
-                t = a[1];
-                t = (t + c) & BN_MASK2;
-                c = (t < c);
-                l = (t + b[1]) & BN_MASK2;
-                c += (l < t);
-                r[1] = l;
-                t = a[2];
-                t = (t + c) & BN_MASK2;
-                c = (t < c);
-                l = (t + b[2]) & BN_MASK2;
-                c += (l < t);
-                r[2] = l;
-                t = a[3];
-                t = (t + c) & BN_MASK2;
-                c = (t < c);
-                l = (t + b[3]) & BN_MASK2;
-                c += (l < t);
-                r[3] = l;
+                bn_addw_addw(a[0], b[0], carry, &carry, &r[0]);
+                bn_addw_addw(a[1], b[1], carry, &carry, &r[1]);
+                bn_addw_addw(a[2], b[2], carry, &carry, &r[2]);
+                bn_addw_addw(a[3], b[3], carry, &carry, &r[3]);
                 a += 4;
                 b += 4;
                 r += 4;
@@ -154,55 +96,37 @@ bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
         }
 #endif
         while (n) {
-                t = a[0];
-                t = (t + c) & BN_MASK2;
-                c = (t < c);
-                l = (t + b[0]) & BN_MASK2;
-                c += (l < t);
-                r[0] = l;
+                bn_addw_addw(a[0], b[0], carry, &carry, &r[0]);
                 a++;
                 b++;
                 r++;
                 n--;
         }
-        return ((BN_ULONG)c);
+        return carry;
 }
-#endif /* !BN_LLONG */
 #endif
 
+/*
+ * bn_sub_words() computes (borrow:r[i]) = a[i] - b[i] - borrow, where a and b
+ * are both arrays of words. Any borrow resulting from the subtraction is
+ * returned.
+ */
 #ifndef HAVE_BN_SUB_WORDS
 BN_ULONG
 bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
 {
-        BN_ULONG t1, t2;
-        int c = 0;
+        BN_ULONG borrow = 0;
 
         assert(n >= 0);
         if (n <= 0)
-                return ((BN_ULONG)0);
+                return 0;
 
 #ifndef OPENSSL_SMALL_FOOTPRINT
-        while (n&~3) {
-                t1 = a[0];
-                t2 = b[0];
-                r[0] = (t1 - t2 - c) & BN_MASK2;
-                if (t1 != t2)
-                        c = (t1 < t2);
-                t1 = a[1];
-                t2 = b[1];
-                r[1] = (t1 - t2 - c) & BN_MASK2;
-                if (t1 != t2)
-                        c = (t1 < t2);
-                t1 = a[2];
-                t2 = b[2];
-                r[2] = (t1 - t2 - c) & BN_MASK2;
-                if (t1 != t2)
-                        c = (t1 < t2);
-                t1 = a[3];
-                t2 = b[3];
-                r[3] = (t1 - t2 - c) & BN_MASK2;
-                if (t1 != t2)
-                        c = (t1 < t2);
+        while (n & ~3) {
+                bn_subw_subw(a[0], b[0], borrow, &borrow, &r[0]);
+                bn_subw_subw(a[1], b[1], borrow, &borrow, &r[1]);
+                bn_subw_subw(a[2], b[2], borrow, &borrow, &r[2]);
+                bn_subw_subw(a[3], b[3], borrow, &borrow, &r[3]);
                 a += 4;
                 b += 4;
                 r += 4;
@@ -210,26 +134,22 @@ bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
         }
 #endif
         while (n) {
-                t1 = a[0];
-                t2 = b[0];
-                r[0] = (t1 - t2 - c) & BN_MASK2;
-                if (t1 != t2)
-                        c = (t1 < t2);
+                bn_subw_subw(a[0], b[0], borrow, &borrow, &r[0]);
                 a++;
                 b++;
                 r++;
                 n--;
         }
-        return (c);
+        return borrow;
 }
 #endif
 
-#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.
  */
+#ifndef HAVE_BN_ADD
 BN_ULONG
 bn_add(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b)
 {
@@ -268,13 +188,13 @@ bn_add(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b)
 }
 #endif
 
-#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.
  */
+#ifndef HAVE_BN_SUB
 BN_ULONG
 bn_sub(BIGNUM *r, int rn, const BIGNUM *a, const BIGNUM *b)
 {
diff --git a/src/lib/libcrypto/bn/bn_internal.h b/src/lib/libcrypto/bn/bn_internal.h
index 12ea3641e6..1b5ab9c42c 100644
--- a/src/lib/libcrypto/bn/bn_internal.h
+++ b/src/lib/libcrypto/bn/bn_internal.h
@@ -1,4 +1,4 @@
-/*      $OpenBSD: bn_internal.h,v 1.4 2023/02/15 04:46:49 tb Exp $ */
+/*      $OpenBSD: bn_internal.h,v 1.5 2023/02/16 04:42:20 jsing Exp $ */
 /*
  * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
  *
@@ -102,6 +102,63 @@ bn_addw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0)
 #endif
 #endif
 
+/*
+ * bn_addw_addw() computes (r1:r0) = a + b + c, where all inputs are single
+ * words, producing a double word result.
+ */
+#ifndef HAVE_BN_ADDW_ADDW
+static inline void
+bn_addw_addw(BN_ULONG a, BN_ULONG b, BN_ULONG c, BN_ULONG *out_r1,
+    BN_ULONG *out_r0)
+{
+        BN_ULONG carry, r1, r0;
+
+        bn_addw(a, b, &r1, &r0);
+        bn_addw(r0, c, &carry, &r0);
+        r1 += carry;
+
+        *out_r1 = r1;
+        *out_r0 = r0;
+}
+#endif
+
+/*
+ * bn_subw() computes r0 = a - b, where both inputs are single words,
+ * producing a single word result and borrow.
+ */
+#ifndef HAVE_BN_SUBW
+static inline void
+bn_subw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_borrow, BN_ULONG *out_r0)
+{
+        BN_ULONG borrow, r0;
+
+        r0 = a - b;
+        borrow = ((r0 | (b & ~a)) & (b | ~a)) >> (BN_BITS2 - 1);
+
+        *out_borrow = borrow;
+        *out_r0 = r0;
+}
+#endif
+
+/*
+ * bn_subw_subw() computes r0 = a - b - c, where all inputs are single words,
+ * producing a single word result and borrow.
+ */
+#ifndef HAVE_BN_SUBW_SUBW
+static inline void
+bn_subw_subw(BN_ULONG a, BN_ULONG b, BN_ULONG c, BN_ULONG *out_borrow,
+    BN_ULONG *out_r0)
+{
+        BN_ULONG b1, b2, r0;
+
+        bn_subw(a, b, &b1, &r0);
+        bn_subw(r0, c, &b2, &r0);
+
+        *out_borrow = b1 + b2;
+        *out_r0 = r0;
+}
+#endif
+
 #ifndef HAVE_BN_UMUL_HILO
 #ifdef BN_LLONG
 static inline void