From 82c46216ca9a164ad34bef5982826b8640035ae8 Mon Sep 17 00:00:00 2001 From: jsing Date: Thu, 16 Feb 2023 10:41:03 +0000 Subject: [PATCH] Rename bn_umul_hilo() to bn_mulw(). This keeps the naming consistent with the other bignum primitives that have been recently introduced. Also, use 1/0 intead of h/l (e.g. a1 instead of ah), as this keeps consistency with other primitives and allows for naming that works with double word, triple word and quadruple word inputs/outputs. Discussed with tb@ --- lib/libcrypto/bn/arch/aarch64/bn_arch.h | 14 +-- lib/libcrypto/bn/arch/alpha/bn_arch.h | 14 +-- lib/libcrypto/bn/arch/amd64/bn_arch.h | 14 +-- lib/libcrypto/bn/arch/i386/bn_arch.h | 14 +-- lib/libcrypto/bn/arch/powerpc64/bn_arch.h | 14 +-- lib/libcrypto/bn/arch/riscv64/bn_arch.h | 14 +-- lib/libcrypto/bn/bn_div.c | 4 +- lib/libcrypto/bn/bn_internal.h | 114 +++++++++++----------- lib/libcrypto/bn/bn_sqr.c | 12 +-- 9 files changed, 109 insertions(+), 105 deletions(-) diff --git a/lib/libcrypto/bn/arch/aarch64/bn_arch.h b/lib/libcrypto/bn/arch/aarch64/bn_arch.h index 7592971dc07..cc456848c97 100644 --- a/lib/libcrypto/bn/arch/aarch64/bn_arch.h +++ b/lib/libcrypto/bn/arch/aarch64/bn_arch.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_arch.h,v 1.3 2023/02/04 11:48:55 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.4 2023/02/16 10:41:03 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -23,20 +23,20 @@ #ifndef OPENSSL_NO_ASM #if defined(__GNUC__) -#define HAVE_BN_UMUL_HILO +#define HAVE_BN_MULW static inline void -bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) +bn_mulw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) { - BN_ULONG h, l; + BN_ULONG r1, r0; /* Unsigned multiplication using a umulh/mul pair. */ __asm__ ("umulh %0, %2, %3; mul %1, %2, %3" - : "=&r"(h), "=r"(l) + : "=&r"(r1), "=r"(r0) : "r"(a), "r"(b)); - *out_h = h; - *out_l = l; + *out_r1 = r1; + *out_r0 = r0; } #endif /* __GNUC__ */ diff --git a/lib/libcrypto/bn/arch/alpha/bn_arch.h b/lib/libcrypto/bn/arch/alpha/bn_arch.h index 0f7c582fdf4..5bf4ba8722c 100644 --- a/lib/libcrypto/bn/arch/alpha/bn_arch.h +++ b/lib/libcrypto/bn/arch/alpha/bn_arch.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_arch.h,v 1.3 2023/02/04 11:48:55 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.4 2023/02/16 10:41:03 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -22,20 +22,20 @@ #if 0 /* Needs testing and enabling. */ #if defined(__GNUC__) -#define HAVE_BN_UMUL_HILO +#define HAVE_BN_MULW static inline void -bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) +bn_mulw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) { - BN_ULONG h, l; + BN_ULONG r1, r0; /* Unsigned multiplication using a umulh/mulq pair. */ __asm__ ("umulh %2, %3, %0; mulq %2, %3, %1" - : "=&r"(h), "=r"(l) + : "=&r"(r1), "=r"(r0) : "r"(a), "r"(b)); - *out_h = h; - *out_l = l; + *out_r1 = r1; + *out_r0 = r0; } #endif /* __GNUC__ */ #endif diff --git a/lib/libcrypto/bn/arch/amd64/bn_arch.h b/lib/libcrypto/bn/arch/amd64/bn_arch.h index 637903077a0..80f73bf15f6 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.11 2023/02/04 14:00:18 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.12 2023/02/16 10:41:03 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -63,24 +63,24 @@ bn_div_rem_words_inline(BN_ULONG h, BN_ULONG l, BN_ULONG d, BN_ULONG *out_q, #endif /* __GNUC__ */ #if defined(__GNUC__) -#define HAVE_BN_UMUL_HILO +#define HAVE_BN_MULW static inline void -bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) +bn_mulw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) { - BN_ULONG h, l; + BN_ULONG r1, r0; /* * Unsigned multiplication of %rax, with the double word result being * stored in %rdx:%rax. */ __asm__ ("mulq %3" - : "=d"(h), "=a"(l) + : "=d"(r1), "=a"(r0) : "a"(a), "rm"(b) : "cc"); - *out_h = h; - *out_l = l; + *out_r1 = r1; + *out_r0 = r0; } #endif /* __GNUC__ */ diff --git a/lib/libcrypto/bn/arch/i386/bn_arch.h b/lib/libcrypto/bn/arch/i386/bn_arch.h index 268c51e41aa..eef519fcc76 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.8 2023/01/31 05:53:49 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.9 2023/02/16 10:41:03 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -61,24 +61,24 @@ bn_div_rem_words_inline(BN_ULONG h, BN_ULONG l, BN_ULONG d, BN_ULONG *out_q, #endif /* __GNUC__ */ #if defined(__GNUC__) -#define HAVE_BN_UMUL_HILO +#define HAVE_BN_MULW static inline void -bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) +bn_mulw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) { - BN_ULONG h, l; + BN_ULONG r1, r0; /* * Unsigned multiplication of %eax, with the double word result being * stored in %edx:%eax. */ __asm__ ("mull %3" - : "=d"(h), "=a"(l) + : "=d"(r1), "=a"(r0) : "a"(a), "rm"(b) : "cc"); - *out_h = h; - *out_l = l; + *out_r1 = r1; + *out_r0 = r0; } #endif /* __GNUC__ */ diff --git a/lib/libcrypto/bn/arch/powerpc64/bn_arch.h b/lib/libcrypto/bn/arch/powerpc64/bn_arch.h index 92e16e9f9c9..18bac203eb2 100644 --- a/lib/libcrypto/bn/arch/powerpc64/bn_arch.h +++ b/lib/libcrypto/bn/arch/powerpc64/bn_arch.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_arch.h,v 1.3 2023/02/04 11:48:55 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.4 2023/02/16 10:41:03 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -22,20 +22,20 @@ #if 0 /* Needs testing and enabling. */ #if defined(__GNUC__) -#define HAVE_BN_UMUL_HILO +#define HAVE_BN_MULW static inline void -bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) +bn_mulw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) { - BN_ULONG h, l; + BN_ULONG r1, r0; /* Unsigned multiplication using a mulhdu/mul pair. */ __asm__ ("mulhdu %0, %2, %3; mul %1, %2, %3" - : "=&r"(h), "=r"(l) + : "=&r"(r1), "=r"(r0) : "r"(a), "r"(b)); - *out_h = h; - *out_l = l; + *out_r1 = r1; + *out_r0 = r0; } #endif /* __GNUC__ */ #endif diff --git a/lib/libcrypto/bn/arch/riscv64/bn_arch.h b/lib/libcrypto/bn/arch/riscv64/bn_arch.h index 36cf3a4f66c..354774cde3d 100644 --- a/lib/libcrypto/bn/arch/riscv64/bn_arch.h +++ b/lib/libcrypto/bn/arch/riscv64/bn_arch.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_arch.h,v 1.3 2023/02/04 11:48:55 jsing Exp $ */ +/* $OpenBSD: bn_arch.h,v 1.4 2023/02/16 10:41:03 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -22,12 +22,12 @@ #if 0 /* Needs testing and enabling. */ #if defined(__GNUC__) -#define HAVE_BN_UMUL_HILO +#define HAVE_BN_MULW static inline void -bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) +bn_mulw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) { - BN_ULONG h, l; + BN_ULONG r1, r0; /* * Unsigned multiplication using a mulh/mul pair. Note that the order @@ -35,11 +35,11 @@ bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) * into a single operation. */ __asm__ ("mulh %0, %2, %3; mul %1, %2, %3" - : "=&r"(h), "=r"(l) + : "=&r"(r1), "=r"(r0) : "r"(a), "r"(b)); - *out_h = h; - *out_l = l; + *out_r1 = r1; + *out_r0 = r0; } #endif /* __GNUC__ */ #endif diff --git a/lib/libcrypto/bn/bn_div.c b/lib/libcrypto/bn/bn_div.c index 686b957eb5a..692e6184070 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.38 2023/02/14 18:19:27 jsing Exp $ */ +/* $OpenBSD: bn_div.c,v 1.39 2023/02/16 10:41:03 jsing Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -204,7 +204,7 @@ bn_div_3_words(const BN_ULONG *m, BN_ULONG d1, BN_ULONG d0) /* n0 < d0 */ bn_div_rem_words(n0, n1, d0, &q, &rem); - bn_umul_hilo(d1, q, &t2h, &t2l); + bn_mulw(d1, q, &t2h, &t2l); for (;;) { if (t2h < rem || (t2h == rem && t2l <= m[-2])) diff --git a/lib/libcrypto/bn/bn_internal.h b/lib/libcrypto/bn/bn_internal.h index 64240555d1c..2872e211854 100644 --- a/lib/libcrypto/bn/bn_internal.h +++ b/lib/libcrypto/bn/bn_internal.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_internal.h,v 1.6 2023/02/16 10:02:02 jsing Exp $ */ +/* $OpenBSD: bn_internal.h,v 1.7 2023/02/16 10:41:03 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -159,17 +159,21 @@ bn_subw_subw(BN_ULONG a, BN_ULONG b, BN_ULONG c, BN_ULONG *out_borrow, } #endif -#ifndef HAVE_BN_UMUL_HILO +/* + * bn_mulw() computes (r1:r0) = a * b, where both inputs are single words, + * producing a double word result. + */ +#ifndef HAVE_BN_MULW #ifdef BN_LLONG static inline void -bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) +bn_mulw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) { BN_ULLONG r; r = (BN_ULLONG)a * (BN_ULLONG)b; - *out_h = r >> BN_BITS2; - *out_l = r & BN_MASK2; + *out_r1 = r >> BN_BITS2; + *out_r0 = r & BN_MASK2; } #else /* !BN_LLONG */ @@ -193,38 +197,38 @@ bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) */ #if 1 static inline void -bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) +bn_mulw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) { - BN_ULONG ah, al, bh, bl, h, l, x, c1, c2; + BN_ULONG a1, a0, b1, b0, r1, r0, c1, c2, x; - ah = a >> BN_BITS4; - al = a & BN_MASK2l; - bh = b >> BN_BITS4; - bl = b & BN_MASK2l; + a1 = a >> BN_BITS4; + a0 = a & BN_MASK2l; + b1 = b >> BN_BITS4; + b0 = b & BN_MASK2l; - h = ah * bh; - l = al * bl; + r1 = a1 * b1; + r0 = a0 * b0; - /* (ah * bl) << BN_BITS4, partition the result across h:l with carry. */ - x = ah * bl; - h += x >> BN_BITS4; + /* (a1 * b0) << BN_BITS4, partition the result across r1:r0 with carry. */ + x = a1 * b0; + r1 += x >> BN_BITS4; x <<= BN_BITS4; - c1 = l | x; - c2 = l & x; - l += x; - h += ((c1 & ~l) | c2) >> (BN_BITS2 - 1); /* carry */ - - /* (bh * al) << BN_BITS4, partition the result across h:l with carry. */ - x = bh * al; - h += x >> BN_BITS4; + c1 = r0 | x; + c2 = r0 & x; + r0 += x; + r1 += ((c1 & ~r0) | c2) >> (BN_BITS2 - 1); /* carry */ + + /* (b1 * a0) << BN_BITS4, partition the result across r1:r0 with carry. */ + x = b1 * a0; + r1 += x >> BN_BITS4; x <<= BN_BITS4; - c1 = l | x; - c2 = l & x; - l += x; - h += ((c1 & ~l) | c2) >> (BN_BITS2 - 1); /* carry */ + c1 = r0 | x; + c2 = r0 & x; + r0 += x; + r1 += ((c1 & ~r0) | c2) >> (BN_BITS2 - 1); /* carry */ - *out_h = h; - *out_l = l; + *out_r1 = r1; + *out_r0 = r0; } #else @@ -236,62 +240,62 @@ bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) * implementations should eventually be removed. */ static inline void -bn_umul_hilo(BN_ULONG a, BN_ULONG b, BN_ULONG *out_h, BN_ULONG *out_l) +bn_mulw(BN_ULONG a, BN_ULONG b, BN_ULONG *out_r1, BN_ULONG *out_r0) { - BN_ULONG ah, bh, al, bl, x, h, l; + BN_ULONG a1, a0, b1, b0, r1, r0, x; BN_ULONG acc0, acc1, acc2, acc3; - ah = a >> BN_BITS4; - bh = b >> BN_BITS4; - al = a & BN_MASK2l; - bl = b & BN_MASK2l; + a1 = a >> BN_BITS4; + b1 = b >> BN_BITS4; + a0 = a & BN_MASK2l; + b0 = b & BN_MASK2l; - h = ah * bh; - l = al * bl; + r1 = a1 * b1; + r0 = a0 * b0; - acc0 = l & BN_MASK2l; - acc1 = l >> BN_BITS4; - acc2 = h & BN_MASK2l; - acc3 = h >> BN_BITS4; + acc0 = r0 & BN_MASK2l; + acc1 = r0 >> BN_BITS4; + acc2 = r1 & BN_MASK2l; + acc3 = r1 >> BN_BITS4; - /* (ah * bl) << BN_BITS4, partition the result across h:l. */ - x = ah * bl; + /* (a1 * b0) << BN_BITS4, partition the result across r1:r0. */ + x = a1 * b0; acc1 += x & BN_MASK2l; acc2 += (acc1 >> BN_BITS4) + (x >> BN_BITS4); acc1 &= BN_MASK2l; acc3 += acc2 >> BN_BITS4; acc2 &= BN_MASK2l; - /* (bh * al) << BN_BITS4, partition the result across h:l. */ - x = bh * al; + /* (b1 * a0) << BN_BITS4, partition the result across r1:r0. */ + x = b1 * a0; acc1 += x & BN_MASK2l; acc2 += (acc1 >> BN_BITS4) + (x >> BN_BITS4); acc1 &= BN_MASK2l; acc3 += acc2 >> BN_BITS4; acc2 &= BN_MASK2l; - *out_h = (acc3 << BN_BITS4) | acc2; - *out_l = (acc1 << BN_BITS4) | acc0; + *out_r1 = (acc3 << BN_BITS4) | acc2; + *out_r0 = (acc1 << BN_BITS4) | acc0; } #endif #endif /* !BN_LLONG */ #endif -#ifndef HAVE_BN_UMUL_LO +#ifndef HAVE_BN_MULW_LO static inline BN_ULONG -bn_umul_lo(BN_ULONG a, BN_ULONG b) +bn_mulw_lo(BN_ULONG a, BN_ULONG b) { return a * b; } #endif -#ifndef HAVE_BN_UMUL_HI +#ifndef HAVE_BN_MULW_HI static inline BN_ULONG -bn_umul_hi(BN_ULONG a, BN_ULONG b) +bn_mulw_hi(BN_ULONG a, BN_ULONG b) { BN_ULONG h, l; - bn_umul_hilo(a, b, &h, &l); + bn_mulw(a, b, &h, &l); return h; } @@ -308,7 +312,7 @@ bn_mulw_addw(BN_ULONG a, BN_ULONG b, BN_ULONG c, BN_ULONG *out_r1, { BN_ULONG carry, r1, r0; - bn_umul_hilo(a, b, &r1, &r0); + bn_mulw(a, b, &r1, &r0); bn_addw(r0, c, &carry, &r0); r1 += carry; @@ -350,7 +354,7 @@ bn_mulw_addtw(BN_ULONG a, BN_ULONG b, BN_ULONG c2, BN_ULONG c1, BN_ULONG c0, { BN_ULONG carry, r2, r1, r0, x1, x0; - bn_umul_hilo(a, b, &x1, &x0); + bn_mulw(a, b, &x1, &x0); bn_addw(c0, x0, &carry, &r0); x1 += carry; bn_addw(c1, x1, &carry, &r1); diff --git a/lib/libcrypto/bn/bn_sqr.c b/lib/libcrypto/bn/bn_sqr.c index 5332d17f6b2..f649b9bce87 100644 --- a/lib/libcrypto/bn/bn_sqr.c +++ b/lib/libcrypto/bn/bn_sqr.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_sqr.c,v 1.25 2023/02/13 04:25:37 jsing Exp $ */ +/* $OpenBSD: bn_sqr.c,v 1.26 2023/02/16 10:41:03 jsing Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -193,17 +193,17 @@ bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n) #ifndef OPENSSL_SMALL_FOOTPRINT while (n & ~3) { - bn_umul_hilo(a[0], a[0], &r[1], &r[0]); - bn_umul_hilo(a[1], a[1], &r[3], &r[2]); - bn_umul_hilo(a[2], a[2], &r[5], &r[4]); - bn_umul_hilo(a[3], a[3], &r[7], &r[6]); + bn_mulw(a[0], a[0], &r[1], &r[0]); + bn_mulw(a[1], a[1], &r[3], &r[2]); + bn_mulw(a[2], a[2], &r[5], &r[4]); + bn_mulw(a[3], a[3], &r[7], &r[6]); a += 4; r += 8; n -= 4; } #endif while (n) { - bn_umul_hilo(a[0], a[0], &r[1], &r[0]); + bn_mulw(a[0], a[0], &r[1], &r[0]); a++; r += 2; n--; -- 2.20.1