[Gmp-commit] /var/hg/gmp: 9 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Wed Feb 27 10:30:21 CET 2013
details: /var/hg/gmp/rev/21801e324a8f
changeset: 15489:21801e324a8f
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Feb 27 09:59:33 2013 +0100
description:
mini-gmp/mini-gmp.c (mpz_div_q_2exp): Adjust only if needed.
details: /var/hg/gmp/rev/d6cbb510de05
changeset: 15490:d6cbb510de05
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Feb 27 10:04:45 2013 +0100
description:
mini-gmp/mini-gmp.c (mpz_scan0, mpz_scan1): Simplify by using mpn_common_scan.
details: /var/hg/gmp/rev/982e8796107b
changeset: 15491:982e8796107b
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Feb 27 10:13:07 2013 +0100
description:
mini-gmp/mini-gmp.c (mpz_make_odd): Simplify, assume in-place operation on positive.
details: /var/hg/gmp/rev/028ee39c97bc
changeset: 15492:028ee39c97bc
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Feb 27 10:14:46 2013 +0100
description:
mini-gmp/mini-gmp.c (mpn_scan0, mpn_scan1): New functions.
details: /var/hg/gmp/rev/cee7f9b2abe5
changeset: 15493:cee7f9b2abe5
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Feb 27 10:15:05 2013 +0100
description:
ChangeLog
details: /var/hg/gmp/rev/0c785e5ddffd
changeset: 15494:0c785e5ddffd
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Feb 27 10:18:04 2013 +0100
description:
mini-gmp/mini-gmp.h (mpn_scan0, mpn_scan1): New declarations.
details: /var/hg/gmp/rev/1c2dd203ccac
changeset: 15495:1c2dd203ccac
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Feb 27 10:18:55 2013 +0100
description:
mini-gmp/tests/t-scan.c: Test also mpn_scan0 and mpn_scan1.
details: /var/hg/gmp/rev/286eb126ef12
changeset: 15496:286eb126ef12
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Feb 27 10:20:06 2013 +0100
description:
ChangeLog
details: /var/hg/gmp/rev/1afcfe1fe381
changeset: 15497:1afcfe1fe381
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Wed Feb 27 10:29:52 2013 +0100
description:
mini-gmp/mini-gmp.c (mpz_make_odd): Size is not needed.
diffstat:
ChangeLog | 10 ++
mini-gmp/mini-gmp.c | 191 ++++++++++++++++++++++++-----------------------
mini-gmp/mini-gmp.h | 3 +
mini-gmp/tests/t-scan.c | 26 ++++++
4 files changed, 135 insertions(+), 95 deletions(-)
diffs (truncated from 371 to 300 lines):
diff -r 1b5daa933fac -r 1afcfe1fe381 ChangeLog
--- a/ChangeLog Tue Feb 26 23:48:15 2013 +0100
+++ b/ChangeLog Wed Feb 27 10:29:52 2013 +0100
@@ -1,3 +1,13 @@
+2013-02-27 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mini-gmp/mini-gmp.c (mpz_div_q_2exp): Adjust only if needed.
+ (mpn_common_scan): New service function to unify scan loops.
+ (mpz_scan0, mpz_scan1): Simplify by using mpn_common_scan.
+ (mpz_make_odd): Simplify, assume in-place operation on positive.
+ (mpn_scan0, mpn_scan1): New functions.
+ * mini-gmp/mini-gmp.h (mpn_scan0, mpn_scan1): New declarations.
+ * mini-gmp/tests/t-scan.c: Test also mpn_scan0 and mpn_scan1.
+
2013-02-26 Niels Möller <nisse at lysator.liu.se>
* tests/mpz/t-limbs.c (check_roinit): Test MPZ_ROINIT_N only if
diff -r 1b5daa933fac -r 1afcfe1fe381 mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Tue Feb 26 23:48:15 2013 +0100
+++ b/mini-gmp/mini-gmp.c Wed Feb 27 10:29:52 2013 +0100
@@ -637,6 +637,46 @@
return retval;
}
+static mp_bitcnt_t
+mpn_common_scan (mp_limb_t limb, mp_size_t i, mp_srcptr up, mp_size_t un,
+ mp_limb_t ux)
+{
+ unsigned cnt;
+
+ assert (ux == 0 || ux == GMP_LIMB_MAX);
+ assert (0 <= i && i <= un );
+
+ while (limb == 0)
+ {
+ i++;
+ if (i == un)
+ return (ux == 0 ? ~(mp_bitcnt_t) 0 : un * GMP_LIMB_BITS);
+ limb = ux ^ up[i];
+ }
+ gmp_ctz (cnt, limb);
+ return (mp_bitcnt_t) i * GMP_LIMB_BITS + cnt;
+}
+
+mp_bitcnt_t
+mpn_scan1 (mp_srcptr ptr, mp_bitcnt_t bit)
+{
+ mp_size_t i;
+ i = bit / GMP_LIMB_BITS;
+
+ return mpn_common_scan ( ptr[i] & (GMP_LIMB_MAX << (bit % GMP_LIMB_BITS)),
+ i, ptr, i, 0);
+}
+
+mp_bitcnt_t
+mpn_scan0 (mp_srcptr ptr, mp_bitcnt_t bit)
+{
+ mp_size_t i;
+ i = bit / GMP_LIMB_BITS;
+
+ return mpn_common_scan (~ptr[i] & (GMP_LIMB_MAX << (bit % GMP_LIMB_BITS)),
+ i, ptr, i, GMP_LIMB_MAX);
+}
+
/* MPN division interface. */
mp_limb_t
@@ -2156,7 +2196,7 @@
mp_size_t un, qn;
mp_size_t limb_cnt;
mp_ptr qp;
- mp_limb_t adjust;
+ int adjust;
un = u->_mp_size;
if (un == 0)
@@ -2198,7 +2238,8 @@
q->_mp_size = qn;
- mpz_add_ui (q, q, adjust);
+ if (adjust)
+ mpz_add_ui (q, q, 1);
if (un < 0)
mpz_neg (q, q);
}
@@ -2551,32 +2592,16 @@
}
static mp_bitcnt_t
-mpz_make_odd (mpz_t r, const mpz_t u)
+mpz_make_odd (mpz_t r)
{
- mp_size_t un, rn, i;
- mp_ptr rp;
- unsigned shift;
-
- un = GMP_ABS (u->_mp_size);
- assert (un > 0);
-
- for (i = 0; u->_mp_d[i] == 0; i++)
- ;
-
- gmp_ctz (shift, u->_mp_d[i]);
-
- rn = un - i;
- rp = MPZ_REALLOC (r, rn);
- if (shift > 0)
- {
- mpn_rshift (rp, u->_mp_d + i, rn, shift);
- rn -= (rp[rn-1] == 0);
- }
- else
- mpn_copyi (rp, u->_mp_d + i, rn);
-
- r->_mp_size = rn;
- return i * GMP_LIMB_BITS + shift;
+ mp_bitcnt_t shift;
+
+ assert (r->_mp_size > 0);
+ /* Count trailing zeros, equivalent to mpn_scan1, because we know that there is a 1 */
+ shift = mpn_common_scan (r->_mp_d[0], 0, r->_mp_d, 0, 0);
+ mpz_tdiv_q_2exp (r, r, shift);
+
+ return shift;
}
void
@@ -2599,8 +2624,10 @@
mpz_init (tu);
mpz_init (tv);
- uz = mpz_make_odd (tu, u);
- vz = mpz_make_odd (tv, v);
+ mpz_abs (tu, u);
+ uz = mpz_make_odd (tu);
+ mpz_abs (tv, v);
+ vz = mpz_make_odd (tv);
gz = GMP_MIN (uz, vz);
if (tu->_mp_size < tv->_mp_size)
@@ -2616,7 +2643,7 @@
{
int c;
- mpz_make_odd (tu, tu);
+ mpz_make_odd (tu);
c = mpz_cmp (tu, tv);
if (c == 0)
{
@@ -2678,8 +2705,10 @@
mpz_init (t0);
mpz_init (t1);
- uz = mpz_make_odd (tu, u);
- vz = mpz_make_odd (tv, v);
+ mpz_abs (tu, u);
+ uz = mpz_make_odd (tu);
+ mpz_abs (tv, v);
+ vz = mpz_make_odd (tv);
gz = GMP_MIN (uz, vz);
uz -= gz;
@@ -2727,7 +2756,7 @@
if (tu->_mp_size > 0)
{
mp_bitcnt_t shift;
- shift = mpz_make_odd (tu, tu);
+ shift = mpz_make_odd (tu);
mpz_mul_2exp (t0, t0, shift);
mpz_mul_2exp (s0, s0, shift);
power += shift;
@@ -2750,7 +2779,7 @@
mpz_add (t0, t0, t1);
mpz_add (s0, s0, s1);
- shift = mpz_make_odd (tv, tv);
+ shift = mpz_make_odd (tv);
mpz_mul_2exp (t1, t1, shift);
mpz_mul_2exp (s1, s1, shift);
}
@@ -2760,7 +2789,7 @@
mpz_add (t1, t0, t1);
mpz_add (s1, s0, s1);
- shift = mpz_make_odd (tu, tu);
+ shift = mpz_make_odd (tu);
mpz_mul_2exp (t0, t0, shift);
mpz_mul_2exp (s0, s0, shift);
}
@@ -3607,10 +3636,8 @@
{
mp_ptr up;
mp_size_t us, un, i;
- mp_limb_t limb, ux, uc;
- unsigned cnt;
-
- up = u->_mp_d;
+ mp_limb_t limb, ux;
+
us = u->_mp_size;
un = GMP_ABS (us);
i = starting_bit / GMP_LIMB_BITS;
@@ -3620,36 +3647,24 @@
if (i >= un)
return (us >= 0 ? ~(mp_bitcnt_t) 0 : starting_bit);
- if (us < 0)
+ up = u->_mp_d;
+ ux = 0;
+ limb = up[i];
+
+ if (starting_bit != 0)
{
- ux = GMP_LIMB_MAX;
- uc = mpn_zero_p (up, i);
+ if (us < 0)
+ {
+ ux = mpn_zero_p (up, i);
+ limb = ~ limb + ux;
+ ux = - (mp_limb_t) (limb >= ux);
+ }
+
+ /* Mask to 0 all bits before starting_bit, thus ignoring them. */
+ limb &= (GMP_LIMB_MAX << (starting_bit % GMP_LIMB_BITS));
}
- else
- ux = uc = 0;
-
- limb = (ux ^ up[i]) + uc;
- uc = limb < uc;
-
- /* Mask to 0 all bits before starting_bit, thus ignoring them. */
- limb &= (GMP_LIMB_MAX << (starting_bit % GMP_LIMB_BITS));
-
- while (limb == 0)
- {
- i++;
- if (i == un)
- {
- assert (uc == 0);
- /* For the u > 0 case, this can happen only for the first
- masked limb. For the u < 0 case, it happens when the
- highest limbs of the absolute value are all ones. */
- return (us >= 0 ? ~(mp_bitcnt_t) 0 : un * GMP_LIMB_BITS);
- }
- limb = (ux ^ up[i]) + uc;
- uc = limb < uc;
- }
- gmp_ctz (cnt, limb);
- return (mp_bitcnt_t) i * GMP_LIMB_BITS + cnt;
+
+ return mpn_common_scan (limb, i, up, un, ux);
}
mp_bitcnt_t
@@ -3657,10 +3672,8 @@
{
mp_ptr up;
mp_size_t us, un, i;
- mp_limb_t limb, ux, uc;
- unsigned cnt;
-
- up = u->_mp_d;
+ mp_limb_t limb, ux;
+
us = u->_mp_size;
un = GMP_ABS (us);
i = starting_bit / GMP_LIMB_BITS;
@@ -3670,33 +3683,21 @@
if (i >= un)
return (us >= 0 ? starting_bit : ~(mp_bitcnt_t) 0);
+ up = u->_mp_d;
+ ux = GMP_LIMB_MAX;
+ limb = ~ up[i];
+
if (us < 0)
{
- ux = GMP_LIMB_MAX;
- uc = mpn_zero_p (up, i);
+ ux = mpn_zero_p (up, i);
+ limb = ~ (limb + ux);
+ ux = 0;
}
- else
- ux = uc = 0;
-
- limb = (ux ^ up[i]) + uc;
- uc = limb < uc;
-
- /* Mask to 1 all bits before starting_bit, thus ignoring them. */
- limb |= ((mp_limb_t) 1 << (starting_bit % GMP_LIMB_BITS)) - 1;
-
- while (limb == GMP_LIMB_MAX)
- {
- i++;
- if (i == un)
- {
- assert (uc == 0);
More information about the gmp-commit
mailing list