From 519d53cbde5b8b75b2de2564dbfbef9f15a1c8a5 Mon Sep 17 00:00:00 2001 From: jsing Date: Sat, 28 Jan 2023 16:33:34 +0000 Subject: [PATCH] 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@ --- lib/libcrypto/bn/arch/amd64/bn_arch.h | 27 ++++++++- lib/libcrypto/bn/arch/i386/bn_arch.h | 27 ++++++++- lib/libcrypto/bn/bn_div.c | 85 ++++++++------------------- lib/libcrypto/bn/bn_local.h | 10 +++- lib/libcrypto/bn/bn_word.c | 5 +- 5 files changed, 87 insertions(+), 67 deletions(-) diff --git a/lib/libcrypto/bn/arch/amd64/bn_arch.h b/lib/libcrypto/bn/arch/amd64/bn_arch.h index 065f6b1c3b4..6b7eaf5eee7 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.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 * @@ -15,6 +15,8 @@ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ +#include + #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/lib/libcrypto/bn/arch/i386/bn_arch.h b/lib/libcrypto/bn/arch/i386/bn_arch.h index 681c2090a70..e2b4957efc2 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.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 * @@ -15,6 +15,8 @@ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ +#include + #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/lib/libcrypto/bn/bn_div.c b/lib/libcrypto/bn/bn_div.c index 8ec2e01831b..e60fb84062c 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.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)< - */ -#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! - * - */ -# 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 /* __ */ -# 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/lib/libcrypto/bn/bn_local.h b/lib/libcrypto/bn/bn_local.h index 74e158d6fd7..bcd6fa27329 100644 --- a/lib/libcrypto/bn/bn_local.h +++ b/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/lib/libcrypto/bn/bn_word.c b/lib/libcrypto/bn/bn_word.c index 4663237b055..7077d3ad7af 100644 --- a/lib/libcrypto/bn/bn_word.c +++ b/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)) -- 2.20.1