[Gmp-commit] /var/hg/gmp-proj/mini-gmp: 2 new changesets

mercurial at gmplib.org mercurial at gmplib.org
Fri Dec 30 22:42:32 CET 2011


details:   /var/hg/gmp-proj/mini-gmp/rev/2d2243feeca3
changeset: 21:2d2243feeca3
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Fri Dec 30 22:27:10 2011 +0100
description:
Implemented mpn_get_str and mpn_set_str, and optimized.

details:   /var/hg/gmp-proj/mini-gmp/rev/31a06c346680
changeset: 22:31a06c346680
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Fri Dec 30 22:42:22 2011 +0100
description:
Merged ws changes.

diffstat:

 mini-gmp.c    |  598 ++++++++++++++++++++++++++++++++++++---------------------
 mini-gmp.h    |    3 +
 tests/t-str.c |    5 +-
 3 files changed, 386 insertions(+), 220 deletions(-)

diffs (truncated from 953 to 300 lines):

diff -r 367d6a1549b5 -r 31a06c346680 mini-gmp.c
--- a/mini-gmp.c	Fri Dec 30 16:43:45 2011 +0100
+++ b/mini-gmp.c	Fri Dec 30 22:42:22 2011 +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, 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 Free Software Foundation,
+Inc.
 
 This file is part of the GNU MP Library.
 
@@ -83,7 +83,7 @@
 #define GMP_LIMB_HIGHBIT ((mp_limb_t) 1 << (GMP_LIMB_BITS - 1))
 
 #define GMP_HLIMB_BIT ((mp_limb_t) 1 << (GMP_LIMB_BITS / 2))
-#define GMP_LLIMB_MASK (GMP_HLIMB_BIT - 1) 
+#define GMP_LLIMB_MASK (GMP_HLIMB_BIT - 1)
 
 #define ABS(x) ((x) >= 0 ? (x) : -(x))
 
@@ -104,7 +104,7 @@
   do {									\
     mp_limb_t __x;							\
     __x = (al) - (bl);							\
-    (sh) = (ah) - (bh) - ((al) < (bl));                                 \
+    (sh) = (ah) - (bh) - ((al) < (bl));					\
     (sl) = __x;								\
   } while (0)
 
@@ -180,57 +180,12 @@
   } while (0)
 
 /* Swap macros. */
-#define MP_LIMB_T_SWAP(x, y)						\
+#define UCHAR_SWAP(x, y)						\
   do {									\
-    mp_limb_t __mp_limb_t_swap__tmp = (x);				\
+    unsigned char __uchar_swap__tmp = (x);				\
     (x) = (y);								\
-    (y) = __mp_limb_t_swap__tmp;					\
+    (y) = __uchar_swap__tmp;						\
   } while (0)
-#define MP_SIZE_T_SWAP(x, y)						\
-  do {									\
-    mp_size_t __mp_size_t_swap__tmp = (x);				\
-    (x) = (y);								\
-    (y) = __mp_size_t_swap__tmp;					\
-  } while (0)
-
-#define MP_PTR_SWAP(x, y)						\
-  do {									\
-    mp_ptr __mp_ptr_swap__tmp = (x);					\
-    (x) = (y);								\
-    (y) = __mp_ptr_swap__tmp;						\
-  } while (0)
-#define MP_SRCPTR_SWAP(x, y)						\
-  do {									\
-    mp_srcptr __mp_srcptr_swap__tmp = (x);				\
-    (x) = (y);								\
-    (y) = __mp_srcptr_swap__tmp;					\
-  } while (0)
-
-#define MPN_PTR_SWAP(xp,xs, yp,ys)					\
-  do {									\
-    MP_PTR_SWAP (xp, yp);						\
-    MP_SIZE_T_SWAP (xs, ys);						\
-  } while(0)
-#define MPN_SRCPTR_SWAP(xp,xs, yp,ys)					\
-  do {									\
-    MP_SRCPTR_SWAP (xp, yp);						\
-    MP_SIZE_T_SWAP (xs, ys);						\
-  } while(0)
-
-#define MPZ_PTR_SWAP(x, y)						\
-  do {									\
-    mpz_ptr __mpz_ptr_swap__tmp = (x);					\
-    (x) = (y);								\
-    (y) = __mpz_ptr_swap__tmp;						\
-  } while (0)
-#define MPZ_SRCPTR_SWAP(x, y)						\
-  do {									\
-    mpz_srcptr __mpz_srcptr_swap__tmp = (x);				\
-    (x) = (y);								\
-    (y) = __mpz_srcptr_swap__tmp;					\
-  } while (0)
-/* Swap macros. */
-
 #define MP_LIMB_T_SWAP(x, y)						\
   do {									\
     mp_limb_t __mp_limb_t_swap__tmp = (x);				\
@@ -318,11 +273,11 @@
   assert (size > 0);
 
   p = realloc (old, size * sizeof(mp_limb_t));
-  
+
   if (!p)
     die("virtual memory exhausted.");
 
-  return p;  
+  return p;
 }
 
 
