diff options
Diffstat (limited to 'gmp/tests/mpn')
49 files changed, 7545 insertions, 0 deletions
diff --git a/gmp/tests/mpn/Makefile.am b/gmp/tests/mpn/Makefile.am new file mode 100644 index 0000000000..180c58692c --- /dev/null +++ b/gmp/tests/mpn/Makefile.am @@ -0,0 +1,38 @@ +## Process this file with automake to generate Makefile.in + +# Copyright 2001-2003, 2009-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/. + + +INCLUDES = -I$(top_srcdir) -I$(top_srcdir)/tests +LDADD = $(top_builddir)/tests/libtests.la $(top_builddir)/libgmp.la + +check_PROGRAMS = t-asmtype t-aors_1 t-divrem_1 t-mod_1 t-fat t-get_d \ + t-instrument t-iord_u t-mp_bases t-perfsqr t-scan logic \ + t-toom22 t-toom32 t-toom33 t-toom42 t-toom43 t-toom44 \ + t-toom52 t-toom53 t-toom54 t-toom62 t-toom63 t-toom6h t-toom8h \ + t-toom2-sqr t-toom3-sqr t-toom4-sqr t-toom6-sqr t-toom8-sqr \ + t-mul t-mullo t-mulmod_bnm1 t-sqrmod_bnm1 t-mulmid \ + t-hgcd t-hgcd_appr t-matrix22 t-invert t-div t-bdiv \ + t-broot t-brootinv t-minvert t-sizeinbase + +EXTRA_DIST = toom-shared.h toom-sqr-shared.h + +TESTS = $(check_PROGRAMS) + +$(top_builddir)/tests/libtests.la: + cd $(top_builddir)/tests; $(MAKE) $(AM_MAKEFLAGS) libtests.la diff --git a/gmp/tests/mpn/Makefile.in b/gmp/tests/mpn/Makefile.in new file mode 100644 index 0000000000..5db22d4f0c --- /dev/null +++ b/gmp/tests/mpn/Makefile.in @@ -0,0 +1,1029 @@ +# Makefile.in generated by automake 1.11.6 from Makefile.am. +# @configure_input@ + +# Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, +# 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software +# Foundation, Inc. +# This Makefile.in is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY, to the extent permitted by law; without +# even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# PARTICULAR PURPOSE. + +@SET_MAKE@ + +# Copyright 2001-2003, 2009-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/. +VPATH = @srcdir@ +am__make_dryrun = \ + { \ + am__dry=no; \ + case $$MAKEFLAGS in \ + *\\[\ \ ]*) \ + echo 'am--echo: ; @echo "AM" OK' | $(MAKE) -f - 2>/dev/null \ + | grep '^AM OK$$' >/dev/null || am__dry=yes;; \ + *) \ + for am__flg in $$MAKEFLAGS; do \ + case $$am__flg in \ + *=*|--*) ;; \ + *n*) am__dry=yes; break;; \ + esac; \ + done;; \ + esac; \ + test $$am__dry = yes; \ + } +pkgdatadir = $(datadir)/@PACKAGE@ +pkgincludedir = $(includedir)/@PACKAGE@ +pkglibdir = $(libdir)/@PACKAGE@ +pkglibexecdir = $(libexecdir)/@PACKAGE@ +am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd +install_sh_DATA = $(install_sh) -c -m 644 +install_sh_PROGRAM = $(install_sh) -c +install_sh_SCRIPT = $(install_sh) -c +INSTALL_HEADER = $(INSTALL_DATA) +transform = $(program_transform_name) +NORMAL_INSTALL = : +PRE_INSTALL = : +POST_INSTALL = : +NORMAL_UNINSTALL = : +PRE_UNINSTALL = : +POST_UNINSTALL = : +build_triplet = @build@ +host_triplet = @host@ +check_PROGRAMS = t-asmtype$(EXEEXT) t-aors_1$(EXEEXT) \ + t-divrem_1$(EXEEXT) t-mod_1$(EXEEXT) t-fat$(EXEEXT) \ + t-get_d$(EXEEXT) t-instrument$(EXEEXT) t-iord_u$(EXEEXT) \ + t-mp_bases$(EXEEXT) t-perfsqr$(EXEEXT) t-scan$(EXEEXT) \ + logic$(EXEEXT) t-toom22$(EXEEXT) t-toom32$(EXEEXT) \ + t-toom33$(EXEEXT) t-toom42$(EXEEXT) t-toom43$(EXEEXT) \ + t-toom44$(EXEEXT) t-toom52$(EXEEXT) t-toom53$(EXEEXT) \ + t-toom54$(EXEEXT) t-toom62$(EXEEXT) t-toom63$(EXEEXT) \ + t-toom6h$(EXEEXT) t-toom8h$(EXEEXT) t-toom2-sqr$(EXEEXT) \ + t-toom3-sqr$(EXEEXT) t-toom4-sqr$(EXEEXT) t-toom6-sqr$(EXEEXT) \ + t-toom8-sqr$(EXEEXT) t-mul$(EXEEXT) t-mullo$(EXEEXT) \ + t-mulmod_bnm1$(EXEEXT) t-sqrmod_bnm1$(EXEEXT) \ + t-mulmid$(EXEEXT) t-hgcd$(EXEEXT) t-hgcd_appr$(EXEEXT) \ + t-matrix22$(EXEEXT) t-invert$(EXEEXT) t-div$(EXEEXT) \ + t-bdiv$(EXEEXT) t-broot$(EXEEXT) t-brootinv$(EXEEXT) \ + t-minvert$(EXEEXT) t-sizeinbase$(EXEEXT) +subdir = tests/mpn +DIST_COMMON = $(srcdir)/Makefile.am $(srcdir)/Makefile.in +ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 +am__aclocal_m4_deps = $(top_srcdir)/acinclude.m4 \ + $(top_srcdir)/configure.ac +am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \ + $(ACLOCAL_M4) +mkinstalldirs = $(install_sh) -d +CONFIG_HEADER = $(top_builddir)/config.h +CONFIG_CLEAN_FILES = +CONFIG_CLEAN_VPATH_FILES = +logic_SOURCES = logic.c +logic_OBJECTS = logic.$(OBJEXT) +logic_LDADD = $(LDADD) +logic_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_aors_1_SOURCES = t-aors_1.c +t_aors_1_OBJECTS = t-aors_1.$(OBJEXT) +t_aors_1_LDADD = $(LDADD) +t_aors_1_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_asmtype_SOURCES = t-asmtype.c +t_asmtype_OBJECTS = t-asmtype.$(OBJEXT) +t_asmtype_LDADD = $(LDADD) +t_asmtype_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_bdiv_SOURCES = t-bdiv.c +t_bdiv_OBJECTS = t-bdiv.$(OBJEXT) +t_bdiv_LDADD = $(LDADD) +t_bdiv_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_broot_SOURCES = t-broot.c +t_broot_OBJECTS = t-broot.$(OBJEXT) +t_broot_LDADD = $(LDADD) +t_broot_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_brootinv_SOURCES = t-brootinv.c +t_brootinv_OBJECTS = t-brootinv.$(OBJEXT) +t_brootinv_LDADD = $(LDADD) +t_brootinv_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_div_SOURCES = t-div.c +t_div_OBJECTS = t-div.$(OBJEXT) +t_div_LDADD = $(LDADD) +t_div_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_divrem_1_SOURCES = t-divrem_1.c +t_divrem_1_OBJECTS = t-divrem_1.$(OBJEXT) +t_divrem_1_LDADD = $(LDADD) +t_divrem_1_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_fat_SOURCES = t-fat.c +t_fat_OBJECTS = t-fat.$(OBJEXT) +t_fat_LDADD = $(LDADD) +t_fat_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_get_d_SOURCES = t-get_d.c +t_get_d_OBJECTS = t-get_d.$(OBJEXT) +t_get_d_LDADD = $(LDADD) +t_get_d_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_hgcd_SOURCES = t-hgcd.c +t_hgcd_OBJECTS = t-hgcd.$(OBJEXT) +t_hgcd_LDADD = $(LDADD) +t_hgcd_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_hgcd_appr_SOURCES = t-hgcd_appr.c +t_hgcd_appr_OBJECTS = t-hgcd_appr.$(OBJEXT) +t_hgcd_appr_LDADD = $(LDADD) +t_hgcd_appr_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_instrument_SOURCES = t-instrument.c +t_instrument_OBJECTS = t-instrument.$(OBJEXT) +t_instrument_LDADD = $(LDADD) +t_instrument_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_invert_SOURCES = t-invert.c +t_invert_OBJECTS = t-invert.$(OBJEXT) +t_invert_LDADD = $(LDADD) +t_invert_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_iord_u_SOURCES = t-iord_u.c +t_iord_u_OBJECTS = t-iord_u.$(OBJEXT) +t_iord_u_LDADD = $(LDADD) +t_iord_u_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_matrix22_SOURCES = t-matrix22.c +t_matrix22_OBJECTS = t-matrix22.$(OBJEXT) +t_matrix22_LDADD = $(LDADD) +t_matrix22_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_minvert_SOURCES = t-minvert.c +t_minvert_OBJECTS = t-minvert.$(OBJEXT) +t_minvert_LDADD = $(LDADD) +t_minvert_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_mod_1_SOURCES = t-mod_1.c +t_mod_1_OBJECTS = t-mod_1.$(OBJEXT) +t_mod_1_LDADD = $(LDADD) +t_mod_1_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_mp_bases_SOURCES = t-mp_bases.c +t_mp_bases_OBJECTS = t-mp_bases.$(OBJEXT) +t_mp_bases_LDADD = $(LDADD) +t_mp_bases_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_mul_SOURCES = t-mul.c +t_mul_OBJECTS = t-mul.$(OBJEXT) +t_mul_LDADD = $(LDADD) +t_mul_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_mullo_SOURCES = t-mullo.c +t_mullo_OBJECTS = t-mullo.$(OBJEXT) +t_mullo_LDADD = $(LDADD) +t_mullo_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_mulmid_SOURCES = t-mulmid.c +t_mulmid_OBJECTS = t-mulmid.$(OBJEXT) +t_mulmid_LDADD = $(LDADD) +t_mulmid_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_mulmod_bnm1_SOURCES = t-mulmod_bnm1.c +t_mulmod_bnm1_OBJECTS = t-mulmod_bnm1.$(OBJEXT) +t_mulmod_bnm1_LDADD = $(LDADD) +t_mulmod_bnm1_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_perfsqr_SOURCES = t-perfsqr.c +t_perfsqr_OBJECTS = t-perfsqr.$(OBJEXT) +t_perfsqr_LDADD = $(LDADD) +t_perfsqr_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_scan_SOURCES = t-scan.c +t_scan_OBJECTS = t-scan.$(OBJEXT) +t_scan_LDADD = $(LDADD) +t_scan_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_sizeinbase_SOURCES = t-sizeinbase.c +t_sizeinbase_OBJECTS = t-sizeinbase.$(OBJEXT) +t_sizeinbase_LDADD = $(LDADD) +t_sizeinbase_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_sqrmod_bnm1_SOURCES = t-sqrmod_bnm1.c +t_sqrmod_bnm1_OBJECTS = t-sqrmod_bnm1.$(OBJEXT) +t_sqrmod_bnm1_LDADD = $(LDADD) +t_sqrmod_bnm1_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom2_sqr_SOURCES = t-toom2-sqr.c +t_toom2_sqr_OBJECTS = t-toom2-sqr.$(OBJEXT) +t_toom2_sqr_LDADD = $(LDADD) +t_toom2_sqr_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom22_SOURCES = t-toom22.c +t_toom22_OBJECTS = t-toom22.$(OBJEXT) +t_toom22_LDADD = $(LDADD) +t_toom22_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom3_sqr_SOURCES = t-toom3-sqr.c +t_toom3_sqr_OBJECTS = t-toom3-sqr.$(OBJEXT) +t_toom3_sqr_LDADD = $(LDADD) +t_toom3_sqr_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom32_SOURCES = t-toom32.c +t_toom32_OBJECTS = t-toom32.$(OBJEXT) +t_toom32_LDADD = $(LDADD) +t_toom32_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom33_SOURCES = t-toom33.c +t_toom33_OBJECTS = t-toom33.$(OBJEXT) +t_toom33_LDADD = $(LDADD) +t_toom33_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom4_sqr_SOURCES = t-toom4-sqr.c +t_toom4_sqr_OBJECTS = t-toom4-sqr.$(OBJEXT) +t_toom4_sqr_LDADD = $(LDADD) +t_toom4_sqr_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom42_SOURCES = t-toom42.c +t_toom42_OBJECTS = t-toom42.$(OBJEXT) +t_toom42_LDADD = $(LDADD) +t_toom42_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom43_SOURCES = t-toom43.c +t_toom43_OBJECTS = t-toom43.$(OBJEXT) +t_toom43_LDADD = $(LDADD) +t_toom43_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom44_SOURCES = t-toom44.c +t_toom44_OBJECTS = t-toom44.$(OBJEXT) +t_toom44_LDADD = $(LDADD) +t_toom44_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom52_SOURCES = t-toom52.c +t_toom52_OBJECTS = t-toom52.$(OBJEXT) +t_toom52_LDADD = $(LDADD) +t_toom52_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom53_SOURCES = t-toom53.c +t_toom53_OBJECTS = t-toom53.$(OBJEXT) +t_toom53_LDADD = $(LDADD) +t_toom53_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom54_SOURCES = t-toom54.c +t_toom54_OBJECTS = t-toom54.$(OBJEXT) +t_toom54_LDADD = $(LDADD) +t_toom54_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom6_sqr_SOURCES = t-toom6-sqr.c +t_toom6_sqr_OBJECTS = t-toom6-sqr.$(OBJEXT) +t_toom6_sqr_LDADD = $(LDADD) +t_toom6_sqr_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom62_SOURCES = t-toom62.c +t_toom62_OBJECTS = t-toom62.$(OBJEXT) +t_toom62_LDADD = $(LDADD) +t_toom62_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom63_SOURCES = t-toom63.c +t_toom63_OBJECTS = t-toom63.$(OBJEXT) +t_toom63_LDADD = $(LDADD) +t_toom63_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom6h_SOURCES = t-toom6h.c +t_toom6h_OBJECTS = t-toom6h.$(OBJEXT) +t_toom6h_LDADD = $(LDADD) +t_toom6h_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom8_sqr_SOURCES = t-toom8-sqr.c +t_toom8_sqr_OBJECTS = t-toom8-sqr.$(OBJEXT) +t_toom8_sqr_LDADD = $(LDADD) +t_toom8_sqr_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +t_toom8h_SOURCES = t-toom8h.c +t_toom8h_OBJECTS = t-toom8h.$(OBJEXT) +t_toom8h_LDADD = $(LDADD) +t_toom8h_DEPENDENCIES = $(top_builddir)/tests/libtests.la \ + $(top_builddir)/libgmp.la +DEFAULT_INCLUDES = -I.@am__isrc@ -I$(top_builddir) +depcomp = +am__depfiles_maybe = +COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \ + $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +LTCOMPILE = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \ + --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) \ + $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +CCLD = $(CC) +LINK = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \ + --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \ + $(LDFLAGS) -o $@ +SOURCES = logic.c t-aors_1.c t-asmtype.c t-bdiv.c t-broot.c \ + t-brootinv.c t-div.c t-divrem_1.c t-fat.c t-get_d.c t-hgcd.c \ + t-hgcd_appr.c t-instrument.c t-invert.c t-iord_u.c \ + t-matrix22.c t-minvert.c t-mod_1.c t-mp_bases.c t-mul.c \ + t-mullo.c t-mulmid.c t-mulmod_bnm1.c t-perfsqr.c t-scan.c \ + t-sizeinbase.c t-sqrmod_bnm1.c t-toom2-sqr.c t-toom22.c \ + t-toom3-sqr.c t-toom32.c t-toom33.c t-toom4-sqr.c t-toom42.c \ + t-toom43.c t-toom44.c t-toom52.c t-toom53.c t-toom54.c \ + t-toom6-sqr.c t-toom62.c t-toom63.c t-toom6h.c t-toom8-sqr.c \ + t-toom8h.c +DIST_SOURCES = logic.c t-aors_1.c t-asmtype.c t-bdiv.c t-broot.c \ + t-brootinv.c t-div.c t-divrem_1.c t-fat.c t-get_d.c t-hgcd.c \ + t-hgcd_appr.c t-instrument.c t-invert.c t-iord_u.c \ + t-matrix22.c t-minvert.c t-mod_1.c t-mp_bases.c t-mul.c \ + t-mullo.c t-mulmid.c t-mulmod_bnm1.c t-perfsqr.c t-scan.c \ + t-sizeinbase.c t-sqrmod_bnm1.c t-toom2-sqr.c t-toom22.c \ + t-toom3-sqr.c t-toom32.c t-toom33.c t-toom4-sqr.c t-toom42.c \ + t-toom43.c t-toom44.c t-toom52.c t-toom53.c t-toom54.c \ + t-toom6-sqr.c t-toom62.c t-toom63.c t-toom6h.c t-toom8-sqr.c \ + t-toom8h.c +am__can_run_installinfo = \ + case $$AM_UPDATE_INFO_DIR in \ + n|no|NO) false;; \ + *) (install-info --version) >/dev/null 2>&1;; \ + esac +ETAGS = etags +CTAGS = ctags +am__tty_colors = \ +red=; grn=; lgn=; blu=; std= +DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) +ABI = @ABI@ +ACLOCAL = @ACLOCAL@ +AMTAR = @AMTAR@ +AR = @AR@ +AS = @AS@ +ASMFLAGS = @ASMFLAGS@ +AUTOCONF = @AUTOCONF@ +AUTOHEADER = @AUTOHEADER@ +AUTOMAKE = @AUTOMAKE@ +AWK = @AWK@ +CALLING_CONVENTIONS_OBJS = @CALLING_CONVENTIONS_OBJS@ +CC = @CC@ +CCAS = @CCAS@ +CC_FOR_BUILD = @CC_FOR_BUILD@ +CFLAGS = @CFLAGS@ +CPP = @CPP@ +CPPFLAGS = @CPPFLAGS@ +CPP_FOR_BUILD = @CPP_FOR_BUILD@ +CXX = @CXX@ +CXXCPP = @CXXCPP@ +CXXFLAGS = @CXXFLAGS@ +CYGPATH_W = @CYGPATH_W@ +DEFN_LONG_LONG_LIMB = @DEFN_LONG_LONG_LIMB@ +DEFS = @DEFS@ +DLLTOOL = @DLLTOOL@ +DSYMUTIL = @DSYMUTIL@ +DUMPBIN = @DUMPBIN@ +ECHO_C = @ECHO_C@ +ECHO_N = @ECHO_N@ +ECHO_T = @ECHO_T@ +EGREP = @EGREP@ +EXEEXT = @EXEEXT@ +EXEEXT_FOR_BUILD = @EXEEXT_FOR_BUILD@ +FGREP = @FGREP@ +GMP_LDFLAGS = @GMP_LDFLAGS@ +GMP_LIMB_BITS = @GMP_LIMB_BITS@ +GMP_NAIL_BITS = @GMP_NAIL_BITS@ +GREP = @GREP@ +HAVE_CLOCK_01 = @HAVE_CLOCK_01@ +HAVE_CPUTIME_01 = @HAVE_CPUTIME_01@ +HAVE_GETRUSAGE_01 = @HAVE_GETRUSAGE_01@ +HAVE_GETTIMEOFDAY_01 = @HAVE_GETTIMEOFDAY_01@ +HAVE_HOST_CPU_FAMILY_power = @HAVE_HOST_CPU_FAMILY_power@ +HAVE_HOST_CPU_FAMILY_powerpc = @HAVE_HOST_CPU_FAMILY_powerpc@ +HAVE_SIGACTION_01 = @HAVE_SIGACTION_01@ +HAVE_SIGALTSTACK_01 = @HAVE_SIGALTSTACK_01@ +HAVE_SIGSTACK_01 = @HAVE_SIGSTACK_01@ +HAVE_STACK_T_01 = @HAVE_STACK_T_01@ +HAVE_SYS_RESOURCE_H_01 = @HAVE_SYS_RESOURCE_H_01@ +INSTALL = @INSTALL@ +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@ +LD = @LD@ +LDFLAGS = @LDFLAGS@ +LEX = @LEX@ +LEXLIB = @LEXLIB@ +LEX_OUTPUT_ROOT = @LEX_OUTPUT_ROOT@ +LIBCURSES = @LIBCURSES@ +LIBGMPXX_LDFLAGS = @LIBGMPXX_LDFLAGS@ +LIBGMP_DLL = @LIBGMP_DLL@ +LIBGMP_LDFLAGS = @LIBGMP_LDFLAGS@ +LIBM = @LIBM@ +LIBM_FOR_BUILD = @LIBM_FOR_BUILD@ +LIBOBJS = @LIBOBJS@ +LIBREADLINE = @LIBREADLINE@ +LIBS = @LIBS@ +LIBTOOL = @LIBTOOL@ +LIPO = @LIPO@ +LN_S = @LN_S@ +LTLIBOBJS = @LTLIBOBJS@ +M4 = @M4@ +MAINT = @MAINT@ +MAKEINFO = @MAKEINFO@ +MANIFEST_TOOL = @MANIFEST_TOOL@ +MKDIR_P = @MKDIR_P@ +NM = @NM@ +NMEDIT = @NMEDIT@ +OBJDUMP = @OBJDUMP@ +OBJEXT = @OBJEXT@ +OTOOL = @OTOOL@ +OTOOL64 = @OTOOL64@ +PACKAGE = @PACKAGE@ +PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@ +PACKAGE_NAME = @PACKAGE_NAME@ +PACKAGE_STRING = @PACKAGE_STRING@ +PACKAGE_TARNAME = @PACKAGE_TARNAME@ +PACKAGE_URL = @PACKAGE_URL@ +PACKAGE_VERSION = @PACKAGE_VERSION@ +PATH_SEPARATOR = @PATH_SEPARATOR@ +RANLIB = @RANLIB@ +SED = @SED@ +SET_MAKE = @SET_MAKE@ +SHELL = @SHELL@ +SPEED_CYCLECOUNTER_OBJ = @SPEED_CYCLECOUNTER_OBJ@ +STRIP = @STRIP@ +TAL_OBJECT = @TAL_OBJECT@ +TUNE_LIBS = @TUNE_LIBS@ +TUNE_SQR_OBJ = @TUNE_SQR_OBJ@ +U_FOR_BUILD = @U_FOR_BUILD@ +VERSION = @VERSION@ +WITH_READLINE_01 = @WITH_READLINE_01@ +YACC = @YACC@ +YFLAGS = @YFLAGS@ +abs_builddir = @abs_builddir@ +abs_srcdir = @abs_srcdir@ +abs_top_builddir = @abs_top_builddir@ +abs_top_srcdir = @abs_top_srcdir@ +ac_ct_AR = @ac_ct_AR@ +ac_ct_CC = @ac_ct_CC@ +ac_ct_CXX = @ac_ct_CXX@ +ac_ct_DUMPBIN = @ac_ct_DUMPBIN@ +am__leading_dot = @am__leading_dot@ +am__tar = @am__tar@ +am__untar = @am__untar@ +bindir = @bindir@ +build = @build@ +build_alias = @build_alias@ +build_cpu = @build_cpu@ +build_os = @build_os@ +build_vendor = @build_vendor@ +builddir = @builddir@ +datadir = @datadir@ +datarootdir = @datarootdir@ +docdir = @docdir@ +dvidir = @dvidir@ +exec_prefix = @exec_prefix@ +gmp_srclinks = @gmp_srclinks@ +host = @host@ +host_alias = @host_alias@ +host_cpu = @host_cpu@ +host_os = @host_os@ +host_vendor = @host_vendor@ +htmldir = @htmldir@ +includedir = @includedir@ +infodir = @infodir@ +install_sh = @install_sh@ +libdir = @libdir@ +libexecdir = @libexecdir@ +localedir = @localedir@ +localstatedir = @localstatedir@ +mandir = @mandir@ +mkdir_p = @mkdir_p@ +mpn_objects = @mpn_objects@ +mpn_objs_in_libgmp = @mpn_objs_in_libgmp@ +oldincludedir = @oldincludedir@ +pdfdir = @pdfdir@ +prefix = @prefix@ +program_transform_name = @program_transform_name@ +psdir = @psdir@ +sbindir = @sbindir@ +sharedstatedir = @sharedstatedir@ +srcdir = @srcdir@ +sysconfdir = @sysconfdir@ +target_alias = @target_alias@ +top_build_prefix = @top_build_prefix@ +top_builddir = @top_builddir@ +top_srcdir = @top_srcdir@ +INCLUDES = -I$(top_srcdir) -I$(top_srcdir)/tests +LDADD = $(top_builddir)/tests/libtests.la $(top_builddir)/libgmp.la +EXTRA_DIST = toom-shared.h toom-sqr-shared.h +TESTS = $(check_PROGRAMS) +all: all-am + +.SUFFIXES: +.SUFFIXES: .c .lo .o .obj +$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ $(srcdir)/Makefile.am $(am__configure_deps) + @for dep in $?; do \ + case '$(am__configure_deps)' in \ + *$$dep*) \ + ( cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh ) \ + && { if test -f $@; then exit 0; else break; fi; }; \ + exit 1;; \ + esac; \ + done; \ + echo ' cd $(top_srcdir) && $(AUTOMAKE) --gnu --ignore-deps tests/mpn/Makefile'; \ + $(am__cd) $(top_srcdir) && \ + $(AUTOMAKE) --gnu --ignore-deps tests/mpn/Makefile +.PRECIOUS: Makefile +Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status + @case '$?' in \ + *config.status*) \ + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \ + *) \ + echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \ + cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \ + esac; + +$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh + +$(top_srcdir)/configure: @MAINTAINER_MODE_TRUE@ $(am__configure_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(ACLOCAL_M4): @MAINTAINER_MODE_TRUE@ $(am__aclocal_m4_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(am__aclocal_m4_deps): + +clean-checkPROGRAMS: + @list='$(check_PROGRAMS)'; test -n "$$list" || exit 0; \ + echo " rm -f" $$list; \ + rm -f $$list || exit $$?; \ + test -n "$(EXEEXT)" || exit 0; \ + list=`for p in $$list; do echo "$$p"; done | sed 's/$(EXEEXT)$$//'`; \ + echo " rm -f" $$list; \ + rm -f $$list +logic$(EXEEXT): $(logic_OBJECTS) $(logic_DEPENDENCIES) $(EXTRA_logic_DEPENDENCIES) + @rm -f logic$(EXEEXT) + $(LINK) $(logic_OBJECTS) $(logic_LDADD) $(LIBS) +t-aors_1$(EXEEXT): $(t_aors_1_OBJECTS) $(t_aors_1_DEPENDENCIES) $(EXTRA_t_aors_1_DEPENDENCIES) + @rm -f t-aors_1$(EXEEXT) + $(LINK) $(t_aors_1_OBJECTS) $(t_aors_1_LDADD) $(LIBS) +t-asmtype$(EXEEXT): $(t_asmtype_OBJECTS) $(t_asmtype_DEPENDENCIES) $(EXTRA_t_asmtype_DEPENDENCIES) + @rm -f t-asmtype$(EXEEXT) + $(LINK) $(t_asmtype_OBJECTS) $(t_asmtype_LDADD) $(LIBS) +t-bdiv$(EXEEXT): $(t_bdiv_OBJECTS) $(t_bdiv_DEPENDENCIES) $(EXTRA_t_bdiv_DEPENDENCIES) + @rm -f t-bdiv$(EXEEXT) + $(LINK) $(t_bdiv_OBJECTS) $(t_bdiv_LDADD) $(LIBS) +t-broot$(EXEEXT): $(t_broot_OBJECTS) $(t_broot_DEPENDENCIES) $(EXTRA_t_broot_DEPENDENCIES) + @rm -f t-broot$(EXEEXT) + $(LINK) $(t_broot_OBJECTS) $(t_broot_LDADD) $(LIBS) +t-brootinv$(EXEEXT): $(t_brootinv_OBJECTS) $(t_brootinv_DEPENDENCIES) $(EXTRA_t_brootinv_DEPENDENCIES) + @rm -f t-brootinv$(EXEEXT) + $(LINK) $(t_brootinv_OBJECTS) $(t_brootinv_LDADD) $(LIBS) +t-div$(EXEEXT): $(t_div_OBJECTS) $(t_div_DEPENDENCIES) $(EXTRA_t_div_DEPENDENCIES) + @rm -f t-div$(EXEEXT) + $(LINK) $(t_div_OBJECTS) $(t_div_LDADD) $(LIBS) +t-divrem_1$(EXEEXT): $(t_divrem_1_OBJECTS) $(t_divrem_1_DEPENDENCIES) $(EXTRA_t_divrem_1_DEPENDENCIES) + @rm -f t-divrem_1$(EXEEXT) + $(LINK) $(t_divrem_1_OBJECTS) $(t_divrem_1_LDADD) $(LIBS) +t-fat$(EXEEXT): $(t_fat_OBJECTS) $(t_fat_DEPENDENCIES) $(EXTRA_t_fat_DEPENDENCIES) + @rm -f t-fat$(EXEEXT) + $(LINK) $(t_fat_OBJECTS) $(t_fat_LDADD) $(LIBS) +t-get_d$(EXEEXT): $(t_get_d_OBJECTS) $(t_get_d_DEPENDENCIES) $(EXTRA_t_get_d_DEPENDENCIES) + @rm -f t-get_d$(EXEEXT) + $(LINK) $(t_get_d_OBJECTS) $(t_get_d_LDADD) $(LIBS) +t-hgcd$(EXEEXT): $(t_hgcd_OBJECTS) $(t_hgcd_DEPENDENCIES) $(EXTRA_t_hgcd_DEPENDENCIES) + @rm -f t-hgcd$(EXEEXT) + $(LINK) $(t_hgcd_OBJECTS) $(t_hgcd_LDADD) $(LIBS) +t-hgcd_appr$(EXEEXT): $(t_hgcd_appr_OBJECTS) $(t_hgcd_appr_DEPENDENCIES) $(EXTRA_t_hgcd_appr_DEPENDENCIES) + @rm -f t-hgcd_appr$(EXEEXT) + $(LINK) $(t_hgcd_appr_OBJECTS) $(t_hgcd_appr_LDADD) $(LIBS) +t-instrument$(EXEEXT): $(t_instrument_OBJECTS) $(t_instrument_DEPENDENCIES) $(EXTRA_t_instrument_DEPENDENCIES) + @rm -f t-instrument$(EXEEXT) + $(LINK) $(t_instrument_OBJECTS) $(t_instrument_LDADD) $(LIBS) +t-invert$(EXEEXT): $(t_invert_OBJECTS) $(t_invert_DEPENDENCIES) $(EXTRA_t_invert_DEPENDENCIES) + @rm -f t-invert$(EXEEXT) + $(LINK) $(t_invert_OBJECTS) $(t_invert_LDADD) $(LIBS) +t-iord_u$(EXEEXT): $(t_iord_u_OBJECTS) $(t_iord_u_DEPENDENCIES) $(EXTRA_t_iord_u_DEPENDENCIES) + @rm -f t-iord_u$(EXEEXT) + $(LINK) $(t_iord_u_OBJECTS) $(t_iord_u_LDADD) $(LIBS) +t-matrix22$(EXEEXT): $(t_matrix22_OBJECTS) $(t_matrix22_DEPENDENCIES) $(EXTRA_t_matrix22_DEPENDENCIES) + @rm -f t-matrix22$(EXEEXT) + $(LINK) $(t_matrix22_OBJECTS) $(t_matrix22_LDADD) $(LIBS) +t-minvert$(EXEEXT): $(t_minvert_OBJECTS) $(t_minvert_DEPENDENCIES) $(EXTRA_t_minvert_DEPENDENCIES) + @rm -f t-minvert$(EXEEXT) + $(LINK) $(t_minvert_OBJECTS) $(t_minvert_LDADD) $(LIBS) +t-mod_1$(EXEEXT): $(t_mod_1_OBJECTS) $(t_mod_1_DEPENDENCIES) $(EXTRA_t_mod_1_DEPENDENCIES) + @rm -f t-mod_1$(EXEEXT) + $(LINK) $(t_mod_1_OBJECTS) $(t_mod_1_LDADD) $(LIBS) +t-mp_bases$(EXEEXT): $(t_mp_bases_OBJECTS) $(t_mp_bases_DEPENDENCIES) $(EXTRA_t_mp_bases_DEPENDENCIES) + @rm -f t-mp_bases$(EXEEXT) + $(LINK) $(t_mp_bases_OBJECTS) $(t_mp_bases_LDADD) $(LIBS) +t-mul$(EXEEXT): $(t_mul_OBJECTS) $(t_mul_DEPENDENCIES) $(EXTRA_t_mul_DEPENDENCIES) + @rm -f t-mul$(EXEEXT) + $(LINK) $(t_mul_OBJECTS) $(t_mul_LDADD) $(LIBS) +t-mullo$(EXEEXT): $(t_mullo_OBJECTS) $(t_mullo_DEPENDENCIES) $(EXTRA_t_mullo_DEPENDENCIES) + @rm -f t-mullo$(EXEEXT) + $(LINK) $(t_mullo_OBJECTS) $(t_mullo_LDADD) $(LIBS) +t-mulmid$(EXEEXT): $(t_mulmid_OBJECTS) $(t_mulmid_DEPENDENCIES) $(EXTRA_t_mulmid_DEPENDENCIES) + @rm -f t-mulmid$(EXEEXT) + $(LINK) $(t_mulmid_OBJECTS) $(t_mulmid_LDADD) $(LIBS) +t-mulmod_bnm1$(EXEEXT): $(t_mulmod_bnm1_OBJECTS) $(t_mulmod_bnm1_DEPENDENCIES) $(EXTRA_t_mulmod_bnm1_DEPENDENCIES) + @rm -f t-mulmod_bnm1$(EXEEXT) + $(LINK) $(t_mulmod_bnm1_OBJECTS) $(t_mulmod_bnm1_LDADD) $(LIBS) +t-perfsqr$(EXEEXT): $(t_perfsqr_OBJECTS) $(t_perfsqr_DEPENDENCIES) $(EXTRA_t_perfsqr_DEPENDENCIES) + @rm -f t-perfsqr$(EXEEXT) + $(LINK) $(t_perfsqr_OBJECTS) $(t_perfsqr_LDADD) $(LIBS) +t-scan$(EXEEXT): $(t_scan_OBJECTS) $(t_scan_DEPENDENCIES) $(EXTRA_t_scan_DEPENDENCIES) + @rm -f t-scan$(EXEEXT) + $(LINK) $(t_scan_OBJECTS) $(t_scan_LDADD) $(LIBS) +t-sizeinbase$(EXEEXT): $(t_sizeinbase_OBJECTS) $(t_sizeinbase_DEPENDENCIES) $(EXTRA_t_sizeinbase_DEPENDENCIES) + @rm -f t-sizeinbase$(EXEEXT) + $(LINK) $(t_sizeinbase_OBJECTS) $(t_sizeinbase_LDADD) $(LIBS) +t-sqrmod_bnm1$(EXEEXT): $(t_sqrmod_bnm1_OBJECTS) $(t_sqrmod_bnm1_DEPENDENCIES) $(EXTRA_t_sqrmod_bnm1_DEPENDENCIES) + @rm -f t-sqrmod_bnm1$(EXEEXT) + $(LINK) $(t_sqrmod_bnm1_OBJECTS) $(t_sqrmod_bnm1_LDADD) $(LIBS) +t-toom2-sqr$(EXEEXT): $(t_toom2_sqr_OBJECTS) $(t_toom2_sqr_DEPENDENCIES) $(EXTRA_t_toom2_sqr_DEPENDENCIES) + @rm -f t-toom2-sqr$(EXEEXT) + $(LINK) $(t_toom2_sqr_OBJECTS) $(t_toom2_sqr_LDADD) $(LIBS) +t-toom22$(EXEEXT): $(t_toom22_OBJECTS) $(t_toom22_DEPENDENCIES) $(EXTRA_t_toom22_DEPENDENCIES) + @rm -f t-toom22$(EXEEXT) + $(LINK) $(t_toom22_OBJECTS) $(t_toom22_LDADD) $(LIBS) +t-toom3-sqr$(EXEEXT): $(t_toom3_sqr_OBJECTS) $(t_toom3_sqr_DEPENDENCIES) $(EXTRA_t_toom3_sqr_DEPENDENCIES) + @rm -f t-toom3-sqr$(EXEEXT) + $(LINK) $(t_toom3_sqr_OBJECTS) $(t_toom3_sqr_LDADD) $(LIBS) +t-toom32$(EXEEXT): $(t_toom32_OBJECTS) $(t_toom32_DEPENDENCIES) $(EXTRA_t_toom32_DEPENDENCIES) + @rm -f t-toom32$(EXEEXT) + $(LINK) $(t_toom32_OBJECTS) $(t_toom32_LDADD) $(LIBS) +t-toom33$(EXEEXT): $(t_toom33_OBJECTS) $(t_toom33_DEPENDENCIES) $(EXTRA_t_toom33_DEPENDENCIES) + @rm -f t-toom33$(EXEEXT) + $(LINK) $(t_toom33_OBJECTS) $(t_toom33_LDADD) $(LIBS) +t-toom4-sqr$(EXEEXT): $(t_toom4_sqr_OBJECTS) $(t_toom4_sqr_DEPENDENCIES) $(EXTRA_t_toom4_sqr_DEPENDENCIES) + @rm -f t-toom4-sqr$(EXEEXT) + $(LINK) $(t_toom4_sqr_OBJECTS) $(t_toom4_sqr_LDADD) $(LIBS) +t-toom42$(EXEEXT): $(t_toom42_OBJECTS) $(t_toom42_DEPENDENCIES) $(EXTRA_t_toom42_DEPENDENCIES) + @rm -f t-toom42$(EXEEXT) + $(LINK) $(t_toom42_OBJECTS) $(t_toom42_LDADD) $(LIBS) +t-toom43$(EXEEXT): $(t_toom43_OBJECTS) $(t_toom43_DEPENDENCIES) $(EXTRA_t_toom43_DEPENDENCIES) + @rm -f t-toom43$(EXEEXT) + $(LINK) $(t_toom43_OBJECTS) $(t_toom43_LDADD) $(LIBS) +t-toom44$(EXEEXT): $(t_toom44_OBJECTS) $(t_toom44_DEPENDENCIES) $(EXTRA_t_toom44_DEPENDENCIES) + @rm -f t-toom44$(EXEEXT) + $(LINK) $(t_toom44_OBJECTS) $(t_toom44_LDADD) $(LIBS) +t-toom52$(EXEEXT): $(t_toom52_OBJECTS) $(t_toom52_DEPENDENCIES) $(EXTRA_t_toom52_DEPENDENCIES) + @rm -f t-toom52$(EXEEXT) + $(LINK) $(t_toom52_OBJECTS) $(t_toom52_LDADD) $(LIBS) +t-toom53$(EXEEXT): $(t_toom53_OBJECTS) $(t_toom53_DEPENDENCIES) $(EXTRA_t_toom53_DEPENDENCIES) + @rm -f t-toom53$(EXEEXT) + $(LINK) $(t_toom53_OBJECTS) $(t_toom53_LDADD) $(LIBS) +t-toom54$(EXEEXT): $(t_toom54_OBJECTS) $(t_toom54_DEPENDENCIES) $(EXTRA_t_toom54_DEPENDENCIES) + @rm -f t-toom54$(EXEEXT) + $(LINK) $(t_toom54_OBJECTS) $(t_toom54_LDADD) $(LIBS) +t-toom6-sqr$(EXEEXT): $(t_toom6_sqr_OBJECTS) $(t_toom6_sqr_DEPENDENCIES) $(EXTRA_t_toom6_sqr_DEPENDENCIES) + @rm -f t-toom6-sqr$(EXEEXT) + $(LINK) $(t_toom6_sqr_OBJECTS) $(t_toom6_sqr_LDADD) $(LIBS) +t-toom62$(EXEEXT): $(t_toom62_OBJECTS) $(t_toom62_DEPENDENCIES) $(EXTRA_t_toom62_DEPENDENCIES) + @rm -f t-toom62$(EXEEXT) + $(LINK) $(t_toom62_OBJECTS) $(t_toom62_LDADD) $(LIBS) +t-toom63$(EXEEXT): $(t_toom63_OBJECTS) $(t_toom63_DEPENDENCIES) $(EXTRA_t_toom63_DEPENDENCIES) + @rm -f t-toom63$(EXEEXT) + $(LINK) $(t_toom63_OBJECTS) $(t_toom63_LDADD) $(LIBS) +t-toom6h$(EXEEXT): $(t_toom6h_OBJECTS) $(t_toom6h_DEPENDENCIES) $(EXTRA_t_toom6h_DEPENDENCIES) + @rm -f t-toom6h$(EXEEXT) + $(LINK) $(t_toom6h_OBJECTS) $(t_toom6h_LDADD) $(LIBS) +t-toom8-sqr$(EXEEXT): $(t_toom8_sqr_OBJECTS) $(t_toom8_sqr_DEPENDENCIES) $(EXTRA_t_toom8_sqr_DEPENDENCIES) + @rm -f t-toom8-sqr$(EXEEXT) + $(LINK) $(t_toom8_sqr_OBJECTS) $(t_toom8_sqr_LDADD) $(LIBS) +t-toom8h$(EXEEXT): $(t_toom8h_OBJECTS) $(t_toom8h_DEPENDENCIES) $(EXTRA_t_toom8h_DEPENDENCIES) + @rm -f t-toom8h$(EXEEXT) + $(LINK) $(t_toom8h_OBJECTS) $(t_toom8h_LDADD) $(LIBS) + +mostlyclean-compile: + -rm -f *.$(OBJEXT) + +distclean-compile: + -rm -f *.tab.c + +.c.o: + $(COMPILE) -c $< + +.c.obj: + $(COMPILE) -c `$(CYGPATH_W) '$<'` + +.c.lo: + $(LTCOMPILE) -c -o $@ $< + +mostlyclean-libtool: + -rm -f *.lo + +clean-libtool: + -rm -rf .libs _libs + +ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES) + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + mkid -fID $$unique +tags: TAGS + +TAGS: $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \ + $(TAGS_FILES) $(LISP) + set x; \ + here=`pwd`; \ + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + shift; \ + if test -z "$(ETAGS_ARGS)$$*$$unique"; then :; else \ + test -n "$$unique" || unique=$$empty_fix; \ + if test $$# -gt 0; then \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + "$$@" $$unique; \ + else \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + $$unique; \ + fi; \ + fi +ctags: CTAGS +CTAGS: $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \ + $(TAGS_FILES) $(LISP) + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + test -z "$(CTAGS_ARGS)$$unique" \ + || $(CTAGS) $(CTAGSFLAGS) $(AM_CTAGSFLAGS) $(CTAGS_ARGS) \ + $$unique + +GTAGS: + here=`$(am__cd) $(top_builddir) && pwd` \ + && $(am__cd) $(top_srcdir) \ + && gtags -i $(GTAGS_ARGS) "$$here" + +distclean-tags: + -rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags + +check-TESTS: $(TESTS) + @failed=0; all=0; xfail=0; xpass=0; skip=0; \ + srcdir=$(srcdir); export srcdir; \ + list=' $(TESTS) '; \ + $(am__tty_colors); \ + if test -n "$$list"; then \ + for tst in $$list; do \ + if test -f ./$$tst; then dir=./; \ + elif test -f $$tst; then dir=; \ + else dir="$(srcdir)/"; fi; \ + if $(TESTS_ENVIRONMENT) $${dir}$$tst; then \ + all=`expr $$all + 1`; \ + case " $(XFAIL_TESTS) " in \ + *[\ \ ]$$tst[\ \ ]*) \ + xpass=`expr $$xpass + 1`; \ + failed=`expr $$failed + 1`; \ + col=$$red; res=XPASS; \ + ;; \ + *) \ + col=$$grn; res=PASS; \ + ;; \ + esac; \ + elif test $$? -ne 77; then \ + all=`expr $$all + 1`; \ + case " $(XFAIL_TESTS) " in \ + *[\ \ ]$$tst[\ \ ]*) \ + xfail=`expr $$xfail + 1`; \ + col=$$lgn; res=XFAIL; \ + ;; \ + *) \ + failed=`expr $$failed + 1`; \ + col=$$red; res=FAIL; \ + ;; \ + esac; \ + else \ + skip=`expr $$skip + 1`; \ + col=$$blu; res=SKIP; \ + fi; \ + echo "$${col}$$res$${std}: $$tst"; \ + done; \ + if test "$$all" -eq 1; then \ + tests="test"; \ + All=""; \ + else \ + tests="tests"; \ + All="All "; \ + fi; \ + if test "$$failed" -eq 0; then \ + if test "$$xfail" -eq 0; then \ + banner="$$All$$all $$tests passed"; \ + else \ + if test "$$xfail" -eq 1; then failures=failure; else failures=failures; fi; \ + banner="$$All$$all $$tests behaved as expected ($$xfail expected $$failures)"; \ + fi; \ + else \ + if test "$$xpass" -eq 0; then \ + banner="$$failed of $$all $$tests failed"; \ + else \ + if test "$$xpass" -eq 1; then passes=pass; else passes=passes; fi; \ + banner="$$failed of $$all $$tests did not behave as expected ($$xpass unexpected $$passes)"; \ + fi; \ + fi; \ + dashes="$$banner"; \ + skipped=""; \ + if test "$$skip" -ne 0; then \ + if test "$$skip" -eq 1; then \ + skipped="($$skip test was not run)"; \ + else \ + skipped="($$skip tests were not run)"; \ + fi; \ + test `echo "$$skipped" | wc -c` -le `echo "$$banner" | wc -c` || \ + dashes="$$skipped"; \ + fi; \ + report=""; \ + if test "$$failed" -ne 0 && test -n "$(PACKAGE_BUGREPORT)"; then \ + report="Please report to $(PACKAGE_BUGREPORT)"; \ + test `echo "$$report" | wc -c` -le `echo "$$banner" | wc -c` || \ + dashes="$$report"; \ + fi; \ + dashes=`echo "$$dashes" | sed s/./=/g`; \ + if test "$$failed" -eq 0; then \ + col="$$grn"; \ + else \ + col="$$red"; \ + fi; \ + echo "$${col}$$dashes$${std}"; \ + echo "$${col}$$banner$${std}"; \ + test -z "$$skipped" || echo "$${col}$$skipped$${std}"; \ + test -z "$$report" || echo "$${col}$$report$${std}"; \ + echo "$${col}$$dashes$${std}"; \ + test "$$failed" -eq 0; \ + else :; fi + +distdir: $(DISTFILES) + @srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + list='$(DISTFILES)'; \ + dist_files=`for file in $$list; do echo $$file; done | \ + sed -e "s|^$$srcdirstrip/||;t" \ + -e "s|^$$topsrcdirstrip/|$(top_builddir)/|;t"`; \ + case $$dist_files in \ + */*) $(MKDIR_P) `echo "$$dist_files" | \ + sed '/\//!d;s|^|$(distdir)/|;s,/[^/]*$$,,' | \ + sort -u` ;; \ + esac; \ + for file in $$dist_files; do \ + if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \ + if test -d $$d/$$file; then \ + dir=`echo "/$$file" | sed -e 's,/[^/]*$$,,'`; \ + if test -d "$(distdir)/$$file"; then \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \ + cp -fpR $(srcdir)/$$file "$(distdir)$$dir" || exit 1; \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + cp -fpR $$d/$$file "$(distdir)$$dir" || exit 1; \ + else \ + test -f "$(distdir)/$$file" \ + || cp -p $$d/$$file "$(distdir)/$$file" \ + || exit 1; \ + fi; \ + done +check-am: all-am + $(MAKE) $(AM_MAKEFLAGS) $(check_PROGRAMS) + $(MAKE) $(AM_MAKEFLAGS) check-TESTS +check: check-am +all-am: Makefile +installdirs: +install: install-am +install-exec: install-exec-am +install-data: install-data-am +uninstall: uninstall-am + +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am + +installcheck: installcheck-am +install-strip: + if test -z '$(STRIP)'; then \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + install; \ + else \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'" install; \ + fi +mostlyclean-generic: + +clean-generic: + +distclean-generic: + -test -z "$(CONFIG_CLEAN_FILES)" || rm -f $(CONFIG_CLEAN_FILES) + -test . = "$(srcdir)" || test -z "$(CONFIG_CLEAN_VPATH_FILES)" || rm -f $(CONFIG_CLEAN_VPATH_FILES) + +maintainer-clean-generic: + @echo "This command is intended for maintainers to use" + @echo "it deletes files that may require special tools to rebuild." +clean: clean-am + +clean-am: clean-checkPROGRAMS clean-generic clean-libtool \ + mostlyclean-am + +distclean: distclean-am + -rm -f Makefile +distclean-am: clean-am distclean-compile distclean-generic \ + distclean-tags + +dvi: dvi-am + +dvi-am: + +html: html-am + +html-am: + +info: info-am + +info-am: + +install-data-am: + +install-dvi: install-dvi-am + +install-dvi-am: + +install-exec-am: + +install-html: install-html-am + +install-html-am: + +install-info: install-info-am + +install-info-am: + +install-man: + +install-pdf: install-pdf-am + +install-pdf-am: + +install-ps: install-ps-am + +install-ps-am: + +installcheck-am: + +maintainer-clean: maintainer-clean-am + -rm -f Makefile +maintainer-clean-am: distclean-am maintainer-clean-generic + +mostlyclean: mostlyclean-am + +mostlyclean-am: mostlyclean-compile mostlyclean-generic \ + mostlyclean-libtool + +pdf: pdf-am + +pdf-am: + +ps: ps-am + +ps-am: + +uninstall-am: + +.MAKE: check-am install-am install-strip + +.PHONY: CTAGS GTAGS all all-am check check-TESTS check-am clean \ + clean-checkPROGRAMS clean-generic clean-libtool ctags \ + distclean distclean-compile distclean-generic \ + distclean-libtool distclean-tags distdir dvi dvi-am html \ + html-am info info-am install install-am install-data \ + install-data-am install-dvi install-dvi-am install-exec \ + install-exec-am install-html install-html-am install-info \ + install-info-am install-man install-pdf install-pdf-am \ + install-ps install-ps-am install-strip installcheck \ + installcheck-am installdirs maintainer-clean \ + maintainer-clean-generic mostlyclean mostlyclean-compile \ + mostlyclean-generic mostlyclean-libtool pdf pdf-am ps ps-am \ + tags uninstall uninstall-am + + +$(top_builddir)/tests/libtests.la: + cd $(top_builddir)/tests; $(MAKE) $(AM_MAKEFLAGS) libtests.la + +# Tell versions [3.59,3.63) of GNU make to not export all variables. +# Otherwise a system limit (for SysV at least) may be exceeded. +.NOEXPORT: diff --git a/gmp/tests/mpn/logic.c b/gmp/tests/mpn/logic.c new file mode 100644 index 0000000000..75b5dca1fc --- /dev/null +++ b/gmp/tests/mpn/logic.c @@ -0,0 +1,134 @@ +/* Test mpn_and, mpn_ior, mpn_xor, mpn_andn, mpn_iorn, mpn_xnor, mpn_nand, and + mpn_nior. + +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 <stdlib.h> +#include <stdio.h> + +/* Fake native prevalence of the tested operations, so that we actually test + the compiled functions, i.e., the ones which users will reach. The inlined + variants will be tested through tests/mpz/logic.c. */ +#define HAVE_NATIVE_mpn_com 1 +#define HAVE_NATIVE_mpn_and_n 1 +#define HAVE_NATIVE_mpn_andn_n 1 +#define HAVE_NATIVE_mpn_nand_n 1 +#define HAVE_NATIVE_mpn_ior_n 1 +#define HAVE_NATIVE_mpn_iorn_n 1 +#define HAVE_NATIVE_mpn_nior_n 1 +#define HAVE_NATIVE_mpn_xor_n 1 +#define HAVE_NATIVE_mpn_xnor_n 1 + +#include "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + + +void +check_one (mp_srcptr refp, mp_srcptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n, char *funcname) +{ + if (mpn_cmp (refp, rp, n)) + { + printf ("ERROR in mpn_%s\n", funcname); + printf ("a: "); mpn_dump (ap, n); + printf ("b: "); mpn_dump (bp, n); + printf ("r: "); mpn_dump (rp, n); + printf ("ref: "); mpn_dump (refp, n); + abort(); + } +} + +int +main (int argc, char **argv) +{ + mpz_t a, b; + mp_ptr ap, bp, rp, refp; + mp_size_t max_n, n, i; + gmp_randstate_ptr rands; + long test, reps = 1000; + TMP_SDECL; + TMP_SMARK; + + tests_start (); + TESTS_REPS (reps, argv, argc); + + mpz_inits (a, b, NULL); + + rands = RANDS; /* FIXME: not used */ + + max_n = 100; + + rp = TMP_SALLOC_LIMBS (1 + max_n * 8 / GMP_LIMB_BITS); + refp = TMP_SALLOC_LIMBS (1 + max_n * 8 / GMP_LIMB_BITS); + + for (test = 0; test < reps; test++) + { + for (i = 1; i <= max_n; i++) + { + mpz_rrandomb (a, rands, i * 8); + mpz_rrandomb (b, rands, i * 8); + mpz_setbit (a, i * 8 - 1); + mpz_setbit (b, i * 8 - 1); + ap = PTR(a); + bp = PTR(b); + n = SIZ(a); + + refmpn_and_n (refp, ap, bp, n); + mpn_and_n (rp, ap, bp, n); + check_one (refp, rp, ap, bp, n, "and_n"); + + refmpn_ior_n (refp, ap, bp, n); + mpn_ior_n (rp, ap, bp, n); + check_one (refp, rp, ap, bp, n, "ior_n"); + + refmpn_xor_n (refp, ap, bp, n); + mpn_xor_n (rp, ap, bp, n); + check_one (refp, rp, ap, bp, n, "xor_n"); + + refmpn_andn_n (refp, ap, bp, n); + mpn_andn_n (rp, ap, bp, n); + check_one (refp, rp, ap, bp, n, "andn_n"); + + refmpn_iorn_n (refp, ap, bp, n); + mpn_iorn_n (rp, ap, bp, n); + check_one (refp, rp, ap, bp, n, "iorn_n"); + + refmpn_nand_n (refp, ap, bp, n); + mpn_nand_n (rp, ap, bp, n); + check_one (refp, rp, ap, bp, n, "nand_n"); + + refmpn_nior_n (refp, ap, bp, n); + mpn_nior_n (rp, ap, bp, n); + check_one (refp, rp, ap, bp, n, "nior_n"); + + refmpn_xnor_n (refp, ap, bp, n); + mpn_xnor_n (rp, ap, bp, n); + check_one (refp, rp, ap, bp, n, "xnor_n"); + + refmpn_com (refp, ap, n); + mpn_com (rp, ap, n); + check_one (refp, rp, ap, bp, n, "com"); + } + } + + TMP_SFREE; + mpz_clears (a, b, NULL); + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-aors_1.c b/gmp/tests/mpn/t-aors_1.c new file mode 100644 index 0000000000..6a946f2d57 --- /dev/null +++ b/gmp/tests/mpn/t-aors_1.c @@ -0,0 +1,311 @@ +/* Test mpn_add_1 and mpn_sub_1. + +Copyright 2001, 2002 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + + +#define M GMP_NUMB_MAX +#define ASIZE 10 +#define MAGIC 0x1234 + +#define SETUP() \ + do { \ + refmpn_random (got, data[i].size); \ + got[data[i].size] = MAGIC; \ + } while (0) + +#define SETUP_INPLACE() \ + do { \ + refmpn_copyi (got, data[i].src, data[i].size); \ + got[data[i].size] = MAGIC; \ + } while (0) + +#define VERIFY(name) \ + do { \ + verify (name, i, data[i].src, data[i].n, \ + got_c, data[i].want_c, \ + got, data[i].want, data[i].size); \ + } while (0) + +typedef mp_limb_t (*mpn_aors_1_t) (mp_ptr, mp_srcptr, mp_size_t, mp_limb_t); +mpn_aors_1_t fudge (mpn_aors_1_t); + + +void +verify (const char *name, int i, + mp_srcptr src, mp_limb_t n, + mp_limb_t got_c, mp_limb_t want_c, + mp_srcptr got, mp_srcptr want, mp_size_t size) +{ + if (got[size] != MAGIC) + { + printf ("Overwrite at %s i=%d\n", name, i); + abort (); + } + + if (got_c != want_c || ! refmpn_equal_anynail (got, want, size)) + { + printf ("Wrong at %s i=%d size=%ld\n", name, i, size); + mpn_trace (" src", src, size); + mpn_trace (" n", &n, (mp_size_t) 1); + mpn_trace (" got", got, size); + mpn_trace (" want", want, size); + mpn_trace (" got c", &got_c, (mp_size_t) 1); + mpn_trace ("want c", &want_c, (mp_size_t) 1); + abort (); + } +} + + +void +check_add_1 (void) +{ + static const struct { + mp_size_t size; + mp_limb_t n; + const mp_limb_t src[ASIZE]; + mp_limb_t want_c; + const mp_limb_t want[ASIZE]; + } data[] = { + { 1, 0, { 0 }, 0, { 0 } }, + { 1, 0, { 1 }, 0, { 1 } }, + { 1, 1, { 0 }, 0, { 1 } }, + { 1, 0, { M }, 0, { M } }, + { 1, M, { 0 }, 0, { M } }, + { 1, 1, { 123 }, 0, { 124 } }, + + { 1, 1, { M }, 1, { 0 } }, + { 1, M, { 1 }, 1, { 0 } }, + { 1, M, { M }, 1, { M-1 } }, + + { 2, 0, { 0, 0 }, 0, { 0, 0 } }, + { 2, 0, { 1, 0 }, 0, { 1, 0 } }, + { 2, 1, { 0, 0 }, 0, { 1, 0 } }, + { 2, 0, { M, 0 }, 0, { M, 0 } }, + { 2, M, { 0, 0 }, 0, { M, 0 } }, + { 2, 1, { M, 0 }, 0, { 0, 1 } }, + { 2, M, { 1, 0 }, 0, { 0, 1 } }, + { 2, M, { M, 0 }, 0, { M-1, 1 } }, + { 2, M, { M, 0 }, 0, { M-1, 1 } }, + + { 2, 1, { M, M }, 1, { 0, 0 } }, + { 2, M, { 1, M }, 1, { 0, 0 } }, + { 2, M, { M, M }, 1, { M-1, 0 } }, + { 2, M, { M, M }, 1, { M-1, 0 } }, + + { 3, 1, { M, M, M }, 1, { 0, 0, 0 } }, + { 3, M, { 1, M, M }, 1, { 0, 0, 0 } }, + { 3, M, { M, M, M }, 1, { M-1, 0, 0 } }, + { 3, M, { M, M, M }, 1, { M-1, 0, 0 } }, + + { 4, 1, { M, M, M, M }, 1, { 0, 0, 0, 0 } }, + { 4, M, { 1, M, M, M }, 1, { 0, 0, 0, 0 } }, + { 4, M, { M, M, M, M }, 1, { M-1, 0, 0, 0 } }, + { 4, M, { M, M, M, M }, 1, { M-1, 0, 0, 0 } }, + + { 4, M, { M, 0, M, M }, 0, { M-1, 1, M, M } }, + { 4, M, { M, M-1, M, M }, 0, { M-1, M, M, M } }, + + { 4, M, { M, M, 0, M }, 0, { M-1, 0, 1, M } }, + { 4, M, { M, M, M-1, M }, 0, { M-1, 0, M, M } }, + }; + + mp_limb_t got[ASIZE]; + mp_limb_t got_c; + /* mpn_sec_add_a_itch(n) <= n */ + mp_limb_t scratch[ASIZE]; + int i; + + for (i = 0; i < numberof (data); i++) + { + SETUP (); + got_c = mpn_add_1 (got, data[i].src, data[i].size, data[i].n); + VERIFY ("check_add_1 (separate)"); + + SETUP_INPLACE (); + got_c = mpn_add_1 (got, got, data[i].size, data[i].n); + VERIFY ("check_add_1 (in-place)"); + + SETUP (); + scratch [mpn_sec_add_1_itch(data[i].size)] = MAGIC; + got_c = mpn_sec_add_1 (got, data[i].src, data[i].size, data[i].n, scratch); + got_c ^= scratch [mpn_sec_add_1_itch(data[i].size)] ^ MAGIC; + VERIFY ("check_sec_add_1 (separate)"); + + SETUP_INPLACE (); + got_c = mpn_sec_add_1 (got, got, data[i].size, data[i].n, scratch); + VERIFY ("check_sec_add_1 (in-place)"); + + if (data[i].n == 1) + { + SETUP (); + got_c = mpn_add_1 (got, data[i].src, data[i].size, CNST_LIMB(1)); + VERIFY ("check_add_1 (separate, const 1)"); + + SETUP_INPLACE (); + got_c = mpn_add_1 (got, got, data[i].size, CNST_LIMB(1)); + VERIFY ("check_add_1 (in-place, const 1)"); + + SETUP (); + got_c = mpn_sec_add_1 (got, data[i].src, data[i].size, + CNST_LIMB(1), scratch); + VERIFY ("check_sec_add_1 (separate, const 1)"); + + SETUP_INPLACE (); + got_c = mpn_sec_add_1 (got, got, data[i].size, + CNST_LIMB(1), scratch); + VERIFY ("check_sec_add_1 (in-place, const 1)"); + } + + /* Same again on functions, not inlines. */ + SETUP (); + got_c = (*fudge(mpn_add_1)) (got, data[i].src, data[i].size, data[i].n); + VERIFY ("check_add_1 (function, separate)"); + + SETUP_INPLACE (); + got_c = (*fudge(mpn_add_1)) (got, got, data[i].size, data[i].n); + VERIFY ("check_add_1 (function, in-place)"); + } +} + +void +check_sub_1 (void) +{ + static const struct { + mp_size_t size; + mp_limb_t n; + const mp_limb_t src[ASIZE]; + mp_limb_t want_c; + const mp_limb_t want[ASIZE]; + } data[] = { + { 1, 0, { 0 }, 0, { 0 } }, + { 1, 0, { 1 }, 0, { 1 } }, + { 1, 1, { 1 }, 0, { 0 } }, + { 1, 0, { M }, 0, { M } }, + { 1, 1, { M }, 0, { M-1 } }, + { 1, 1, { 123 }, 0, { 122 } }, + + { 1, 1, { 0 }, 1, { M } }, + { 1, M, { 0 }, 1, { 1 } }, + + { 2, 0, { 0, 0 }, 0, { 0, 0 } }, + { 2, 0, { 1, 0 }, 0, { 1, 0 } }, + { 2, 1, { 1, 0 }, 0, { 0, 0 } }, + { 2, 0, { M, 0 }, 0, { M, 0 } }, + { 2, 1, { M, 0 }, 0, { M-1, 0 } }, + { 2, 1, { 123, 0 }, 0, { 122, 0 } }, + + { 2, 1, { 0, 0 }, 1, { M, M } }, + { 2, M, { 0, 0 }, 1, { 1, M } }, + + { 3, 0, { 0, 0, 0 }, 0, { 0, 0, 0 } }, + { 3, 0, { 123, 0, 0 }, 0, { 123, 0, 0 } }, + + { 3, 1, { 0, 0, 0 }, 1, { M, M, M } }, + { 3, M, { 0, 0, 0 }, 1, { 1, M, M } }, + + { 4, 1, { 0, 0, 0, 0 }, 1, { M, M, M, M } }, + { 4, M, { 0, 0, 0, 0 }, 1, { 1, M, M, M } }, + + { 4, 1, { 0, 0, 1, 42 }, 0, { M, M, 0, 42 } }, + { 4, M, { 0, 0, 123, 24 }, 0, { 1, M, 122, 24 } }, + }; + + mp_limb_t got[ASIZE]; + mp_limb_t got_c; + /* mpn_sec_sub_1_itch(n) <= n */ + mp_limb_t scratch[ASIZE]; + int i; + + for (i = 0; i < numberof (data); i++) + { + SETUP (); + got_c = mpn_sub_1 (got, data[i].src, data[i].size, data[i].n); + VERIFY ("check_sub_1 (separate)"); + + SETUP_INPLACE (); + got_c = mpn_sub_1 (got, got, data[i].size, data[i].n); + VERIFY ("check_sub_1 (in-place)"); + + SETUP (); + scratch [mpn_sec_sub_1_itch(data[i].size)] = MAGIC; + got_c = mpn_sec_sub_1 (got, data[i].src, data[i].size, data[i].n, scratch); + got_c ^= scratch [mpn_sec_sub_1_itch(data[i].size)] ^ MAGIC; + VERIFY ("check_sec_sub_1 (separate)"); + + SETUP_INPLACE (); + got_c = mpn_sec_sub_1 (got, got, data[i].size, data[i].n, scratch); + VERIFY ("check_sec_sub_1 (in-place)"); + + if (data[i].n == 1) + { + SETUP (); + got_c = mpn_sub_1 (got, data[i].src, data[i].size, CNST_LIMB(1)); + VERIFY ("check_sub_1 (separate, const 1)"); + + SETUP_INPLACE (); + got_c = mpn_sub_1 (got, got, data[i].size, CNST_LIMB(1)); + VERIFY ("check_sub_1 (in-place, const 1)"); + + SETUP (); + got_c = mpn_sec_sub_1 (got, data[i].src, data[i].size, + CNST_LIMB(1), scratch); + VERIFY ("check_sec_sub_1 (separate, const 1)"); + + SETUP_INPLACE (); + got_c = mpn_sec_sub_1 (got, got, data[i].size, + CNST_LIMB(1), scratch); + VERIFY ("check_sec_sub_1 (in-place, const 1)"); + } + + /* Same again on functions, not inlines. */ + SETUP (); + got_c = (*fudge(mpn_sub_1)) (got, data[i].src, data[i].size, data[i].n); + VERIFY ("check_sub_1 (function, separate)"); + + SETUP_INPLACE (); + got_c = (*fudge(mpn_sub_1)) (got, got, data[i].size, data[i].n); + VERIFY ("check_sub_1 (function, in-place)"); + } +} + +/* Try to prevent the optimizer inlining. */ +mpn_aors_1_t +fudge (mpn_aors_1_t f) +{ + return f; +} + +int +main (void) +{ + tests_start (); + mp_trace_base = -16; + + check_add_1 (); + check_sub_1 (); + + tests_end (); + exit (0); +} diff --git a/gmp/tests/mpn/t-asmtype.c b/gmp/tests/mpn/t-asmtype.c new file mode 100644 index 0000000000..93960f7aef --- /dev/null +++ b/gmp/tests/mpn/t-asmtype.c @@ -0,0 +1,64 @@ +/* Test .type directives on assembler functions. + +Copyright 2001 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 "gmp.h" +#include "gmp-impl.h" + +#include "tests.h" + + +/* This apparently trivial test is designed to detect missing .type and + .size directives in asm code, per the problem described under + GMP_ASM_TYPE in acinclude.m4. + + A failure can be provoked in a shared or shared+static build by making + TYPE and SIZE in config.m4 empty, either by editing it or by configuring + with + + ./configure gmp_cv_asm_type= gmp_cv_asm_size= + + mpn_add_n is used for the test because normally it's implemented in + assembler on a CPU that has any asm code. + + Enhancement: As noted with GMP_ASM_TYPE, if .type is wrong but .size is + right then everything works, but uses code copied down to the mainline + data area. Maybe we could detect that if we built a test library with an + object that had .size deliberately disabled. */ + +int +main (void) +{ + static const mp_limb_t x[3] = { 1, 2, 3 }; + static const mp_limb_t y[3] = { 4, 5, 6 }; + static const mp_limb_t want[3] = { 5, 7, 9 }; + mp_limb_t got[3]; + + mpn_add_n (got, x, y, (mp_size_t) 3); + + if (refmpn_cmp (got, want, (mp_size_t) 3) != 0) + { + printf ("Wrong result from mpn_add_n\n"); + abort (); + } + + exit (0); +} diff --git a/gmp/tests/mpn/t-bdiv.c b/gmp/tests/mpn/t-bdiv.c new file mode 100644 index 0000000000..0056ca9e38 --- /dev/null +++ b/gmp/tests/mpn/t-bdiv.c @@ -0,0 +1,368 @@ +/* Copyright 2006, 2007, 2009, 2010 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> /* for strtol */ +#include <stdio.h> /* for printf */ + +#include "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" +#include "tests/tests.h" + + +static void +dumpy (mp_srcptr p, mp_size_t n) +{ + mp_size_t i; + if (n > 20) + { + for (i = n - 1; i >= n - 4; i--) + { + printf ("%0*lx", (int) (2 * sizeof (mp_limb_t)), p[i]); + printf (" "); + } + printf ("... "); + for (i = 3; i >= 0; i--) + { + printf ("%0*lx", (int) (2 * sizeof (mp_limb_t)), p[i]); + printf (" " + (i == 0)); + } + } + else + { + for (i = n - 1; i >= 0; i--) + { + printf ("%0*lx", (int) (2 * sizeof (mp_limb_t)), p[i]); + printf (" " + (i == 0)); + } + } + puts (""); +} + +static unsigned long test; + +void +check_one (mp_ptr qp, mp_srcptr rp, mp_limb_t rh, + mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, const char *fname) +{ + mp_size_t qn; + int cmp; + mp_ptr tp; + mp_limb_t cy = 4711; /* silence warnings */ + TMP_DECL; + + qn = nn - dn; + + if (qn == 0) + return; + + TMP_MARK; + + tp = TMP_ALLOC_LIMBS (nn + 1); + + if (dn >= qn) + mpn_mul (tp, dp, dn, qp, qn); + else + mpn_mul (tp, qp, qn, dp, dn); + + if (rp != NULL) + { + cy = mpn_add_n (tp + qn, tp + qn, rp, dn); + cmp = cy != rh || mpn_cmp (tp, np, nn) != 0; + } + else + cmp = mpn_cmp (tp, np, nn - dn) != 0; + + if (cmp != 0) + { + printf ("\r*******************************************************************************\n"); + printf ("%s inconsistent in test %lu\n", fname, test); + printf ("N= "); dumpy (np, nn); + printf ("D= "); dumpy (dp, dn); + printf ("Q= "); dumpy (qp, qn); + if (rp != NULL) + { + printf ("R= "); dumpy (rp, dn); + printf ("Rb= %d, Cy=%d\n", (int) cy, (int) rh); + } + printf ("T= "); dumpy (tp, nn); + printf ("nn = %ld, dn = %ld, qn = %ld", nn, dn, qn); + printf ("\n*******************************************************************************\n"); + abort (); + } + + TMP_FREE; +} + + +/* These are *bit* sizes. */ +#define SIZE_LOG 16 +#define MAX_DN (1L << SIZE_LOG) +#define MAX_NN (1L << (SIZE_LOG + 1)) + +#define COUNT 500 + +mp_limb_t +random_word (gmp_randstate_ptr rs) +{ + mpz_t x; + mp_limb_t r; + TMP_DECL; + TMP_MARK; + + MPZ_TMP_INIT (x, 2); + mpz_urandomb (x, rs, 32); + r = mpz_get_ui (x); + TMP_FREE; + return r; +} + +int +main (int argc, char **argv) +{ + gmp_randstate_ptr rands; + unsigned long maxnbits, maxdbits, nbits, dbits; + mpz_t n, d, tz; + mp_size_t maxnn, maxdn, nn, dn, clearn, i; + mp_ptr np, dp, qp, rp; + mp_limb_t rh; + mp_limb_t t; + mp_limb_t dinv; + int count = COUNT; + mp_ptr scratch; + mp_limb_t ran; + mp_size_t alloc, itch; + mp_limb_t rran0, rran1, qran0, qran1; + TMP_DECL; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + + maxdbits = MAX_DN; + maxnbits = MAX_NN; + + tests_start (); + rands = RANDS; + + mpz_init (n); + mpz_init (d); + mpz_init (tz); + + maxnn = maxnbits / GMP_NUMB_BITS + 1; + maxdn = maxdbits / GMP_NUMB_BITS + 1; + + TMP_MARK; + + qp = TMP_ALLOC_LIMBS (maxnn + 2) + 1; + rp = TMP_ALLOC_LIMBS (maxnn + 2) + 1; + + alloc = 1; + scratch = __GMP_ALLOCATE_FUNC_LIMBS (alloc); + + for (test = 0; test < count;) + { + nbits = random_word (rands) % (maxnbits - GMP_NUMB_BITS) + 2 * GMP_NUMB_BITS; + if (maxdbits > nbits) + dbits = random_word (rands) % nbits + 1; + else + dbits = random_word (rands) % maxdbits + 1; + +#if RAND_UNIFORM +#define RANDFUNC mpz_urandomb +#else +#define RANDFUNC mpz_rrandomb +#endif + + do + { + RANDFUNC (n, rands, nbits); + do + { + RANDFUNC (d, rands, dbits); + } + while (mpz_sgn (d) == 0); + + np = PTR (n); + dp = PTR (d); + nn = SIZ (n); + dn = SIZ (d); + } + while (nn < dn); + + dp[0] |= 1; + + mpz_urandomb (tz, rands, 32); + t = mpz_get_ui (tz); + + if (t % 17 == 0) + dp[0] = GMP_NUMB_MAX; + + switch ((int) t % 16) + { + case 0: + clearn = random_word (rands) % nn; + for (i = 0; i <= clearn; i++) + np[i] = 0; + break; + case 1: + mpn_sub_1 (np + nn - dn, dp, dn, random_word (rands)); + break; + case 2: + mpn_add_1 (np + nn - dn, dp, dn, random_word (rands)); + break; + } + + test++; + + binvert_limb (dinv, dp[0]); + + rran0 = random_word (rands); + rran1 = random_word (rands); + qran0 = random_word (rands); + qran1 = random_word (rands); + + qp[-1] = qran0; + qp[nn - dn + 1] = qran1; + rp[-1] = rran0; + + ran = random_word (rands); + + if ((double) (nn - dn) * dn < 1e5) + { + if (nn > dn) + { + /* Test mpn_sbpi1_bdiv_qr */ + MPN_ZERO (qp, nn - dn); + MPN_ZERO (rp, dn); + MPN_COPY (rp, np, nn); + rh = mpn_sbpi1_bdiv_qr (qp, rp, nn, dp, dn, -dinv); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); + check_one (qp, rp + nn - dn, rh, np, nn, dp, dn, "mpn_sbpi1_bdiv_qr"); + } + + if (nn > dn) + { + /* Test mpn_sbpi1_bdiv_q */ + MPN_COPY (rp, np, nn); + MPN_ZERO (qp, nn - dn); + mpn_sbpi1_bdiv_q (qp, rp, nn - dn, dp, MIN(dn,nn-dn), -dinv); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); + check_one (qp, NULL, 0, np, nn, dp, dn, "mpn_sbpi1_bdiv_q"); + } + } + + if (dn >= 4 && nn - dn >= 2) + { + /* Test mpn_dcpi1_bdiv_qr */ + MPN_COPY (rp, np, nn); + MPN_ZERO (qp, nn - dn); + rh = mpn_dcpi1_bdiv_qr (qp, rp, nn, dp, dn, -dinv); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); + check_one (qp, rp + nn - dn, rh, np, nn, dp, dn, "mpn_dcpi1_bdiv_qr"); + } + + if (dn >= 4 && nn - dn >= 2) + { + /* Test mpn_dcpi1_bdiv_q */ + MPN_COPY (rp, np, nn); + MPN_ZERO (qp, nn - dn); + mpn_dcpi1_bdiv_q (qp, rp, nn - dn, dp, MIN(dn,nn-dn), -dinv); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); + check_one (qp, NULL, 0, np, nn, dp, dn, "mpn_dcpi1_bdiv_q"); + } + + if (nn > dn) + { + /* Test mpn_bdiv_qr */ + itch = mpn_bdiv_qr_itch (nn, dn); + if (itch + 1 > alloc) + { + scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1); + alloc = itch + 1; + } + scratch[itch] = ran; + MPN_ZERO (qp, nn - dn); + MPN_ZERO (rp, dn); + rp[dn] = rran1; + rh = mpn_bdiv_qr (qp, rp, np, nn, dp, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); ASSERT_ALWAYS (rp[dn] == rran1); + + check_one (qp, rp, rh, np, nn, dp, dn, "mpn_bdiv_qr"); + } + + if (nn - dn < 2 || dn < 2) + continue; + + /* Test mpn_mu_bdiv_qr */ + itch = mpn_mu_bdiv_qr_itch (nn, dn); + if (itch + 1 > alloc) + { + scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1); + alloc = itch + 1; + } + scratch[itch] = ran; + MPN_ZERO (qp, nn - dn); + MPN_ZERO (rp, dn); + rp[dn] = rran1; + rh = mpn_mu_bdiv_qr (qp, rp, np, nn, dp, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); ASSERT_ALWAYS (rp[dn] == rran1); + check_one (qp, rp, rh, np, nn, dp, dn, "mpn_mu_bdiv_qr"); + + /* Test mpn_mu_bdiv_q */ + itch = mpn_mu_bdiv_q_itch (nn, dn); + if (itch + 1 > alloc) + { + scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1); + alloc = itch + 1; + } + scratch[itch] = ran; + MPN_ZERO (qp, nn - dn + 1); + mpn_mu_bdiv_q (qp, np, nn - dn, dp, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + check_one (qp, NULL, 0, np, nn, dp, dn, "mpn_mu_bdiv_q"); + } + + __GMP_FREE_FUNC_LIMBS (scratch, alloc); + + TMP_FREE; + + mpz_clear (n); + mpz_clear (d); + mpz_clear (tz); + + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-broot.c b/gmp/tests/mpn/t-broot.c new file mode 100644 index 0000000000..1aa43319ec --- /dev/null +++ b/gmp/tests/mpn/t-broot.c @@ -0,0 +1,105 @@ +/* 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> /* for strtol */ +#include <stdio.h> /* for printf */ + +#include "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" +#include "tests/tests.h" + +#define MAX_LIMBS 150 +#define COUNT 500 + +int +main (int argc, char **argv) +{ + gmp_randstate_ptr rands; + + mp_ptr ap, rp, pp, scratch; + int count = COUNT; + unsigned i; + TMP_DECL; + + TMP_MARK; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + tests_start (); + rands = RANDS; + + ap = TMP_ALLOC_LIMBS (MAX_LIMBS); + rp = TMP_ALLOC_LIMBS (MAX_LIMBS); + pp = TMP_ALLOC_LIMBS (MAX_LIMBS); + scratch = TMP_ALLOC_LIMBS (3*MAX_LIMBS); /* For mpn_powlo */ + + for (i = 0; i < count; i++) + { + mp_size_t n; + mp_limb_t k; + int c; + + n = 1 + gmp_urandomm_ui (rands, MAX_LIMBS); + + if (i & 1) + mpn_random2 (ap, n); + else + mpn_random (ap, n); + + ap[0] |= 1; + + if (i < 100) + k = 3 + 2*i; + else + { + mpn_random (&k, 1); + if (k < 3) + k = 3; + else + k |= 1; + } + mpn_broot (rp, ap, n, k); + mpn_powlo (pp, rp, &k, 1, n, scratch); + + MPN_CMP (c, ap, pp, n); + if (c != 0) + { + gmp_fprintf (stderr, + "mpn_broot returned bad result: %u limbs\n", + (unsigned) n); + gmp_fprintf (stderr, "k = %Mx\n", k); + gmp_fprintf (stderr, "a = %Nx\n", ap, n); + gmp_fprintf (stderr, "r = %Nx\n", rp, n); + gmp_fprintf (stderr, "r^n = %Nx\n", pp, n); + abort (); + } + } + TMP_FREE; + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-brootinv.c b/gmp/tests/mpn/t-brootinv.c new file mode 100644 index 0000000000..11f40b9543 --- /dev/null +++ b/gmp/tests/mpn/t-brootinv.c @@ -0,0 +1,106 @@ +/* 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> /* for strtol */ +#include <stdio.h> /* for printf */ + +#include "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" +#include "tests/tests.h" + +#define MAX_LIMBS 150 +#define COUNT 500 + +int +main (int argc, char **argv) +{ + gmp_randstate_ptr rands; + + mp_ptr ap, rp, pp, app, scratch; + int count = COUNT; + unsigned i; + TMP_DECL; + + TMP_MARK; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + tests_start (); + rands = RANDS; + + ap = TMP_ALLOC_LIMBS (MAX_LIMBS); + rp = TMP_ALLOC_LIMBS (MAX_LIMBS); + pp = TMP_ALLOC_LIMBS (MAX_LIMBS); + app = TMP_ALLOC_LIMBS (MAX_LIMBS); + scratch = TMP_ALLOC_LIMBS (5*MAX_LIMBS); + + for (i = 0; i < count; i++) + { + mp_size_t n; + mp_limb_t k; + + n = 1 + gmp_urandomm_ui (rands, MAX_LIMBS); + + if (i & 1) + mpn_random2 (ap, n); + else + mpn_random (ap, n); + + ap[0] |= 1; + + if (i < 100) + k = 3 + 2*i; + else + { + mpn_random (&k, 1); + if (k < 3) + k = 3; + else + k |= 1; + } + mpn_brootinv (rp, ap, n, k, scratch); + mpn_powlo (pp, rp, &k, 1, n, scratch); + mpn_mullo_n (app, ap, pp, n); + + if (app[0] != 1 || !mpn_zero_p (app+1, n-1)) + { + gmp_fprintf (stderr, + "mpn_brootinv returned bad result: %u limbs\n", + (unsigned) n); + gmp_fprintf (stderr, "k = %Mx\n", k); + gmp_fprintf (stderr, "a = %Nx\n", ap, n); + gmp_fprintf (stderr, "r = %Nx\n", rp, n); + gmp_fprintf (stderr, "r^n = %Nx\n", pp, n); + gmp_fprintf (stderr, "a r^n = %Nx\n", app, n); + abort (); + } + } + TMP_FREE; + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-div.c b/gmp/tests/mpn/t-div.c new file mode 100644 index 0000000000..9dbe0f8185 --- /dev/null +++ b/gmp/tests/mpn/t-div.c @@ -0,0 +1,505 @@ +/* Copyright 2006, 2007, 2009, 2010, 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 <stdlib.h> /* for strtol */ +#include <stdio.h> /* for printf */ + +#include "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" +#include "tests/tests.h" + + +static void +dumpy (mp_srcptr p, mp_size_t n) +{ + mp_size_t i; + if (n > 20) + { + for (i = n - 1; i >= n - 4; i--) + { + printf ("%0*lx", (int) (2 * sizeof (mp_limb_t)), p[i]); + printf (" "); + } + printf ("... "); + for (i = 3; i >= 0; i--) + { + printf ("%0*lx", (int) (2 * sizeof (mp_limb_t)), p[i]); + printf (" " + (i == 0)); + } + } + else + { + for (i = n - 1; i >= 0; i--) + { + printf ("%0*lx", (int) (2 * sizeof (mp_limb_t)), p[i]); + printf (" " + (i == 0)); + } + } + puts (""); +} + +static signed long test; + +static void +check_one (mp_ptr qp, mp_srcptr rp, + mp_srcptr np, mp_size_t nn, mp_srcptr dp, mp_size_t dn, + const char *fname, mp_limb_t q_allowed_err) +{ + mp_size_t qn = nn - dn + 1; + mp_ptr tp; + const char *msg; + const char *tvalue; + mp_limb_t i; + TMP_DECL; + TMP_MARK; + + tp = TMP_ALLOC_LIMBS (nn + 1); + if (dn >= qn) + refmpn_mul (tp, dp, dn, qp, qn); + else + refmpn_mul (tp, qp, qn, dp, dn); + + for (i = 0; i < q_allowed_err && (tp[nn] > 0 || mpn_cmp (tp, np, nn) > 0); i++) + ASSERT_NOCARRY (refmpn_sub (tp, tp, nn+1, dp, dn)); + + if (tp[nn] > 0 || mpn_cmp (tp, np, nn) > 0) + { + msg = "q too large"; + tvalue = "Q*D"; + error: + printf ("\r*******************************************************************************\n"); + printf ("%s failed test %ld: %s\n", fname, test, msg); + printf ("N= "); dumpy (np, nn); + printf ("D= "); dumpy (dp, dn); + printf ("Q= "); dumpy (qp, qn); + if (rp) + { printf ("R= "); dumpy (rp, dn); } + printf ("%5s=", tvalue); dumpy (tp, nn+1); + printf ("nn = %ld, dn = %ld, qn = %ld\n", nn, dn, qn); + abort (); + } + + ASSERT_NOCARRY (refmpn_sub_n (tp, np, tp, nn)); + tvalue = "N-Q*D"; + if (!mpn_zero_p (tp + dn, nn - dn) || mpn_cmp (tp, dp, dn) >= 0) + { + msg = "q too small"; + goto error; + } + + if (rp && mpn_cmp (rp, tp, dn) != 0) + { + msg = "r incorrect"; + goto error; + } + + TMP_FREE; +} + + +/* These are *bit* sizes. */ +#ifndef SIZE_LOG +#define SIZE_LOG 17 +#endif +#define MAX_DN (1L << SIZE_LOG) +#define MAX_NN (1L << (SIZE_LOG + 1)) + +#define COUNT 200 + +int +main (int argc, char **argv) +{ + gmp_randstate_ptr rands; + unsigned long maxnbits, maxdbits, nbits, dbits; + mpz_t n, d, q, r, tz, junk; + mp_size_t maxnn, maxdn, nn, dn, clearn, i; + mp_ptr np, dup, dnp, qp, rp, junkp; + mp_limb_t t; + gmp_pi1_t dinv; + long count = COUNT; + mp_ptr scratch; + mp_limb_t ran; + mp_size_t alloc, itch; + mp_limb_t rran0, rran1, qran0, qran1; + TMP_DECL; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + maxdbits = MAX_DN; + maxnbits = MAX_NN; + + tests_start (); + rands = RANDS; + + mpz_init (n); + mpz_init (d); + mpz_init (q); + mpz_init (r); + mpz_init (tz); + mpz_init (junk); + + maxnn = maxnbits / GMP_NUMB_BITS + 1; + maxdn = maxdbits / GMP_NUMB_BITS + 1; + + TMP_MARK; + + qp = TMP_ALLOC_LIMBS (maxnn + 2) + 1; + rp = TMP_ALLOC_LIMBS (maxnn + 2) + 1; + dnp = TMP_ALLOC_LIMBS (maxdn); + + alloc = 1; + scratch = __GMP_ALLOCATE_FUNC_LIMBS (alloc); + + for (test = -300; test < count; test++) + { + nbits = urandom () % (maxnbits - GMP_NUMB_BITS) + 2 * GMP_NUMB_BITS; + + if (test < 0) + dbits = (test + 300) % (nbits - 1) + 1; + else + dbits = urandom () % (nbits - 1) % maxdbits + 1; + +#if RAND_UNIFORM +#define RANDFUNC mpz_urandomb +#else +#define RANDFUNC mpz_rrandomb +#endif + + do + RANDFUNC (d, rands, dbits); + while (mpz_sgn (d) == 0); + dn = SIZ (d); + dup = PTR (d); + MPN_COPY (dnp, dup, dn); + dnp[dn - 1] |= GMP_NUMB_HIGHBIT; + + if (test % 2 == 0) + { + RANDFUNC (n, rands, nbits); + nn = SIZ (n); + ASSERT_ALWAYS (nn >= dn); + } + else + { + do + { + RANDFUNC (q, rands, urandom () % (nbits - dbits + 1)); + RANDFUNC (r, rands, urandom () % mpz_sizeinbase (d, 2)); + mpz_mul (n, q, d); + mpz_add (n, n, r); + nn = SIZ (n); + } + while (nn > maxnn || nn < dn); + } + + ASSERT_ALWAYS (nn <= maxnn); + ASSERT_ALWAYS (dn <= maxdn); + + mpz_urandomb (junk, rands, nbits); + junkp = PTR (junk); + + np = PTR (n); + + mpz_urandomb (tz, rands, 32); + t = mpz_get_ui (tz); + + if (t % 17 == 0) + { + dnp[dn - 1] = GMP_NUMB_MAX; + dup[dn - 1] = GMP_NUMB_MAX; + } + + switch ((int) t % 16) + { + case 0: + clearn = urandom () % nn; + for (i = clearn; i < nn; i++) + np[i] = 0; + break; + case 1: + mpn_sub_1 (np + nn - dn, dnp, dn, urandom ()); + break; + case 2: + mpn_add_1 (np + nn - dn, dnp, dn, urandom ()); + break; + } + + if (dn >= 2) + invert_pi1 (dinv, dnp[dn - 1], dnp[dn - 2]); + + rran0 = urandom (); + rran1 = urandom (); + qran0 = urandom (); + qran1 = urandom (); + + qp[-1] = qran0; + qp[nn - dn + 1] = qran1; + rp[-1] = rran0; + + ran = urandom (); + + if ((double) (nn - dn) * dn < 1e5) + { + /* Test mpn_sbpi1_div_qr */ + if (dn > 2) + { + MPN_COPY (rp, np, nn); + if (nn > dn) + MPN_COPY (qp, junkp, nn - dn); + qp[nn - dn] = mpn_sbpi1_div_qr (qp, rp, nn, dnp, dn, dinv.inv32); + check_one (qp, rp, np, nn, dnp, dn, "mpn_sbpi1_div_qr", 0); + } + + /* Test mpn_sbpi1_divappr_q */ + if (dn > 2) + { + MPN_COPY (rp, np, nn); + if (nn > dn) + MPN_COPY (qp, junkp, nn - dn); + qp[nn - dn] = mpn_sbpi1_divappr_q (qp, rp, nn, dnp, dn, dinv.inv32); + check_one (qp, NULL, np, nn, dnp, dn, "mpn_sbpi1_divappr_q", 1); + } + + /* Test mpn_sbpi1_div_q */ + if (dn > 2) + { + MPN_COPY (rp, np, nn); + if (nn > dn) + MPN_COPY (qp, junkp, nn - dn); + qp[nn - dn] = mpn_sbpi1_div_q (qp, rp, nn, dnp, dn, dinv.inv32); + check_one (qp, NULL, np, nn, dnp, dn, "mpn_sbpi1_div_q", 0); + } + + /* Test mpn_sec_div_qr */ + itch = mpn_sec_div_qr_itch (nn, dn); + if (itch + 1 > alloc) + { + scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1); + alloc = itch + 1; + } + scratch[itch] = ran; + MPN_COPY (rp, np, nn); + if (nn >= dn) + MPN_COPY (qp, junkp, nn - dn + 1); + qp[nn - dn] = mpn_sec_div_qr (qp, rp, nn, dup, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + check_one (qp, rp, np, nn, dup, dn, "mpn_sec_div_qr (unnorm)", 0); + + /* Test mpn_sec_div_r */ + itch = mpn_sec_div_r_itch (nn, dn); + if (itch + 1 > alloc) + { + scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1); + alloc = itch + 1; + } + scratch[itch] = ran; + MPN_COPY (rp, np, nn); + mpn_sec_div_r (rp, nn, dup, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + /* Note: Since check_one cannot cope with remainder-only functions, we + pass qp[] from the previous function, mpn_sec_div_qr. */ + check_one (qp, rp, np, nn, dup, dn, "mpn_sec_div_r (unnorm)", 0); + + /* Normalised case, mpn_sec_div_qr */ + itch = mpn_sec_div_qr_itch (nn, dn); + scratch[itch] = ran; + + MPN_COPY (rp, np, nn); + if (nn >= dn) + MPN_COPY (qp, junkp, nn - dn + 1); + qp[nn - dn] = mpn_sec_div_qr (qp, rp, nn, dnp, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + check_one (qp, rp, np, nn, dnp, dn, "mpn_sec_div_qr (norm)", 0); + + /* Normalised case, mpn_sec_div_r */ + itch = mpn_sec_div_r_itch (nn, dn); + scratch[itch] = ran; + MPN_COPY (rp, np, nn); + mpn_sec_div_r (rp, nn, dnp, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + /* Note: Since check_one cannot cope with remainder-only functions, we + pass qp[] from the previous function, mpn_sec_div_qr. */ + check_one (qp, rp, np, nn, dnp, dn, "mpn_sec_div_r (norm)", 0); + } + + /* Test mpn_dcpi1_div_qr */ + if (dn >= 6 && nn - dn >= 3) + { + MPN_COPY (rp, np, nn); + if (nn > dn) + MPN_COPY (qp, junkp, nn - dn); + qp[nn - dn] = mpn_dcpi1_div_qr (qp, rp, nn, dnp, dn, &dinv); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); + check_one (qp, rp, np, nn, dnp, dn, "mpn_dcpi1_div_qr", 0); + } + + /* Test mpn_dcpi1_divappr_q */ + if (dn >= 6 && nn - dn >= 3) + { + MPN_COPY (rp, np, nn); + if (nn > dn) + MPN_COPY (qp, junkp, nn - dn); + qp[nn - dn] = mpn_dcpi1_divappr_q (qp, rp, nn, dnp, dn, &dinv); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); + check_one (qp, NULL, np, nn, dnp, dn, "mpn_dcpi1_divappr_q", 1); + } + + /* Test mpn_dcpi1_div_q */ + if (dn >= 6 && nn - dn >= 3) + { + MPN_COPY (rp, np, nn); + if (nn > dn) + MPN_COPY (qp, junkp, nn - dn); + qp[nn - dn] = mpn_dcpi1_div_q (qp, rp, nn, dnp, dn, &dinv); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); + check_one (qp, NULL, np, nn, dnp, dn, "mpn_dcpi1_div_q", 0); + } + + /* Test mpn_mu_div_qr */ + if (nn - dn > 2 && dn >= 2) + { + itch = mpn_mu_div_qr_itch (nn, dn, 0); + if (itch + 1 > alloc) + { + scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1); + alloc = itch + 1; + } + scratch[itch] = ran; + MPN_COPY (qp, junkp, nn - dn); + MPN_ZERO (rp, dn); + rp[dn] = rran1; + qp[nn - dn] = mpn_mu_div_qr (qp, rp, np, nn, dnp, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + ASSERT_ALWAYS (rp[-1] == rran0); ASSERT_ALWAYS (rp[dn] == rran1); + check_one (qp, rp, np, nn, dnp, dn, "mpn_mu_div_qr", 0); + } + + /* Test mpn_mu_divappr_q */ + if (nn - dn > 2 && dn >= 2) + { + itch = mpn_mu_divappr_q_itch (nn, dn, 0); + if (itch + 1 > alloc) + { + scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1); + alloc = itch + 1; + } + scratch[itch] = ran; + MPN_COPY (qp, junkp, nn - dn); + qp[nn - dn] = mpn_mu_divappr_q (qp, np, nn, dnp, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + check_one (qp, NULL, np, nn, dnp, dn, "mpn_mu_divappr_q", 4); + } + + /* Test mpn_mu_div_q */ + if (nn - dn > 2 && dn >= 2) + { + itch = mpn_mu_div_q_itch (nn, dn, 0); + if (itch + 1> alloc) + { + scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1); + alloc = itch + 1; + } + scratch[itch] = ran; + MPN_COPY (qp, junkp, nn - dn); + qp[nn - dn] = mpn_mu_div_q (qp, np, nn, dnp, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + check_one (qp, NULL, np, nn, dnp, dn, "mpn_mu_div_q", 0); + } + + if (1) + { + itch = nn + 1; + if (itch + 1> alloc) + { + scratch = __GMP_REALLOCATE_FUNC_LIMBS (scratch, alloc, itch + 1); + alloc = itch + 1; + } + scratch[itch] = ran; + mpn_div_q (qp, np, nn, dup, dn, scratch); + ASSERT_ALWAYS (ran == scratch[itch]); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - dn + 1] == qran1); + check_one (qp, NULL, np, nn, dup, dn, "mpn_div_q", 0); + } + + if (dn >= 2 && nn >= 2) + { + mp_limb_t qh; + + /* mpn_divrem_2 */ + MPN_COPY (rp, np, nn); + qp[nn - 2] = qp[nn-1] = qran1; + + qh = mpn_divrem_2 (qp, 0, rp, nn, dnp + dn - 2); + ASSERT_ALWAYS (qp[nn - 2] == qran1); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - 1] == qran1); + qp[nn - 2] = qh; + check_one (qp, rp, np, nn, dnp + dn - 2, 2, "mpn_divrem_2", 0); + + /* Missing: divrem_2 with fraction limbs. */ + + /* mpn_div_qr_2 */ + qp[nn - 2] = qran1; + + qh = mpn_div_qr_2 (qp, rp, np, nn, dup + dn - 2); + ASSERT_ALWAYS (qp[nn - 2] == qran1); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - 1] == qran1); + qp[nn - 2] = qh; + check_one (qp, rp, np, nn, dup + dn - 2, 2, "mpn_div_qr_2", 0); + } + if (dn >= 1 && nn >= 1) + { + /* mpn_div_qr_1 */ + mp_limb_t qh; + qp[nn-1] = qran1; + rp[0] = mpn_div_qr_1 (qp, &qh, np, nn, dnp[dn - 1]); + ASSERT_ALWAYS (qp[-1] == qran0); ASSERT_ALWAYS (qp[nn - 1] == qran1); + qp[nn - 1] = qh; + check_one (qp, rp, np, nn, dnp + dn - 1, 1, "mpn_div_qr_1", 0); + } + } + + __GMP_FREE_FUNC_LIMBS (scratch, alloc); + + TMP_FREE; + + mpz_clear (n); + mpz_clear (d); + mpz_clear (q); + mpz_clear (r); + mpz_clear (tz); + mpz_clear (junk); + + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-divrem_1.c b/gmp/tests/mpn/t-divrem_1.c new file mode 100644 index 0000000000..9ffe90548f --- /dev/null +++ b/gmp/tests/mpn/t-divrem_1.c @@ -0,0 +1,124 @@ +/* Test mpn_divrem_1 and mpn_preinv_divrem_1. + +Copyright 2003 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + + +void +check_data (void) +{ + static const struct { + mp_limb_t n[1]; + mp_size_t nsize; + mp_limb_t d; + mp_size_t qxn; + mp_limb_t want_q[5]; + mp_limb_t want_r; + } data[] = { + { { 0 }, 1, 1, 0, + { 0 }, 0}, + + { { 5 }, 1, 2, 0, + { 2 }, 1}, + + /* Exercises the q update in the nl == constant 0 case of + udiv_qrnnd_preinv3. Test case copied from t-fat.c. */ + { { 287 }, 1, 7, 1, + { 0, 41 }, 0 }, + +#if GMP_NUMB_BITS == 32 + { { 0x3C }, 1, 0xF2, 1, + { 0x3F789854, 0 }, 0x98 }, +#endif + +#if GMP_NUMB_BITS == 64 + { { 0x3C }, 1, 0xF2, 1, + { CNST_LIMB(0x3F789854A0CB1B81), 0 }, 0x0E }, + + /* This case exposed some wrong code generated by SGI cc on mips64 irix + 6.5 with -n32 -O2, in the fractional loop for normalized divisor + using udiv_qrnnd_preinv. A test "x>al" in one of the sub_ddmmss + expansions came out wrong, leading to an incorrect quotient. */ + { { CNST_LIMB(0x3C00000000000000) }, 1, CNST_LIMB(0xF200000000000000), 1, + { CNST_LIMB(0x3F789854A0CB1B81), 0 }, CNST_LIMB(0x0E00000000000000) }, +#endif + }; + + mp_limb_t dinv, got_r, got_q[numberof(data[0].want_q)]; + mp_size_t qsize; + int i, shift; + + for (i = 0; i < numberof (data); i++) + { + qsize = data[i].nsize + data[i].qxn; + ASSERT_ALWAYS (qsize <= numberof (got_q)); + + got_r = mpn_divrem_1 (got_q, data[i].qxn, data[i].n, data[i].nsize, + data[i].d); + if (got_r != data[i].want_r + || refmpn_cmp (got_q, data[i].want_q, qsize) != 0) + { + printf ("mpn_divrem_1 wrong at data[%d]\n", i); + bad: + mpn_trace (" n", data[i].n, data[i].nsize); + printf (" nsize=%ld\n", (long) data[i].nsize); + mp_limb_trace (" d", data[i].d); + printf (" qxn=%ld\n", (long) data[i].qxn); + mpn_trace (" want q", data[i].want_q, qsize); + mpn_trace (" got q", got_q, qsize); + mp_limb_trace (" want r", data[i].want_r); + mp_limb_trace (" got r", got_r); + abort (); + } + + /* test if available */ +#if USE_PREINV_DIVREM_1 || HAVE_NATIVE_mpn_preinv_divrem_1 + shift = refmpn_count_leading_zeros (data[i].d); + dinv = refmpn_invert_limb (data[i].d << shift); + got_r = mpn_preinv_divrem_1 (got_q, data[i].qxn, + data[i].n, data[i].nsize, + data[i].d, dinv, shift); + if (got_r != data[i].want_r + || refmpn_cmp (got_q, data[i].want_q, qsize) != 0) + { + printf ("mpn_preinv divrem_1 wrong at data[%d]\n", i); + printf (" shift=%d\n", shift); + mp_limb_trace (" dinv", dinv); + goto bad; + } +#endif + } +} + +int +main (void) +{ + tests_start (); + mp_trace_base = -16; + + check_data (); + + tests_end (); + exit (0); +} diff --git a/gmp/tests/mpn/t-fat.c b/gmp/tests/mpn/t-fat.c new file mode 100644 index 0000000000..abb288e4b0 --- /dev/null +++ b/gmp/tests/mpn/t-fat.c @@ -0,0 +1,311 @@ +/* Test fat binary setups. + +Copyright 2003, 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 <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" +#include "tests.h" + + +/* In this program we're aiming to pick up certain subtle problems that + might creep into a fat binary. + + 1. We want to ensure the application entry point routines like + __gmpn_add_n dispatch to the correct field of __gmpn_cpuvec. + + Note that these routines are not exercised as a side effect of other + tests (eg. the mpz routines). Internally the fields of __gmpn_cpuvec + are used directly, so we need to write test code explicitly calling + the mpn functions, like an application will have. + + 2. We want to ensure the initial __gmpn_cpuvec data has the initializer + function pointers in the correct fields, and that those initializer + functions dispatch to their correct corresponding field once + initialization has been done. + + Only one of the initializer routines executes in a normal program, + since that routine sets all the pointers to actual mpn functions. We + forcibly reset __gmpn_cpuvec so we can run each. + + In both cases for the above, the data put through the functions is + nothing special, just enough to verify that for instance an add_n is + really doing an add_n and has not for instance mistakenly gone to sub_n + or something. + + The loop around each test will exercise the initializer routine on the + first iteration, and the dispatcher routine on the second. + + If the dispatcher and/or initializer routines are generated mechanically + via macros (eg. mpn/x86/fat/fat_entry.asm) then there shouldn't be too + much risk of them going wrong, provided the structure layout is correctly + expressed. But if they're in C then it's good to guard against typos in + what is rather repetitive code. The initializer data for __gmpn_cpuvec + in fat.c is always done by hand and is likewise a bit repetitive. */ + + +/* dummies when not a fat binary */ +#if ! WANT_FAT_BINARY +struct cpuvec_t { + int dummy; +}; +struct cpuvec_t __gmpn_cpuvec; +#define ITERATE_FAT_THRESHOLDS() do { } while (0) +#endif + +/* saved from program startup */ +struct cpuvec_t initial_cpuvec; + +void +check_functions (void) +{ + mp_limb_t wp[2], xp[2], yp[2], r; + int i; + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 123; + yp[0] = 456; + mpn_add_n (wp, xp, yp, (mp_size_t) 1); + ASSERT_ALWAYS (wp[0] == 579); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 123; + wp[0] = 456; + r = mpn_addmul_1 (wp, xp, (mp_size_t) 1, CNST_LIMB(2)); + ASSERT_ALWAYS (wp[0] == 702); + ASSERT_ALWAYS (r == 0); + } + +#if HAVE_NATIVE_mpn_copyd + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 123; + xp[1] = 456; + mpn_copyd (xp+1, xp, (mp_size_t) 1); + ASSERT_ALWAYS (xp[1] == 123); + } +#endif + +#if HAVE_NATIVE_mpn_copyi + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 123; + xp[1] = 456; + mpn_copyi (xp, xp+1, (mp_size_t) 1); + ASSERT_ALWAYS (xp[0] == 456); + } +#endif + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 1605; + mpn_divexact_1 (wp, xp, (mp_size_t) 1, CNST_LIMB(5)); + ASSERT_ALWAYS (wp[0] == 321); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 1296; + r = mpn_divexact_by3c (wp, xp, (mp_size_t) 1, CNST_LIMB(0)); + ASSERT_ALWAYS (wp[0] == 432); + ASSERT_ALWAYS (r == 0); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 287; + r = mpn_divrem_1 (wp, (mp_size_t) 1, xp, (mp_size_t) 1, CNST_LIMB(7)); + ASSERT_ALWAYS (wp[1] == 41); + ASSERT_ALWAYS (wp[0] == 0); + ASSERT_ALWAYS (r == 0); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 12; + r = mpn_gcd_1 (xp, (mp_size_t) 1, CNST_LIMB(9)); + ASSERT_ALWAYS (r == 3); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 0x1001; + mpn_lshift (wp, xp, (mp_size_t) 1, 1); + ASSERT_ALWAYS (wp[0] == 0x2002); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 14; + r = mpn_mod_1 (xp, (mp_size_t) 1, CNST_LIMB(4)); + ASSERT_ALWAYS (r == 2); + } + +#if (GMP_NUMB_BITS % 4) == 0 + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + int bits = (GMP_NUMB_BITS / 4) * 3; + mp_limb_t mod = (CNST_LIMB(1) << bits) - 1; + mp_limb_t want = GMP_NUMB_MAX % mod; + xp[0] = GMP_NUMB_MAX; + r = mpn_mod_34lsub1 (xp, (mp_size_t) 1); + ASSERT_ALWAYS (r % mod == want); + } +#endif + + /* DECL_modexact_1c_odd ((*modexact_1c_odd)); */ + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 14; + r = mpn_mul_1 (wp, xp, (mp_size_t) 1, CNST_LIMB(4)); + ASSERT_ALWAYS (wp[0] == 56); + ASSERT_ALWAYS (r == 0); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 5; + yp[0] = 7; + mpn_mul_basecase (wp, xp, (mp_size_t) 1, yp, (mp_size_t) 1); + ASSERT_ALWAYS (wp[0] == 35); + ASSERT_ALWAYS (wp[1] == 0); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 5; + yp[0] = 7; + mpn_mullo_basecase (wp, xp, yp, (mp_size_t) 1); + ASSERT_ALWAYS (wp[0] == 35); + } + +#if HAVE_NATIVE_mpn_preinv_divrem_1 && GMP_NAIL_BITS == 0 + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 0x101; + r = mpn_preinv_divrem_1 (wp, (mp_size_t) 1, xp, (mp_size_t) 1, + GMP_LIMB_HIGHBIT, + refmpn_invert_limb (GMP_LIMB_HIGHBIT), 0); + ASSERT_ALWAYS (wp[0] == 0x202); + ASSERT_ALWAYS (wp[1] == 0); + ASSERT_ALWAYS (r == 0); + } +#endif + +#if GMP_NAIL_BITS == 0 + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = GMP_LIMB_HIGHBIT+123; + r = mpn_preinv_mod_1 (xp, (mp_size_t) 1, GMP_LIMB_HIGHBIT, + refmpn_invert_limb (GMP_LIMB_HIGHBIT)); + ASSERT_ALWAYS (r == 123); + } +#endif + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 0x8008; + mpn_rshift (wp, xp, (mp_size_t) 1, 1); + ASSERT_ALWAYS (wp[0] == 0x4004); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 5; + mpn_sqr_basecase (wp, xp, (mp_size_t) 1); + ASSERT_ALWAYS (wp[0] == 25); + ASSERT_ALWAYS (wp[1] == 0); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 999; + yp[0] = 666; + mpn_sub_n (wp, xp, yp, (mp_size_t) 1); + ASSERT_ALWAYS (wp[0] == 333); + } + + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); + for (i = 0; i < 2; i++) + { + xp[0] = 123; + wp[0] = 456; + r = mpn_submul_1 (wp, xp, (mp_size_t) 1, CNST_LIMB(2)); + ASSERT_ALWAYS (wp[0] == 210); + ASSERT_ALWAYS (r == 0); + } +} + +/* Expect the first use of each fat threshold to invoke the necessary + initialization. */ +void +check_thresholds (void) +{ +#define ITERATE(name,field) \ + do { \ + __gmpn_cpuvec_initialized = 0; \ + memcpy (&__gmpn_cpuvec, &initial_cpuvec, sizeof (__gmpn_cpuvec)); \ + ASSERT_ALWAYS (name != 0); \ + ASSERT_ALWAYS (name == __gmpn_cpuvec.field); \ + ASSERT_ALWAYS (__gmpn_cpuvec_initialized); \ + } while (0) + + ITERATE_FAT_THRESHOLDS (); +} + + +int +main (void) +{ + memcpy (&initial_cpuvec, &__gmpn_cpuvec, sizeof (__gmpn_cpuvec)); + + tests_start (); + + check_functions (); + check_thresholds (); + + tests_end (); + exit (0); +} diff --git a/gmp/tests/mpn/t-get_d.c b/gmp/tests/mpn/t-get_d.c new file mode 100644 index 0000000000..1499391e06 --- /dev/null +++ b/gmp/tests/mpn/t-get_d.c @@ -0,0 +1,498 @@ +/* Test mpn_get_d. + +Copyright 2002-2004 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 "config.h" + +#include <setjmp.h> +#include <signal.h> +#include <stdio.h> +#include <stdlib.h> + +#include "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + + +#ifndef _GMP_IEEE_FLOATS +#define _GMP_IEEE_FLOATS 0 +#endif + + +/* Exercise various 2^n values, with various exponents and positive and + negative. */ +void +check_onebit (void) +{ + static const int bit_table[] = { + 0, 1, 2, 3, + GMP_NUMB_BITS - 2, GMP_NUMB_BITS - 1, + GMP_NUMB_BITS, + GMP_NUMB_BITS + 1, GMP_NUMB_BITS + 2, + 2 * GMP_NUMB_BITS - 2, 2 * GMP_NUMB_BITS - 1, + 2 * GMP_NUMB_BITS, + 2 * GMP_NUMB_BITS + 1, 2 * GMP_NUMB_BITS + 2, + 3 * GMP_NUMB_BITS - 2, 3 * GMP_NUMB_BITS - 1, + 3 * GMP_NUMB_BITS, + 3 * GMP_NUMB_BITS + 1, 3 * GMP_NUMB_BITS + 2, + 4 * GMP_NUMB_BITS - 2, 4 * GMP_NUMB_BITS - 1, + 4 * GMP_NUMB_BITS, + 4 * GMP_NUMB_BITS + 1, 4 * GMP_NUMB_BITS + 2, + 5 * GMP_NUMB_BITS - 2, 5 * GMP_NUMB_BITS - 1, + 5 * GMP_NUMB_BITS, + 5 * GMP_NUMB_BITS + 1, 5 * GMP_NUMB_BITS + 2, + 6 * GMP_NUMB_BITS - 2, 6 * GMP_NUMB_BITS - 1, + 6 * GMP_NUMB_BITS, + 6 * GMP_NUMB_BITS + 1, 6 * GMP_NUMB_BITS + 2, + }; + static const int exp_table[] = { + 0, -100, -10, -1, 1, 10, 100, + }; + + /* FIXME: It'd be better to base this on the float format. */ +#if defined (__vax) || defined (__vax__) + int limit = 127; /* vax fp numbers have limited range */ +#else + int limit = 511; +#endif + + int bit_i, exp_i, i; + double got, want; + mp_size_t nsize, sign; + long bit, exp, want_bit; + mp_limb_t np[20]; + + for (bit_i = 0; bit_i < numberof (bit_table); bit_i++) + { + bit = bit_table[bit_i]; + + nsize = BITS_TO_LIMBS (bit+1); + refmpn_zero (np, nsize); + np[bit/GMP_NUMB_BITS] = CNST_LIMB(1) << (bit % GMP_NUMB_BITS); + + for (exp_i = 0; exp_i < numberof (exp_table); exp_i++) + { + exp = exp_table[exp_i]; + + want_bit = bit + exp; + if (want_bit >= limit || want_bit <= -limit) + continue; + + want = 1.0; + for (i = 0; i < want_bit; i++) + want *= 2.0; + for (i = 0; i > want_bit; i--) + want *= 0.5; + + for (sign = 0; sign >= -1; sign--, want = -want) + { + got = mpn_get_d (np, nsize, sign, exp); + if (got != want) + { + printf ("mpn_get_d wrong on 2^n\n"); + printf (" bit %ld\n", bit); + printf (" exp %ld\n", exp); + printf (" want_bit %ld\n", want_bit); + printf (" sign %ld\n", (long) sign); + mpn_trace (" n ", np, nsize); + printf (" nsize %ld\n", (long) nsize); + d_trace (" want ", want); + d_trace (" got ", got); + abort(); + } + } + } + } +} + + +/* Exercise values 2^n+1, while such a value fits the mantissa of a double. */ +void +check_twobit (void) +{ + int i, mant_bits; + double got, want; + mp_size_t nsize, sign; + mp_ptr np; + + mant_bits = tests_dbl_mant_bits (); + if (mant_bits == 0) + return; + + np = refmpn_malloc_limbs (BITS_TO_LIMBS (mant_bits)); + want = 3.0; + for (i = 1; i < mant_bits; i++) + { + nsize = BITS_TO_LIMBS (i+1); + refmpn_zero (np, nsize); + np[i/GMP_NUMB_BITS] = CNST_LIMB(1) << (i % GMP_NUMB_BITS); + np[0] |= 1; + + for (sign = 0; sign >= -1; sign--) + { + got = mpn_get_d (np, nsize, sign, 0); + if (got != want) + { + printf ("mpn_get_d wrong on 2^%d + 1\n", i); + printf (" sign %ld\n", (long) sign); + mpn_trace (" n ", np, nsize); + printf (" nsize %ld\n", (long) nsize); + d_trace (" want ", want); + d_trace (" got ", got); + abort(); + } + want = -want; + } + + want = 2.0 * want - 1.0; + } + + free (np); +} + + +/* Expect large negative exponents to underflow to 0.0. + Some systems might have hardware traps for such an underflow (though + usually it's not the default), so watch out for SIGFPE. */ +void +check_underflow (void) +{ + static const long exp_table[] = { + -999999L, LONG_MIN, + }; + static const mp_limb_t np[1] = { 1 }; + + static long exp; + mp_size_t nsize, sign; + double got; + int exp_i; + + nsize = numberof (np); + + if (tests_setjmp_sigfpe() == 0) + { + for (exp_i = 0; exp_i < numberof (exp_table); exp_i++) + { + exp = exp_table[exp_i]; + + for (sign = 0; sign >= -1; sign--) + { + got = mpn_get_d (np, nsize, sign, exp); + if (got != 0.0) + { + printf ("mpn_get_d wrong, didn't get 0.0 on underflow\n"); + printf (" nsize %ld\n", (long) nsize); + printf (" exp %ld\n", exp); + printf (" sign %ld\n", (long) sign); + d_trace (" got ", got); + abort (); + } + } + } + } + else + { + printf ("Warning, underflow to zero tests skipped due to SIGFPE (exp=%ld)\n", exp); + } + tests_sigfpe_done (); +} + + +/* Expect large values to result in +/-inf, on IEEE systems. */ +void +check_inf (void) +{ + static const long exp_table[] = { + 999999L, LONG_MAX, + }; + static const mp_limb_t np[4] = { 1, 1, 1, 1 }; + long exp; + mp_size_t nsize, sign, got_sign; + double got; + int exp_i; + + if (! _GMP_IEEE_FLOATS) + return; + + for (nsize = 1; nsize <= numberof (np); nsize++) + { + for (exp_i = 0; exp_i < numberof (exp_table); exp_i++) + { + exp = exp_table[exp_i]; + + for (sign = 0; sign >= -1; sign--) + { + got = mpn_get_d (np, nsize, sign, exp); + got_sign = (got >= 0 ? 0 : -1); + if (! tests_isinf (got)) + { + printf ("mpn_get_d wrong, didn't get infinity\n"); + bad: + printf (" nsize %ld\n", (long) nsize); + printf (" exp %ld\n", exp); + printf (" sign %ld\n", (long) sign); + d_trace (" got ", got); + printf (" got sign %ld\n", (long) got_sign); + abort (); + } + if (got_sign != sign) + { + printf ("mpn_get_d wrong sign on infinity\n"); + goto bad; + } + } + } + } +} + +/* Check values 2^n approaching and into IEEE denorm range. + Some systems might not support denorms, or might have traps setup, so + watch out for SIGFPE. */ +void +check_ieee_denorm (void) +{ + static long exp; + mp_limb_t n = 1; + long i; + mp_size_t sign; + double want, got; + + if (! _GMP_IEEE_FLOATS) + return; + + if (tests_setjmp_sigfpe() == 0) + { + exp = -1020; + want = 1.0; + for (i = 0; i > exp; i--) + want *= 0.5; + + for ( ; exp > -1500 && want != 0.0; exp--) + { + for (sign = 0; sign >= -1; sign--) + { + got = mpn_get_d (&n, (mp_size_t) 1, sign, exp); + if (got != want) + { + printf ("mpn_get_d wrong on denorm\n"); + printf (" n=1\n"); + printf (" exp %ld\n", exp); + printf (" sign %ld\n", (long) sign); + d_trace (" got ", got); + d_trace (" want ", want); + abort (); + } + want = -want; + } + want *= 0.5; + FORCE_DOUBLE (want); + } + } + else + { + printf ("Warning, IEEE denorm tests skipped due to SIGFPE (exp=%ld)\n", exp); + } + tests_sigfpe_done (); +} + + +/* Check values 2^n approaching exponent overflow. + Some systems might trap on overflow, so watch out for SIGFPE. */ +void +check_ieee_overflow (void) +{ + static long exp; + mp_limb_t n = 1; + long i; + mp_size_t sign; + double want, got; + + if (! _GMP_IEEE_FLOATS) + return; + + if (tests_setjmp_sigfpe() == 0) + { + exp = 1010; + want = 1.0; + for (i = 0; i < exp; i++) + want *= 2.0; + + for ( ; exp < 1050; exp++) + { + for (sign = 0; sign >= -1; sign--) + { + got = mpn_get_d (&n, (mp_size_t) 1, sign, exp); + if (got != want) + { + printf ("mpn_get_d wrong on overflow\n"); + printf (" n=1\n"); + printf (" exp %ld\n", exp); + printf (" sign %ld\n", (long) sign); + d_trace (" got ", got); + d_trace (" want ", want); + abort (); + } + want = -want; + } + want *= 2.0; + FORCE_DOUBLE (want); + } + } + else + { + printf ("Warning, IEEE overflow tests skipped due to SIGFPE (exp=%ld)\n", exp); + } + tests_sigfpe_done (); +} + + +/* ARM gcc 2.95.4 was seen generating bad code for ulong->double + conversions, resulting in for instance 0x81c25113 incorrectly converted. + This test exercises that value, to see mpn_get_d has avoided the + problem. */ +void +check_0x81c25113 (void) +{ +#if GMP_NUMB_BITS >= 32 + double want = 2176995603.0; + double got; + mp_limb_t np[4]; + mp_size_t nsize; + long exp; + + if (tests_dbl_mant_bits() < 32) + return; + + for (nsize = 1; nsize <= numberof (np); nsize++) + { + refmpn_zero (np, nsize-1); + np[nsize-1] = CNST_LIMB(0x81c25113); + exp = - (nsize-1) * GMP_NUMB_BITS; + got = mpn_get_d (np, nsize, (mp_size_t) 0, exp); + if (got != want) + { + printf ("mpn_get_d wrong on 2176995603 (0x81c25113)\n"); + printf (" nsize %ld\n", (long) nsize); + printf (" exp %ld\n", exp); + d_trace (" got ", got); + d_trace (" want ", want); + abort (); + } + } +#endif +} + + +void +check_rand (void) +{ + gmp_randstate_ptr rands = RANDS; + int rep, i; + unsigned long mant_bits; + long exp, exp_min, exp_max; + double got, want, d; + mp_size_t nalloc, nsize, sign; + mp_limb_t nhigh_mask; + mp_ptr np; + + mant_bits = tests_dbl_mant_bits (); + if (mant_bits == 0) + return; + + /* Allow for vax D format with exponent 127 to -128 only. + FIXME: Do something to probe for a valid exponent range. */ + exp_min = -100 - mant_bits; + exp_max = 100 - mant_bits; + + /* space for mant_bits */ + nalloc = BITS_TO_LIMBS (mant_bits); + np = refmpn_malloc_limbs (nalloc); + nhigh_mask = MP_LIMB_T_MAX + >> (GMP_NAIL_BITS + nalloc * GMP_NUMB_BITS - mant_bits); + + for (rep = 0; rep < 200; rep++) + { + /* random exp_min to exp_max, inclusive */ + exp = exp_min + (long) gmp_urandomm_ui (rands, exp_max - exp_min + 1); + + /* mant_bits worth of random at np */ + if (rep & 1) + mpn_random (np, nalloc); + else + mpn_random2 (np, nalloc); + nsize = nalloc; + np[nsize-1] &= nhigh_mask; + MPN_NORMALIZE (np, nsize); + if (nsize == 0) + continue; + + sign = (mp_size_t) gmp_urandomb_ui (rands, 1L) - 1; + + /* want = {np,nsize}, converting one bit at a time */ + want = 0.0; + for (i = 0, d = 1.0; i < mant_bits; i++, d *= 2.0) + if (np[i/GMP_NUMB_BITS] & (CNST_LIMB(1) << (i%GMP_NUMB_BITS))) + want += d; + if (sign < 0) + want = -want; + + /* want = want * 2^exp */ + for (i = 0; i < exp; i++) + want *= 2.0; + for (i = 0; i > exp; i--) + want *= 0.5; + + got = mpn_get_d (np, nsize, sign, exp); + + if (got != want) + { + printf ("mpn_get_d wrong on random data\n"); + printf (" sign %ld\n", (long) sign); + mpn_trace (" n ", np, nsize); + printf (" nsize %ld\n", (long) nsize); + printf (" exp %ld\n", exp); + d_trace (" want ", want); + d_trace (" got ", got); + abort(); + } + } + + free (np); +} + + +int +main (void) +{ + tests_start (); + mp_trace_base = -16; + + check_onebit (); + check_twobit (); + check_inf (); + check_underflow (); + check_ieee_denorm (); + check_ieee_overflow (); + check_0x81c25113 (); +#if ! (defined (__vax) || defined (__vax__)) + check_rand (); +#endif + + tests_end (); + exit (0); +} diff --git a/gmp/tests/mpn/t-hgcd.c b/gmp/tests/mpn/t-hgcd.c new file mode 100644 index 0000000000..64d33ef006 --- /dev/null +++ b/gmp/tests/mpn/t-hgcd.c @@ -0,0 +1,407 @@ +/* Test mpn_hgcd. + +Copyright 1991, 1993, 1994, 1996, 1997, 2000-2004 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +static mp_size_t one_test (mpz_t, mpz_t, int); +static void debug_mp (mpz_t, int); + +#define MIN_OPERAND_SIZE 2 + +/* Fixed values, for regression testing of mpn_hgcd. */ +struct value { int res; const char *a; const char *b; }; +static const struct value hgcd_values[] = { +#if GMP_NUMB_BITS == 32 + { 5, + "0x1bddff867272a9296ac493c251d7f46f09a5591fe", + "0xb55930a2a68a916450a7de006031068c5ddb0e5c" }, + { 4, + "0x2f0ece5b1ee9c15e132a01d55768dc13", + "0x1c6f4fd9873cdb24466e6d03e1cc66e7" }, + { 3, "0x7FFFFC003FFFFFFFFFC5", "0x3FFFFE001FFFFFFFFFE3"}, +#endif + { -1, NULL, NULL } +}; + +struct hgcd_ref +{ + mpz_t m[2][2]; +}; + +static void hgcd_ref_init (struct hgcd_ref *); +static void hgcd_ref_clear (struct hgcd_ref *); +static int hgcd_ref (struct hgcd_ref *, mpz_t, mpz_t); +static int hgcd_ref_equal (const struct hgcd_matrix *, const struct hgcd_ref *); + +int +main (int argc, char **argv) +{ + mpz_t op1, op2, temp1, temp2; + int i, j, chain_len; + gmp_randstate_ptr rands; + mpz_t bs; + unsigned long size_range; + + tests_start (); + rands = RANDS; + + mpz_init (bs); + mpz_init (op1); + mpz_init (op2); + mpz_init (temp1); + mpz_init (temp2); + + for (i = 0; hgcd_values[i].res >= 0; i++) + { + mp_size_t res; + + mpz_set_str (op1, hgcd_values[i].a, 0); + mpz_set_str (op2, hgcd_values[i].b, 0); + + res = one_test (op1, op2, -1-i); + if (res != hgcd_values[i].res) + { + fprintf (stderr, "ERROR in test %d\n", -1-i); + fprintf (stderr, "Bad return code from hgcd\n"); + fprintf (stderr, "op1="); debug_mp (op1, -16); + fprintf (stderr, "op2="); debug_mp (op2, -16); + fprintf (stderr, "expected: %d\n", hgcd_values[i].res); + fprintf (stderr, "hgcd: %d\n", (int) res); + abort (); + } + } + + for (i = 0; i < 15; i++) + { + /* Generate plain operands with unknown gcd. These types of operands + have proven to trigger certain bugs in development versions of the + gcd code. */ + + mpz_urandomb (bs, rands, 32); + size_range = mpz_get_ui (bs) % 13 + 2; + + mpz_urandomb (bs, rands, size_range); + mpz_rrandomb (op1, rands, mpz_get_ui (bs) + MIN_OPERAND_SIZE); + mpz_urandomb (bs, rands, size_range); + mpz_rrandomb (op2, rands, mpz_get_ui (bs) + MIN_OPERAND_SIZE); + + if (mpz_cmp (op1, op2) < 0) + mpz_swap (op1, op2); + + if (mpz_size (op1) > 0) + one_test (op1, op2, i); + + /* Generate a division chain backwards, allowing otherwise + unlikely huge quotients. */ + + mpz_set_ui (op1, 0); + mpz_urandomb (bs, rands, 32); + mpz_urandomb (bs, rands, mpz_get_ui (bs) % 16 + 1); + mpz_rrandomb (op2, rands, mpz_get_ui (bs)); + mpz_add_ui (op2, op2, 1); + +#if 0 + chain_len = 1000000; +#else + mpz_urandomb (bs, rands, 32); + chain_len = mpz_get_ui (bs) % (GMP_NUMB_BITS * GCD_DC_THRESHOLD / 256); +#endif + + for (j = 0; j < chain_len; j++) + { + mpz_urandomb (bs, rands, 32); + mpz_urandomb (bs, rands, mpz_get_ui (bs) % 12 + 1); + mpz_rrandomb (temp2, rands, mpz_get_ui (bs) + 1); + mpz_add_ui (temp2, temp2, 1); + mpz_mul (temp1, op2, temp2); + mpz_add (op1, op1, temp1); + + /* Don't generate overly huge operands. */ + if (SIZ (op1) > 3 * GCD_DC_THRESHOLD) + break; + + mpz_urandomb (bs, rands, 32); + mpz_urandomb (bs, rands, mpz_get_ui (bs) % 12 + 1); + mpz_rrandomb (temp2, rands, mpz_get_ui (bs) + 1); + mpz_add_ui (temp2, temp2, 1); + mpz_mul (temp1, op1, temp2); + mpz_add (op2, op2, temp1); + + /* Don't generate overly huge operands. */ + if (SIZ (op2) > 3 * GCD_DC_THRESHOLD) + break; + } + if (mpz_cmp (op1, op2) < 0) + mpz_swap (op1, op2); + + if (mpz_size (op1) > 0) + one_test (op1, op2, i); + } + + mpz_clear (bs); + mpz_clear (op1); + mpz_clear (op2); + mpz_clear (temp1); + mpz_clear (temp2); + + tests_end (); + exit (0); +} + +static void +debug_mp (mpz_t x, int base) +{ + mpz_out_str (stderr, base, x); fputc ('\n', stderr); +} + +static int +mpz_mpn_equal (const mpz_t a, mp_srcptr bp, mp_size_t bsize); + +static mp_size_t +one_test (mpz_t a, mpz_t b, int i) +{ + struct hgcd_matrix hgcd; + struct hgcd_ref ref; + + mpz_t ref_r0; + mpz_t ref_r1; + mpz_t hgcd_r0; + mpz_t hgcd_r1; + + mp_size_t res[2]; + mp_size_t asize; + mp_size_t bsize; + + mp_size_t hgcd_init_scratch; + mp_size_t hgcd_scratch; + + mp_ptr hgcd_init_tp; + mp_ptr hgcd_tp; + + asize = a->_mp_size; + bsize = b->_mp_size; + + ASSERT (asize >= bsize); + + hgcd_init_scratch = MPN_HGCD_MATRIX_INIT_ITCH (asize); + hgcd_init_tp = refmpn_malloc_limbs (hgcd_init_scratch); + mpn_hgcd_matrix_init (&hgcd, asize, hgcd_init_tp); + + hgcd_scratch = mpn_hgcd_itch (asize); + hgcd_tp = refmpn_malloc_limbs (hgcd_scratch); + +#if 0 + fprintf (stderr, + "one_test: i = %d asize = %d, bsize = %d\n", + i, a->_mp_size, b->_mp_size); + + gmp_fprintf (stderr, + "one_test: i = %d\n" + " a = %Zx\n" + " b = %Zx\n", + i, a, b); +#endif + hgcd_ref_init (&ref); + + mpz_init_set (ref_r0, a); + mpz_init_set (ref_r1, b); + res[0] = hgcd_ref (&ref, ref_r0, ref_r1); + + mpz_init_set (hgcd_r0, a); + mpz_init_set (hgcd_r1, b); + if (bsize < asize) + { + _mpz_realloc (hgcd_r1, asize); + MPN_ZERO (hgcd_r1->_mp_d + bsize, asize - bsize); + } + res[1] = mpn_hgcd (hgcd_r0->_mp_d, + hgcd_r1->_mp_d, + asize, + &hgcd, hgcd_tp); + + if (res[0] != res[1]) + { + fprintf (stderr, "ERROR in test %d\n", i); + fprintf (stderr, "Different return value from hgcd and hgcd_ref\n"); + fprintf (stderr, "op1="); debug_mp (a, -16); + fprintf (stderr, "op2="); debug_mp (b, -16); + fprintf (stderr, "hgcd_ref: %ld\n", (long) res[0]); + fprintf (stderr, "mpn_hgcd: %ld\n", (long) res[1]); + abort (); + } + if (res[0] > 0) + { + if (!hgcd_ref_equal (&hgcd, &ref) + || !mpz_mpn_equal (ref_r0, hgcd_r0->_mp_d, res[1]) + || !mpz_mpn_equal (ref_r1, hgcd_r1->_mp_d, res[1])) + { + fprintf (stderr, "ERROR in test %d\n", i); + fprintf (stderr, "mpn_hgcd and hgcd_ref returned different values\n"); + fprintf (stderr, "op1="); debug_mp (a, -16); + fprintf (stderr, "op2="); debug_mp (b, -16); + abort (); + } + } + + refmpn_free_limbs (hgcd_init_tp); + refmpn_free_limbs (hgcd_tp); + hgcd_ref_clear (&ref); + mpz_clear (ref_r0); + mpz_clear (ref_r1); + mpz_clear (hgcd_r0); + mpz_clear (hgcd_r1); + + return res[0]; +} + +static void +hgcd_ref_init (struct hgcd_ref *hgcd) +{ + unsigned i; + for (i = 0; i<2; i++) + { + unsigned j; + for (j = 0; j<2; j++) + mpz_init (hgcd->m[i][j]); + } +} + +static void +hgcd_ref_clear (struct hgcd_ref *hgcd) +{ + unsigned i; + for (i = 0; i<2; i++) + { + unsigned j; + for (j = 0; j<2; j++) + mpz_clear (hgcd->m[i][j]); + } +} + + +static int +sdiv_qr (mpz_t q, mpz_t r, mp_size_t s, const mpz_t a, const mpz_t b) +{ + mpz_fdiv_qr (q, r, a, b); + if (mpz_size (r) <= s) + { + mpz_add (r, r, b); + mpz_sub_ui (q, q, 1); + } + + return (mpz_sgn (q) > 0); +} + +static int +hgcd_ref (struct hgcd_ref *hgcd, mpz_t a, mpz_t b) +{ + mp_size_t n = MAX (mpz_size (a), mpz_size (b)); + mp_size_t s = n/2 + 1; + mp_size_t asize; + mp_size_t bsize; + mpz_t q; + int res; + + if (mpz_size (a) <= s || mpz_size (b) <= s) + return 0; + + res = mpz_cmp (a, b); + if (res < 0) + { + mpz_sub (b, b, a); + if (mpz_size (b) <= s) + return 0; + + mpz_set_ui (hgcd->m[0][0], 1); mpz_set_ui (hgcd->m[0][1], 0); + mpz_set_ui (hgcd->m[1][0], 1); mpz_set_ui (hgcd->m[1][1], 1); + } + else if (res > 0) + { + mpz_sub (a, a, b); + if (mpz_size (a) <= s) + return 0; + + mpz_set_ui (hgcd->m[0][0], 1); mpz_set_ui (hgcd->m[0][1], 1); + mpz_set_ui (hgcd->m[1][0], 0); mpz_set_ui (hgcd->m[1][1], 1); + } + else + return 0; + + mpz_init (q); + + for (;;) + { + ASSERT (mpz_size (a) > s); + ASSERT (mpz_size (b) > s); + + if (mpz_cmp (a, b) > 0) + { + if (!sdiv_qr (q, a, s, a, b)) + break; + mpz_addmul (hgcd->m[0][1], q, hgcd->m[0][0]); + mpz_addmul (hgcd->m[1][1], q, hgcd->m[1][0]); + } + else + { + if (!sdiv_qr (q, b, s, b, a)) + break; + mpz_addmul (hgcd->m[0][0], q, hgcd->m[0][1]); + mpz_addmul (hgcd->m[1][0], q, hgcd->m[1][1]); + } + } + + mpz_clear (q); + + asize = mpz_size (a); + bsize = mpz_size (b); + return MAX (asize, bsize); +} + +static int +mpz_mpn_equal (const mpz_t a, mp_srcptr bp, mp_size_t bsize) +{ + mp_srcptr ap = a->_mp_d; + mp_size_t asize = a->_mp_size; + + MPN_NORMALIZE (bp, bsize); + return asize == bsize && mpn_cmp (ap, bp, asize) == 0; +} + +static int +hgcd_ref_equal (const struct hgcd_matrix *hgcd, const struct hgcd_ref *ref) +{ + unsigned i; + + for (i = 0; i<2; i++) + { + unsigned j; + + for (j = 0; j<2; j++) + if (!mpz_mpn_equal (ref->m[i][j], hgcd->p[i][j], hgcd->n)) + return 0; + } + + return 1; +} diff --git a/gmp/tests/mpn/t-hgcd_appr.c b/gmp/tests/mpn/t-hgcd_appr.c new file mode 100644 index 0000000000..23ffbf0b76 --- /dev/null +++ b/gmp/tests/mpn/t-hgcd_appr.c @@ -0,0 +1,564 @@ +/* Test mpn_hgcd_appr. + +Copyright 1991, 1993, 1994, 1996, 1997, 2000-2004, 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 <string.h> + +#include "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +static mp_size_t one_test (mpz_t, mpz_t, int); +static void debug_mp (mpz_t, int); + +#define MIN_OPERAND_SIZE 2 + +struct hgcd_ref +{ + mpz_t m[2][2]; +}; + +static void hgcd_ref_init (struct hgcd_ref *hgcd); +static void hgcd_ref_clear (struct hgcd_ref *hgcd); +static int hgcd_ref (struct hgcd_ref *hgcd, mpz_t a, mpz_t b); +static int hgcd_ref_equal (const struct hgcd_ref *, const struct hgcd_ref *); +static int hgcd_appr_valid_p (mpz_t, mpz_t, mp_size_t, struct hgcd_ref *, + mpz_t, mpz_t, mp_size_t, struct hgcd_matrix *); + +static int verbose_flag = 0; + +int +main (int argc, char **argv) +{ + mpz_t op1, op2, temp1, temp2; + int i, j, chain_len; + gmp_randstate_ptr rands; + mpz_t bs; + unsigned long size_range; + + if (argc > 1) + { + if (strcmp (argv[1], "-v") == 0) + verbose_flag = 1; + else + { + fprintf (stderr, "Invalid argument.\n"); + return 1; + } + } + + tests_start (); + rands = RANDS; + + mpz_init (bs); + mpz_init (op1); + mpz_init (op2); + mpz_init (temp1); + mpz_init (temp2); + + for (i = 0; i < 15; i++) + { + /* Generate plain operands with unknown gcd. These types of operands + have proven to trigger certain bugs in development versions of the + gcd code. */ + + mpz_urandomb (bs, rands, 32); + size_range = mpz_get_ui (bs) % 13 + 2; + + mpz_urandomb (bs, rands, size_range); + mpz_urandomb (op1, rands, mpz_get_ui (bs) + MIN_OPERAND_SIZE); + mpz_urandomb (bs, rands, size_range); + mpz_urandomb (op2, rands, mpz_get_ui (bs) + MIN_OPERAND_SIZE); + + if (mpz_cmp (op1, op2) < 0) + mpz_swap (op1, op2); + + if (mpz_size (op1) > 0) + one_test (op1, op2, i); + + /* Generate a division chain backwards, allowing otherwise + unlikely huge quotients. */ + + mpz_set_ui (op1, 0); + mpz_urandomb (bs, rands, 32); + mpz_urandomb (bs, rands, mpz_get_ui (bs) % 16 + 1); + mpz_rrandomb (op2, rands, mpz_get_ui (bs)); + mpz_add_ui (op2, op2, 1); + +#if 0 + chain_len = 1000000; +#else + mpz_urandomb (bs, rands, 32); + chain_len = mpz_get_ui (bs) % (GMP_NUMB_BITS * GCD_DC_THRESHOLD / 256); +#endif + + for (j = 0; j < chain_len; j++) + { + mpz_urandomb (bs, rands, 32); + mpz_urandomb (bs, rands, mpz_get_ui (bs) % 12 + 1); + mpz_rrandomb (temp2, rands, mpz_get_ui (bs) + 1); + mpz_add_ui (temp2, temp2, 1); + mpz_mul (temp1, op2, temp2); + mpz_add (op1, op1, temp1); + + /* Don't generate overly huge operands. */ + if (SIZ (op1) > 3 * GCD_DC_THRESHOLD) + break; + + mpz_urandomb (bs, rands, 32); + mpz_urandomb (bs, rands, mpz_get_ui (bs) % 12 + 1); + mpz_rrandomb (temp2, rands, mpz_get_ui (bs) + 1); + mpz_add_ui (temp2, temp2, 1); + mpz_mul (temp1, op1, temp2); + mpz_add (op2, op2, temp1); + + /* Don't generate overly huge operands. */ + if (SIZ (op2) > 3 * GCD_DC_THRESHOLD) + break; + } + if (mpz_cmp (op1, op2) < 0) + mpz_swap (op1, op2); + + if (mpz_size (op1) > 0) + one_test (op1, op2, i); + } + + mpz_clear (bs); + mpz_clear (op1); + mpz_clear (op2); + mpz_clear (temp1); + mpz_clear (temp2); + + tests_end (); + exit (0); +} + +static void +debug_mp (mpz_t x, int base) +{ + mpz_out_str (stderr, base, x); fputc ('\n', stderr); +} + +static mp_size_t +one_test (mpz_t a, mpz_t b, int i) +{ + struct hgcd_matrix hgcd; + struct hgcd_ref ref; + + mpz_t ref_r0; + mpz_t ref_r1; + mpz_t hgcd_r0; + mpz_t hgcd_r1; + + int res[2]; + mp_size_t asize; + mp_size_t bsize; + + mp_size_t hgcd_init_scratch; + mp_size_t hgcd_scratch; + + mp_ptr hgcd_init_tp; + mp_ptr hgcd_tp; + mp_limb_t marker[4]; + + asize = a->_mp_size; + bsize = b->_mp_size; + + ASSERT (asize >= bsize); + + hgcd_init_scratch = MPN_HGCD_MATRIX_INIT_ITCH (asize); + hgcd_init_tp = refmpn_malloc_limbs (hgcd_init_scratch + 2) + 1; + mpn_hgcd_matrix_init (&hgcd, asize, hgcd_init_tp); + + hgcd_scratch = mpn_hgcd_appr_itch (asize); + hgcd_tp = refmpn_malloc_limbs (hgcd_scratch + 2) + 1; + + mpn_random (marker, 4); + + hgcd_init_tp[-1] = marker[0]; + hgcd_init_tp[hgcd_init_scratch] = marker[1]; + hgcd_tp[-1] = marker[2]; + hgcd_tp[hgcd_scratch] = marker[3]; + +#if 0 + fprintf (stderr, + "one_test: i = %d asize = %d, bsize = %d\n", + i, a->_mp_size, b->_mp_size); + + gmp_fprintf (stderr, + "one_test: i = %d\n" + " a = %Zx\n" + " b = %Zx\n", + i, a, b); +#endif + hgcd_ref_init (&ref); + + mpz_init_set (ref_r0, a); + mpz_init_set (ref_r1, b); + res[0] = hgcd_ref (&ref, ref_r0, ref_r1); + + mpz_init_set (hgcd_r0, a); + mpz_init_set (hgcd_r1, b); + if (bsize < asize) + { + _mpz_realloc (hgcd_r1, asize); + MPN_ZERO (hgcd_r1->_mp_d + bsize, asize - bsize); + } + res[1] = mpn_hgcd_appr (hgcd_r0->_mp_d, + hgcd_r1->_mp_d, + asize, + &hgcd, hgcd_tp); + + if (hgcd_init_tp[-1] != marker[0] + || hgcd_init_tp[hgcd_init_scratch] != marker[1] + || hgcd_tp[-1] != marker[2] + || hgcd_tp[hgcd_scratch] != marker[3]) + { + fprintf (stderr, "ERROR in test %d\n", i); + fprintf (stderr, "scratch space overwritten!\n"); + + if (hgcd_init_tp[-1] != marker[0]) + gmp_fprintf (stderr, + "before init_tp: %Mx\n" + "expected: %Mx\n", + hgcd_init_tp[-1], marker[0]); + if (hgcd_init_tp[hgcd_init_scratch] != marker[1]) + gmp_fprintf (stderr, + "after init_tp: %Mx\n" + "expected: %Mx\n", + hgcd_init_tp[hgcd_init_scratch], marker[1]); + if (hgcd_tp[-1] != marker[2]) + gmp_fprintf (stderr, + "before tp: %Mx\n" + "expected: %Mx\n", + hgcd_tp[-1], marker[2]); + if (hgcd_tp[hgcd_scratch] != marker[3]) + gmp_fprintf (stderr, + "after tp: %Mx\n" + "expected: %Mx\n", + hgcd_tp[hgcd_scratch], marker[3]); + + abort (); + } + + if (!hgcd_appr_valid_p (a, b, res[0], &ref, ref_r0, ref_r1, + res[1], &hgcd)) + { + fprintf (stderr, "ERROR in test %d\n", i); + fprintf (stderr, "Invalid results for hgcd and hgcd_ref\n"); + fprintf (stderr, "op1="); debug_mp (a, -16); + fprintf (stderr, "op2="); debug_mp (b, -16); + fprintf (stderr, "hgcd_ref: %ld\n", (long) res[0]); + fprintf (stderr, "mpn_hgcd_appr: %ld\n", (long) res[1]); + abort (); + } + + refmpn_free_limbs (hgcd_init_tp - 1); + refmpn_free_limbs (hgcd_tp - 1); + hgcd_ref_clear (&ref); + mpz_clear (ref_r0); + mpz_clear (ref_r1); + mpz_clear (hgcd_r0); + mpz_clear (hgcd_r1); + + return res[0]; +} + +static void +hgcd_ref_init (struct hgcd_ref *hgcd) +{ + unsigned i; + for (i = 0; i<2; i++) + { + unsigned j; + for (j = 0; j<2; j++) + mpz_init (hgcd->m[i][j]); + } +} + +static void +hgcd_ref_clear (struct hgcd_ref *hgcd) +{ + unsigned i; + for (i = 0; i<2; i++) + { + unsigned j; + for (j = 0; j<2; j++) + mpz_clear (hgcd->m[i][j]); + } +} + +static int +sdiv_qr (mpz_t q, mpz_t r, mp_size_t s, const mpz_t a, const mpz_t b) +{ + mpz_fdiv_qr (q, r, a, b); + if (mpz_size (r) <= s) + { + mpz_add (r, r, b); + mpz_sub_ui (q, q, 1); + } + + return (mpz_sgn (q) > 0); +} + +static int +hgcd_ref (struct hgcd_ref *hgcd, mpz_t a, mpz_t b) +{ + mp_size_t n = MAX (mpz_size (a), mpz_size (b)); + mp_size_t s = n/2 + 1; + mpz_t q; + int res; + + if (mpz_size (a) <= s || mpz_size (b) <= s) + return 0; + + res = mpz_cmp (a, b); + if (res < 0) + { + mpz_sub (b, b, a); + if (mpz_size (b) <= s) + return 0; + + mpz_set_ui (hgcd->m[0][0], 1); mpz_set_ui (hgcd->m[0][1], 0); + mpz_set_ui (hgcd->m[1][0], 1); mpz_set_ui (hgcd->m[1][1], 1); + } + else if (res > 0) + { + mpz_sub (a, a, b); + if (mpz_size (a) <= s) + return 0; + + mpz_set_ui (hgcd->m[0][0], 1); mpz_set_ui (hgcd->m[0][1], 1); + mpz_set_ui (hgcd->m[1][0], 0); mpz_set_ui (hgcd->m[1][1], 1); + } + else + return 0; + + mpz_init (q); + + for (;;) + { + ASSERT (mpz_size (a) > s); + ASSERT (mpz_size (b) > s); + + if (mpz_cmp (a, b) > 0) + { + if (!sdiv_qr (q, a, s, a, b)) + break; + mpz_addmul (hgcd->m[0][1], q, hgcd->m[0][0]); + mpz_addmul (hgcd->m[1][1], q, hgcd->m[1][0]); + } + else + { + if (!sdiv_qr (q, b, s, b, a)) + break; + mpz_addmul (hgcd->m[0][0], q, hgcd->m[0][1]); + mpz_addmul (hgcd->m[1][0], q, hgcd->m[1][1]); + } + } + + mpz_clear (q); + + return 1; +} + +static int +hgcd_ref_equal (const struct hgcd_ref *A, const struct hgcd_ref *B) +{ + unsigned i; + + for (i = 0; i<2; i++) + { + unsigned j; + + for (j = 0; j<2; j++) + if (mpz_cmp (A->m[i][j], B->m[i][j]) != 0) + return 0; + } + + return 1; +} + +static int +hgcd_appr_valid_p (mpz_t a, mpz_t b, mp_size_t res0, + struct hgcd_ref *ref, mpz_t ref_r0, mpz_t ref_r1, + mp_size_t res1, struct hgcd_matrix *hgcd) +{ + mp_size_t n = MAX (mpz_size (a), mpz_size (b)); + mp_size_t s = n/2 + 1; + + mp_bitcnt_t dbits, abits, margin; + mpz_t appr_r0, appr_r1, t, q; + struct hgcd_ref appr; + + if (!res0) + { + if (!res1) + return 1; + + fprintf (stderr, "mpn_hgcd_appr returned 1 when no reduction possible.\n"); + return 0; + } + + /* NOTE: No *_clear calls on error return, since we're going to + abort anyway. */ + mpz_init (t); + mpz_init (q); + hgcd_ref_init (&appr); + mpz_init (appr_r0); + mpz_init (appr_r1); + + if (mpz_size (ref_r0) <= s) + { + fprintf (stderr, "ref_r0 too small!!!: "); debug_mp (ref_r0, 16); + return 0; + } + if (mpz_size (ref_r1) <= s) + { + fprintf (stderr, "ref_r1 too small!!!: "); debug_mp (ref_r1, 16); + return 0; + } + + mpz_sub (t, ref_r0, ref_r1); + dbits = mpz_sizeinbase (t, 2); + if (dbits > s*GMP_NUMB_BITS) + { + fprintf (stderr, "ref |r0 - r1| too large!!!: "); debug_mp (t, 16); + return 0; + } + + if (!res1) + { + mpz_set (appr_r0, a); + mpz_set (appr_r1, b); + } + else + { + unsigned i; + + for (i = 0; i<2; i++) + { + unsigned j; + + for (j = 0; j<2; j++) + { + mp_size_t mn = hgcd->n; + MPN_NORMALIZE (hgcd->p[i][j], mn); + mpz_realloc (appr.m[i][j], mn); + MPN_COPY (PTR (appr.m[i][j]), hgcd->p[i][j], mn); + SIZ (appr.m[i][j]) = mn; + } + } + mpz_mul (appr_r0, appr.m[1][1], a); + mpz_mul (t, appr.m[0][1], b); + mpz_sub (appr_r0, appr_r0, t); + if (mpz_sgn (appr_r0) <= 0 + || mpz_size (appr_r0) <= s) + { + fprintf (stderr, "appr_r0 too small: "); debug_mp (appr_r0, 16); + return 0; + } + + mpz_mul (appr_r1, appr.m[1][0], a); + mpz_mul (t, appr.m[0][0], b); + mpz_sub (appr_r1, t, appr_r1); + if (mpz_sgn (appr_r1) <= 0 + || mpz_size (appr_r1) <= s) + { + fprintf (stderr, "appr_r1 too small: "); debug_mp (appr_r1, 16); + return 0; + } + } + + mpz_sub (t, appr_r0, appr_r1); + abits = mpz_sizeinbase (t, 2); + if (abits < dbits) + { + fprintf (stderr, "|r0 - r1| too small: "); debug_mp (t, 16); + return 0; + } + + /* We lose one bit each time we discard the least significant limbs. + For the lehmer code, that can happen at most s * (GMP_NUMB_BITS) + / (GMP_NUMB_BITS - 1) times. For the dc code, we lose an entire + limb (or more?) for each level of recursion. */ + + margin = (n/2+1) * GMP_NUMB_BITS / (GMP_NUMB_BITS - 1); + { + mp_size_t rn; + for (rn = n; ABOVE_THRESHOLD (rn, HGCD_APPR_THRESHOLD); rn = (rn + 1)/2) + margin += GMP_NUMB_BITS; + } + + if (verbose_flag && abits > dbits) + fprintf (stderr, "n = %u: sbits = %u: ref #(r0-r1): %u, appr #(r0-r1): %u excess: %d, margin: %u\n", + (unsigned) n, (unsigned) s*GMP_NUMB_BITS, + (unsigned) dbits, (unsigned) abits, + (int) (abits - s * GMP_NUMB_BITS), (unsigned) margin); + + if (abits > s*GMP_NUMB_BITS + margin) + { + fprintf (stderr, "appr |r0 - r1| much larger than minimal (by %u bits, margin = %u bits)\n", + (unsigned) (abits - s*GMP_NUMB_BITS), (unsigned) margin); + return 0; + } + + while (mpz_cmp (appr_r0, ref_r0) > 0 || mpz_cmp (appr_r1, ref_r1) > 0) + { + ASSERT (mpz_size (appr_r0) > s); + ASSERT (mpz_size (appr_r1) > s); + + if (mpz_cmp (appr_r0, appr_r1) > 0) + { + if (!sdiv_qr (q, appr_r0, s, appr_r0, appr_r1)) + break; + mpz_addmul (appr.m[0][1], q, appr.m[0][0]); + mpz_addmul (appr.m[1][1], q, appr.m[1][0]); + } + else + { + if (!sdiv_qr (q, appr_r1, s, appr_r1, appr_r0)) + break; + mpz_addmul (appr.m[0][0], q, appr.m[0][1]); + mpz_addmul (appr.m[1][0], q, appr.m[1][1]); + } + } + + if (mpz_cmp (appr_r0, ref_r0) != 0 + || mpz_cmp (appr_r1, ref_r1) != 0 + || !hgcd_ref_equal (ref, &appr)) + { + fprintf (stderr, "appr_r0: "); debug_mp (appr_r0, 16); + fprintf (stderr, "ref_r0: "); debug_mp (ref_r0, 16); + + fprintf (stderr, "appr_r1: "); debug_mp (appr_r1, 16); + fprintf (stderr, "ref_r1: "); debug_mp (ref_r1, 16); + + return 0; + } + mpz_clear (t); + mpz_clear (q); + hgcd_ref_clear (&appr); + mpz_clear (appr_r0); + mpz_clear (appr_r1); + + return 1; +} diff --git a/gmp/tests/mpn/t-instrument.c b/gmp/tests/mpn/t-instrument.c new file mode 100644 index 0000000000..338fef1773 --- /dev/null +++ b/gmp/tests/mpn/t-instrument.c @@ -0,0 +1,416 @@ +/* Test assembler support for --enable-profiling=instrument. + +Copyright 2002, 2003 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 "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" +#include "tests.h" + + +#if WANT_PROFILING_INSTRUMENT + +/* This program exercises each mpn routine that might be implemented in + assembler. It ensures the __cyg_profile_func_enter and exit calls have + come out right, and that in the x86 code "ret_internal" is correctly used + for PIC setups. */ + + +/* Changes to enter_seen done by __cyg_profile_func_enter are essentially + unknown to the optimizer, so must use volatile. */ +volatile int enter_seen; + +/* Dummy used to stop various calls going dead. */ +unsigned long notdead; + +const char *name = "<none>"; +int old_ncall; + +struct { + void *this_fn; + void *call_site; +} call[100]; +int ncall; + + +void __cyg_profile_func_enter (void *, void *) + __attribute__ ((no_instrument_function)); + +void +__cyg_profile_func_enter (void *this_fn, void *call_site) +{ +#if 0 + printf ("%24s %p %p\n", name, this_fn, call_site); +#endif + ASSERT_ALWAYS (ncall >= 0); + ASSERT_ALWAYS (ncall <= numberof (call)); + + if (ncall >= numberof (call)) + { + printf ("__cyg_profile_func_enter: oops, call stack full, from %s\n", name); + abort (); + } + + enter_seen = 1; + call[ncall].this_fn = this_fn; + call[ncall].call_site = call_site; + ncall++; +} + +void __cyg_profile_func_exit (void *, void *) + __attribute__ ((no_instrument_function)); + +void +__cyg_profile_func_exit (void *this_fn, void *call_site) +{ + ASSERT_ALWAYS (ncall >= 0); + ASSERT_ALWAYS (ncall <= numberof (call)); + + if (ncall == 0) + { + printf ("__cyg_profile_func_exit: call stack empty, from %s\n", name); + abort (); + } + + ncall--; + if (this_fn != call[ncall].this_fn || call_site != call[ncall].call_site) + { + printf ("__cyg_profile_func_exit: unbalanced this_fn/call_site from %s\n", name); + printf (" this_fn got %p\n", this_fn); + printf (" want %p\n", call[ncall].this_fn); + printf (" call_site got %p\n", call_site); + printf (" want %p\n", call[ncall].call_site); + abort (); + } +} + + +void +pre (const char *str) +{ + name = str; + enter_seen = 0; + old_ncall = ncall; +} + +void +post (void) +{ + if (! enter_seen) + { + printf ("did not reach __cyg_profile_func_enter from %s\n", name); + abort (); + } + + if (ncall != old_ncall) + { + printf ("unbalance enter/exit calls from %s\n", name); + printf (" ncall %d\n", ncall); + printf (" old_ncall %d\n", old_ncall); + abort (); + } +} + +void +check (void) +{ + mp_limb_t wp[100], xp[100], yp[100]; + mp_size_t size = 100; + + refmpn_zero (xp, size); + refmpn_zero (yp, size); + refmpn_zero (wp, size); + + pre ("mpn_add_n"); + mpn_add_n (wp, xp, yp, size); + post (); + +#if HAVE_NATIVE_mpn_add_nc + pre ("mpn_add_nc"); + mpn_add_nc (wp, xp, yp, size, CNST_LIMB(0)); + post (); +#endif + +#if HAVE_NATIVE_mpn_addlsh1_n + pre ("mpn_addlsh1_n"); + mpn_addlsh1_n (wp, xp, yp, size); + post (); +#endif + +#if HAVE_NATIVE_mpn_and_n + pre ("mpn_and_n"); + mpn_and_n (wp, xp, yp, size); + post (); +#endif + +#if HAVE_NATIVE_mpn_andn_n + pre ("mpn_andn_n"); + mpn_andn_n (wp, xp, yp, size); + post (); +#endif + + pre ("mpn_addmul_1"); + mpn_addmul_1 (wp, xp, size, yp[0]); + post (); + +#if HAVE_NATIVE_mpn_addmul_1c + pre ("mpn_addmul_1c"); + mpn_addmul_1c (wp, xp, size, yp[0], CNST_LIMB(0)); + post (); +#endif + +#if HAVE_NATIVE_mpn_com + pre ("mpn_com"); + mpn_com (wp, xp, size); + post (); +#endif + +#if HAVE_NATIVE_mpn_copyd + pre ("mpn_copyd"); + mpn_copyd (wp, xp, size); + post (); +#endif + +#if HAVE_NATIVE_mpn_copyi + pre ("mpn_copyi"); + mpn_copyi (wp, xp, size); + post (); +#endif + + pre ("mpn_divexact_1"); + mpn_divexact_1 (wp, xp, size, CNST_LIMB(123)); + post (); + + pre ("mpn_divexact_by3c"); + mpn_divexact_by3c (wp, xp, size, CNST_LIMB(0)); + post (); + + pre ("mpn_divrem_1"); + mpn_divrem_1 (wp, (mp_size_t) 0, xp, size, CNST_LIMB(123)); + post (); + +#if HAVE_NATIVE_mpn_divrem_1c + pre ("mpn_divrem_1c"); + mpn_divrem_1c (wp, (mp_size_t) 0, xp, size, CNST_LIMB(123), CNST_LIMB(122)); + post (); +#endif + + pre ("mpn_gcd_1"); + xp[0] |= 1; + notdead += (unsigned long) mpn_gcd_1 (xp, size, CNST_LIMB(123)); + post (); + + pre ("mpn_hamdist"); + notdead += mpn_hamdist (xp, yp, size); + post (); + +#if HAVE_NATIVE_mpn_ior_n + pre ("mpn_ior_n"); + mpn_ior_n (wp, xp, yp, size); + post (); +#endif + +#if HAVE_NATIVE_mpn_iorn_n + pre ("mpn_iorn_n"); + mpn_iorn_n (wp, xp, yp, size); + post (); +#endif + + pre ("mpn_lshift"); + mpn_lshift (wp, xp, size, 1); + post (); + + pre ("mpn_mod_1"); + notdead += mpn_mod_1 (xp, size, CNST_LIMB(123)); + post (); + +#if HAVE_NATIVE_mpn_mod_1c + pre ("mpn_mod_1c"); + notdead += mpn_mod_1c (xp, size, CNST_LIMB(123), CNST_LIMB(122)); + post (); +#endif + +#if GMP_NUMB_BITS % 4 == 0 + pre ("mpn_mod_34lsub1"); + notdead += mpn_mod_34lsub1 (xp, size); + post (); +#endif + + pre ("mpn_modexact_1_odd"); + notdead += mpn_modexact_1_odd (xp, size, CNST_LIMB(123)); + post (); + + pre ("mpn_modexact_1c_odd"); + notdead += mpn_modexact_1c_odd (xp, size, CNST_LIMB(123), CNST_LIMB(456)); + post (); + + pre ("mpn_mul_1"); + mpn_mul_1 (wp, xp, size, yp[0]); + post (); + +#if HAVE_NATIVE_mpn_mul_1c + pre ("mpn_mul_1c"); + mpn_mul_1c (wp, xp, size, yp[0], CNST_LIMB(0)); + post (); +#endif + +#if HAVE_NATIVE_mpn_mul_2 + pre ("mpn_mul_2"); + mpn_mul_2 (wp, xp, size-1, yp); + post (); +#endif + + pre ("mpn_mul_basecase"); + mpn_mul_basecase (wp, xp, (mp_size_t) 3, yp, (mp_size_t) 3); + post (); + +#if HAVE_NATIVE_mpn_nand_n + pre ("mpn_nand_n"); + mpn_nand_n (wp, xp, yp, size); + post (); +#endif + +#if HAVE_NATIVE_mpn_nior_n + pre ("mpn_nior_n"); + mpn_nior_n (wp, xp, yp, size); + post (); +#endif + + pre ("mpn_popcount"); + notdead += mpn_popcount (xp, size); + post (); + + pre ("mpn_preinv_mod_1"); + notdead += mpn_preinv_mod_1 (xp, size, GMP_NUMB_MAX, + refmpn_invert_limb (GMP_NUMB_MAX)); + post (); + +#if USE_PREINV_DIVREM_1 || HAVE_NATIVE_mpn_preinv_divrem_1 + pre ("mpn_preinv_divrem_1"); + mpn_preinv_divrem_1 (wp, (mp_size_t) 0, xp, size, GMP_NUMB_MAX, + refmpn_invert_limb (GMP_NUMB_MAX), 0); + post (); +#endif + +#if HAVE_NATIVE_mpn_rsh1add_n + pre ("mpn_rsh1add_n"); + mpn_rsh1add_n (wp, xp, yp, size); + post (); +#endif + +#if HAVE_NATIVE_mpn_rsh1sub_n + pre ("mpn_rsh1sub_n"); + mpn_rsh1sub_n (wp, xp, yp, size); + post (); +#endif + + pre ("mpn_rshift"); + mpn_rshift (wp, xp, size, 1); + post (); + + pre ("mpn_sqr_basecase"); + mpn_sqr_basecase (wp, xp, (mp_size_t) 3); + post (); + + pre ("mpn_submul_1"); + mpn_submul_1 (wp, xp, size, yp[0]); + post (); + +#if HAVE_NATIVE_mpn_submul_1c + pre ("mpn_submul_1c"); + mpn_submul_1c (wp, xp, size, yp[0], CNST_LIMB(0)); + post (); +#endif + + pre ("mpn_sub_n"); + mpn_sub_n (wp, xp, yp, size); + post (); + +#if HAVE_NATIVE_mpn_sub_nc + pre ("mpn_sub_nc"); + mpn_sub_nc (wp, xp, yp, size, CNST_LIMB(0)); + post (); +#endif + +#if HAVE_NATIVE_mpn_sublsh1_n + pre ("mpn_sublsh1_n"); + mpn_sublsh1_n (wp, xp, yp, size); + post (); +#endif + +#if HAVE_NATIVE_mpn_udiv_qrnnd + pre ("mpn_udiv_qrnnd"); + mpn_udiv_qrnnd (&wp[0], CNST_LIMB(122), xp[0], CNST_LIMB(123)); + post (); +#endif + +#if HAVE_NATIVE_mpn_udiv_qrnnd_r + pre ("mpn_udiv_qrnnd_r"); + mpn_udiv_qrnnd (CNST_LIMB(122), xp[0], CNST_LIMB(123), &wp[0]); + post (); +#endif + +#if HAVE_NATIVE_mpn_umul_ppmm + pre ("mpn_umul_ppmm"); + mpn_umul_ppmm (&wp[0], xp[0], yp[0]); + post (); +#endif + +#if HAVE_NATIVE_mpn_umul_ppmm_r + pre ("mpn_umul_ppmm_r"); + mpn_umul_ppmm_r (&wp[0], xp[0], yp[0]); + post (); +#endif + +#if HAVE_NATIVE_mpn_xor_n + pre ("mpn_xor_n"); + mpn_xor_n (wp, xp, yp, size); + post (); +#endif + +#if HAVE_NATIVE_mpn_xnor_n + pre ("mpn_xnor_n"); + mpn_xnor_n (wp, xp, yp, size); + post (); +#endif +} + + +int +main (void) +{ + tests_start (); + + check (); + + tests_end (); + exit (0); +} + + +#else /* ! WANT_PROFILING_INSTRUMENT */ + +int +main (void) +{ + exit (0); +} + +#endif diff --git a/gmp/tests/mpn/t-invert.c b/gmp/tests/mpn/t-invert.c new file mode 100644 index 0000000000..c9b0080b76 --- /dev/null +++ b/gmp/tests/mpn/t-invert.c @@ -0,0 +1,161 @@ +/* Test for mpn_invert function. + + Contributed to the GNU project by Marco Bodrato. + +Copyright 2009 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +/* Sizes are up to 2^SIZE_LOG limbs */ +#ifndef SIZE_LOG +#define SIZE_LOG 12 +#endif + +#ifndef COUNT +#define COUNT 1000 +#endif + +#define MAX_N (1L << SIZE_LOG) +#define MIN_N 1 + + +static int +invert_valid (mp_srcptr ip, mp_srcptr dp, mp_size_t n) +{ + mp_ptr tp; + int cy; + TMP_DECL; + + TMP_MARK; + tp = TMP_ALLOC_LIMBS (2*n); + + refmpn_mul (tp, ip, n, dp, n); + cy = refmpn_add_n (tp + n, tp + n, dp, n); /* This must not give a carry. */ + cy -= refmpn_add (tp, tp, 2*n, dp, n); /* This must give a carry. */ + TMP_FREE; + + return (cy == -1); +} + +/* + Check the result of the mpn_invert function in the library. +*/ + +int +main (int argc, char **argv) +{ + mp_ptr ip, dp, scratch; + int count = COUNT; + int test; + gmp_randstate_ptr rands; + TMP_DECL; + TMP_MARK; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + tests_start (); + rands = RANDS; + + dp = TMP_ALLOC_LIMBS (MAX_N); + ip = 1+TMP_ALLOC_LIMBS (MAX_N + 2); + scratch + = 1+TMP_ALLOC_LIMBS (mpn_invert_itch (MAX_N) + 2); + + for (test = 0; test < count; test++) + { + unsigned size_min; + unsigned size_range; + mp_size_t n; + mp_size_t itch; + mp_limb_t i_before, i_after, s_before, s_after; + + for (size_min = 1; (1L << size_min) < MIN_N; size_min++) + ; + + /* We generate an in the MIN_N <= n <= (1 << size_range). */ + size_range = size_min + + gmp_urandomm_ui (rands, SIZE_LOG + 1 - size_min); + + n = MIN_N + + gmp_urandomm_ui (rands, (1L << size_range) + 1 - MIN_N); + + mpn_random2 (dp, n); + + mpn_random2 (ip-1, n + 2); + i_before = ip[-1]; + i_after = ip[n]; + + itch = mpn_invert_itch (n); + ASSERT_ALWAYS (itch <= mpn_invert_itch (MAX_N)); + mpn_random2 (scratch-1, itch+2); + s_before = scratch[-1]; + s_after = scratch[itch]; + + dp[n-1] |= GMP_NUMB_HIGHBIT; + mpn_invert (ip, dp, n, scratch); + if (ip[-1] != i_before || ip[n] != i_after + || scratch[-1] != s_before || scratch[itch] != s_after + || ! invert_valid(ip, dp, n)) + { + printf ("ERROR in test %d, n = %d\n", + test, (int) n); + if (ip[-1] != i_before) + { + printf ("before ip:"); mpn_dump (ip -1, 1); + printf ("keep: "); mpn_dump (&i_before, 1); + } + if (ip[n] != i_after) + { + printf ("after ip:"); mpn_dump (ip + n, 1); + printf ("keep: "); mpn_dump (&i_after, 1); + } + if (scratch[-1] != s_before) + { + printf ("before scratch:"); mpn_dump (scratch-1, 1); + printf ("keep: "); mpn_dump (&s_before, 1); + } + if (scratch[itch] != s_after) + { + printf ("after scratch:"); mpn_dump (scratch + itch, 1); + printf ("keep: "); mpn_dump (&s_after, 1); + } + mpn_dump (dp, n); + mpn_dump (ip, n); + + abort(); + } + } + TMP_FREE; + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-iord_u.c b/gmp/tests/mpn/t-iord_u.c new file mode 100644 index 0000000000..93e68c5c3f --- /dev/null +++ b/gmp/tests/mpn/t-iord_u.c @@ -0,0 +1,221 @@ +/* Test MPN_INCR_U and MPN_DECR_U. + +Copyright 2001, 2002 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + + +/* The i386 MPN_INCR_U and MPN_DECR_U have special cases for "n" being a + compile-time constant 1, so that's exercised explicitly. */ + + +#define M GMP_NUMB_MAX +#define SIZE ((mp_size_t) 10) + + +void +check_one (const char *name, int i, + mp_srcptr src, mp_limb_t n, + mp_srcptr got, mp_srcptr want, mp_size_t size) +{ + if (! refmpn_equal_anynail (got, want, size)) + { + printf ("Wrong at %s i=%d\n", name, i); + mpn_trace (" src", src, size); + mpn_trace (" n", &n, (mp_size_t) 1); + mpn_trace (" got", got, size); + mpn_trace (" want", want, size); + abort (); + } +} + + +void +check_incr_data (void) +{ + static const struct { + mp_limb_t n; + const mp_limb_t src[SIZE]; + const mp_limb_t want[SIZE]; + } data[] = { + { 1, { 0 }, { 1 } }, + { 1, { 123 }, { 124 } }, + { 2, { 0 }, { 2 } }, + { 2, { 123 }, { 125 } }, + { M, { 0 }, { M } }, + + { 1, { M, 0 }, { 0, 1 } }, + { 1, { M, 123 }, { 0, 124 } }, + { 2, { M, 0 }, { 1, 1 } }, + { 2, { M, 123 }, { 1, 124 } }, + { M, { M, 0 }, { M-1, 1 } }, + { M, { M, 123 }, { M-1, 124 } }, + + { 1, { M, M, 0 }, { 0, 0, 1 } }, + { 1, { M, M, 123 }, { 0, 0, 124 } }, + { 2, { M, M, 0 }, { 1, 0, 1 } }, + { 2, { M, M, 123 }, { 1, 0, 124 } }, + { M, { M, M, 0 }, { M-1, 0, 1 } }, + { M, { M, M, 123 }, { M-1, 0, 124 } }, + + { 1, { M, M, M, 0 }, { 0, 0, 0, 1 } }, + { 1, { M, M, M, 123 }, { 0, 0, 0, 124 } }, + { 2, { M, M, M, 0 }, { 1, 0, 0, 1 } }, + { 2, { M, M, M, 123 }, { 1, 0, 0, 124 } }, + { M, { M, M, M, 0 }, { M-1, 0, 0, 1 } }, + { M, { M, M, M, 123 }, { M-1, 0, 0, 124 } }, + + { 1, { M, M, M, M, 0 }, { 0, 0, 0, 0, 1 } }, + { 1, { M, M, M, M, 123 }, { 0, 0, 0, 0, 124 } }, + { 2, { M, M, M, M, 0 }, { 1, 0, 0, 0, 1 } }, + { 2, { M, M, M, M, 123 }, { 1, 0, 0, 0, 124 } }, + { M, { M, M, M, M, 0 }, { M-1, 0, 0, 0, 1 } }, + { M, { M, M, M, M, 123 }, { M-1, 0, 0, 0, 124 +#if defined (__hpux) && ! defined (__GNUC__) + /* Some versions (at least HP92453-01 B.11.11.23709.GP) of the + HP C compilers fail to zero-fill aggregates as the ISO C standard + requires (cf 6.5.7 Initialization). Compensate here: */ + , 0, 0, 0, 0, 0 +#endif + } } + }; + + mp_limb_t got[SIZE]; + int i; + + for (i = 0; i < numberof (data); i++) + { + refmpn_copyi (got, data[i].src, SIZE); + MPN_INCR_U (got, SIZE, data[i].n); + check_one ("check_incr (general)", i, + data[i].src, data[i].n, + got, data[i].want, SIZE); + + if (data[i].n == 1) + { + refmpn_copyi (got, data[i].src, SIZE); + MPN_INCR_U (got, SIZE, CNST_LIMB(1)); + check_one ("check_incr (const 1)", i, + data[i].src, data[i].n, + got, data[i].want, SIZE); + } + } +} + +void +check_decr_data (void) +{ + static const struct { + mp_limb_t n; + const mp_limb_t src[SIZE]; + const mp_limb_t want[SIZE]; + } data[] = { + { 1, { 1 }, { 0 } }, + { 1, { 123 }, { 122 } }, + { 1, { M }, { M-1 } }, + { 2, { 2 }, { 0 } }, + { 2, { 123 }, { 121 } }, + { M, { M }, { 0 } }, + { M-1, { M }, { 1 } }, + + { 1, { 0, 1 }, { M, 0 } }, + { 1, { 0, 123 }, { M, 122 } }, + { 1, { 0, M }, { M, M-1 } }, + { 2, { 0, 123 }, { M-1, 122 } }, + { 2, { 1, 123 }, { M, 122 } }, + { M, { 0, 123 }, { 1, 122 } }, + { M, { M-1, M }, { M, M-1 } }, + + { 1, { 0, 0, 1 }, { M, M, 0 } }, + { 1, { 0, 0, 123 }, { M, M, 122 } }, + { 1, { 0, 0, M }, { M, M, M-1 } }, + { 2, { 0, 0, 123 }, { M-1, M, 122 } }, + { 2, { 1, 0, 123 }, { M, M, 122 } }, + { M, { 0, 0, 123 }, { 1, M, 122 } }, + { M, { M-1, 0, M }, { M, M, M-1 } }, + + { 1, { 0, 0, 0, 1 }, { M, M, M, 0 } }, + { 1, { 0, 0, 0, 123 }, { M, M, M, 122 } }, + { 1, { 0, 0, 0, M }, { M, M, M, M-1 } }, + { 2, { 0, 0, 0, 123 }, { M-1, M, M, 122 } }, + { 2, { 1, 0, 0, 123 }, { M, M, M, 122 } }, + { M, { 0, 0, 0, 123 }, { 1, M, M, 122 } }, + { M, { M-1, 0, 0, M }, { M, M, M, M-1 } }, + + { 1, { 0, 0, 0, 0, 1 }, { M, M, M, M, 0 } }, + { 1, { 0, 0, 0, 0, 123 }, { M, M, M, M, 122 } }, + { 1, { 0, 0, 0, 0, M }, { M, M, M, M, M-1 } }, + { 2, { 0, 0, 0, 0, 123 }, { M-1, M, M, M, 122 } }, + { 2, { 1, 0, 0, 0, 123 }, { M, M, M, M, 122 } }, + { M, { 0, 0, 0, 0, 123 }, { 1, M, M, M, 122 } }, + { M, { M-1, 0, 0, 0, M }, { M, M, M, M, M-1 } }, + + { 1, { 0, 0, 0, 0, 0, 1 }, { M, M, M, M, M, 0 } }, + { 1, { 0, 0, 0, 0, 0, 123 }, { M, M, M, M, M, 122 } }, + { 1, { 0, 0, 0, 0, 0, M }, { M, M, M, M, M, M-1 } }, + { 2, { 0, 0, 0, 0, 0, 123 }, { M-1, M, M, M, M, 122 } }, + { 2, { 1, 0, 0, 0, 0, 123 }, { M, M, M, M, M, 122 } }, + { M, { 0, 0, 0, 0, 0, 123 }, { 1, M, M, M, M, 122 } }, + { M, { M-1, 0, 0, 0, 0, M }, { M, M, M, M, M, M-1 +#if defined (__hpux) && ! defined (__GNUC__) + /* For explanation of this garbage, see previous function. */ + , 0, 0, 0, 0 +#endif + } } + }; + + mp_limb_t got[SIZE]; + int i; + + for (i = 0; i < numberof (data); i++) + { + refmpn_copyi (got, data[i].src, SIZE); + MPN_DECR_U (got, SIZE, data[i].n); + check_one ("check_decr_data", i, + data[i].src, data[i].n, + got, data[i].want, SIZE); + + if (data[i].n == 1) + { + refmpn_copyi (got, data[i].src, SIZE); + MPN_DECR_U (got, SIZE, CNST_LIMB(1)); + check_one ("check_decr (const 1)", i, + data[i].src, data[i].n, + got, data[i].want, SIZE); + } + } +} + + +int +main (void) +{ + tests_start (); + mp_trace_base = -16; + + check_incr_data (); + check_decr_data (); + + tests_end (); + exit (0); +} diff --git a/gmp/tests/mpn/t-matrix22.c b/gmp/tests/mpn/t-matrix22.c new file mode 100644 index 0000000000..e63cbe27bb --- /dev/null +++ b/gmp/tests/mpn/t-matrix22.c @@ -0,0 +1,207 @@ +/* Tests matrix22_mul. + +Copyright 2008 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +struct matrix { + mp_size_t alloc; + mp_size_t n; + mp_ptr e00, e01, e10, e11; +}; + +static void +matrix_init (struct matrix *M, mp_size_t n) +{ + mp_ptr p = refmpn_malloc_limbs (4*(n+1)); + M->e00 = p; p += n+1; + M->e01 = p; p += n+1; + M->e10 = p; p += n+1; + M->e11 = p; + M->alloc = n + 1; + M->n = 0; +} + +static void +matrix_clear (struct matrix *M) +{ + refmpn_free_limbs (M->e00); +} + +static void +matrix_copy (struct matrix *R, const struct matrix *M) +{ + R->n = M->n; + MPN_COPY (R->e00, M->e00, M->n); + MPN_COPY (R->e01, M->e01, M->n); + MPN_COPY (R->e10, M->e10, M->n); + MPN_COPY (R->e11, M->e11, M->n); +} + +/* Used with same size, so no need for normalization. */ +static int +matrix_equal_p (const struct matrix *A, const struct matrix *B) +{ + return (A->n == B->n + && mpn_cmp (A->e00, B->e00, A->n) == 0 + && mpn_cmp (A->e01, B->e01, A->n) == 0 + && mpn_cmp (A->e10, B->e10, A->n) == 0 + && mpn_cmp (A->e11, B->e11, A->n) == 0); +} + +static void +matrix_random(struct matrix *M, mp_size_t n, gmp_randstate_ptr rands) +{ + M->n = n; + mpn_random (M->e00, n); + mpn_random (M->e01, n); + mpn_random (M->e10, n); + mpn_random (M->e11, n); +} + +#define MUL(rp, ap, an, bp, bn) do { \ + if (an > bn) \ + mpn_mul (rp, ap, an, bp, bn); \ + else \ + mpn_mul (rp, bp, bn, ap, an); \ + } while(0) + +static void +ref_matrix22_mul (struct matrix *R, + const struct matrix *A, + const struct matrix *B, mp_ptr tp) +{ + mp_size_t an, bn, n; + mp_ptr r00, r01, r10, r11, a00, a01, a10, a11, b00, b01, b10, b11; + + if (A->n >= B->n) + { + r00 = R->e00; a00 = A->e00; b00 = B->e00; + r01 = R->e01; a01 = A->e01; b01 = B->e01; + r10 = R->e10; a10 = A->e10; b10 = B->e10; + r11 = R->e11; a11 = A->e11; b11 = B->e11; + an = A->n, bn = B->n; + } + else + { + /* Transpose */ + r00 = R->e00; a00 = B->e00; b00 = A->e00; + r01 = R->e10; a01 = B->e10; b01 = A->e10; + r10 = R->e01; a10 = B->e01; b10 = A->e01; + r11 = R->e11; a11 = B->e11; b11 = A->e11; + an = B->n, bn = A->n; + } + n = an + bn; + R->n = n + 1; + + mpn_mul (r00, a00, an, b00, bn); + mpn_mul (tp, a01, an, b10, bn); + r00[n] = mpn_add_n (r00, r00, tp, n); + + mpn_mul (r01, a00, an, b01, bn); + mpn_mul (tp, a01, an, b11, bn); + r01[n] = mpn_add_n (r01, r01, tp, n); + + mpn_mul (r10, a10, an, b00, bn); + mpn_mul (tp, a11, an, b10, bn); + r10[n] = mpn_add_n (r10, r10, tp, n); + + mpn_mul (r11, a10, an, b01, bn); + mpn_mul (tp, a11, an, b11, bn); + r11[n] = mpn_add_n (r11, r11, tp, n); +} + +static void +one_test (const struct matrix *A, const struct matrix *B, int i) +{ + struct matrix R; + struct matrix P; + mp_ptr tp; + + matrix_init (&R, A->n + B->n + 1); + matrix_init (&P, A->n + B->n + 1); + + tp = refmpn_malloc_limbs (mpn_matrix22_mul_itch (A->n, B->n)); + + ref_matrix22_mul (&R, A, B, tp); + matrix_copy (&P, A); + mpn_matrix22_mul (P.e00, P.e01, P.e10, P.e11, A->n, + B->e00, B->e01, B->e10, B->e11, B->n, tp); + P.n = A->n + B->n + 1; + if (!matrix_equal_p (&R, &P)) + { + fprintf (stderr, "ERROR in test %d\n", i); + gmp_fprintf (stderr, "A = (%Nx, %Nx\n %Nx, %Nx)\n" + "B = (%Nx, %Nx\n %Nx, %Nx)\n" + "R = (%Nx, %Nx (expected)\n %Nx, %Nx)\n" + "P = (%Nx, %Nx (incorrect)\n %Nx, %Nx)\n", + A->e00, A->n, A->e01, A->n, A->e10, A->n, A->e11, A->n, + B->e00, B->n, B->e01, B->n, B->e10, B->n, B->e11, B->n, + R.e00, R.n, R.e01, R.n, R.e10, R.n, R.e11, R.n, + P.e00, P.n, P.e01, P.n, P.e10, P.n, P.e11, P.n); + abort(); + } + refmpn_free_limbs (tp); + matrix_clear (&R); + matrix_clear (&P); +} + +#define MAX_SIZE (2+2*MATRIX22_STRASSEN_THRESHOLD) + +int +main (int argc, char **argv) +{ + struct matrix A; + struct matrix B; + + gmp_randstate_ptr rands; + mpz_t bs; + int i; + + tests_start (); + rands = RANDS; + + matrix_init (&A, MAX_SIZE); + matrix_init (&B, MAX_SIZE); + mpz_init (bs); + + for (i = 0; i < 1000; i++) + { + mp_size_t an, bn; + mpz_urandomb (bs, rands, 32); + an = 1 + mpz_get_ui (bs) % MAX_SIZE; + mpz_urandomb (bs, rands, 32); + bn = 1 + mpz_get_ui (bs) % MAX_SIZE; + + matrix_random (&A, an, rands); + matrix_random (&B, bn, rands); + + one_test (&A, &B, i); + } + mpz_clear (bs); + matrix_clear (&A); + matrix_clear (&B); + + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-minvert.c b/gmp/tests/mpn/t-minvert.c new file mode 100644 index 0000000000..ade61a1523 --- /dev/null +++ b/gmp/tests/mpn/t-minvert.c @@ -0,0 +1,179 @@ +/* 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> /* for strtol */ + +#include "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" +#include "tests/tests.h" + +#define MAX_SIZE 50 + +#define COUNT 200 + +static void +mpz_to_mpn (mp_ptr ap, mp_size_t an, const mpz_t b) +{ + mp_size_t bn = mpz_size (b); + ASSERT_ALWAYS (bn <= an); + MPN_COPY_INCR (ap, mpz_limbs_read (b), bn); + MPN_ZERO (ap + bn, an - bn); +} + +int +mpz_eq_mpn (mp_ptr ap, mp_size_t an, const mpz_t b) +{ + mp_size_t bn = mpz_size (b); + + return (bn >= 0 && bn <= an + && mpn_cmp (ap, mpz_limbs_read (b), bn) == 0 + && mpn_zero_p (ap + bn, an - bn)); +} + +static mp_bitcnt_t +bit_size (mp_srcptr xp, mp_size_t n) +{ + MPN_NORMALIZE (xp, n); + return n > 0 ? mpn_sizeinbase (xp, n, 2) : 0; +} + +int +main (int argc, char **argv) +{ + gmp_randstate_ptr rands; + long count = COUNT; + mp_ptr mp; + mp_ptr ap; + mp_ptr vp; + mp_ptr tp; + mp_ptr scratch; + mpz_t m, a, r, g; + int test; + mp_limb_t ran; + mp_size_t itch; + TMP_DECL; + + tests_start (); + rands = RANDS; + + + TMP_MARK; + mpz_init (m); + mpz_init (a); + mpz_init (r); + mpz_init (g); + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + mp = TMP_ALLOC_LIMBS (MAX_SIZE); + ap = TMP_ALLOC_LIMBS (MAX_SIZE); + vp = TMP_ALLOC_LIMBS (MAX_SIZE); + tp = TMP_ALLOC_LIMBS (MAX_SIZE); + scratch = TMP_ALLOC_LIMBS (mpn_sec_invert_itch (MAX_SIZE) + 1); + + for (test = 0; test < count; test++) + { + mp_bitcnt_t bits; + int rres, tres; + mp_size_t n; + + bits = urandom () % (GMP_NUMB_BITS * MAX_SIZE) + 1; + + if (test & 1) + mpz_rrandomb (m, rands, bits); + else + mpz_urandomb (m, rands, bits); + if (test & 2) + mpz_rrandomb (a, rands, bits); + else + mpz_urandomb (a, rands, bits); + + mpz_setbit (m, 0); + if (test & 4) + { + /* Ensure it really is invertible */ + if (mpz_sgn (a) == 0) + mpz_set_ui (a, 1); + else + for (;;) + { + mpz_gcd (g, a, m); + if (mpz_cmp_ui (g, 1) == 0) + break; + mpz_remove (a, a, g); + } + } + + rres = mpz_invert (r, a, m); + if ( (test & 4) && !rres) + { + gmp_fprintf (stderr, "test %d: Not invertible!\n" + "m = %Zd\n" + "a = %Zd\n", test, m, a); + abort (); + } + ASSERT_ALWAYS (! (test & 4) || rres); + + n = (bits + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS; + ASSERT_ALWAYS (n <= MAX_SIZE); + itch = mpn_sec_invert_itch (n); + scratch[itch] = ran = urandom (); + + mpz_to_mpn (ap, n, a); + mpz_to_mpn (mp, n, m); + tres = mpn_sec_invert (tp, ap, mp, n, + bit_size (ap, n) + bit_size (mp, n), + scratch); + + if (rres != tres || (rres == 1 && !mpz_eq_mpn (tp, n, r)) || ran != scratch[itch]) + { + gmp_fprintf (stderr, "Test %d failed.\n" + "m = %Zd\n" + "a = %Zd\n", test, m, a); + fprintf (stderr, "ref ret: %d\n" + "got ret: %d\n", rres, tres); + if (rres) + gmp_fprintf (stderr, "ref: %Zd\n", r); + if (tres) + gmp_fprintf (stderr, "got: %Nd\n", tp, n); + if (ran != scratch[itch]) + fprintf (stderr, "scratch[itch] changed.\n"); + abort (); + } + } + + TMP_FREE; + + mpz_clear (m); + mpz_clear (a); + mpz_clear (r); + mpz_clear (g); + + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-mod_1.c b/gmp/tests/mpn/t-mod_1.c new file mode 100644 index 0000000000..3d08a9018f --- /dev/null +++ b/gmp/tests/mpn/t-mod_1.c @@ -0,0 +1,129 @@ +/* Test mpn_mod_1 variants. + +Copyright 2010, 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +static void +check_one (mp_srcptr ap, mp_size_t n, mp_limb_t b) +{ + mp_limb_t r_ref = refmpn_mod_1 (ap, n, b); + mp_limb_t r; + + if (n >= 2) + { + mp_limb_t pre[4]; + mpn_mod_1_1p_cps (pre, b); + r = mpn_mod_1_1p (ap, n, b << pre[1], pre); + if (r != r_ref) + { + printf ("mpn_mod_1_1p failed\n"); + goto fail; + } + } + if ((b & GMP_NUMB_HIGHBIT) == 0) + { + mp_limb_t pre[5]; + mpn_mod_1s_2p_cps (pre, b); + r = mpn_mod_1s_2p (ap, n, b << pre[1], pre); + if (r != r_ref) + { + printf ("mpn_mod_1s_2p failed\n"); + goto fail; + } + } + if (b <= GMP_NUMB_MASK / 3) + { + mp_limb_t pre[6]; + mpn_mod_1s_3p_cps (pre, b); + r = mpn_mod_1s_3p (ap, n, b << pre[1], pre); + if (r != r_ref) + { + printf ("mpn_mod_1s_3p failed\n"); + goto fail; + } + } + if (b <= GMP_NUMB_MASK / 4) + { + mp_limb_t pre[7]; + mpn_mod_1s_4p_cps (pre, b); + r = mpn_mod_1s_4p (ap, n, b << pre[1], pre); + if (r != r_ref) + { + printf ("mpn_mod_1s_4p failed\n"); + goto fail; + } + } + r = mpn_mod_1 (ap, n, b); + if (r != r_ref) + { + printf ("mpn_mod_1 failed\n"); + fail: + printf ("an = %d, a: ", (int) n); mpn_dump (ap, n); + printf ("b : "); mpn_dump (&b, 1); + printf ("r (expected): "); mpn_dump (&r_ref, 1); + printf ("r (bad) : "); mpn_dump (&r, 1); + abort(); + } +} + +int +main (int argc, char **argv) +{ + gmp_randstate_ptr rands; + int i; + unsigned a_bits; + unsigned b_bits; + mpz_t a; + mpz_t b; + + tests_start (); + rands = RANDS; + mpz_init (a); + mpz_init (b); + + for (i = 0; i < 300; i++) + { + mp_size_t asize; + a_bits = 1 + gmp_urandomm_ui (rands, 1000); + b_bits = 1 + gmp_urandomm_ui (rands, GMP_NUMB_BITS); + + mpz_rrandomb (a, rands, a_bits); + mpz_rrandomb (b, rands, b_bits); + + asize = SIZ(a); + if (!asize) + asize = 1; + if (mpz_sgn (b) == 0) + mpz_set_ui (b, 1); + + check_one (PTR(a), asize, PTR(b)[0]); + } + + mpz_clear (a); + mpz_clear (b); + + tests_end (); + return 0; +} + diff --git a/gmp/tests/mpn/t-mp_bases.c b/gmp/tests/mpn/t-mp_bases.c new file mode 100644 index 0000000000..c0b228825a --- /dev/null +++ b/gmp/tests/mpn/t-mp_bases.c @@ -0,0 +1,105 @@ +/* Check mp_bases values. + +Copyright 2002 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 "gmp.h" +#include "gmp-impl.h" +#include "longlong.h" +#include "tests.h" + + +int +main (int argc, char *argv[]) +{ + mp_limb_t want_bb, want_bb_inv; + int base, want_chars_per_limb; + + want_chars_per_limb = refmpn_chars_per_limb (10); + if (MP_BASES_CHARS_PER_LIMB_10 != want_chars_per_limb) + { + printf ("MP_BASES_CHARS_PER_LIMB_10 wrong\n"); + abort (); + } + + want_bb = refmpn_big_base (10); + if (MP_BASES_BIG_BASE_10 != want_bb) + { + printf ("MP_BASES_BIG_BASE_10 wrong\n"); + abort (); + } + + want_bb_inv = refmpn_invert_limb + (want_bb << refmpn_count_leading_zeros (want_bb)); + if (MP_BASES_BIG_BASE_INVERTED_10 != want_bb_inv) + { + printf ("MP_BASES_BIG_BASE_INVERTED_10 wrong\n"); + abort (); + } + + if (MP_BASES_NORMALIZATION_STEPS_10 + != refmpn_count_leading_zeros (MP_BASES_BIG_BASE_10)) + { + printf ("MP_BASES_NORMALIZATION_STEPS_10 wrong\n"); + abort (); + } + + for (base = 2; base < numberof (mp_bases); base++) + { + want_chars_per_limb = refmpn_chars_per_limb (base); + if (mp_bases[base].chars_per_limb != want_chars_per_limb) + { + printf ("mp_bases[%d].chars_per_limb wrong\n", base); + printf (" got %d\n", mp_bases[base].chars_per_limb); + printf (" want %d\n", want_chars_per_limb); + abort (); + } + + if (POW2_P (base)) + { + want_bb = refmpn_count_trailing_zeros ((mp_limb_t) base); + if (mp_bases[base].big_base != want_bb) + { + printf ("mp_bases[%d].big_base (log2 of base) wrong\n", base); + abort (); + } + } + else + { + want_bb = refmpn_big_base (base); + if (mp_bases[base].big_base != want_bb) + { + printf ("mp_bases[%d].big_base wrong\n", base); + abort (); + } + +#if USE_PREINV_DIVREM_1 + want_bb_inv = refmpn_invert_limb + (want_bb << refmpn_count_leading_zeros (want_bb)); + if (mp_bases[base].big_base_inverted != want_bb_inv) + { + printf ("mp_bases[%d].big_base_inverted wrong\n", base); + abort (); + } +#endif + } + } + + exit (0); +} diff --git a/gmp/tests/mpn/t-mul.c b/gmp/tests/mpn/t-mul.c new file mode 100644 index 0000000000..26e4227334 --- /dev/null +++ b/gmp/tests/mpn/t-mul.c @@ -0,0 +1,101 @@ +/* Test mpn_mul function for all sizes up to a selected limit. + +Copyright 2011, 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +static unsigned +isqrt (unsigned t) +{ + unsigned s, b; + + for (b = 0, s = t; b++, s >>= 1; ) + ; + + s = 1 << (b >> 1); + if (b & 1) + s += s >> 1; + + do + { + b = t / s; + s = (s + b) >> 1; + } + while (b < s); + + return s; +} + +int +main (int argc, char **argv) +{ + mp_ptr ap, bp, rp, refp; + mp_size_t max_n, an, bn, rn; + gmp_randstate_ptr rands; + int reps; + TMP_DECL; + TMP_MARK; + + reps = 1; + + tests_start (); + TESTS_REPS (reps, argv, argc); + + rands = RANDS; + + /* Re-interpret reps argument as a size argument. */ + max_n = isqrt (reps * 25000); + + ap = TMP_ALLOC_LIMBS (max_n + 1); + bp = TMP_ALLOC_LIMBS (max_n + 1); + rp = TMP_ALLOC_LIMBS (2 * max_n); + refp = TMP_ALLOC_LIMBS (2 * max_n); + + for (an = 1; an <= max_n; an += 1) + { + for (bn = 1; bn <= an; bn += 1) + { + mpn_random2 (ap, an + 1); + mpn_random2 (bp, bn + 1); + + refmpn_mul (refp, ap, an, bp, bn); + mpn_mul (rp, ap, an, bp, bn); + + rn = an + bn; + if (mpn_cmp (refp, rp, rn)) + { + printf ("ERROR, an = %d, bn = %d, rn = %d\n", + (int) an, (int) bn, (int) rn); + printf ("a: "); mpn_dump (ap, an); + printf ("b: "); mpn_dump (bp, bn); + printf ("r: "); mpn_dump (rp, rn); + printf ("ref: "); mpn_dump (refp, rn); + abort(); + } + } + } + TMP_FREE; + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-mullo.c b/gmp/tests/mpn/t-mullo.c new file mode 100644 index 0000000000..d4789976ac --- /dev/null +++ b/gmp/tests/mpn/t-mullo.c @@ -0,0 +1,142 @@ +/* Test for mullo function. + +Copyright 2009 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +/* Sizes are up to 2^SIZE_LOG limbs */ +#ifndef SIZE_LOG +#define SIZE_LOG 10 +#endif + +#ifndef COUNT +#define COUNT 10000 +#endif + +#define MAX_N (1L << SIZE_LOG) +#define MIN_N (1) + +int +main (int argc, char **argv) +{ + mp_ptr ap, bp, refp, pp, scratch; + int count = COUNT; + int test; + gmp_randstate_ptr rands; + TMP_DECL; + TMP_MARK; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + tests_start (); + rands = RANDS; + +#define mpn_mullo_itch(n) (0) + + ap = TMP_ALLOC_LIMBS (MAX_N); + bp = TMP_ALLOC_LIMBS (MAX_N); + refp = TMP_ALLOC_LIMBS (MAX_N * 2); + pp = 1+TMP_ALLOC_LIMBS (MAX_N + 2); + scratch + = 1+TMP_ALLOC_LIMBS (mpn_mullo_itch (MAX_N) + 2); + + for (test = 0; test < count; test++) + { + unsigned size_min; + unsigned size_range; + mp_size_t n; + mp_size_t itch; + mp_limb_t p_before, p_after, s_before, s_after; + + for (size_min = 1; (1L << size_min) < MIN_N; size_min++) + ; + + /* We generate an in the MIN_N <= n <= (1 << size_range). */ + size_range = size_min + + gmp_urandomm_ui (rands, SIZE_LOG + 1 - size_min); + + n = MIN_N + + gmp_urandomm_ui (rands, (1L << size_range) + 1 - MIN_N); + + mpn_random2 (ap, n); + mpn_random2 (bp, n); + mpn_random2 (pp-1, n + 2); + p_before = pp[-1]; + p_after = pp[n]; + + itch = mpn_mullo_itch (n); + ASSERT_ALWAYS (itch <= mpn_mullo_itch (MAX_N)); + mpn_random2 (scratch-1, itch+2); + s_before = scratch[-1]; + s_after = scratch[itch]; + + mpn_mullo_n (pp, ap, bp, n); + mpn_mul_n (refp, ap, bp, n); + if (pp[-1] != p_before || pp[n] != p_after + || scratch[-1] != s_before || scratch[itch] != s_after + || mpn_cmp (refp, pp, n) != 0) + { + printf ("ERROR in test %d, n = %d", + test, (int) n); + if (pp[-1] != p_before) + { + printf ("before pp:"); mpn_dump (pp -1, 1); + printf ("keep: "); mpn_dump (&p_before, 1); + } + if (pp[n] != p_after) + { + printf ("after pp:"); mpn_dump (pp + n, 1); + printf ("keep: "); mpn_dump (&p_after, 1); + } + if (scratch[-1] != s_before) + { + printf ("before scratch:"); mpn_dump (scratch-1, 1); + printf ("keep: "); mpn_dump (&s_before, 1); + } + if (scratch[itch] != s_after) + { + printf ("after scratch:"); mpn_dump (scratch + itch, 1); + printf ("keep: "); mpn_dump (&s_after, 1); + } + mpn_dump (ap, n); + mpn_dump (bp, n); + mpn_dump (pp, n); + mpn_dump (refp, n); + + abort(); + } + } + TMP_FREE; + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-mulmid.c b/gmp/tests/mpn/t-mulmid.c new file mode 100644 index 0000000000..8978c4c1fd --- /dev/null +++ b/gmp/tests/mpn/t-mulmid.c @@ -0,0 +1,93 @@ +/* Test for mulmid function. + +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 <stdlib.h> +#include <stdio.h> + +#include "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +/* Sizes are up to 2^SIZE_LOG limbs */ +#ifndef SIZE_LOG +#define SIZE_LOG 9 +#endif + +#ifndef COUNT +#define COUNT 5000 +#endif + +#define MAX_N (1L << SIZE_LOG) + +int +main (int argc, char **argv) +{ + mp_ptr ap, bp, rp, refp; + gmp_randstate_ptr rands; + int test; + TMP_DECL; + TMP_MARK; + + tests_start (); + rands = RANDS; + + ap = TMP_ALLOC_LIMBS (MAX_N); + bp = TMP_ALLOC_LIMBS (MAX_N); + rp = TMP_ALLOC_LIMBS (MAX_N + 2); + refp = TMP_ALLOC_LIMBS (MAX_N + 2); + + for (test = 0; test < COUNT; test++) + { + mp_size_t an, bn, rn; + unsigned size_log; + + size_log = 1 + gmp_urandomm_ui (rands, SIZE_LOG); + an = 1 + gmp_urandomm_ui(rands, 1L << size_log); + + size_log = 1 + gmp_urandomm_ui (rands, SIZE_LOG); + bn = 1 + gmp_urandomm_ui(rands, 1L << size_log); + + /* Make sure an >= bn */ + if (an < bn) + MP_SIZE_T_SWAP (an, bn); + + mpn_random2 (ap, an); + mpn_random2 (bp, bn); + + refmpn_mulmid (refp, ap, an, bp, bn); + mpn_mulmid (rp, ap, an, bp, bn); + + rn = an + 3 - bn; + if (mpn_cmp (refp, rp, rn)) + { + printf ("ERROR in test %d, an = %d, bn = %d, rn = %d\n", + test, (int) an, (int) bn, (int) rn); + printf("a: "); mpn_dump (ap, an); + printf("b: "); mpn_dump (bp, bn); + printf("r: "); mpn_dump (rp, rn); + printf("ref: "); mpn_dump (refp, rn); + + abort(); + } + } + TMP_FREE; + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-mulmod_bnm1.c b/gmp/tests/mpn/t-mulmod_bnm1.c new file mode 100644 index 0000000000..374b722c6b --- /dev/null +++ b/gmp/tests/mpn/t-mulmod_bnm1.c @@ -0,0 +1,218 @@ +/* Test for mulmod_bnm1 function. + + Contributed to the GNU project by Marco Bodrato. + +Copyright 2009 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +/* Sizes are up to 2^SIZE_LOG limbs */ +#ifndef SIZE_LOG +#define SIZE_LOG 11 +#endif + +#ifndef COUNT +#define COUNT 5000 +#endif + +#define MAX_N (1L << SIZE_LOG) +#define MIN_N 1 + +/* + Reference function for multiplication modulo B^rn-1. + + The result is expected to be ZERO if and only if one of the operand + already is. Otherwise the class [0] Mod(B^rn-1) is represented by + B^rn-1. This should not be a problem if mulmod_bnm1 is used to + combine results and obtain a natural number when one knows in + advance that the final value is less than (B^rn-1). +*/ + +static void +ref_mulmod_bnm1 (mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an, mp_srcptr bp, mp_size_t bn) +{ + mp_limb_t cy; + + ASSERT (0 < an && an <= rn); + ASSERT (0 < bn && bn <= rn); + + if (an >= bn) + refmpn_mul (rp, ap, an, bp, bn); + else + refmpn_mul (rp, bp, bn, ap, an); + an += bn; + if (an > rn) { + cy = mpn_add (rp, rp, rn, rp + rn, an - rn); + /* If cy == 1, then the value of rp is at most B^rn - 2, so there can + * be no overflow when adding in the carry. */ + MPN_INCR_U (rp, rn, cy); + } +} + +/* + Compare the result of the mpn_mulmod_bnm1 function in the library + with the reference function above. +*/ + +int +main (int argc, char **argv) +{ + mp_ptr ap, bp, refp, pp, scratch; + int count = COUNT; + int test; + gmp_randstate_ptr rands; + TMP_DECL; + TMP_MARK; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + tests_start (); + rands = RANDS; + + ASSERT_ALWAYS (mpn_mulmod_bnm1_next_size (MAX_N) == MAX_N); + + ap = TMP_ALLOC_LIMBS (MAX_N); + bp = TMP_ALLOC_LIMBS (MAX_N); + refp = TMP_ALLOC_LIMBS (MAX_N * 4); + pp = 1+TMP_ALLOC_LIMBS (MAX_N + 2); + scratch + = 1+TMP_ALLOC_LIMBS (mpn_mulmod_bnm1_itch (MAX_N, MAX_N, MAX_N) + 2); + + for (test = 0; test < count; test++) + { + unsigned size_min; + unsigned size_range; + mp_size_t an,bn,rn,n; + mp_size_t itch; + mp_limb_t p_before, p_after, s_before, s_after; + + for (size_min = 1; (1L << size_min) < MIN_N; size_min++) + ; + + /* We generate an in the MIN_N <= n <= (1 << size_range). */ + size_range = size_min + + gmp_urandomm_ui (rands, SIZE_LOG + 1 - size_min); + + n = MIN_N + + gmp_urandomm_ui (rands, (1L << size_range) + 1 - MIN_N); + n = mpn_mulmod_bnm1_next_size (n); + + if ( (test & 1) || n == 1) { + /* Half of the tests are done with the main scenario in mind: + both an and bn >= rn/2 */ + an = ((n+1) >> 1) + gmp_urandomm_ui (rands, (n+1) >> 1); + bn = ((n+1) >> 1) + gmp_urandomm_ui (rands, (n+1) >> 1); + } else { + /* Second half of the tests are done using mulmod to compute a + full product with n/2 < an+bn <= n. */ + an = 1 + gmp_urandomm_ui (rands, n - 1); + if (an >= n/2) + bn = 1 + gmp_urandomm_ui (rands, n - an); + else + bn = n/2 + 1 - an + gmp_urandomm_ui (rands, (n+1)/2); + } + + /* Make sure an >= bn */ + if (an < bn) + MP_SIZE_T_SWAP (an, bn); + + mpn_random2 (ap, an); + mpn_random2 (bp, bn); + + /* Sometime trigger the borderline conditions + A = -1,0,+1 or B = -1,0,+1 or A*B == -1,0,1 Mod(B^{n/2}+1). + This only makes sense if there is at least a split, i.e. n is even. */ + if ((test & 0x1f) == 1 && (n & 1) == 0) { + mp_size_t x; + MPN_COPY (ap, ap + (n >> 1), an - (n >> 1)); + MPN_ZERO (ap + an - (n >> 1) , n - an); + MPN_COPY (bp, bp + (n >> 1), bn - (n >> 1)); + MPN_ZERO (bp + bn - (n >> 1) , n - bn); + x = (n == an) ? 0 : gmp_urandomm_ui (rands, n - an); + ap[x] += gmp_urandomm_ui (rands, 3) - 1; + x = (n >> 1) - x % (n >> 1); + bp[x] += gmp_urandomm_ui (rands, 3) - 1; + /* We don't propagate carry, this means that the desired condition + is not triggered all the times. A few times are enough anyway. */ + } + rn = MIN(n, an + bn); + mpn_random2 (pp-1, rn + 2); + p_before = pp[-1]; + p_after = pp[rn]; + + itch = mpn_mulmod_bnm1_itch (n, an, bn); + ASSERT_ALWAYS (itch <= mpn_mulmod_bnm1_itch (MAX_N, MAX_N, MAX_N)); + mpn_random2 (scratch-1, itch+2); + s_before = scratch[-1]; + s_after = scratch[itch]; + + mpn_mulmod_bnm1 ( pp, n, ap, an, bp, bn, scratch); + ref_mulmod_bnm1 (refp, n, ap, an, bp, bn); + if (pp[-1] != p_before || pp[rn] != p_after + || scratch[-1] != s_before || scratch[itch] != s_after + || mpn_cmp (refp, pp, rn) != 0) + { + printf ("ERROR in test %d, an = %d, bn = %d, n = %d\n", + test, (int) an, (int) bn, (int) n); + if (pp[-1] != p_before) + { + printf ("before pp:"); mpn_dump (pp -1, 1); + printf ("keep: "); mpn_dump (&p_before, 1); + } + if (pp[rn] != p_after) + { + printf ("after pp:"); mpn_dump (pp + rn, 1); + printf ("keep: "); mpn_dump (&p_after, 1); + } + if (scratch[-1] != s_before) + { + printf ("before scratch:"); mpn_dump (scratch-1, 1); + printf ("keep: "); mpn_dump (&s_before, 1); + } + if (scratch[itch] != s_after) + { + printf ("after scratch:"); mpn_dump (scratch + itch, 1); + printf ("keep: "); mpn_dump (&s_after, 1); + } + mpn_dump (ap, an); + mpn_dump (bp, bn); + mpn_dump (pp, rn); + mpn_dump (refp, rn); + + abort(); + } + } + TMP_FREE; + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-perfsqr.c b/gmp/tests/mpn/t-perfsqr.c new file mode 100644 index 0000000000..322ab6c3a4 --- /dev/null +++ b/gmp/tests/mpn/t-perfsqr.c @@ -0,0 +1,117 @@ +/* Test mpn_perfect_square_p data. + +Copyright 2002 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +#include "mpn/perfsqr.h" + + +#define PERFSQR_MOD_MASK ((CNST_LIMB(1) << PERFSQR_MOD_BITS) - 1) + +void +check_mod_2 (mp_limb_t d, mp_limb_t inv, mp_limb_t got_hi, mp_limb_t got_lo) +{ + int want[2*GMP_LIMB_BITS], got; + unsigned r, idx; + mp_limb_t q; + + ASSERT_ALWAYS (d <= numberof (want)); + ASSERT_ALWAYS (((inv * d) & PERFSQR_MOD_MASK) == 1); + ASSERT_ALWAYS (MP_LIMB_T_MAX / d >= PERFSQR_MOD_MASK); + + /* the squares mod d */ + for (r = 0; r < d; r++) + want[r] = 0; + for (r = 0; r < d; r++) + want[(r*r)%d] = 1; + + /* for each remainder mod d, expect the table data to correctly identify + it as a residue or non-residue */ + for (r = 0; r < d; r++) + { + /* as per PERFSQR_MOD_IDX */ + q = ((r) * (inv)) & PERFSQR_MOD_MASK; + idx = (q * (d)) >> PERFSQR_MOD_BITS; + + if (idx >= GMP_LIMB_BITS) + got = (got_hi >> (idx - GMP_LIMB_BITS)) & 1; + else + got = (got_lo >> idx) & 1; + + if (got != want[r]) + { + printf ("Wrong generated data\n"); + printf (" d=%u\n", (unsigned) d); + printf (" r=%u\n", r); + printf (" idx=%u\n", idx); + printf (" got %d\n", got); + printf (" want %d\n", want[r]); + abort (); + } + } +} + +/* Check the generated data in perfsqr.h. */ +void +check_mod (void) +{ +#define PERFSQR_MOD_34(r, up, usize) { r = 0; } /* so r isn't unused */ +#define PERFSQR_MOD_PP(r, up, usize) { r = 0; } +#define PERFSQR_MOD_1(r, d, inv, mask) check_mod_2 (d, inv, CNST_LIMB(0), mask) +#define PERFSQR_MOD_2(r, d, inv, mhi, mlo) check_mod_2 (d, inv, mhi, mlo) + + PERFSQR_MOD_TEST (dummy, dummy); +} + +/* Check PERFSQR_PP, if in use. */ +void +check_pp (void) +{ +#ifdef PERFSQR_PP + ASSERT_ALWAYS_LIMB (PERFSQR_PP); + ASSERT_ALWAYS_LIMB (PERFSQR_PP_NORM); + ASSERT_ALWAYS_LIMB (PERFSQR_PP_INVERTED); + + /* preinv stuff only for nails==0 */ + if (GMP_NAIL_BITS == 0) + { + ASSERT_ALWAYS (PERFSQR_PP_NORM + == PERFSQR_PP << refmpn_count_leading_zeros (PERFSQR_PP)); + ASSERT_ALWAYS (PERFSQR_PP_INVERTED + == refmpn_invert_limb (PERFSQR_PP_NORM)); + } +#endif +} + +int +main (void) +{ + tests_start (); + + check_mod (); + check_pp (); + + tests_end (); + exit (0); +} diff --git a/gmp/tests/mpn/t-scan.c b/gmp/tests/mpn/t-scan.c new file mode 100644 index 0000000000..f4478af335 --- /dev/null +++ b/gmp/tests/mpn/t-scan.c @@ -0,0 +1,145 @@ +/* Test mpn_scan0 and mpn_scan1. + +Copyright 2002 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 "gmp.h" +#include "gmp-impl.h" + +#include "tests.h" + + +#define SIZE ((mp_size_t) 3) +mp_limb_t x[SIZE+1]; + +void +check (void) +{ + unsigned long i, got, want; + + x[SIZE] = 1; + for (i = 0; i < SIZE*GMP_NUMB_BITS; i++) + { + got = refmpn_scan1 (x, i); + want = mpn_scan1 (x, i); + if (got != want) + { + printf ("mpn_scan1\n"); + printf (" i %lu\n", i); + printf (" got %lu\n", got); + printf (" want %lu\n", want); + mpn_trace (" x ", x, SIZE); + abort (); + } + } + + x[SIZE] = 0; + for (i = 0; i < SIZE*GMP_NUMB_BITS; i++) + { + got = refmpn_scan0 (x, i); + want = mpn_scan0 (x, i); + if (got != want) + { + printf ("mpn_scan0\n"); + printf (" i %lu\n", i); + printf (" got %lu\n", got); + printf (" want %lu\n", want); + mpn_trace (" x ", x, SIZE); + abort (); + } + } +} + +void +check_twobits (void) +{ +#define TWOBITS(a, b) \ + ((CNST_LIMB(1) << (a)) | (CNST_LIMB(1) << (b))) + + refmpn_zero (x, SIZE); + x[0] = TWOBITS (1, 0); + check (); + + refmpn_zero (x, SIZE); + x[0] = TWOBITS (GMP_NUMB_BITS-1, 1); + check (); + + refmpn_zero (x, SIZE); + x[0] = CNST_LIMB(1); + x[1] = CNST_LIMB(1); + check (); + + refmpn_zero (x, SIZE); + x[0] = CNST_LIMB(1) << (GMP_NUMB_BITS-1); + x[1] = CNST_LIMB(1); + check (); + + refmpn_zero (x, SIZE); + x[1] = TWOBITS (1, 0); + check (); + + refmpn_zero (x, SIZE); + x[1] = CNST_LIMB(1); + x[2] = CNST_LIMB(1); + check (); +} + +/* This is unused, it takes too long, especially on 64-bit systems. */ +void +check_twobits_exhaustive (void) +{ + unsigned long i, j; + + for (i = 0; i < GMP_NUMB_BITS * SIZE; i++) + { + for (j = 0; j < GMP_NUMB_BITS * SIZE; j++) + { + refmpn_zero (x, SIZE); + refmpn_setbit (x, i); + refmpn_setbit (x, j); + check (); + } + } +} + +void +check_rand (void) +{ + int i; + + for (i = 0; i < 100; i++) + { + refmpn_random2 (x, SIZE); + check (); + } +} + +int +main (void) +{ + mp_trace_base = -16; + tests_start (); + + check_twobits (); + check_rand (); + + tests_end (); + exit (0); +} diff --git a/gmp/tests/mpn/t-sizeinbase.c b/gmp/tests/mpn/t-sizeinbase.c new file mode 100644 index 0000000000..0887815d8b --- /dev/null +++ b/gmp/tests/mpn/t-sizeinbase.c @@ -0,0 +1,108 @@ +/* Test for sizeinbase function. + +Copyright 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 <stdlib.h> +#include <stdio.h> + +#include "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +/* Exponents up to 2^SIZE_LOG */ +#ifndef SIZE_LOG +#define SIZE_LOG 13 +#endif + +#ifndef COUNT +#define COUNT 30 +#endif + +#define MAX_N (1<<SIZE_LOG) + +int +main (int argc, char **argv) +{ + mp_limb_t a; + mp_ptr pp, scratch; + mp_limb_t max_b; + int count = COUNT; + int test; + gmp_randstate_ptr rands; + TMP_DECL; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + tests_start (); + TMP_MARK; + rands = RANDS; + + pp = TMP_ALLOC_LIMBS (MAX_N); + scratch = TMP_ALLOC_LIMBS (MAX_N); + max_b = numberof (mp_bases); + + ASSERT_ALWAYS (max_b > 62); + ASSERT_ALWAYS (max_b < GMP_NUMB_MAX); + + for (a = 2; a < max_b; ++a) + for (test = 0; test < count; ++test) + { + mp_size_t pn; + mp_limb_t exp; + mp_bitcnt_t res; + + exp = gmp_urandomm_ui (rands, MAX_N); + + pn = mpn_pow_1 (pp, &a, 1, exp, scratch); + + res = mpn_sizeinbase (pp, pn, a) - 1; + + if ((res < exp) || (res > exp + 1)) + { + printf ("ERROR in test %d, base = %d, exp = %d, res = %d\n", + test, (int) a, (int) exp, (int) res); + abort(); + } + + mpn_sub_1 (pp, pp, pn, CNST_LIMB(1)); + pn -= pp[pn-1] == 0; + + res = mpn_sizeinbase (pp, pn, a); + + if ((res < exp) || (res - 1 > exp)) + { + printf ("ERROR in -1 test %d, base = %d, exp = %d, res = %d\n", + test, (int) a, (int) exp, (int) res); + abort(); + } + } + + TMP_FREE; + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-sqrmod_bnm1.c b/gmp/tests/mpn/t-sqrmod_bnm1.c new file mode 100644 index 0000000000..47ccf81083 --- /dev/null +++ b/gmp/tests/mpn/t-sqrmod_bnm1.c @@ -0,0 +1,191 @@ +/* Test for sqrmod_bnm1 function. + + Contributed to the GNU project by Marco Bodrato. + +Copyright 2009 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +/* Sizes are up to 2^SIZE_LOG limbs */ +#ifndef SIZE_LOG +#define SIZE_LOG 12 +#endif + +#ifndef COUNT +#define COUNT 3000 +#endif + +#define MAX_N (1L << SIZE_LOG) +#define MIN_N 1 + +/* + Reference function for squaring modulo B^rn-1. + + The result is expected to be ZERO if and only if one of the operand + already is. Otherwise the class [0] Mod(B^rn-1) is represented by + B^rn-1. This should not be a problem if sqrmod_bnm1 is used to + combine results and obtain a natural number when one knows in + advance that the final value is less than (B^rn-1). +*/ + +static void +ref_sqrmod_bnm1 (mp_ptr rp, mp_size_t rn, mp_srcptr ap, mp_size_t an) +{ + mp_limb_t cy; + + ASSERT (0 < an && an <= rn); + + refmpn_mul (rp, ap, an, ap, an); + an *= 2; + if (an > rn) { + cy = mpn_add (rp, rp, rn, rp + rn, an - rn); + /* If cy == 1, then the value of rp is at most B^rn - 2, so there can + * be no overflow when adding in the carry. */ + MPN_INCR_U (rp, rn, cy); + } +} + +/* + Compare the result of the mpn_sqrmod_bnm1 function in the library + with the reference function above. +*/ + +int +main (int argc, char **argv) +{ + mp_ptr ap, refp, pp, scratch; + int count = COUNT; + int test; + gmp_randstate_ptr rands; + TMP_DECL; + TMP_MARK; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + tests_start (); + rands = RANDS; + + ASSERT_ALWAYS (mpn_sqrmod_bnm1_next_size (MAX_N) == MAX_N); + + ap = TMP_ALLOC_LIMBS (MAX_N); + refp = TMP_ALLOC_LIMBS (MAX_N * 4); + pp = 1+TMP_ALLOC_LIMBS (MAX_N + 2); + scratch + = 1+TMP_ALLOC_LIMBS (mpn_sqrmod_bnm1_itch (MAX_N, MAX_N) + 2); + + for (test = 0; test < count; test++) + { + unsigned size_min; + unsigned size_range; + mp_size_t an,rn,n; + mp_size_t itch; + mp_limb_t p_before, p_after, s_before, s_after; + + for (size_min = 1; (1L << size_min) < MIN_N; size_min++) + ; + + /* We generate an in the MIN_N <= n <= (1 << size_range). */ + size_range = size_min + + gmp_urandomm_ui (rands, SIZE_LOG + 1 - size_min); + + n = MIN_N + + gmp_urandomm_ui (rands, (1L << size_range) + 1 - MIN_N); + n = mpn_sqrmod_bnm1_next_size (n); + + if (n == 1) + an = 1; + else + an = ((n+1) >> 1) + gmp_urandomm_ui (rands, (n+1) >> 1); + + mpn_random2 (ap, an); + + /* Sometime trigger the borderline conditions + A = -1,0,+1 Mod(B^{n/2}+1). + This only makes sense if there is at least a split, i.e. n is even. */ + if ((test & 0x1f) == 1 && (n & 1) == 0) { + mp_size_t x; + MPN_COPY (ap, ap + (n >> 1), an - (n >> 1)); + MPN_ZERO (ap + an - (n >> 1) , n - an); + x = (n == an) ? 0 : gmp_urandomm_ui (rands, n - an); + ap[x] += gmp_urandomm_ui (rands, 3) - 1; + } + rn = MIN(n, 2*an); + mpn_random2 (pp-1, rn + 2); + p_before = pp[-1]; + p_after = pp[rn]; + + itch = mpn_sqrmod_bnm1_itch (n, an); + ASSERT_ALWAYS (itch <= mpn_sqrmod_bnm1_itch (MAX_N, MAX_N)); + mpn_random2 (scratch-1, itch+2); + s_before = scratch[-1]; + s_after = scratch[itch]; + + mpn_sqrmod_bnm1 ( pp, n, ap, an, scratch); + ref_sqrmod_bnm1 (refp, n, ap, an); + if (pp[-1] != p_before || pp[rn] != p_after + || scratch[-1] != s_before || scratch[itch] != s_after + || mpn_cmp (refp, pp, rn) != 0) + { + printf ("ERROR in test %d, an = %d, n = %d\n", + test, (int) an, (int) n); + if (pp[-1] != p_before) + { + printf ("before pp:"); mpn_dump (pp -1, 1); + printf ("keep: "); mpn_dump (&p_before, 1); + } + if (pp[rn] != p_after) + { + printf ("after pp:"); mpn_dump (pp + rn, 1); + printf ("keep: "); mpn_dump (&p_after, 1); + } + if (scratch[-1] != s_before) + { + printf ("before scratch:"); mpn_dump (scratch-1, 1); + printf ("keep: "); mpn_dump (&s_before, 1); + } + if (scratch[itch] != s_after) + { + printf ("after scratch:"); mpn_dump (scratch + itch, 1); + printf ("keep: "); mpn_dump (&s_after, 1); + } + mpn_dump (ap, an); + mpn_dump (pp, rn); + mpn_dump (refp, rn); + + abort(); + } + } + TMP_FREE; + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/t-toom2-sqr.c b/gmp/tests/mpn/t-toom2-sqr.c new file mode 100644 index 0000000000..a5cdcb5778 --- /dev/null +++ b/gmp/tests/mpn/t-toom2-sqr.c @@ -0,0 +1,6 @@ +#define mpn_toomN_sqr mpn_toom2_sqr +#define mpn_toomN_sqr_itch mpn_toom2_sqr_itch +#define MIN_AN MPN_TOOM2_SQR_MINSIZE +#define MAX_AN SQR_TOOM3_THRESHOLD + +#include "toom-sqr-shared.h" diff --git a/gmp/tests/mpn/t-toom22.c b/gmp/tests/mpn/t-toom22.c new file mode 100644 index 0000000000..939a88e9d8 --- /dev/null +++ b/gmp/tests/mpn/t-toom22.c @@ -0,0 +1,10 @@ +#define mpn_toomMN_mul mpn_toom22_mul +#define mpn_toomMN_mul_itch mpn_toom22_mul_itch +#define MIN_AN 2 + +#define MIN_BN(an) \ + ((an) >= 2*MUL_TOOM22_THRESHOLD \ + ? (an) + 2 - MUL_TOOM22_THRESHOLD \ + : ((an)+1)/2 + 1) + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom3-sqr.c b/gmp/tests/mpn/t-toom3-sqr.c new file mode 100644 index 0000000000..ccc3b99504 --- /dev/null +++ b/gmp/tests/mpn/t-toom3-sqr.c @@ -0,0 +1,6 @@ +#define mpn_toomN_sqr mpn_toom3_sqr +#define mpn_toomN_sqr_itch mpn_toom3_sqr_itch +#define MIN_AN MAX(SQR_TOOM3_THRESHOLD,MPN_TOOM3_SQR_MINSIZE) +#define MAX_AN SQR_TOOM4_THRESHOLD + +#include "toom-sqr-shared.h" diff --git a/gmp/tests/mpn/t-toom32.c b/gmp/tests/mpn/t-toom32.c new file mode 100644 index 0000000000..e42745da96 --- /dev/null +++ b/gmp/tests/mpn/t-toom32.c @@ -0,0 +1,8 @@ +#define mpn_toomMN_mul mpn_toom32_mul +#define mpn_toomMN_mul_itch mpn_toom32_mul_itch + +#define MIN_AN 6 +#define MIN_BN(an) (((an) + 8) / (size_t) 3) +#define MAX_BN(an) ((an) - 2) + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom33.c b/gmp/tests/mpn/t-toom33.c new file mode 100644 index 0000000000..7de82b20c9 --- /dev/null +++ b/gmp/tests/mpn/t-toom33.c @@ -0,0 +1,11 @@ +#define mpn_toomMN_mul mpn_toom33_mul +#define mpn_toomMN_mul_itch mpn_toom33_mul_itch + +/* Smaller sizes not supported; may lead to recursive calls to + toom22_mul with invalid input size. */ +#define MIN_AN MUL_TOOM33_THRESHOLD +#define MIN_BN(an) (1 + 2*(((an)+2)/(size_t) 3)) + +#define COUNT 1000 + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom4-sqr.c b/gmp/tests/mpn/t-toom4-sqr.c new file mode 100644 index 0000000000..ca14ab1482 --- /dev/null +++ b/gmp/tests/mpn/t-toom4-sqr.c @@ -0,0 +1,6 @@ +#define mpn_toomN_sqr mpn_toom4_sqr +#define mpn_toomN_sqr_itch mpn_toom4_sqr_itch +#define MIN_AN MAX(SQR_TOOM3_THRESHOLD,MAX(SQR_TOOM4_THRESHOLD,MPN_TOOM4_SQR_MINSIZE)) +#define MAX_AN SQR_TOOM6_THRESHOLD + +#include "toom-sqr-shared.h" diff --git a/gmp/tests/mpn/t-toom42.c b/gmp/tests/mpn/t-toom42.c new file mode 100644 index 0000000000..09a4a0c115 --- /dev/null +++ b/gmp/tests/mpn/t-toom42.c @@ -0,0 +1,8 @@ +#define mpn_toomMN_mul mpn_toom42_mul +#define mpn_toomMN_mul_itch mpn_toom42_mul_itch + +#define MIN_AN 10 +#define MIN_BN(an) (((an) + 7) >> 2) +#define MAX_BN(an) ((2*(an)-5) / (size_t) 3) + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom43.c b/gmp/tests/mpn/t-toom43.c new file mode 100644 index 0000000000..224a45bc38 --- /dev/null +++ b/gmp/tests/mpn/t-toom43.c @@ -0,0 +1,8 @@ +#define mpn_toomMN_mul mpn_toom43_mul +#define mpn_toomMN_mul_itch mpn_toom43_mul_itch + +#define MIN_AN 25 +#define MIN_BN(an) (1 + 2*(((an)+3) >> 2)) +#define MAX_BN(an) ((an)-3) + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom44.c b/gmp/tests/mpn/t-toom44.c new file mode 100644 index 0000000000..6c627e3428 --- /dev/null +++ b/gmp/tests/mpn/t-toom44.c @@ -0,0 +1,11 @@ +#define mpn_toomMN_mul mpn_toom44_mul +#define mpn_toomMN_mul_itch mpn_toom44_mul_itch + +/* Smaller sizes not supported; may lead to recursive calls to + toom22_mul or toom33_mul with invalid input size. */ +#define MIN_AN MUL_TOOM44_THRESHOLD +#define MIN_BN(an) (1 + 3*(((an)+3)>>2)) + +#define COUNT 1000 + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom52.c b/gmp/tests/mpn/t-toom52.c new file mode 100644 index 0000000000..d3fb134f2e --- /dev/null +++ b/gmp/tests/mpn/t-toom52.c @@ -0,0 +1,8 @@ +#define mpn_toomMN_mul mpn_toom52_mul +#define mpn_toomMN_mul_itch mpn_toom52_mul_itch + +#define MIN_AN 32 +#define MIN_BN(an) (((an) + 9) / (size_t) 5) +#define MAX_BN(an) (((an) - 3) >> 1) + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom53.c b/gmp/tests/mpn/t-toom53.c new file mode 100644 index 0000000000..ddbf177aec --- /dev/null +++ b/gmp/tests/mpn/t-toom53.c @@ -0,0 +1,8 @@ +#define mpn_toomMN_mul mpn_toom53_mul +#define mpn_toomMN_mul_itch mpn_toom53_mul_itch + +#define MIN_AN 17 +#define MIN_BN(an) (1 + 2*(((an) + 4) / (size_t) 5)) +#define MAX_BN(an) ((3*(an) - 11) >> 2) + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom54.c b/gmp/tests/mpn/t-toom54.c new file mode 100644 index 0000000000..52a2bee7b3 --- /dev/null +++ b/gmp/tests/mpn/t-toom54.c @@ -0,0 +1,8 @@ +#define mpn_toomMN_mul mpn_toom54_mul +#define mpn_toomMN_mul_itch mpn_toom54_mul_itch + +#define MIN_AN 31 +#define MIN_BN(an) ((3*(an) + 32) / (size_t) 5) /* 3/5 */ +#define MAX_BN(an) ((an) - 6) /* 1/1 */ + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom6-sqr.c b/gmp/tests/mpn/t-toom6-sqr.c new file mode 100644 index 0000000000..67d7a63d32 --- /dev/null +++ b/gmp/tests/mpn/t-toom6-sqr.c @@ -0,0 +1,8 @@ +#define mpn_toomN_sqr mpn_toom6_sqr +#define mpn_toomN_sqr_itch mpn_toom6_sqr_itch +#define MIN_AN MAX(SQR_TOOM3_THRESHOLD,MAX(SQR_TOOM4_THRESHOLD,MAX(SQR_TOOM6_THRESHOLD,MPN_TOOM6_SQR_MINSIZE))) +#define MAX_AN SQR_TOOM8_THRESHOLD + +#define COUNT 250 + +#include "toom-sqr-shared.h" diff --git a/gmp/tests/mpn/t-toom62.c b/gmp/tests/mpn/t-toom62.c new file mode 100644 index 0000000000..1cb2aab26c --- /dev/null +++ b/gmp/tests/mpn/t-toom62.c @@ -0,0 +1,8 @@ +#define mpn_toomMN_mul mpn_toom62_mul +#define mpn_toomMN_mul_itch mpn_toom62_mul_itch + +#define MIN_AN 31 +#define MIN_BN(an) (((an) + 11) / (size_t) 6) +#define MAX_BN(an) ((2*(an) - 7) / (size_t) 5) + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom63.c b/gmp/tests/mpn/t-toom63.c new file mode 100644 index 0000000000..d79165dcbe --- /dev/null +++ b/gmp/tests/mpn/t-toom63.c @@ -0,0 +1,8 @@ +#define mpn_toomMN_mul mpn_toom63_mul +#define mpn_toomMN_mul_itch mpn_toom63_mul_itch + +#define MIN_AN 49 +#define MIN_BN(an) (2*(((an) + 23) / (size_t) 6)) /* 2/6 */ +#define MAX_BN(an) ((3*(an) - 23) / (size_t) 5) /* 3/5 */ + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom6h.c b/gmp/tests/mpn/t-toom6h.c new file mode 100644 index 0000000000..5cca9fc90e --- /dev/null +++ b/gmp/tests/mpn/t-toom6h.c @@ -0,0 +1,13 @@ +#define mpn_toomMN_mul mpn_toom6h_mul +#define mpn_toomMN_mul_itch mpn_toom6h_mul_itch + +#define SIZE_LOG 11 + +/* Smaller sizes not supported; may lead to recursive calls to + toom22_mul, toom33_mul, or toom44_mul with invalid input size. */ +#define MIN_AN MUL_TOOM6H_MIN +#define MIN_BN(an) (MAX ((an*3)>>3, 46)) + +#define COUNT 1000 + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/t-toom8-sqr.c b/gmp/tests/mpn/t-toom8-sqr.c new file mode 100644 index 0000000000..0eee605928 --- /dev/null +++ b/gmp/tests/mpn/t-toom8-sqr.c @@ -0,0 +1,8 @@ +#define mpn_toomN_sqr mpn_toom8_sqr +#define mpn_toomN_sqr_itch mpn_toom8_sqr_itch +#define MIN_AN MAX(SQR_TOOM3_THRESHOLD,MAX(SQR_TOOM4_THRESHOLD,MAX(SQR_TOOM6_THRESHOLD,MAX(SQR_TOOM8_THRESHOLD,MPN_TOOM8_SQR_MINSIZE)))) +#define MAX_AN SQR_FFT_THRESHOLD + +#define COUNT 250 + +#include "toom-sqr-shared.h" diff --git a/gmp/tests/mpn/t-toom8h.c b/gmp/tests/mpn/t-toom8h.c new file mode 100644 index 0000000000..aeeabb274b --- /dev/null +++ b/gmp/tests/mpn/t-toom8h.c @@ -0,0 +1,18 @@ +#define mpn_toomMN_mul mpn_toom8h_mul +#define mpn_toomMN_mul_itch mpn_toom8h_mul_itch + +#define SIZE_LOG 11 + +/* Smaller sizes not supported; may lead to recursive calls to + toom{22,33,44,6h}_mul with invalid input size. */ +#define MIN_AN MUL_TOOM8H_MIN + +#define MIN_BN(an) \ +(MAX(GMP_NUMB_BITS <= 10*3 ? (an*6)/10 : \ + GMP_NUMB_BITS <= 11*3 ? (an*5)/11 : \ + GMP_NUMB_BITS <= 12*3 ? (an*4)/12 : \ + (an*4)/13, 86) ) + +#define COUNT 1000 + +#include "toom-shared.h" diff --git a/gmp/tests/mpn/toom-shared.h b/gmp/tests/mpn/toom-shared.h new file mode 100644 index 0000000000..7479e7efd9 --- /dev/null +++ b/gmp/tests/mpn/toom-shared.h @@ -0,0 +1,158 @@ +/* Test for various Toom functions. + +Copyright 2009 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +/* Main file is expected to define mpn_toomMN_mul, + * mpn_toomMN_mul_itch, MIN_AN, MIN_BN(an), MAX_BN(an) and then + * include this file. */ + +/* Sizes are up to 2^SIZE_LOG limbs */ +#ifndef SIZE_LOG +#define SIZE_LOG 10 +#endif + +#ifndef COUNT +#define COUNT 2000 +#endif + +#define MAX_AN (1L << SIZE_LOG) + +#ifndef MAX_BN +#define MAX_BN(an) (an) +#endif + +/* For general toomMN_mul, we need + * + * MIN_BN(an) = N + floor(((N-1)*an + M - N)/M) + * + * MAX_BN(an) = floor(N*(an-1)/(M-1)) - N + 1 + */ + +int +main (int argc, char **argv) +{ + mp_ptr ap, bp, refp, pp, scratch; + int count = COUNT; + int test; + gmp_randstate_ptr rands; + TMP_DECL; + TMP_MARK; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + tests_start (); + rands = RANDS; + + ap = TMP_ALLOC_LIMBS (MAX_AN); + bp = TMP_ALLOC_LIMBS (MAX_BN(MAX_AN)); + refp = TMP_ALLOC_LIMBS (MAX_AN + MAX_BN(MAX_AN)); + pp = 1+TMP_ALLOC_LIMBS (MAX_AN + MAX_BN(MAX_AN)+2); + scratch + = 1+TMP_ALLOC_LIMBS (mpn_toomMN_mul_itch (MAX_AN, MAX_BN(MAX_AN)) + + 2); + + for (test = 0; test < count; test++) + { + unsigned size_min; + unsigned size_range; + mp_size_t an, bn; + mp_size_t itch; + mp_limb_t p_before, p_after, s_before, s_after; + + for (size_min = 1; (1L << size_min) < MIN_AN; size_min++) + ; + + /* We generate an in the MIN_AN <= an <= (1 << size_range). */ + size_range = size_min + + gmp_urandomm_ui (rands, SIZE_LOG + 1 - size_min); + + an = MIN_AN + + gmp_urandomm_ui (rands, (1L << size_range) + 1 - MIN_AN); + bn = MIN_BN(an) + + gmp_urandomm_ui (rands, MAX_BN(an) + 1 - MIN_BN(an)); + + mpn_random2 (ap, an); + mpn_random2 (bp, bn); + mpn_random2 (pp-1, an + bn + 2); + p_before = pp[-1]; + p_after = pp[an + bn]; + + itch = mpn_toomMN_mul_itch (an, bn); + ASSERT_ALWAYS (itch <= mpn_toomMN_mul_itch (MAX_AN, MAX_BN(MAX_AN))); + mpn_random2 (scratch-1, itch+2); + s_before = scratch[-1]; + s_after = scratch[itch]; + + mpn_toomMN_mul (pp, ap, an, bp, bn, scratch); + refmpn_mul (refp, ap, an, bp, bn); + if (pp[-1] != p_before || pp[an + bn] != p_after + || scratch[-1] != s_before || scratch[itch] != s_after + || mpn_cmp (refp, pp, an + bn) != 0) + { + printf ("ERROR in test %d, an = %d, bn = %d\n", + test, (int) an, (int) bn); + if (pp[-1] != p_before) + { + printf ("before pp:"); mpn_dump (pp -1, 1); + printf ("keep: "); mpn_dump (&p_before, 1); + } + if (pp[an + bn] != p_after) + { + printf ("after pp:"); mpn_dump (pp + an + bn, 1); + printf ("keep: "); mpn_dump (&p_after, 1); + } + if (scratch[-1] != s_before) + { + printf ("before scratch:"); mpn_dump (scratch-1, 1); + printf ("keep: "); mpn_dump (&s_before, 1); + } + if (scratch[itch] != s_after) + { + printf ("after scratch:"); mpn_dump (scratch + itch, 1); + printf ("keep: "); mpn_dump (&s_after, 1); + } + mpn_dump (ap, an); + mpn_dump (bp, bn); + mpn_dump (pp, an + bn); + mpn_dump (refp, an + bn); + + abort(); + } + } + TMP_FREE; + + tests_end (); + return 0; +} diff --git a/gmp/tests/mpn/toom-sqr-shared.h b/gmp/tests/mpn/toom-sqr-shared.h new file mode 100644 index 0000000000..944cfab000 --- /dev/null +++ b/gmp/tests/mpn/toom-sqr-shared.h @@ -0,0 +1,129 @@ +/* Test for various Toom squaring functions. + +Copyright 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 "gmp.h" +#include "gmp-impl.h" +#include "tests.h" + +/* Main file is expected to define mpn_toomN_mul, mpn_toomN_sqr_itch, + * MIN_AN, MAX_AN and then include this file. */ + +#ifndef COUNT +#define COUNT 2000 +#endif + +int +main (int argc, char **argv) +{ + mp_ptr ap, refp, pp, scratch; + int count = COUNT; + int test; + gmp_randstate_ptr rands; + TMP_DECL; + TMP_MARK; + + if (argc > 1) + { + char *end; + count = strtol (argv[1], &end, 0); + if (*end || count <= 0) + { + fprintf (stderr, "Invalid test count: %s.\n", argv[1]); + return 1; + } + } + + tests_start (); + + if (MAX_AN > MIN_AN) { + rands = RANDS; + + ap = TMP_ALLOC_LIMBS (MAX_AN); + refp = TMP_ALLOC_LIMBS (MAX_AN * 2); + pp = 1 + TMP_ALLOC_LIMBS (MAX_AN * 2 + 2); + scratch + = 1+TMP_ALLOC_LIMBS (mpn_toomN_sqr_itch (MAX_AN) + 2); + + for (test = 0; test < count; test++) + { + unsigned size_min; + unsigned size_range; + mp_size_t an; + mp_size_t itch; + mp_limb_t p_before, p_after, s_before, s_after; + + an = MIN_AN + + gmp_urandomm_ui (rands, MAX_AN - MIN_AN); + + mpn_random2 (ap, an); + mpn_random2 (pp-1, an * 2 + 2); + p_before = pp[-1]; + p_after = pp[an * 2]; + + itch = mpn_toomN_sqr_itch (an); + ASSERT_ALWAYS (itch <= mpn_toomN_sqr_itch (MAX_AN)); + mpn_random2 (scratch-1, itch+2); + s_before = scratch[-1]; + s_after = scratch[itch]; + + mpn_toomN_sqr (pp, ap, an, scratch); + refmpn_mul (refp, ap, an, ap, an); + if (pp[-1] != p_before || pp[an * 2] != p_after + || scratch[-1] != s_before || scratch[itch] != s_after + || mpn_cmp (refp, pp, an * 2) != 0) + { + printf ("ERROR in test %d, an = %d\n", + test, (int) an); + if (pp[-1] != p_before) + { + printf ("before pp:"); mpn_dump (pp -1, 1); + printf ("keep: "); mpn_dump (&p_before, 1); + } + if (pp[an * 2] != p_after) + { + printf ("after pp:"); mpn_dump (pp + an * 2, 1); + printf ("keep: "); mpn_dump (&p_after, 1); + } + if (scratch[-1] != s_before) + { + printf ("before scratch:"); mpn_dump (scratch-1, 1); + printf ("keep: "); mpn_dump (&s_before, 1); + } + if (scratch[itch] != s_after) + { + printf ("after scratch:"); mpn_dump (scratch + itch, 1); + printf ("keep: "); mpn_dump (&s_after, 1); + } + mpn_dump (ap, an); + mpn_dump (pp, an * 2); + mpn_dump (refp, an * 2); + + abort(); + } + } + TMP_FREE; + } + + tests_end (); + return 0; +} |