[Gmp-commit] /home/hgfiles/gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Mon May 3 22:25:27 CEST 2010
details: /home/hgfiles/gmp/rev/2b7f473c761e
changeset: 13595:2b7f473c761e
user: Torbjorn Granlund <tege at gmplib.org>
date: Mon May 03 10:06:40 2010 +0200
description:
Fix typo, and align labels.
details: /home/hgfiles/gmp/rev/c3eb43a57d77
changeset: 13596:c3eb43a57d77
user: Torbjorn Granlund <tege at gmplib.org>
date: Mon May 03 20:50:10 2010 +0200
description:
(tune_mod_1): Rewrite.
details: /home/hgfiles/gmp/rev/489fdf411a02
changeset: 13597:489fdf411a02
user: Torbjorn Granlund <tege at gmplib.org>
date: Mon May 03 22:24:14 2010 +0200
description:
Avoid multiply for 2 limb feed-in.
details: /home/hgfiles/gmp/rev/c7b665ec4bda
changeset: 13598:c7b665ec4bda
user: Torbjorn Granlund <tege at gmplib.org>
date: Mon May 03 22:25:23 2010 +0200
description:
Trivial merge.
diffstat:
ChangeLog | 33 ++++++++
doc/gmp.texi | 2 +-
gmp-impl.h | 16 +--
mpn/alpha/ev6/mod_1_4.asm | 9 +-
mpn/generic/gcd.c | 13 +--
mpn/generic/gcd_subdiv_step.c | 83 ++++++++++++---------
mpn/generic/gcdext.c | 4 +-
mpn/generic/gcdext_lehmer.c | 147 ++++++++++++++++++-------------------
mpn/generic/jacobi_lehmer.c | 112 ++++------------------------
mpn/generic/mod_1_1.c | 6 +-
mpn/generic/mod_1_2.c | 5 +-
mpn/generic/mod_1_3.c | 5 +-
mpn/generic/mod_1_4.c | 7 +-
mpn/powerpc64/sqr_diagonal.asm | 3 +-
mpn/x86/k7/mod_1_4.asm | 5 +-
mpn/x86/pentium4/sse2/mod_1_4.asm | 11 +-
mpn/x86_64/mod_1_1.asm | 8 +-
mpn/x86_64/mod_1_2.asm | 16 +--
mpn/x86_64/mod_1_4.asm | 5 +-
tune/tuneup.c | 72 ++++++++++--------
20 files changed, 253 insertions(+), 309 deletions(-)
diffs (truncated from 966 to 300 lines):
diff -r acb26f202896 -r c7b665ec4bda ChangeLog
--- a/ChangeLog Mon May 03 02:29:52 2010 +0200
+++ b/ChangeLog Mon May 03 22:25:23 2010 +0200
@@ -1,5 +1,38 @@
+2010-05-03 Niels Möller <nisse at lysator.liu.se>
+
+ * mpn/generic/jacobi_lehmer.c (jacobi_hook): New function.
+ (mpn_jacobi_subdiv_step): Deleted function.
+ (mpn_jacobi_lehmer): Use general mpn_gcd_subdiv_step.
+
+ * mpn/generic/gcd_subdiv_step.c (mpn_gcd_subdiv_step): Reorganized
+ to use a single hook function.
+ * mpn/generic/gcdext.c (mpn_gcdext): Adapted to new hook
+ interface.
+ * mpn/generic/gcdext_lehmer.c (mpn_gcdext_hook): New unified hook
+ function.
+ * mpn/generic/gcd.c (gcd_hook): Renamed from gcd_done, and adapted
+ to new hook interface.
+ * gmp-impl.h (gcd_subdiv_step_hook): New typedef, now a function
+ type, not a struct.
+ (mpn_gcdext_hook): Declare.
+
2010-05-03 Torbjorn Granlund <tege at gmplib.org>
+ * mpn/generic/mod_1_1.c: Avoid multiply for 2 limb feed-in.
+ * mpn/generic/mod_1_2.c: Likewise.
+ * mpn/generic/mod_1_3.c: Likewise.
+ * mpn/generic/mod_1_4.c: Likewise.
+ * mpn/x86_64/mod_1_1.asm: Likewise.
+ * mpn/x86_64/mod_1_2.asm: Likewise.
+ * mpn/x86_64/mod_1_4.asm: Likewise.
+ * mpn/x86/k7/mod_1_4.asm: Likewise.
+ * mpn/x86/pentium4/sse2/mod_1_4.asm: Likewise.
+ * mpn/alpha/ev6/mod_1_4.asm: Likewise.
+
+ * tune/tuneup.c (tune_mod_1): Measure MOD_1_1_TO_MOD_1_2_THRESHOLD and
+ MOD_1_2_TO_MOD_1_4_THRESHOLD before MOD_1U_TO_MOD_1_1_THRESHOLD for
+ correctness.
+
* mpn/powerpc64/sqr_diagonal.asm: Complete rewrite.
* mpn/powerpc64/mode64/mod_1_4.asm: New file.
diff -r acb26f202896 -r c7b665ec4bda doc/gmp.texi
--- a/doc/gmp.texi Mon May 03 02:29:52 2010 +0200
+++ b/doc/gmp.texi Mon May 03 22:25:23 2010 +0200
@@ -5322,7 +5322,7 @@
@code{mp_bits_per_limb} is even, which is always so currently).
@end deftypefn
- at deftypefun mp_limb_t mpn_mod_1 (mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, mp_limb_t @var{s2limb})
+ at deftypefun mp_limb_t mpn_mod_1 (const mp_limb_t *@var{s1p}, mp_size_t @var{s1n}, mp_limb_t @var{s2limb})
Divide @{@var{s1p}, @var{s1n}@} by @var{s2limb}, and return the remainder.
@var{s1n} can be zero.
@end deftypefun
diff -r acb26f202896 -r c7b665ec4bda gmp-impl.h
--- a/gmp-impl.h Mon May 03 02:29:52 2010 +0200
+++ b/gmp-impl.h Mon May 03 22:25:23 2010 +0200
@@ -3859,18 +3859,13 @@
#define mpn_hgcd __MPN (hgcd)
__GMP_DECLSPEC mp_size_t mpn_hgcd __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, struct hgcd_matrix *, mp_ptr));
-struct gcd_subdiv_step_hook
-{
- /* Passes quotient. */
- void (*update)(void *, mp_srcptr, mp_size_t, unsigned);
- /* Passes final gcd (must be copied if it is to be retained). */
- void (*done)(void *, mp_srcptr, mp_size_t, unsigned);
-};
+typedef void gcd_subdiv_step_hook(void *, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, int);
+
/* Needs storage for the quotient */
#define MPN_GCD_SUBDIV_STEP_ITCH(n) (n)
#define mpn_gcd_subdiv_step __MPN(gcd_subdiv_step)
-__GMP_DECLSPEC mp_size_t mpn_gcd_subdiv_step __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, const struct gcd_subdiv_step_hook *, void *, mp_ptr));
+__GMP_DECLSPEC mp_size_t mpn_gcd_subdiv_step __GMP_PROTO ((mp_ptr, mp_ptr, mp_size_t, gcd_subdiv_step_hook *, void *, mp_ptr));
struct gcdext_ctx
{
@@ -3885,9 +3880,8 @@
mp_ptr u0, u1, tp;
};
-#define gcdext_hook __gmp_gcdext_hook
-extern const struct gcd_subdiv_step_hook
-gcdext_hook;
+#define mpn_gcdext_hook __MPN (gcdext_hook)
+gcd_subdiv_step_hook mpn_gcdext_hook;
#define MPN_GCDEXT_LEHMER_N_ITCH(n) (4*(n) + 3)
diff -r acb26f202896 -r c7b665ec4bda mpn/alpha/ev6/mod_1_4.asm
--- a/mpn/alpha/ev6/mod_1_4.asm Mon May 03 02:29:52 2010 +0200
+++ b/mpn/alpha/ev6/mod_1_4.asm Mon May 03 22:25:23 2010 +0200
@@ -115,13 +115,8 @@
lda ap, -40(ap)
br L(com)
-L(b2): ldq r21, -8(ap)
- ldq r20, -16(ap)
- mulq r21, B1modb, r8
- umulh r21, B1modb, r12
- addq r8, r20, rl
- cmpult rl, r8, r0
- addq r0, r12, rh
+L(b2): ldq rh, -8(ap)
+ ldq rl, -16(ap)
lda ap, -48(ap)
L(com): ble n, L(ed3)
diff -r acb26f202896 -r c7b665ec4bda mpn/generic/gcd.c
--- a/mpn/generic/gcd.c Mon May 03 02:29:52 2010 +0200
+++ b/mpn/generic/gcd.c Mon May 03 22:25:23 2010 +0200
@@ -18,8 +18,6 @@
You should have received a copy of the GNU Lesser General Public License
along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
-#include <stdlib.h> /* for NULL */
-
#include "gmp.h"
#include "gmp-impl.h"
#include "longlong.h"
@@ -60,18 +58,13 @@
};
static void
-gcd_done (void *p, mp_srcptr gp, mp_size_t gn, unsigned swapped)
+gcd_hook (void *p, mp_srcptr gp, mp_size_t gn,
+ mp_srcptr qp, mp_size_t qn, int d)
{
struct gcd_ctx *ctx = (struct gcd_ctx *) p;
MPN_COPY (ctx->gp, gp, gn);
ctx->gn = gn;
}
-
-static const struct gcd_subdiv_step_hook
-gcd_hook = {
- NULL,
- gcd_done,
-};
#if GMP_NAIL_BITS > 0
/* Nail supports should be easy, replacing the sub_ddmmss with nails
@@ -213,7 +206,7 @@
else
{
/* Temporary storage n */
- n = mpn_gcd_subdiv_step (up, vp, n, &gcd_hook, &ctx, tp);
+ n = mpn_gcd_subdiv_step (up, vp, n, gcd_hook, &ctx, tp);
if (n == 0)
goto done;
}
diff -r acb26f202896 -r c7b665ec4bda mpn/generic/gcd_subdiv_step.c
--- a/mpn/generic/gcd_subdiv_step.c Mon May 03 02:29:52 2010 +0200
+++ b/mpn/generic/gcd_subdiv_step.c Mon May 03 22:25:23 2010 +0200
@@ -21,6 +21,8 @@
You should have received a copy of the GNU Lesser General Public License
along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
+#include <stdlib.h> /* for NULL */
+
#include "gmp.h"
#include "gmp-impl.h"
#include "longlong.h"
@@ -30,29 +32,39 @@
followed by one division. Returns zero if the gcd is found.
Otherwise, compute the reduced a and b, and return the new size. */
-/* About the hook functions.
+/* The hook function is called as
- hook->update (ctx, qp, qn, d)
+ hook(ctx, gp, gn, qp, qn, d)
- is called when one of the numbers, or a multiple of it, is
- subtracted from the other. d == 0 means q a is subtracted from b, d
- == 1 means that q b is subtracted from a.
+ in the following cases:
- hook->done (ctx, gp, gn, d)
+ + If A == B at the start, G is the gcd, Q is NULL, d = -1.
- is called when the gcd is found. d == 0 if the last reduction
- subtracted a from b, d == 1 if it subtracted b from a, and d == 2
- if it is unknown which was the most recent reduction. */
+ + If one input is zero at the start, G is the gcd, Q is NULL,
+ d = 0 if A == G and d = 1 if B == G.
+
+ Otherwise, if d = 0 we have just subtracted a multiple of A from B,
+ and if d = 1 we have subtracted a multiple of B from A.
+
+ + If A == B after subtraction, G is the gcd, Q is NULL.
+
+ + If we get a zero remainder after division, G is the gcd, Q is the
+ quotient.
+
+ + Otherwise, G is NULL, Q is the quotient (often 1).
+
+ */
mp_size_t
mpn_gcd_subdiv_step (mp_ptr ap, mp_ptr bp, mp_size_t n,
- const struct gcd_subdiv_step_hook *hook, void *ctx,
+ gcd_subdiv_step_hook *hook, void *ctx,
mp_ptr tp)
{
- mp_size_t an, bn;
+ static const mp_limb_t one = CNST_LIMB(1);
+ mp_size_t an, bn, qn;
int swapped;
-
+
ASSERT (n > 0);
ASSERT (ap[n-1] > 0 || bp[n-1] > 0);
@@ -71,7 +83,7 @@
if (UNLIKELY (c == 0))
{
/* For gcdext, return the smallest of the two cofactors. */
- hook->done (ctx, ap, an, 2);
+ hook (ctx, ap, an, NULL, 0, -1);
return 0;
}
else if (c > 0)
@@ -89,7 +101,7 @@
}
if (an == 0)
{
- hook->done (ctx, bp, bn, swapped ^ 1);
+ hook (ctx, bp, bn, NULL, 0, swapped ^ 1);
return 0;
}
}
@@ -97,47 +109,46 @@
MPN_NORMALIZE (bp, bn);
ASSERT (bn > 0);
- if (hook->update)
- {
- static const mp_limb_t one = CNST_LIMB(1);
- hook->update(ctx, &one, 1, swapped);
- }
-
- /* Arrange so that a < b, and divide b = q a + r */
+ /* Arrange so that a < b */
if (an == bn)
{
int c;
MPN_CMP (c, ap, bp, an);
if (UNLIKELY (c == 0))
{
- hook->done (ctx, bp, bn, swapped);
+ hook (ctx, bp, bn, NULL, 0, swapped);
return 0;
}
- else if (c > 0)
+
+ hook (ctx, NULL, 0, &one, 1, swapped);
+
+ if (c > 0)
{
MP_PTR_SWAP (ap, bp);
swapped ^= 1;
}
}
- else if (an > bn)
+ else
{
- MPN_PTR_SWAP (ap, an, bp, bn);
- swapped ^= 1;
+ hook (ctx, NULL, 0, &one, 1, swapped);
+
+ if (an > bn)
+ {
+ MPN_PTR_SWAP (ap, an, bp, bn);
+ swapped ^= 1;
+ }
}
mpn_tdiv_qr (tp, bp, 0, bp, bn, ap, an);
-
- /* FIXME: For jacobi, we need to call update before calling done.
- While for gcdext, calling update in this case would do useless
- work. */
+ qn = bn - an + 1;
if (mpn_zero_p (bp, an))
{
- hook->done (ctx, ap, an, swapped);
+ hook (ctx, ap, an, tp, qn, swapped);
return 0;
}
-
- if (hook->update)
- hook->update(ctx, tp, bn - an + 1, swapped);
-
- return an;
+ else
+ {
+ hook (ctx, NULL, 0, tp, qn, swapped);
More information about the gmp-commit
mailing list