@@ -349,11 +304,30 @@
   return 0;
 }
 
+static int
+mpn_cmp4 (mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn)
+{
+  if (an > bn)
+    return 1;
+  else if (an < bn)
+    return -1;
+  else
+    return mpn_cmp (ap, bp, an);
+}
+
+static mp_size_t
+mpn_normalized_size (mp_srcptr xp, mp_size_t n)
+{
+  for (; n > 0 && xp[n-1] == 0; n--)
+    ;
+  return n;
+}
+
 mp_limb_t
 mpn_add_1 (mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_limb_t b)
 {
   mp_size_t i;
-  
+
   assert (n > 0);
 
   for (i = 0; i < n; i++)
@@ -402,7 +376,7 @@
 mpn_sub_1 (mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_limb_t b)
 {
   mp_size_t i;
-  
+
   assert (n > 0);
 
   for (i = 0; i < n; i++)
@@ -410,7 +384,7 @@
       mp_limb_t a = ap[i];
       /* Carry out */
       mp_limb_t cy = a < b;;
-      rp[i] = a - b; 
+      rp[i] = a - b;
       b = cy;
     }
   return b;
@@ -544,7 +518,7 @@
       rp += 1, vp += 1, vn -= 1;
     }
   return rp[un - 1];
-}  
+}
 
 void
 mpn_mul_n (mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
@@ -634,7 +608,7 @@
 
   qh = ~u1 / uh;
   r = ((~u1 - (mp_limb_t) qh * uh) << (GMP_LIMB_BITS / 2)) | GMP_LLIMB_MASK;
-  
+
   p = (mp_limb_t) qh * ul;
   /* Adjustment steps taken from udiv_qrnnd_c */
   if (r < p)
@@ -718,7 +692,7 @@
 mpn_div_qr_1_invert (struct div_qr_1_inverse *inv, mp_limb_t d)
 {
   unsigned shift;
-  left_normalize_limb (shift, d);  
+  left_normalize_limb (shift, d);
   inv->shift = shift;
   inv->d = d;
   inv->di = mpn_invert_limb (d);
@@ -800,7 +774,7 @@
       r0 = (r0 >> shift) | (r1 << (GMP_LIMB_BITS - shift));
       r1 >>= shift;
     }
-  
+
   rp[1] = r1;
   rp[0] = r0;
 }
@@ -812,7 +786,7 @@
 		mp_limb_t dinv)
 {
   mp_size_t i;
-  
+
   mp_limb_t d1, d0;
   mp_limb_t cy, cy1;
   mp_limb_t q;
@@ -877,12 +851,12 @@
   else if (dn == 2)
     mpn_div_qr_2 (qp, np, np, nn, dp[1], dp[0]);
   else
-    {      
+    {
       mp_ptr tp;
       mp_limb_t d1, d0, di;
       mp_limb_t nh;
       unsigned shift;
-      
+
       d1 = dp[dn - 1];
 
       left_normalize_limb (shift, d1);
@@ -910,23 +884,264 @@
     }
 }
 
-static int
-mpn_cmp4 (mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn)
+struct mpn_base_info
 {
-  if (an > bn)
-    return 1;
-  else if (an < bn)
-    return -1;
+  /* When base is a power of two, bits is non-zero and the other
+     fields are unused. For other bases, bits is zero and bb is the
+     largest power of the base which fits in one limb. */
+  unsigned bits;
+  unsigned exp;
+  mp_limb_t bb;
+};
+
+static void
+mpn_get_base_info (struct mpn_base_info *info, mp_limb_t b)
+{
+  if ( (b & (b-1)) == 0)
+    {
+      /* Power of two */
+      switch (b)
+	{
+	case 2:
+	  info->bits = 1;
+	  break;
+	case 4:
+	  info->bits = 2;
+	  break;
+	case 8:
+	  info->bits = 3;
+	  break;
+	case 16:
+	  info->bits = 4;
+	  break;
+	case 32:
+	  info->bits = 5;
+	  break;
+	case 64:
+	  info->bits = 6;
+	  break;
+	case 128:
+	  info->bits = 7;
+	  break;
+	case 256:
+	  info->bits = 8;
+	  break;
+	default:
+	  die ("Unsupported base.");
+	}
+    }
   else
-    return mpn_cmp (ap, bp, an);
+    {
+      mp_limb_t m;
+      mp_limb_t p;
+      unsigned exp;
+
+      m = MP_LIMB_T_MAX / b;
+      for (exp = 1, p = b; p <= m; exp++)
+	p *= b;
+
+      info->bits = 0;
+      info->exp = exp;
+      info->bb = p;
+    }
+}
+
+mp_bitcnt_t
+limb_size_in_base_2 (mp_limb_t u)
+{
+  mp_bitcnt_t bits;
+  for (bits = 0; u > 0; bits++)
+    u >>= 1;
+
+  return bits;
+}


More information about the gmp-commit mailing list