Provide bn_div_rem_words() and make use of it.

Provide a function that divides 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. Call this from the three places that currently implement this
themselves.

This is implemented with some slight indirection, which allows for per
architecture implementations, replacing the define/macro tangle, which
messes with variables that are not passed to it.

Also remove a duplicate of bn_div_words() for the BN_ULLONG && BN_DIV2W
case - this is already handled.

ok tb@

1 files changed, 26 insertions, 59 deletions

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);