[Gmp-commit] /home/hgfiles/gmp: (mpn_gcd_subdiv_step): Reorganized to use a s...
mercurial at gmplib.org
mercurial at gmplib.org
Mon May 3 14:47:06 CEST 2010
details: /home/hgfiles/gmp/rev/b1ecb9d6e581
changeset: 13592:b1ecb9d6e581
user: Niels M?ller <nisse at lysator.liu.se>
date: Mon May 03 14:38:06 2010 +0200
description:
(mpn_gcd_subdiv_step): Reorganized to use a single hook function.
diffstat:
ChangeLog | 14 ++++
gmp-impl.h | 16 +---
mpn/generic/gcd.c | 13 +--
mpn/generic/gcd_subdiv_step.c | 83 +++++++++++++----------
mpn/generic/gcdext.c | 4 +-
mpn/generic/gcdext_lehmer.c | 147 ++++++++++++++++++++----------------------
6 files changed, 141 insertions(+), 136 deletions(-)
diffs (truncated from 456 to 300 lines):
diff -r acb26f202896 -r b1ecb9d6e581 ChangeLog
--- a/ChangeLog Mon May 03 02:29:52 2010 +0200
+++ b/ChangeLog Mon May 03 14:38:06 2010 +0200
@@ -1,3 +1,17 @@
+2010-05-03 Niels Möller <nisse at lysator.liu.se>
+
+ * 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/powerpc64/sqr_diagonal.asm: Complete rewrite.
diff -r acb26f202896 -r b1ecb9d6e581 gmp-impl.h
--- a/gmp-impl.h Mon May 03 02:29:52 2010 +0200
+++ b/gmp-impl.h Mon May 03 14:38:06 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 b1ecb9d6e581 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 14:38:06 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 b1ecb9d6e581 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 14:38:06 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);
+ return an;
+ }
}
diff -r acb26f202896 -r b1ecb9d6e581 mpn/generic/gcdext.c
--- a/mpn/generic/gcdext.c Mon May 03 02:29:52 2010 +0200
+++ b/mpn/generic/gcdext.c Mon May 03 14:38:06 2010 +0200
@@ -318,7 +318,7 @@
ctx.un = 1;
/* Temporary storage n */
- n = mpn_gcd_subdiv_step (ap, bp, n, &gcdext_hook, &ctx, tp);
+ n = mpn_gcd_subdiv_step (ap, bp, n, mpn_gcdext_hook, &ctx, tp);
if (n == 0)
{
TMP_FREE;
@@ -373,7 +373,7 @@
ctx.un = un;
/* Temporary storage n */
- n = mpn_gcd_subdiv_step (ap, bp, n, &gcdext_hook, &ctx, tp);
+ n = mpn_gcd_subdiv_step (ap, bp, n, mpn_gcdext_hook, &ctx, tp);
if (n == 0)
{
TMP_FREE;
diff -r acb26f202896 -r b1ecb9d6e581 mpn/generic/gcdext_lehmer.c
--- a/mpn/generic/gcdext_lehmer.c Mon May 03 02:29:52 2010 +0200
+++ b/mpn/generic/gcdext_lehmer.c Mon May 03 14:38:06 2010 +0200
@@ -24,102 +24,95 @@
/* Here, d is the index of the cofactor to update. FIXME: Could use qn
= 0 for the common case q = 1. */
-static void
-gcdext_update (void *p, mp_srcptr qp, mp_size_t qn, unsigned d)
+void
+mpn_gcdext_hook (void *p, mp_srcptr gp, mp_size_t gn,
+ mp_srcptr qp, mp_size_t qn, int d)
{
struct gcdext_ctx *ctx = (struct gcdext_ctx *) p;
- mp_ptr u0;
- mp_ptr u1;
mp_size_t un = ctx->un;
- mp_limb_t cy;
- u0 = ctx->u0;
- u1 = ctx->u1;
- if (d)
- MP_PTR_SWAP (u0, u1);
+ if (gp)
+ {
+ mp_srcptr up;
- qn -= (qp[qn-1] == 0);
More information about the gmp-commit
mailing list