[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Sun Feb 26 17:44:15 CET 2012
details: /var/hg/gmp/rev/93444f2db27c
changeset: 14682:93444f2db27c
user: Niels M?ller <nisse at lysator.liu.se>
date: Sun Feb 26 17:18:00 2012 +0100
description:
Added mini-gmp. Use it for bootstrap. Deleted dumbmp.c.
details: /var/hg/gmp/rev/f97048b1f08c
changeset: 14683:f97048b1f08c
user: Niels M?ller <nisse at lysator.liu.se>
date: Sun Feb 26 17:43:51 2012 +0100
description:
Trivial merge.
diffstat:
.hgignore | 16 +
ChangeLog | 30 +
Makefile.am | 20 +-
bootstrap.c | 135 +
dumbmp.c | 990 ----------
gen-bases.c | 2 +-
gen-fac_ui.c | 2 +-
gen-fib.c | 6 +-
gen-psqr.c | 23 +-
gen-trialdivtab.c | 2 +-
gmp-h.in | 3 +
mini-gmp/README | 46 +
mini-gmp/mini-gmp.c | 4041 ++++++++++++++++++++++++++++++++++++++++++
mini-gmp/mini-gmp.h | 238 ++
mini-gmp/tests/Makefile | 40 +
mini-gmp/tests/hex-random.c | 386 ++++
mini-gmp/tests/hex-random.h | 43 +
mini-gmp/tests/mini-random.c | 117 +
mini-gmp/tests/mini-random.h | 32 +
mini-gmp/tests/run-tests | 108 +
mini-gmp/tests/t-add.c | 50 +
mini-gmp/tests/t-bitops.c | 96 +
mini-gmp/tests/t-div.c | 94 +
mini-gmp/tests/t-div_2exp.c | 75 +
mini-gmp/tests/t-double.c | 108 +
mini-gmp/tests/t-gcd.c | 164 +
mini-gmp/tests/t-invert.c | 91 +
mini-gmp/tests/t-lcm.c | 52 +
mini-gmp/tests/t-logops.c | 75 +
mini-gmp/tests/t-mul.c | 51 +
mini-gmp/tests/t-powm.c | 54 +
mini-gmp/tests/t-scan.c | 57 +
mini-gmp/tests/t-sqrt.c | 75 +
mini-gmp/tests/t-str.c | 92 +
mini-gmp/tests/t-sub.c | 50 +
mpz/2fac_ui.c | 98 +
mpz/fac_ui.c | 2 +-
tests/mpz/t-fac_ui.c | 25 +-
38 files changed, 6568 insertions(+), 1021 deletions(-)
diffs (truncated from 7943 to 300 lines):
diff -r b3d04bbfafa7 -r f97048b1f08c .hgignore
--- a/.hgignore Fri Feb 24 17:45:54 2012 +0100
+++ b/.hgignore Sun Feb 26 17:43:51 2012 +0100
@@ -56,6 +56,22 @@
^tests/mpz/logic$
^tests/mpz/reuse$
+^mini-gmp/tests/t-add$
+^mini-gmp/tests/t-sub$
+^mini-gmp/tests/t-mul$
+^mini-gmp/tests/t-invert$
+^mini-gmp/tests/t-div$
+^mini-gmp/tests/t-div_2exp$
+^mini-gmp/tests/t-double$
+^mini-gmp/tests/t-gcd$
+^mini-gmp/tests/t-lcm$
+^mini-gmp/tests/t-sqrt
+^mini-gmp/tests/t-powm$
+^mini-gmp/tests/t-logops$
+^mini-gmp/tests/t-bitops$
+^mini-gmp/tests/t-scan$
+^mini-gmp/tests/t-str$
+
^\.libs
.*\.a$
diff -r b3d04bbfafa7 -r f97048b1f08c ChangeLog
--- a/ChangeLog Fri Feb 24 17:45:54 2012 +0100
+++ b/ChangeLog Sun Feb 26 17:43:51 2012 +0100
@@ -1,3 +1,33 @@
+2012-02-26 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpz/2fac_ui.c: New file: implements n!!.
+ * Makefile.am (MPZ_OBJECTS): Add mpz/2fac_ui.
+ * gmp-h.in: Declare mpz_2fac_ui.
+ * tests/mpz/t-fac.c: Test mpz_2fac_ui.
+
+2012-02-26 Niels Möller <nisse at lysator.liu.se>
+
+ * mini-gmp: New subdirectory. For use by GMP bootstrap, and as a
+ fallback for applications needing bignums but not high
+ performance.
+
+ * bootstrap.c: New file, replacing dumbmp.c. Uses mini-gmp for the
+ standard GMP functions, and then defines the few functions
+ particular for the bootstrap.
+ * dumbmp.c: Deleted file. A few functions moved to bootstrap.c.
+
+ * gen-bases.c: Include bootstrap.c, not dumbmp.c.
+ * gen-fac_ui.c: Likewise.
+ * gen-trialdivtab.c: Likewise.
+ * gen-fib.c: Include bootstrap.c, not dumbmp.c. Use assert rather
+ than ASSERT. Deleted casts of xmalloc return value.
+ * gen-psqr.c: Likewise.
+ (COLLAPSE_ELEMENT): Use memmove rather than mem_copyi.
+
+ * Makefile.am: Replaced all uses of dumbmp.c by bootstrap.c.
+ (EXTRA_DIST, dist-hook): Arrange for distribution of the mini-gmp
+ files.
+
2012-02-24 Marco Bodrato <bodrato at mail.dm.unipi.it>
* mpz/invert.c: Use ABSIZ, MPZ_EQUAL_1_P.
diff -r b3d04bbfafa7 -r f97048b1f08c Makefile.am
--- a/Makefile.am Fri Feb 24 17:45:54 2012 +0100
+++ b/Makefile.am Sun Feb 26 17:43:51 2012 +0100
@@ -157,7 +157,8 @@
mpz/cong$U.lo mpz/cong_2exp$U.lo mpz/cong_ui$U.lo \
mpz/divexact$U.lo mpz/divegcd$U.lo mpz/dive_ui$U.lo \
mpz/divis$U.lo mpz/divis_ui$U.lo mpz/divis_2exp$U.lo mpz/dump$U.lo \
- mpz/export$U.lo mpz/fac_ui$U.lo mpz/oddfac_1$U.lo mpz/prodlimbs$U.lo \
+ mpz/export$U.lo \
+ mpz/2fac_ui$U.lo mpz/fac_ui$U.lo mpz/oddfac_1$U.lo mpz/prodlimbs$U.lo \
mpz/fdiv_q_ui$U.lo mpz/fdiv_qr$U.lo mpz/fdiv_qr_ui$U.lo \
mpz/fdiv_r$U.lo mpz/fdiv_r_ui$U.lo mpz/fdiv_q$U.lo \
mpz/fdiv_ui$U.lo mpz/fib_ui$U.lo mpz/fib2_ui$U.lo mpz/fits_sint$U.lo \
@@ -309,13 +310,13 @@
# the .h files are not properly expressed for the various objects that use
# them.
-EXTRA_DIST += dumbmp.c
+EXTRA_DIST += bootstrap.c
fac_ui.h: gen-fac_ui$(EXEEXT_FOR_BUILD)
./gen-fac_ui $(GMP_LIMB_BITS) $(GMP_NAIL_BITS) >fac_ui.h || (rm -f fac_ui.h; exit 1)
BUILT_SOURCES += fac_ui.h
-gen-fac_ui$(EXEEXT_FOR_BUILD): gen-fac_ui$(U_FOR_BUILD).c dumbmp.c
+gen-fac_ui$(EXEEXT_FOR_BUILD): gen-fac_ui$(U_FOR_BUILD).c bootstrap.c
$(CC_FOR_BUILD) `test -f 'gen-fac_ui$(U_FOR_BUILD).c' || echo '$(srcdir)/'`gen-fac_ui$(U_FOR_BUILD).c -o gen-fac_ui$(EXEEXT_FOR_BUILD)
DISTCLEANFILES += gen-fac_ui$(EXEEXT_FOR_BUILD)
EXTRA_DIST += gen-fac_ui.c
@@ -329,7 +330,7 @@
./gen-fib table $(GMP_LIMB_BITS) $(GMP_NAIL_BITS) >mpn/fib_table.c || (rm -f mpn/fib_table.c; exit 1)
BUILT_SOURCES += mpn/fib_table.c
-gen-fib$(EXEEXT_FOR_BUILD): gen-fib$(U_FOR_BUILD).c dumbmp.c
+gen-fib$(EXEEXT_FOR_BUILD): gen-fib$(U_FOR_BUILD).c bootstrap.c
$(CC_FOR_BUILD) `test -f 'gen-fib$(U_FOR_BUILD).c' || echo '$(srcdir)/'`gen-fib$(U_FOR_BUILD).c -o gen-fib$(EXEEXT_FOR_BUILD)
DISTCLEANFILES += gen-fib$(EXEEXT_FOR_BUILD)
EXTRA_DIST += gen-fib.c
@@ -343,7 +344,7 @@
./gen-bases table $(GMP_LIMB_BITS) $(GMP_NAIL_BITS) >mpn/mp_bases.c || (rm -f mpn/mp_bases.c; exit 1)
BUILT_SOURCES += mpn/mp_bases.c
-gen-bases$(EXEEXT_FOR_BUILD): gen-bases$(U_FOR_BUILD).c dumbmp.c
+gen-bases$(EXEEXT_FOR_BUILD): gen-bases$(U_FOR_BUILD).c bootstrap.c
$(CC_FOR_BUILD) `test -f 'gen-bases$(U_FOR_BUILD).c' || echo '$(srcdir)/'`gen-bases$(U_FOR_BUILD).c -o gen-bases$(EXEEXT_FOR_BUILD) $(LIBM_FOR_BUILD)
DISTCLEANFILES += gen-bases$(EXEEXT_FOR_BUILD)
EXTRA_DIST += gen-bases.c
@@ -353,7 +354,7 @@
./gen-trialdivtab $(GMP_LIMB_BITS) 8000 >trialdivtab.h || (rm -f trialdivtab.h; exit 1)
BUILT_SOURCES += trialdivtab.h
-gen-trialdivtab$(EXEEXT_FOR_BUILD): gen-trialdivtab$(U_FOR_BUILD).c dumbmp.c
+gen-trialdivtab$(EXEEXT_FOR_BUILD): gen-trialdivtab$(U_FOR_BUILD).c bootstrap.c
$(CC_FOR_BUILD) `test -f 'gen-trialdivtab$(U_FOR_BUILD).c' || echo '$(srcdir)/'`gen-trialdivtab$(U_FOR_BUILD).c -o gen-trialdivtab$(EXEEXT_FOR_BUILD) $(LIBM_FOR_BUILD)
DISTCLEANFILES += gen-trialdivtab$(EXEEXT_FOR_BUILD)
EXTRA_DIST += gen-trialdivtab.c
@@ -373,12 +374,14 @@
./gen-psqr $(GMP_LIMB_BITS) $(GMP_NAIL_BITS) >mpn/perfsqr.h || (rm -f mpn/perfsqr.h; exit 1)
BUILT_SOURCES += mpn/perfsqr.h
-gen-psqr$(EXEEXT_FOR_BUILD): gen-psqr$(U_FOR_BUILD).c dumbmp.c
+gen-psqr$(EXEEXT_FOR_BUILD): gen-psqr$(U_FOR_BUILD).c bootstrap.c
$(CC_FOR_BUILD) `test -f 'gen-psqr$(U_FOR_BUILD).c' || echo '$(srcdir)/'`gen-psqr$(U_FOR_BUILD).c -o gen-psqr$(EXEEXT_FOR_BUILD) $(LIBM_FOR_BUILD)
DISTCLEANFILES += gen-psqr$(EXEEXT_FOR_BUILD)
EXTRA_DIST += gen-psqr.c
-
+# Distribute mini-gmp. Test sources copied by dist-hook.
+EXTRA_DIST += mini-gmp/README mini-gmp/mini-gmp.c mini-gmp/mini-gmp.h \
+ mini-gmp/tests/Makefile mini-gmp/tests/run-tests
# Avoid: CVS - cvs directories
# *~ - emacs backups
@@ -390,6 +393,7 @@
dist-hook:
-find $(distdir) \( -name CVS -type d \) -o -name "*~" -o -name ".#*" \
| xargs rm -rf
+ cp "$(srcdir)"/mini-gmp/tests/*.[ch] "$(distdir)/mini-gmp/tests"
# grep -F $(VERSION) $(srcdir)/Makefile.am \
# | grep -q "^# *$(VERSION) *$(LIBGMP_LT_CURRENT):$(LIBGMP_LT_REVISION):$(LIBGMP_LT_AGE) *$(LIBGMPXX_LT_CURRENT):$(LIBGMPXX_LT_REVISION):$(LIBGMPXX_LT_AGE) *$(LIBMP_LT_CURRENT):$(LIBMP_LT_REVISION):$(LIBMP_LT_AGE)"
# test -z "`sed -n 's/^# *[0-9]*\.[0-9]*\.[0-9]* *\([0-9]*:[0-9]*:[0-9]*\) *\([0-9]*:[0-9]*:[0-9]*\) *\([0-9]*:[0-9]*:[0-9]*\).*/A\1\nB\2\nC\3/p' $(srcdir)/Makefile.am | grep -v 'A6:3:3\|B3:5:0\|C4:7:1' | sort | uniq -d`"
diff -r b3d04bbfafa7 -r f97048b1f08c bootstrap.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/bootstrap.c Sun Feb 26 17:43:51 2012 +0100
@@ -0,0 +1,135 @@
+/* Functions needed for bootstrapping the gmp build, based on mini-gmp.
+
+Copyright 2001, 2002, 2004, 2011, 2012 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 3 of the License, or (at your
+option) any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+License for more details.
+
+You should have received a copy of the GNU Lesser General Public License
+along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
+
+
+#include "mini-gmp/mini-gmp.c"
+
+#define MIN(l,o) ((l) < (o) ? (l) : (o))
+#define PTR(x) ((x)->_mp_d)
+#define SIZ(x) ((x)->_mp_size)
+
+#define xmalloc gmp_default_alloc
+
+int
+isprime (unsigned long int t)
+{
+ unsigned long int q, r, d;
+
+ if (t < 32)
+ return (0xa08a28acUL >> t) & 1;
+ if ((t & 1) == 0)
+ return 0;
+
+ if (t % 3 == 0)
+ return 0;
+ if (t % 5 == 0)
+ return 0;
+ if (t % 7 == 0)
+ return 0;
+
+ for (d = 11;;)
+ {
+ q = t / d;
+ r = t - q * d;
+ if (q < d)
+ return 1;
+ if (r == 0)
+ break;
+ d += 2;
+ q = t / d;
+ r = t - q * d;
+ if (q < d)
+ return 1;
+ if (r == 0)
+ break;
+ d += 4;
+ }
+ return 0;
+}
+
+int
+log2_ceil (int n)
+{
+ int e;
+ assert (n >= 1);
+ for (e = 0; ; e++)
+ if ((1 << e) >= n)
+ break;
+ return e;
+}
+
+/* Set inv to the inverse of d, in the style of invert_limb, ie. for
+ udiv_qrnnd_preinv. */
+void
+mpz_preinv_invert (mpz_t inv, mpz_t d, int numb_bits)
+{
+ mpz_t t;
+ int norm;
+ assert (SIZ(d) > 0);
+
+ norm = numb_bits - mpz_sizeinbase (d, 2);
+ assert (norm >= 0);
+ mpz_init_set_ui (t, 1L);
+ mpz_mul_2exp (t, t, 2*numb_bits - norm);
+ mpz_tdiv_q (inv, t, d);
+ mpz_set_ui (t, 1L);
+ mpz_mul_2exp (t, t, numb_bits);
+ mpz_sub (inv, inv, t);
+
+ mpz_clear (t);
+}
+
+/* Calculate r satisfying r*d == 1 mod 2^n. */
+void
+mpz_invert_2exp (mpz_t r, mpz_t a, unsigned long n)
+{
+ unsigned long i;
+ mpz_t inv, prod;
+
+ assert (mpz_odd_p (a));
+
+ mpz_init_set_ui (inv, 1L);
+ mpz_init (prod);
+
+ for (i = 1; i < n; i++)
+ {
+ mpz_mul (prod, inv, a);
+ if (mpz_tstbit (prod, i) != 0)
+ mpz_setbit (inv, i);
+ }
+
+ mpz_mul (prod, inv, a);
+ mpz_tdiv_r_2exp (prod, prod, n);
+ assert (mpz_cmp_ui (prod, 1L) == 0);
+
+ mpz_set (r, inv);
+
+ mpz_clear (inv);
+ mpz_clear (prod);
+}
+
+/* Calculate inv satisfying r*a == 1 mod 2^n. */
+void
+mpz_invert_ui_2exp (mpz_t r, unsigned long a, unsigned long n)
+{
+ mpz_t az;
+ mpz_init_set_ui (az, a);
+ mpz_invert_2exp (r, az, n);
+ mpz_clear (az);
+}
diff -r b3d04bbfafa7 -r f97048b1f08c dumbmp.c
--- a/dumbmp.c Fri Feb 24 17:45:54 2012 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,990 +0,0 @@
-/* dumbmp mini GMP compatible library.
-
-Copyright 2001, 2002, 2004, 2011 Free Software Foundation, Inc.
-
-This file is part of the GNU MP Library.
-
-The GNU MP Library is free software; you can redistribute it and/or modify
-it under the terms of the GNU Lesser General Public License as published by
-the Free Software Foundation; either version 3 of the License, or (at your
-option) any later version.
-
-The GNU MP Library is distributed in the hope that it will be useful, but
-WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
More information about the gmp-commit
mailing list