ext/html; charset=UTF-8 Last-Modified: Mon, 02 Nov 2026 11:33:17 GMT Expires: Thu, 30 Oct 2036 11:33:17 GMT Update embedded mini-gmp to version 6.2.0 (#9396) - minetest.git - modified minetest for gpcfs purposes
aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorMaksim <MoNTE48@mail.ua>2020-02-14 20:36:41 +0100
committerGitHub <noreply@github.com>2020-02-14 20:36:41 +0100
commit71899e11d2cf4674eb8b543905cf4f2df8a8339c (patch)
tree87251b8f5f709eb8b8dae6ec141dc0c736d88b93 /lib
parentff769e7df592e3dd5e94ff2ab2ad3bd7cb313f21 (diff)
Update embedded mini-gmp to version 6.2.0 (#9396)
Diffstat (limited to 'lib')
-rw-r--r--lib/gmp/mini-gmp.c1810
-rw-r--r--lib/gmp/mini-gmp.h41
2 files changed, 1159 insertions, 692 deletions
diff --git a/lib/gmp/mini-gmp.c b/lib/gmp/mini-gmp.c
index f3b43fbe8..e2e686123 100644
--- a/lib/gmp/mini-gmp.c
+++ b/lib/gmp/mini-gmp.c
@@ -2,9 +2,7 @@
Contributed to the GNU project by Niels Möller
-Copyright 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1999, 2000, 2001,
-2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013
-Free Software Foundation, Inc.
+Copyright 1991-1997, 1999-2019 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -41,11 +39,15 @@ along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
#include "mini-gmp.h"
-
+#if !defined(MINI_GMP_DONT_USE_FLOAT_H)
+#include <float.h>
+#endif
+
+
/* Macros */
#define GMP_LIMB_BITS (sizeof(mp_limb_t) * CHAR_BIT)
-#define GMP_LIMB_MAX (~ (mp_limb_t) 0)
+#define GMP_LIMB_MAX ((mp_limb_t) ~ (mp_limb_t) 0)
#define GMP_LIMB_HIGHBIT ((mp_limb_t) 1 << (GMP_LIMB_BITS - 1))
#define GMP_HLIMB_BIT ((mp_limb_t) 1 << (GMP_LIMB_BITS / 2))
@@ -60,18 +62,34 @@ along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
#define GMP_MIN(a, b) ((a) < (b) ? (a) : (b))
#define GMP_MAX(a, b) ((a) > (b) ? (a) : (b))
+#define GMP_CMP(a,b) (((a) > (b)) - ((a) < (b)))
+
+#if defined(DBL_MANT_DIG) && FLT_RADIX == 2
+#define GMP_DBL_MANT_BITS DBL_MANT_DIG
+#else
+#define GMP_DBL_MANT_BITS (53)
+#endif
+
+/* Return non-zero if xp,xsize and yp,ysize overlap.
+ If xp+xsize<=yp there's no overlap, or if yp+ysize<=xp there's no
+ overlap. If both these are false, there's an overlap. */
+#define GMP_MPN_OVERLAP_P(xp, xsize, yp, ysize) \
+ ((xp) + (xsize) > (yp) && (yp) + (ysize) > (xp))
+
#define gmp_assert_nocarry(x) do { \
- mp_limb_t __cy = x; \
+ mp_limb_t __cy = (x); \
assert (__cy == 0); \
} while (0)
#define gmp_clz(count, x) do { \
mp_limb_t __clz_x = (x); \
- unsigned __clz_c; \
- for (__clz_c = 0; \
- (__clz_x & ((mp_limb_t) 0xff << (GMP_LIMB_BITS - 8))) == 0; \
- __clz_c += 8) \
- __clz_x <<= 8; \
+ unsigned __clz_c = 0; \
+ int LOCAL_SHIFT_BITS = 8; \
+ if (GMP_LIMB_BITS > LOCAL_SHIFT_BITS) \
+ for (; \
+ (__clz_x & ((mp_limb_t) 0xff << (GMP_LIMB_BITS - 8))) == 0; \
+ __clz_c += 8) \
+ { __clz_x <<= LOCAL_SHIFT_BITS; } \
for (; (__clz_x & GMP_LIMB_HIGHBIT) == 0; __clz_c++) \
__clz_x <<= 1; \
(count) = __clz_c; \
@@ -102,27 +120,42 @@ along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
#define gmp_umul_ppmm(w1, w0, u, v) \
do { \
- mp_limb_t __x0, __x1, __x2, __x3; \
- unsigned __ul, __vl, __uh, __vh; \
- mp_limb_t __u = (u), __v = (v); \
+ int LOCAL_GMP_LIMB_BITS = GMP_LIMB_BITS; \
+ if (sizeof(unsigned int) * CHAR_BIT >= 2 * GMP_LIMB_BITS) \
+ { \
+ unsigned int __ww = (unsigned int) (u) * (v); \
+ w0 = (mp_limb_t) __ww; \
+ w1 = (mp_limb_t) (__ww >> LOCAL_GMP_LIMB_BITS); \
+ } \
+ else if (GMP_ULONG_BITS >= 2 * GMP_LIMB_BITS) \
+ { \
+ 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); \
\
- __ul = __u & GMP_LLIMB_MASK; \
- __uh = __u >> (GMP_LIMB_BITS / 2); \
- __vl = __v & GMP_LLIMB_MASK; \
- __vh = __v >> (GMP_LIMB_BITS / 2); \
+ __ul = __u & GMP_LLIMB_MASK; \
+ __uh = __u >> (GMP_LIMB_BITS / 2); \
+ __vl = __v & GMP_LLIMB_MASK; \
+ __vh = __v >> (GMP_LIMB_BITS / 2); \
\
- __x0 = (mp_limb_t) __ul * __vl; \
- __x1 = (mp_limb_t) __ul * __vh; \
- __x2 = (mp_limb_t) __uh * __vl; \
- __x3 = (mp_limb_t) __uh * __vh; \
+ __x0 = (mp_limb_t) __ul * __vl; \
+ __x1 = (mp_limb_t) __ul * __vh; \
+ __x2 = (mp_limb_t) __uh * __vl; \
+ __x3 = (mp_limb_t) __uh * __vh; \
\
- __x1 += __x0 >> (GMP_LIMB_BITS / 2);/* this can't give carry */ \
- __x1 += __x2; /* but this indeed can */ \
- if (__x1 < __x2) /* did we get it? */ \
- __x3 += GMP_HLIMB_BIT; /* yes, add it in the proper pos. */ \
+ __x1 += __x0 >> (GMP_LIMB_BITS / 2);/* this can't give carry */ \
+ __x1 += __x2; /* but this indeed can */ \
+ if (__x1 < __x2) /* did we get it? */ \
+ __x3 += GMP_HLIMB_BIT; /* yes, add it in the proper pos. */ \
\
- (w1) = __x3 + (__x1 >> (GMP_LIMB_BITS / 2)); \
- (w0) = (__x1 << (GMP_LIMB_BITS / 2)) + (__x0 & GMP_LLIMB_MASK); \
+ (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) \
@@ -222,11 +255,13 @@ along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
} while (0)
#define MPZ_SRCPTR_SWAP(x, y) \
do { \
- mpz_srcptr __mpz_srcptr_swap__tmp = (x); \
+ mpz_srcptr __mpz_srcptr_swap__tmp = (x); \
(x) = (y); \
(y) = __mpz_srcptr_swap__tmp; \
} while (0)
+const int mp_bits_per_limb = GMP_LIMB_BITS;
+
/* Memory allocation and other helper functions. */
static void
@@ -251,20 +286,20 @@ gmp_default_alloc (size_t size)
}
static void *
-gmp_default_realloc (void *old, size_t old_size, size_t new_size)
+gmp_default_realloc (void *old, size_t unused_old_size, size_t new_size)
{
- mp_ptr p;
+ void * p;
p = realloc (old, new_size);
if (!p)
- gmp_die("gmp_default_realoc: Virtual memory exhausted.");
+ gmp_die("gmp_default_realloc: Virtual memory exhausted.");
return p;
}
static void
-gmp_default_free (void *p, size_t size)
+gmp_default_free (void *p, size_t unused_size)
{
free (p);
}
@@ -311,14 +346,14 @@ mp_set_memory_functions (void *(*alloc_func) (size_t),
static mp_ptr
gmp_xalloc_limbs (mp_size_t size)
{
- return gmp_xalloc (size * sizeof (mp_limb_t));
+ return (mp_ptr) gmp_xalloc (size * sizeof (mp_limb_t));
}
static mp_ptr
gmp_xrealloc_limbs (mp_ptr old, mp_size_t size)
{
assert (size > 0);
- return (*gmp_reallocate_func) (old, 0, size * sizeof (mp_limb_t));
+ return (mp_ptr) (*gmp_reallocate_func) (old, 0, size * sizeof (mp_limb_t));
}
@@ -335,19 +370,17 @@ mpn_copyi (mp_ptr d, mp_srcptr s, mp_size_t n)
void
mpn_copyd (mp_ptr d, mp_srcptr s, mp_size_t n)
{
- while (n-- > 0)
+ while (--n >= 0)
d[n] = s[n];
}
int
mpn_cmp (mp_srcptr ap, mp_srcptr bp, mp_size_t n)
{
- for (; n > 0; n--)
+ while (--n >= 0)
{
- if (ap[n-1] < bp[n-1])
- return -1;
- else if (ap[n-1] > bp[n-1])
- return 1;
+ if (ap[n] != bp[n])
+ return ap[n] > bp[n] ? 1 : -1;
}
return 0;
}
@@ -355,10 +388,8 @@ mpn_cmp (mp_srcptr ap, mp_srcptr bp, mp_size_t n)
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;
+ if (an != bn)
+ return an < bn ? -1 : 1;
else
return mpn_cmp (ap, bp, an);
}
@@ -366,12 +397,23 @@ mpn_cmp4 (mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn)
static mp_size_t
mpn_normalized_size (mp_srcptr xp, mp_size_t n)
{
- for (; n > 0 && xp[n-1] == 0; n--)
- ;
+ while (n > 0 && xp[n-1] == 0)
+ --n;
return n;
}
-#define mpn_zero_p(xp, n) (mpn_normalized_size ((xp), (n)) == 0)
+int
+mpn_zero_p(mp_srcptr rp, mp_size_t n)
+{
+ return mpn_normalized_size (rp, n) == 0;
+}
+
+void
+mpn_zero (mp_ptr rp, mp_size_t n)
+{
+ while (--n >= 0)
+ rp[n] = 0;
+}
mp_limb_t
mpn_add_1 (mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_limb_t b)
@@ -379,14 +421,16 @@ 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++)
+ i = 0;
+ do
{
mp_limb_t r = ap[i] + b;
/* Carry out */
b = (r < b);
rp[i] = r;
}
+ while (++i < n);
+
return b;
}
@@ -429,14 +473,17 @@ mpn_sub_1 (mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_limb_t b)
assert (n > 0);
- for (i = 0; i < n; i++)
+ i = 0;
+ do
{
mp_limb_t a = ap[i];
/* Carry out */
- mp_limb_t cy = a < b;;
+ mp_limb_t cy = a < b;
rp[i] = a - b;
b = cy;
}
+ while (++i < n);
+
return b;
}
@@ -551,23 +598,24 @@ mpn_mul (mp_ptr rp, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
{
assert (un >= vn);
assert (vn >= 1);
+ assert (!GMP_MPN_OVERLAP_P(rp, un + vn, up, un));
+ assert (!GMP_MPN_OVERLAP_P(rp, un + vn, vp, vn));
/* We first multiply by the low order limb. This result can be
stored, not added, to rp. We also avoid a loop for zeroing this
way. */
rp[un] = mpn_mul_1 (rp, up, un, vp[0]);
- rp += 1, vp += 1, vn -= 1;
/* Now accumulate the product of up[] and the next higher limb from
vp[]. */
- while (vn >= 1)
+ while (--vn >= 1)
{
+ rp += 1, vp += 1;
rp[un] = mpn_addmul_1 (rp, up, un, vp[0]);
- rp += 1, vp += 1, vn -= 1;
}
- return rp[un - 1];
+ return rp[un];
}
void
@@ -587,7 +635,6 @@ mpn_lshift (mp_ptr rp, mp_srcptr up, mp_size_t n, unsigned int cnt)
{
mp_limb_t high_limb, low_limb;
unsigned int tnc;
- mp_size_t i;
mp_limb_t retval;
assert (n >= 1);
@@ -602,7 +649,7 @@ mpn_lshift (mp_ptr rp, mp_srcptr up, mp_size_t n, unsigned int cnt)
retval = low_limb >> tnc;
high_limb = (low_limb << cnt);
- for (i = n - 1; i != 0; i--)
+ while (--n != 0)
{
low_limb = *--up;
*--rp = high_limb | (low_limb >> tnc);
@@ -618,7 +665,6 @@ mpn_rshift (mp_ptr rp, mp_srcptr up, mp_size_t n, unsigned int cnt)
{
mp_limb_t high_limb, low_limb;
unsigned int tnc;
- mp_size_t i;
mp_limb_t retval;
assert (n >= 1);
@@ -630,7 +676,7 @@ mpn_rshift (mp_ptr rp, mp_srcptr up, mp_size_t n, unsigned int cnt)
retval = (high_limb << tnc);
low_limb = high_limb >> cnt;
- for (i = n - 1; i != 0; i--)
+ while (--n != 0)
{
high_limb = *up++;
*rp++ = low_limb | (high_limb << tnc);
@@ -641,60 +687,156 @@ mpn_rshift (mp_ptr rp, mp_srcptr up, mp_size_t n, unsigned int cnt)
return retval;
}
+static mp_bitcnt_t
+mpn_common_scan (mp_limb_t limb, mp_size_t i, mp_srcptr up, mp_size_t un,
+ mp_limb_t ux)
+{
+ unsigned cnt;
+
+ assert (ux == 0 || ux == GMP_LIMB_MAX);
+ assert (0 <= i && i <= un );
+
+ while (limb == 0)
+ {
+ i++;
+ if (i == un)
+ return (ux == 0 ? ~(mp_bitcnt_t) 0 : un * GMP_LIMB_BITS);
+ limb = ux ^ up[i];
+ }
+ gmp_ctz (cnt, limb);
+ return (mp_bitcnt_t) i * GMP_LIMB_BITS + cnt;
+}
+
+mp_bitcnt_t
+mpn_scan1 (mp_srcptr ptr, mp_bitcnt_t bit)
+{
+ mp_size_t i;
+ i = bit / GMP_LIMB_BITS;
+
+ return mpn_common_scan ( ptr[i] & (GMP_LIMB_MAX << (bit % GMP_LIMB_BITS)),
+ i, ptr, i, 0);
+}
+
+mp_bitcnt_t
+mpn_scan0 (mp_srcptr ptr, mp_bitcnt_t bit)
+{
+ mp_size_t i;
+ i = bit / GMP_LIMB_BITS;
+
+ return mpn_common_scan (~ptr[i] & (GMP_LIMB_MAX << (bit % GMP_LIMB_BITS)),
+ i, ptr, i, GMP_LIMB_MAX);
+}
+
+void
+mpn_com (mp_ptr rp, mp_srcptr up, mp_size_t n)
+{
+ while (--n >= 0)
+ *rp++ = ~ *up++;
+}
+
+mp_limb_t
+mpn_neg (mp_ptr rp, mp_srcptr up, mp_size_t n)
+{
+ while (*up == 0)
+ {
+ *rp = 0;
+ if (!--n)
+ return 0;
+ ++up; ++rp;
+ }
+ *rp = - *up;
+ mpn_com (++rp, ++up, --n);
+ return 1;
+}
+
/* MPN division interface. */
+
+/* The 3/2 inverse is defined as
+
+ m = floor( (B^3-1) / (B u1 + u0)) - B
+*/
mp_limb_t
mpn_invert_3by2 (mp_limb_t u1, mp_limb_t u0)
{
- mp_limb_t r, p, m;
- unsigned ul, uh;
- unsigned ql, qh;
+ mp_limb_t r, m;
- /* First, do a 2/1 inverse. */
- /* The inverse m is defined as floor( (B^2 - 1 - u1)/u1 ), so that 0 <
- * B^2 - (B + m) u1 <= u1 */
- assert (u1 >= GMP_LIMB_HIGHBIT);
+ {
+ mp_limb_t p, ql;
+ unsigned ul, uh, qh;
- ul = u1 & GMP_LLIMB_MASK;
- uh = u1 >> (GMP_LIMB_BITS / 2);
+ /* For notation, let b denote the half-limb base, so that B = b^2.
+ Split u1 = b uh + ul. */
+ ul = u1 & GMP_LLIMB_MASK;
+ uh = u1 >> (GMP_LIMB_BITS / 2);
- qh = ~u1 / uh;
- r = ((~u1 - (mp_limb_t) qh * uh) << (GMP_LIMB_BITS / 2)) | GMP_LLIMB_MASK;
+ /* Approximation of the high half of quotient. Differs from the 2/1
+ inverse of the half limb uh, since we have already subtracted
+ u0. */
+ qh = (u1 ^ GMP_LIMB_MAX) / uh;
- p = (mp_limb_t) qh * ul;
- /* Adjustment steps taken from udiv_qrnnd_c */
- if (r < p)
- {
- qh--;
- r += u1;
- if (r >= u1) /* i.e. we didn't get carry when adding to r */
- if (r < p)
- {
- qh--;
- r += u1;
- }
- }
- r -= p;
+ /* Adjust to get a half-limb 3/2 inverse, i.e., we want
- /* Do a 3/2 division (with half limb size) */
- p = (r >> (GMP_LIMB_BITS / 2)) * qh + r;
- ql = (p >> (GMP_LIMB_BITS / 2)) + 1;
+ qh' = floor( (b^3 - 1) / u) - b = floor ((b^3 - b u - 1) / u
+ = floor( (b (~u) + b-1) / u),
- /* By the 3/2 method, we don't need the high half limb. */
- r = (r << (GMP_LIMB_BITS / 2)) + GMP_LLIMB_MASK - ql * u1;
+ and the remainder
- if (r >= (p << (GMP_LIMB_BITS / 2)))
- {
- ql--;
- r += u1;
- }
- m = ((mp_limb_t) qh << (GMP_LIMB_BITS / 2)) + ql;
- if (r >= u1)
- {
- m++;
- r -= u1;
- }
+ r = b (~u) + b-1 - qh (b uh + ul)
+ = b (~u - qh uh) + b-1 - qh ul
+
+ Subtraction of qh ul may underflow, which implies adjustments.
+ But by normalization, 2 u >= B > qh ul, so we need to adjust by
+ at most 2.
+ */
+
+ 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)
+ {
+ qh--;
+ r += u1;
+ if (r >= u1) /* i.e. we didn't get carry when adding to r */
+ if (r < p)
+ {