5 files changed, 87 insertions, 67 deletions

diff --git a/src/lib/libcrypto/bn/arch/amd64/bn_arch.h b/src/lib/libcrypto/bn/arch/amd64/bn_arch.h
index 065f6b1c3b..6b7eaf5eee 100644
--- a/src/lib/libcrypto/bn/arch/amd64/bn_arch.h
+++ b/src/lib/libcrypto/bn/arch/amd64/bn_arch.h
@@ -1,4 +1,4 @@
-/*      $OpenBSD: bn_arch.h,v 1.7 2023/01/23 12:17:57 jsing Exp $ */
+/*      $OpenBSD: bn_arch.h,v 1.8 2023/01/28 16:33:34 jsing Exp $ */
 /*
  * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
  *
@@ -15,6 +15,8 @@
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
+#include <openssl/bn.h>
+
 #ifndef HEADER_BN_ARCH_H
 #define HEADER_BN_ARCH_H
 
@@ -36,5 +38,28 @@
 
 #define HAVE_BN_SUB_WORDS
 
+#if defined(__GNUC__)
+#define HAVE_BN_DIV_REM_WORDS_INLINE
+
+static inline void
+bn_div_rem_words_inline(BN_ULONG h, BN_ULONG l, BN_ULONG d, BN_ULONG *out_q,
+    BN_ULONG *out_r)
+{
+        BN_ULONG q, r;
+
+        /*
+         * Unsigned division of %rdx:%rax by d with quotient being stored in
+         * %rax and remainder in %rdx.
+         */
+        __asm__ volatile ("divq %4"
+            : "=a"(q), "=d"(r)
+            : "d"(h), "a"(l), "rm"(d)
+            : "cc");
+
+        *out_q = q;
+        *out_r = r;
+}
+#endif /* __GNUC__ */
+
 #endif
 #endif
diff --git a/src/lib/libcrypto/bn/arch/i386/bn_arch.h b/src/lib/libcrypto/bn/arch/i386/bn_arch.h
index 681c2090a7..e2b4957efc 100644
--- a/src/lib/libcrypto/bn/arch/i386/bn_arch.h
+++ b/src/lib/libcrypto/bn/arch/i386/bn_arch.h
@@ -1,4 +1,4 @@
-/*      $OpenBSD: bn_arch.h,v 1.6 2023/01/23 12:17:57 jsing Exp $ */
+/*      $OpenBSD: bn_arch.h,v 1.7 2023/01/28 16:33:34 jsing Exp $ */
 /*
  * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
  *
@@ -15,6 +15,8 @@
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
+#include <openssl/bn.h>
+
 #ifndef HEADER_BN_ARCH_H
 #define HEADER_BN_ARCH_H
 
@@ -35,5 +37,28 @@
 
 #define HAVE_BN_SUB_WORDS
 
+#if defined(__GNUC__)
+#define HAVE_BN_DIV_REM_WORDS_INLINE
+
+static inline void
+bn_div_rem_words_inline(BN_ULONG h, BN_ULONG l, BN_ULONG d, BN_ULONG *out_q,
+    BN_ULONG *out_r)
+{
+        BN_ULONG q, r;
+
+        /*
+         * Unsigned division of %edx:%eax by d with quotient being stored in
+         * %eax and remainder in %edx.
+         */
+        __asm__ volatile ("divl %4"
+            : "=a"(q), "=d"(r)
+            : "a"(l), "d"(h), "rm"(d)
+            : "cc");
+
+        *out_q = q;
+        *out_r = r;
+}
+#endif /* __GNUC__ */
+
 #endif
 #endif
diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c
index 8ec2e01831..e60fb84062 100644
--- a/src/lib/libcrypto/bn/bn_div.c
+++ b/src/lib/libcrypto/bn/bn_div.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_div.c,v 1.33 2023/01/23 12:02:48 jsing Exp $ */
+/* $OpenBSD: bn_div.c,v 1.34 2023/01/28 16:33:34 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -150,49 +150,30 @@ bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
 #endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
 #endif
 
-#ifndef HAVE_BN_DIV_3_WORDS
+/*
+ * Divide a double word (h:l) by d, returning the quotient q and the remainder
+ * r, such that q * d + r is equal to the numerator.
+ */
+#ifndef HAVE_BN_DIV_REM_WORDS
+#ifndef HAVE_BN_DIV_REM_WORDS_INLINE
+static inline
+bn_div_rem_words_inline(BN_ULONG h, BN_ULONG l, BN_ULONG d, BN_ULONG *out_q,
+    BN_ULONG *out_r)
+{
+        *q = bn_div_words(h, l, d);
+        *r = (l - q * d) & BN_MASK2;
+}
+#endif
 
