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.