[Gmp-commit] /var/hg/gmp-proj/mini-gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Tue Jan 3 22:14:55 CET 2012
details: /var/hg/gmp-proj/mini-gmp/rev/bbc347ced82c
changeset: 38:bbc347ced82c
user: Niels M?ller <nisse at lysator.liu.se>
date: Mon Jan 02 22:15:11 2012 +0100
description:
Updated list of functions left to do.
details: /var/hg/gmp-proj/mini-gmp/rev/350e6927f88a
changeset: 39:350e6927f88a
user: Niels M?ller <nisse at lysator.liu.se>
date: Tue Jan 03 21:37:38 2012 +0100
description:
Implemented bit op and logical operations.
details: /var/hg/gmp-proj/mini-gmp/rev/7dc249a96d28
changeset: 40:7dc249a96d28
user: Niels M?ller <nisse at lysator.liu.se>
date: Tue Jan 03 21:56:59 2012 +0100
description:
mpn_div_qr_1: handle powers of two by shifting.
mpz_div_qr_ui: Allow q and r NULL in all cases. Handle DIV_EXACT.
mpz_divexact_ui: Call mpz_div_qr_ui with mode DIV_EXACT.
mpz_divexact_2exp: Deleted
mpz_gcdext: Use mpz_divexact_ui rather than mpz_divexact_2exp.
details: /var/hg/gmp-proj/mini-gmp/rev/1b62bce64f48
changeset: 41:1b62bce64f48
user: Niels M?ller <nisse at lysator.liu.se>
date: Tue Jan 03 22:14:16 2012 +0100
description:
Direct handling of zero input to mpz_and and mpz_xor.
diffstat:
.hgignore | 3 +-
mini-gmp.c | 453 ++++++++++++++++++++++++++++++++++++++++++++--------
mini-gmp.h | 8 +
tests/Makefile | 6 +-
tests/hex-random.c | 11 +-
tests/hex-random.h | 3 +-
6 files changed, 408 insertions(+), 76 deletions(-)
diffs (truncated from 635 to 300 lines):
diff -r 4bdf488fa1a3 -r 1b62bce64f48 .hgignore
--- a/.hgignore Mon Jan 02 21:58:47 2012 +0100
+++ b/.hgignore Tue Jan 03 22:14:16 2012 +0100
@@ -9,5 +9,6 @@
^tests/t-invert$
^tests/t-div$
^tests/t-double$
+^tests/t-gcd$
+^tests/t-logops$
^tests/t-str$
-^tests/t-gcd$
diff -r 4bdf488fa1a3 -r 1b62bce64f48 mini-gmp.c
--- a/mini-gmp.c Mon Jan 02 21:58:47 2012 +0100
+++ b/mini-gmp.c Tue Jan 03 22:14:16 2012 +0100
@@ -28,23 +28,17 @@
/* Missing functions, needed by guile:
- mpz_and
mpz_cmp_d
- mpz_com
- mpz_divexact_ui
mpz_divisible_p
mpz_divisible_ui_p
mpz_export
mpz_getlimbn
mpz_hamdist
- mpz_ior
mpz_lcm_ui
- mpz_neg
mpz_popcount
mpz_powm
mpz_sqrtrem
mpz_tstbit
- mpz_xor
*/
#include <assert.h>
#include <ctype.h>
@@ -745,9 +739,24 @@
static mp_limb_t
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);
- return mpn_div_qr_1_preinv (qp, np, nn, &inv);
+ assert (d > 0);
+
+ if (d > 1 && (d & (d-1)) == 0)
+ {
+ /* Power of two */
+ unsigned shift;
+ mp_limb_t r = np[0] & (d-1);
+ count_trailing_zeros (shift, d);
+ mpn_rshift (qp, np, nn, shift);
+
+ return r;
+ }
+ else
+ {
+ struct div_qr_1_inverse inv;
+ mpn_div_qr_1_invert (&inv, d);
+ return mpn_div_qr_1_preinv (qp, np, nn, &inv);
+ }
}
static void
@@ -1793,7 +1802,10 @@
ns = n->_mp_size;
if (ns == 0)
{
- q->_mp_size = r->_mp_size = 0;
+ if (q)
+ q->_mp_size = 0;
+ if (r)
+ r->_mp_size = 0;
return 0;
}
@@ -1806,6 +1818,8 @@
rl = mpn_div_qr_1 (qp, n->_mp_d, qn, d);
assert (rl < d);
+ assert (mode != DIV_EXACT || rl == 0);
+
rs = rl > 0;
rs = (ns < 0) ? -rs : rs;
@@ -1817,7 +1831,7 @@
rl = d - rl;
rs = -rs;
}
-
+
if (r)
{
r->_mp_d[0] = rl;
@@ -1891,7 +1905,7 @@
void
mpz_divexact_ui (mpz_t q, const mpz_t n, unsigned long d)
{
- assert_nocarry (mpz_tdiv_q_ui (q, n, d));
+ mpz_div_qr_ui (q, NULL, n, d, DIV_EXACT);
}
static mp_limb_t
@@ -2060,41 +2074,6 @@
mpz_mul_2exp (g, g, gz);
}
-static void
-mpz_divexact_2exp (mpz_t q, const mpz_t u, mp_bitcnt_t e)
-{
- mp_size_t un, qn, limbs, i;
- mp_ptr qp;
- unsigned shift;
-
- un = ABS (u->_mp_size);
-
- if (un == 0)
- {
- q->_mp_size = 0;
- return;
- }
-
- limbs = e / GMP_LIMB_BITS;
- shift = e % GMP_LIMB_BITS;
-
- assert (limbs < un);
- for (i = 0; i < limbs; i++)
- assert (u->_mp_d[i] == 0);
-
- qn = un - limbs;
- qp = MPZ_REALLOC (q, qn);
- if (shift > 0)
- {
- mpn_rshift (qp, u->_mp_d + limbs, qn, shift);
- qn -= (qp[qn-1] == 0);
- }
- else
- mpn_copyi (qp, u->_mp_d + limbs, qn);
-
- q->_mp_size = (u->_mp_size) < 0 ? - qn : qn;
-}
-
void
mpz_gcdext (mpz_t g, mpz_t s, mpz_t t, const mpz_t u, const mpz_t v)
{
@@ -2112,6 +2091,7 @@
mpz_set_si (t, mpz_sgn (v));
return;
}
+
if (v->_mp_size == 0)
{
/* g = sgn(u) u + 0 v */
@@ -2120,7 +2100,6 @@
mpz_set_si (s, mpz_sgn (u));
if (t)
mpz_set_ui (t, 0);
-
return;
}
@@ -2243,8 +2222,8 @@
mpz_sub (s0, s0, s1);
mpz_add (t0, t0, t1);
}
- mpz_divexact_2exp (s0, s0, 1);
- mpz_divexact_2exp (t0, t0, 1);
+ mpz_divexact_ui (s0, s0, 2);
+ mpz_divexact_ui (t0, t0, 2);
}
/* Arrange so that |s| < |u| / 2g */
@@ -2273,35 +2252,367 @@
mpz_clear (t1);
}
+/* For logical and bit-manipulation operations, numbers are treated as
+ if represented in two's complement (and infinitely sign extended).
+ For a negative values we get the two's complement from -x = ~x + 1,
+ where ~ is bitwise complementt. Negation transforms
+
+ xxxx10...0
+
+ into
+
+ yyyy10...0
+
+ where yyyy is the bitwise complement of xxxx. So least significant
+ bits, up to and including the first one bit, are unchanged, and
+ the more significant bits are all complemented.
+
+ To change a bit from zero to one in a negative number, subtract the
+ corresponding power of two from the absolute value. This can never
+ underflow. To change a bit from one to zero, add the corresponding
+ power of two, and this might overflow. E.g., if x = -001111, the
+ two's complement is 110001. Clearing the least significant bit, we
+ get two's complement 110000, and -010000. */
+
+int
+mpz_tstbit (const mpz_t d, mp_bitcnt_t bit_index)
+{
+ mp_size_t limb_index;
+ unsigned shift;
+ mp_size_t ds;
+ mp_size_t dn;
+ mp_limb_t w;
+ int bit;
+
+ ds = d->_mp_size;
+ dn = ABS (ds);
+ limb_index = bit_index / GMP_LIMB_BITS;
+ if (limb_index >= dn)
+ return ds < 0;
+
+ shift = bit_index % GMP_LIMB_BITS;
+ w = d->_mp_d[limb_index];
+ bit = (w >> shift) & 1;
+
+ if (ds < 0)
+ {
+ /* d < 0. Check if any of the bits below is set: If so, our bit
+ must be complemented. */
+ if (shift > 0 && (w << (GMP_LIMB_BITS - shift)) > 0)
+ return bit ^ 1;
+ while (limb_index-- > 0)
+ if (d->_mp_d[limb_index] > 0)
+ return bit ^ 1;
+ }
+ return bit;
+}
+
+static void
+mpz_abs_add_bit (mpz_t d, mp_bitcnt_t bit_index)
+{
+ mp_size_t dn, limb_index;
+ mp_limb_t bit;
+ mp_ptr dp;
+
+ dn = ABS (d->_mp_size);
+
+ limb_index = bit_index / GMP_LIMB_BITS;
+ bit = (mp_limb_t) 1 << (bit_index % GMP_LIMB_BITS);
+
+ if (limb_index >= dn)
+ {
+ mp_size_t i;
+ /* The bit should be set outside of the end of the number.
+ We have to increase the size of the number. */
+ dp = MPZ_REALLOC (d, limb_index + 1);
+
+ dp[limb_index] = bit;
+ for (i = dn; i < limb_index; i++)
+ dp[i] = 0;
+ dn = limb_index + 1;
+ }
+ else
+ {
+ mp_limb_t cy;
+
+ dp = d->_mp_d;
+
+ cy = mpn_add_1 (dp + limb_index, dp + limb_index, dn - limb_index, bit);
+ if (cy > 0)
+ {
+ dp = MPZ_REALLOC (d, dn + 1);
+ dp[dn++] = cy;
+ }
+ }
+
+ d->_mp_size = (d->_mp_size < 0) ? - dn : dn;
+}
+
+static void
+mpz_abs_sub_bit (mpz_t d, mp_bitcnt_t bit_index)
+{
+ mp_size_t dn, limb_index;
+ mp_ptr dp;
+ mp_limb_t bit;
+
+ dn = ABS (d->_mp_size);
+ dp = d->_mp_d;
+
+ limb_index = bit_index / GMP_LIMB_BITS;
+ bit = (mp_limb_t) 1 << (bit_index % GMP_LIMB_BITS);
+
+ assert (limb_index < dn);
+
+ assert_nocarry (mpn_sub_1 (dp + limb_index, dp + limb_index,
+ dn - limb_index, bit));
+ dn -= (dp[dn-1] == 0);
+ d->_mp_size = (d->_mp_size < 0) ? - dn : dn;
+}
+
void
mpz_setbit (mpz_t d, mp_bitcnt_t bit_index)
{
- mp_size_t dsize = d->_mp_size;
- mp_ptr dp = d->_mp_d;
More information about the gmp-commit
mailing list