1 files changed, 83 insertions, 1 deletions

diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c
index df4b7517d7..8ec2e01831 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.32 2023/01/20 10:07:52 jsing Exp $ */
+/* $OpenBSD: bn_div.c,v 1.33 2023/01/23 12:02:48 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -56,6 +56,7 @@
  * [including the GNU Public Licence.]
  */
 
+#include <assert.h>
 #include <stdio.h>
 
 #include <openssl/opensslconf.h>
@@ -68,6 +69,87 @@
 
 BN_ULONG bn_div_3_words(const BN_ULONG *m, BN_ULONG d1, BN_ULONG d0);
 
+#ifndef HAVE_BN_DIV_WORDS
+#if defined(BN_LLONG) && defined(BN_DIV2W)
+
+BN_ULONG
+bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
+{
+        return ((BN_ULONG)(((((BN_ULLONG)h) << BN_BITS2)|l)/(BN_ULLONG)d));
+}
+
+#else
+
+/* Divide h,l by d and return the result. */
+/* I need to test this some more :-( */
+BN_ULONG
+bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
+{
+        BN_ULONG dh, dl, q,ret = 0, th, tl, t;
+        int i, count = 2;
+
+        if (d == 0)
+                return (BN_MASK2);
+
+        i = BN_num_bits_word(d);
+        assert((i == BN_BITS2) || (h <= (BN_ULONG)1 << i));
+
+        i = BN_BITS2 - i;
+        if (h >= d)
+                h -= d;
+
+        if (i) {
+                d <<= i;
+                h = (h << i) | (l >> (BN_BITS2 - i));
+                l <<= i;
+        }
+        dh = (d & BN_MASK2h) >> BN_BITS4;
+        dl = (d & BN_MASK2l);
+        for (;;) {
+                if ((h >> BN_BITS4) == dh)
+                        q = BN_MASK2l;
+                else
+                        q = h / dh;
+
+                th = q * dh;
+                tl = dl * q;
+                for (;;) {
+                        t = h - th;
+                        if ((t & BN_MASK2h) ||
+                            ((tl) <= (
+                            (t << BN_BITS4) |
+                            ((l & BN_MASK2h) >> BN_BITS4))))
+                                break;
+                        q--;
+                        th -= dh;
+                        tl -= dl;
+                }
+                t = (tl >> BN_BITS4);
+                tl = (tl << BN_BITS4) & BN_MASK2h;
+                th += t;
+
+                if (l < tl)
+                        th++;
+                l -= tl;
+                if (h < th) {
+                        h += d;
+                        q--;
+                }
+                h -= th;
+
+                if (--count == 0)
+                        break;
+
+                ret = q << BN_BITS4;
+                h = ((h << BN_BITS4) | (l >> BN_BITS4)) & BN_MASK2;
+                l = (l & BN_MASK2l) << BN_BITS4;
+        }
+        ret |= q;
+        return (ret);
+}
+#endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
+#endif
+
 #ifndef HAVE_BN_DIV_3_WORDS
 
 #if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM)