[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