3 ### Build script for mathematical infrastructure
5 ### (c) 2013 Straylight/Edgeware
8 ###----- Licensing notice ---------------------------------------------------
10 ### This file is part of Catacomb.
12 ### Catacomb is free software; you can redistribute it and/or modify
13 ### it under the terms of the GNU Library General Public License as
14 ### published by the Free Software Foundation; either version 2 of the
15 ### License, or (at your option) any later version.
17 ### Catacomb is distributed in the hope that it will be useful,
18 ### but WITHOUT ANY WARRANTY; without even the implied warranty of
19 ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 ### GNU Library General Public License for more details.
22 ### You should have received a copy of the GNU Library General Public
23 ### License along with Catacomb; if not, write to the Free
24 ### Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 ### MA 02111-1307, USA.
27 include $(top_srcdir)/vars.am
29 noinst_LTLIBRARIES = libmath.la
31 nodist_libmath_la_SOURCES =
34 TEST_LIBS = libmath.la
36 ###--------------------------------------------------------------------------
37 ### Representation of multiprecision integers.
39 ## The `mpgen' tool for dealing with these things.
40 mpgen = $(srcdir)/mpgen
42 AM_V_MPGEN = $(AM_V_MPGEN_@AM_V@)
43 AM_V_MPGEN_ = $(AM_V_MPGEN_@AM_DEFAULT_V@)
44 AM_V_MPGEN_0 = @echo " MPGEN $@";
45 MPGEN = $(AM_V_MPGEN)$(PYTHON) $(mpgen)
47 ## The type information collected by `configure'.
48 CLEANFILES += typeinfo.py
49 EXTRA_DIST += typeinfo.py.in
50 typeinfo.py: $(srcdir)/typeinfo.py.in Makefile
51 $(SUBST) $(srcdir)/typeinfo.py.in >typeinfo.py.new \
52 type_bits="@type_bits@" \
53 limits="@limits@" && \
54 mv typeinfo.py.new typeinfo.py
56 ## The header file containing our representation choices.
57 BUILT_SOURCES += mptypes.h
58 CLEANFILES += mptypes.h
59 nodist_archinclude_HEADERS += mptypes.h
60 mptypes.h: $(mpgen) typeinfo.py
61 $(MPGEN) mptypes >mptypes.h.in && mv mptypes.h.in mptypes.h
63 ## Limits of C types as multiprecision integers.
64 BUILT_SOURCES += mplimits.h mplimits.c
65 CLEANFILES += mplimits.h mplimits.c
66 nodist_archinclude_HEADERS += mplimits.h
67 nodist_libmath_la_SOURCES += mplimits.c
68 mplimits.h: $(mpgen) typeinfo.py
69 $(MPGEN) mplimits_h >mplimits.h.in && mv mplimits.h.in mplimits.h
70 mplimits.c: $(mpgen) typeinfo.py
71 $(MPGEN) mplimits_c >mplimits.c.in && mv mplimits.c.in mplimits.c
73 ###--------------------------------------------------------------------------
74 ### Main multiprecision integer library.
76 ## Additional buffer I/O functions for mathematical objects.
77 pkginclude_HEADERS += buf.h
78 libmath_la_SOURCES += buf.c
80 ## Infrastructure for fast exponentiation.
81 pkginclude_HEADERS += exp.h
82 libmath_la_SOURCES += exp.c
84 ## Main user-visible multiprecision arithmetic.
85 pkginclude_HEADERS += mp.h
86 libmath_la_SOURCES += mp-arith.c
87 TESTS += mp-arith.t$(EXEEXT)
88 libmath_la_SOURCES += mp-const.c
89 libmath_la_SOURCES += mp-exp.c mp-exp.h
90 libmath_la_SOURCES += mp-gcd.c
91 TESTS += mp-gcd.t$(EXEEXT)
92 libmath_la_SOURCES += mp-io.c
93 libmath_la_SOURCES += mp-jacobi.c
94 TESTS += mp-jacobi.t$(EXEEXT)
95 libmath_la_SOURCES += mp-mem.c
96 libmath_la_SOURCES += mp-misc.c
97 libmath_la_SOURCES += mp-modexp.c
98 TESTS += mp-modexp.t$(EXEEXT)
99 libmath_la_SOURCES += mp-modsqrt.c
100 TESTS += mp-modsqrt.t$(EXEEXT)
101 libmath_la_SOURCES += mp-sqrt.c
102 TESTS += mp-sqrt.t$(EXEEXT)
103 libmath_la_SOURCES += mp-nthrt.c
104 TESTS += mp-nthrt.t$(EXEEXT)
105 libmath_la_SOURCES += mp-test.c
108 ## Computing Fibonacci numbers.
109 pkginclude_HEADERS += mp-fibonacci.h
110 libmath_la_SOURCES += mp-fibonacci.c
111 TESTS += mp-fibonacci.t$(EXEEXT)
113 ## Special memory allocation for multiprecision integers.
114 pkginclude_HEADERS += mparena.h
115 libmath_la_SOURCES += mparena.c
117 ## Barrett reduction, an efficient method for modular reduction.
118 pkginclude_HEADERS += mpbarrett.h
119 libmath_la_SOURCES += mpbarrett.c
120 TESTS += mpbarrett.t$(EXEEXT)
121 libmath_la_SOURCES += mpbarrett-exp.c mpbarrett-mexp.c mpbarrett-exp.h
122 TESTS += mpbarrett-exp.t$(EXEEXT) mpbarrett-mexp.t$(EXEEXT)
123 TESTS += mpbarrett.t$(EXEEXT)
124 EXTRA_DIST += t/mpbarrett
126 ## Solving congruences using the Chinese Remainder Theorem.
127 pkginclude_HEADERS += mpcrt.h
128 libmath_la_SOURCES += mpcrt.c
129 TESTS += mpcrt.t$(EXEEXT)
130 EXTRA_DIST += t/mpcrt
132 ## Conversions between machine-native and multiprecision integers.
133 pkginclude_HEADERS += mpint.h
134 libmath_la_SOURCES += mpint.c
135 TESTS += mpint.t$(EXEEXT)
136 EXTRA_DIST += t/mpint
138 ## Montgomery reduction, a clever method for modular arithmetic.
139 pkginclude_HEADERS += mpmont.h
140 libmath_la_SOURCES += mpmont.c
141 TESTS += mpmont.t$(EXEEXT)
142 libmath_la_SOURCES += mpmont-exp.c mpmont-mexp.c mpmont-exp.h
143 TESTS += mpmont-exp.t$(EXEEXT) mpmont-mexp.t$(EXEEXT)
144 EXTRA_DIST += t/mpmont
146 ## Efficient multiplication of many small numbers.
147 pkginclude_HEADERS += mpmul.h
148 libmath_la_SOURCES += mpmul.c
149 TESTS += mpmul.t$(EXEEXT)
151 ## Generating random numbers.
152 pkginclude_HEADERS += mprand.h
153 libmath_la_SOURCES += mprand.c
155 ## Efficient reduction modulo numbers with conveninent binary
157 pkginclude_HEADERS += mpreduce.h
158 libmath_la_SOURCES += mpreduce.c mpreduce-exp.h
159 TESTS += mpreduce.t$(EXEEXT)
160 EXTRA_DIST += t/mpreduce
162 ## Iteratiion over the bianry representation of multiprecision integers.
163 pkginclude_HEADERS += mpscan.h
164 libmath_la_SOURCES += mpscan.c
166 ## Conversion between multiprecision integers and their textual
168 pkginclude_HEADERS += mptext.h
169 libmath_la_SOURCES += mptext.c
170 TESTS += mptext.t$(EXEEXT)
171 libmath_la_SOURCES += mptext-dstr.c
172 libmath_la_SOURCES += mptext-file.c
173 libmath_la_SOURCES += mptext-len.c
174 libmath_la_SOURCES += mptext-string.c
175 EXTRA_DIST += t/mptext
177 ## Low-level multiprecision arithmetic.
178 pkginclude_HEADERS += mpx.h bitops.h mpw.h
179 libmath_la_SOURCES += mpx.c
180 TESTS += mpx.t$(EXEEXT)
181 libmath_la_SOURCES += karatsuba.h mpx-kmul.c mpx-ksqr.c
182 TESTS += mpx-kmul.t$(EXEEXT) mpx-ksqr.t$(EXEEXT)
183 noinst_PROGRAMS += bittest
188 MPX_MUL4_SOURCES = mpx-mul4-x86-sse2.S
189 check_PROGRAMS += mpx-mul4.t
190 TESTS += mpx-mul4.t$(EXEEXT)
193 MPX_MUL4_SOURCES = mpx-mul4-amd64-sse2.S
194 check_PROGRAMS += mpx-mul4.t
195 TESTS += mpx-mul4.t$(EXEEXT)
198 MPX_MUL4_SOURCES = mpx-mul4-arm-neon.S
199 check_PROGRAMS += mpx-mul4.t
200 TESTS += mpx-mul4.t$(EXEEXT)
203 MPX_MUL4_SOURCES = mpx-mul4-arm64-simd.S
204 check_PROGRAMS += mpx-mul4.t
205 TESTS += mpx-mul4.t$(EXEEXT)
207 libmath_la_SOURCES += $(MPX_MUL4_SOURCES)
208 mpx_mul4_t_SOURCES = mpx-mul4-test.c $(MPX_MUL4_SOURCES)
209 mpx_mul4_t_CPPFLAGS = \
211 -DTEST_MUL4 -DSRCDIR="\"$(srcdir)\""
212 mpx_mul4_t_LDFLAGS = $(TEST_LDFLAGS)
213 mpx_mul4_t_LDADD = $(top_builddir)/libcatacomb.la $(mLib_LIBS)
214 EXTRA_DIST += t/mpx-mul4
216 ## A quick-and-dirty parser, used for parsing descriptions of groups, fields,
218 pkginclude_HEADERS += qdparse.h
219 libmath_la_SOURCES += qdparse.c
221 ## Pollard's `rho' algorithm for determining discrete logarithms.
222 pkginclude_HEADERS += rho.h
223 libmath_la_SOURCES += rho.c
224 TESTS += rho.t$(EXEEXT)
226 ###--------------------------------------------------------------------------
227 ### Prime number checking, searching, and related jobs.
229 ## Generating Lim--Lee groups, i.e., unit groups of finite fields without
230 ## small subgroups (except for the obvious ones).
231 pkginclude_HEADERS += limlee.h
232 libmath_la_SOURCES += limlee.c
234 ## A table of small prime numbers.
235 pkginclude_HEADERS += $(precomp)/math/primetab.h
236 nodist_libmath_la_SOURCES += ../precomp/math/primetab.c
237 PRECOMPS += $(precomp)/math/primetab.h \
238 $(precomp)/math/primetab.c
239 PRECOMP_PROGS += genprimes
240 genprimes_LDADD = $(mLib_LIBS)
242 $(precomp)/math/primetab.h: $(precomp)/math/primetab.c
243 $(precomp)/math/primetab.c:
244 $(AM_V_at)$(MKDIR_P) $(precomp)/math
245 $(AM_V_at)$(MAKE) genprimes$(EXEEXT)
246 $(AM_V_GEN)./genprimes -sCATACOMB_PRIMETAB_H \
247 -h$(precomp)/math/primetab.h -c$(precomp)/math/primetab.c \
248 -n256 -t"unsigned short" -iprimetab
251 ## Filtering candidate prime numbers by checking for small factors
253 pkginclude_HEADERS += pfilt.h
254 libmath_la_SOURCES += pfilt.c
256 ## Generating prime numbers (and other kinds of numbers which need searching
258 pkginclude_HEADERS += pgen.h
259 libmath_la_SOURCES += pgen.c
260 libmath_la_SOURCES += pgen-gcd.c
261 libmath_la_SOURCES += pgen-granfrob.c
262 libmath_la_SOURCES += pgen-simul.c
263 libmath_la_SOURCES += pgen-stdev.c
264 TESTS += pgen.t$(EXEEXT) pgen-granfrob.t$(EXEEXT)
267 ## Finding primitive elements in finite fields.
268 pkginclude_HEADERS += prim.h
269 libmath_la_SOURCES += prim.c
271 ## Iterating over all prime numbers from a given starting point.
272 pkginclude_HEADERS += primeiter.h
273 libmath_la_SOURCES += primeiter.c
274 TESTS += primeiter.t$(EXEEXT)
275 primeiter.lo: $(precomp)/math/wheel.h
277 ## The Miller--Rabin primality test.
278 pkginclude_HEADERS += rabin.h
279 libmath_la_SOURCES += rabin.c
281 ## Finding `strong' primes, using Gordon's algorithm. Once upon a time,
282 ## products of these kinds of numbers were harder to factor.
283 pkginclude_HEADERS += strongprime.h
284 libmath_la_SOURCES += strongprime.c
286 ## A `wheel', used by the prime iteration machinery.
287 pkginclude_HEADERS += $(precomp)/math/wheel.h
288 nodist_libmath_la_SOURCES += ../precomp/math/wheel.c
289 PRECOMPS += $(precomp)/math/wheel.h $(precomp)/math/wheel.c
290 PRECOMP_PROGS += genwheel
291 genwheel_LDADD = $(mLib_LIBS)
293 $(precomp)/math/wheel.h: $(precomp)/math/wheel.c
294 $(precomp)/math/wheel.c:
295 $(AM_V_at)$(MKDIR_P) $(precomp)/math
296 $(AM_V_at)$(MAKE) genwheel$(EXEEXT)
297 $(AM_V_GEN)./genwheel -sCATACOMB_WHEEL_H \
298 -h$(precomp)/math/wheel.h -c$(precomp)/math/wheel.c \
299 -n5 -t"unsigned char" -iwheel
302 ###--------------------------------------------------------------------------
303 ### Binary polynomial arithmetic.
305 ## User-visible binary polynomial arithmetic.
306 pkginclude_HEADERS += gf.h
307 libmath_la_SOURCES += gf-arith.c
308 TESTS += gf-arith.t$(EXEEXT)
309 libmath_la_SOURCES += gf-exp.c gf-exp.h
310 libmath_la_SOURCES += gf-gcd.c
311 TESTS += gf-gcd.t$(EXEEXT)
314 ## Low-level binary polynomial arithmetic.
315 pkginclude_HEADERS += gfx.h
316 libmath_la_SOURCES += gfx.c
317 TESTS += gfx.t$(EXEEXT)
318 libmath_la_SOURCES += gfx-kmul.c
319 TESTS += gfx-kmul.t$(EXEEXT)
320 libmath_la_SOURCES += gfx-sqr.c
321 TESTS += gfx-sqr.t$(EXEEXT)
324 ## Conversions between normal and polynomial basis representations for binary
326 pkginclude_HEADERS += gfn.h
327 libmath_la_SOURCES += gfn.c
328 TESTS += gfn.t$(EXEEXT)
331 ## Efficient reduction modulo sparse polynomials.
332 pkginclude_HEADERS += gfreduce.h
333 libmath_la_SOURCES += gfreduce.c gfreduce-exp.h
334 TESTS += gfreduce.t$(EXEEXT)
335 EXTRA_DIST += t/gfreduce
337 ###--------------------------------------------------------------------------
338 ### Abstractions for various kinds of algebraic objects.
340 ## Abstract cyclic groups.
341 pkginclude_HEADERS += group.h group-guts.h
342 libmath_la_SOURCES += group-dstr.c
343 libmath_la_SOURCES += group-exp.c group-exp.h
344 libmath_la_SOURCES += group-file.c
345 libmath_la_SOURCES += group-parse.c
346 libmath_la_SOURCES += group-stdops.c
347 libmath_la_SOURCES += group-string.c
348 libmath_la_SOURCES += g-bin.c
349 libmath_la_SOURCES += g-prime.c
350 libmath_la_SOURCES += g-ec.c
351 EXTRA_DIST += group-test.c
352 TESTS += group-test.t$(EXEEXT)
353 EXTRA_DIST += t/group
355 ## Abstract finite fields.
356 pkginclude_HEADERS += field.h field-guts.h
357 libmath_la_SOURCES += field.c
358 libmath_la_SOURCES += field-exp.c field-exp.h
359 libmath_la_SOURCES += field-parse.c
360 libmath_la_SOURCES += f-binpoly.c
361 libmath_la_SOURCES += f-niceprime.c
362 libmath_la_SOURCES += f-prime.c
364 ## Table of built-in binary fields.
365 pkginclude_HEADERS += bintab.h
366 nodist_libmath_la_SOURCES += bintab.c
367 CLEANFILES += bintab.c
368 EXTRA_DIST += bintab.in
369 bintab.c: $(mpgen) typeinfo.py bintab.in
370 $(MPGEN) bintab $(srcdir)/bintab.in >bintab.c.new && \
371 mv bintab.c.new bintab.c
373 ## Table of built-in prime fields.
374 pkginclude_HEADERS += ptab.h
375 nodist_libmath_la_SOURCES += ptab.c
377 EXTRA_DIST += ptab.in
378 ptab.c: $(mpgen) typeinfo.py ptab.in
379 $(MPGEN) ptab $(srcdir)/ptab.in >ptab.c.new && \
382 ###--------------------------------------------------------------------------
383 ### Elliptic curve arithmetic.
385 ## Basic elliptic curve arithmetic.
386 pkginclude_HEADERS += ec.h ec-guts.h
387 libmath_la_SOURCES += ec.c
388 libmath_la_SOURCES += ec-exp.c ec-exp.h
389 libmath_la_SOURCES += ec-info.c
390 TESTS += ec-info.t$(EXEEXT)
391 libmath_la_SOURCES += ec-bin.c
392 TESTS += ec-bin.t$(EXEEXT)
393 libmath_la_SOURCES += ec-prime.c
394 TESTS += ec-prime.t$(EXEEXT)
397 ## The standard `raw' encoding (`EC2OSP') of elliptic curve points.
398 pkginclude_HEADERS += ec-raw.h
399 libmath_la_SOURCES += ec-raw.c
401 ## Assistance for elliptic-curve keys.
402 pkginclude_HEADERS += ec-keys.h
403 libmath_la_SOURCES += ec-fetch.c
405 ## Test infrastructure for elliptic curves.
406 pkginclude_HEADERS += ec-test.h
407 libmath_la_SOURCES += ec-test.c
408 TESTS += ec-test.t$(EXEEXT)
410 ## Table of built-in elliptic-curve groups.
411 pkginclude_HEADERS += ectab.h
412 nodist_libmath_la_SOURCES += ectab.c
413 CLEANFILES += ectab.c
414 EXTRA_DIST += ectab.in
415 ectab.c: $(mpgen) typeinfo.py ectab.in
416 $(MPGEN) ectab $(srcdir)/ectab.in >ectab.c.new && \
417 mv ectab.c.new ectab.c
419 ###--------------------------------------------------------------------------
420 ### Other strange things.
422 pkginclude_HEADERS += qfarith.h
424 pkginclude_HEADERS += f25519.h
425 libmath_la_SOURCES += f25519.c
426 TESTS += f25519.t$(EXEEXT)
427 TESTS += f25519-p10.t$(EXEEXT)
428 EXTRA_DIST += t/f25519
430 check_PROGRAMS += f25519-p10.t
431 f25519_p10_t_SOURCES = f25519.c
432 f25519_p10_t_CPPFLAGS = $(AM_CPPFLAGS) -DTEST_RIG -DSRCDIR="\"$(srcdir)\""
433 f25519_p10_t_CPPFLAGS += -DF25519_IMPL=10
434 f25519_p10_t_LDFLAGS = $(TEST_LDFLAGS)
435 f25519_p10_t_LDADD = $(TEST_LIBS) $(top_builddir)/libcatacomb.la
436 f25519_p10_t_LDADD += $(mLib_LIBS) $(CATACOMB_LIBS) $(LIBS)
438 pkginclude_HEADERS += fgoldi.h
439 libmath_la_SOURCES += fgoldi.c
440 TESTS += fgoldi.t$(EXEEXT)
441 TESTS += fgoldi-p12.t$(EXEEXT)
442 EXTRA_DIST += t/fgoldi
444 check_PROGRAMS += fgoldi-p12.t
445 fgoldi_p12_t_SOURCES = fgoldi.c
446 fgoldi_p12_t_CPPFLAGS = $(AM_CPPFLAGS) -DTEST_RIG -DSRCDIR="\"$(srcdir)\""
447 fgoldi_p12_t_CPPFLAGS += -DFGOLDI_IMPL=12
448 fgoldi_p12_t_LDFLAGS = $(TEST_LDFLAGS)
449 fgoldi_p12_t_LDADD = $(TEST_LIBS) $(top_builddir)/libcatacomb.la
450 fgoldi_p12_t_LDADD += $(mLib_LIBS) $(CATACOMB_LIBS) $(LIBS)
452 pkginclude_HEADERS += scaf.h
453 libmath_la_SOURCES += scaf.c
455 pkginclude_HEADERS += montladder.h
456 pkginclude_HEADERS += scmul.h
458 ###----- That's all, folks --------------------------------------------------