[Gmp-commit] /var/hg/gmp-proj/mini-gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sun Jan 1 23:23:58 CET 2012
details: /var/hg/gmp-proj/mini-gmp/rev/5e706b40e929
changeset: 30:5e706b40e929
user: Niels M?ller <nisse at lysator.liu.se>
date: Sun Jan 01 23:23:12 2012 +0100
description:
Implemented mpz_gcd_ui and mpz_gcd.
Also added count_leading_zeros, count_trailing_zeros (replacing
left_normalize_limb), mpn_copyd, mpz_abs, mpz_mul_2exp. Made
mpn_div_qr_1_preinv, mpn_div_qr_1 and mpn_div_qr_2 not modify the np
input, instead allocating space for any needed normalized copy.
details: /var/hg/gmp-proj/mini-gmp/rev/c2aa8afe583f
changeset: 31:c2aa8afe583f
user: Niels M?ller <nisse at lysator.liu.se>
date: Sun Jan 01 23:23:55 2012 +0100
description:
gcd testing.
diffstat:
.hgignore | 1 +
mini-gmp.c | 375 ++++++++++++++++++++++++++++++++++++++++++++++++----
mini-gmp.h | 11 +-
tests/Makefile | 2 +-
tests/hex-random.c | 14 +-
tests/hex-random.h | 2 +-
tests/t-gcd.c | 51 +++++++
7 files changed, 416 insertions(+), 40 deletions(-)
diffs (truncated from 676 to 300 lines):
diff -r 7c34a20624ec -r c2aa8afe583f .hgignore
--- a/.hgignore Sun Jan 01 16:24:11 2012 +0100
+++ b/.hgignore Sun Jan 01 23:23:55 2012 +0100
@@ -10,3 +10,4 @@
^tests/t-div$
^tests/t-double$
^tests/t-str$
+^tests/t-gcd$
diff -r 7c34a20624ec -r c2aa8afe583f mini-gmp.c
--- a/mini-gmp.c Sun Jan 01 16:24:11 2012 +0100
+++ b/mini-gmp.c Sun Jan 01 23:23:55 2012 +0100
@@ -1,8 +1,8 @@
/* Implementation for GNU minimalistic multiple precision functions.
-Copyright 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1999, 2000, 2001, 2002,
-2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation,
-Inc.
+Copyright 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1999, 2000, 2001,
+2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Free
+Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -72,9 +72,30 @@
#define ABS(x) ((x) >= 0 ? (x) : -(x))
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+
#define assert_nocarry(x) do { \
- mp_limb_t __cy = x; \
- assert (__cy == 0); \
+ mp_limb_t __cy = x; \
+ assert (__cy == 0); \
+ } while (0)
+
+#define count_leading_zeros(count, x) do { \
+ mp_limb_t __clz_x = (x); \
+ unsigned __clz_c; \
+ for (__clz_c = 0; \
+ (__clz_x & ((mp_limb_t) 0xff << (GMP_LIMB_BITS - 8))) == 0; \
+ __clz_c += 8) \
+ __clz_x <<= 8; \
+ for (; (__clz_x & GMP_LIMB_HIGHBIT) == 0; __clz_c++) \
+ __clz_x <<= 1; \
+ (count) = __clz_c; \
+ } while (0)
+
+#define count_trailing_zeros(count, x) do { \
+ mp_limb_t __ctz_x = (x); \
+ unsigned __ctz_c = 0; \
+ count_leading_zeros (__ctz_c, __ctz_x & - __ctz_x); \
+ (count) = GMP_LIMB_BITS - 1 - __ctz_c; \
} while (0)
#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
@@ -276,6 +297,13 @@
d[i] = s[i];
}
+void
+mpn_copyd (mp_ptr d, mp_srcptr s, mp_size_t n)
+{
+ while (n-- > 0)
+ d[n] = s[n];
+}
+
int
mpn_cmp (mp_srcptr ap, mp_srcptr bp, mp_size_t n)
{
@@ -656,13 +684,6 @@
return m;
}
-#define left_normalize_limb(c, x) do { \
- unsigned __c; \
- for (__c = 0; ((x) & GMP_LIMB_HIGHBIT) == 0; __c++) \
- (x) <<= 1; \
- (c) = __c; \
- } while (0)
-
struct div_qr_1_inverse
{
/* Normalization shift count. */
@@ -677,26 +698,32 @@
mpn_div_qr_1_invert (struct div_qr_1_inverse *inv, mp_limb_t d)
{
unsigned shift;
- left_normalize_limb (shift, d);
+ count_leading_zeros (shift, d);
inv->shift = shift;
- inv->d = d;
- inv->di = mpn_invert_limb (d);
+ inv->d = d << shift;
+ inv->di = mpn_invert_limb (inv->d);
}
/* Not matching current public gmp interface, rather corresponding to
the sbpi1_div_* functions. */
static mp_limb_t
-mpn_div_qr_1_preinv (mp_ptr qp, mp_ptr np, mp_size_t nn,
+mpn_div_qr_1_preinv (mp_ptr qp, mp_srcptr np, mp_size_t nn,
const struct div_qr_1_inverse *inv)
{
mp_limb_t d, di;
mp_limb_t r;
+ mp_ptr tp = NULL;
if (inv->shift > 0)
- r = mpn_lshift (np, np, nn, inv->shift);
+ {
+ tp = xalloc_limbs (nn);
+ r = mpn_lshift (tp, np, nn, inv->shift);
+ np = tp;
+ }
else
r = 0;
+
d = inv->d;
di = inv->di;
while (nn-- > 0)
@@ -707,11 +734,14 @@
if (qp)
qp[nn] = q;
}
+ if (inv->shift > 0)
+ free (tp);
+
return r >> inv->shift;
}
static mp_limb_t
-mpn_div_qr_1 (mp_ptr qp, mp_ptr np, mp_size_t nn, mp_limb_t d)
+mpn_div_qr_1 (mp_ptr qp, mp_srcptr np, mp_size_t nn, mp_limb_t d)
{
struct div_qr_1_inverse inv;
mpn_div_qr_1_invert (&inv, d);
@@ -719,21 +749,24 @@
}
static void
-mpn_div_qr_2 (mp_ptr qp, mp_ptr rp, mp_ptr np, mp_size_t nn,
+mpn_div_qr_2 (mp_ptr qp, mp_ptr rp, mp_srcptr np, mp_size_t nn,
mp_limb_t d1, mp_limb_t d0)
{
unsigned shift;
mp_size_t i;
mp_limb_t di, r1, r0;
+ mp_ptr tp;
assert (nn >= 2);
- left_normalize_limb (shift, d1);
+ count_leading_zeros (shift, d1);
if (shift > 0)
{
- d1 |= d0 >> (GMP_LIMB_BITS - shift);
+ d1 = (d1 << shift) | (d0 >> (GMP_LIMB_BITS - shift));
d0 <<= shift;
- r1 = mpn_lshift (np, np, nn, shift);
+ tp = xalloc_limbs (nn);
+ r1 = mpn_lshift (tp, np, nn, shift);
+ np = tp;
}
else
r1 = 0;
@@ -758,6 +791,8 @@
assert ((r0 << (GMP_LIMB_BITS - shift)) == 0);
r0 = (r0 >> shift) | (r1 << (GMP_LIMB_BITS - shift));
r1 >>= shift;
+
+ free (tp);
}
rp[1] = r1;
@@ -837,22 +872,21 @@
mpn_div_qr_2 (qp, np, np, nn, dp[1], dp[0]);
else
{
- mp_ptr tp;
+ mp_ptr tp = NULL;
mp_limb_t d1, d0, di;
mp_limb_t nh;
unsigned shift;
d1 = dp[dn - 1];
- left_normalize_limb (shift, d1);
+ count_leading_zeros (shift, d1);
if (shift > 0)
{
- /* FIXME: Or is it better to modify dp? */
tp = xalloc_limbs (dn);
- d1 |= mpn_lshift (tp, dp, dn-1, shift);
- tp[dn-1] = d1;
+ assert_nocarry (mpn_lshift (tp, dp, dn, shift));
nh = mpn_lshift (np, np, nn, shift);
dp = tp;
+ d1 = dp[dn - 1];
}
else
nh = 0;
@@ -1156,14 +1190,6 @@
? mpz_realloc(z,n) \
: (z)->_mp_d)
-void
-mpz_swap (mpz_t u, mpz_t v)
-{
- MP_SIZE_T_SWAP (u->_mp_size, v->_mp_size);
- MP_SIZE_T_SWAP (u->_mp_alloc, v->_mp_alloc);
- MP_PTR_SWAP (u->_mp_d, v->_mp_d);
-}
-
int
mpz_sgn (const mpz_t u)
{
@@ -1278,6 +1304,29 @@
v->_mp_d, ABS(v->_mp_size));
}
+void mpz_abs (mpz_t r, const mpz_t u)
+{
+ mp_size_t n = ABS (u->_mp_size);
+
+ if (r != u)
+ {
+ mp_ptr rp;
+ rp = MPZ_REALLOC (r, n);
+ mpn_copyi (rp, u->_mp_d, n);
+ }
+
+ r->_mp_size = n;
+}
+
+void
+mpz_swap (mpz_t u, mpz_t v)
+{
+ MP_SIZE_T_SWAP (u->_mp_size, v->_mp_size);
+ MP_SIZE_T_SWAP (u->_mp_alloc, v->_mp_alloc);
+ MP_PTR_SWAP (u->_mp_d, v->_mp_d);
+}
+
+
/* Adds to the absolute value. Returns new size, but doesn't store it. */
static mp_size_t
abs_add_ui (mpz_t r, const mpz_t a, unsigned long b)
@@ -1510,6 +1559,36 @@
mpz_clear (t);
}
+void
+mpz_mul_2exp (mpz_t r, const mpz_t u, mp_bitcnt_t bits)
+{
+ mp_size_t un, rn;
+ mp_size_t limbs;
+ unsigned shift;
+ mp_ptr rp;
+
+ un = ABS (u->_mp_size);
+
+ limbs = bits / GMP_LIMB_BITS;
+ shift = bits % GMP_LIMB_BITS;
+
+ rn = un + limbs + (shift > 0);
+ rp = MPZ_REALLOC (r, rn);
+ if (shift > 0)
+ {
+ mp_limb_t cy = mpn_lshift (rp + limbs, u->_mp_d, un, shift);
+ rp[rn-1] = cy;
+ rn -= (cy == 0);
+ }
+ else
+ mpn_copyd (rp + limbs, u->_mp_d, un);
+
+ while (limbs > 0)
+ rp[--limbs] = 0;
+
+ r->_mp_size = (u->_mp_size < 0) ? - rn : rn;
+}
+
enum div_round_mode { DIV_FLOOR, DIV_CEIL, DIV_TRUNC };
/* Allows q or r to be zero. */
@@ -1787,6 +1866,232 @@
return mpz_div_qr_ui (NULL, NULL, n, d, DIV_TRUNC);
}
+static mp_limb_t
+limb_gcd (mp_limb_t u, mp_limb_t v)
+{
+ unsigned shift;
+
+ assert ( (u | v) > 0);
+
+ if (u == 0)
+ return v;
+ else if (v == 0)
+ return u;
More information about the gmp-commit
mailing list