From 2c5f73fa46dd4d5c09eaf03038764be3180f3194 Mon Sep 17 00:00:00 2001 From: jsing Date: Mon, 23 Jan 2023 12:02:48 +0000 Subject: [PATCH] Move bn_div_words from bn_asm.c to bn_div.c. This is wrapped with #ifndef HAVE_BN_DIV_WORDS, which are defined for architectures that provide their own assembly versions. --- lib/libcrypto/bn/arch/amd64/bn_arch.h | 4 +- lib/libcrypto/bn/arch/i386/bn_arch.h | 4 +- lib/libcrypto/bn/arch/mips64/bn_arch.h | 3 +- lib/libcrypto/bn/arch/powerpc/bn_arch.h | 4 +- lib/libcrypto/bn/arch/sparc/bn_arch.h | 4 +- lib/libcrypto/bn/bn_asm.c | 81 +----------------------- lib/libcrypto/bn/bn_div.c | 84 ++++++++++++++++++++++++- 7 files changed, 98 insertions(+), 86 deletions(-) diff --git a/lib/libcrypto/bn/arch/amd64/bn_arch.h b/lib/libcrypto/bn/arch/amd64/bn_arch.h index fd4a6cde7ab..2d11fbd7c22 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.4 2023/01/23 10:31:03 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.5 2023/01/23 12:02:48 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -22,6 +22,8 @@ #define HAVE_BN_ADD_WORDS +#define HAVE_BN_DIV_WORDS + #define HAVE_BN_MUL_COMBA4 #define HAVE_BN_MUL_COMBA8 diff --git a/lib/libcrypto/bn/arch/i386/bn_arch.h b/lib/libcrypto/bn/arch/i386/bn_arch.h index ab35efd56f5..18d7e519ec6 100644 --- a/lib/libcrypto/bn/arch/i386/bn_arch.h +++ b/lib/libcrypto/bn/arch/i386/bn_arch.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_arch.h,v 1.3 2023/01/23 10:31:03 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.4 2023/01/23 12:02:48 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -22,6 +22,8 @@ #define HAVE_BN_ADD_WORDS +#define HAVE_BN_DIV_WORDS + #define HAVE_BN_MUL_COMBA4 #define HAVE_BN_MUL_COMBA8 diff --git a/lib/libcrypto/bn/arch/mips64/bn_arch.h b/lib/libcrypto/bn/arch/mips64/bn_arch.h index e22d882970a..f53c75472c1 100644 --- a/lib/libcrypto/bn/arch/mips64/bn_arch.h +++ b/lib/libcrypto/bn/arch/mips64/bn_arch.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_arch.h,v 1.4 2023/01/23 10:31:03 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.5 2023/01/23 12:02:48 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -22,6 +22,7 @@ #define HAVE_BN_ADD_WORDS +#define HAVE_BN_DIV_WORDS #define HAVE_BN_DIV_3_WORDS #define HAVE_BN_MUL_COMBA4 diff --git a/lib/libcrypto/bn/arch/powerpc/bn_arch.h b/lib/libcrypto/bn/arch/powerpc/bn_arch.h index ab35efd56f5..18d7e519ec6 100644 --- a/lib/libcrypto/bn/arch/powerpc/bn_arch.h +++ b/lib/libcrypto/bn/arch/powerpc/bn_arch.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_arch.h,v 1.3 2023/01/23 10:31:03 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.4 2023/01/23 12:02:48 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -22,6 +22,8 @@ #define HAVE_BN_ADD_WORDS +#define HAVE_BN_DIV_WORDS + #define HAVE_BN_MUL_COMBA4 #define HAVE_BN_MUL_COMBA8 diff --git a/lib/libcrypto/bn/arch/sparc/bn_arch.h b/lib/libcrypto/bn/arch/sparc/bn_arch.h index ab35efd56f5..18d7e519ec6 100644 --- a/lib/libcrypto/bn/arch/sparc/bn_arch.h +++ b/lib/libcrypto/bn/arch/sparc/bn_arch.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_arch.h,v 1.3 2023/01/23 10:31:03 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.4 2023/01/23 12:02:48 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -22,6 +22,8 @@ #define HAVE_BN_ADD_WORDS +#define HAVE_BN_DIV_WORDS + #define HAVE_BN_MUL_COMBA4 #define HAVE_BN_MUL_COMBA8 diff --git a/lib/libcrypto/bn/bn_asm.c b/lib/libcrypto/bn/bn_asm.c index 4224396c00b..a7f288fc1c8 100644 --- a/lib/libcrypto/bn/bn_asm.c +++ b/lib/libcrypto/bn/bn_asm.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_asm.c,v 1.20 2023/01/23 10:31:03 jsing Exp $ */ +/* $OpenBSD: bn_asm.c,v 1.21 2023/01/23 12:02:48 jsing Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -246,85 +246,6 @@ bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n) #endif /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */ -#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) */ - #if defined(BN_MUL_COMBA) && !defined(OPENSSL_SMALL_FOOTPRINT) #ifdef OPENSSL_NO_ASM diff --git a/lib/libcrypto/bn/bn_div.c b/lib/libcrypto/bn/bn_div.c index df4b7517d71..8ec2e01831b 100644 --- a/lib/libcrypto/bn/bn_div.c +++ b/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 #include #include @@ -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) -- 2.20.1