Authors: Richard Brent, Pierrick Gaudry, Emmanuel Thomé, Paul Zimmermann.
License (for the library) is either:
- If the archive contains a file named toom-gpl.c (not a trivial
placeholder), the GNU General Public License, either version 3 of
the License, or (at your option) any later version.
- If the archive contains a file named toom-gpl.c which is a trivial
placeholder, the GNU Lesser General Public License, either
version 2.1 of the License, or (at your option) any later
version.
License for the apps/ subdir is the GNU General Public License, either
version 2 of the License, or (at your option) any later version.
This package contains routines for fast arithmetic in GF(2)[x]
(multiplication, squaring, gcd).
Dependencies
============
gf2x has no external dependencies.
Some of the demos in the apps/ subdirectory require the gmp and NTL
libraries. (use ./configure ; make from that directory. You may want to
use PKG_CONFIG_PATH to have the autotools stuff there find gf2x
properly).
# The text below is somewhat outdated, and was originally written for
# gf2x 1.0 at best, and was marginally updated since. It is still
# "reasonably accurate", but must be followed with caution.
------------------------------------------------------------------------
Summary:
========
This README covers:
- Package contents
- Caution for gcc users
- Instructions to install the package
- Caution regarding installation
- Hooking gf2x into ntl
- Using the library
Package contents:
=================
It contains the following files:
Miscellaneous doc files:
README
BUGS
src/TODO
src/README
already_tuned/tuned/README
AUTHORS
ChangeLog
Actual code:
gf2x.h - main api
gf2x-impl.h - internal api
gf2x.c - top-level source for multiplication code
gf2x-small.h - small-sized inlined multiplication routines
toom.c - main file for Karatsuba and Toom-Cook multiplication
toom-gpl.c - same, for GPL-tainted distribution
fft.c - multiplication using Fast Fourier Transform
Code adapted for the selected hardware
already_tuned/ - pre-configured codes for selected architectures.
already_tuned/*/gf2x-thresholds.h - pre-tuned thresholds files
already_tuned/generic/gf2x-thresholds.h - placeholder thresholds
already_tuned/generic64/ - code that works on any 64-bit platform
already_tuned/generic32/ - code that works on any 32-bit platform
already_tuned/x86_64/ - code that works on amd64 and intel core2
already_tuned/x86_sse2/ - code that works on x86 platforms supporting sse2
already_tuned/generic/ - code that works everywhere. Does _not_ include mul1
gf2x/ - place where symlinks to the files above go
For testing:
tests/check-mul.c - simple check program
tests/do-check-mul.sh - shell script driving check-mul
For tuning:
lowlevel/mul*.c - various candidate code samples for basic routines
src/tuneup.c - tuning program for basecase multiplication
src/tunetoom.c - tuning program for Karatsuba/Toom-Cook multiplication
src/tunefft.c - tuning program for FFT multiplication
src/tune-lowlevel.pl
src/gen_bb_mul_code.c - program to generate many alternatives for mul1
src/replace.h - helper code
src/replace.c - helper code
src/tuning-common.h - helper code
src/tuning-common.c - helper code
src/timing.h - helper code
src/timing.c - helper code
src/modify-thresholds.c - helper code
Applications that use gf2x and NTL. These applications are covered by the
GPL.
apps/halfgcd.hpp - subquadratic gcd over GF(2)[x]
apps/halfgcd.cpp - subquadratic gcd over GF(2)[x]
apps/factor.cpp - finds smallest irreducible factor of trinomial over GF(2)
apps/check*.sh - some tests using factor
Caution for gcc users:
======================
gcc versions 4.3.0 and 4.3.1 have a bug which affects gf2x in a an
unpredictable way. It is recommended to upgrade to at least 4.3.2, or
configure with --disable-sse2
Instructions to install the package:
====================================
Cautious users follow steps 1 to 5 below. Urged users follow only 1 and 5.
1) Type:
./configure && make
A special case: your hardware platform may support several ABIs
(Application Binary Interfaces), corresponding to the type ``unsigned
long'' being either 32-bit or 64-bit wide. The gf2x package
accomodates for this under the assumption that ABI selection is
covered by the selection of the appropriate compiler options. In order
to compile for an ABI different from the default one, you have to pass
additional parameters to the configure script:
./configure ABI=<bit width of unsigned long> CFLAGS=<corresponding CFLAGS> && make
For example on a Mac OS X computer with an Intel Core 2 processor
using gcc, one may use: ./configure ABI=64 CFLAGS="-O2 -m64" && make
(equivalently, one may also use ABI=64 CC='gcc -m64')
Several other flags and arguments can be passed to ./configure (or set
as environment variables) ; see ./configure --help
2) Highly recommended ; run
make check
To guard against possible bugs (either from gf2x or from the
compiler).
3) Optional, but recommended: tune low-level routines, Karatsuba/Toom-Cook and
FFT multiplication:
make tune-lowlevel
make tune-toom
make tune-fft
Note that there are some minor issues related to tuning on amd64 -- see BUGS.
Tuning unfortunately takes a long while ; it is possible to decrease
the time spent in tuning using additional parameters to the ``make
tune-*'' commands, more specifically:
make tune-toom TOOM_TUNING_LIMIT=<max size in words>
make tune-fft FFT_TUNING_LIMIT=<max size in words>
The default values for TOOM_TUNING_LIMIT and FFT_TUNING_LIMIT are 2048
and 8000000, respectively. TOOM_TUNING_LIMIT must be in the range [30,2048],
while FFT_TUNING_LIMIT is only limited by the available memory.
More detailed information on tuning can be found in the
src/tunetoom.c and src/tunefft.c files, as well as
src/README.
All the tuning targets automatically rebuild the library in order to
incorporate the tuned parameters. So an additional ``make'' is
unnecessary (although innocuous, since the library should be up to
date).
4) Highly recommended ; run
make check
to see whether everything went ok.
5) Either run:
make install
Or, if you prefer, keep your build tree, and have your programs
include <buildtree>/gf2x.h, and link against the library
<buildtree>/.libs/libgf2x.a (static) or <buildtree>/.libs/libgf2x.so
(dynamic). Usual pitfalls apply regarding dynamic linking: if you are
familiar with none of the "-Wl,-rpath,<path>" or "LD_LIBRARY_PATH"
ways of making this work, your easiest bet is to stick to the static
library approach.
Notes for specific systems:
===========================
- ABI selection is sometimes tricky. Be sure that you select the proper
combination of ABI= and CFLAGS= parameters. You must also make sure
that those correspond to the CFLAGS that were used by any other binary
object you're linking gf2x with. That applies, in particular, to the
GMP library if you intend to compile the files in apps/
- under AIX the following might be required to build the gf2x binaries:
$ export OBJECT_MODE=64
Caution regarding installation:
===============================
The header files installed in $includedir/gf2x/ are architecure-dependent.
Hooking gf2x into ntl:
======================
ntl-5.5 offers the possibility to replace the multiplication of
polynomials with the gf2x code. For this, you have to install the gf2x
library in your favorite /path/to/gf2x/ (e.g. using gf2x's ./configure
--prefix=/path/to/gf2x/ && make && make install). Then configure NTL with
./configure NTL_GF2X_LIB=on GF2X_PREFIX=/path/to/gf2x/
If for some reason gf2x was installed with custom directories, you may
also consider the GF2X_INCDIR and GF2X_LIBDIR options ; some setups will
typically require GF2X_LIBDIR=/path/to/gf2x/lib64, for example.
Using the library:
==================
gf2x exports one public header called gf2x.h . This header exports one
function gf2x_mul, whose use is documented in gf2x.h . Unlike with
versions of gf2x up to 1.1, the function gf2x_mul is now reentrant as of
gf2x-1.2, and manages its own allocation needs. The companion function
gf2x_mul_r is here if you want to control the allocation needs -- within
a call to gf2x_mul_r, below the FFT threshold, no allocation is
performed. Above, there is some, and this is an acknowledged bug.
Some ``half-public'' headers are in the gf2x/ subdirectory. Some of these
headers (gf2x/gf2x-thresholds.h and gf2x/gf2x_mul* are
architecture-dependent). In order to use the inlined multiplication
routines for small sizes, you may use gf2x/gf2x-small.h.
By default, gf2x creates both static and dynamic libraries.
Generated by dwww version 1.15 on Thu Jun 27 23:24:45 CEST 2024.