[Gmp-commit] /var/hg/gmp: 3 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Fri Dec 21 00:28:13 UTC 2018
details: /var/hg/gmp/rev/47cfa7925988
changeset: 17735:47cfa7925988
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Fri Dec 21 00:23:06 2018 +0100
description:
mini-gmp/mini-gmp.c: Simplify mpz_{add_ui,sub_ui,ui_sub}.
details: /var/hg/gmp/rev/3f1afa83957e
changeset: 17736:3f1afa83957e
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Fri Dec 21 00:35:50 2018 +0100
description:
mini-gmp/mini-gmp.c: Initial support for non-standard limb sizes.
details: /var/hg/gmp/rev/37d769986c8f
changeset: 17737:37d769986c8f
user: "Marco Bodrato <bodrato at mail.dm.unipi.it>"
date: Fri Dec 21 01:07:08 2018 +0100
description:
mini-gmp (mpz_lucas_mod): Don't export if not testing.
diffstat:
mini-gmp/mini-gmp.c | 252 ++++++++++++++++++++++++++++++++------------
mini-gmp/tests/testutils.c | 1 +
2 files changed, 184 insertions(+), 69 deletions(-)
diffs (truncated from 450 to 300 lines):
diff -r 0b950ea75d42 -r 37d769986c8f mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Sat Dec 15 08:07:13 2018 +0100
+++ b/mini-gmp/mini-gmp.c Fri Dec 21 01:07:08 2018 +0100
@@ -129,6 +129,20 @@
#define gmp_umul_ppmm(w1, w0, u, v) \
do { \
+ int LOCAL_GMP_LIMB_BITS = GMP_LIMB_BITS; \
+ if (sizeof (unsigned int) >= 2 * sizeof (mp_limb_t)) \
+ { \
+ unsigned int __ww = (unsigned int) (u) * (v); \
+ w0 = (mp_limb_t) __ww; \
+ w1 = (mp_limb_t) (__ww >> LOCAL_GMP_LIMB_BITS); \
+ } \
+ else if (sizeof (unsigned long int) >= 2 * sizeof (mp_limb_t)) \
+ { \
+ unsigned long int __ww = (unsigned long int) (u) * (v); \
+ w0 = (mp_limb_t) __ww; \
+ w1 = (mp_limb_t) (__ww >> LOCAL_GMP_LIMB_BITS); \
+ } \
+ else { \
mp_limb_t __x0, __x1, __x2, __x3; \
unsigned __ul, __vl, __uh, __vh; \
mp_limb_t __u = (u), __v = (v); \
@@ -150,6 +164,7 @@
\
(w1) = __x3 + (__x1 >> (GMP_LIMB_BITS / 2)); \
(w0) = (__x1 << (GMP_LIMB_BITS / 2)) + (__x0 & GMP_LLIMB_MASK); \
+ } \
} while (0)
#define gmp_udiv_qrnnd_preinv(q, r, nh, nl, d, di) \
@@ -753,6 +768,18 @@
mp_limb_t
mpn_invert_3by2 (mp_limb_t u1, mp_limb_t u0)
{
+ int GMP_LIMB_BITS_MUL_3 = GMP_LIMB_BITS * 3;
+ if (sizeof (unsigned) * CHAR_BIT > GMP_LIMB_BITS_MUL_3)
+ {
+ return (((unsigned) 1 << GMP_LIMB_BITS_MUL_3) - 1) /
+ (((unsigned) u1 << GMP_LIMB_BITS_MUL_3 / 3) + u0);
+ }
+ else if (GMP_ULONG_BITS > GMP_LIMB_BITS_MUL_3)
+ {
+ return (((unsigned long) 1 << GMP_LIMB_BITS_MUL_3) - 1) /
+ (((unsigned long) u1 << GMP_LIMB_BITS_MUL_3 / 3) + u0);
+ }
+ else {
mp_limb_t r, p, m, ql;
unsigned ul, uh, qh;
@@ -854,6 +881,7 @@
}
return m;
+ }
}
struct gmp_div_inverse
@@ -1478,6 +1506,12 @@
if (x >= 0)
mpz_set_ui (r, x);
else /* (x < 0) */
+ if (GMP_LIMB_BITS < GMP_ULONG_BITS)
+ {
+ mpz_set_ui (r, GMP_NEG_CAST (unsigned long int, x));
+ mpz_neg (r, r);
+ }
+ else
{
r->_mp_size = -1;
MPZ_REALLOC (r, 1)[0] = GMP_NEG_CAST (unsigned long int, x);
@@ -1491,6 +1525,15 @@
{
r->_mp_size = 1;
MPZ_REALLOC (r, 1)[0] = x;
+ if (GMP_LIMB_BITS < GMP_ULONG_BITS)
+ {
+ int LOCAL_GMP_LIMB_BITS = GMP_LIMB_BITS;
+ while (x >>= LOCAL_GMP_LIMB_BITS)
+ {
+ ++ r->_mp_size;
+ MPZ_REALLOC (r, r->_mp_size)[r->_mp_size - 1] = x;
+ }
+ }
}
else
r->_mp_size = 0;
@@ -1539,7 +1582,10 @@
{
mp_size_t us = u->_mp_size;
- if (us == 1)
+ if (GMP_LIMB_BITS < GMP_ULONG_BITS)
+ return (LONG_MAX + LONG_MIN == 0 || mpz_cmp_ui (u, LONG_MAX) <= 0) &&
+ mpz_cmpabs_ui (u, GMP_NEG_CAST (unsigned long int, LONG_MIN)) <= 0;
+ else if (us == 1)
return u->_mp_d[0] <= LONG_MAX;
else if (us == -1)
return u->_mp_d[0] <= GMP_NEG_CAST (mp_limb_t, LONG_MIN);
@@ -1547,11 +1593,26 @@
return (us == 0);
}
+static int
+mpn_absfits_ulong_p (mp_srcptr up, mp_size_t un)
+{
+ int ulongsize = GMP_ULONG_BITS / GMP_LIMB_BITS;
+ mp_limb_t ulongrem = 0;
+
+ if (GMP_ULONG_BITS % GMP_LIMB_BITS != 0)
+ ulongrem = (mp_limb_t) (ULONG_MAX >> GMP_LIMB_BITS * ulongsize) + 1;
+
+ return un <= ulongsize || (up[ulongsize] < ulongrem && un == ulongsize + 1);
+}
+
int
mpz_fits_ulong_p (const mpz_t u)
{
mp_size_t us = u->_mp_size;
+ if (GMP_LIMB_BITS < GMP_ULONG_BITS)
+ return us >= 0 && mpn_absfits_ulong_p (u->_mp_d, us);
+
return (us == (us > 0));
}
@@ -1559,10 +1620,11 @@
mpz_get_si (const mpz_t u)
{
unsigned long r = mpz_get_ui (u);
+ unsigned long c = -LONG_MAX - LONG_MIN;
if (u->_mp_size < 0)
/* This expression is necessary to properly handle -LONG_MIN */
- return -(long) 1 - (long) ((r - 1) & LONG_MAX);
+ return -(long) c - (long) ((r - c) & LONG_MAX);
else
return (long) (r & LONG_MAX);
}
@@ -1570,6 +1632,17 @@
unsigned long int
mpz_get_ui (const mpz_t u)
{
+ if (GMP_LIMB_BITS < GMP_ULONG_BITS)
+ {
+ int LOCAL_GMP_LIMB_BITS = GMP_LIMB_BITS;
+ unsigned long r = 0;
+ mp_size_t n = GMP_ABS (u->_mp_size);
+ n = GMP_MIN (n, 1 + (GMP_ULONG_BITS - 1) / GMP_LIMB_BITS);
+ while (--n >= 0)
+ r = (r << LOCAL_GMP_LIMB_BITS) + u->_mp_d[n];
+ return r;
+ }
+
return u->_mp_size == 0 ? 0 : u->_mp_d[0];
}
@@ -1667,7 +1740,7 @@
r->_mp_size = 0;
return;
}
- B = 2.0 * (double) GMP_LIMB_HIGHBIT;
+ B = 4.0 * (double) (GMP_LIMB_HIGHBIT >> 1);
Bi = 1.0 / B;
for (rn = 1; x >= B; rn++)
x *= Bi;
@@ -1705,7 +1778,7 @@
mp_limb_t l;
mp_size_t un;
double x;
- double B = 2.0 * (double) GMP_LIMB_HIGHBIT;
+ double B = 4.0 * (double) (GMP_LIMB_HIGHBIT >> 1);
un = GMP_ABS (u->_mp_size);
@@ -1750,7 +1823,7 @@
{
xn = GMP_ABS (xn);
- B = 2.0 * (double) GMP_LIMB_HIGHBIT;
+ B = 4.0 * (double) (GMP_LIMB_HIGHBIT >> 1);
Bi = 1.0 / B;
/* Scale d so it can be compared with the top limb. */
@@ -1813,6 +1886,8 @@
return mpz_cmp_ui (u, v);
else if (usize >= 0)
return 1;
+ else if (GMP_LIMB_BITS < GMP_ULONG_BITS)
+ return - mpz_cmpabs_ui (u, GMP_NEG_CAST (unsigned long int, v));
else if (usize < -1)
return -1;
else /* usize == -1 */
@@ -1830,6 +1905,8 @@
if (usize < 0)
return -1;
+ else if (GMP_LIMB_BITS < GMP_ULONG_BITS)
+ return mpz_cmpabs_ui (u, v);
else if (usize > 1)
return 1;
else
@@ -1856,7 +1933,9 @@
int
mpz_cmpabs_ui (const mpz_t u, unsigned long v)
{
- if (GMP_ABS (u->_mp_size) > 1)
+ mp_size_t un = GMP_ABS (u->_mp_size);
+
+ if (! mpn_absfits_ulong_p (u->_mp_d, un))
return 1;
else
{
@@ -1897,81 +1976,58 @@
/* MPZ addition and subtraction */
-/* Adds to the absolute value. Returns new size, but doesn't store it. */
-static mp_size_t
-mpz_abs_add_ui (mpz_t r, const mpz_t a, unsigned long b)
-{
- mp_size_t an;
- mp_ptr rp;
- mp_limb_t cy;
-
- an = GMP_ABS (a->_mp_size);
- if (an == 0)
- {
- MPZ_REALLOC (r, 1)[0] = b;
- return b > 0;
- }
-
- rp = MPZ_REALLOC (r, an + 1);
-
- cy = mpn_add_1 (rp, a->_mp_d, an, b);
- rp[an] = cy;
- an += cy;
-
- return an;
-}
-
-/* Subtract from the absolute value. Returns new size, (or -1 on underflow),
- but doesn't store it. */
-static mp_size_t
-mpz_abs_sub_ui (mpz_t r, const mpz_t a, unsigned long b)
-{
- mp_size_t an = GMP_ABS (a->_mp_size);
- mp_ptr rp;
-
- if (an == 0)
- {
- MPZ_REALLOC (r, 1)[0] = b;
- return -(b > 0);
- }
- rp = MPZ_REALLOC (r, an);
- if (an == 1 && a->_mp_d[0] < b)
- {
- rp[0] = b - a->_mp_d[0];
- return -1;
- }
- else
- {
- gmp_assert_nocarry (mpn_sub_1 (rp, a->_mp_d, an, b));
- return mpn_normalized_size (rp, an);
- }
-}
void
mpz_add_ui (mpz_t r, const mpz_t a, unsigned long b)
{
- if (a->_mp_size >= 0)
- r->_mp_size = mpz_abs_add_ui (r, a, b);
+ if (b > GMP_LIMB_MAX)
+ {
+ mpz_t bb;
+ mpz_init_set_ui (bb, b);
+ mpz_add (r, a, bb);
+ mpz_clear (bb);
+ }
else
- r->_mp_size = -mpz_abs_sub_ui (r, a, b);
+ {
+ mp_size_t an = a->_mp_size;
+
+ if (an == 0)
+ mpz_set_ui (r, b);
+ else if (an > 0)
+ {
+ mp_ptr rp = MPZ_REALLOC (r, an + 1);
+ mp_limb_t cy = mpn_add_1 (rp, a->_mp_d, an, b);
+ rp[an] = cy;
+ r->_mp_size = an + cy;
+ }
+ else
+ {
+ mp_ptr rp = MPZ_REALLOC (r, -an);
+ an = -an;
+
+ if (mpn_sub_1 (rp, a->_mp_d, an, b) != 0)
More information about the gmp-commit
mailing list