[Gmp-commit] /var/hg/gmp: 7 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Tue Feb 15 09:18:48 CET 2022
details: /var/hg/gmp/rev/f17d1ba07fd6
changeset: 18303:f17d1ba07fd6
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Sun Feb 13 23:03:57 2022 +0100
description:
mpz/import.c: Remove now unused label
details: /var/hg/gmp/rev/1450eccad11c
changeset: 18304:1450eccad11c
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Feb 14 14:57:38 2022 +0100
description:
mpz/gcd_ui.c: Handle NULL in (v > GMP_NUMB_MAX) branch (unused)
details: /var/hg/gmp/rev/81696abce164
changeset: 18305:81696abce164
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Feb 15 08:42:14 2022 +0100
description:
mpn/generic/strongfibo.c: Correct condition in #if
details: /var/hg/gmp/rev/7174048e10e9
changeset: 18306:7174048e10e9
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Feb 15 08:53:21 2022 +0100
description:
mpn/generic/mulmod_bknp1.c: New file, with mpn_{mul,sqr}mod_bknp1
configure.ac: Compile it
gmp-impl.h: Define new functions
details: /var/hg/gmp/rev/b1043b213bc5
changeset: 18307:b1043b213bc5
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Feb 15 08:57:56 2022 +0100
description:
tests/mpn/t-{mul,sqr}mod_bknp1.c: New tests for mpn_{mul,sqr}mod_bknp1
tests/mpn/Makefile.ami (check_PROGRAMS): Compile and run new tests
details: /var/hg/gmp/rev/9c2f515b6a2f
changeset: 18308:9c2f515b6a2f
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Feb 15 09:04:59 2022 +0100
description:
tune/: tune/speed support for mpn_{mul,sqr}mod_bknp1
details: /var/hg/gmp/rev/f4f4f6030f8f
changeset: 18309:f4f4f6030f8f
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Tue Feb 15 09:18:40 2022 +0100
description:
Trivial merge
diffstat:
config.guess | 4 +-
configure.ac | 2 +-
gmp-impl.h | 63 +++++
mpn/generic/mulmod_bknp1.c | 501 +++++++++++++++++++++++++++++++++++++++++++++
mpn/generic/strongfibo.c | 3 +-
mpz/gcd_ui.c | 12 +-
mpz/import.c | 1 -
tests/mpn/Makefile.am | 1 +
tests/mpn/t-mulmod_bknp1.c | 195 +++++++++++++++++
tests/mpn/t-sqrmod_bknp1.c | 235 +++++++++++++++++++++
tune/common.c | 52 ++++
tune/speed.c | 5 +
tune/speed.h | 68 ++++++
13 files changed, 1135 insertions(+), 7 deletions(-)
diffs (truncated from 1274 to 300 lines):
diff -r ed0406cf3c70 -r f4f4f6030f8f config.guess
--- a/config.guess Wed Feb 02 19:16:36 2022 +0100
+++ b/config.guess Tue Feb 15 09:18:40 2022 +0100
@@ -923,13 +923,15 @@
else if (model == 0x7a) cpu_64bit = 1, modelstr = "goldmont"; /* Goldmont Plus */
else if (model == 0x7d) cpu_64bit = 1, cpu_avx=1, modelstr = "icelake"; /* Ice Lake Y */
else if (model == 0x7e) cpu_64bit = 1, cpu_avx=1, modelstr = "icelake"; /* Ice Lake U */
- else if (model == 0x9e) cpu_64bit = 1, cpu_avx=1, modelstr = "icelake"; /* Ice Lake ? */
+ else if (model == 0x8a) cpu_64bit = 1, modelstr = "goldmont"; /* Tremont */
else if (model == 0x8c) cpu_64bit = 1, cpu_avx=1, modelstr = "tigerlake"; /* Tiger Lake U */
else if (model == 0x8d) cpu_64bit = 1, cpu_avx=1, modelstr = "tigerlake"; /* Tiger Lake H */
else if (model == 0x8e) cpu_64bit = 1, cpu_avx=1, modelstr = "kabylake"; /* Kaby Lake Y/U */
else if (model == 0x8f) cpu_64bit = 1, cpu_avx=1, modelstr = "alderlake"; /* Sapphire Rapids */
+ else if (model == 0x96) cpu_64bit = 1, modelstr = "goldmont"; /* Tremont */
else if (model == 0x97) cpu_64bit = 1, cpu_avx=1, modelstr = "alderlake"; /* Alder Lake S */
else if (model == 0x9a) cpu_64bit = 1, cpu_avx=1, modelstr = "alderlake"; /* Alder Lake P */
+ else if (model == 0x9c) cpu_64bit = 1, modelstr = "goldmont"; /* Tremont */
else if (model == 0x9e) cpu_64bit = 1, cpu_avx=1, modelstr = "kabylake"; /* Kaby Lake desktop */
else if (model == 0xa7) cpu_64bit = 1, cpu_avx=1, modelstr = "rocketlake"; /* Rocket Lake S */
else cpu_64bit = 1, modelstr = "nehalem"; /* default */
diff -r ed0406cf3c70 -r f4f4f6030f8f configure.ac
--- a/configure.ac Wed Feb 02 19:16:36 2022 +0100
+++ b/configure.ac Tue Feb 15 09:18:40 2022 +0100
@@ -3053,7 +3053,7 @@
toom_eval_pm1 toom_eval_pm2 toom_eval_pm2exp toom_eval_pm2rexp \
toom_interpolate_5pts toom_interpolate_6pts toom_interpolate_7pts \
toom_interpolate_8pts toom_interpolate_12pts toom_interpolate_16pts \
- invertappr invert binvert mulmod_bnm1 sqrmod_bnm1 \
+ invertappr invert binvert mulmod_bnm1 sqrmod_bnm1 mulmod_bknp1 \
div_qr_1 div_qr_1n_pi1 \
div_qr_2 div_qr_2n_pi1 div_qr_2u_pi1 \
sbpi1_div_q sbpi1_div_qr sbpi1_divappr_q \
diff -r ed0406cf3c70 -r f4f4f6030f8f gmp-impl.h
--- a/gmp-impl.h Wed Feb 02 19:16:36 2022 +0100
+++ b/gmp-impl.h Tue Feb 15 09:18:40 2022 +0100
@@ -1276,6 +1276,64 @@
return itch;
}
+#ifndef MOD_BKNP1_USE11
+#define MOD_BKNP1_USE11 ((GMP_NUMB_BITS % 8 != 0) && (GMP_NUMB_BITS % 2 == 0))
+#endif
+#ifndef MOD_BKNP1_ONLY3
+#define MOD_BKNP1_ONLY3 0
+#endif
+#define mpn_mulmod_bknp1 __MPN(mulmod_bknp1)
+__GMP_DECLSPEC void mpn_mulmod_bknp1 (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, unsigned, mp_ptr);
+static inline mp_size_t
+mpn_mulmod_bknp1_itch (mp_size_t rn) {
+ return rn << 2;
+}
+#if MOD_BKNP1_ONLY3
+#define MPN_MULMOD_BKNP1_USABLE(rn, k, mn) \
+ ((GMP_NUMB_BITS % 8 == 0) && ((mn) >= 18) && ((rn) > 16) && \
+ (((rn) % ((k) = 3) == 0)))
+#else
+#define MPN_MULMOD_BKNP1_USABLE(rn, k, mn) \
+ ((GMP_NUMB_BITS % 8 == 0) && ((mn) >= 18) && ((rn) > 16) && \
+ (((rn) % ((k) = 3) == 0) || \
+ ((GMP_NUMB_BITS % 16 != 0) || ((mn) >= 35) && ((rn) >= 32)) && \
+ ((GMP_NUMB_BITS % 16 == 0) && ((rn) % ((k) = 5) == 0) || \
+ ((mn) >= 49) && \
+ (((rn) % ((k) = 7) == 0) || \
+ (GMP_NUMB_BITS % 16 == 0) && ((mn) >= 104) && ((rn) >= 64) && \
+ ((MOD_BKNP1_USE11 && ((rn) % ((k) = 11) == 0)) || \
+ ((rn) % ((k) = 13) == 0) || \
+ (GMP_NUMB_BITS % 32 == 0) && ((mn) >= 136) && ((rn) >= 128) && \
+ ((rn) % ((k) = 17) == 0) \
+ )))))
+#endif
+
+#define mpn_sqrmod_bknp1 __MPN(sqrmod_bknp1)
+__GMP_DECLSPEC void mpn_sqrmod_bknp1 (mp_ptr, mp_srcptr, mp_size_t, unsigned, mp_ptr);
+static inline mp_size_t
+mpn_sqrmod_bknp1_itch (mp_size_t rn) {
+ return rn * 3;
+}
+#if MOD_BKNP1_ONLY3
+#define MPN_SQRMOD_BKNP1_USABLE(rn, k, mn) \
+ MPN_MULMOD_BKNP1_USABLE(rn, k, mn)
+#else
+#define MPN_SQRMOD_BKNP1_USABLE(rn, k, mn) \
+ ((GMP_NUMB_BITS % 8 == 0) && ((mn) >= 27) && ((rn) > 24) && \
+ (((rn) % ((k) = 3) == 0) || \
+ ((GMP_NUMB_BITS % 16 != 0) || ((mn) >= 55) && ((rn) > 50)) && \
+ ((GMP_NUMB_BITS % 16 == 0) && ((rn) % ((k) = 5) == 0) || \
+ ((mn) >= 56) && \
+ (((rn) % ((k) = 7) == 0) || \
+ (GMP_NUMB_BITS % 16 == 0) && ((mn) >= 143) && ((rn) >= 128) && \
+ ((MOD_BKNP1_USE11 && ((rn) % ((k) = 11) == 0)) || \
+ ((rn) % ((k) = 13) == 0) || \
+ (GMP_NUMB_BITS % 32 == 0) && ((mn) >= 272) && ((rn) >= 256) && \
+ ((rn) % ((k) = 17) == 0) \
+ )))))
+#endif
+
+
#define mpn_sqrmod_bnm1 __MPN(sqrmod_bnm1)
__GMP_DECLSPEC void mpn_sqrmod_bnm1 (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_sqrmod_bnm1_next_size __MPN(sqrmod_bnm1_next_size)
@@ -1697,6 +1755,11 @@
(15 & 1 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 15)))
#endif
+#if GMP_NUMB_BITS % 8 == 0
+#define mpn_divexact_by17(dst,src,size) \
+ (31 & 15 * mpn_bdiv_dbm1 (dst, src, size, __GMP_CAST (mp_limb_t, GMP_NUMB_MASK / 17)))
+#endif
+
#define mpz_divexact_gcd __gmpz_divexact_gcd
__GMP_DECLSPEC void mpz_divexact_gcd (mpz_ptr, mpz_srcptr, mpz_srcptr);
diff -r ed0406cf3c70 -r f4f4f6030f8f mpn/generic/mulmod_bknp1.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/mulmod_bknp1.c Tue Feb 15 09:18:40 2022 +0100
@@ -0,0 +1,501 @@
+/* Mulptiplication mod B^n+1, for small operands.
+
+ Contributed to the GNU project by Marco Bodrato.
+
+ THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES. IT IS ONLY
+ SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
+ GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
+
+Copyright 2020-2022 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of either:
+
+ * the GNU Lesser General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at your
+ option) any later version.
+
+or
+
+ * the GNU General Public License as published by the Free Software
+ Foundation; either version 2 of the License, or (at your option) any
+ later version.
+
+or both in parallel, as here.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received copies of the GNU General Public License and the
+GNU Lesser General Public License along with the GNU MP Library. If not,
+see https://www.gnu.org/licenses/. */
+
+#include "gmp-impl.h"
+
+#ifndef MOD_BKNP1_USE11
+#define MOD_BKNP1_USE11 ((GMP_NUMB_BITS % 8 != 0) && (GMP_NUMB_BITS % 2 == 0))
+#endif
+#ifndef MOD_BKNP1_ONLY3
+#define MOD_BKNP1_ONLY3 0
+#endif
+
+/* {rp, (k - 1) * n} = {op, k * n + 1} % (B^{k*n}+1) / (B^n+1) */
+static void
+_mpn_modbknp1dbnp1_n (mp_ptr rp, mp_srcptr op, mp_size_t n, unsigned k)
+{
+ mp_limb_t hl;
+ mp_srcptr hp;
+ unsigned i;
+
+#if MOD_BKNP1_ONLY3
+ ASSERT (k == 3);
+ k = 3;
+#endif
+ ASSERT (k > 2);
+ ASSERT (k % 2 == 1);
+
+ --k;
+
+ rp += k * n;
+ op += k * n;
+ hp = op;
+ hl = hp[n]; /* initial op[k*n]. */
+ ASSERT (hl < GMP_NUMB_MAX - 1);
+
+#if MOD_BKNP1_ONLY3 == 0
+ /* The first MPN_INCR_U (rp + n, 1, cy); in the loop should be
+ rp[n] = cy; */
+ *rp = 0;
+#endif
+
+ i = k >> 1;
+ do
+ {
+ mp_limb_t cy, bw;
+ rp -= n;
+ op -= n;
+ cy = hl + mpn_add_n (rp, op, hp, n);
+#if MOD_BKNP1_ONLY3
+ rp[n] = cy;
+#else
+ MPN_INCR_U (rp + n, (k - i * 2) * n + 1, cy);
+#endif
+ rp -= n;
+ op -= n;
+ bw = hl + mpn_sub_n (rp, op, hp, n);
+ MPN_DECR_U (rp + n, (k - i * 2 + 1) * n + 1, bw);
+ }
+ while (--i != 0);
+
+ rp += k * n;
+ for (; (hl = *rp) != 0; rp += k * n) /* Should run only once... */
+ {
+ *rp = 0;
+ i = k >> 1;
+ do
+ {
+ rp -= n;
+ MPN_INCR_U (rp, (k - i * 2 + 1) * n + 1, hl);
+ rp -= n;
+ MPN_DECR_U (rp, (k - i * 2 + 2) * n + 1, hl);
+ }
+ while (--i != 0);
+ }
+}
+
+static void
+_mpn_modbnp1_pn_ip (mp_ptr r, mp_size_t n, mp_limb_t h)
+{
+ ASSERT (r[n] == h);
+
+ /* Fully normalise */
+ MPN_DECR_U (r, n + 1, h);
+ h -= r[n];
+ r[n] = 0;
+ MPN_INCR_U (r, n + 1, h);
+}
+
+static void
+_mpn_modbnp1_neg_ip (mp_ptr r, mp_size_t n, mp_limb_t h)
+{
+ r[n] = 0;
+ MPN_INCR_U (r, n + 1, -h);
+ h = r[n];
+ if (UNLIKELY (h != 0))
+ _mpn_modbnp1_pn_ip (r, n, h);
+}
+
+static void
+_mpn_modbnp1_nc_ip (mp_ptr r, mp_size_t n, mp_limb_t h)
+{
+ if (h & GMP_NUMB_HIGHBIT) /* This means h < 0 */
+ {
+ _mpn_modbnp1_neg_ip (r, n, h);
+ return;
+ }
+
+ r[n] = h;
+ if (h)
+ _mpn_modbnp1_pn_ip(r, n, h);
+}
+
+/* {rp, rn + 1} = {op, on} mod (B^{rn}+1) */
+/* Used when rn < on < 2*rn. */
+static void
+_mpn_modbnp1 (mp_ptr rp, mp_size_t rn, mp_srcptr op, mp_size_t on)
+{
+ mp_limb_t bw;
+
+#if 0
+ if (UNLIKELY (on <= rn))
+ {
+ MPN_COPY (rp, op, on);
+ MPN_ZERO (rp + on, rn - on);
+ return;
+ }
+#endif
+
+ ASSERT (on > rn);
+ ASSERT (on <= 2 * rn);
+
+ bw = mpn_sub (rp, op, rn, op + rn, on - rn);
+ rp[rn] = 0;
+ MPN_INCR_U (rp, rn + 1, bw);
+}
+
+/* {rp, rn + 1} = {op, k * rn + 1} % (B^{rn}+1) */
+/* With odd k >= 3. */
+static void
+_mpn_modbnp1_kn (mp_ptr rp, mp_srcptr op, mp_size_t rn, unsigned k)
+{
+ mp_limb_t cy;
+
+#if MOD_BKNP1_ONLY3
+ ASSERT (k == 3);
+ k = 3;
+#endif
+ ASSERT (k & 1);
+ k >>= 1;
+ ASSERT (0 < k && k < GMP_NUMB_HIGHBIT - 1);
+ ASSERT (op[(1 + 2 * k) * rn] < GMP_NUMB_HIGHBIT - 2 - k);
More information about the gmp-commit
mailing list