[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