-#if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM)
-# if defined(__GNUC__) && __GNUC__>=2
-#  if defined(__i386) || defined (__i386__)
-   /*
-    * There were two reasons for implementing this template:
-    * - GNU C generates a call to a function (__udivdi3 to be exact)
-    *   in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to
-    *   understand why...);
-    * - divl doesn't only calculate quotient, but also leaves
-    *   remainder in %edx which we can definitely use here:-)
-    *
-    *                                   <appro@fy.chalmers.se>
-    */
-#undef bn_div_words
-#  define bn_div_words(n0,n1,d0)                \
-        ({  asm volatile (                      \
-                "divl   %4"                     \
-                : "=a"(q), "=d"(rem)            \
-                : "a"(n1), "d"(n0), "g"(d0)     \
-                : "cc");                        \
-            q;                                  \
-        })
-#  define REMAINDER_IS_ALREADY_CALCULATED
-#  elif defined(__x86_64)
-   /*
-    * Same story here, but it's 128-bit by 64-bit division. Wow!
-    *                                   <appro@fy.chalmers.se>
-    */
-#  undef bn_div_words
-#  define bn_div_words(n0,n1,d0)                \
-        ({  asm volatile (                      \
-                "divq   %4"                     \
-                : "=a"(q), "=d"(rem)            \
-                : "a"(n1), "d"(n0), "g"(d0)     \
-                : "cc");                        \
-            q;                                  \
-        })
-#  define REMAINDER_IS_ALREADY_CALCULATED
-#  endif /* __<cpu> */
-# endif /* __GNUC__ */
-#endif /* OPENSSL_NO_ASM */
+void
+bn_div_rem_words(BN_ULONG h, BN_ULONG l, BN_ULONG d, BN_ULONG *out_q,
+    BN_ULONG *out_r)
+{
+        bn_div_rem_words_inline(h, l, d, out_q, out_r);
+}
+#endif
+
+#ifndef HAVE_BN_DIV_3_WORDS
 
 /*
  * Interface is somewhat quirky, |m| is pointer to most significant limb,
@@ -219,19 +200,8 @@ bn_div_3_words(const BN_ULONG *m, BN_ULONG d1, BN_ULONG d0)
 #ifdef BN_LLONG
                 BN_ULLONG t2;
 
-#if defined(BN_DIV2W) && !defined(bn_div_words)
-                q = (BN_ULONG)((((BN_ULLONG)n0 << BN_BITS2) | n1) / d0);
-#else
-                q = bn_div_words(n0, n1, d0);
-#endif
+                bn_div_rem_words(n0, n1, d0, &q, &rem);
 
-#ifndef REMAINDER_IS_ALREADY_CALCULATED
-                /*
-                 * rem doesn't have to be BN_ULLONG. The least we
-                 * know it's less that d0, isn't it?
-                 */
-                rem = (n1 - q * d0) & BN_MASK2;
-#endif
                 t2 = (BN_ULLONG)d1 * q;
 
                 for (;;) {
@@ -245,10 +215,7 @@ bn_div_3_words(const BN_ULONG *m, BN_ULONG d1, BN_ULONG d0)
 #else /* !BN_LLONG */
                 BN_ULONG t2l, t2h;
 
-                q = bn_div_words(n0, n1, d0);
-#ifndef REMAINDER_IS_ALREADY_CALCULATED
-                rem = (n1 - q * d0) & BN_MASK2;
-#endif
+                bn_div_rem_words(n0, n1, d0, &q, &rem);
 
 #if defined(BN_UMULT_LOHI)
                 BN_UMULT_LOHI(t2l, t2h, d1, q);
diff --git a/src/lib/libcrypto/bn/bn_local.h b/src/lib/libcrypto/bn/bn_local.h
index 74e158d6fd..bcd6fa2732 100644
--- a/src/lib/libcrypto/bn/bn_local.h
+++ b/src/lib/libcrypto/bn/bn_local.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_local.h,v 1.5 2023/01/20 17:26:03 jsing Exp $ */
+/* $OpenBSD: bn_local.h,v 1.6 2023/01/28 16:33:34 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -657,12 +657,16 @@ void bn_correct_top(BIGNUM *a);
 int bn_expand(BIGNUM *a, int bits);
 int bn_wexpand(BIGNUM *a, int words);
 
+BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
+    int num);
+BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
+    int num);
 BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w);
 BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w);
 void     bn_sqr_words(BN_ULONG *rp, const BN_ULONG *ap, int num);
 BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
-BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, int num);
-BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, int num);
+void bn_div_rem_words(BN_ULONG h, BN_ULONG l, BN_ULONG d, BN_ULONG *out_q,
+    BN_ULONG *out_r);
 
 int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom);
 int bn_rand_interval(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc);
diff --git a/src/lib/libcrypto/bn/bn_word.c b/src/lib/libcrypto/bn/bn_word.c
index 4663237b05..7077d3ad7a 100644
--- a/src/lib/libcrypto/bn/bn_word.c
+++ b/src/lib/libcrypto/bn/bn_word.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_word.c,v 1.16 2022/11/26 16:08:51 tb Exp $ */
+/* $OpenBSD: bn_word.c,v 1.17 2023/01/28 16:33:34 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -125,8 +125,7 @@ BN_div_word(BIGNUM *a, BN_ULONG w)
                 BN_ULONG l, d;
 
                 l = a->d[i];
-                d = bn_div_words(ret, l, w);
-                ret = (l - ((d*w)&BN_MASK2))&BN_MASK2;
+                bn_div_rem_words(ret, l, w, &d, &ret);
                 a->d[i] = d;
         }
         if ((a->top > 0) && (a->d[a->top - 1] == 0))