diff options
Diffstat (limited to 'gmp/mini-gmp')
36 files changed, 0 insertions, 9748 deletions
diff --git a/gmp/mini-gmp/README b/gmp/mini-gmp/README deleted file mode 100644 index f291489ea3..0000000000 --- a/gmp/mini-gmp/README +++ /dev/null @@ -1,77 +0,0 @@ -Copyright 2011-2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library. - -The GNU MP Library is free software; you can redistribute it and/or modify -it under the terms of either: - - * the GNU Lesser General Public License as published by the Free - Software Foundation; either version 3 of the License, or (at your - option) any later version. - -or - - * the GNU General Public License as published by the Free Software - Foundation; either version 2 of the License, or (at your option) any - later version. - -or both in parallel, as here. - -The GNU MP Library is distributed in the hope that it will be useful, but -WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -for more details. - -You should have received copies of the GNU General Public License and the -GNU Lesser General Public License along with the GNU MP Library. If not, -see https://www.gnu.org/licenses/. - - -This is "mini-gmp", a small implementation of a subset of GMP's mpn -and mpz interfaces. - -It is intended for applications which need arithmetic on numbers -larger than a machine word, but which don't need to handle very large -numbers very efficiently. Those applications can include a copy of -mini-gmp to get a GMP-compatible interface with small footprint. One -can also arrange for optional linking with the real GMP library, using -mini-gmp as a fallback when for some reason GMP is not available, or -not desired as a dependency. - -The supported GMP subset is declared in mini-gmp.h. The implemented -functions are fully compatible with the corresponding GMP functions, -as specified in the GMP manual, with a few exceptions: - - mpz_set_str, mpz_init_set_str, mpz_get_str, mpz_out_str and - mpz_sizeinbase support only |base| <= 36; - mpz_export and mpz_import support only NAILS = 0. - - The REALLOC_FUNC and FREE_FUNC registered with - mp_set_memory_functions does not get the correct size of the - allocated block in the corresponding argument. mini-gmp always - passes zero for these rarely used arguments. - -The implementation is a single file, mini-gmp.c. - -The performance target for mini-gmp is to be at most 10 times slower -than the real GMP library, for numbers of size up to a few hundred -bits. No asymptotically fast algorithms are included in mini-gmp, so -it will be many orders of magnitude slower than GMP for very large -numbers. - -You should never "install" mini-gmp. Applications can either just -#include mini-gmp.c (but then, beware that it defines several macros -and functions outside of the advertised interface). Or compile -mini-gmp.c as a separate compilation unit, and use the declarations in -mini-gmp.h. - -The tests subdirectory contains a testsuite. To use it, you need GMP -and GNU make. Just run make check in the tests directory. If the -hard-coded compiler settings are not right, you have to either edit the -Makefile or pass overriding values on the make command line (e.g., -make CC=cc check). Testing is not (yet) as thorough as for the real -GMP. - -The current version was put together by Niels Möller -<nisse@lysator.liu.se>, with a fair amount of copy-and-paste from the -GMP sources. diff --git a/gmp/mini-gmp/mini-gmp.c b/gmp/mini-gmp/mini-gmp.c deleted file mode 100644 index b9186951cb..0000000000 --- a/gmp/mini-gmp/mini-gmp.c +++ /dev/null @@ -1,4386 +0,0 @@ -/* mini-gmp, a minimalistic implementation of a GNU GMP subset. - - Contributed to the GNU project by Niels Möller - -Copyright 1991-1997, 1999-2014 Free Software Foundation, Inc. - -This file is part of the GNU MP Library. - -The GNU MP Library is free software; you can redistribute it and/or modify -it under the terms of either: - - * the GNU Lesser General Public License as published by the Free - Software Foundation; either version 3 of the License, or (at your - option) any later version. - -or - - * the GNU General Public License as published by the Free Software - Foundation; either version 2 of the License, or (at your option) any - later version. - -or both in parallel, as here. - -The GNU MP Library is distributed in the hope that it will be useful, but -WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -for more details. - -You should have received copies of the GNU General Public License and the -GNU Lesser General Public License along with the GNU MP Library. If not, -see https://www.gnu.org/licenses/. */ - -/* NOTE: All functions in this file which are not declared in - mini-gmp.h are internal, and are not intended to be compatible - neither with GMP nor with future versions of mini-gmp. */ - -/* Much of the material copied from GMP files, including: gmp-impl.h, - longlong.h, mpn/generic/add_n.c, mpn/generic/addmul_1.c, - mpn/generic/lshift.c, mpn/generic/mul_1.c, - mpn/generic/mul_basecase.c, mpn/generic/rshift.c, - mpn/generic/sbpi1_div_qr.c, mpn/generic/sub_n.c, - mpn/generic/submul_1.c. */ - -#include <assert.h> -#include <ctype.h> -#include <limits.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -#include "mini-gmp.h" - - -/* Macros */ -#define GMP_LIMB_BITS (sizeof(mp_limb_t) * CHAR_BIT) - -#define GMP_LIMB_MAX (~ (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)) -#define GMP_LLIMB_MASK (GMP_HLIMB_BIT - 1) - -#define GMP_ULONG_BITS (sizeof(unsigned long) * CHAR_BIT) -#define GMP_ULONG_HIGHBIT ((unsigned long) 1 << (GMP_ULONG_BITS - 1)) - -#define GMP_ABS(x) ((x) >= 0 ? (x) : -(x)) -#define GMP_NEG_CAST(T,x) (-((T)((x) + 1) - 1)) - -#define GMP_MIN(a, b) ((a) < (b) ? (a) : (b)) -#define GMP_MAX(a, b) ((a) > (b) ? (a) : (b)) - -#define gmp_assert_nocarry(x) do { \ - 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; \ - for (; (__clz_x & GMP_LIMB_HIGHBIT) == 0; __clz_c++) \ - __clz_x <<= 1; \ - (count) = __clz_c; \ - } while (0) - -#define gmp_ctz(count, x) do { \ - mp_limb_t __ctz_x = (x); \ - unsigned __ctz_c = 0; \ - gmp_clz (__ctz_c, __ctz_x & - __ctz_x); \ - (count) = GMP_LIMB_BITS - 1 - __ctz_c; \ - } while (0) - -#define gmp_add_ssaaaa(sh, sl, ah, al, bh, bl) \ - do { \ - mp_limb_t __x; \ - __x = (al) + (bl); \ - (sh) = (ah) + (bh) + (__x < (al)); \ - (sl) = __x; \ - } while (0) - -#define gmp_sub_ddmmss(sh, sl, ah, al, bh, bl) \ - do { \ - mp_limb_t __x; \ - __x = (al) - (bl); \ - (sh) = (ah) - (bh) - ((al) < (bl)); \ - (sl) = __x; \ - } while (0) - -#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); \ - \ - __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; \ - \ - __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); \ - } while (0) - -#define gmp_udiv_qrnnd_preinv(q, r, nh, nl, d, di) \ - do { \ - mp_limb_t _qh, _ql, _r, _mask; \ - gmp_umul_ppmm (_qh, _ql, (nh), (di)); \ - gmp_add_ssaaaa (_qh, _ql, _qh, _ql, (nh) + 1, (nl)); \ - _r = (nl) - _qh * (d); \ - _mask = -(mp_limb_t) (_r > _ql); /* both > and >= are OK */ \ - _qh += _mask; \ - _r += _mask & (d); \ - if (_r >= (d)) \ - { \ - _r -= (d); \ - _qh++; \ - } \ - \ - (r) = _r; \ - (q) = _qh; \ - } while (0) - -#define gmp_udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv) \ - do { \ - mp_limb_t _q0, _t1, _t0, _mask; \ - gmp_umul_ppmm ((q), _q0, (n2), (dinv)); \ - gmp_add_ssaaaa ((q), _q0, (q), _q0, (n2), (n1)); \ - \ - /* Compute the two most significant limbs of n - q'd */ \ - (r1) = (n1) - (d1) * (q); \ - gmp_sub_ddmmss ((r1), (r0), (r1), (n0), (d1), (d0)); \ - gmp_umul_ppmm (_t1, _t0, (d0), (q)); \ - gmp_sub_ddmmss ((r1), (r0), (r1), (r0), _t1, _t0); \ - (q)++; \ - \ - /* Conditionally adjust q and the remainders */ \ - _mask = - (mp_limb_t) ((r1) >= _q0); \ - (q) += _mask; \ - gmp_add_ssaaaa ((r1), (r0), (r1), (r0), _mask & (d1), _mask & (d0)); \ - if ((r1) >= (d1)) \ - { \ - if ((r1) > (d1) || (r0) >= (d0)) \ - { \ - (q)++; \ - gmp_sub_ddmmss ((r1), (r0), (r1), (r0), (d1), (d0)); \ - } \ - } \ - } while (0) - -/* Swap macros. */ -#define MP_LIMB_T_SWAP(x, y) \ - do { \ - mp_limb_t __mp_limb_t_swap__tmp = (x); \ - (x) = (y); \ - (y) = __mp_limb_t_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_BITCNT_T_SWAP(x,y) \ - do { \ - mp_bitcnt_t __mp_bitcnt_t_swap__tmp = (x); \ - (x) = (y); \ - (y) = __mp_bitcnt_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) - -const int mp_bits_per_limb = GMP_LIMB_BITS; - - -/* Memory allocation and other helper functions. */ -static void -gmp_die (const char *msg) -{ - fprintf (stderr, "%s\n", msg); - abort(); -} - -static void * -gmp_default_alloc (size_t size) -{ - void *p; - - assert (size > 0); - - p = malloc (size); - if (!p) - gmp_die("gmp_default_alloc: Virtual memory exhausted."); - - return p; -} - -static void * -gmp_default_realloc (void *old, size_t old_size, size_t new_size) -{ - mp_ptr p; - - p = realloc (old, new_size); - - if (!p) - gmp_die("gmp_default_realoc: Virtual memory exhausted."); - - return p; -} - -static void -gmp_default_free (void *p, size_t size) -{ - free (p); -} - -static void * (*gmp_allocate_func) (size_t) = gmp_default_alloc; -static void * (*gmp_reallocate_func) (void *, size_t, size_t) = gmp_default_realloc; -static void (*gmp_free_func) (void *, size_t) = gmp_default_free; - -void -mp_get_memory_functions (void *(**alloc_func) (size_t), - void *(**realloc_func) (void *, size_t, size_t), - void (**free_func) (void *, size_t)) -{ - if (alloc_func) - *alloc_func = gmp_allocate_func; - - if (realloc_func) - *realloc_func = gmp_reallocate_func; - - if (free_func) - *free_func = gmp_free_func; -} - -void -mp_set_memory_functions (void *(*alloc_func) (size_t), - void *(*realloc_func) (void *, size_t, size_t), - void (*free_func) (void *, size_t)) -{ - if (!alloc_func) - alloc_func = gmp_default_alloc; - if (!realloc_func) - realloc_func = gmp_default_realloc; - if (!free_func) - free_func = gmp_default_free; - - gmp_allocate_func = alloc_func; - gmp_reallocate_func = realloc_func; - gmp_free_func = free_func; -} - -#define gmp_xalloc(size) ((*gmp_allocate_func)((size))) -#define gmp_free(p) ((*gmp_free_func) ((p), 0)) - -static mp_ptr -gmp_xalloc_limbs (mp_size_t size) -{ - return 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)); -} - - -/* MPN interface */ - -void -mpn_copyi (mp_ptr d, mp_srcptr s, mp_size_t n) -{ - mp_size_t i; - for (i = 0; i < n; i++) - d[i] = s[i]; -} - -void -mpn_copyd (mp_ptr d, mp_srcptr s, mp_size_t n) -{ - while (n-- > 0) - d[n] = s[n]; -} - -int -mpn_cmp (mp_srcptr ap, mp_srcptr bp, mp_size_t n) -{ - while (--n >= 0) - { - if (ap[n] != bp[n]) - return ap[n] > bp[n] ? 1 : -1; - } - return 0; -} - -static int -mpn_cmp4 (mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn) -{ - if (an != bn) - return an < bn ? -1 : 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; -} - -#define mpn_zero_p(xp, n) (mpn_normalized_size ((xp), (n)) == 0) - -void -mpn_zero (mp_ptr rp, mp_size_t n) -{ - mp_size_t i; - - for (i = 0; i < n; i++) - rp[i] = 0; -} - -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); - i = 0; - do - { - mp_limb_t r = ap[i] + b; - /* Carry out */ - b = (r < b); - rp[i] = r; - } - while (++i < n); - - return b; -} - -mp_limb_t -mpn_add_n (mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n) -{ - mp_size_t i; - mp_limb_t cy; - - for (i = 0, cy = 0; i < n; i++) - { - mp_limb_t a, b, r; - a = ap[i]; b = bp[i]; - r = a + cy; - cy = (r < cy); - r += b; - cy += (r < b); - rp[i] = r; - } - return cy; -} - -mp_limb_t -mpn_add (mp_ptr rp, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn) -{ - mp_limb_t cy; - - assert (an >= bn); - - cy = mpn_add_n (rp, ap, bp, bn); - if (an > bn) - cy = mpn_add_1 (rp + bn, ap + bn, an - bn, cy); - return cy; -} - -mp_limb_t -mpn_sub_1 (mp_ptr rp, mp_srcptr ap, mp_size_t n, mp_limb_t b) -{ - mp_size_t i; - - assert (n > 0); - - i = 0; - do - { - mp_limb_t a = ap[i]; - /* Carry out */ - mp_limb_t cy = a < b;; - rp[i] = a - b; - b = cy; - } - while (++i < n); - - return b; -} - -mp_limb_t -mpn_sub_n (mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n) -{ - mp_size_t i; - mp_limb_t cy; - - for (i = 0, cy = 0; i < n; i++) - { - mp_limb_t a, b; - a = ap[i]; b = bp[i]; - b += cy; - cy = (b < cy); - cy += (a < b); - rp[i] = a - b; - } - return cy; -} - -mp_limb_t -mpn_sub (mp_ptr rp, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn) -{ - mp_limb_t cy; - - assert (an >= bn); - - cy = mpn_sub_n (rp, ap, bp, bn); - if (an > bn) - cy = mpn_sub_1 (rp + bn, ap + bn, an - bn, cy); - return cy; -} - -mp_limb_t -mpn_mul_1 (mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t vl) -{ - mp_limb_t ul, cl, hpl, lpl; - - assert (n >= 1); - - cl = 0; - do - { - ul = *up++; - gmp_umul_ppmm (hpl, lpl, ul, vl); - - lpl += cl; - cl = (lpl < cl) + hpl; - - *rp++ = lpl; - } - while (--n != 0); - - return cl; -} - -mp_limb_t -mpn_addmul_1 (mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t vl) -{ - mp_limb_t ul, cl, hpl, lpl, rl; - - assert (n >= 1); - - cl = 0; - do - { - ul = *up++; - gmp_umul_ppmm (hpl, lpl, ul, vl); - - lpl += cl; - cl = (lpl < cl) + hpl; - - rl = *rp; - lpl = rl + lpl; - cl += lpl < rl; - *rp++ = lpl; - } - while (--n != 0); - - return cl; -} - -mp_limb_t -mpn_submul_1 (mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t vl) -{ - mp_limb_t ul, cl, hpl, lpl, rl; - - assert (n >= 1); - - cl = 0; - do - { - ul = *up++; - gmp_umul_ppmm (hpl, lpl, ul, vl); - - lpl += cl; - cl = (lpl < cl) + hpl; - - rl = *rp; - lpl = rl - lpl; - cl += lpl > rl; - *rp++ = lpl; - } - while (--n != 0); - - return cl; -} - -mp_limb_t -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); - - /* 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) - { - rp[un] = mpn_addmul_1 (rp, up, un, vp[0]); - 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) -{ - mpn_mul (rp, ap, n, bp, n); -} - -void -mpn_sqr (mp_ptr rp, mp_srcptr ap, mp_size_t n) -{ - mpn_mul (rp, ap, n, ap, n); -} - -mp_limb_t -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); - assert (cnt >= 1); - assert (cnt < GMP_LIMB_BITS); - - up += n; - rp += n; - - tnc = GMP_LIMB_BITS - cnt; - low_limb = *--up; - retval = low_limb >> tnc; - high_limb = (low_limb << cnt); - - for (i = n; --i != 0;) - { - low_limb = *--up; - *--rp = high_limb | (low_limb >> tnc); - high_limb = (low_limb << cnt); - } - *--rp = high_limb; - - return retval; -} - -mp_limb_t -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); - assert (cnt >= 1); - assert (cnt < GMP_LIMB_BITS); - - tnc = GMP_LIMB_BITS - cnt; - high_limb = *up++; - retval = (high_limb << tnc); - low_limb = high_limb >> cnt; - - for (i = n; --i != 0;) - { - high_limb = *up++; - *rp++ = low_limb | (high_limb << tnc); - low_limb = high_limb >> cnt; - } - *rp = low_limb; - - 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); -} - - -/* MPN division interface. */ -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; - - /* 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); - - 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; - - 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; - - /* Do a 3/2 division (with half limb size) */ - p = (r >> (GMP_LIMB_BITS / 2)) * qh + r; - ql = (p >> (GMP_LIMB_BITS / 2)) + 1; - - /* By the 3/2 method, we don't need the high half limb. */ - r = (r << (GMP_LIMB_BITS / 2)) + GMP_LLIMB_MASK - ql * u1; - - 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; - } - - if (u0 > 0) - { - mp_limb_t th, tl; - r = ~r; - r += u0; - if (r < u0) - { - m--; - if (r >= u1) - { - m--; - r -= u1; - } - r -= u1; - } - gmp_umul_ppmm (th, tl, u0, m); - r += th; - if (r < th) - { - m--; - m -= ((r > u1) | ((r == u1) & (tl > u0))); - } - } - - return m; -} - -struct gmp_div_inverse -{ - /* Normalization shift count. */ - unsigned shift; - /* Normalized divisor (d0 unused for mpn_div_qr_1) */ - mp_limb_t d1, d0; - /* Inverse, for 2/1 or 3/2. */ - mp_limb_t di; -}; - -static void -mpn_div_qr_1_invert (struct gmp_div_inverse *inv, mp_limb_t d) -{ - unsigned shift; - - assert (d > 0); - gmp_clz (shift, d); - inv->shift = shift; - inv->d1 = d << shift; - inv->di = mpn_invert_limb (inv->d1); -} - -static void -mpn_div_qr_2_invert (struct gmp_div_inverse *inv, - mp_limb_t d1, mp_limb_t d0) -{ - unsigned shift; - - assert (d1 > 0); - gmp_clz (shift, d1); - inv->shift = shift; - if (shift > 0) - { - d1 = (d1 << shift) | (d0 >> (GMP_LIMB_BITS - shift)); - d0 <<= shift; - } - inv->d1 = d1; - inv->d0 = d0; - inv->di = mpn_invert_3by2 (d1, d0); -} - -static void -mpn_div_qr_invert (struct gmp_div_inverse *inv, - mp_srcptr dp, mp_size_t dn) -{ - assert (dn > 0); - - if (dn == 1) - mpn_div_qr_1_invert (inv, dp[0]); - else if (dn == 2) - mpn_div_qr_2_invert (inv, dp[1], dp[0]); - else - { - unsigned shift; - mp_limb_t d1, d0; - - d1 = dp[dn-1]; - d0 = dp[dn-2]; - assert (d1 > 0); - gmp_clz (shift, d1); - inv->shift = shift; - if (shift > 0) - { - d1 = (d1 << shift) | (d0 >> (GMP_LIMB_BITS - shift)); - d0 = (d0 << shift) | (dp[dn-3] >> (GMP_LIMB_BITS - shift)); - } - inv->d1 = d1; - inv->d0 = d0; - inv->di = mpn_invert_3by2 (d1, d0); - } -} - -/* Not matching current public gmp interface, rather corresponding to - the sbpi1_div_* functions. */ -static mp_limb_t -mpn_div_qr_1_preinv (mp_ptr qp, mp_srcptr np, mp_size_t nn, - const struct gmp_div_inverse *inv) -{ - mp_limb_t d, di; - mp_limb_t r; - mp_ptr tp = NULL; - - if (inv->shift > 0) - { - tp = gmp_xalloc_limbs (nn); - r = mpn_lshift (tp, np, nn, inv->shift); - np = tp; - } - else - r = 0; - - d = inv->d1; - di = inv->di; - while (nn-- > 0) - { - mp_limb_t q; - - gmp_udiv_qrnnd_preinv (q, r, r, np[nn], d, di); - if (qp) - qp[nn] = q; - } - if (inv->shift > 0) - gmp_free (tp); - - return r >> inv->shift; -} - -static mp_limb_t -mpn_div_qr_1 (mp_ptr qp, mp_srcptr np, mp_size_t nn, mp_limb_t d) -{ - assert (d > 0); - - /* Special case for powers of two. */ - if ((d & (d-1)) == 0) - { - mp_limb_t r = np[0] & (d-1); - if (qp) - { - if (d <= 1) - mpn_copyi (qp, np, nn); - else - { - unsigned shift; - gmp_ctz (shift, d); - mpn_rshift (qp, np, nn, shift); - } - } - return r; - } - else - { - struct gmp_div_inverse inv; - mpn_div_qr_1_invert (&inv, d); - return mpn_div_qr_1_preinv (qp, np, nn, &inv); - } -} - -static void -mpn_div_qr_2_preinv (mp_ptr qp, mp_ptr rp, mp_srcptr np, mp_size_t nn, - const struct gmp_div_inverse *inv) -{ - unsigned shift; - mp_size_t i; - mp_limb_t d1, d0, di, r1, r0; - mp_ptr tp; - - assert (nn >= 2); - shift = inv->shift; - d1 = inv->d1; - d0 = inv->d0; - di = inv->di; - - if (shift > 0) - { - tp = gmp_xalloc_limbs (nn); - r1 = mpn_lshift (tp, np, nn, shift); - np = tp; - } - else - r1 = 0; - - r0 = np[nn - 1]; - - i = nn - 2; - do - { - mp_limb_t n0, q; - n0 = np[i]; - gmp_udiv_qr_3by2 (q, r1, r0, r1, r0, n0, d1, d0, di); - - if (qp) - qp[i] = q; - } - while (--i >= 0); - - if (shift > 0) - { - assert ((r0 << (GMP_LIMB_BITS - shift)) == 0); - r0 = (r0 >> shift) | (r1 << (GMP_LIMB_BITS - shift)); - r1 >>= shift; - - gmp_free (tp); - } - - rp[1] = r1; - rp[0] = r0; -} - -#if 0 -static void -mpn_div_qr_2 (mp_ptr qp, mp_ptr rp, mp_srcptr np, mp_size_t nn, - mp_limb_t d1, mp_limb_t d0) -{ - struct gmp_div_inverse inv; - assert (nn >= 2); - - mpn_div_qr_2_invert (&inv, d1, d0); - mpn_div_qr_2_preinv (qp, rp, np, nn, &inv); -} -#endif - -static void -mpn_div_qr_pi1 (mp_ptr qp, - mp_ptr np, mp_size_t nn, mp_limb_t n1, - mp_srcptr dp, mp_size_t dn, - mp_limb_t dinv) -{ - mp_size_t i; - - mp_limb_t d1, d0; - mp_limb_t cy, cy1; - mp_limb_t q; - - assert (dn > 2); - assert (nn >= dn); - - d1 = dp[dn - 1]; - d0 = dp[dn - 2]; - - assert ((d1 & GMP_LIMB_HIGHBIT) != 0); - /* Iteration variable is the index of the q limb. - * - * We divide <n1, np[dn-1+i], np[dn-2+i], np[dn-3+i],..., np[i]> - * by <d1, d0, dp[dn-3], ..., dp[0] > - */ - - i = nn - dn; - do - { - mp_limb_t n0 = np[dn-1+i]; - - if (n1 == d1 && n0 == d0) - { - q = GMP_LIMB_MAX; - mpn_submul_1 (np+i, dp, dn, q); - n1 = np[dn-1+i]; /* update n1, last loop's value will now be invalid */ - } - else - { - gmp_udiv_qr_3by2 (q, n1, n0, n1, n0, np[dn-2+i], d1, d0, dinv); - - cy = mpn_submul_1 (np + i, dp, dn-2, q); - - cy1 = n0 < cy; - n0 = n0 - cy; - cy = n1 < cy1; - n1 = n1 - cy1; - np[dn-2+i] = n0; - - if (cy != 0) - { - n1 += d1 + mpn_add_n (np + i, np + i, dp, dn - 1); - q--; - } - } - - if (qp) - qp[i] = q; - } - while (--i >= 0); - - np[dn - 1] = n1; -} - -static void -mpn_div_qr_preinv (mp_ptr qp, mp_ptr np, mp_size_t nn, - mp_srcptr dp, mp_size_t dn, - const struct gmp_div_inverse *inv) -{ - assert (dn > 0); - assert (nn >= dn); - - if (dn == 1) - np[0] = mpn_div_qr_1_preinv (qp, np, nn, inv); - else if (dn == 2) - mpn_div_qr_2_preinv (qp, np, np, nn, inv); - else - { - mp_limb_t nh; - unsigned shift; - - assert (inv->d1 == dp[dn-1]); - assert (inv->d0 == dp[dn-2]); - assert ((inv->d1 & GMP_LIMB_HIGHBIT) != 0); - - shift = inv->shift; - if (shift > 0) - nh = mpn_lshift (np, np, nn, shift); - else - nh = 0; - - mpn_div_qr_pi1 (qp, np, nn, nh, dp, dn, inv->di); - - if (shift > 0) - gmp_assert_nocarry (mpn_rshift (np, np, dn, shift)); - } -} - -static void -mpn_div_qr (mp_ptr qp, mp_ptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn) -{ - struct gmp_div_inverse inv; - mp_ptr tp = NULL; - - assert (dn > 0); - assert (nn >= dn); - - mpn_div_qr_invert (&inv, dp, dn); - if (dn > 2 && inv.shift > 0) - { - tp = gmp_xalloc_limbs (dn); - gmp_assert_nocarry (mpn_lshift (tp, dp, dn, inv.shift)); - dp = tp; - } - mpn_div_qr_preinv (qp, np, nn, dp, dn, &inv); - if (tp) - gmp_free (tp); -} - - -/* MPN base conversion. */ -static unsigned -mpn_base_power_of_two_p (unsigned b) -{ - switch (b) - { - case 2: return 1; - case 4: return 2; - case 8: return 3; - case 16: return 4; - case 32: return 5; - case 64: return 6; - case 128: return 7; - case 256: return 8; - default: return 0; - } -} - -struct mpn_base_info -{ - /* bb is the largest power of the base which fits in one limb, and - exp is the corresponding exponent. */ - unsigned exp; - mp_limb_t bb; -}; - -static void -mpn_get_base_info (struct mpn_base_info *info, mp_limb_t b) -{ - mp_limb_t m; - mp_limb_t p; - unsigned exp; - - m = GMP_LIMB_MAX / b; - for (exp = 1, p = b; p <= m; exp++) - p *= b; - - info->exp = exp; - info->bb = p; -} - -static mp_bitcnt_t -mpn_limb_size_in_base_2 (mp_limb_t u) -{ - unsigned shift; - - assert (u > 0); - gmp_clz (shift, u); - return GMP_LIMB_BITS - shift; -} - -static size_t -mpn_get_str_bits (unsigned char *sp, unsigned bits, mp_srcptr up, mp_size_t un) -{ - unsigned char mask; - size_t sn, j; - mp_size_t i; - int shift; - - sn = ((un - 1) * GMP_LIMB_BITS + mpn_limb_size_in_base_2 (up[un-1]) - + bits - 1) / bits; - - mask = (1U << bits) - 1; - - for (i = 0, j = sn, shift = 0; j-- > 0;) - { - unsigned char digit = up[i] >> shift; - - shift += bits; - - if (shift >= GMP_LIMB_BITS && ++i < un) - { - shift -= GMP_LIMB_BITS; - digit |= up[i] << (bits - shift); - } - sp[j] = digit & mask; - } - return sn; -} - -/* We generate digits from the least significant end, and reverse at - the end. */ -static size_t -mpn_limb_get_str (unsigned char *sp, mp_limb_t w, - const struct gmp_div_inverse *binv) -{ - mp_size_t i; - for (i = 0; w > 0; i++) - { - mp_limb_t h, l, r; - - h = w >> (GMP_LIMB_BITS - binv->shift); - l = w << binv->shift; - - gmp_udiv_qrnnd_preinv (w, r, h, l, binv->d1, binv->di); - assert ( (r << (GMP_LIMB_BITS - binv->shift)) == 0); - r >>= binv->shift; - - sp[i] = r; - } - return i; -} - -static size_t -mpn_get_str_other (unsigned char *sp, - int base, const struct mpn_base_info *info, - mp_ptr up, mp_size_t un) -{ - struct gmp_div_inverse binv; - size_t sn; - size_t i; - - mpn_div_qr_1_invert (&binv, base); - - sn = 0; - - if (un > 1) - { - struct gmp_div_inverse bbinv; - mpn_div_qr_1_invert (&bbinv, info->bb); - - do - { - mp_limb_t w; - size_t done; - w = mpn_div_qr_1_preinv (up, up, un, &bbinv); - un -= (up[un-1] == 0); - done = mpn_limb_get_str (sp + sn, w, &binv); - - for (sn += done; done < info->exp; done++) - sp[sn++] = 0; - } - while (un > 1); - } - sn += mpn_limb_get_str (sp + sn, up[0], &binv); - - /* Reverse order */ - for (i = 0; 2*i + 1 < sn; i++) - { - unsigned char t = sp[i]; - sp[i] = sp[sn - i - 1]; - sp[sn - i - 1] = t; - } - - return sn; -} - -size_t -mpn_get_str (unsigned char *sp, int base, mp_ptr up, mp_size_t un) -{ - unsigned bits; - - assert (un > 0); - assert (up[un-1] > 0); - - bits = mpn_base_power_of_two_p (base); - if (bits) - return mpn_get_str_bits (sp, bits, up, un); - else - { - struct mpn_base_info info; - - mpn_get_base_info (&info, base); - return mpn_get_str_other (sp, base, &info, up, un); - } -} - -static mp_size_t -mpn_set_str_bits (mp_ptr rp, const unsigned char *sp, size_t sn, - unsigned bits) -{ - mp_size_t rn; - size_t j; - unsigned shift; - - for (j = sn, rn = 0, shift = 0; j-- > 0; ) - { - if (shift == 0) - { - rp[rn++] = sp[j]; - shift += bits; - } - else - { - rp[rn-1] |= (mp_limb_t) sp[j] << shift; - shift += bits; - if (shift >= GMP_LIMB_BITS) - { - shift -= GMP_LIMB_BITS; - if (shift > 0) - rp[rn++] = (mp_limb_t) sp[j] >> (bits - shift); - } - } - } - rn = mpn_normalized_size (rp, rn); - return rn; -} - -static mp_size_t -mpn_set_str_other (mp_ptr rp, const unsigned char *sp, size_t sn, - mp_limb_t b, const struct mpn_base_info *info) -{ - mp_size_t rn; - mp_limb_t w; - unsigned k; - size_t j; - - k = 1 + (sn - 1) % info->exp; - - j = 0; - w = sp[j++]; - for (; --k > 0; ) - w = w * b + sp[j++]; - - rp[0] = w; - - for (rn = (w > 0); j < sn;) - { - mp_limb_t cy; - - w = sp[j++]; - for (k = 1; k < info->exp; k++) - w = w * b + sp[j++]; - - cy = mpn_mul_1 (rp, rp, rn, info->bb); - cy += mpn_add_1 (rp, rp, rn, w); - if (cy > 0) - rp[rn++] = cy; - } - assert (j == sn); - - return rn; -} - -mp_size_t -mpn_set_str (mp_ptr rp, const unsigned char *sp, size_t sn, int base) -{ - unsigned bits; - - if (sn == 0) - return 0; - - bits = mpn_base_power_of_two_p (base); - if (bits) - return mpn_set_str_bits (rp, sp, sn, bits); - else - { - struct mpn_base_info info; - - mpn_get_base_info (&info, base); - return mpn_set_str_other (rp, sp, sn, base, &info); - } -} - - -/* MPZ interface */ -void -mpz_init (mpz_t r) -{ - r->_mp_alloc = 1; - r->_mp_size = 0; - r->_mp_d = gmp_xalloc_limbs (1); -} - -/* The utility of this function is a bit limited, since many functions - assigns the result variable using mpz_swap. */ -void -mpz_init2 (mpz_t r, mp_bitcnt_t bits) -{ - mp_size_t rn; - - bits -= (bits != 0); /* Round down, except if 0 */ - rn = 1 + bits / GMP_LIMB_BITS; - - r->_mp_alloc = rn; - r->_mp_size = 0; - r->_mp_d = gmp_xalloc_limbs (rn); -} - -void -mpz_clear (mpz_t r) -{ - gmp_free (r->_mp_d); -} - -static void * -mpz_realloc (mpz_t r, mp_size_t size) -{ - size = GMP_MAX (size, 1); - - r->_mp_d = gmp_xrealloc_limbs (r->_mp_d, size); - r->_mp_alloc = size; - - if (GMP_ABS (r->_mp_size) > size) - r->_mp_size = 0; - - return r->_mp_d; -} - -/* Realloc for an mpz_t WHAT if it has less than NEEDED limbs. */ -#define MPZ_REALLOC(z,n) ((n) > (z)->_mp_alloc \ - ? mpz_realloc(z,n) \ - : (z)->_mp_d) - -/* MPZ assignment and basic conversions. */ -void -mpz_set_si (mpz_t r, signed long int x) -{ - if (x >= 0) - mpz_set_ui (r, x); - else /* (x < 0) */ - { - r->_mp_size = -1; - r->_mp_d[0] = GMP_NEG_CAST (unsigned long int, x); - } -} - -void -mpz_set_ui (mpz_t r, unsigned long int x) -{ - if (x > 0) - { - r->_mp_size = 1; - r->_mp_d[0] = x; - } - else - r->_mp_size = 0; -} - -void -mpz_set (mpz_t r, const mpz_t x) -{ - /* Allow the NOP r == x */ - if (r != x) - { - mp_size_t n; - mp_ptr rp; - - n = GMP_ABS (x->_mp_size); - rp = MPZ_REALLOC (r, n); - - mpn_copyi (rp, x->_mp_d, n); - r->_mp_size = x->_mp_size; - } -} - -void -mpz_init_set_si (mpz_t r, signed long int x) -{ - mpz_init (r); - mpz_set_si (r, x); -} - -void -mpz_init_set_ui (mpz_t r, unsigned long int x) -{ - mpz_init (r); - mpz_set_ui (r, x); -} - -void -mpz_init_set (mpz_t r, const mpz_t x) -{ - mpz_init (r); - mpz_set (r, x); -} - -int -mpz_fits_slong_p (const mpz_t u) -{ - mp_size_t us = u->_mp_size; - - if (us == 0) - return 1; - else if (us == 1) - return u->_mp_d[0] < GMP_LIMB_HIGHBIT; - else if (us == -1) - return u->_mp_d[0] <= GMP_LIMB_HIGHBIT; - else - return 0; -} - -int -mpz_fits_ulong_p (const mpz_t u) -{ - mp_size_t us = u->_mp_size; - - return (us == (us > 0)); -} - -long int -mpz_get_si (const mpz_t u) -{ - mp_size_t us = u->_mp_size; - - if (us > 0) - return (long) (u->_mp_d[0] & ~GMP_LIMB_HIGHBIT); - else if (us < 0) - return (long) (- u->_mp_d[0] | GMP_LIMB_HIGHBIT); - else - return 0; -} - -unsigned long int -mpz_get_ui (const mpz_t u) -{ - return u->_mp_size == 0 ? 0 : u->_mp_d[0]; -} - -size_t -mpz_size (const mpz_t u) -{ - return GMP_ABS (u->_mp_size); -} - -mp_limb_t -mpz_getlimbn (const mpz_t u, mp_size_t n) -{ - if (n >= 0 && n < GMP_ABS (u->_mp_size)) - return u->_mp_d[n]; - else - return 0; -} - -void -mpz_realloc2 (mpz_t x, mp_bitcnt_t n) -{ - mpz_realloc (x, 1 + (n - (n != 0)) / GMP_LIMB_BITS); -} - -mp_srcptr -mpz_limbs_read (mpz_srcptr x) -{ - return x->_mp_d;; -} - -mp_ptr -mpz_limbs_modify (mpz_t x, mp_size_t n) -{ - assert (n > 0); - return MPZ_REALLOC (x, n); -} - -mp_ptr -mpz_limbs_write (mpz_t x, mp_size_t n) -{ - return mpz_limbs_modify (x, n); -} - -void -mpz_limbs_finish (mpz_t x, mp_size_t xs) -{ - mp_size_t xn; - xn = mpn_normalized_size (x->_mp_d, GMP_ABS (xs)); - x->_mp_size = xs < 0 ? -xn : xn; -} - -mpz_srcptr -mpz_roinit_n (mpz_t x, mp_srcptr xp, mp_size_t xs) -{ - x->_mp_alloc = 0; - x->_mp_d = (mp_ptr) xp; - mpz_limbs_finish (x, xs); - return x; -} - - -/* Conversions and comparison to double. */ -void -mpz_set_d (mpz_t r, double x) -{ - int sign; - mp_ptr rp; - mp_size_t rn, i; - double B; - double Bi; - mp_limb_t f; - - /* x != x is true when x is a NaN, and x == x * 0.5 is true when x is - zero or infinity. */ - if (x != x || x == x * 0.5) - { - r->_mp_size = 0; - return; - } - - sign = x < 0.0 ; - if (sign) - x = - x; - - if (x < 1.0) - { - r->_mp_size = 0; - return; - } - B = 2.0 * (double) GMP_LIMB_HIGHBIT; - Bi = 1.0 / B; - for (rn = 1; x >= B; rn++) - x *= Bi; - - rp = MPZ_REALLOC (r, rn); - - f = (mp_limb_t) x; - x -= f; - assert (x < 1.0); - i = rn-1; - rp[i] = f; - while (--i >= 0) - { - x = B * x; - f = (mp_limb_t) x; - x -= f; - assert (x < 1.0); - rp[i] = f; - } - - r->_mp_size = sign ? - rn : rn; -} - -void -mpz_init_set_d (mpz_t r, double x) -{ - mpz_init (r); - mpz_set_d (r, x); -} - -double -mpz_get_d (const mpz_t u) -{ - mp_size_t un; - double x; - double B = 2.0 * (double) GMP_LIMB_HIGHBIT; - - un = GMP_ABS (u->_mp_size); - - if (un == 0) - return 0.0; - - x = u->_mp_d[--un]; - while (un > 0) - x = B*x + u->_mp_d[--un]; - - if (u->_mp_size < 0) - x = -x; - - return x; -} - -int -mpz_cmpabs_d (const mpz_t x, double d) -{ - mp_size_t xn; - double B, Bi; - mp_size_t i; - - xn = x->_mp_size; - d = GMP_ABS (d); - - if (xn != 0) - { - xn = GMP_ABS (xn); - - B = 2.0 * (double) GMP_LIMB_HIGHBIT; - Bi = 1.0 / B; - - /* Scale d so it can be compared with the top limb. */ - for (i = 1; i < xn; i++) - d *= Bi; - - if (d >= B) - return -1; - - /* Compare floor(d) to top limb, subtract and cancel when equal. */ - for (i = xn; i-- > 0;) - { - mp_limb_t f, xl; - - f = (mp_limb_t) d; - xl = x->_mp_d[i]; - if (xl > f) - return 1; - else if (xl < f) - return -1; - d = B * (d - f); - } - } - return - (d > 0.0); -} - -int -mpz_cmp_d (const mpz_t x, double d) -{ - if (x->_mp_size < 0) - { - if (d >= 0.0) - return -1; - else - return -mpz_cmpabs_d (x, d); - } - else - { - if (d < 0.0) - return 1; - else - return mpz_cmpabs_d (x, d); - } -} - - -/* MPZ comparisons and the like. */ -int -mpz_sgn (const mpz_t u) -{ - mp_size_t usize = u->_mp_size; - - return (usize > 0) - (usize < 0); -} - -int -mpz_cmp_si (const mpz_t u, long v) -{ - mp_size_t usize = u->_mp_size; - - if (usize < -1) - return -1; - else if (v >= 0) - return mpz_cmp_ui (u, v); - else if (usize >= 0) - return 1; - else /* usize == -1 */ - { - mp_limb_t ul = u->_mp_d[0]; - if ((mp_limb_t)GMP_NEG_CAST (unsigned long int, v) < ul) - return -1; - else - return (mp_limb_t)GMP_NEG_CAST (unsigned long int, v) > ul; - } -} - -int -mpz_cmp_ui (const mpz_t u, unsigned long v) -{ - mp_size_t usize = u->_mp_size; - - if (usize > 1) - return 1; - else if (usize < 0) - return -1; - else - { - mp_limb_t ul = (usize > 0) ? u->_mp_d[0] : 0; - return (ul > v) - (ul < v); - } -} - -int -mpz_cmp (const mpz_t a, const mpz_t b) -{ - mp_size_t asize = a->_mp_size; - mp_size_t bsize = b->_mp_size; - - if (asize != bsize) - return (asize < bsize) ? -1 : 1; - else if (asize >= 0) - return mpn_cmp (a->_mp_d, b->_mp_d, asize); - else - return mpn_cmp (b->_mp_d, a->_mp_d, -asize); -} - -int -mpz_cmpabs_ui (const mpz_t u, unsigned long v) -{ - mp_size_t un = GMP_ABS (u->_mp_size); - mp_limb_t ul; - - if (un > 1) - return 1; - - ul = (un == 1) ? u->_mp_d[0] : 0; - - return (ul > v) - (ul < v); -} - -int -mpz_cmpabs (const mpz_t u, const mpz_t v) -{ - return mpn_cmp4 (u->_mp_d, GMP_ABS (u->_mp_size), - v->_mp_d, GMP_ABS (v->_mp_size)); -} - -void -mpz_abs (mpz_t r, const mpz_t u) -{ - if (r != u) - mpz_set (r, u); - - r->_mp_size = GMP_ABS (r->_mp_size); -} - -void -mpz_neg (mpz_t r, const mpz_t u) -{ - if (r != u) - mpz_set (r, u); - - r->_mp_size = -r->_mp_size; -} - -void -mpz_swap (mpz_t u, mpz_t v) -{ - MP_SIZE_T_SWAP (u->_mp_size, v->_mp_size); - MP_SIZE_T_SWAP (u->_mp_alloc, v->_mp_alloc); - MP_PTR_SWAP (u->_mp_d, v->_mp_d); -} - - -/* 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) - { - r->_mp_d[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 = MPZ_REALLOC (r, an); - - if (an == 0) - { - rp[0] = b; - return -(b > 0); - } - else 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); - else - r->_mp_size = -mpz_abs_sub_ui (r, a, b); -} - -void -mpz_sub_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); - else - r->_mp_size = mpz_abs_sub_ui (r, a, b); -} - -void -mpz_ui_sub (mpz_t r, unsigned long a, const mpz_t b) -{ - if (b->_mp_size < 0) - r->_mp_size = mpz_abs_add_ui (r, b, a); - else - r->_mp_size = -mpz_abs_sub_ui (r, b, a); -} - -static mp_size_t -mpz_abs_add (mpz_t r, const mpz_t a, const mpz_t b) -{ - mp_size_t an = GMP_ABS (a->_mp_size); - mp_size_t bn = GMP_ABS (b->_mp_size); - mp_ptr rp; - mp_limb_t cy; - - if (an < bn) - { - MPZ_SRCPTR_SWAP (a, b); - MP_SIZE_T_SWAP (an, bn); - } - - rp = MPZ_REALLOC (r, an + 1); - cy = mpn_add (rp, a->_mp_d, an, b->_mp_d, bn); - - rp[an] = cy; - - return an + cy; -} - -static mp_size_t -mpz_abs_sub (mpz_t r, const mpz_t a, const mpz_t b) -{ - mp_size_t an = GMP_ABS (a->_mp_size); - mp_size_t bn = GMP_ABS (b->_mp_size); - int cmp; - mp_ptr rp; - - cmp = mpn_cmp4 (a->_mp_d, an, b->_mp_d, bn); - if (cmp > 0) - { - rp = MPZ_REALLOC (r, an); - gmp_assert_nocarry (mpn_sub (rp, a->_mp_d, an, b->_mp_d, bn)); - return mpn_normalized_size (rp, an); - } - else if (cmp < 0) - { - rp = MPZ_REALLOC (r, bn); - gmp_assert_nocarry (mpn_sub (rp, b->_mp_d, bn, a->_mp_d, an)); - return -mpn_normalized_size (rp, bn); - } - else - return 0; -} - -void -mpz_add (mpz_t r, const mpz_t a, const mpz_t b) -{ - mp_size_t rn; - - if ( (a->_mp_size ^ b->_mp_size) >= 0) - rn = mpz_abs_add (r, a, b); - else - rn = mpz_abs_sub (r, a, b); - - r->_mp_size = a->_mp_size >= 0 ? rn : - rn; -} - -void -mpz_sub (mpz_t r, const mpz_t a, const mpz_t b) -{ - mp_size_t rn; - - if ( (a->_mp_size ^ b->_mp_size) >= 0) - rn = mpz_abs_sub (r, a, b); - else - rn = mpz_abs_add (r, a, b); - - r->_mp_size = a->_mp_size >= 0 ? rn : - rn; -} - - -/* MPZ multiplication */ -void -mpz_mul_si (mpz_t r, const mpz_t u, long int v) -{ - if (v < 0) - { - mpz_mul_ui (r, u, GMP_NEG_CAST (unsigned long int, v)); - mpz_neg (r, r); - } - else - mpz_mul_ui (r, u, (unsigned long int) v); -} - -void -mpz_mul_ui (mpz_t r, const mpz_t u, unsigned long int v) -{ - mp_size_t un, us; - mp_ptr tp; - mp_limb_t cy; - - us = u->_mp_size; - - if (us == 0 || v == 0) - { - r->_mp_size = 0; - return; - } - - un = GMP_ABS (us); - - tp = MPZ_REALLOC (r, un + 1); - cy = mpn_mul_1 (tp, u->_mp_d, un, v); - tp[un] = cy; - - un += (cy > 0); - r->_mp_size = (us < 0) ? - un : un; -} - -void -mpz_mul (mpz_t r, const mpz_t u, const mpz_t v) -{ - int sign; - mp_size_t un, vn, rn; - mpz_t t; - mp_ptr tp; - - un = u->_mp_size; - vn = v->_mp_size; - - if (un == 0 || vn == 0) - { - r->_mp_size = 0; - return; - } - - sign = (un ^ vn) < 0; - - un = GMP_ABS (un); - vn = GMP_ABS (vn); - - mpz_init2 (t, (un + vn) * GMP_LIMB_BITS); - - tp = t->_mp_d; - if (un >= vn) - mpn_mul (tp, u->_mp_d, un, v->_mp_d, vn); - else - mpn_mul (tp, v->_mp_d, vn, u->_mp_d, un); - - rn = un + vn; - rn -= tp[rn-1] == 0; - - t->_mp_size = sign ? - rn : rn; - mpz_swap (r, t); - mpz_clear (t); -} - -void -mpz_mul_2exp (mpz_t r, const mpz_t u, mp_bitcnt_t bits) -{ - mp_size_t un, rn; - mp_size_t limbs; - unsigned shift; - mp_ptr rp; - - un = GMP_ABS (u->_mp_size); - if (un == 0) - { - r->_mp_size = 0; - return; - } - - limbs = bits / GMP_LIMB_BITS; - shift = bits % GMP_LIMB_BITS; - - rn = un + limbs + (shift > 0); - rp = MPZ_REALLOC (r, rn); - if (shift > 0) - { - mp_limb_t cy = mpn_lshift (rp + limbs, u->_mp_d, un, shift); - rp[rn-1] = cy; - rn -= (cy == 0); - } - else - mpn_copyd (rp + limbs, u->_mp_d, un); - - while (limbs > 0) - rp[--limbs] = 0; - - r->_mp_size = (u->_mp_size < 0) ? - rn : rn; -} - -void -mpz_addmul_ui (mpz_t r, const mpz_t u, unsigned long int v) -{ - mpz_t t; - mpz_init (t); - mpz_mul_ui (t, u, v); - mpz_add (r, r, t); - mpz_clear (t); -} - -void -mpz_submul_ui (mpz_t r, const mpz_t u, unsigned long int v) -{ - mpz_t t; - mpz_init (t); - mpz_mul_ui (t, u, v); - mpz_sub (r, r, t); - mpz_clear (t); -} - -void -mpz_addmul (mpz_t r, const mpz_t u, const mpz_t v) -{ - mpz_t t; - mpz_init (t); - mpz_mul (t, u, v); - mpz_add (r, r, t); - mpz_clear (t); -} - -void -mpz_submul (mpz_t r, const mpz_t u, const mpz_t v) -{ - mpz_t t; - mpz_init (t); - mpz_mul (t, u, v); - mpz_sub (r, r, t); - mpz_clear (t); -} - - -/* MPZ division */ -enum mpz_div_round_mode { GMP_DIV_FLOOR, GMP_DIV_CEIL, GMP_DIV_TRUNC }; - -/* Allows q or r to be zero. Returns 1 iff remainder is non-zero. */ -static int -mpz_div_qr (mpz_t q, mpz_t r, - const mpz_t n, const mpz_t d, enum mpz_div_round_mode mode) -{ - mp_size_t ns, ds, nn, dn, qs; - ns = n->_mp_size; - ds = d->_mp_size; - - if (ds == 0) - gmp_die("mpz_div_qr: Divide by zero."); - - if (ns == 0) - { - if (q) - q->_mp_size = 0; - if (r) - r->_mp_size = 0; - return 0; - } - - nn = GMP_ABS (ns); - dn = GMP_ABS (ds); - - qs = ds ^ ns; - - if (nn < dn) - { - if (mode == GMP_DIV_CEIL && qs >= 0) - { - /* q = 1, r = n - d */ - if (r) - mpz_sub (r, n, d); - if (q) - mpz_set_ui (q, 1); - } - else if (mode == GMP_DIV_FLOOR && qs < 0) - { - /* q = -1, r = n + d */ - if (r) - mpz_add (r, n, d); - if (q) - mpz_set_si (q, -1); - } - else - { - /* q = 0, r = d */ - if (r) - mpz_set (r, n); - if (q) - q->_mp_size = 0; - } - return 1; - } - else - { - mp_ptr np, qp; - mp_size_t qn, rn; - mpz_t tq, tr; - - mpz_init_set (tr, n); - np = tr->_mp_d; - - qn = nn - dn + 1; - - if (q) - { - mpz_init2 (tq, qn * GMP_LIMB_BITS); - qp = tq->_mp_d; - } - else - qp = NULL; - - mpn_div_qr (qp, np, nn, d->_mp_d, dn); - - if (qp) - { - qn -= (qp[qn-1] == 0); - - tq->_mp_size = qs < 0 ? -qn : qn; - } - rn = mpn_normalized_size (np, dn); - tr->_mp_size = ns < 0 ? - rn : rn; - - if (mode == GMP_DIV_FLOOR && qs < 0 && rn != 0) - { - if (q) - mpz_sub_ui (tq, tq, 1); - if (r) - mpz_add (tr, tr, d); - } - else if (mode == GMP_DIV_CEIL && qs >= 0 && rn != 0) - { - if (q) - mpz_add_ui (tq, tq, 1); - if (r) - mpz_sub (tr, tr, d); - } - - if (q) - { - mpz_swap (tq, q); - mpz_clear (tq); - } - if (r) - mpz_swap (tr, r); - - mpz_clear (tr); - - return rn != 0; - } -} - -void -mpz_cdiv_qr (mpz_t q, mpz_t r, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (q, r, n, d, GMP_DIV_CEIL); -} - -void -mpz_fdiv_qr (mpz_t q, mpz_t r, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (q, r, n, d, GMP_DIV_FLOOR); -} - -void -mpz_tdiv_qr (mpz_t q, mpz_t r, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (q, r, n, d, GMP_DIV_TRUNC); -} - -void -mpz_cdiv_q (mpz_t q, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (q, NULL, n, d, GMP_DIV_CEIL); -} - -void -mpz_fdiv_q (mpz_t q, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (q, NULL, n, d, GMP_DIV_FLOOR); -} - -void -mpz_tdiv_q (mpz_t q, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (q, NULL, n, d, GMP_DIV_TRUNC); -} - -void -mpz_cdiv_r (mpz_t r, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (NULL, r, n, d, GMP_DIV_CEIL); -} - -void -mpz_fdiv_r (mpz_t r, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (NULL, r, n, d, GMP_DIV_FLOOR); -} - -void -mpz_tdiv_r (mpz_t r, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (NULL, r, n, d, GMP_DIV_TRUNC); -} - -void -mpz_mod (mpz_t r, const mpz_t n, const mpz_t d) -{ - mpz_div_qr (NULL, r, n, d, d->_mp_size >= 0 ? GMP_DIV_FLOOR : GMP_DIV_CEIL); -} - -static void -mpz_div_q_2exp (mpz_t q, const mpz_t u, mp_bitcnt_t bit_index, - enum mpz_div_round_mode mode) -{ - mp_size_t un, qn; - mp_size_t limb_cnt; - mp_ptr qp; - int adjust; - - un = u->_mp_size; - if (un == 0) - { - q->_mp_size = 0; - return; - } - limb_cnt = bit_index / GMP_LIMB_BITS; - qn = GMP_ABS (un) - limb_cnt; - bit_index %= GMP_LIMB_BITS; - - if (mode == ((un > 0) ? GMP_DIV_CEIL : GMP_DIV_FLOOR)) /* un != 0 here. */ - /* Note: Below, the final indexing at limb_cnt is valid because at - that point we have qn > 0. */ - adjust = (qn <= 0 - || !mpn_zero_p (u->_mp_d, limb_cnt) - || (u->_mp_d[limb_cnt] - & (((mp_limb_t) 1 << bit_index) - 1))); - else - adjust = 0; - - if (qn <= 0) - qn = 0; - - else - { - qp = MPZ_REALLOC (q, qn); - - if (bit_index != 0) - { - mpn_rshift (qp, u->_mp_d + limb_cnt, qn, bit_index); - qn -= qp[qn - 1] == 0; - } - else - { - mpn_copyi (qp, u->_mp_d + limb_cnt, qn); - } - } - - q->_mp_size = qn; - - if (adjust) - mpz_add_ui (q, q, 1); - if (un < 0) - mpz_neg (q, q); -} - -static void -mpz_div_r_2exp (mpz_t r, const mpz_t u, mp_bitcnt_t bit_index, - enum mpz_div_round_mode mode) -{ - mp_size_t us, un, rn; - mp_ptr rp; - mp_limb_t mask; - - us = u->_mp_size; - if (us == 0 || bit_index == 0) - { - r->_mp_size = 0; - return; - } - rn = (bit_index + GMP_LIMB_BITS - 1) / GMP_LIMB_BITS; - assert (rn > 0); - - rp = MPZ_REALLOC (r, rn); - un = GMP_ABS (us); - - mask = GMP_LIMB_MAX >> (rn * GMP_LIMB_BITS - bit_index); - - if (rn > un) - { - /* Quotient (with truncation) is zero, and remainder is - non-zero */ - if (mode == ((us > 0) ? GMP_DIV_CEIL : GMP_DIV_FLOOR)) /* us != 0 here. */ - { - /* Have to negate and sign extend. */ - mp_size_t i; - mp_limb_t cy; - - for (cy = 1, i = 0; i < un; i++) - { - mp_limb_t s = ~u->_mp_d[i] + cy; - cy = s < cy; - rp[i] = s; - } - assert (cy == 0); - for (; i < rn - 1; i++) - rp[i] = GMP_LIMB_MAX; - - rp[rn-1] = mask; - us = -us; - } - else - { - /* Just copy */ - if (r != u) - mpn_copyi (rp, u->_mp_d, un); - - rn = un; - } - } - else - { - if (r != u) - mpn_copyi (rp, u->_mp_d, rn - 1); - - rp[rn-1] = u->_mp_d[rn-1] & mask; - - if (mode == ((us > 0) ? GMP_DIV_CEIL : GMP_DIV_FLOOR)) /* us != 0 here. */ - { - /* If r != 0, compute 2^{bit_count} - r. */ - mp_size_t i; - - for (i = 0; i < rn && rp[i] == 0; i++) - ; - if (i < rn) - { - /* r > 0, need to flip sign. */ - rp[i] = ~rp[i] + 1; - while (++i < rn) - rp[i] = ~rp[i]; - - rp[rn-1] &= mask; - - /* us is not used for anything else, so we can modify it - here to indicate flipped sign. */ - us = -us; - } - } - } - rn = mpn_normalized_size (rp, rn); - r->_mp_size = us < 0 ? -rn : rn; -} - -void -mpz_cdiv_q_2exp (mpz_t r, const mpz_t u, mp_bitcnt_t cnt) -{ - mpz_div_q_2exp (r, u, cnt, GMP_DIV_CEIL); -} - -void -mpz_fdiv_q_2exp (mpz_t r, const mpz_t u, mp_bitcnt_t cnt) -{ - mpz_div_q_2exp (r, u, cnt, GMP_DIV_FLOOR); -} - -void -mpz_tdiv_q_2exp (mpz_t r, const mpz_t u, mp_bitcnt_t cnt) -{ - mpz_div_q_2exp (r, u, cnt, GMP_DIV_TRUNC); -} - -void -mpz_cdiv_r_2exp (mpz_t r, const mpz_t u, mp_bitcnt_t cnt) -{ - mpz_div_r_2exp (r, u, cnt, GMP_DIV_CEIL); -} - -void -mpz_fdiv_r_2exp (mpz_t r, const mpz_t u, mp_bitcnt_t cnt) -{ - mpz_div_r_2exp (r, u, cnt, GMP_DIV_FLOOR); -} - -void -mpz_tdiv_r_2exp (mpz_t r, const mpz_t u, mp_bitcnt_t cnt) -{ - mpz_div_r_2exp (r, u, cnt, GMP_DIV_TRUNC); -} - -void -mpz_divexact (mpz_t q, const mpz_t n, const mpz_t d) -{ - gmp_assert_nocarry (mpz_div_qr (q, NULL, n, d, GMP_DIV_TRUNC)); -} - -int -mpz_divisible_p (const mpz_t n, const mpz_t d) -{ - return mpz_div_qr (NULL, NULL, n, d, GMP_DIV_TRUNC) == 0; -} - -int -mpz_congruent_p (const mpz_t a, const mpz_t b, const mpz_t m) -{ - mpz_t t; - int res; - - /* a == b (mod 0) iff a == b */ - if (mpz_sgn (m) == 0) - return (mpz_cmp (a, b) == 0); - - mpz_init (t); - mpz_sub (t, a, b); - res = mpz_divisible_p (t, m); - mpz_clear (t); - - return res; -} - -static unsigned long -mpz_div_qr_ui (mpz_t q, mpz_t r, - const mpz_t n, unsigned long d, enum mpz_div_round_mode mode) -{ - mp_size_t ns, qn; - mp_ptr qp; - mp_limb_t rl; - mp_size_t rs; - - ns = n->_mp_size; - if (ns == 0) - { - if (q) - q->_mp_size = 0; - if (r) - r->_mp_size = 0; - return 0; - } - - qn = GMP_ABS (ns); - if (q) - qp = MPZ_REALLOC (q, qn); - else - qp = NULL; - - rl = mpn_div_qr_1 (qp, n->_mp_d, qn, d); - assert (rl < d); - - rs = rl > 0; - rs = (ns < 0) ? -rs : rs; - - if (rl > 0 && ( (mode == GMP_DIV_FLOOR && ns < 0) - || (mode == GMP_DIV_CEIL && ns >= 0))) - { - if (q) - gmp_assert_nocarry (mpn_add_1 (qp, qp, qn, 1)); - rl = d - rl; - rs = -rs; - } - - if (r) - { - r->_mp_d[0] = rl; - r->_mp_size = rs; - } - if (q) - { - qn -= (qp[qn-1] == 0); - assert (qn == 0 || qp[qn-1] > 0); - - q->_mp_size = (ns < 0) ? - qn : qn; - } - - return rl; -} - -unsigned long -mpz_cdiv_qr_ui (mpz_t q, mpz_t r, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (q, r, n, d, GMP_DIV_CEIL); -} - -unsigned long -mpz_fdiv_qr_ui (mpz_t q, mpz_t r, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (q, r, n, d, GMP_DIV_FLOOR); -} - -unsigned long -mpz_tdiv_qr_ui (mpz_t q, mpz_t r, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (q, r, n, d, GMP_DIV_TRUNC); -} - -unsigned long -mpz_cdiv_q_ui (mpz_t q, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (q, NULL, n, d, GMP_DIV_CEIL); -} - -unsigned long -mpz_fdiv_q_ui (mpz_t q, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (q, NULL, n, d, GMP_DIV_FLOOR); -} - -unsigned long -mpz_tdiv_q_ui (mpz_t q, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (q, NULL, n, d, GMP_DIV_TRUNC); -} - -unsigned long -mpz_cdiv_r_ui (mpz_t r, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (NULL, r, n, d, GMP_DIV_CEIL); -} -unsigned long -mpz_fdiv_r_ui (mpz_t r, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (NULL, r, n, d, GMP_DIV_FLOOR); -} -unsigned long -mpz_tdiv_r_ui (mpz_t r, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (NULL, r, n, d, GMP_DIV_TRUNC); -} - -unsigned long -mpz_cdiv_ui (const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (NULL, NULL, n, d, GMP_DIV_CEIL); -} - -unsigned long -mpz_fdiv_ui (const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (NULL, NULL, n, d, GMP_DIV_FLOOR); -} - -unsigned long -mpz_tdiv_ui (const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (NULL, NULL, n, d, GMP_DIV_TRUNC); -} - -unsigned long -mpz_mod_ui (mpz_t r, const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (NULL, r, n, d, GMP_DIV_FLOOR); -} - -void -mpz_divexact_ui (mpz_t q, const mpz_t n, unsigned long d) -{ - gmp_assert_nocarry (mpz_div_qr_ui (q, NULL, n, d, GMP_DIV_TRUNC)); -} - -int -mpz_divisible_ui_p (const mpz_t n, unsigned long d) -{ - return mpz_div_qr_ui (NULL, NULL, n, d, GMP_DIV_TRUNC) == 0; -} - - -/* GCD */ -static mp_limb_t -mpn_gcd_11 (mp_limb_t u, mp_limb_t v) -{ - unsigned shift; - - assert ( (u | v) > 0); - - if (u == 0) - return v; - else if (v == 0) - return u; - - gmp_ctz (shift, u | v); - - u >>= shift; - v >>= shift; - - if ( (u & 1) == 0) - MP_LIMB_T_SWAP (u, v); - - while ( (v & 1) == 0) - v >>= 1; - - while (u != v) - { - if (u > v) - { - u -= v; - do - u >>= 1; - while ( (u & 1) == 0); - } - else - { - v -= u; - do - v >>= 1; - while ( (v & 1) == 0); - } - } - return u << shift; -} - -unsigned long -mpz_gcd_ui (mpz_t g, const mpz_t u, unsigned long v) -{ - mp_size_t un; - - if (v == 0) - { - if (g) - mpz_abs (g, u); - } - else - { - un = GMP_ABS (u->_mp_size); - if (un != 0) - v = mpn_gcd_11 (mpn_div_qr_1 (NULL, u->_mp_d, un, v), v); - - if (g) - mpz_set_ui (g, v); - } - - return v; -} - -static mp_bitcnt_t -mpz_make_odd (mpz_t r) -{ - mp_bitcnt_t shift; - - assert (r->_mp_size > 0); - /* Count trailing zeros, equivalent to mpn_scan1, because we know that there is a 1 */ - shift = mpn_common_scan (r->_mp_d[0], 0, r->_mp_d, 0, 0); - mpz_tdiv_q_2exp (r, r, shift); - - return shift; -} - -void -mpz_gcd (mpz_t g, const mpz_t u, const mpz_t v) -{ - mpz_t tu, tv; - mp_bitcnt_t uz, vz, gz; - - if (u->_mp_size == 0) - { - mpz_abs (g, v); - return; - } - if (v->_mp_size == 0) - { - mpz_abs (g, u); - return; - } - - mpz_init (tu); - mpz_init (tv); - - mpz_abs (tu, u); - uz = mpz_make_odd (tu); - mpz_abs (tv, v); - vz = mpz_make_odd (tv); - gz = GMP_MIN (uz, vz); - - if (tu->_mp_size < tv->_mp_size) - mpz_swap (tu, tv); - - mpz_tdiv_r (tu, tu, tv); - if (tu->_mp_size == 0) - { - mpz_swap (g, tv); - } - else - for (;;) - { - int c; - - mpz_make_odd (tu); - c = mpz_cmp (tu, tv); - if (c == 0) - { - mpz_swap (g, tu); - break; - } - if (c < 0) - mpz_swap (tu, tv); - - if (tv->_mp_size == 1) - { - mp_limb_t vl = tv->_mp_d[0]; - mp_limb_t ul = mpz_tdiv_ui (tu, vl); - mpz_set_ui (g, mpn_gcd_11 (ul, vl)); - break; - } - mpz_sub (tu, tu, tv); - } - mpz_clear (tu); - mpz_clear (tv); - mpz_mul_2exp (g, g, gz); -} - -void -mpz_gcdext (mpz_t g, mpz_t s, mpz_t t, const mpz_t u, const mpz_t v) -{ - mpz_t tu, tv, s0, s1, t0, t1; - mp_bitcnt_t uz, vz, gz; - mp_bitcnt_t power; - - if (u->_mp_size == 0) - { - /* g = 0 u + sgn(v) v */ - signed long sign = mpz_sgn (v); - mpz_abs (g, v); - if (s) - mpz_set_ui (s, 0); - if (t) - mpz_set_si (t, sign); - return; - } - - if (v->_mp_size == 0) - { - /* g = sgn(u) u + 0 v */ - signed long sign = mpz_sgn (u); - mpz_abs (g, u); - if (s) - mpz_set_si (s, sign); - if (t) - mpz_set_ui (t, 0); - return; - } - - mpz_init (tu); - mpz_init (tv); - mpz_init (s0); - mpz_init (s1); - mpz_init (t0); - mpz_init (t1); - - mpz_abs (tu, u); - uz = mpz_make_odd (tu); - mpz_abs (tv, v); - vz = mpz_make_odd (tv); - gz = GMP_MIN (uz, vz); - - uz -= gz; - vz -= gz; - - /* Cofactors corresponding to odd gcd. gz handled later. */ - if (tu->_mp_size < tv->_mp_size) - { - mpz_swap (tu, tv); - MPZ_SRCPTR_SWAP (u, v); - MPZ_PTR_SWAP (s, t); - MP_BITCNT_T_SWAP (uz, vz); - } - - /* Maintain - * - * u = t0 tu + t1 tv - * v = s0 tu + s1 tv - * - * where u and v denote the inputs with common factors of two - * eliminated, and det (s0, t0; s1, t1) = 2^p. Then - * - * 2^p tu = s1 u - t1 v - * 2^p tv = -s0 u + t0 v - */ - - /* After initial division, tu = q tv + tu', we have - * - * u = 2^uz (tu' + q tv) - * v = 2^vz tv - * - * or - * - * t0 = 2^uz, t1 = 2^uz q - * s0 = 0, s1 = 2^vz - */ - - mpz_setbit (t0, uz); - mpz_tdiv_qr (t1, tu, tu, tv); - mpz_mul_2exp (t1, t1, uz); - - mpz_setbit (s1, vz); - power = uz + vz; - - if (tu->_mp_size > 0) - { - mp_bitcnt_t shift; - shift = mpz_make_odd (tu); - mpz_mul_2exp (t0, t0, shift); - mpz_mul_2exp (s0, s0, shift); - power += shift; - - for (;;) - { - int c; - c = mpz_cmp (tu, tv); - if (c == 0) - break; - - if (c < 0) - { - /* tv = tv' + tu - * - * u = t0 tu + t1 (tv' + tu) = (t0 + t1) tu + t1 tv' - * v = s0 tu + s1 (tv' + tu) = (s0 + s1) tu + s1 tv' */ - - mpz_sub (tv, tv, tu); - mpz_add (t0, t0, t1); - mpz_add (s0, s0, s1); - - shift = mpz_make_odd (tv); - mpz_mul_2exp (t1, t1, shift); - mpz_mul_2exp (s1, s1, shift); - } - else - { - mpz_sub (tu, tu, tv); - mpz_add (t1, t0, t1); - mpz_add (s1, s0, s1); - - shift = mpz_make_odd (tu); - mpz_mul_2exp (t0, t0, shift); - mpz_mul_2exp (s0, s0, shift); - } - power += shift; - } - } - - /* Now tv = odd part of gcd, and -s0 and t0 are corresponding - cofactors. */ - - mpz_mul_2exp (tv, tv, gz); - mpz_neg (s0, s0); - - /* 2^p g = s0 u + t0 v. Eliminate one factor of two at a time. To - adjust cofactors, we need u / g and v / g */ - - mpz_divexact (s1, v, tv); - mpz_abs (s1, s1); - mpz_divexact (t1, u, tv); - mpz_abs (t1, t1); - - while (power-- > 0) - { - /* s0 u + t0 v = (s0 - v/g) u - (t0 + u/g) v */ - if (mpz_odd_p (s0) || mpz_odd_p (t0)) - { - mpz_sub (s0, s0, s1); - mpz_add (t0, t0, t1); - } - mpz_divexact_ui (s0, s0, 2); - mpz_divexact_ui (t0, t0, 2); - } - - /* Arrange so that |s| < |u| / 2g */ - mpz_add (s1, s0, s1); - if (mpz_cmpabs (s0, s1) > 0) - { - mpz_swap (s0, s1); - mpz_sub (t0, t0, t1); - } - if (u->_mp_size < 0) - mpz_neg (s0, s0); - if (v->_mp_size < 0) - mpz_neg (t0, t0); - - mpz_swap (g, tv); - if (s) - mpz_swap (s, s0); - if (t) - mpz_swap (t, t0); - - mpz_clear (tu); - mpz_clear (tv); - mpz_clear (s0); - mpz_clear (s1); - mpz_clear (t0); - mpz_clear (t1); -} - -void -mpz_lcm (mpz_t r, const mpz_t u, const mpz_t v) -{ - mpz_t g; - - if (u->_mp_size == 0 || v->_mp_size == 0) - { - r->_mp_size = 0; - return; - } - - mpz_init (g); - - mpz_gcd (g, u, v); - mpz_divexact (g, u, g); - mpz_mul (r, g, v); - - mpz_clear (g); - mpz_abs (r, r); -} - -void -mpz_lcm_ui (mpz_t r, const mpz_t u, unsigned long v) -{ - if (v == 0 || u->_mp_size == 0) - { - r->_mp_size = 0; - return; - } - - v /= mpz_gcd_ui (NULL, u, v); - mpz_mul_ui (r, u, v); - - mpz_abs (r, r); -} - -int -mpz_invert (mpz_t r, const mpz_t u, const mpz_t m) -{ - mpz_t g, tr; - int invertible; - - if (u->_mp_size == 0 || mpz_cmpabs_ui (m, 1) <= 0) - return 0; - - mpz_init (g); - mpz_init (tr); - - mpz_gcdext (g, tr, NULL, u, m); - invertible = (mpz_cmp_ui (g, 1) == 0); - - if (invertible) - { - if (tr->_mp_size < 0) - { - if (m->_mp_size >= 0) - mpz_add (tr, tr, m); - else - mpz_sub (tr, tr, m); - } - mpz_swap (r, tr); - } - - mpz_clear (g); - mpz_clear (tr); - return invertible; -} - - -/* Higher level operations (sqrt, pow and root) */ - -void -mpz_pow_ui (mpz_t r, const mpz_t b, unsigned long e) -{ - unsigned long bit; - mpz_t tr; - mpz_init_set_ui (tr, 1); - - bit = GMP_ULONG_HIGHBIT; - do - { - mpz_mul (tr, tr, tr); - if (e & bit) - mpz_mul (tr, tr, b); - bit >>= 1; - } - while (bit > 0); - - mpz_swap (r, tr); - mpz_clear (tr); -} - -void -mpz_ui_pow_ui (mpz_t r, unsigned long blimb, unsigned long e) -{ - mpz_t b; - mpz_init_set_ui (b, blimb); - mpz_pow_ui (r, b, e); - mpz_clear (b); -} - -void -mpz_powm (mpz_t r, const mpz_t b, const mpz_t e, const mpz_t m) -{ - mpz_t tr; - mpz_t base; - mp_size_t en, mn; - mp_srcptr mp; - struct gmp_div_inverse minv; - unsigned shift; - mp_ptr tp = NULL; - - en = GMP_ABS (e->_mp_size); - mn = GMP_ABS (m->_mp_size); - if (mn == 0) - gmp_die ("mpz_powm: Zero modulo."); - - if (en == 0) - { - mpz_set_ui (r, 1); - return; - } - - mp = m->_mp_d; - mpn_div_qr_invert (&minv, mp, mn); - shift = minv.shift; - - if (shift > 0) - { - /* To avoid shifts, we do all our reductions, except the final - one, using a *normalized* m. */ - minv.shift = 0; - - tp = gmp_xalloc_limbs (mn); - gmp_assert_nocarry (mpn_lshift (tp, mp, mn, shift)); - mp = tp; - } - - mpz_init (base); - - if (e->_mp_size < 0) - { - if (!mpz_invert (base, b, m)) - gmp_die ("mpz_powm: Negative exponent and non-invertible base."); - } - else - { - mp_size_t bn; - mpz_abs (base, b); - - bn = base->_mp_size; - if (bn >= mn) - { - mpn_div_qr_preinv (NULL, base->_mp_d, base->_mp_size, mp, mn, &minv); - bn = mn; - } - - /* We have reduced the absolute value. Now take care of the - sign. Note that we get zero represented non-canonically as - m. */ - if (b->_mp_size < 0) - { - mp_ptr bp = MPZ_REALLOC (base, mn); - gmp_assert_nocarry (mpn_sub (bp, mp, mn, bp, bn)); - bn = mn; - } - base->_mp_size = mpn_normalized_size (base->_mp_d, bn); - } - mpz_init_set_ui (tr, 1); - - while (en-- > 0) - { - mp_limb_t w = e->_mp_d[en]; - mp_limb_t bit; - - bit = GMP_LIMB_HIGHBIT; - do - { - mpz_mul (tr, tr, tr); - if (w & bit) - mpz_mul (tr, tr, base); - if (tr->_mp_size > mn) - { - mpn_div_qr_preinv (NULL, tr->_mp_d, tr->_mp_size, mp, mn, &minv); - tr->_mp_size = mpn_normalized_size (tr->_mp_d, mn); - } - bit >>= 1; - } - while (bit > 0); - } - - /* Final reduction */ - if (tr->_mp_size >= mn) - { - minv.shift = shift; - mpn_div_qr_preinv (NULL, tr->_mp_d, tr->_mp_size, mp, mn, &minv); - tr->_mp_size = mpn_normalized_size (tr->_mp_d, mn); - } - if (tp) - gmp_free (tp); - - mpz_swap (r, tr); - mpz_clear (tr); - mpz_clear (base); -} - -void -mpz_powm_ui (mpz_t r, const mpz_t b, unsigned long elimb, const mpz_t m) -{ - mpz_t e; - mpz_init_set_ui (e, elimb); - mpz_powm (r, b, e, m); - mpz_clear (e); -} - -/* x=trunc(y^(1/z)), r=y-x^z */ -void -mpz_rootrem (mpz_t x, mpz_t r, const mpz_t y, unsigned long z) -{ - int sgn; - mpz_t t, u; - - sgn = y->_mp_size < 0; - if ((~z & sgn) != 0) - gmp_die ("mpz_rootrem: Negative argument, with even root."); - if (z == 0) - gmp_die ("mpz_rootrem: Zeroth root."); - - if (mpz_cmpabs_ui (y, 1) <= 0) { - if (x) - mpz_set (x, y); - if (r) - r->_mp_size = 0; - return; - } - - mpz_init (u); - { - mp_bitcnt_t tb; - tb = mpz_sizeinbase (y, 2) / z + 1; - mpz_init2 (t, tb); - mpz_setbit (t, tb); - } - - if (z == 2) /* simplify sqrt loop: z-1 == 1 */ - do { - mpz_swap (u, t); /* u = x */ - mpz_tdiv_q (t, y, u); /* t = y/x */ - mpz_add (t, t, u); /* t = y/x + x */ - mpz_tdiv_q_2exp (t, t, 1); /* x'= (y/x + x)/2 */ - } while (mpz_cmpabs (t, u) < 0); /* |x'| < |x| */ - else /* z != 2 */ { - mpz_t v; - - mpz_init (v); - if (sgn) - mpz_neg (t, t); - - do { - mpz_swap (u, t); /* u = x */ - mpz_pow_ui (t, u, z - 1); /* t = x^(z-1) */ - mpz_tdiv_q (t, y, t); /* t = y/x^(z-1) */ - mpz_mul_ui (v, u, z - 1); /* v = x*(z-1) */ - mpz_add (t, t, v); /* t = y/x^(z-1) + x*(z-1) */ - mpz_tdiv_q_ui (t, t, z); /* x'=(y/x^(z-1) + x*(z-1))/z */ - } while (mpz_cmpabs (t, u) < 0); /* |x'| < |x| */ - - mpz_clear (v); - } - - if (r) { - mpz_pow_ui (t, u, z); - mpz_sub (r, y, t); - } - if (x) - mpz_swap (x, u); - mpz_clear (u); - mpz_clear (t); -} - -int -mpz_root (mpz_t x, const mpz_t y, unsigned long z) -{ - int res; - mpz_t r; - - mpz_init (r); - mpz_rootrem (x, r, y, z); - res = r->_mp_size == 0; - mpz_clear (r); - - return res; -} - -/* Compute s = floor(sqrt(u)) and r = u - s^2. Allows r == NULL */ -void -mpz_sqrtrem (mpz_t s, mpz_t r, const mpz_t u) -{ - mpz_rootrem (s, r, u, 2); -} - -void -mpz_sqrt (mpz_t s, const mpz_t u) -{ - mpz_rootrem (s, NULL, u, 2); -} - -int -mpz_perfect_square_p (const mpz_t u) -{ - if (u->_mp_size <= 0) - return (u->_mp_size == 0); - else - return mpz_root (NULL, u, 2); -} - -int -mpn_perfect_square_p (mp_srcptr p, mp_size_t n) -{ - mpz_t t; - - assert (n > 0); - assert (p [n-1] != 0); - return mpz_root (NULL, mpz_roinit_n (t, p, n), 2); -} - -mp_size_t -mpn_sqrtrem (mp_ptr sp, mp_ptr rp, mp_srcptr p, mp_size_t n) -{ - mpz_t s, r, u; - mp_size_t res; - - assert (n > 0); - assert (p [n-1] != 0); - - mpz_init (r); - mpz_init (s); - mpz_rootrem (s, r, mpz_roinit_n (u, p, n), 2); - - assert (s->_mp_size == (n+1)/2); - mpn_copyd (sp, s->_mp_d, s->_mp_size); - mpz_clear (s); - res = r->_mp_size; - if (rp) - mpn_copyd (rp, r->_mp_d, res); - mpz_clear (r); - return res; -} - -/* Combinatorics */ - -void -mpz_fac_ui (mpz_t x, unsigned long n) -{ - mpz_set_ui (x, n + (n == 0)); - for (;n > 2;) - mpz_mul_ui (x, x, --n); -} - -void -mpz_bin_uiui (mpz_t r, unsigned long n, unsigned long k) -{ - mpz_t t; - - mpz_set_ui (r, k <= n); - - if (k > (n >> 1)) - k = (k <= n) ? n - k : 0; - - mpz_init (t); - mpz_fac_ui (t, k); - - for (; k > 0; k--) - mpz_mul_ui (r, r, n--); - - mpz_divexact (r, r, t); - mpz_clear (t); -} - - -/* Primality testing */ -static int -gmp_millerrabin (const mpz_t n, const mpz_t nm1, mpz_t y, - const mpz_t q, mp_bitcnt_t k) -{ - assert (k > 0); - - /* Caller must initialize y to the base. */ - mpz_powm (y, y, q, n); - - if (mpz_cmp_ui (y, 1) == 0 || mpz_cmp (y, nm1) == 0) - return 1; - - while (--k > 0) - { - mpz_powm_ui (y, y, 2, n); - if (mpz_cmp (y, nm1) == 0) - return 1; - /* y == 1 means that the previous y was a non-trivial square root - of 1 (mod n). y == 0 means that n is a power of the base. - In either case, n is not prime. */ - if (mpz_cmp_ui (y, 1) <= 0) - return 0; - } - return 0; -} - -/* This product is 0xc0cfd797, and fits in 32 bits. */ -#define GMP_PRIME_PRODUCT \ - (3UL*5UL*7UL*11UL*13UL*17UL*19UL*23UL*29UL) - -/* Bit (p+1)/2 is set, for each odd prime <= 61 */ -#define GMP_PRIME_MASK 0xc96996dcUL - -int -mpz_probab_prime_p (const mpz_t n, int reps) -{ - mpz_t nm1; - mpz_t q; - mpz_t y; - mp_bitcnt_t k; - int is_prime; - int j; - - /* Note that we use the absolute value of n only, for compatibility - with the real GMP. */ - if (mpz_even_p (n)) - return (mpz_cmpabs_ui (n, 2) == 0) ? 2 : 0; - - /* Above test excludes n == 0 */ - assert (n->_mp_size != 0); - - if (mpz_cmpabs_ui (n, 64) < 0) - return (GMP_PRIME_MASK >> (n->_mp_d[0] >> 1)) & 2; - - if (mpz_gcd_ui (NULL, n, GMP_PRIME_PRODUCT) != 1) - return 0; - - /* All prime factors are >= 31. */ - if (mpz_cmpabs_ui (n, 31*31) < 0) - return 2; - - /* Use Miller-Rabin, with a deterministic sequence of bases, a[j] = - j^2 + j + 41 using Euler's polynomial. We potentially stop early, - if a[j] >= n - 1. Since n >= 31*31, this can happen only if reps > - 30 (a[30] == 971 > 31*31 == 961). */ - - mpz_init (nm1); - mpz_init (q); - mpz_init (y); - - /* Find q and k, where q is odd and n = 1 + 2**k * q. */ - nm1->_mp_size = mpz_abs_sub_ui (nm1, n, 1); - k = mpz_scan1 (nm1, 0); - mpz_tdiv_q_2exp (q, nm1, k); - - for (j = 0, is_prime = 1; is_prime & (j < reps); j++) - { - mpz_set_ui (y, (unsigned long) j*j+j+41); - if (mpz_cmp (y, nm1) >= 0) - { - /* Don't try any further bases. This "early" break does not affect - the result for any reasonable reps value (<=5000 was tested) */ - assert (j >= 30); - break; - } - is_prime = gmp_millerrabin (n, nm1, y, q, k); - } - mpz_clear (nm1); - mpz_clear (q); - mpz_clear (y); - - return is_prime; -} - - -/* Logical operations and bit manipulation. */ - -/* 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 complement. - 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 = GMP_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 = GMP_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 = GMP_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); - - gmp_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) -{ - if (!mpz_tstbit (d, bit_index)) - { - if (d->_mp_size >= 0) - mpz_abs_add_bit (d, bit_index); - else - mpz_abs_sub_bit (d, bit_index); - } -} - -void -mpz_clrbit (mpz_t d, mp_bitcnt_t bit_index) -{ - if (mpz_tstbit (d, bit_index)) - { - if (d->_mp_size >= 0) - mpz_abs_sub_bit (d, bit_index); - else - mpz_abs_add_bit (d, bit_index); - } -} - -void -mpz_combit (mpz_t d, mp_bitcnt_t bit_index) -{ - if (mpz_tstbit (d, bit_index) ^ (d->_mp_size < 0)) - mpz_abs_sub_bit (d, bit_index); - else - mpz_abs_add_bit (d, bit_index); -} - -void -mpz_com (mpz_t r, const mpz_t u) -{ - mpz_neg (r, u); - mpz_sub_ui (r, r, 1); -} - -void -mpz_and (mpz_t r, const mpz_t u, const mpz_t v) -{ - mp_size_t un, vn, rn, i; - mp_ptr up, vp, rp; - - mp_limb_t ux, vx, rx; - mp_limb_t uc, vc, rc; - mp_limb_t ul, vl, rl; - - un = GMP_ABS (u->_mp_size); - vn = GMP_ABS (v->_mp_size); - if (un < vn) - { - MPZ_SRCPTR_SWAP (u, v); - MP_SIZE_T_SWAP (un, vn); - } - if (vn == 0) - { - r->_mp_size = 0; - return; - } - - uc = u->_mp_size < 0; - vc = v->_mp_size < 0; - rc = uc & vc; - - ux = -uc; - vx = -vc; - rx = -rc; - - /* If the smaller input is positive, higher limbs don't matter. */ - rn = vx ? un : vn; - - rp = MPZ_REALLOC (r, rn + rc); - - up = u->_mp_d; - vp = v->_mp_d; - - i = 0; - do - { - ul = (up[i] ^ ux) + uc; - uc = ul < uc; - - vl = (vp[i] ^ vx) + vc; - vc = vl < vc; - - rl = ( (ul & vl) ^ rx) + rc; - rc = rl < rc; - rp[i] = rl; - } - while (++i < vn); - assert (vc == 0); - - for (; i < rn; i++) - { - ul = (up[i] ^ ux) + uc; - uc = ul < uc; - - rl = ( (ul & vx) ^ rx) + rc; - rc = rl < rc; - rp[i] = rl; - } - if (rc) - rp[rn++] = rc; - else - rn = mpn_normalized_size (rp, rn); - - r->_mp_size = rx ? -rn : rn; -} - -void -mpz_ior (mpz_t r, const mpz_t u, const mpz_t v) -{ - mp_size_t un, vn, rn, i; - mp_ptr up, vp, rp; - - mp_limb_t ux, vx, rx; - mp_limb_t uc, vc, rc; - mp_limb_t ul, vl, rl; - - un = GMP_ABS (u->_mp_size); - vn = GMP_ABS (v->_mp_size); - if (un < vn) - { - MPZ_SRCPTR_SWAP (u, v); - MP_SIZE_T_SWAP (un, vn); - } - if (vn == 0) - { - mpz_set (r, u); - return; - } - - uc = u->_mp_size < 0; - vc = v->_mp_size < 0; - rc = uc | vc; - - ux = -uc; - vx = -vc; - rx = -rc; - - /* If the smaller input is negative, by sign extension higher limbs - don't matter. */ - rn = vx ? vn : un; - - rp = MPZ_REALLOC (r, rn + rc); - - up = u->_mp_d; - vp = v->_mp_d; - - i = 0; - do - { - ul = (up[i] ^ ux) + uc; - uc = ul < uc; - - vl = (vp[i] ^ vx) + vc; - vc = vl < vc; - - rl = ( (ul | vl) ^ rx) + rc; - rc = rl < rc; - rp[i] = rl; - } - while (++i < vn); - assert (vc == 0); - - for (; i < rn; i++) - { - ul = (up[i] ^ ux) + uc; - uc = ul < uc; - - rl = ( (ul | vx) ^ rx) + rc; - rc = rl < rc; - rp[i] = rl; - } - if (rc) - rp[rn++] = rc; - else - rn = mpn_normalized_size (rp, rn); - - r->_mp_size = rx ? -rn : rn; -} - -void -mpz_xor (mpz_t r, const mpz_t u, const mpz_t v) -{ - mp_size_t un, vn, i; - mp_ptr up, vp, rp; - - mp_limb_t ux, vx, rx; - mp_limb_t uc, vc, rc; - mp_limb_t ul, vl, rl; - - un = GMP_ABS (u->_mp_size); - vn = GMP_ABS (v->_mp_size); - if (un < vn) - { - MPZ_SRCPTR_SWAP (u, v); - MP_SIZE_T_SWAP (un, vn); - } - if (vn == 0) - { - mpz_set (r, u); - return; - } - - uc = u->_mp_size < 0; - vc = v->_mp_size < 0; - rc = uc ^ vc; - - ux = -uc; - vx = -vc; - rx = -rc; - - rp = MPZ_REALLOC (r, un + rc); - - up = u->_mp_d; - vp = v->_mp_d; - - i = 0; - do - { - ul = (up[i] ^ ux) + uc; - uc = ul < uc; - - vl = (vp[i] ^ vx) + vc; - vc = vl < vc; - - rl = (ul ^ vl ^ rx) + rc; - rc = rl < rc; - rp[i] = rl; - } - while (++i < vn); - assert (vc == 0); - - for (; i < un; i++) - { - ul = (up[i] ^ ux) + uc; - uc = ul < uc; - - rl = (ul ^ ux) + rc; - rc = rl < rc; - rp[i] = rl; - } - if (rc) - rp[un++] = rc; - else - un = mpn_normalized_size (rp, un); - - r->_mp_size = rx ? -un : un; -} - -static unsigned -gmp_popcount_limb (mp_limb_t x) -{ - unsigned c; - - /* Do 16 bits at a time, to avoid limb-sized constants. */ - for (c = 0; x > 0; x >>= 16) - { - unsigned w = ((x >> 1) & 0x5555) + (x & 0x5555); - w = ((w >> 2) & 0x3333) + (w & 0x3333); - w = ((w >> 4) & 0x0f0f) + (w & 0x0f0f); - w = (w >> 8) + (w & 0x00ff); - c += w; - } - return c; -} - -mp_bitcnt_t -mpn_popcount (mp_srcptr p, mp_size_t n) -{ - mp_size_t i; - mp_bitcnt_t c; - - for (c = 0, i = 0; i < n; i++) - c += gmp_popcount_limb (p[i]); - - return c; -} - -mp_bitcnt_t -mpz_popcount (const mpz_t u) -{ - mp_size_t un; - - un = u->_mp_size; - - if (un < 0) - return ~(mp_bitcnt_t) 0; - - return mpn_popcount (u->_mp_d, un); -} - -mp_bitcnt_t -mpz_hamdist (const mpz_t u, const mpz_t v) -{ - mp_size_t un, vn, i; - mp_limb_t uc, vc, ul, vl, comp; - mp_srcptr up, vp; - mp_bitcnt_t c; - - un = u->_mp_size; - vn = v->_mp_size; - - if ( (un ^ vn) < 0) - return ~(mp_bitcnt_t) 0; - - comp = - (uc = vc = (un < 0)); - if (uc) - { - assert (vn < 0); - un = -un; - vn = -vn; - } - - up = u->_mp_d; - vp = v->_mp_d; - - if (un < vn) - MPN_SRCPTR_SWAP (up, un, vp, vn); - - for (i = 0, c = 0; i < vn; i++) - { - ul = (up[i] ^ comp) + uc; - uc = ul < uc; - - vl = (vp[i] ^ comp) + vc; - vc = vl < vc; - - c += gmp_popcount_limb (ul ^ vl); - } - assert (vc == 0); - - for (; i < un; i++) - { - ul = (up[i] ^ comp) + uc; - uc = ul < uc; - - c += gmp_popcount_limb (ul ^ comp); - } - - return c; -} - -mp_bitcnt_t -mpz_scan1 (const mpz_t u, mp_bitcnt_t starting_bit) -{ - mp_ptr up; - mp_size_t us, un, i; - mp_limb_t limb, ux; - - us = u->_mp_size; - un = GMP_ABS (us); - i = starting_bit / GMP_LIMB_BITS; - - /* Past the end there's no 1 bits for u>=0, or an immediate 1 bit - for u<0. Notice this test picks up any u==0 too. */ - if (i >= un) - return (us >= 0 ? ~(mp_bitcnt_t) 0 : starting_bit); - - up = u->_mp_d; - ux = 0; - limb = up[i]; - - if (starting_bit != 0) - { - if (us < 0) - { - ux = mpn_zero_p (up, i); - limb = ~ limb + ux; - ux = - (mp_limb_t) (limb >= ux); - } - - /* Mask to 0 all bits before starting_bit, thus ignoring them. */ - limb &= (GMP_LIMB_MAX << (starting_bit % GMP_LIMB_BITS)); - } - - return mpn_common_scan (limb, i, up, un, ux); -} - -mp_bitcnt_t -mpz_scan0 (const mpz_t u, mp_bitcnt_t starting_bit) -{ - mp_ptr up; - mp_size_t us, un, i; - mp_limb_t limb, ux; - - us = u->_mp_size; - ux = - (mp_limb_t) (us >= 0); - un = GMP_ABS (us); - i = starting_bit / GMP_LIMB_BITS; - - /* When past end, there's an immediate 0 bit for u>=0, or no 0 bits for - u<0. Notice this test picks up all cases of u==0 too. */ - if (i >= un) - return (ux ? starting_bit : ~(mp_bitcnt_t) 0); - - up = u->_mp_d; - limb = up[i] ^ ux; - - if (ux == 0) - limb -= mpn_zero_p (up, i); /* limb = ~(~limb + zero_p) */ - - /* Mask all bits before starting_bit, thus ignoring them. */ - limb &= (GMP_LIMB_MAX << (starting_bit % GMP_LIMB_BITS)); - - return mpn_common_scan (limb, i, up, un, ux); -} - - -/* MPZ base conversion. */ - -size_t -mpz_sizeinbase (const mpz_t u, int base) -{ - mp_size_t un; - mp_srcptr up; - mp_ptr tp; - mp_bitcnt_t bits; - struct gmp_div_inverse bi; - size_t ndigits; - - assert (base >= 2); - assert (base <= 36); - - un = GMP_ABS (u->_mp_size); - if (un == 0) - return 1; - - up = u->_mp_d; - - bits = (un - 1) * GMP_LIMB_BITS + mpn_limb_size_in_base_2 (up[un-1]); - switch (base) - { - case 2: - return bits; - case 4: - return (bits + 1) / 2; - case 8: - return (bits + 2) / 3; - case 16: - return (bits + 3) / 4; - case 32: - return (bits + 4) / 5; - /* FIXME: Do something more clever for the common case of base - 10. */ - } - - tp = gmp_xalloc_limbs (un); - mpn_copyi (tp, up, un); - mpn_div_qr_1_invert (&bi, base); - - ndigits = 0; - do - { - ndigits++; - mpn_div_qr_1_preinv (tp, tp, un, &bi); - un -= (tp[un-1] == 0); - } - while (un > 0); - - gmp_free (tp); - return ndigits; -} - -char * -mpz_get_str (char *sp, int base, const mpz_t u) -{ - unsigned bits; - const char *digits; - mp_size_t un; - size_t i, sn; - - if (base >= 0) - { - digits = "0123456789abcdefghijklmnopqrstuvwxyz"; - } - else - { - base = -base; - digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; - } - if (base <= 1) - base = 10; - if (base > 36) - return NULL; - - sn = 1 + mpz_sizeinbase (u, base); - if (!sp) - sp = gmp_xalloc (1 + sn); - - un = GMP_ABS (u->_mp_size); - - if (un == 0) - { - sp[0] = '0'; - sp[1] = '\0'; - return sp; - } - - i = 0; - - if (u->_mp_size < 0) - sp[i++] = '-'; - - bits = mpn_base_power_of_two_p (base); - - if (bits) - /* Not modified in this case. */ - sn = i + mpn_get_str_bits ((unsigned char *) sp + i, bits, u->_mp_d, un); - else - { - struct mpn_base_info info; - mp_ptr tp; - - mpn_get_base_info (&info, base); - tp = gmp_xalloc_limbs (un); - mpn_copyi (tp, u->_mp_d, un); - - sn = i + mpn_get_str_other ((unsigned char *) sp + i, base, &info, tp, un); - gmp_free (tp); - } - - for (; i < sn; i++) - sp[i] = digits[(unsigned char) sp[i]]; - - sp[sn] = '\0'; - return sp; -} - -int -mpz_set_str (mpz_t r, const char *sp, int base) -{ - unsigned bits; - mp_size_t rn, alloc; - mp_ptr rp; - size_t sn; - int sign; - unsigned char *dp; - - assert (base == 0 || (base >= 2 && base <= 36)); - - while (isspace( (unsigned char) *sp)) - sp++; - - sign = (*sp == '-'); - sp += sign; - - if (base == 0) - { - if (*sp == '0') - { - sp++; - if (*sp == 'x' || *sp == 'X') - { - base = 16; - sp++; - } - else if (*sp == 'b' || *sp == 'B') - { - base = 2; - sp++; - } - else - base = 8; - } - else - base = 10; - } - - sn = strlen (sp); - dp = gmp_xalloc (sn + (sn == 0)); - - for (sn = 0; *sp; sp++) - { - unsigned digit; - - if (isspace ((unsigned char) *sp)) - continue; - if (*sp >= '0' && *sp <= '9') - digit = *sp - '0'; - else if (*sp >= 'a' && *sp <= 'z') - digit = *sp - 'a' + 10; - else if (*sp >= 'A' && *sp <= 'Z') - digit = *sp - 'A' + 10; - else - digit = base; /* fail */ - - if (digit >= base) - { - gmp_free (dp); - r->_mp_size = 0; - return -1; - } - - dp[sn++] = digit; - } - - bits = mpn_base_power_of_two_p (base); - - if (bits > 0) - { - alloc = (sn * bits + GMP_LIMB_BITS - 1) / GMP_LIMB_BITS; - rp = MPZ_REALLOC (r, alloc); - rn = mpn_set_str_bits (rp, dp, sn, bits); - } - else - { - struct mpn_base_info info; - mpn_get_base_info (&info, base); - alloc = (sn + info.exp - 1) / info.exp; - rp = MPZ_REALLOC (r, alloc); - rn = mpn_set_str_other (rp, dp, sn, base, &info); - } - assert (rn <= alloc); - gmp_free (dp); - - r->_mp_size = sign ? - rn : rn; - - return 0; -} - -int -mpz_init_set_str (mpz_t r, const char *sp, int base) -{ - mpz_init (r); - return mpz_set_str (r, sp, base); -} - -size_t -mpz_out_str (FILE *stream, int base, const mpz_t x) -{ - char *str; - size_t len; - - str = mpz_get_str (NULL, base, x); - len = strlen (str); - len = fwrite (str, 1, len, stream); - gmp_free (str); - return len; -} - - -static int -gmp_detect_endian (void) -{ - static const int i = 2; - const unsigned char *p = (const unsigned char *) &i; - return 1 - *p; -} - -/* Import and export. Does not support nails. */ -void -mpz_import (mpz_t r, size_t count, int order, size_t size, int endian, - size_t nails, const void *src) -{ - const unsigned char *p; - ptrdiff_t word_step; - mp_ptr rp; - mp_size_t rn; - - /* The current (partial) limb. */ - mp_limb_t limb; - /* The number of bytes already copied to this limb (starting from - the low end). */ - size_t bytes; - /* The index where the limb should be stored, when completed. */ - mp_size_t i; - - if (nails != 0) - gmp_die ("mpz_import: Nails not supported."); - - assert (order == 1 || order == -1); - assert (endian >= -1 && endian <= 1); - - if (endian == 0) - endian = gmp_detect_endian (); - - p = (unsigned char *) src; - - word_step = (order != endian) ? 2 * size : 0; - - /* Process bytes from the least significant end, so point p at the - least significant word. */ - if (order == 1) - { - p += size * (count - 1); - word_step = - word_step; - } - - /* And at least significant byte of that word. */ - if (endian == 1) - p += (size - 1); - - rn = (size * count + sizeof(mp_limb_t) - 1) / sizeof(mp_limb_t); - rp = MPZ_REALLOC (r, rn); - - for (limb = 0, bytes = 0, i = 0; count > 0; count--, p += word_step) - { - size_t j; - for (j = 0; j < size; j++, p -= (ptrdiff_t) endian) - { - limb |= (mp_limb_t) *p << (bytes++ * CHAR_BIT); - if (bytes == sizeof(mp_limb_t)) - { - rp[i++] = limb; - bytes = 0; - limb = 0; - } - } - } - assert (i + (bytes > 0) == rn); - if (limb != 0) - rp[i++] = limb; - else - i = mpn_normalized_size (rp, i); - - r->_mp_size = i; -} - -void * -mpz_export (void *r, size_t *countp, int order, size_t size, int endian, - size_t nails, const mpz_t u) -{ - size_t count; - mp_size_t un; - - if (nails != 0) - gmp_die ("mpz_import: Nails not supported."); - - assert (order == 1 || order == -1); - assert (endian >= -1 && endian <= 1); - assert (size > 0 || u->_mp_size == 0); - - un = u->_mp_size; - count = 0; - if (un != 0) - { - size_t k; - unsigned char *p; - ptrdiff_t word_step; - /* The current (partial) limb. */ - mp_limb_t limb; - /* The number of bytes left to to in this limb. */ - size_t bytes; - /* The index where the limb was read. */ - mp_size_t i; - - un = GMP_ABS (un); - - /* Count bytes in top limb. */ - limb = u->_mp_d[un-1]; - assert (limb != 0); - - k = 0; - do { - k++; limb >>= CHAR_BIT; - } while (limb != 0); - - count = (k + (un-1) * sizeof (mp_limb_t) + size - 1) / size; - - if (!r) - r = gmp_xalloc (count * size); - - if (endian == 0) - endian = gmp_detect_endian (); - - p = (unsigned char *) r; - - word_step = (order != endian) ? 2 * size : 0; - - /* Process bytes from the least significant end, so point p at the - least significant word. */ - if (order == 1) - { - p += size * (count - 1); - word_step = - word_step; - } - - /* And at least significant byte of that word. */ - if (endian == 1) - p += (size - 1); - - for (bytes = 0, i = 0, k = 0; k < count; k++, p += word_step) - { - size_t j; - for (j = 0; j < size; j++, p -= (ptrdiff_t) endian) - { - if (bytes == 0) - { - if (i < un) - limb = u->_mp_d[i++]; - bytes = sizeof (mp_limb_t); - } - *p = limb; - limb >>= CHAR_BIT; - bytes--; - } - } - assert (i == un); - assert (k == count); - } - - if (countp) - *countp = count; - - return r; -} diff --git a/gmp/mini-gmp/mini-gmp.h b/gmp/mini-gmp/mini-gmp.h deleted file mode 100644 index c043ca7e66..0000000000 --- a/gmp/mini-gmp/mini-gmp.h +++ /dev/null @@ -1,294 +0,0 @@ -/* mini-gmp, a minimalistic implementation of a GNU GMP subset. - -Copyright 2011-2014 Free Software Foundation, Inc. - -This file is part of the GNU MP Library. - -The GNU MP Library is free software; you can redistribute it and/or modify -it under the terms of either: - - * the GNU Lesser General Public License as published by the Free - Software Foundation; either version 3 of the License, or (at your - option) any later version. - -or - - * the GNU General Public License as published by the Free Software - Foundation; either version 2 of the License, or (at your option) any - later version. - -or both in parallel, as here. - -The GNU MP Library is distributed in the hope that it will be useful, but -WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -for more details. - -You should have received copies of the GNU General Public License and the -GNU Lesser General Public License along with the GNU MP Library. If not, -see https://www.gnu.org/licenses/. */ - -/* About mini-gmp: This is a minimal implementation of a subset of the - GMP interface. It is intended for inclusion into applications which - have modest bignums needs, as a fallback when the real GMP library - is not installed. - - This file defines the public interface. */ - -#ifndef __MINI_GMP_H__ -#define __MINI_GMP_H__ - -/* For size_t */ -#include <stddef.h> - -#if defined (__cplusplus) -extern "C" { -#endif - -void mp_set_memory_functions (void *(*) (size_t), - void *(*) (void *, size_t, size_t), - void (*) (void *, size_t)); - -void mp_get_memory_functions (void *(**) (size_t), - void *(**) (void *, size_t, size_t), - void (**) (void *, size_t)); - -typedef unsigned long mp_limb_t; -typedef long mp_size_t; -typedef unsigned long mp_bitcnt_t; - -typedef mp_limb_t *mp_ptr; -typedef const mp_limb_t *mp_srcptr; - -typedef struct -{ - int _mp_alloc; /* Number of *limbs* allocated and pointed - to by the _mp_d field. */ - int _mp_size; /* abs(_mp_size) is the number of limbs the - last field points to. If _mp_size is - negative this is a negative number. */ - mp_limb_t *_mp_d; /* Pointer to the limbs. */ -} __mpz_struct; - -typedef __mpz_struct mpz_t[1]; - -typedef __mpz_struct *mpz_ptr; -typedef const __mpz_struct *mpz_srcptr; - -extern const int mp_bits_per_limb; - -void mpn_copyi (mp_ptr, mp_srcptr, mp_size_t); -void mpn_copyd (mp_ptr, mp_srcptr, mp_size_t); -void mpn_zero (mp_ptr, mp_size_t); - -int mpn_cmp (mp_srcptr, mp_srcptr, mp_size_t); - -mp_limb_t mpn_add_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); -mp_limb_t mpn_add_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t); -mp_limb_t mpn_add (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t); - -mp_limb_t mpn_sub_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); -mp_limb_t mpn_sub_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t); -mp_limb_t mpn_sub (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t); - -mp_limb_t mpn_mul_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); -mp_limb_t mpn_addmul_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); -mp_limb_t mpn_submul_1 (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); - -mp_limb_t mpn_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t); -void mpn_mul_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t); -void mpn_sqr (mp_ptr, mp_srcptr, mp_size_t); -int mpn_perfect_square_p (mp_srcptr, mp_size_t); -mp_size_t mpn_sqrtrem (mp_ptr, mp_ptr, mp_srcptr, mp_size_t); - -mp_limb_t mpn_lshift (mp_ptr, mp_srcptr, mp_size_t, unsigned int); -mp_limb_t mpn_rshift (mp_ptr, mp_srcptr, mp_size_t, unsigned int); - -mp_bitcnt_t mpn_scan0 (mp_srcptr, mp_bitcnt_t); -mp_bitcnt_t mpn_scan1 (mp_srcptr, mp_bitcnt_t); - -mp_bitcnt_t mpn_popcount (mp_srcptr, mp_size_t); - -mp_limb_t mpn_invert_3by2 (mp_limb_t, mp_limb_t); -#define mpn_invert_limb(x) mpn_invert_3by2 ((x), 0) - -size_t mpn_get_str (unsigned char *, int, mp_ptr, mp_size_t); -mp_size_t mpn_set_str (mp_ptr, const unsigned char *, size_t, int); - -void mpz_init (mpz_t); -void mpz_init2 (mpz_t, mp_bitcnt_t); -void mpz_clear (mpz_t); - -#define mpz_odd_p(z) (((z)->_mp_size != 0) & (int) (z)->_mp_d[0]) -#define mpz_even_p(z) (! mpz_odd_p (z)) - -int mpz_sgn (const mpz_t); -int mpz_cmp_si (const mpz_t, long); -int mpz_cmp_ui (const mpz_t, unsigned long); -int mpz_cmp (const mpz_t, const mpz_t); -int mpz_cmpabs_ui (const mpz_t, unsigned long); -int mpz_cmpabs (const mpz_t, const mpz_t); -int mpz_cmp_d (const mpz_t, double); -int mpz_cmpabs_d (const mpz_t, double); - -void mpz_abs (mpz_t, const mpz_t); -void mpz_neg (mpz_t, const mpz_t); -void mpz_swap (mpz_t, mpz_t); - -void mpz_add_ui (mpz_t, const mpz_t, unsigned long); -void mpz_add (mpz_t, const mpz_t, const mpz_t); -void mpz_sub_ui (mpz_t, const mpz_t, unsigned long); -void mpz_ui_sub (mpz_t, unsigned long, const mpz_t); -void mpz_sub (mpz_t, const mpz_t, const mpz_t); - -void mpz_mul_si (mpz_t, const mpz_t, long int); -void mpz_mul_ui (mpz_t, const mpz_t, unsigned long int); -void mpz_mul (mpz_t, const mpz_t, const mpz_t); -void mpz_mul_2exp (mpz_t, const mpz_t, mp_bitcnt_t); -void mpz_addmul_ui (mpz_t, const mpz_t, unsigned long int); -void mpz_addmul (mpz_t, const mpz_t, const mpz_t); -void mpz_submul_ui (mpz_t, const mpz_t, unsigned long int); -void mpz_submul (mpz_t, const mpz_t, const mpz_t); - -void mpz_cdiv_qr (mpz_t, mpz_t, const mpz_t, const mpz_t); -void mpz_fdiv_qr (mpz_t, mpz_t, const mpz_t, const mpz_t); -void mpz_tdiv_qr (mpz_t, mpz_t, const mpz_t, const mpz_t); -void mpz_cdiv_q (mpz_t, const mpz_t, const mpz_t); -void mpz_fdiv_q (mpz_t, const mpz_t, const mpz_t); -void mpz_tdiv_q (mpz_t, const mpz_t, const mpz_t); -void mpz_cdiv_r (mpz_t, const mpz_t, const mpz_t); -void mpz_fdiv_r (mpz_t, const mpz_t, const mpz_t); -void mpz_tdiv_r (mpz_t, const mpz_t, const mpz_t); - -void mpz_cdiv_q_2exp (mpz_t, const mpz_t, mp_bitcnt_t); -void mpz_fdiv_q_2exp (mpz_t, const mpz_t, mp_bitcnt_t); -void mpz_tdiv_q_2exp (mpz_t, const mpz_t, mp_bitcnt_t); -void mpz_cdiv_r_2exp (mpz_t, const mpz_t, mp_bitcnt_t); -void mpz_fdiv_r_2exp (mpz_t, const mpz_t, mp_bitcnt_t); -void mpz_tdiv_r_2exp (mpz_t, const mpz_t, mp_bitcnt_t); - -void mpz_mod (mpz_t, const mpz_t, const mpz_t); - -void mpz_divexact (mpz_t, const mpz_t, const mpz_t); - -int mpz_divisible_p (const mpz_t, const mpz_t); -int mpz_congruent_p (const mpz_t, const mpz_t, const mpz_t); - -unsigned long mpz_cdiv_qr_ui (mpz_t, mpz_t, const mpz_t, unsigned long); -unsigned long mpz_fdiv_qr_ui (mpz_t, mpz_t, const mpz_t, unsigned long); -unsigned long mpz_tdiv_qr_ui (mpz_t, mpz_t, const mpz_t, unsigned long); -unsigned long mpz_cdiv_q_ui (mpz_t, const mpz_t, unsigned long); -unsigned long mpz_fdiv_q_ui (mpz_t, const mpz_t, unsigned long); -unsigned long mpz_tdiv_q_ui (mpz_t, const mpz_t, unsigned long); -unsigned long mpz_cdiv_r_ui (mpz_t, const mpz_t, unsigned long); -unsigned long mpz_fdiv_r_ui (mpz_t, const mpz_t, unsigned long); -unsigned long mpz_tdiv_r_ui (mpz_t, const mpz_t, unsigned long); -unsigned long mpz_cdiv_ui (const mpz_t, unsigned long); -unsigned long mpz_fdiv_ui (const mpz_t, unsigned long); -unsigned long mpz_tdiv_ui (const mpz_t, unsigned long); - -unsigned long mpz_mod_ui (mpz_t, const mpz_t, unsigned long); - -void mpz_divexact_ui (mpz_t, const mpz_t, unsigned long); - -int mpz_divisible_ui_p (const mpz_t, unsigned long); - -unsigned long mpz_gcd_ui (mpz_t, const mpz_t, unsigned long); -void mpz_gcd (mpz_t, const mpz_t, const mpz_t); -void mpz_gcdext (mpz_t, mpz_t, mpz_t, const mpz_t, const mpz_t); -void mpz_lcm_ui (mpz_t, const mpz_t, unsigned long); -void mpz_lcm (mpz_t, const mpz_t, const mpz_t); -int mpz_invert (mpz_t, const mpz_t, const mpz_t); - -void mpz_sqrtrem (mpz_t, mpz_t, const mpz_t); -void mpz_sqrt (mpz_t, const mpz_t); -int mpz_perfect_square_p (const mpz_t); - -void mpz_pow_ui (mpz_t, const mpz_t, unsigned long); -void mpz_ui_pow_ui (mpz_t, unsigned long, unsigned long); -void mpz_powm (mpz_t, const mpz_t, const mpz_t, const mpz_t); -void mpz_powm_ui (mpz_t, const mpz_t, unsigned long, const mpz_t); - -void mpz_rootrem (mpz_t, mpz_t, const mpz_t, unsigned long); -int mpz_root (mpz_t, const mpz_t, unsigned long); - -void mpz_fac_ui (mpz_t, unsigned long); -void mpz_bin_uiui (mpz_t, unsigned long, unsigned long); - -int mpz_probab_prime_p (const mpz_t, int); - -int mpz_tstbit (const mpz_t, mp_bitcnt_t); -void mpz_setbit (mpz_t, mp_bitcnt_t); -void mpz_clrbit (mpz_t, mp_bitcnt_t); -void mpz_combit (mpz_t, mp_bitcnt_t); - -void mpz_com (mpz_t, const mpz_t); -void mpz_and (mpz_t, const mpz_t, const mpz_t); -void mpz_ior (mpz_t, const mpz_t, const mpz_t); -void mpz_xor (mpz_t, const mpz_t, const mpz_t); - -mp_bitcnt_t mpz_popcount (const mpz_t); -mp_bitcnt_t mpz_hamdist (const mpz_t, const mpz_t); -mp_bitcnt_t mpz_scan0 (const mpz_t, mp_bitcnt_t); -mp_bitcnt_t mpz_scan1 (const mpz_t, mp_bitcnt_t); - -int mpz_fits_slong_p (const mpz_t); -int mpz_fits_ulong_p (const mpz_t); -long int mpz_get_si (const mpz_t); -unsigned long int mpz_get_ui (const mpz_t); -double mpz_get_d (const mpz_t); -size_t mpz_size (const mpz_t); -mp_limb_t mpz_getlimbn (const mpz_t, mp_size_t); - -void mpz_realloc2 (mpz_t, mp_bitcnt_t); -mp_srcptr mpz_limbs_read (mpz_srcptr); -mp_ptr mpz_limbs_modify (mpz_t, mp_size_t); -mp_ptr mpz_limbs_write (mpz_t, mp_size_t); -void mpz_limbs_finish (mpz_t, mp_size_t); -mpz_srcptr mpz_roinit_n (mpz_t, mp_srcptr, mp_size_t); - -#define MPZ_ROINIT_N(xp, xs) {{0, (xs),(xp) }} - -void mpz_set_si (mpz_t, signed long int); -void mpz_set_ui (mpz_t, unsigned long int); -void mpz_set (mpz_t, const mpz_t); -void mpz_set_d (mpz_t, double); - -void mpz_init_set_si (mpz_t, signed long int); -void mpz_init_set_ui (mpz_t, unsigned long int); -void mpz_init_set (mpz_t, const mpz_t); -void mpz_init_set_d (mpz_t, double); - -size_t mpz_sizeinbase (const mpz_t, int); -char *mpz_get_str (char *, int, const mpz_t); -int mpz_set_str (mpz_t, const char *, int); -int mpz_init_set_str (mpz_t, const char *, int); - -/* This long list taken from gmp.h. */ -/* For reference, "defined(EOF)" cannot be used here. In g++ 2.95.4, - <iostream> defines EOF but not FILE. */ -#if defined (FILE) \ - || defined (H_STDIO) \ - || defined (_H_STDIO) /* AIX */ \ - || defined (_STDIO_H) /* glibc, Sun, SCO */ \ - || defined (_STDIO_H_) /* BSD, OSF */ \ - || defined (__STDIO_H) /* Borland */ \ - || defined (__STDIO_H__) /* IRIX */ \ - || defined (_STDIO_INCLUDED) /* HPUX */ \ - || defined (__dj_include_stdio_h_) /* DJGPP */ \ - || defined (_FILE_DEFINED) /* Microsoft */ \ - || defined (__STDIO__) /* Apple MPW MrC */ \ - || defined (_MSL_STDIO_H) /* Metrowerks */ \ - || defined (_STDIO_H_INCLUDED) /* QNX4 */ \ - || defined (_ISO_STDIO_ISO_H) /* Sun C++ */ \ - || defined (__STDIO_LOADED) /* VMS */ -size_t mpz_out_str (FILE *, int, const mpz_t); -#endif - -void mpz_import (mpz_t, size_t, int, size_t, int, size_t, const void *); -void *mpz_export (void *, size_t *, int, size_t, int, size_t, const mpz_t); - -#if defined (__cplusplus) -} -#endif -#endif /* __MINI_GMP_H__ */ diff --git a/gmp/mini-gmp/tests/Makefile b/gmp/mini-gmp/tests/Makefile deleted file mode 100644 index fe052a02f7..0000000000 --- a/gmp/mini-gmp/tests/Makefile +++ /dev/null @@ -1,60 +0,0 @@ -# Note: Requires GNU make - -# Copyright 2011, 2012, 2014 Free Software Foundation, Inc. -# -# This file is part of the GNU MP Library test suite. -# -# The GNU MP Library test suite is free software; you can redistribute it -# and/or modify it under the terms of the GNU General Public License as -# published by the Free Software Foundation; either version 3 of the License, -# or (at your option) any later version. -# -# The GNU MP Library test suite is distributed in the hope that it will be -# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -# Public License for more details. -# -# You should have received a copy of the GNU General Public License along with -# the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. - -srcdir=. -MINI_GMP_DIR=.. - -CC = gcc -EXTRA_CFLAGS = -O -Wall -g -CFLAGS = $(EXTRA_CFLAGS) -I$(MINI_GMP_DIR) -LDFLAGS = - -LIBS = -lgmp -lm -lmcheck - -CHECK_PROGRAMS = t-add t-sub t-mul t-invert t-div t-div_2exp \ - t-double t-cmp_d t-gcd t-lcm t-import t-comb t-signed \ - t-sqrt t-root t-powm t-logops t-bitops t-scan t-str \ - t-reuse t-aorsmul t-limbs t-cong t-pprime_p - -MISC_OBJS = hex-random.o mini-random.o testutils.o - -all: - -clean: - rm -f *.o $(CHECK_PROGRAMS) - -%: %.c -.c: - -# Keep object files -.PRECIOUS: %.o - -%.o: %.c $(MINI_GMP_DIR)/mini-gmp.h hex-random.h mini-random.h - $(CC) $(CFLAGS) -c $< -o $@ - -testutils.o: $(MINI_GMP_DIR)/mini-gmp.c - -%: %.o $(MISC_OBJS) - $(CC) $(LDFLAGS) $^ $(LIBS) -o $@ - -# Missing tests include: -# mpz_cmp_d, mpz_popcount, mpz_hamdist, mpz_ui_pow_ui - -check: $(CHECK_PROGRAMS) - $(srcdir)/run-tests $(CHECK_PROGRAMS) diff --git a/gmp/mini-gmp/tests/hex-random.c b/gmp/mini-gmp/tests/hex-random.c deleted file mode 100644 index eb8d3f84ec..0000000000 --- a/gmp/mini-gmp/tests/hex-random.c +++ /dev/null @@ -1,434 +0,0 @@ -/* - -Copyright 2011, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <stdio.h> -#include <stdlib.h> - -#include <time.h> -#include <unistd.h> - -#include "gmp.h" - -#include "hex-random.h" - -static gmp_randstate_t state; - -void -hex_random_init (void) -{ - unsigned long seed; - char *env_seed; - - env_seed = getenv("GMP_CHECK_RANDOMIZE"); - if (env_seed && env_seed[0]) - { - seed = strtoul (env_seed, NULL, 0); - if (seed) - printf ("Re-seeding with GMP_CHECK_RANDOMIZE=%lu\n", seed); - else - { - seed = time(NULL) + getpid(); - printf ("Seed GMP_CHECK_RANDOMIZE=%lu (include this in bug reports)\n", seed); - } - } - else - seed = 4711; - - gmp_randinit_default (state); - gmp_randseed_ui (state, seed); -} - -char * -hex_urandomb (unsigned long bits) -{ - char *res; - mpz_t x; - - mpz_init (x); - mpz_urandomb (x, state, bits); - gmp_asprintf (&res, "%Zx", x); - mpz_clear (x); - return res; -} - -char * -hex_rrandomb (unsigned long bits) -{ - char *res; - mpz_t x; - - mpz_init (x); - mpz_rrandomb (x, state, bits); - gmp_asprintf (&res, "%Zx", x); - mpz_clear (x); - return res; -} - -char * -hex_rrandomb_export (void *dst, size_t *countp, - int order, size_t size, int endian, unsigned long bits) -{ - char *res; - mpz_t x; - mpz_init (x); - mpz_rrandomb (x, state, bits); - gmp_asprintf (&res, "%Zx", x); - mpz_export (dst, countp, order, size, endian, 0, x); - mpz_clear (x); - return res; -} - -void hex_random_op2 (enum hex_random_op op, unsigned long maxbits, - char **ap, char **rp) -{ - mpz_t a, r; - unsigned long abits; - unsigned signs; - - mpz_init (a); - mpz_init (r); - - abits = gmp_urandomb_ui (state, 32) % maxbits; - - mpz_rrandomb (a, state, abits); - - signs = gmp_urandomb_ui (state, 1); - if (signs & 1) - mpz_neg (a, a); - - switch (op) - { - default: - abort (); - case OP_SQR: - mpz_mul (r, a, a); - break; - } - - gmp_asprintf (ap, "%Zx", a); - gmp_asprintf (rp, "%Zx", r); - - mpz_clear (a); - mpz_clear (r); -} - -void -hex_random_op3 (enum hex_random_op op, unsigned long maxbits, - char **ap, char **bp, char **rp) -{ - mpz_t a, b, r; - unsigned long abits, bbits; - unsigned signs; - - mpz_init (a); - mpz_init (b); - mpz_init (r); - - abits = gmp_urandomb_ui (state, 32) % maxbits; - bbits = gmp_urandomb_ui (state, 32) % maxbits; - - mpz_rrandomb (a, state, abits); - mpz_rrandomb (b, state, bbits); - - signs = gmp_urandomb_ui (state, 3); - if (signs & 1) - mpz_neg (a, a); - if (signs & 2) - mpz_neg (b, b); - - switch (op) - { - default: - abort (); - case OP_ADD: - mpz_add (r, a, b); - break; - case OP_SUB: - mpz_sub (r, a, b); - break; - case OP_MUL: - mpz_mul (r, a, b); - break; - case OP_GCD: - if (signs & 4) - { - /* Produce a large gcd */ - unsigned long gbits = gmp_urandomb_ui (state, 32) % maxbits; - mpz_rrandomb (r, state, gbits); - mpz_mul (a, a, r); - mpz_mul (b, b, r); - } - mpz_gcd (r, a, b); - break; - case OP_LCM: - if (signs & 4) - { - /* Produce a large gcd */ - unsigned long gbits = gmp_urandomb_ui (state, 32) % maxbits; - mpz_rrandomb (r, state, gbits); - mpz_mul (a, a, r); - mpz_mul (b, b, r); - } - mpz_lcm (r, a, b); - break; - case OP_AND: - mpz_and (r, a, b); - break; - case OP_IOR: - mpz_ior (r, a, b); - break; - case OP_XOR: - mpz_xor (r, a, b); - break; - } - - gmp_asprintf (ap, "%Zx", a); - gmp_asprintf (bp, "%Zx", b); - gmp_asprintf (rp, "%Zx", r); - - mpz_clear (a); - mpz_clear (b); - mpz_clear (r); -} - -void -hex_random_op4 (enum hex_random_op op, unsigned long maxbits, - char **ap, char **bp, char **cp, char **dp) -{ - mpz_t a, b, c, d; - unsigned long abits, bbits; - unsigned signs; - - mpz_init (a); - mpz_init (b); - mpz_init (c); - mpz_init (d); - - if (op == OP_POWM) - { - unsigned long cbits; - abits = gmp_urandomb_ui (state, 32) % maxbits; - bbits = 1 + gmp_urandomb_ui (state, 32) % maxbits; - cbits = 2 + gmp_urandomb_ui (state, 32) % maxbits; - - mpz_rrandomb (a, state, abits); - mpz_rrandomb (b, state, bbits); - mpz_rrandomb (c, state, cbits); - - signs = gmp_urandomb_ui (state, 3); - if (signs & 1) - mpz_neg (a, a); - if (signs & 2) - { - mpz_t g; - - /* If we negate the exponent, must make sure that gcd(a, c) = 1 */ - if (mpz_sgn (a) == 0) - mpz_set_ui (a, 1); - else - { - mpz_init (g); - - for (;;) - { - mpz_gcd (g, a, c); - if (mpz_cmp_ui (g, 1) == 0) - break; - mpz_divexact (a, a, g); - } - mpz_clear (g); - } - mpz_neg (b, b); - } - if (signs & 4) - mpz_neg (c, c); - - mpz_powm (d, a, b, c); - } - else - { - unsigned long qbits; - bbits = 1 + gmp_urandomb_ui (state, 32) % maxbits; - qbits = gmp_urandomb_ui (state, 32) % maxbits; - abits = bbits + qbits; - if (abits > 30) - abits -= 30; - else - abits = 0; - - mpz_rrandomb (a, state, abits); - mpz_rrandomb (b, state, bbits); - - signs = gmp_urandomb_ui (state, 2); - if (signs & 1) - mpz_neg (a, a); - if (signs & 2) - mpz_neg (b, b); - - switch (op) - { - default: - abort (); - case OP_CDIV: - mpz_cdiv_qr (c, d, a, b); - break; - case OP_FDIV: - mpz_fdiv_qr (c, d, a, b); - break; - case OP_TDIV: - mpz_tdiv_qr (c, d, a, b); - break; - } - } - gmp_asprintf (ap, "%Zx", a); - gmp_asprintf (bp, "%Zx", b); - gmp_asprintf (cp, "%Zx", c); - gmp_asprintf (dp, "%Zx", d); - - mpz_clear (a); - mpz_clear (b); - mpz_clear (c); - mpz_clear (d); -} - -void -hex_random_bit_op (enum hex_random_op op, unsigned long maxbits, - char **ap, unsigned long *b, char **rp) -{ - mpz_t a, r; - unsigned long abits, bbits; - unsigned signs; - - mpz_init (a); - mpz_init (r); - - abits = gmp_urandomb_ui (state, 32) % maxbits; - bbits = gmp_urandomb_ui (state, 32) % (maxbits + 100); - - mpz_rrandomb (a, state, abits); - - signs = gmp_urandomb_ui (state, 1); - if (signs & 1) - mpz_neg (a, a); - - switch (op) - { - default: - abort (); - - case OP_SETBIT: - mpz_set (r, a); - mpz_setbit (r, bbits); - break; - case OP_CLRBIT: - mpz_set (r, a); - mpz_clrbit (r, bbits); - break; - case OP_COMBIT: - mpz_set (r, a); - mpz_combit (r, bbits); - break; - case OP_CDIV_Q_2: - mpz_cdiv_q_2exp (r, a, bbits); - break; - case OP_CDIV_R_2: - mpz_cdiv_r_2exp (r, a, bbits); - break; - case OP_FDIV_Q_2: - mpz_fdiv_q_2exp (r, a, bbits); - break; - case OP_FDIV_R_2: - mpz_fdiv_r_2exp (r, a, bbits); - break; - case OP_TDIV_Q_2: - mpz_tdiv_q_2exp (r, a, bbits); - break; - case OP_TDIV_R_2: - mpz_tdiv_r_2exp (r, a, bbits); - break; - } - - gmp_asprintf (ap, "%Zx", a); - *b = bbits; - gmp_asprintf (rp, "%Zx", r); - - mpz_clear (a); - mpz_clear (r); -} - -void -hex_random_scan_op (enum hex_random_op op, unsigned long maxbits, - char **ap, unsigned long *b, unsigned long *r) -{ - mpz_t a; - unsigned long abits, bbits; - unsigned signs; - - mpz_init (a); - - abits = gmp_urandomb_ui (state, 32) % maxbits; - bbits = gmp_urandomb_ui (state, 32) % (maxbits + 100); - - mpz_rrandomb (a, state, abits); - - signs = gmp_urandomb_ui (state, 1); - if (signs & 1) - mpz_neg (a, a); - - switch (op) - { - default: - abort (); - - case OP_SCAN0: - *r = mpz_scan0 (a, bbits); - break; - case OP_SCAN1: - *r = mpz_scan1 (a, bbits); - break; - } - gmp_asprintf (ap, "%Zx", a); - *b = bbits; - - mpz_clear (a); -} - -void -hex_random_str_op (unsigned long maxbits, - int base, char **ap, char **rp) -{ - mpz_t a; - unsigned long abits; - unsigned signs; - - mpz_init (a); - - abits = gmp_urandomb_ui (state, 32) % maxbits; - - mpz_rrandomb (a, state, abits); - - signs = gmp_urandomb_ui (state, 2); - if (signs & 1) - mpz_neg (a, a); - - *ap = mpz_get_str (NULL, 16, a); - *rp = mpz_get_str (NULL, base, a); - - mpz_clear (a); -} diff --git a/gmp/mini-gmp/tests/hex-random.h b/gmp/mini-gmp/tests/hex-random.h deleted file mode 100644 index 7a3913a0bc..0000000000 --- a/gmp/mini-gmp/tests/hex-random.h +++ /dev/null @@ -1,50 +0,0 @@ -/* - -Copyright 2011, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -enum hex_random_op - { - OP_ADD, OP_SUB, OP_MUL, OP_SQR, - OP_CDIV, OP_FDIV, OP_TDIV, - OP_CDIV_Q_2, OP_CDIV_R_2, - OP_FDIV_Q_2, OP_FDIV_R_2, - OP_TDIV_Q_2, OP_TDIV_R_2, - OP_GCD, OP_LCM, OP_POWM, OP_AND, OP_IOR, OP_XOR, - OP_SETBIT, OP_CLRBIT, OP_COMBIT, - OP_SCAN0, OP_SCAN1, - }; - -void hex_random_init (void); -char *hex_urandomb (unsigned long bits); -char *hex_rrandomb (unsigned long bits); -char *hex_rrandomb_export (void *dst, size_t *countp, - int order, size_t size, int endian, - unsigned long bits); - -void hex_random_op2 (enum hex_random_op op, unsigned long maxbits, - char **ap, char **rp); -void hex_random_op3 (enum hex_random_op op, unsigned long maxbits, - char **ap, char **bp, char **rp); -void hex_random_op4 (enum hex_random_op op, unsigned long maxbits, - char **ap, char **bp, char **rp, char **qp); -void hex_random_bit_op (enum hex_random_op op, unsigned long maxbits, - char **ap, unsigned long *b, char **rp); -void hex_random_scan_op (enum hex_random_op op, unsigned long maxbits, - char **ap, unsigned long *b, unsigned long *r); -void hex_random_str_op (unsigned long maxbits, - int base, char **ap, char **rp); diff --git a/gmp/mini-gmp/tests/mini-random.c b/gmp/mini-gmp/tests/mini-random.c deleted file mode 100644 index 300d386b2c..0000000000 --- a/gmp/mini-gmp/tests/mini-random.c +++ /dev/null @@ -1,142 +0,0 @@ -/* - -Copyright 2011, 2013, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <stdio.h> -#include <stdlib.h> - -#include "mini-random.h" - -static void -set_str (mpz_t r, const char *s) -{ - if (mpz_set_str (r, s, 16) != 0) - { - fprintf (stderr, "mpz_set_str failed on input %s\n", s); - abort (); - } -} - -void -mini_urandomb (mpz_t r, unsigned long bits) -{ - char *s; - s = hex_urandomb (bits); - set_str (r, s); - free (s); -} - -void -mini_rrandomb (mpz_t r, unsigned long bits) -{ - char *s; - s = hex_rrandomb (bits); - set_str (r, s); - free (s); -} - -void -mini_rrandomb_export (mpz_t r, void *dst, size_t *countp, - int order, size_t size, int endian, unsigned long bits) -{ - char *s; - s = hex_rrandomb_export (dst, countp, order, size, endian, bits); - set_str (r, s); - free (s); -} - -void -mini_random_op2 (enum hex_random_op op, unsigned long maxbits, - mpz_t a, mpz_t r) -{ - char *ap; - char *rp; - - hex_random_op2 (op, maxbits, &ap, &rp); - set_str (a, ap); - set_str (r, rp); - - free (ap); - free (rp); -} - -void -mini_random_op3 (enum hex_random_op op, unsigned long maxbits, - mpz_t a, mpz_t b, mpz_t r) -{ - char *ap; - char *bp; - char *rp; - - hex_random_op3 (op, maxbits, &ap, &bp, &rp); - set_str (a, ap); - set_str (b, bp); - set_str (r, rp); - - free (ap); - free (bp); - free (rp); -} - -void -mini_random_op4 (enum hex_random_op op, unsigned long maxbits, - mpz_t a, mpz_t b, mpz_t c, mpz_t d) -{ - char *ap; - char *bp; - char *cp; - char *dp; - - hex_random_op4 (op, maxbits, &ap, &bp, &cp, &dp); - set_str (a, ap); - set_str (b, bp); - set_str (c, cp); - set_str (d, dp); - - free (ap); - free (bp); - free (cp); - free (dp); -} - -void -mini_random_bit_op (enum hex_random_op op, unsigned long maxbits, - mpz_t a, mp_bitcnt_t *b, mpz_t r) -{ - char *ap; - char *rp; - - hex_random_bit_op (op, maxbits, &ap, b, &rp); - set_str (a, ap); - set_str (r, rp); - - free (ap); - free (rp); -} - -void -mini_random_scan_op (enum hex_random_op op, unsigned long maxbits, - mpz_t a, mp_bitcnt_t *b, mp_bitcnt_t *r) -{ - char *ap; - - hex_random_scan_op (op, maxbits, &ap, b, r); - set_str (a, ap); - - free (ap); -} diff --git a/gmp/mini-gmp/tests/mini-random.h b/gmp/mini-gmp/tests/mini-random.h deleted file mode 100644 index f36c56fc82..0000000000 --- a/gmp/mini-gmp/tests/mini-random.h +++ /dev/null @@ -1,33 +0,0 @@ -/* - -Copyright 2011, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include "mini-gmp.h" -#include "hex-random.h" - -void mini_urandomb (mpz_t, unsigned long); -void mini_rrandomb (mpz_t, unsigned long); -void mini_rrandomb_export (mpz_t r, void *dst, size_t *countp, - int order, size_t size, int endian, - unsigned long bits); - -void mini_random_op2 (enum hex_random_op, unsigned long, mpz_t, mpz_t); -void mini_random_op3 (enum hex_random_op, unsigned long, mpz_t, mpz_t, mpz_t); -void mini_random_op4 (enum hex_random_op, unsigned long, mpz_t, mpz_t, mpz_t, mpz_t); -void mini_random_scan_op (enum hex_random_op, unsigned long, mpz_t, mp_bitcnt_t *, mp_bitcnt_t *); -void mini_random_bit_op (enum hex_random_op, unsigned long, mpz_t, mp_bitcnt_t *, mpz_t); diff --git a/gmp/mini-gmp/tests/run-tests b/gmp/mini-gmp/tests/run-tests deleted file mode 100755 index 5fc2952d76..0000000000 --- a/gmp/mini-gmp/tests/run-tests +++ /dev/null @@ -1,123 +0,0 @@ -#! /bin/sh - -# Copyright (C) 2000-2002, 2004, 2005, 2011, 2012 Niels Möller -# -# This program is free software; you can redistribute it and/or modify -# it under the terms of the GNU General Public License as published by -# the Free Software Foundation; either version 2 of the License, or -# (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License along -# with this program; if not, write to the Free Software Foundation, Inc., -# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - -failed=0 -all=0 - -debug='no' -testflags='' - -if [ -z "$srcdir" ] ; then - srcdir=`pwd` -fi - -export srcdir - -# When used in make rules, we sometimes get the filenames VPATH -# expanded, but usually not. -find_program () { - case "$1" in - */*) - echo "$1" - ;; - *) - if [ -x "$1" ] ; then - echo "./$1" - else - echo "$srcdir/$1" - fi - ;; - esac -} - -env_program () { - if [ -x "$1" ] ; then - if "$1"; then : ; else - echo FAIL: $1 - exit 1 - fi - fi -} - -test_program () { - testname=`basename "$1" .exe` - testname=`basename "$testname" -test` - if [ -z "$EMULATOR" ] || head -1 "$1" | grep '^#!' > /dev/null; then - "$1" $testflags - else - $EMULATOR "$1" $testflags - fi - case "$?" in - 0) - echo PASS: $testname - all=`expr $all + 1` - ;; - 77) - echo SKIP: $testname - ;; - *) - echo FAIL: $testname - failed=`expr $failed + 1` - all=`expr $all + 1` - ;; - esac -} - -env_program `find_program setup-env` - -while test $# != 0 -do - case "$1" in - --debug) - debug=yes - ;; - -v) - testflags='-v' - ;; - -*) - echo >&2 'Unknown option `'"$1'" - exit 1 - ;; - *) - break - ;; - esac - shift -done - -if [ $# -eq 0 ] ; then - for f in *-test; do test_program "./$f"; done -else - for f in "$@" ; do test_program `find_program "$f"`; done -fi - -if [ $failed -eq 0 ] ; then - banner="All $all tests passed" -else - banner="$failed of $all tests failed" -fi -dashes=`echo "$banner" | sed s/./=/g` -echo "$dashes" -echo "$banner" -echo "$dashes" - -if [ "x$debug" = xno ] ; then - env_program `find_program teardown-env` -fi - -[ "$failed" -eq 0 ] diff --git a/gmp/mini-gmp/tests/t-add.c b/gmp/mini-gmp/tests/t-add.c deleted file mode 100644 index 0a093efd90..0000000000 --- a/gmp/mini-gmp/tests/t-add.c +++ /dev/null @@ -1,57 +0,0 @@ -/* - -Copyright 2012, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, b, res, ref; - - mpz_init (a); - mpz_init (b); - mpz_init (res); - mpz_init (ref); - - for (i = 0; i < COUNT; i++) - { - mini_random_op3 (OP_ADD, MAXBITS, a, b, ref); - mpz_add (res, a, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_add failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - } - mpz_clear (a); - mpz_clear (b); - mpz_clear (res); - mpz_clear (ref); -} diff --git a/gmp/mini-gmp/tests/t-aorsmul.c b/gmp/mini-gmp/tests/t-aorsmul.c deleted file mode 100644 index eb275a8088..0000000000 --- a/gmp/mini-gmp/tests/t-aorsmul.c +++ /dev/null @@ -1,77 +0,0 @@ -/* - -Copyright 2012, 2014, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> -#include <string.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -#define GMP_LIMB_BITS (sizeof(mp_limb_t) * CHAR_BIT) -#define MAXLIMBS ((MAXBITS + GMP_LIMB_BITS - 1) / GMP_LIMB_BITS) - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, b, res, ref; - - mpz_init (a); - mpz_init (b); - mpz_init_set_ui (res, 5); - mpz_init (ref); - - for (i = 0; i < COUNT; i++) - { - mini_random_op3 (OP_MUL, MAXBITS, a, b, ref); - if (i & 1) { - mpz_add (ref, ref, res); - if (mpz_fits_ulong_p (b)) - mpz_addmul_ui (res, a, mpz_get_ui (b)); - else - mpz_addmul (res, a, b); - } else { - mpz_sub (ref, res, ref); - if (mpz_fits_ulong_p (b)) - mpz_submul_ui (res, a, mpz_get_ui (b)); - else - mpz_submul (res, a, b); - } - if (mpz_cmp (res, ref)) - { - if (i & 1) - fprintf (stderr, "mpz_addmul failed:\n"); - else - fprintf (stderr, "mpz_submul failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - } - mpz_clear (a); - mpz_clear (b); - mpz_clear (res); - mpz_clear (ref); -} diff --git a/gmp/mini-gmp/tests/t-bitops.c b/gmp/mini-gmp/tests/t-bitops.c deleted file mode 100644 index 7e1688e662..0000000000 --- a/gmp/mini-gmp/tests/t-bitops.c +++ /dev/null @@ -1,103 +0,0 @@ -/* - -Copyright 2012, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, res, ref; - mp_bitcnt_t b; - - mpz_init (a); - mpz_init (res); - mpz_init (ref); - - for (i = 0; i < COUNT; i++) - { - mini_random_bit_op (OP_SETBIT, MAXBITS, a, &b, ref); - mpz_set (res, a); - mpz_setbit (res, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_setbit failed:\n"); - dump ("a", a); - fprintf (stderr, "b: %lu\n", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - if (!mpz_tstbit (res, b)) - { - fprintf (stderr, "mpz_tstbit failed (after mpz_setbit):\n"); - dump ("res", a); - fprintf (stderr, "b: %lu\n", b); - abort (); - } - mini_random_bit_op (OP_CLRBIT, MAXBITS, a, &b, ref); - mpz_set (res, a); - mpz_clrbit (res, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_clrbit failed:\n"); - dump ("a", a); - fprintf (stderr, "b: %lu\n", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - if (mpz_tstbit (res, b)) - { - fprintf (stderr, "mpz_tstbit failed (after mpz_clrbit):\n"); - dump ("res", a); - fprintf (stderr, "b: %lu\n", b); - abort (); - } - mini_random_bit_op (OP_COMBIT, MAXBITS, a, &b, ref); - mpz_set (res, a); - mpz_combit (res, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_combit failed:\n"); - dump ("a", a); - fprintf (stderr, "b: %lu\n", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - if (mpz_tstbit (res, b) == mpz_tstbit (a, b)) - { - fprintf (stderr, "mpz_tstbit failed (after mpz_combit):\n"); - dump ("res", a); - fprintf (stderr, "b: %lu\n", b); - abort (); - } - } - mpz_clear (a); - mpz_clear (res); - mpz_clear (ref); -} diff --git a/gmp/mini-gmp/tests/t-cmp_d.c b/gmp/mini-gmp/tests/t-cmp_d.c deleted file mode 100644 index 4eab278527..0000000000 --- a/gmp/mini-gmp/tests/t-cmp_d.c +++ /dev/null @@ -1,283 +0,0 @@ -/* Test mpz_cmp_d and mpz_cmpabs_d. - -Copyright 2001-2003, 2005, 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <math.h> - -#include "testutils.h" - -/* FIXME: Not sure if the tests here are exhaustive. Ought to try to get - each possible exit from mpz_cmp_d (and mpz_cmpabs_d) exercised. */ - - -#define SGN(n) ((n) > 0 ? 1 : (n) < 0 ? -1 : 0) - - -void -check_one (const char *name, mpz_srcptr x, double y, int cmp, int cmpabs) -{ - int got; - - got = mpz_cmp_d (x, y); - if (SGN(got) != cmp) - { - int i; - printf ("mpz_cmp_d wrong (from %s)\n", name); - printf (" got %d\n", got); - printf (" want %d\n", cmp); - fail: - printf (" x="); - mpz_out_str (stdout, 10, x); - printf ("\n y %g\n", y); - printf (" x=0x"); - mpz_out_str (stdout, -16, x); - printf ("\n y %g\n", y); - printf (" y"); - for (i = 0; i < sizeof(y); i++) - printf (" %02X", (unsigned) ((unsigned char *) &y)[i]); - printf ("\n"); - abort (); - } - - got = mpz_cmpabs_d (x, y); - if (SGN(got) != cmpabs) - { - printf ("mpz_cmpabs_d wrong\n"); - printf (" got %d\n", got); - printf (" want %d\n", cmpabs); - goto fail; - } -} - -void -check_data (void) -{ - static const struct { - const char *x; - double y; - int cmp, cmpabs; - - } data[] = { - - { "0", 0.0, 0, 0 }, - - { "1", 0.0, 1, 1 }, - { "-1", 0.0, -1, 1 }, - - { "1", 0.5, 1, 1 }, - { "-1", -0.5, -1, 1 }, - - { "0", 1.0, -1, -1 }, - { "0", -1.0, 1, -1 }, - - { "0x1000000000000000000000000000000000000000000000000", 1.0, 1, 1 }, - { "-0x1000000000000000000000000000000000000000000000000", 1.0, -1, 1 }, - - { "0", 1e100, -1, -1 }, - { "0", -1e100, 1, -1 }, - - { "2", 1.5, 1, 1 }, - { "2", -1.5, 1, 1 }, - { "-2", 1.5, -1, 1 }, - { "-2", -1.5, -1, 1 }, - }; - - mpz_t x; - int i; - - mpz_init (x); - - for (i = 0; i < numberof (data); i++) - { - mpz_set_str_or_abort (x, data[i].x, 0); - check_one ("check_data", x, data[i].y, data[i].cmp, data[i].cmpabs); - } - - mpz_clear (x); -} - - -/* Equality of integers with up to 53 bits */ -void -check_onebits (void) -{ - mpz_t x, x2; - double y; - int i; - - mpz_init_set_ui (x, 0L); - mpz_init (x2); - - for (i = 0; i < 512; i++) - { - mpz_mul_2exp (x, x, 1); - mpz_add_ui (x, x, 1L); - - y = mpz_get_d (x); - mpz_set_d (x2, y); - - /* stop if any truncation is occurring */ - if (mpz_cmp (x, x2) != 0) - break; - - check_one ("check_onebits", x, y, 0, 0); - check_one ("check_onebits", x, -y, 1, 0); - mpz_neg (x, x); - check_one ("check_onebits", x, y, -1, 0); - check_one ("check_onebits", x, -y, 0, 0); - mpz_neg (x, x); - } - - mpz_clear (x); - mpz_clear (x2); -} - - -/* With the mpz differing by 1, in a limb position possibly below the double */ -void -check_low_z_one (void) -{ - mpz_t x; - double y; - unsigned long i; - - mpz_init (x); - - /* FIXME: It'd be better to base this on the float format. */ -#if defined (__vax) || defined (__vax__) -#define LIM 127 /* vax fp numbers have limited range */ -#else -#define LIM 512 -#endif - - for (i = 1; i < LIM; i++) - { - mpz_set_ui (x, 1L); - mpz_mul_2exp (x, x, i); - y = mpz_get_d (x); - - check_one ("check_low_z_one", x, y, 0, 0); - check_one ("check_low_z_one", x, -y, 1, 0); - mpz_neg (x, x); - check_one ("check_low_z_one", x, y, -1, 0); - check_one ("check_low_z_one", x, -y, 0, 0); - mpz_neg (x, x); - - mpz_sub_ui (x, x, 1); - - check_one ("check_low_z_one", x, y, -1, -1); - check_one ("check_low_z_one", x, -y, 1, -1); - mpz_neg (x, x); - check_one ("check_low_z_one", x, y, -1, -1); - check_one ("check_low_z_one", x, -y, 1, -1); - mpz_neg (x, x); - - mpz_add_ui (x, x, 2); - - check_one ("check_low_z_one", x, y, 1, 1); - check_one ("check_low_z_one", x, -y, 1, 1); - mpz_neg (x, x); - check_one ("check_low_z_one", x, y, -1, 1); - check_one ("check_low_z_one", x, -y, -1, 1); - mpz_neg (x, x); - } - - mpz_clear (x); -} - -/* Comparing 1 and 1+2^-n. "y" is volatile to make gcc store and fetch it, - which forces it to a 64-bit double, whereas on x86 it would otherwise - remain on the float stack as an 80-bit long double. */ -void -check_one_2exp (void) -{ - double e; - mpz_t x; - volatile double y; - int i; - - mpz_init (x); - - e = 1.0; - for (i = 0; i < 128; i++) - { - e /= 2.0; - y = 1.0 + e; - if (y == 1.0) - break; - - mpz_set_ui (x, 1L); - check_one ("check_one_2exp", x, y, -1, -1); - check_one ("check_one_2exp", x, -y, 1, -1); - - mpz_set_si (x, -1L); - check_one ("check_one_2exp", x, y, -1, -1); - check_one ("check_one_2exp", x, -y, 1, -1); - } - - mpz_clear (x); -} - -void -check_infinity (void) -{ - mpz_t x; - double y = HUGE_VAL; - if (y != 2*y) - return; - - mpz_init (x); - - /* 0 cmp inf */ - mpz_set_ui (x, 0L); - check_one ("check_infinity", x, y, -1, -1); - check_one ("check_infinity", x, -y, 1, -1); - - /* 123 cmp inf */ - mpz_set_ui (x, 123L); - check_one ("check_infinity", x, y, -1, -1); - check_one ("check_infinity", x, -y, 1, -1); - - /* -123 cmp inf */ - mpz_set_si (x, -123L); - check_one ("check_infinity", x, y, -1, -1); - check_one ("check_infinity", x, -y, 1, -1); - - /* 2^5000 cmp inf */ - mpz_set_ui (x, 1L); - mpz_mul_2exp (x, x, 5000L); - check_one ("check_infinity", x, y, -1, -1); - check_one ("check_infinity", x, -y, 1, -1); - - /* -2^5000 cmp inf */ - mpz_neg (x, x); - check_one ("check_infinity", x, y, -1, -1); - check_one ("check_infinity", x, -y, 1, -1); - - mpz_clear (x); -} - -void -testmain (int argc, char *argv[]) -{ - check_data (); - check_onebits (); - check_low_z_one (); - check_one_2exp (); - check_infinity (); -} diff --git a/gmp/mini-gmp/tests/t-comb.c b/gmp/mini-gmp/tests/t-comb.c deleted file mode 100644 index 31ee5a6ad6..0000000000 --- a/gmp/mini-gmp/tests/t-comb.c +++ /dev/null @@ -1,164 +0,0 @@ -/* Exercise mpz_fac_ui and mpz_bin_uiui. - -Copyright 2000-2002, 2012, 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <stdio.h> -#include <stdlib.h> - -#include "testutils.h" - -/* Usage: t-fac_ui [x|num] - - With no arguments testing goes up to the initial value of "limit" below. - With a number argument tests are carried that far, or with a literal "x" - tests are continued without limit (this being meant only for development - purposes). */ - -void -try_mpz_bin_uiui (mpz_srcptr want, unsigned long n, unsigned long k) -{ - mpz_t got; - - mpz_init (got); - mpz_bin_uiui (got, n, k); - if (mpz_cmp (got, want) != 0) - { - printf ("mpz_bin_uiui wrong\n"); - printf (" n=%lu\n", n); - printf (" k=%lu\n", k); - printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n"); - printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n"); - abort(); - } - mpz_clear (got); -} - -/* Test all bin(n,k) cases, with 0 <= k <= n + 1 <= count. */ -void -bin_smallexaustive (unsigned int count) -{ - mpz_t want; - unsigned long n, k; - - mpz_init (want); - - for (n = 0; n < count; n++) - { - mpz_set_ui (want, 1); - for (k = 0; k <= n; k++) - { - try_mpz_bin_uiui (want, n, k); - mpz_mul_ui (want, want, n - k); - mpz_fdiv_q_ui (want, want, k + 1); - } - try_mpz_bin_uiui (want, n, k); - } - - mpz_clear (want); -} - -/* Test all fac(n) cases, with 0 <= n <= limit. */ -void -fac_smallexaustive (unsigned int limit) -{ - mpz_t f, r; - unsigned long n; - mpz_init_set_si (f, 1); /* 0! = 1 */ - mpz_init (r); - - for (n = 0; n < limit; n++) - { - mpz_fac_ui (r, n); - - if (mpz_cmp (f, r) != 0) - { - printf ("mpz_fac_ui(%lu) wrong\n", n); - printf (" got "); mpz_out_str (stdout, 10, r); printf("\n"); - printf (" want "); mpz_out_str (stdout, 10, f); printf("\n"); - abort (); - } - - mpz_mul_ui (f, f, n+1); /* (n+1)! = n! * (n+1) */ - } - - mpz_clear (f); - mpz_clear (r); -} - -void checkWilson (mpz_t f, unsigned long n) -{ - unsigned long m; - - mpz_fac_ui (f, n - 1); - m = mpz_fdiv_ui (f, n); - if ( m != n - 1) - { - printf ("mpz_fac_ui(%lu) wrong\n", n - 1); - printf (" Wilson's theorem not verified: got %lu, expected %lu.\n",m ,n - 1); - abort (); - } -} - -void -checkprimes (unsigned long p1, unsigned long p2, unsigned long p3) -{ - mpz_t b, f; - - if (p1 - 1 != p2 - 1 + p3 - 1) - { - printf ("checkprimes(%lu, %lu, %lu) wrong\n", p1, p2, p3); - printf (" %lu - 1 != %lu - 1 + %lu - 1 \n", p1, p2, p3); - abort (); - } - - mpz_init (b); - mpz_init (f); - - checkWilson (b, p1); /* b = (p1-1)! */ - checkWilson (f, p2); /* f = (p2-1)! */ - mpz_divexact (b, b, f); - checkWilson (f, p3); /* f = (p3-1)! */ - mpz_divexact (b, b, f); /* b = (p1-1)!/((p2-1)!(p3-1)!) */ - mpz_bin_uiui (f, p1 - 1, p2 - 1); - if (mpz_cmp (f, b) != 0) - { - printf ("checkprimes(%lu, %lu, %lu) wrong\n", p1, p2, p3); - printf (" got "); mpz_out_str (stdout, 10, b); printf("\n"); - printf (" want "); mpz_out_str (stdout, 10, f); printf("\n"); - abort (); - } - - mpz_clear (b); - mpz_clear (f); - -} - -void -testmain (int argc, char *argv[]) -{ - unsigned long limit = 128; - - if (argc > 1 && argv[1][0] == 'x') - limit = ~ limit; - else if (argc > 1) - limit = atoi (argv[1]); - - checkprimes(1009, 733, 277); - fac_smallexaustive (limit); - bin_smallexaustive (limit); -} diff --git a/gmp/mini-gmp/tests/t-cong.c b/gmp/mini-gmp/tests/t-cong.c deleted file mode 100644 index 8ddfe9bf46..0000000000 --- a/gmp/mini-gmp/tests/t-cong.c +++ /dev/null @@ -1,212 +0,0 @@ -/* test mpz_congruent_p - -Copyright 2001, 2002, 2012, 2014 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include "testutils.h" - -#define MPZ_SRCPTR_SWAP(x, y) \ - do { \ - mpz_srcptr __mpz_srcptr_swap__tmp = (x); \ - (x) = (y); \ - (y) = __mpz_srcptr_swap__tmp; \ - } while (0) - -void -check_one (mpz_srcptr a, mpz_srcptr c, mpz_srcptr d, int want) -{ - int got; - int swap; - - for (swap = 0; swap <= 1; swap++) - { - got = (mpz_congruent_p (a, c, d) != 0); - if (want != got) - { - printf ("mpz_congruent_p wrong\n"); - printf (" expected %d got %d\n", want, got); - dump (" a", a); - dump (" c", c); - dump (" d", d); - abort (); - } - -#if 0 - if (mpz_fits_ulong_p (c) && mpz_fits_ulong_p (d)) - { - unsigned long uc = mpz_get_ui (c); - unsigned long ud = mpz_get_ui (d); - got = (mpz_congruent_ui_p (a, uc, ud) != 0); - if (want != got) - { - printf ("mpz_congruent_ui_p wrong\n"); - printf (" expected %d got %d\n", want, got); - dump (" a", a); - printf (" c=%lu\n", uc); - printf (" d=%lu\n", ud); - abort (); - } - } -#endif - MPZ_SRCPTR_SWAP (a, c); - } -} - - -void -check_data (void) -{ - static const struct { - const char *a; - const char *c; - const char *d; - int want; - - } data[] = { - - /* strict equality mod 0 */ - { "0", "0", "0", 1 }, - { "11", "11", "0", 1 }, - { "3", "11", "0", 0 }, - - /* anything congruent mod 1 */ - { "0", "0", "1", 1 }, - { "1", "0", "1", 1 }, - { "0", "1", "1", 1 }, - { "123", "456", "1", 1 }, - { "0x123456789123456789", "0x987654321987654321", "1", 1 }, - - /* csize==1, dsize==2 changing to 1 after stripping 2s */ - { "0x3333333333333333", "0x33333333", - "0x180000000", 1 }, - { "0x33333333333333333333333333333333", "0x3333333333333333", - "0x18000000000000000", 1 }, - - /* another dsize==2 becoming 1, with opposite signs this time */ - { "0x444444441", - "-0x22222221F", - "0x333333330", 1 }, - { "0x44444444444444441", - "-0x2222222222222221F", - "0x33333333333333330", 1 }, - }; - - mpz_t a, c, d; - int i; - - mpz_init (a); - mpz_init (c); - mpz_init (d); - - for (i = 0; i < numberof (data); i++) - { - mpz_set_str_or_abort (a, data[i].a, 0); - mpz_set_str_or_abort (c, data[i].c, 0); - mpz_set_str_or_abort (d, data[i].d, 0); - check_one (a, c, d, data[i].want); - } - - mpz_clear (a); - mpz_clear (c); - mpz_clear (d); -} - - -void -check_random (int argc, char *argv[]) -{ - mpz_t a, c, d, ra, rc; - int i; - int want; - int reps = 10000; - mpz_t bs; - unsigned long size_range, size; - - if (argc >= 2) - reps = atoi (argv[1]); - - mpz_init (bs); - - mpz_init (a); - mpz_init (c); - mpz_init (d); - mpz_init (ra); - mpz_init (rc); - - for (i = 0; i < reps; i++) - { - mini_urandomb (bs, 32); - size_range = mpz_get_ui (bs) % 13 + 1; /* 0..8192 bit operands */ - - mini_urandomb (bs, size_range); - size = mpz_get_ui (bs); - mini_rrandomb (a, size); - - mini_urandomb (bs, 32); - size_range = mpz_get_ui (bs) % 13 + 1; /* 0..8192 bit operands */ - - mini_urandomb (bs, size_range); - size = mpz_get_ui (bs); - mini_rrandomb (c, size); - - do - { - mini_urandomb (bs, 32); - size_range = mpz_get_ui (bs) % 13 + 1; /* 0..8192 bit operands */ - - mini_urandomb (bs, size_range); - size = mpz_get_ui (bs); - mini_rrandomb (d, size); - } - while (mpz_sgn(d) == 0); - - mini_urandomb (bs, 3); - if (mpz_tstbit (bs, 0)) - mpz_neg (a, a); - if (mpz_tstbit (bs, 1)) - mpz_neg (c, c); - if (mpz_tstbit (bs, 2)) - mpz_neg (d, d); - - mpz_fdiv_r (ra, a, d); - mpz_fdiv_r (rc, c, d); - - want = (mpz_cmp (ra, rc) == 0); - check_one (a, c, d, want); - - mpz_sub (ra, ra, rc); - mpz_sub (a, a, ra); - check_one (a, c, d, 1); - - } - - mpz_clear (bs); - - mpz_clear (a); - mpz_clear (c); - mpz_clear (d); - mpz_clear (ra); - mpz_clear (rc); -} - - -void -testmain (int argc, char *argv[]) -{ - check_data (); - check_random (argc, argv); -} diff --git a/gmp/mini-gmp/tests/t-div.c b/gmp/mini-gmp/tests/t-div.c deleted file mode 100644 index a114a0f180..0000000000 --- a/gmp/mini-gmp/tests/t-div.c +++ /dev/null @@ -1,254 +0,0 @@ -/* - -Copyright 2012, 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <assert.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -typedef void div_qr_func (mpz_t, mpz_t, const mpz_t, const mpz_t); -typedef unsigned long div_qr_ui_func (mpz_t, mpz_t, const mpz_t, unsigned long); -typedef void div_func (mpz_t, const mpz_t, const mpz_t); -typedef unsigned long div_x_ui_func (mpz_t, const mpz_t, unsigned long); -typedef unsigned long div_ui_func (const mpz_t, unsigned long); - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, b, q, r, rq, rr; - int div_p; - - mpz_init (a); - mpz_init (b); - mpz_init (r); - mpz_init (q); - mpz_init (rr); - mpz_init (rq); - - for (i = 0; i < COUNT; i++) - { - unsigned j; - for (j = 0; j < 3; j++) - { - static const enum hex_random_op ops[3] = { OP_CDIV, OP_FDIV, OP_TDIV }; - static const char name[3] = { 'c', 'f', 't'}; - static div_qr_func * const div_qr [3] = - { - mpz_cdiv_qr, mpz_fdiv_qr, mpz_tdiv_qr - }; - static div_qr_ui_func *div_qr_ui[3] = - { - mpz_cdiv_qr_ui, mpz_fdiv_qr_ui, mpz_tdiv_qr_ui - }; - static div_func * const div_q [3] = - { - mpz_cdiv_q, mpz_fdiv_q, mpz_tdiv_q - }; - static div_x_ui_func *div_q_ui[3] = - { - mpz_cdiv_q_ui, mpz_fdiv_q_ui, mpz_tdiv_q_ui - }; - static div_func * const div_r [3] = - { - mpz_cdiv_r, mpz_fdiv_r, mpz_tdiv_r - }; - static div_x_ui_func *div_r_ui[3] = - { - mpz_cdiv_r_ui, mpz_fdiv_r_ui, mpz_tdiv_r_ui - }; - static div_ui_func *div_ui[3] = - { - mpz_cdiv_ui, mpz_fdiv_ui, mpz_tdiv_ui - }; - - mini_random_op4 (ops[j], MAXBITS, a, b, rq, rr); - div_qr[j] (q, r, a, b); - if (mpz_cmp (r, rr) || mpz_cmp (q, rq)) - { - fprintf (stderr, "mpz_%cdiv_qr failed:\n", name[j]); - dump ("a", a); - dump ("b", b); - dump ("r ", r); - dump ("rref", rr); - dump ("q ", q); - dump ("qref", rq); - abort (); - } - mpz_set_si (q, -5); - div_q[j] (q, a, b); - if (mpz_cmp (q, rq)) - { - fprintf (stderr, "mpz_%cdiv_q failed:\n", name[j]); - dump ("a", a); - dump ("b", b); - dump ("q ", q); - dump ("qref", rq); - abort (); - } - mpz_set_ui (r, ~5); - div_r[j] (r, a, b); - if (mpz_cmp (r, rr)) - { - fprintf (stderr, "mpz_%cdiv_r failed:\n", name[j]); - dump ("a", a); - dump ("b", b); - dump ("r ", r); - dump ("rref", rr); - abort (); - } - - if (j == 0) /* do this once, not for all roundings */ - { - div_p = mpz_divisible_p (a, b); - if ((mpz_sgn (r) == 0) ^ (div_p != 0)) - { - fprintf (stderr, "mpz_divisible_p failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r ", r); - abort (); - } - } - - if (j == 0 && mpz_sgn (b) < 0) /* ceil, negative divisor */ - { - mpz_mod (r, a, b); - if (mpz_cmp (r, rr)) - { - fprintf (stderr, "mpz_mod failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r ", r); - dump ("rref", rr); - abort (); - } - } - - if (j == 1 && mpz_sgn (b) > 0) /* floor, positive divisor */ - { - mpz_mod (r, a, b); - if (mpz_cmp (r, rr)) - { - fprintf (stderr, "mpz_mod failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r ", r); - dump ("rref", rr); - abort (); - } - } - - if (mpz_fits_ulong_p (b)) - { - mp_limb_t rl; - - rl = div_qr_ui[j] (q, r, a, mpz_get_ui (b)); - if (rl != mpz_get_ui (rr) - || mpz_cmp (r, rr) || mpz_cmp (q, rq)) - { - fprintf (stderr, "mpz_%cdiv_qr_ui failed:\n", name[j]); - dump ("a", a); - dump ("b", b); - fprintf(stderr, "rl = %lx\n", rl); - dump ("r ", r); - dump ("rref", rr); - dump ("q ", q); - dump ("qref", rq); - abort (); - } - - mpz_set_si (q, 3); - rl = div_q_ui[j] (q, a, mpz_get_ui (b)); - if (rl != mpz_get_ui (rr) || mpz_cmp (q, rq)) - { - fprintf (stderr, "mpz_%cdiv_q_ui failed:\n", name[j]); - dump ("a", a); - dump ("b", b); - fprintf(stderr, "rl = %lx\n", rl); - dump ("rref", rr); - dump ("q ", q); - dump ("qref", rq); - abort (); - } - - mpz_set_ui (r, 7); - rl = div_r_ui[j] (r, a, mpz_get_ui (b)); - if (rl != mpz_get_ui (rr) || mpz_cmp (r, rr)) - { - fprintf (stderr, "mpz_%cdiv_qr_ui failed:\n", name[j]); - dump ("a", a); - dump ("b", b); - fprintf(stderr, "rl = %lx\n", rl); - dump ("r ", r); - dump ("rref", rr); - abort (); - } - - rl = div_ui[j] (a, mpz_get_ui (b)); - if (rl != mpz_get_ui (rr)) - { - fprintf (stderr, "mpz_%cdiv_qr_ui failed:\n", name[j]); - dump ("a", a); - dump ("b", b); - fprintf(stderr, "rl = %lx\n", rl); - dump ("rref", rr); - abort (); - } - - if (j == 0) /* do this once, not for all roundings */ - { - div_p = mpz_divisible_ui_p (a, mpz_get_ui (b)); - if ((mpz_sgn (r) == 0) ^ (div_p != 0)) - { - fprintf (stderr, "mpz_divisible_ui_p failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r ", r); - abort (); - } - } - - if (j == 1) /* floor */ - { - mpz_mod_ui (r, a, mpz_get_ui (b)); - if (mpz_cmp (r, rr)) - { - fprintf (stderr, "mpz_mod failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r ", r); - dump ("rref", rr); - abort (); - } - } - } - } - } - mpz_clear (a); - mpz_clear (b); - mpz_clear (r); - mpz_clear (q); - mpz_clear (rr); - mpz_clear (rq); -} diff --git a/gmp/mini-gmp/tests/t-div_2exp.c b/gmp/mini-gmp/tests/t-div_2exp.c deleted file mode 100644 index 53d3f2b84d..0000000000 --- a/gmp/mini-gmp/tests/t-div_2exp.c +++ /dev/null @@ -1,82 +0,0 @@ -/* - -Copyright 2012, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <assert.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -typedef void div_func (mpz_t, const mpz_t, mp_bitcnt_t); - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, res, ref; - mp_bitcnt_t b; - - mpz_init (a); - mpz_init (res); - mpz_init (ref); - - for (i = 0; i < COUNT; i++) - { - unsigned j; - for (j = 0; j < 6; j++) - { - static const enum hex_random_op ops[6] = - { - OP_CDIV_Q_2, OP_CDIV_R_2, - OP_FDIV_Q_2, OP_FDIV_R_2, - OP_TDIV_Q_2, OP_TDIV_R_2 - }; - static const char *name[6] = - { - "cdiv_q", "cdiv_r", - "fdiv_q", "fdiv_r", - "tdiv_q", "tdiv_r" - }; - static div_func * const div [6] = - { - mpz_cdiv_q_2exp, mpz_cdiv_r_2exp, - mpz_fdiv_q_2exp, mpz_fdiv_r_2exp, - mpz_tdiv_q_2exp, mpz_tdiv_r_2exp - }; - - mini_random_bit_op (ops[j], MAXBITS, a, &b, ref); - div[j] (res, a, b); - if (mpz_cmp (ref, res)) - { - fprintf (stderr, "mpz_%s_2exp failed:\n", name[j]); - dump ("a", a); - fprintf (stderr, "b: %lu\n", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - } - } - mpz_clear (a); - mpz_clear (res); - mpz_clear (ref); -} diff --git a/gmp/mini-gmp/tests/t-double.c b/gmp/mini-gmp/tests/t-double.c deleted file mode 100644 index 9e8101ecfd..0000000000 --- a/gmp/mini-gmp/tests/t-double.c +++ /dev/null @@ -1,138 +0,0 @@ -/* - -Copyright 2012, 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <math.h> -#include <stdlib.h> -#include <stdio.h> -#include <string.h> - -#include "testutils.h" - -#define GMP_LIMB_BITS (sizeof(mp_limb_t) * CHAR_BIT) - -#define COUNT 10000 - -static const struct -{ - double d; - const char *s; -} values[] = { - { 0.0, "0" }, - { 0.3, "0" }, - { -0.3, "0" }, - { M_PI, "3" }, - { M_PI*1e15, "b29430a256d21" }, - { -M_PI*1e15, "-b29430a256d21" }, - /* 17 * 2^{200} = - 27317946752402834684213355569799764242877450894307478200123392 */ - {0.2731794675240283468421335556979976424288e62, - "1100000000000000000000000000000000000000000000000000" }, - { 0.0, NULL } -}; - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t x; - - for (i = 0; values[i].s; i++) - { - char *s; - mpz_init_set_d (x, values[i].d); - s = mpz_get_str (NULL, 16, x); - if (strcmp (s, values[i].s) != 0) - { - fprintf (stderr, "mpz_set_d failed:\n" - "d = %.20g\n" - "s = %s\n" - "r = %s\n", - values[i].d, s, values[i].s); - abort (); - } - testfree (s); - mpz_clear (x); - } - - mpz_init (x); - - for (i = 0; i < COUNT; i++) - { - /* Use volatile, to avoid extended precision in floating point - registers, e.g., on m68k and 80387. */ - volatile double d, f; - unsigned long m; - int e; - - mini_rrandomb (x, GMP_LIMB_BITS); - m = mpz_get_ui (x); - mini_urandomb (x, 8); - e = mpz_get_ui (x) - 100; - - d = ldexp ((double) m, e); - mpz_set_d (x, d); - f = mpz_get_d (x); - if (f != floor (d)) - { - fprintf (stderr, "mpz_set_d/mpz_get_d failed:\n"); - goto dumperror; - } - if ((f == d) ? (mpz_cmp_d (x, d) != 0) : (mpz_cmp_d (x, d) >= 0)) - { - fprintf (stderr, "mpz_cmp_d (x, d) failed:\n"); - goto dumperror; - } - f = d + 1.0; - if (f > d && ! (mpz_cmp_d (x, f) < 0)) - { - fprintf (stderr, "mpz_cmp_d (x, f) failed:\n"); - goto dumperror; - } - - d = - d; - - mpz_set_d (x, d); - f = mpz_get_d (x); - if (f != ceil (d)) - { - fprintf (stderr, "mpz_set_d/mpz_get_d failed:\n"); - dumperror: - dump ("x", x); - fprintf (stderr, "m = %lx, e = %i\n", m, e); - fprintf (stderr, "d = %.15g\n", d); - fprintf (stderr, "f = %.15g\n", f); - fprintf (stderr, "f - d = %.5g\n", f - d); - abort (); - } - if ((f == d) ? (mpz_cmp_d (x, d) != 0) : (mpz_cmp_d (x, d) <= 0)) - { - fprintf (stderr, "mpz_cmp_d (x, d) failed:\n"); - goto dumperror; - } - f = d - 1.0; - if (f < d && ! (mpz_cmp_d (x, f) > 0)) - { - fprintf (stderr, "mpz_cmp_d (x, f) failed:\n"); - goto dumperror; - } - } - - mpz_clear (x); -} diff --git a/gmp/mini-gmp/tests/t-gcd.c b/gmp/mini-gmp/tests/t-gcd.c deleted file mode 100644 index 1278000296..0000000000 --- a/gmp/mini-gmp/tests/t-gcd.c +++ /dev/null @@ -1,176 +0,0 @@ -/* - -Copyright 2012, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -/* Called when g is supposed to be gcd(a,b), and g = s a + t b. */ -static int -gcdext_valid_p (const mpz_t a, const mpz_t b, - const mpz_t g, const mpz_t s, const mpz_t t) -{ - mpz_t ta, tb, r; - - /* It's not clear that gcd(0,0) is well defined, but we allow it and - require that gcd(0,0) = 0. */ - if (mpz_sgn (g) < 0) - return 0; - - if (mpz_sgn (a) == 0) - { - /* Must have g == abs (b). Any value for s is in some sense "correct", - but it makes sense to require that s == 0. */ - return mpz_cmpabs (g, b) == 0 && mpz_sgn (s) == 0; - } - else if (mpz_sgn (b) == 0) - { - /* Must have g == abs (a), s == sign (a) */ - return mpz_cmpabs (g, a) == 0 && mpz_cmp_si (s, mpz_sgn (a)) == 0; - } - - if (mpz_sgn (g) <= 0) - return 0; - - mpz_init (ta); - mpz_init (tb); - mpz_init (r); - - mpz_mul (ta, s, a); - mpz_mul (tb, t, b); - mpz_add (ta, ta, tb); - - if (mpz_cmp (ta, g) != 0) - { - fail: - mpz_clear (ta); - mpz_clear (tb); - mpz_clear (r); - return 0; - } - mpz_tdiv_qr (ta, r, a, g); - if (mpz_sgn (r) != 0) - goto fail; - - mpz_tdiv_qr (tb, r, b, g); - if (mpz_sgn (r) != 0) - goto fail; - - /* Require that 2 |s| < |b/g|, or |s| == 1. */ - if (mpz_cmpabs_ui (s, 1) > 0) - { - mpz_mul_2exp (r, s, 1); - if (mpz_cmpabs (r, tb) > 0) - goto fail; - } - - /* Require that 2 |t| < |a/g| or |t| == 1*/ - if (mpz_cmpabs_ui (t, 1) > 0) - { - mpz_mul_2exp (r, t, 1); - if (mpz_cmpabs (r, ta) > 0) - return 0; - } - - mpz_clear (ta); - mpz_clear (tb); - mpz_clear (r); - - return 1; -} - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, b, g, s, t; - - mpz_init (a); - mpz_init (b); - mpz_init (g); - mpz_init (s); - mpz_init (t); - - for (i = 0; i < COUNT; i++) - { - mini_random_op3 (OP_GCD, MAXBITS, a, b, s); - mpz_gcd (g, a, b); - if (mpz_cmp (g, s)) - { - fprintf (stderr, "mpz_gcd failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", g); - dump ("ref", s); - abort (); - } - } - - for (i = 0; i < COUNT; i++) - { - unsigned flags; - mini_urandomb (a, 32); - flags = mpz_get_ui (a); - mini_rrandomb (a, MAXBITS); - mini_rrandomb (b, MAXBITS); - - if (flags % 37 == 0) - mpz_mul (a, a, b); - if (flags % 37 == 1) - mpz_mul (b, a, b); - - if (flags & 1) - mpz_neg (a, a); - if (flags & 2) - mpz_neg (b, b); - - mpz_gcdext (g, s, t, a, b); - if (!gcdext_valid_p (a, b, g, s, t)) - { - fprintf (stderr, "mpz_gcdext failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("g", g); - dump ("s", s); - dump ("t", t); - abort (); - } - - mpz_gcd (s, a, b); - if (mpz_cmp (g, s)) - { - fprintf (stderr, "mpz_gcd failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", g); - dump ("ref", s); - abort (); - } - } - mpz_clear (a); - mpz_clear (b); - mpz_clear (g); - mpz_clear (s); - mpz_clear (t); -} diff --git a/gmp/mini-gmp/tests/t-import.c b/gmp/mini-gmp/tests/t-import.c deleted file mode 100644 index 66c9d5e8d5..0000000000 --- a/gmp/mini-gmp/tests/t-import.c +++ /dev/null @@ -1,99 +0,0 @@ -/* - -Copyright 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <stdlib.h> -#include <stdio.h> -#include <string.h> - -#include "testutils.h" - -#define MAX_WORDS 20 -#define MAX_WORD_SIZE 10 - -static void -dump_bytes (const char *label, const unsigned char *s, size_t n) -{ - size_t i; - fprintf (stderr, "%s:", label); - for (i = 0; i < n; i++) - { - if (i && (i % 16) == 0) - fprintf (stderr, "\n"); - fprintf (stderr, " %02x", s[i]); - } - fprintf (stderr, "\n"); -} - -/* Tests both mpz_import and mpz_export. */ -void -testmain (int argc, char **argv) -{ - unsigned char input[MAX_WORDS * MAX_WORD_SIZE]; - unsigned char output[MAX_WORDS * MAX_WORD_SIZE + 2]; - size_t count, in_count, out_count, size; - int endian, order; - - mpz_t a, res; - - mpz_init (a); - mpz_init (res); - - for (size = 0; size <= MAX_WORD_SIZE; size++) - for (count = 0; count <= MAX_WORDS; count++) - for (endian = -1; endian <= 1; endian++) - for (order = -1; order <= 1; order += 2) - { - mini_rrandomb_export (a, input, &in_count, - order, size, endian, size*count * 8); - mpz_import (res, in_count, order, size, endian, 0, input); - if (mpz_cmp (a, res)) - { - fprintf (stderr, "mpz_import failed:\n" - "in_count %lu, out_count %lu, endian = %d, order = %d\n", - (unsigned long) in_count, (unsigned long) out_count, endian, order); - dump ("a", a); - dump ("res", res); - abort (); - } - output[0] = 17; - output[1+in_count*size] = 17; - - mpz_export (output+1, &out_count, order, size, endian, 0, a); - if (out_count != in_count - || memcmp (output+1, input, in_count * size) - || output[0] != 17 - || output[1+in_count*size] != 17) - { - fprintf (stderr, "mpz_export failed:\n" - "in_count %lu, out_count %lu, endian = %d, order = %d\n", - (unsigned long) in_count, (unsigned long) out_count, endian, order); - dump_bytes ("input", input, in_count * size); - dump_bytes ("output", output+1, out_count * size); - if (output[0] != 17) - fprintf (stderr, "Overwrite at -1, value %02x\n", output[0]); - if (output[1+in_count*size] != 17) - fprintf (stderr, "Overwrite at %lu, value %02x\n", - (unsigned long) (in_count*size), output[1+in_count*size]); - - abort (); - } - } - mpz_clear (a); - mpz_clear (res); -} diff --git a/gmp/mini-gmp/tests/t-invert.c b/gmp/mini-gmp/tests/t-invert.c deleted file mode 100644 index 496e8d4f53..0000000000 --- a/gmp/mini-gmp/tests/t-invert.c +++ /dev/null @@ -1,98 +0,0 @@ -/* - -Copyright 2012, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define GMP_LIMB_BITS (sizeof(mp_limb_t) * CHAR_BIT) - -#define COUNT 10000 - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t u, m, p, t; - - mpz_init (u); - mpz_init (m); - mpz_init (p); - mpz_init (t); - - for (i = 0; i < COUNT; i++) - { - mini_urandomb (u, GMP_LIMB_BITS); - mpz_setbit (u, GMP_LIMB_BITS -1); - - mpz_set_ui (m, mpn_invert_limb (u->_mp_d[0])); - mpz_setbit (m, GMP_LIMB_BITS); - - mpz_mul (p, m, u); - - mpz_set_ui (t, 0); - mpz_setbit (t, 2* GMP_LIMB_BITS); - mpz_sub (t, t, p); - - /* Should have 0 < B^2 - m u <= u */ - if (mpz_sgn (t) <= 0 || mpz_cmp (t, u) > 0) - { - fprintf (stderr, "mpn_invert_limb failed:\n"); - dump ("u", u); - dump ("m", m); - dump ("p", p); - dump ("t", t); - abort (); - } - } - - for (i = 0; i < COUNT; i++) - { - mini_urandomb (u, 2*GMP_LIMB_BITS); - mpz_setbit (u, 2*GMP_LIMB_BITS -1); - - mpz_set_ui (m, mpn_invert_3by2 (u->_mp_d[1], u[0]._mp_d[0])); - - mpz_setbit (m, GMP_LIMB_BITS); - - mpz_mul (p, m, u); - - mpz_set_ui (t, 0); - mpz_setbit (t, 3 * GMP_LIMB_BITS); - mpz_sub (t, t, p); - - /* Should have 0 < B^3 - m u <= u */ - if (mpz_sgn (t) <= 0 || mpz_cmp (t, u) > 0) - { - fprintf (stderr, "mpn_invert_3by2 failed:\n"); - dump ("u", u); - dump ("m", m); - dump ("p", p); - dump ("t", t); - abort (); - } - } - - mpz_clear (u); - mpz_clear (m); - mpz_clear (p); - mpz_clear (t); -} diff --git a/gmp/mini-gmp/tests/t-lcm.c b/gmp/mini-gmp/tests/t-lcm.c deleted file mode 100644 index f21a39a66a..0000000000 --- a/gmp/mini-gmp/tests/t-lcm.c +++ /dev/null @@ -1,73 +0,0 @@ -/* - -Copyright 2012, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, b, g, s; - - mpz_init (a); - mpz_init (b); - mpz_init (g); - mpz_init (s); - - for (i = 0; i < COUNT; i++) - { - mini_random_op3 (OP_LCM, MAXBITS, a, b, s); - mpz_lcm (g, a, b); - if (mpz_cmp (g, s)) - { - fprintf (stderr, "mpz_lcm failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", g); - dump ("ref", s); - abort (); - } - if (mpz_fits_ulong_p (b)) - { - mpz_set_si (g, 0); - mpz_lcm_ui (g, a, mpz_get_ui (b)); - if (mpz_cmp (g, s)) - { - fprintf (stderr, "mpz_lcm_ui failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", g); - dump ("ref", s); - abort (); - } - } - } - - mpz_clear (a); - mpz_clear (b); - mpz_clear (g); - mpz_clear (s); -} diff --git a/gmp/mini-gmp/tests/t-limbs.c b/gmp/mini-gmp/tests/t-limbs.c deleted file mode 100644 index fa65782db2..0000000000 --- a/gmp/mini-gmp/tests/t-limbs.c +++ /dev/null @@ -1,106 +0,0 @@ -/* - -Copyright 2012, 2014, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> -#include <string.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 100 - -void -my_mpz_mul (mpz_t r, mpz_srcptr a, mpz_srcptr b) -{ - mp_limb_t *tp; - mp_size_t tn, an, bn; - - an = mpz_size (a); - bn = mpz_size (b); - tn = an + bn; - - tp = mpz_limbs_write (r, tn); - if (mpz_sgn (a) * mpz_sgn(b) == 0) - mpn_zero (tp, tn); - else if (an > bn) - mpn_mul (tp, mpz_limbs_read (a), an, mpz_limbs_read (b), bn); - else - mpn_mul (tp, mpz_limbs_read (b), bn, mpz_limbs_read (a), an); - - if (mpz_sgn (a) != mpz_sgn(b)) - tn = - tn; - - mpz_limbs_finish (r, tn); -} - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, b, t, res, ref; - - mpz_init (a); - mpz_init (b); - mpz_init (res); - mpz_init (ref); - - for (i = 0; i < COUNT; i++) - { - mini_random_op3 (OP_MUL, MAXBITS, a, b, ref); - my_mpz_mul (res, a, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "my_mpz_mul failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - /* The following test exploits a side-effect of my_mpz_mul: res - points to a buffer with at least an+bn limbs, and the limbs - above the result are zeroed. */ - if (mpz_size (b) > 0 && mpz_getlimbn (res, mpz_size(a)) != mpz_limbs_read (res) [mpz_size(a)]) - { - fprintf (stderr, "getlimbn - limbs_read differ.\n"); - abort (); - } - if ((i % 4 == 0) && mpz_size (res) > 1) - { - mpz_realloc2 (res, 1); - if (mpz_cmp_ui (res, 0)) - { - fprintf (stderr, "mpz_realloc2 did not clear res.\n"); - abort (); - } - mpz_limbs_finish (ref, 0); - if (mpz_cmp_d (ref, 0)) - { - fprintf (stderr, "mpz_limbs_finish did not clear res.\n"); - abort (); - } - } - } - mpz_clear (a); - mpz_clear (b); - mpz_clear (res); - mpz_clear (ref); -} diff --git a/gmp/mini-gmp/tests/t-logops.c b/gmp/mini-gmp/tests/t-logops.c deleted file mode 100644 index 7e2d68187a..0000000000 --- a/gmp/mini-gmp/tests/t-logops.c +++ /dev/null @@ -1,112 +0,0 @@ -/* - -Copyright 2012, 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -void -testlogops (int count) -{ - unsigned i; - mpz_t a, b, res, ref; - mp_bitcnt_t c; - - mpz_init (a); - mpz_init (b); - mpz_init (res); - mpz_init (ref); - - for (i = 0; i < count; i++) - { - mini_random_op3 (OP_AND, MAXBITS, a, b, ref); - mpz_and (res, a, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_and failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - - mini_random_op3 (OP_IOR, MAXBITS, a, b, ref); - mpz_ior (res, a, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_ior failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - - mini_random_op3 (OP_XOR, MAXBITS, a, b, ref); - mpz_xor (res, a, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_xor failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - - if (i % 8) { - c = 0; - mpz_mul_2exp (res, res, i % 8); - } else if (mpz_sgn (res) >= 0) { - c = mpz_odd_p (res) != 0; - mpz_tdiv_q_2exp (res, res, 1); - } else { - c = (~ (mp_bitcnt_t) 0) - 3; - mpz_set_ui (res, 11 << ((i >> 3)%4)); /* set 3 bits */ - } - - if (mpz_popcount (res) + c != mpz_hamdist (a, b)) - { - fprintf (stderr, "mpz_popcount(r) + %lu and mpz_hamdist(a,b) differ:\n", c); - dump ("a", a); - dump ("b", b); - dump ("r", res); - fprintf (stderr, "mpz_popcount(r) = %lu:\n", mpz_popcount (res)); - fprintf (stderr, "mpz_hamdist(a,b) = %lu:\n", mpz_hamdist (a, b)); - abort (); - } - } - mpz_clear (a); - mpz_clear (b); - mpz_clear (res); - mpz_clear (ref); -} - -void -testmain (int argc, char **argv) -{ - testhalves (COUNT*2/3, testlogops); - testlogops (COUNT/3); -} diff --git a/gmp/mini-gmp/tests/t-mul.c b/gmp/mini-gmp/tests/t-mul.c deleted file mode 100644 index 57ec4ed36c..0000000000 --- a/gmp/mini-gmp/tests/t-mul.c +++ /dev/null @@ -1,113 +0,0 @@ -/* - -Copyright 2012, 2014, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> -#include <string.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -#define GMP_LIMB_BITS (sizeof(mp_limb_t) * CHAR_BIT) -#define MAXLIMBS ((MAXBITS + GMP_LIMB_BITS - 1) / GMP_LIMB_BITS) - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, b, res, res_ui, ref, tz; - mp_limb_t t[2*MAXLIMBS]; - mp_size_t an; - - mpz_init (a); - mpz_init (b); - mpz_init (res); - mpz_init (res_ui); - mpz_init (ref); - - for (i = 0; i < COUNT; i++) - { - mini_random_op3 (OP_MUL, MAXBITS, a, b, ref); - mpz_mul (res, a, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_mul failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - if (mpz_size (a) == mpz_size (b)) - { - memset (t, 0x55, sizeof(t)); - an = mpz_size (a); - if (an > 0) - { - mpn_mul_n (t, a->_mp_d, b->_mp_d, an); - - mpz_roinit_n (tz, t, 2*an); - if (mpz_cmpabs (tz, ref)) - { - fprintf (stderr, "mpn_mul_n failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("ref", ref); - abort (); - } - } - } - if (mpz_fits_slong_p (b)) { - mpz_mul_si (res_ui, a, mpz_get_si (b)); - if (mpz_cmp (res_ui, ref)) - { - fprintf (stderr, "mpz_mul_si failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res_ui); - dump ("ref", ref); - abort (); - } - } - mini_random_op2 (OP_SQR, MAXBITS, a, ref); - an = mpz_size (a); - if (an > 0) - { - memset (t, 0x33, sizeof(t)); - mpn_sqr (t, mpz_limbs_read (a), an); - - mpz_roinit_n (tz, t, 2*an); - if (mpz_cmp (tz, ref)) - { - fprintf (stderr, "mpn (squaring) failed:\n"); - dump ("a", a); - dump ("ref", ref); - abort (); - } - } - } - mpz_clear (a); - mpz_clear (b); - mpz_clear (res); - mpz_clear (res_ui); - mpz_clear (ref); -} diff --git a/gmp/mini-gmp/tests/t-powm.c b/gmp/mini-gmp/tests/t-powm.c deleted file mode 100644 index d6c108d47a..0000000000 --- a/gmp/mini-gmp/tests/t-powm.c +++ /dev/null @@ -1,61 +0,0 @@ -/* - -Copyright 2012, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 1000 - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t b, e, m, res, ref; - - mpz_init (b); - mpz_init (e); - mpz_init (m); - mpz_init (res); - mpz_init (ref); - - for (i = 0; i < COUNT; i++) - { - mini_random_op4 (OP_POWM, MAXBITS, b, e, m, ref); - mpz_powm (res, b, e, m); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_powm failed:\n"); - dump ("b", b); - dump ("e", e); - dump ("m", m); - dump ("r", res); - dump ("ref", ref); - abort (); - } - } - mpz_clear (b); - mpz_clear (e); - mpz_clear (m); - mpz_clear (res); - mpz_clear (ref); -} diff --git a/gmp/mini-gmp/tests/t-pprime_p.c b/gmp/mini-gmp/tests/t-pprime_p.c deleted file mode 100644 index a7ffcdb758..0000000000 --- a/gmp/mini-gmp/tests/t-pprime_p.c +++ /dev/null @@ -1,182 +0,0 @@ -/* test mpz_probab_prime_p - -Copyright 2001, 2002, 2004, 2011, 2012, 2014 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include "testutils.h" - -static int -isprime (unsigned long int t) -{ - unsigned long int q, r, d; - - if (t < 32) - return (0xa08a28acUL >> t) & 1; - if ((t & 1) == 0) - return 0; - - if (t % 3 == 0) - return 0; - if (t % 5 == 0) - return 0; - if (t % 7 == 0) - return 0; - - for (d = 11;;) - { - q = t / d; - r = t - q * d; - if (q < d) - return 1; - if (r == 0) - break; - d += 2; - q = t / d; - r = t - q * d; - if (q < d) - return 1; - if (r == 0) - break; - d += 4; - } - return 0; -} - -static void -check_one (mpz_srcptr n, int want) -{ - int got; - - got = mpz_probab_prime_p (n, 25); - - /* "definitely prime" is fine if we only wanted "probably prime" */ - if (got == 2 && want == 1) - want = 2; - - if (got != want) - { - printf ("mpz_probab_prime_p\n"); - dump (" n ", n); - printf (" got =%d", got); - printf (" want=%d\n", want); - abort (); - } -} - -static void -check_pn (mpz_ptr n, int want) -{ - check_one (n, want); - mpz_neg (n, n); - check_one (n, want); -} - -static void -check_small (void) -{ - mpz_t n; - long i; - - mpz_init (n); - - for (i = 0; i < 1700; i++) - { - mpz_set_si (n, i); - check_pn (n, isprime (i)); - } - - mpz_clear (n); -} - -void -check_composites (void) -{ - int i; - int reps = 1000; - mpz_t a, b, n, bs; - unsigned long size_range, size; - - mpz_init (a); - mpz_init (b); - mpz_init (n); - mpz_init (bs); - - for (i = 0; i < reps; i++) - { - mini_urandomb (bs, 32); - size_range = mpz_get_ui (bs) % 12 + 1; /* 0..4096 bit operands */ - - mini_urandomb (bs, size_range); - size = mpz_get_ui (bs); - mini_rrandomb (a, size); - - mini_urandomb (bs, 32); - size_range = mpz_get_ui (bs) % 12 + 1; /* 0..4096 bit operands */ - mini_rrandomb (b, size); - - /* Exclude trivial factors */ - if (mpz_cmp_ui (a, 1) == 0) - mpz_set_ui (a, 2); - if (mpz_cmp_ui (b, 1) == 0) - mpz_set_ui (b, 2); - - mpz_mul (n, a, b); - - check_pn (n, 0); - } - mpz_clear (a); - mpz_clear (b); - mpz_clear (n); - mpz_clear (bs); -} - -static void -check_primes (void) -{ - static const char * const primes[] = { - "2", "17", "65537", - /* diffie-hellman-group1-sha1, also "Well known group 2" in RFC - 2412, 2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 } */ - "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1" - "29024E088A67CC74020BBEA63B139B22514A08798E3404DD" - "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245" - "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED" - "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381" - "FFFFFFFFFFFFFFFF", - NULL - }; - - mpz_t n; - int i; - - mpz_init (n); - - for (i = 0; primes[i]; i++) - { - mpz_set_str_or_abort (n, primes[i], 0); - check_one (n, 1); - } - mpz_clear (n); -} - -void -testmain (int argc, char *argv[]) -{ - check_small (); - check_composites (); - check_primes (); -} diff --git a/gmp/mini-gmp/tests/t-reuse.c b/gmp/mini-gmp/tests/t-reuse.c deleted file mode 100644 index 018f8fd632..0000000000 --- a/gmp/mini-gmp/tests/t-reuse.c +++ /dev/null @@ -1,663 +0,0 @@ -/* Test that routines allow reusing a source variable as destination. - -Copyright 1996, 1999-2002, 2009, 2012 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <stdlib.h> -#include <stdio.h> -#include <string.h> - -#include "testutils.h" - -#define COUNT 100 - -void dump3 (const char *, mpz_t, mpz_t, mpz_t); -void mpz_check_format (const mpz_t); - -typedef void (*dss_func) (mpz_t, const mpz_t, const mpz_t); -typedef void (*dsi_func) (mpz_t, const mpz_t, unsigned long int); -typedef unsigned long int (*dsi_div_func) (mpz_t, const mpz_t, unsigned long int); -typedef unsigned long int (*ddsi_div_func) (mpz_t, mpz_t, const mpz_t, unsigned long int); -typedef void (*ddss_div_func) (mpz_t, mpz_t, const mpz_t, const mpz_t); -typedef void (*ds_func) (mpz_t, const mpz_t); - - -void -mpz_xinvert (mpz_t r, const mpz_t a, const mpz_t b) -{ - int res; - res = mpz_invert (r, a, b); - if (res == 0) - mpz_set_ui (r, 0); -} - -dss_func dss_funcs[] = -{ - mpz_add, mpz_sub, mpz_mul, - mpz_cdiv_q, mpz_cdiv_r, mpz_fdiv_q, mpz_fdiv_r, mpz_tdiv_q, mpz_tdiv_r, - mpz_xinvert, - mpz_gcd, mpz_lcm, mpz_and, mpz_ior, mpz_xor -}; -const char *dss_func_names[] = -{ - "mpz_add", "mpz_sub", "mpz_mul", - "mpz_cdiv_q", "mpz_cdiv_r", "mpz_fdiv_q", "mpz_fdiv_r", "mpz_tdiv_q", "mpz_tdiv_r", - "mpz_xinvert", - "mpz_gcd", "mpz_lcm", "mpz_and", "mpz_ior", "mpz_xor" -}; -char dss_func_division[] = {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}; - -dsi_func dsi_funcs[] = -{ - /* Don't change order here without changing the code in main(). */ - mpz_add_ui, mpz_mul_ui, mpz_sub_ui, - mpz_fdiv_q_2exp, mpz_fdiv_r_2exp, - mpz_cdiv_q_2exp, mpz_cdiv_r_2exp, - mpz_tdiv_q_2exp, mpz_tdiv_r_2exp, - mpz_mul_2exp, - mpz_pow_ui -}; -const char *dsi_func_names[] = -{ - "mpz_add_ui", "mpz_mul_ui", "mpz_sub_ui", - "mpz_fdiv_q_2exp", "mpz_fdiv_r_2exp", - "mpz_cdiv_q_2exp", "mpz_cdiv_r_2exp", - "mpz_tdiv_q_2exp", "mpz_tdiv_r_2exp", - "mpz_mul_2exp", - "mpz_pow_ui" -}; - -dsi_div_func dsi_div_funcs[] = -{ - mpz_cdiv_q_ui, mpz_cdiv_r_ui, - mpz_fdiv_q_ui, mpz_fdiv_r_ui, - mpz_tdiv_q_ui, mpz_tdiv_r_ui -}; -const char *dsi_div_func_names[] = -{ - "mpz_cdiv_q_ui", "mpz_cdiv_r_ui", - "mpz_fdiv_q_ui", "mpz_fdiv_r_ui", - "mpz_tdiv_q_ui", "mpz_tdiv_r_ui" -}; - -ddsi_div_func ddsi_div_funcs[] = -{ - mpz_cdiv_qr_ui, - mpz_fdiv_qr_ui, - mpz_tdiv_qr_ui -}; -const char *ddsi_div_func_names[] = -{ - "mpz_cdiv_qr_ui", - "mpz_fdiv_qr_ui", - "mpz_tdiv_qr_ui" -}; - -ddss_div_func ddss_div_funcs[] = -{ - mpz_cdiv_qr, - mpz_fdiv_qr, - mpz_tdiv_qr -}; -const char *ddss_div_func_names[] = -{ - "mpz_cdiv_qr", - "mpz_fdiv_qr", - "mpz_tdiv_qr" -}; - -ds_func ds_funcs[] = -{ - mpz_abs, mpz_com, mpz_neg, mpz_sqrt -}; -const char *ds_func_names[] = -{ - "mpz_abs", "mpz_com", "mpz_neg", "mpz_sqrt" -}; - - -#define FAIL(class,indx,op1,op2,op3) \ - do { \ - class##_funcs[indx] = 0; \ - dump3 (class##_func_names[indx], op1, op2, op3); \ - failures++; \ - } while (0) -#define FAIL2(fname,op1,op2,op3) \ - do { \ - dump3 (#fname, op1, op2, op3); \ - failures++; \ - } while (0) - -void -testmain (int argc, char **argv) -{ - int i; - int pass, reps = COUNT; - mpz_t in1, in2, in3; - unsigned long int in2i; - mp_size_t size; - mpz_t res1, res2, res3; - mpz_t ref1, ref2, ref3; - mpz_t t; - unsigned long int r1, r2; - long failures = 0; - mpz_t bs; - unsigned long bsi, size_range; - - mpz_init (bs); - - mpz_init (in1); - mpz_init (in2); - mpz_init (in3); - mpz_init (ref1); - mpz_init (ref2); - mpz_init (ref3); - mpz_init (res1); - mpz_init (res2); - mpz_init (res3); - mpz_init (t); - - for (pass = 1; pass <= reps; pass++) - { - mini_urandomb (bs, 32); - size_range = mpz_get_ui (bs) % 12 + 2; - - mini_urandomb (bs, size_range); - size = mpz_get_ui (bs); - mini_rrandomb (in1, size); - - mini_urandomb (bs, size_range); - size = mpz_get_ui (bs); - mini_rrandomb (in2, size); - - mini_urandomb (bs, size_range); - size = mpz_get_ui (bs); - mini_rrandomb (in3, size); - - mini_urandomb (bs, 3); - bsi = mpz_get_ui (bs); - if ((bsi & 1) != 0) - mpz_neg (in1, in1); - if ((bsi & 2) != 0) - mpz_neg (in2, in2); - if ((bsi & 4) != 0) - mpz_neg (in3, in3); - - for (i = 0; i < sizeof (dss_funcs) / sizeof (dss_func); i++) - { - if (dss_funcs[i] == 0) - continue; - if (dss_func_division[i] && mpz_sgn (in2) == 0) - continue; - - (dss_funcs[i]) (ref1, in1, in2); - mpz_check_format (ref1); - - mpz_set (res1, in1); - (dss_funcs[i]) (res1, res1, in2); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL (dss, i, in1, in2, NULL); - - mpz_set (res1, in2); - (dss_funcs[i]) (res1, in1, res1); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL (dss, i, in1, in2, NULL); - } - - for (i = 0; i < sizeof (ddss_div_funcs) / sizeof (ddss_div_func); i++) - { - if (ddss_div_funcs[i] == 0) - continue; - if (mpz_sgn (in2) == 0) - continue; - - (ddss_div_funcs[i]) (ref1, ref2, in1, in2); - mpz_check_format (ref1); - mpz_check_format (ref2); - - mpz_set (res1, in1); - (ddss_div_funcs[i]) (res1, res2, res1, in2); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0) - FAIL (ddss_div, i, in1, in2, NULL); - - mpz_set (res2, in1); - (ddss_div_funcs[i]) (res1, res2, res2, in2); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0) - FAIL (ddss_div, i, in1, in2, NULL); - - mpz_set (res1, in2); - (ddss_div_funcs[i]) (res1, res2, in1, res1); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0) - FAIL (ddss_div, i, in1, in2, NULL); - - mpz_set (res2, in2); - (ddss_div_funcs[i]) (res1, res2, in1, res2); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0) - FAIL (ddss_div, i, in1, in2, NULL); - } - - for (i = 0; i < sizeof (ds_funcs) / sizeof (ds_func); i++) - { - if (ds_funcs[i] == 0) - continue; - if (strcmp (ds_func_names[i], "mpz_sqrt") == 0 - && mpz_sgn (in1) < 0) - continue; - - (ds_funcs[i]) (ref1, in1); - mpz_check_format (ref1); - - mpz_set (res1, in1); - (ds_funcs[i]) (res1, res1); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL (ds, i, in1, in2, NULL); - } - - in2i = mpz_get_ui (in2); - - for (i = 0; i < sizeof (dsi_funcs) / sizeof (dsi_func); i++) - { - if (dsi_funcs[i] == 0) - continue; - if (strcmp (dsi_func_names[i], "mpz_fdiv_q_2exp") == 0) - /* Limit exponent to something reasonable for the division - functions. Without this, we'd normally shift things off - the end and just generate the trivial values 1, 0, -1. */ - in2i %= 0x1000; - if (strcmp (dsi_func_names[i], "mpz_mul_2exp") == 0) - /* Limit exponent more for mpz_mul_2exp to save time. */ - in2i %= 0x100; - if (strcmp (dsi_func_names[i], "mpz_pow_ui") == 0) - /* Limit exponent yet more for mpz_pow_ui to save time. */ - in2i %= 0x10; - - (dsi_funcs[i]) (ref1, in1, in2i); - mpz_check_format (ref1); - - mpz_set (res1, in1); - (dsi_funcs[i]) (res1, res1, in2i); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL (dsi, i, in1, in2, NULL); - } - - if (in2i != 0) /* Don't divide by 0. */ - { - for (i = 0; i < sizeof (dsi_div_funcs) / sizeof (dsi_div_funcs); i++) - { - r1 = (dsi_div_funcs[i]) (ref1, in1, in2i); - mpz_check_format (ref1); - - mpz_set (res1, in1); - r2 = (dsi_div_funcs[i]) (res1, res1, in2i); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0 || r1 != r2) - FAIL (dsi_div, i, in1, in2, NULL); - } - - for (i = 0; i < sizeof (ddsi_div_funcs) / sizeof (ddsi_div_funcs); i++) - { - r1 = (ddsi_div_funcs[i]) (ref1, ref2, in1, in2i); - mpz_check_format (ref1); - - mpz_set (res1, in1); - r2 = (ddsi_div_funcs[i]) (res1, res2, res1, in2i); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 || r1 != r2) - FAIL (ddsi_div, i, in1, in2, NULL); - - mpz_set (res2, in1); - (ddsi_div_funcs[i]) (res1, res2, res2, in2i); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 || r1 != r2) - FAIL (ddsi_div, i, in1, in2, NULL); - } - } - - if (mpz_sgn (in1) >= 0) - { - mpz_sqrtrem (ref1, ref2, in1); - mpz_check_format (ref1); - mpz_check_format (ref2); - - mpz_set (res1, in1); - mpz_sqrtrem (res1, res2, res1); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0) - FAIL2 (mpz_sqrtrem, in1, NULL, NULL); - - mpz_set (res2, in1); - mpz_sqrtrem (res1, res2, res2); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0) - FAIL2 (mpz_sqrtrem, in1, NULL, NULL); - } - - if (mpz_sgn (in1) >= 0) - { - mpz_root (ref1, in1, in2i % 0x1000 + 1); - mpz_check_format (ref1); - - mpz_set (res1, in1); - mpz_root (res1, res1, in2i % 0x1000 + 1); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_root, in1, in2, NULL); - } - - if (mpz_sgn (in1) >= 0) - { - mpz_rootrem (ref1, ref2, in1, in2i % 0x1000 + 1); - mpz_check_format (ref1); - mpz_check_format (ref2); - - mpz_set (res1, in1); - mpz_rootrem (res1, res2, res1, in2i % 0x1000 + 1); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0) - FAIL2 (mpz_rootrem, in1, in2, NULL); - - mpz_set (res2, in1); - mpz_rootrem (res1, res2, res2, in2i % 0x1000 + 1); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0) - FAIL2 (mpz_rootrem, in1, in2, NULL); - } - - if (pass < reps / 2) /* run fewer tests since gcdext lots of time */ - { - mpz_gcdext (ref1, ref2, ref3, in1, in2); - mpz_check_format (ref1); - mpz_check_format (ref2); - mpz_check_format (ref3); - - mpz_set (res1, in1); - mpz_gcdext (res1, res2, res3, res1, in2); - mpz_check_format (res1); - mpz_check_format (res2); - mpz_check_format (res3); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - - mpz_set (res2, in1); - mpz_gcdext (res1, res2, res3, res2, in2); - mpz_check_format (res1); - mpz_check_format (res2); - mpz_check_format (res3); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - - mpz_set (res3, in1); - mpz_gcdext (res1, res2, res3, res3, in2); - mpz_check_format (res1); - mpz_check_format (res2); - mpz_check_format (res3); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - - mpz_set (res1, in2); - mpz_gcdext (res1, res2, res3, in1, res1); - mpz_check_format (res1); - mpz_check_format (res2); - mpz_check_format (res3); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - - mpz_set (res2, in2); - mpz_gcdext (res1, res2, res3, in1, res2); - mpz_check_format (res1); - mpz_check_format (res2); - mpz_check_format (res3); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - - mpz_set (res3, in2); - mpz_gcdext (res1, res2, res3, in1, res3); - mpz_check_format (res1); - mpz_check_format (res2); - mpz_check_format (res3); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - - mpz_set (res1, in1); - mpz_gcdext (res1, res2, NULL, res1, in2); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - - mpz_set (res2, in1); - mpz_gcdext (res1, res2, NULL, res2, in2); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - - mpz_set (res1, in2); - mpz_gcdext (res1, res2, NULL, in1, res1); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - - mpz_set (res2, in2); - mpz_gcdext (res1, res2, NULL, in1, res2); - mpz_check_format (res1); - mpz_check_format (res2); - if (mpz_cmp (ref1, res1) != 0 || mpz_cmp (ref2, res2) != 0 - || mpz_cmp (ref3, res3) != 0) - FAIL2 (mpz_gcdext, in1, in2, NULL); - } - - /* Don't run mpz_powm for huge exponents or when undefined. */ - if (mpz_sizeinbase (in2, 2) < 250 && mpz_sgn (in3) != 0 - && (mpz_sgn (in2) >= 0 || mpz_invert (t, in1, in3))) - { - mpz_powm (ref1, in1, in2, in3); - mpz_check_format (ref1); - - mpz_set (res1, in1); - mpz_powm (res1, res1, in2, in3); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_powm, in1, in2, in3); - - mpz_set (res1, in2); - mpz_powm (res1, in1, res1, in3); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_powm, in1, in2, in3); - - mpz_set (res1, in3); - mpz_powm (res1, in1, in2, res1); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_powm, in1, in2, in3); - } - - /* Don't run mpz_powm_ui when undefined. */ - if (mpz_sgn (in3) != 0) - { - mpz_powm_ui (ref1, in1, in2i, in3); - mpz_check_format (ref1); - - mpz_set (res1, in1); - mpz_powm_ui (res1, res1, in2i, in3); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_powm_ui, in1, in2, in3); - - mpz_set (res1, in3); - mpz_powm_ui (res1, in1, in2i, res1); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_powm_ui, in1, in2, in3); - } - - { - r1 = mpz_gcd_ui (ref1, in1, in2i); - mpz_check_format (ref1); - - mpz_set (res1, in1); - r2 = mpz_gcd_ui (res1, res1, in2i); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_gcd_ui, in1, in2, NULL); - } -#if 0 - if (mpz_cmp_ui (in2, 1L) > 0 && mpz_sgn (in1) != 0) - { - /* Test mpz_remove */ - mpz_remove (ref1, in1, in2); - mpz_check_format (ref1); - - mpz_set (res1, in1); - mpz_remove (res1, res1, in2); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_remove, in1, in2, NULL); - - mpz_set (res1, in2); - mpz_remove (res1, in1, res1); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_remove, in1, in2, NULL); - } -#endif - if (mpz_sgn (in2) != 0) - { - /* Test mpz_divexact */ - mpz_mul (t, in1, in2); - mpz_divexact (ref1, t, in2); - mpz_check_format (ref1); - - mpz_set (res1, t); - mpz_divexact (res1, res1, in2); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_divexact, t, in2, NULL); - - mpz_set (res1, in2); - mpz_divexact (res1, t, res1); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_divexact, t, in2, NULL); - } - -#if 0 - if (mpz_sgn (in2) > 0) - { - /* Test mpz_divexact_gcd, same as mpz_divexact */ - mpz_mul (t, in1, in2); - mpz_divexact_gcd (ref1, t, in2); - mpz_check_format (ref1); - - mpz_set (res1, t); - mpz_divexact_gcd (res1, res1, in2); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_divexact_gcd, t, in2, NULL); - - mpz_set (res1, in2); - mpz_divexact_gcd (res1, t, res1); - mpz_check_format (res1); - if (mpz_cmp (ref1, res1) != 0) - FAIL2 (mpz_divexact_gcd, t, in2, NULL); - } -#endif - } - - if (failures != 0) - { - fprintf (stderr, "mpz/reuse: %ld error%s\n", failures, "s" + (failures == 1)); - exit (1); - } - - mpz_clear (bs); - mpz_clear (in1); - mpz_clear (in2); - mpz_clear (in3); - mpz_clear (ref1); - mpz_clear (ref2); - mpz_clear (ref3); - mpz_clear (res1); - mpz_clear (res2); - mpz_clear (res3); - mpz_clear (t); -} - -void -dump3 (const char *name, mpz_t in1, mpz_t in2, mpz_t in3) -{ - printf ("failure in %s (", name); - mpz_out_str (stdout, -16, in1); - if (in2 != NULL) - { - printf (" "); - mpz_out_str (stdout, -16, in2); - } - if (in3 != NULL) - { - printf (" "); - mpz_out_str (stdout, -16, in3); - } - printf (")\n"); -} - -void -mpz_check_format (const mpz_t x) -{ - mp_size_t n = x ->_mp_size; - if (n < 0) - n = - n; - - if (n > x->_mp_alloc) - { - fprintf (stderr, "mpz_t size exceeds allocation!\n"); - abort (); - } - - if (n > 0 && x->_mp_d[n-1] == 0) - { - fprintf (stderr, "Unnormalized mpz_t!\n"); - abort (); - } -} diff --git a/gmp/mini-gmp/tests/t-root.c b/gmp/mini-gmp/tests/t-root.c deleted file mode 100644 index 1f46c435c0..0000000000 --- a/gmp/mini-gmp/tests/t-root.c +++ /dev/null @@ -1,95 +0,0 @@ -/* - -Copyright 2012, 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -/* Called when s is supposed to be floor(root(u,z)), and r = u - s^z */ -static int -rootrem_valid_p (const mpz_t u, const mpz_t s, const mpz_t r, unsigned long z) -{ - mpz_t t; - - mpz_init (t); - if (mpz_fits_ulong_p (s)) - mpz_ui_pow_ui (t, mpz_get_ui (s), z); - else - mpz_pow_ui (t, s, z); - mpz_sub (t, u, t); - if ((mpz_sgn (t) != mpz_sgn(u) && mpz_sgn (t) != 0) || mpz_cmp (t, r) != 0) - { - mpz_clear (t); - return 0; - } - if (mpz_sgn (s) > 0) - mpz_add_ui (t, s, 1); - else - mpz_sub_ui (t, s, 1); - mpz_pow_ui (t, t, z); - if (mpz_cmpabs (t, u) <= 0) - { - mpz_clear (t); - return 0; - } - - mpz_clear (t); - return 1; -} - -void -testmain (int argc, char **argv) -{ - unsigned i; - unsigned long e; - mpz_t u, s, r, bs; - - mpz_init (u); - mpz_init (s); - mpz_init (r); - mpz_init (bs); - - for (i = 0; i < COUNT; i++) - { - mini_rrandomb (u, MAXBITS); - mini_rrandomb (bs, 12); - e = mpz_getlimbn (bs, 0) % mpz_sizeinbase (u, 2) + 1; - if ((e & 1) && (mpz_getlimbn (bs, 0) & (1L<<10))) - mpz_neg (u, u); - mpz_rootrem (s, r, u, e); - - if (!rootrem_valid_p (u, s, r, e)) - { - fprintf (stderr, "mpz_rootrem(%lu-th) failed:\n", e); - dump ("u", u); - dump ("root", s); - dump ("rem", r); - abort (); - } - } - mpz_clear (bs); - mpz_clear (u); - mpz_clear (s); - mpz_clear (r); -} diff --git a/gmp/mini-gmp/tests/t-scan.c b/gmp/mini-gmp/tests/t-scan.c deleted file mode 100644 index 39b1f35cf4..0000000000 --- a/gmp/mini-gmp/tests/t-scan.c +++ /dev/null @@ -1,90 +0,0 @@ -/* - -Copyright 2012, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a; - mp_bitcnt_t b, res, ref; - - mpz_init (a); - - for (i = 0; i < COUNT; i++) - { - mini_random_scan_op (OP_SCAN0, MAXBITS, a, &b, &ref); - res = mpz_scan0 (a, b); - if (res != ref) - { - fprintf (stderr, "mpz_scan0 failed:\n"); - dump ("a", a); - fprintf (stderr, "b: %lu\n", b); - fprintf (stderr, "r: %lu\n", res); - fprintf (stderr, "ref: %lu\n", ref); - abort (); - } - if (mpz_sgn (a) > 0 && ref < mpz_sizeinbase (a, 2)) - { - res = mpn_scan0 (a->_mp_d, b); - if (res != ref) - { - fprintf (stderr, "mpn_scan0 failed:\n"); - dump ("a", a); - fprintf (stderr, "b: %lu\n", b); - fprintf (stderr, "r: %lu\n", res); - fprintf (stderr, "ref: %lu\n", ref); - abort (); - } - } - mini_random_scan_op (OP_SCAN1, MAXBITS, a, &b, &ref); - res = mpz_scan1 (a, b); - if (res != ref) - { - fprintf (stderr, "mpz_scan1 failed:\n"); - dump ("a", a); - fprintf (stderr, "b: %lu\n", b); - fprintf (stderr, "r: %lu\n", res); - fprintf (stderr, "ref: %lu\n", ref); - abort (); - } - if (mpz_sgn (a) > 0 && ref != ~ (mp_bitcnt_t) 0) - { - res = mpn_scan1 (a->_mp_d, b); - if (res != ref) - { - fprintf (stderr, "mpn_scan1 failed:\n"); - dump ("a", a); - fprintf (stderr, "b: %lu\n", b); - fprintf (stderr, "r: %lu\n", res); - fprintf (stderr, "ref: %lu\n", ref); - abort (); - } - } - } - mpz_clear (a); -} diff --git a/gmp/mini-gmp/tests/t-signed.c b/gmp/mini-gmp/tests/t-signed.c deleted file mode 100644 index e2502d6e9f..0000000000 --- a/gmp/mini-gmp/tests/t-signed.c +++ /dev/null @@ -1,142 +0,0 @@ -/* Exercise some mpz_..._si functions. - -Copyright 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <stdio.h> -#include <stdlib.h> - -#include "testutils.h" - -int -check_si (mpz_t sz, mpz_t oz, long si, long oi, int c) -{ - mpz_t t; - int fail; - - if (mpz_cmp_si (sz, oi) != c) - { - printf ("mpz_cmp_si (sz, %ld) != %i.\n", oi, c); - printf (" sz="); mpz_out_str (stdout, 10, sz); printf ("\n"); - abort (); - } - - if ((si < oi ? -1 : si > oi) != c) - return 1; - - mpz_init_set_si (t, si); - - if ((fail = mpz_cmp_si (sz, si)) != 0) - printf ("mpz_cmp_si (sz, %ld) != 0.\n", si); - if (mpz_cmp_si (oz, si) != -c) - printf ("mpz_cmp_si (oz, %ld) != %i.\n", si, -c), fail = 1; - if (! mpz_fits_slong_p (sz)) - printf ("mpz_fits_slong_p (sz) != 1.\n"), fail = 1; - if (mpz_get_si (sz) != si) - printf ("mpz_get_si (sz) != %ld.\n", si), fail = 1; - if (mpz_cmp (t, sz) != 0) - { - printf ("mpz_init_set_si (%ld) failed.\n", si); - printf (" got="); mpz_out_str (stdout, 10, t); printf ("\n"); - fail = 1; - } - - mpz_clear (t); - - if (fail) - { - printf (" sz="); mpz_out_str (stdout, 10, sz); printf ("\n"); - printf (" oz="); mpz_out_str (stdout, 10, oz); printf ("\n"); - printf (" si=%ld\n", si); - abort (); - } - - return 0; -} - -void -try_op_si (int c) -{ - long si, oi; - mpz_t sz, oz; - - si = c; - mpz_init_set_si (sz, si); - - oi = si; - mpz_init_set (oz, sz); - - do { - si *= 2; /* c * 2^k */ - mpz_mul_2exp (sz, sz, 1); - - if (check_si (sz, oz, si, oi, c)) - { - mpz_set (oz, sz); - break; - } - - oi = si + c; /* c * (2^k + 1) */ - if (c == -1) - mpz_sub_ui (oz, sz, 1); - else - mpz_add_ui (oz, sz, 1); - - if (check_si (oz, sz, oi, si, c)) - break; - - oi = (si - c) * 2 + c; /* c * (2^K - 1) */ - mpz_mul_si (oz, sz, 2*c); - if (c == -1) - mpz_ui_sub (oz, 1, oz); /* oz = sz * 2 + 1 */ - else - mpz_sub_ui (oz, oz, 1); /* oz = sz * 2 - 1 */ - } while (check_si (oz, sz, oi, si, c) == 0); - - mpz_clear (sz); - - if (mpz_fits_slong_p (oz)) - { - printf ("Should not fit a signed long any more.\n"); - printf (" oz="); mpz_out_str (stdout, 10, oz); printf ("\n"); - abort (); - } - - if (mpz_cmp_si (oz, -c) != c) - { - printf ("mpz_cmp_si (oz, %i) != %i.\n", c, c); - printf (" oz="); mpz_out_str (stdout, 10, oz); printf ("\n"); - abort (); - } - - mpz_mul_2exp (oz, oz, 1); - if (mpz_cmp_si (oz, -c) != c) - { - printf ("mpz_cmp_si (oz, %i) != %i.\n", c, c); - printf (" oz="); mpz_out_str (stdout, 10, oz); printf ("\n"); - abort (); - } - - mpz_clear (oz); -} - -void -testmain (int argc, char *argv[]) -{ - try_op_si (-1); - try_op_si (1); -} diff --git a/gmp/mini-gmp/tests/t-sqrt.c b/gmp/mini-gmp/tests/t-sqrt.c deleted file mode 100644 index f4ce7cbb4d..0000000000 --- a/gmp/mini-gmp/tests/t-sqrt.c +++ /dev/null @@ -1,181 +0,0 @@ -/* - -Copyright 2012, 2014, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 9000 - -/* Called when s is supposed to be floor(sqrt(u)), and r = u - s^2 */ -static int -sqrtrem_valid_p (const mpz_t u, const mpz_t s, const mpz_t r) -{ - mpz_t t; - - mpz_init (t); - mpz_mul (t, s, s); - mpz_sub (t, u, t); - if (mpz_sgn (t) < 0 || mpz_cmp (t, r) != 0) - { - mpz_clear (t); - return 0; - } - mpz_add_ui (t, s, 1); - mpz_mul (t, t, t); - if (mpz_cmp (t, u) <= 0) - { - mpz_clear (t); - return 0; - } - - mpz_clear (t); - return 1; -} - -void -mpz_mpn_sqrtrem (mpz_t s, mpz_t r, const mpz_t u) -{ - mp_limb_t *sp, *rp; - mp_size_t un, sn, ret; - - un = mpz_size (u); - - mpz_xor (s, s, u); - sn = (un + 1) / 2; - sp = mpz_limbs_write (s, sn + 1); - sp [sn] = 11; - - if (un & 1) - rp = NULL; /* Exploits the fact that r already is correct. */ - else { - mpz_add (r, u, s); - rp = mpz_limbs_write (r, un + 1); - rp [un] = 19; - } - - ret = mpn_sqrtrem (sp, rp, mpz_limbs_read (u), un); - - if (sp [sn] != 11) - { - fprintf (stderr, "mpn_sqrtrem buffer overrun on sp.\n"); - abort (); - } - if (un & 1) { - if ((ret != 0) != (mpz_size (r) != 0)) { - fprintf (stderr, "mpn_sqrtrem wrong return value with NULL.\n"); - abort (); - } - } else { - mpz_limbs_finish (r, ret); - if (ret != mpz_size (r)) { - fprintf (stderr, "mpn_sqrtrem wrong return value.\n"); - abort (); - } - if (rp [un] != 19) - { - fprintf (stderr, "mpn_sqrtrem buffer overrun on rp.\n"); - abort (); - } - } - - mpz_limbs_finish (s, (un + 1) / 2); -} - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t u, s, r; - - mpz_init (s); - mpz_init (r); - - mpz_init_set_si (u, -1); - if (mpz_perfect_square_p (u)) - { - fprintf (stderr, "mpz_perfect_square_p failed on -1.\n"); - abort (); - } - - if (!mpz_perfect_square_p (s)) - { - fprintf (stderr, "mpz_perfect_square_p failed on 0.\n"); - abort (); - } - - for (i = 0; i < COUNT; i++) - { - mini_rrandomb (u, MAXBITS - (i & 0xFF)); - mpz_sqrtrem (s, r, u); - - if (!sqrtrem_valid_p (u, s, r)) - { - fprintf (stderr, "mpz_sqrtrem failed:\n"); - dump ("u", u); - dump ("sqrt", s); - dump ("rem", r); - abort (); - } - - mpz_mpn_sqrtrem (s, r, u); - - if (!sqrtrem_valid_p (u, s, r)) - { - fprintf (stderr, "mpn_sqrtrem failed:\n"); - dump ("u", u); - dump ("sqrt", s); - dump ("rem", r); - abort (); - } - - if (mpz_sgn (r) == 0) { - mpz_neg (u, u); - mpz_sub_ui (u, u, 1); - } - - if ((mpz_sgn (u) <= 0 || (i & 1)) ? - mpz_perfect_square_p (u) : - mpn_perfect_square_p (mpz_limbs_read (u), mpz_size (u))) - { - fprintf (stderr, "mp%s_perfect_square_p failed on non square:\n", - (mpz_sgn (u) <= 0 || (i & 1)) ? "z" : "n"); - dump ("u", u); - abort (); - } - - mpz_mul (u, s, s); - if (!((mpz_sgn (u) <= 0 || (i & 1)) ? - mpz_perfect_square_p (u) : - mpn_perfect_square_p (mpz_limbs_read (u), mpz_size (u)))) - { - fprintf (stderr, "mp%s_perfect_square_p failed on square:\n", - (mpz_sgn (u) <= 0 || (i & 1)) ? "z" : "n"); - dump ("u", u); - abort (); - } - - } - mpz_clear (u); - mpz_clear (s); - mpz_clear (r); -} diff --git a/gmp/mini-gmp/tests/t-str.c b/gmp/mini-gmp/tests/t-str.c deleted file mode 100644 index 2c384bd1d2..0000000000 --- a/gmp/mini-gmp/tests/t-str.c +++ /dev/null @@ -1,307 +0,0 @@ -/* - -Copyright 2012, 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <assert.h> -#include <limits.h> -#include <stdlib.h> -#include <stdio.h> -#include <string.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 2000 - -#define GMP_LIMB_BITS (sizeof(mp_limb_t) * CHAR_BIT) -#define MAXLIMBS ((MAXBITS + GMP_LIMB_BITS - 1) / GMP_LIMB_BITS) - -static void -test_small (void) -{ - struct { - const char *input; - const char *decimal; - } data[] = { - { "183407", "183407" }, - { " 763959", "763959" }, - { "9 81999", "981999" }, - { "10\t7398", "107398" }, - { "-9585 44", "-00958544" }, - { "-0", "0000" }, - { " -000 ", "0" }, - { "0704436", "231710" }, - { " 02503517", "689999" }, - { "0 1312143", "365667" }, - { "-03 274062", "-882738" }, - { "012\t242", "005282" }, - { "0b11010111110010001111", "883855" }, - { " 0b11001010010100001", "103585" }, - { "-0b101010110011101111", "-175343" }, - { "0b 1111111011011100110", "521958" }, - { "0b1 1111110111001000011", "1044035" }, - { " 0x53dfc", "343548" }, - { "0xfA019", "1024025" }, - { "0x 642d1", "410321" }, - { "0x5 8067", "360551" }, - { "-0xd6Be6", "-879590" }, - { "\t0B1110000100000000011", "460803" }, - { "0B\t1111110010010100101", "517285" }, - { "0B1\t010111101101110100", "359284" }, - { "-0B101\t1001101111111001", "-367609" }, - { "0B10001001010111110000", "562672" }, - { "0Xe4B7e", "936830" }, - { "0X1E4bf", "124095" }, - { "-0Xfdb90", "-1039248" }, - { "0X7fc47", "523335" }, - { "0X8167c", "530044" }, - /* Some invalid inputs */ - { "0ab", NULL }, - { "10x0", NULL }, - { "0xxab", NULL }, - { "ab", NULL }, - { "0%#", NULL }, - { "$foo", NULL }, - { NULL, NULL } - }; - unsigned i; - mpz_t a, b; - mpz_init (b); - - for (i = 0; data[i].input; i++) - { - int res = mpz_init_set_str (a, data[i].input, 0); - if (data[i].decimal) - { - if (res != 0) - { - fprintf (stderr, "mpz_set_str returned -1, input: %s\n", - data[i].input); - abort (); - } - if (mpz_set_str (b, data[i].decimal, 10) != 0) - { - fprintf (stderr, "mpz_set_str returned -1, decimal input: %s\n", - data[i].input); - abort (); - } - if (mpz_cmp (a, b) != 0) - { - fprintf (stderr, "mpz_set_str failed for input: %s\n", - data[i].input); - - dump ("got", a); - dump ("ref", b); - abort (); - } - } - else if (res != -1) - { - fprintf (stderr, "mpz_set_str returned %d, invalid input: %s\n", - res, data[i].input); - abort (); - } - mpz_clear (a); - } - - mpz_clear (b); -} - -void -testmain (int argc, char **argv) -{ - unsigned i; - char *ap; - char *bp; - char *rp; - size_t bn, rn, arn; - - mpz_t a, b; - - FILE *tmp; - - test_small (); - - mpz_init (a); - mpz_init (b); - - tmp = tmpfile (); - if (!tmp) - fprintf (stderr, - "Failed to create temporary file. Skipping mpz_out_str tests.\n"); - - for (i = 0; i < COUNT; i++) - { - int base; - for (base = 0; base <= 36; base += 1 + (base == 0)) - { - hex_random_str_op (MAXBITS, i&1 ? base: -base, &ap, &rp); - if (mpz_set_str (a, ap, 16) != 0) - { - fprintf (stderr, "mpz_set_str failed on input %s\n", ap); - abort (); - } - - rn = strlen (rp); - arn = rn - (rp[0] == '-'); - - bn = mpz_sizeinbase (a, base ? base : 10); - if (bn < arn || bn > (arn + 1)) - { - fprintf (stderr, "mpz_sizeinbase failed:\n"); - dump ("a", a); - fprintf (stderr, "r = %s\n", rp); - fprintf (stderr, " base %d, correct size %u, got %u\n", - base, (unsigned) arn, (unsigned)bn); - abort (); - } - bp = mpz_get_str (NULL, i&1 ? base: -base, a); - if (strcmp (bp, rp)) - { - fprintf (stderr, "mpz_get_str failed:\n"); - dump ("a", a); - fprintf (stderr, "b = %s\n", bp); - fprintf (stderr, " base = %d\n", base); - fprintf (stderr, "r = %s\n", rp); - abort (); - } - - /* Just a few tests with file i/o. */ - if (tmp && i < 20) - { - size_t tn; - rewind (tmp); - tn = mpz_out_str (tmp, i&1 ? base: -base, a); - if (tn != rn) - { - fprintf (stderr, "mpz_out_str, bad return value:\n"); - dump ("a", a); - fprintf (stderr, "r = %s\n", rp); - fprintf (stderr, " base %d, correct size %u, got %u\n", - base, (unsigned) rn, (unsigned)tn); - abort (); - } - rewind (tmp); - memset (bp, 0, rn); - tn = fread (bp, 1, rn, tmp); - if (tn != rn) - { - fprintf (stderr, - "fread failed, expected %lu bytes, got only %lu.\n", - (unsigned long) rn, (unsigned long) tn); - abort (); - } - - if (memcmp (bp, rp, rn) != 0) - { - fprintf (stderr, "mpz_out_str failed:\n"); - dump ("a", a); - fprintf (stderr, "b = %s\n", bp); - fprintf (stderr, " base = %d\n", base); - fprintf (stderr, "r = %s\n", rp); - abort (); - } - } - - mpz_set_str (b, rp, base); - - if (mpz_cmp (a, b)) - { - fprintf (stderr, "mpz_set_str failed:\n"); - fprintf (stderr, "r = %s\n", rp); - fprintf (stderr, " base = %d\n", base); - fprintf (stderr, "r = %s\n", ap); - fprintf (stderr, " base = 16\n"); - dump ("b", b); - dump ("r", a); - abort (); - } - - /* Test mpn interface */ - if (base && mpz_sgn (a)) - { - size_t i; - const char *absr; - mp_limb_t t[MAXLIMBS]; - mp_size_t tn = mpz_size (a); - - assert (tn <= MAXLIMBS); - mpn_copyi (t, a->_mp_d, tn); - - bn = mpn_get_str (bp, base, t, tn); - if (bn != arn) - { - fprintf (stderr, "mpn_get_str failed:\n"); - fprintf (stderr, "returned length: %lu (bad)\n", (unsigned long) bn); - fprintf (stderr, "expected: %lu\n", (unsigned long) arn); - fprintf (stderr, " base = %d\n", base); - fprintf (stderr, "r = %s\n", ap); - fprintf (stderr, " base = 16\n"); - dump ("b", b); - dump ("r", a); - abort (); - } - absr = rp + (rp[0] == '-'); - - for (i = 0; i < bn; i++) - { - unsigned char digit = absr[i]; - unsigned value; - if (digit >= '0' && digit <= '9') - value = digit - '0'; - else if (digit >= 'a' && digit <= 'z') - value = digit - 'a' + 10; - else if (digit >= 'A' && digit <= 'Z') - value = digit - 'A' + 10; - else - { - fprintf (stderr, "Internal error in test.\n"); - abort(); - } - if (bp[i] != value) - { - fprintf (stderr, "mpn_get_str failed:\n"); - fprintf (stderr, "digit %lu: %d (bad)\n", (unsigned long) i, bp[i]); - fprintf (stderr, "expected: %d\n", value); - fprintf (stderr, " base = %d\n", base); - fprintf (stderr, "r = %s\n", ap); - fprintf (stderr, " base = 16\n"); - dump ("b", b); - dump ("r", a); - abort (); - } - } - tn = mpn_set_str (t, bp, bn, base); - if (tn != mpz_size (a) || mpn_cmp (t, a->_mp_d, tn)) - { - fprintf (stderr, "mpn_set_str failed:\n"); - fprintf (stderr, "r = %s\n", rp); - fprintf (stderr, " base = %d\n", base); - fprintf (stderr, "r = %s\n", ap); - fprintf (stderr, " base = 16\n"); - dump ("r", a); - abort (); - } - } - free (ap); - testfree (bp); - } - } - mpz_clear (a); - mpz_clear (b); -} diff --git a/gmp/mini-gmp/tests/t-sub.c b/gmp/mini-gmp/tests/t-sub.c deleted file mode 100644 index e230fda1fb..0000000000 --- a/gmp/mini-gmp/tests/t-sub.c +++ /dev/null @@ -1,71 +0,0 @@ -/* - -Copyright 2012, 2013 Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <stdlib.h> -#include <stdio.h> - -#include "testutils.h" - -#define MAXBITS 400 -#define COUNT 10000 - -void -testmain (int argc, char **argv) -{ - unsigned i; - mpz_t a, b, res, res_ui, ref; - - mpz_init (a); - mpz_init (b); - mpz_init (res); - mpz_init (res_ui); - mpz_init (ref); - - for (i = 0; i < COUNT; i++) - { - mini_random_op3 (OP_SUB, MAXBITS, a, b, ref); - mpz_sub (res, a, b); - if (mpz_cmp (res, ref)) - { - fprintf (stderr, "mpz_sub failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res); - dump ("ref", ref); - abort (); - } - if (mpz_fits_ulong_p (a)) { - mpz_ui_sub (res_ui, mpz_get_ui (a), b); - if (mpz_cmp (res_ui, ref)) - { - fprintf (stderr, "mpz_ui_sub failed:\n"); - dump ("a", a); - dump ("b", b); - dump ("r", res_ui); - dump ("ref", ref); - abort (); - } - } - } - mpz_clear (a); - mpz_clear (b); - mpz_clear (res); - mpz_clear (res_ui); - mpz_clear (ref); -} diff --git a/gmp/mini-gmp/tests/testutils.c b/gmp/mini-gmp/tests/testutils.c deleted file mode 100644 index c3840b36bc..0000000000 --- a/gmp/mini-gmp/tests/testutils.c +++ /dev/null @@ -1,173 +0,0 @@ -/* - -Copyright 2013, 2014, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include "testutils.h" - -/* Include it here, so we we could tweak, e.g., how MPZ_REALLOC - works. */ -#include "../mini-gmp.c" - -static size_t total_alloc = 0; - -/* Custom memory allocation to track memory usage, and add a small red - zone. - - About alignment: In general, getting a block from malloc, and - incrementing it by sizeof(size_t), like we do here, might give a - pointer which is not properly aligned for all types. But the - largest type we allocate space for is unsigned long (mp_limb_t), - which shouldn't have stricter alignment requirements than - size_t. */ - -static char block_end[8] = - { 0x7c, 0x37, 0xd6, 0x12, 0xa8, 0x6c, 0x01, 0xd1 }; - -static void * -block_init (size_t *block, size_t size) -{ - char *p; - *block++ = size; - - p = (char *) block; - memcpy (p + size, block_end, sizeof(block_end)); - - total_alloc += size; - return p; -} - -/* Check small redzone, return pointer to malloced block. */ -static size_t * -block_check (char *p) -{ - size_t *block = (size_t *) p - 1; - size_t size = block[0]; - - if (memcmp (p + size, block_end, sizeof(block_end)) != 0) - { - fprintf (stderr, "red zone overwritten.\n"); - abort (); - } - total_alloc -= size; - return block; -} - -static void * -tu_alloc (size_t size) -{ - size_t *block = malloc (sizeof(size_t) + size + sizeof(block_end)); - if (!block) - { - fprintf (stderr, "Virtual memory exhausted.\n"); - abort (); - } - - return block_init (block, size); -} - -static void * -tu_realloc (void *p, size_t old_size, size_t new_size) -{ - size_t *block = block_check (p); - block = realloc (block, sizeof(size_t) + new_size + sizeof(block_end)); - if (!block) - { - fprintf (stderr, "Virtual memory exhausted.\n"); - abort (); - } - - return block_init (block, new_size); -} - -static void -tu_free (void *p, size_t old_size) -{ - free (block_check (p)); -} - -/* Free memory allocated via mini-gmp allocation function. */ -void -testfree (void *p) -{ - void (*freefunc) (void *, size_t); - mp_get_memory_functions (NULL, NULL, &freefunc); - - freefunc (p, 0); -} - -int -main (int argc, char **argv) -{ - hex_random_init (); - - mp_set_memory_functions (tu_alloc, tu_realloc, tu_free); - - /* Currently, t-comb seems to be the only program accepting any - arguments. It might make sense to parse common arguments here. */ - testmain (argc, argv); - - if (total_alloc != 0) - { - fprintf (stderr, "Memory leaked: %lu bytes.\n", - (unsigned long) total_alloc); - abort (); - } - return 0; -} - -void -testhalves (int count, void (*tested_fun) (int)) -{ - void (*freefunc) (void *, size_t); - void *(*reallocfunc) (void *, size_t, size_t); - void *(*allocfunc) (size_t); - size_t initial_alloc; - - mp_get_memory_functions (&allocfunc, &reallocfunc, &freefunc); - initial_alloc = total_alloc; - (*tested_fun) (count / 2); - if (initial_alloc != total_alloc) - { - fprintf (stderr, "First half, memory leaked: %lu bytes.\n", - (unsigned long) total_alloc - initial_alloc); - abort (); - } - mp_set_memory_functions (NULL, NULL, NULL); - (*tested_fun) (count / 2); - mp_set_memory_functions (allocfunc, reallocfunc, freefunc); -} - -void -dump (const char *label, const mpz_t x) -{ - char *buf = mpz_get_str (NULL, 16, x); - fprintf (stderr, "%s: %s\n", label, buf); - testfree (buf); -} - -void -mpz_set_str_or_abort (mpz_ptr z, const char *str, int base) -{ - if (mpz_set_str (z, str, base) != 0) - { - fprintf (stderr, "ERROR: mpz_set_str failed\n"); - fprintf (stderr, " str = \"%s\"\n", str); - fprintf (stderr, " base = %d\n", base); - abort(); - } -} diff --git a/gmp/mini-gmp/tests/testutils.h b/gmp/mini-gmp/tests/testutils.h deleted file mode 100644 index bc56c06a75..0000000000 --- a/gmp/mini-gmp/tests/testutils.h +++ /dev/null @@ -1,37 +0,0 @@ -/* - -Copyright 2013, 2014, Free Software Foundation, Inc. - -This file is part of the GNU MP Library test suite. - -The GNU MP Library test suite is free software; you can redistribute it -and/or modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 3 of the License, -or (at your option) any later version. - -The GNU MP Library test suite is distributed in the hope that it will be -useful, but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General -Public License for more details. - -You should have received a copy of the GNU General Public License along with -the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ - -#include <stdio.h> -#include <stdlib.h> - -#include "mini-random.h" - -#define numberof(x) (sizeof (x) / sizeof ((x)[0])) - -void testmain (int argc, char **argv); - -void testhalves (int count, void (*tested_fun) (int)); - -void testfree (void *p); - -void -dump (const char *label, const mpz_t x); - -void -mpz_set_str_or_abort (mpz_ptr z, const char *str, int base); |