[Gmp-commit] /var/hg/gmp-proj/mini-gmp: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sat Jan 14 09:57:30 CET 2012
details: /var/hg/gmp-proj/mini-gmp/rev/57d03b410426
changeset: 80:57d03b410426
user: Niels M?ller <nisse at lysator.liu.se>
date: Sat Jan 14 00:50:37 2012 +0100
description:
Simplified mpz_scan1 considerably. Related changes:
New macro mpn_zero_p. Deleted mpz_divisible_2exp_p; inline the logic
including a call to mpn_zero_p in mpz_div_q_2exp, the only user.
details: /var/hg/gmp-proj/mini-gmp/rev/8d745da00b12
changeset: 81:8d745da00b12
user: Niels M?ller <nisse at lysator.liu.se>
date: Sat Jan 14 09:56:58 2012 +0100
description:
Simplified mpz_scan0.
details: /var/hg/gmp-proj/mini-gmp/rev/5d7c2121ca17
changeset: 82:5d7c2121ca17
user: Niels M?ller <nisse at lysator.liu.se>
date: Sat Jan 14 09:57:24 2012 +0100
description:
Whitespace cleanup.
diffstat:
mini-gmp.c | 293 +++++++++++++++++-------------------------------------------
1 files changed, 82 insertions(+), 211 deletions(-)
diffs (truncated from 364 to 300 lines):
diff -r e1a604332735 -r 5d7c2121ca17 mini-gmp.c
--- a/mini-gmp.c Sat Jan 14 00:24:54 2012 +0100
+++ b/mini-gmp.c Sat Jan 14 09:57:24 2012 +0100
@@ -328,6 +328,8 @@
return n;
}
+#define mpn_zero_p(xp, n) (mpn_normalized_size ((xp), (n)) == 0)
+
mp_limb_t
mpn_add_1 (mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_limb_t b)
{
@@ -2165,31 +2167,6 @@
mpz_div_qr (NULL, r, n, d, DIV_TRUNC);
}
-static int
-mpz_divisible_2exp_p (const mpz_t x, mp_bitcnt_t bit_index)
-{
- mp_size_t xn, limb_index;
- mp_ptr xp;
- mp_limb_t bit;
- mp_size_t i;
-
- xn = GMP_ABS (x->_mp_size);
- if (xn == 0)
- return 1;
-
- limb_index = bit_index / GMP_LIMB_BITS;
- if (limb_index >= xn)
- return 0;
-
- xp = x->_mp_d;
- for (i = limb_index; i-- > 0; )
- if (xp[i] != 0)
- return 0;
-
- bit = (mp_limb_t) 1 << (bit_index % GMP_LIMB_BITS);
- return (xp[limb_index] & (bit - 1)) == 0;
-}
-
static void
mpz_div_q_2exp (mpz_t q, const mpz_t u, mp_bitcnt_t bit_index,
enum mpz_div_round_mode mode)
@@ -2207,12 +2184,19 @@
}
limb_cnt = bit_index / GMP_LIMB_BITS;
qn = GMP_ABS (un) - limb_cnt;
-
+ bit_index %= GMP_LIMB_BITS;
+
+ adjust = 0;
if ( (mode == DIV_FLOOR && un < 0) || (mode == DIV_CEIL && un > 0))
- adjust = !mpz_divisible_2exp_p (u, bit_index);
+ /* Note: Below, the final indexing at limb_cnt is valid because at
+ that point we have qn > 0. */
+ adjust = (!mpn_zero_p (u->_mp_d, limb_cnt)
+ || qn <= 0
+ || (u->_mp_d[limb_cnt]
+ & (((mp_limb_t) 1 << bit_index) - 1)));
else
adjust = 0;
-
+
if (qn <= 0)
qn = 0;
@@ -2220,7 +2204,6 @@
{
qp = MPZ_REALLOC (q, qn);
- bit_index %= GMP_LIMB_BITS;
if (bit_index != 0)
{
mpn_rshift (qp, u->_mp_d + limb_cnt, qn, bit_index);
@@ -2270,7 +2253,7 @@
/* Have to negate and sign extend. */
mp_size_t i;
mp_limb_t cy;
-
+
for (cy = 1, i = 0; i < un; i++)
{
mp_limb_t s = ~u->_mp_d[i] + cy;
@@ -3530,210 +3513,98 @@
mp_bitcnt_t
mpz_scan1 (const mpz_t u, mp_bitcnt_t starting_bit)
{
- mp_limb_t *u_ptr;
- mp_size_t size;
- mp_size_t abs_size;
- mp_limb_t *u_end;
- mp_size_t starting_limb;
- mp_limb_t *p;
- mp_limb_t limb;
- int cnt;
-
- u_ptr = u->_mp_d;
- size = u->_mp_size;
- abs_size = GMP_ABS (size);
- u_end = u_ptr + abs_size;
- starting_limb = starting_bit / GMP_LIMB_BITS;
- p = u_ptr + starting_limb;
-
- /* Past the end there's no 1 bits for u>=0, or an immediate 1 bit for u<0.
- Notice this test picks up any u==0 too. */
- if (starting_limb >= abs_size)
- return (size >= 0 ? ULONG_MAX : starting_bit);
-
- limb = *p;
-
- if (size >= 0)
+ mp_ptr up;
+ mp_size_t us, un, i;
+ mp_limb_t limb, ux, uc;;
+ unsigned cnt;
+
+ up = u->_mp_d;
+ us = u->_mp_size;
+ un = GMP_ABS (us);
+ i = starting_bit / GMP_LIMB_BITS;
+
+ /* Past the end there's no 1 bits for u>=0, or an immediate 1 bit
+ for u<0. Notice this test picks up any u==0 too. */
+ if (i >= un)
+ return (us >= 0 ? ~(mp_bitcnt_t) 0 : starting_bit);
+
+ if (us < 0)
{
- /* Mask to 0 all bits before starting_bit, thus ignoring them. */
- limb &= (GMP_LIMB_MAX << (starting_bit % GMP_LIMB_BITS));
-
- if (limb == 0)
- {
- /* If it's the high limb which is zero after masking, then there's
- no 1 bits after starting_bit. */
- p++;
- if (p == u_end)
- return ULONG_MAX;
-
- /* Otherwise search further for a non-zero limb. The high limb is
- non-zero, if nothing else. */
- for (;;)
- {
- limb = *p;
- if (limb != 0)
- break;
- p++;
- }
- }
+ ux = GMP_LIMB_MAX;
+ uc = mpn_zero_p (up, i);
}
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)
{
- mp_srcptr q;
-
- /* If there's a non-zero limb before ours then we're in the ones
- complement region. Search from *(p-1) downwards since that might
- give better cache locality, and since a non-zero in the middle of a
- number is perhaps a touch more likely than at the end. */
- q = p;
- while (q != u_ptr)
+ i++;
+ if (i == un)
{
- q--;
- if (*q != 0)
- goto inverted;
+ 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);
}
-
- if (limb == 0)
- {
- /* Skip zero limbs, to find the start of twos complement. The
- high limb is non-zero, if nothing else. This search is
- necessary so the -limb is applied at the right spot. */
- do
- {
- p++;
- limb = *p;
- }
- while (limb == 0);
-
- /* Apply twos complement, and look for a 1 bit in that. Since
- limb!=0 here, also have (-limb)!=0 so there's certainly a 1
- bit. */
- limb = -limb;
- goto got_limb;
- }
-
- /* Adjust so ~limb implied by searching for 0 bit becomes -limb. */
- limb--;
-
- inverted:
- /* Now seeking a 0 bit. */
-
- /* Mask to 1 all bits before starting_bit, thus ignoring them. */
- limb |= (1UL << (starting_bit % GMP_LIMB_BITS)) - 1;
-
- /* Search for a limb which is not all ones. If the end is reached
- then the zero immediately past the end is the result. */
- while (limb == GMP_LIMB_MAX)
- {
- p++;
- if (p == u_end)
- return (mp_bitcnt_t) abs_size * GMP_LIMB_BITS;
- limb = *p;
- }
-
- /* Now seeking low 1 bit. */
- limb = ~limb;
+ limb = (ux ^ up[i]) + uc;
+ uc = limb < uc;
}
-
- got_limb:
gmp_ctz (cnt, limb);
- return (mp_bitcnt_t) (p - u_ptr) * GMP_LIMB_BITS + cnt;
+ return (mp_bitcnt_t) i * GMP_LIMB_BITS + cnt;
}
mp_bitcnt_t
mpz_scan0 (const mpz_t u, mp_bitcnt_t starting_bit)
{
- mp_limb_t *u_ptr;
- mp_size_t size;
- mp_size_t abs_size;
- mp_limb_t *u_end;
- mp_size_t starting_limb;
- mp_limb_t *p;
- mp_limb_t limb;
- int cnt;
-
- u_ptr = u->_mp_d;
- size = u->_mp_size;
- abs_size = GMP_ABS (size);
- u_end = u_ptr + abs_size;
- starting_limb = starting_bit / GMP_LIMB_BITS;
- p = u_ptr + starting_limb;
+ mp_ptr up;
+ mp_size_t us, un, i;
+ mp_limb_t limb, ux, uc;;
+ unsigned cnt;
+
+ up = u->_mp_d;
+ us = u->_mp_size;
+ un = GMP_ABS (us);
+ i = starting_bit / GMP_LIMB_BITS;
/* When past end, there's an immediate 0 bit for u>=0, or no 0 bits for
u<0. Notice this test picks up all cases of u==0 too. */
- if (starting_limb >= abs_size)
- return (size >= 0 ? starting_bit : ULONG_MAX);
-
- limb = *p;
-
- if (size >= 0)
+ if (i >= un)
+ return (us >= 0 ? starting_bit : ~(mp_bitcnt_t) 0);
+
+ if (us < 0)
{
- /* Mask to 1 all bits before starting_bit, thus ignoring them. */
- limb |= (1UL << (starting_bit % GMP_LIMB_BITS)) - 1;
-
- /* Search for a limb which isn't all ones. If the end is reached then
- the zero bit immediately past the end is returned. */
- while (limb == GMP_LIMB_MAX)
- {
- p++;
- if (p == u_end)
- return (mp_bitcnt_t) abs_size * GMP_LIMB_BITS;
- limb = *p;
- }
-
- /* Now seek low 1 bit. */
- limb = ~limb;
+ ux = GMP_LIMB_MAX;
+ uc = mpn_zero_p (up, i);
}
else
+ ux = uc = 0;
+
+ limb = (ux ^ up[i]) + uc;
+ uc = limb < uc;
+
More information about the gmp-commit
mailing list