[Gmp-commit] /var/hg/gmp: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Tue Nov 2 00:43:14 UTC 2021
details: /var/hg/gmp/rev/524b398baadc
changeset: 18269:524b398baadc
user: Torbjorn Granlund <tg at gmplib.org>
date: Tue Nov 02 01:39:46 2021 +0100
description:
Disambiguate an insn.
details: /var/hg/gmp/rev/d8f1f6b7b51f
changeset: 18270:d8f1f6b7b51f
user: Torbjorn Granlund <tg at gmplib.org>
date: Tue Nov 02 01:40:37 2021 +0100
description:
Provide alternative function.
details: /var/hg/gmp/rev/55c556393cb9
changeset: 18271:55c556393cb9
user: Torbjorn Granlund <tg at gmplib.org>
date: Tue Nov 02 01:42:34 2021 +0100
description:
Trivial merge.
diffstat:
ChangeLog | 4 ++
mpn/generic/sec_tabselect.c | 68 +++++++++++++++++++++++++++++++++++++++++++++
mpn/x86/sec_tabselect.asm | 2 +-
mpz/fac_ui.c | 30 ++++++++++++++-----
4 files changed, 95 insertions(+), 9 deletions(-)
diffs (164 lines):
diff -r d343c620e614 -r 55c556393cb9 ChangeLog
--- a/ChangeLog Sun Oct 31 02:09:45 2021 +0100
+++ b/ChangeLog Tue Nov 02 01:42:34 2021 +0100
@@ -1,3 +1,7 @@
+2021-10-31 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpz/fac_ui.c: Save half the products for small values.
+
2021-10-08 Niels Möller <nisse at lysator.liu.se>
* tests/mpn/t-addaddmul.c: Unit test for mpn_addaddmul_1msb0.
diff -r d343c620e614 -r 55c556393cb9 mpn/generic/sec_tabselect.c
--- a/mpn/generic/sec_tabselect.c Sun Oct 31 02:09:45 2021 +0100
+++ b/mpn/generic/sec_tabselect.c Tue Nov 02 01:42:34 2021 +0100
@@ -30,9 +30,15 @@
#include "gmp-impl.h"
+#ifndef SEC_TABSELECT_METHOD
+#define SEC_TABSELECT_METHOD 1
+#endif
+
/* Select entry `which' from table `tab', which has nents entries, each `n'
limbs. Store the selected entry at rp. Reads entire table to avoid
side-channel information leaks. O(n*nents). */
+
+#if SEC_TABSELECT_METHOD == 1
void
mpn_sec_tabselect (volatile mp_limb_t *rp, volatile const mp_limb_t *tab,
mp_size_t n, mp_size_t nents, mp_size_t which)
@@ -60,3 +66,65 @@
rp[i] = (rp[i] & mask) | (tp[i] & ~mask);
}
}
+#endif
+
+#if SEC_TABSELECT_METHOD == 2
+void
+mpn_sec_tabselect (volatile mp_limb_t * restrict rp,
+ volatile const mp_limb_t * restrict tab,
+ mp_size_t n, mp_size_t nents, mp_size_t which)
+{
+ mp_size_t k, i;
+ mp_limb_t mask, r0, r1, r2, r3;
+ volatile const mp_limb_t * restrict tp;
+
+ for (i = 0; i <= n - 4; i += 4)
+ {
+ tp = tab + i;
+ r0 = r1 = r2 = r3 = 0;
+ for (k = 0; k < nents; k++)
+ {
+ mask = (mp_limb_t) ((-(unsigned long) (which ^ k)) >> (BITS_PER_ULONG - 1)) - 1;
+ r0 += tp[0] & mask;
+ r1 += tp[1] & mask;
+ r2 += tp[2] & mask;
+ r3 += tp[3] & mask;
+ tp += n;
+ }
+ rp[0] = r0;
+ rp[1] = r1;
+ rp[2] = r2;
+ rp[3] = r3;
+ rp += 4;
+ }
+
+ if (n & 2 != 0)
+ {
+ tp = tab + n - 2;
+ r0 = r1 = 0;
+ for (k = 0; k < nents; k++)
+ {
+ mask = (mp_limb_t) ((-(unsigned long) (which ^ k)) >> (BITS_PER_ULONG - 1)) - 1;
+ r0 += tp[0] & mask;
+ r1 += tp[1] & mask;
+ tp += n;
+ }
+ rp[0] = r0;
+ rp[1] = r1;
+ rp += 2;
+ }
+
+ if (n & 1 != 0)
+ {
+ tp = tab + n - 1;
+ r0 = r1 = 0;
+ for (k = 0; k < nents; k++)
+ {
+ mask = (mp_limb_t) ((-(unsigned long) (which ^ k)) >> (BITS_PER_ULONG - 1)) - 1;
+ r0 += tp[0] & mask;
+ tp += n;
+ }
+ rp[0] = r0;
+ }
+}
+#endif
diff -r d343c620e614 -r 55c556393cb9 mpn/x86/sec_tabselect.asm
--- a/mpn/x86/sec_tabselect.asm Sun Oct 31 02:09:45 2021 +0100
+++ b/mpn/x86/sec_tabselect.asm Tue Nov 02 01:42:34 2021 +0100
@@ -77,7 +77,7 @@
lea (rp,n,4), rp
lea (tp,n,4), tp
L(outer):
- sub $1, which
+ subl $1, which
sbb mask, mask
mov n, i
diff -r d343c620e614 -r 55c556393cb9 mpz/fac_ui.c
--- a/mpz/fac_ui.c Sun Oct 31 02:09:45 2021 +0100
+++ b/mpz/fac_ui.c Tue Nov 02 01:42:34 2021 +0100
@@ -2,8 +2,8 @@
Contributed to the GNU project by Marco Bodrato.
-Copyright 1991, 1993-1995, 2000-2003, 2011, 2012, 2015 Free Software
-Foundation, Inc.
+Copyright 1991, 1993-1995, 2000-2003, 2011, 2012, 2015, 2021 Free
+Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -68,21 +68,35 @@
mp_limb_t prod, max_prod;
mp_size_t j;
mp_ptr factors;
+ mp_limb_t fac, diff = n - numberof (table);
TMP_SDECL;
TMP_SMARK;
- factors = TMP_SALLOC_LIMBS (2 + (n - numberof (table)) / FACTORS_PER_LIMB);
+ factors = TMP_SALLOC_LIMBS (2 + diff / FACTORS_PER_LIMB);
factors[0] = table[numberof (table)-1];
j = 1;
- prod = n;
+ if ((diff & 1) == 0)
+ {
+ prod = n;
+ /* if (diff != 0) */
+ fac = --n * numberof (table);
+ }
+ else
+ {
+ prod = n * numberof (table);
+ fac = prod + --diff;
+ }
+
#if TUNE_PROGRAM_BUILD
- max_prod = GMP_NUMB_MAX / FAC_DSC_THRESHOLD_LIMIT;
+ max_prod = GMP_NUMB_MAX / (FAC_DSC_THRESHOLD_LIMIT * FAC_DSC_THRESHOLD_LIMIT);
#else
- max_prod = GMP_NUMB_MAX / (FAC_ODD_THRESHOLD | 1);
+ max_prod = GMP_NUMB_MAX /
+ (((FAC_ODD_THRESHOLD + numberof (table) + 1) / 2) *
+ ((FAC_ODD_THRESHOLD + numberof (table)) / 2));
#endif
- while (--n >= numberof (table))
- FACTOR_LIST_STORE (n, prod, max_prod, factors, j);
+ for (;diff != 0; fac += (diff -= 2))
+ FACTOR_LIST_STORE (fac, prod, max_prod, factors, j);
factors[j++] = prod;
mpz_prodlimbs (x, factors, j);
More information about the gmp-commit
mailing list