%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This file is part of the C Meat-Axe.                                 %
% Written by Michael Ringe <mringe@tiffy.math.rwth-aachen.de>          %
% (C) Copyright 1992:	    Lehrstuhl D fuer Mathematik                %
%                           RWTH Aachen                                %
%                           Aachen, Germany                            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\def\Libitem#1#2{\subsection*{\hfill{\tt #1}}\vspace{-1.3em}%
\rule{\linewidth}{0.3mm}\\\vspace{-2em}}

\def\Function#1#2{\Libitem{#1()}{#2}\index{#1@{\tt #1()}}}

%\def\Synopsis{\subsubsection*{\sc Synopsis}}
%\def\Description{\subsubsection*{\sc Description}}

\def\Synopsis{\goodbreak\vspace{-0.0em}\par\noindent\rule{\linewidth}{0.2mm}\nopagebreak\vspace{-1em}%
\nopagebreak}
\def\EndSynopsis{\nopagebreak\vspace{-1.5em}\nopagebreak\rule{\linewidth}{0.2mm}\goodbreak}
\def\Description{\medskip\par\noindent}

\chapter{The MeatAxe Library}\label{chap:libs}
%============================
\index{libraries}

The {\MeatAxe} system consists of a library of functions and user
programs (see chapter \ref{chap:progs}) depending on the library.
Using the library you can create your own {\MeatAxe} programs, or
modify the existing programs to suit your personal needs.
In the following sections you will find
\begin{enumerate}
\item
    a description of all {\MeatAxe} library functions. The functions
    are grouped by category (e.g., matrix functions, memory
    functions, etc.). To find a specific function by name, look
    in the index at the end of this document.
\item
    instructions for writing your own {\MeatAxe} programs. For each
    library function there is a short description, and (sometimes)
    more detailed instructions including short examples.
\end{enumerate}
Note: Throughout this chapter I assume that you are familiar with
the C programming language. If you have no experience in writing
programs in C, this is probably not the best way to start.


\section{How to use the library}
%-------------------------------
To use the {\MeatAxe} library in your programs you need two files:
\begin{center}
\begin{tabular}{lp{0.8\linewidth}}
\verb"libmtx.a" & The library file. This file is generated during
	the compilation process (see section \ref{sec:compile}
	for details).\\
\verb"meataxe.h" & The header file for all {\MeatAxe} library
	functions. This file is part of the distribution.
\end{tabular}
\end{center}
You must include the header file in your program by putting the line
\begin{verbatim}
    #include "meataxe.h"
\end{verbatim}
somewhere at the top of your program. If \verb"meataxe.h" resides in
the same directory as your program the compiler will find it there.
Otherwise you must specify a complete path in the include statement
or specify the directory on the command line, for example:
\msg{cc -c -I/usr/joe/mtx/src -o myprog.o myprog.c}
Having compiled your program you must link it with the
{\MeatAxe} library. Here is an example:
\msg{cc -o myprog myprog.o libmtx.a}

Some hints for using the library:
\begin{enumerate}
\item
    Library functions don't terminate your program if an error
    occurs. See section \ref{sec:liberr} for details about
    error messages and error handling.
\item
    Always use pointers for complex data types such as \verb"matrix_t".
    For example, declaring a variable as \verb"matrix_t mat" is usually
    more complicated than declaring "\verb"matrix_t *mat".
\item
    There is a sample file called \verb"examples.c" which has no
    functionality but demonstrates the use of many library functions.
    You may use this sample program as a basis for your own programs.
\end{enumerate}



\section{{\MeatAxe} data types}\label{sec:intdata}
%-----------------------------
\index{data types (overview)}

\subsection{Simple data types}
%-----------------------------
\index{FEL@{\tt FEL} data type}
\index{PTR@{\tt PTR} data type}
\index{simple data types}
There are two basic data types:
\begin{center}
\begin{tabular}{|l|l|}
\hline
Data type	& Meaning \\
\hline
\verb"FEL"	& Finite field element\\
\verb"PTR"	& Pointer to a (packed) vector or matrix\\
\hline
\end{tabular}
\end{center}
The actual implementation of these types depends on the library
version you are using. Currently, there are two versions of the
{\MeatAxe}
library available, a `small' version for field orders up to 256,
and a `big' version for larger fields up to $q=2^{16}$. In the
small version vectors are stored in packed format putting two or
more elements into one byte (see \ref{sec:fel}). This saves both
memory and speed since
arithmetic operations can be performed simultaneously on multiple
elements. The version is selected at compile time, see section
\ref{sec:compile} for details.

\subsection{Complex data types}
%------------------------------
In addition to the elementary data types, there are more complex
types: 
\begin{center}
\begin{tabular}{|l|l|}
\hline
Data type	& Meaning \\
\hline
\verb"matrix_t"	& Matrix over a finite field (see \ref{sec:matrix})\\
\verb"perm_t"	& Permutation (see \ref{sec:perms})\\
\verb"poly_t"	& Polynomial over a finite field (see \ref{sec:poly})\\
\verb"bitstring_t"& Set (bit string) (see \ref{sec:bitstrings})\\
\verb"set_t"	& Set (ordered list) (see \ref{sec:sets})\\
\verb"sequence_t"& A sequence (see \ref{sec:seq})\\
\hline
\end{tabular}
\end{center}


\subsection{Internal representation}
%-----------------------------------
\subsubsection{Field elements}\label{sec:fel}
%- - - - - - - - - - - - -
In the small version, field elements of GF$(q)$ are represented
by the numbers $0,1,\ldots,q-1$. The field is defined by its
Conway polynomial $p(x)$, a polynomial of degree $n$ over $\Z_p[x]$,
where $q=p^n$. Thus, we have a one-to-one correspondence of field
elements $a\in{\rm GF}(q)$ and polynomials $f_a(x)\in\Z_p[x]$ of
degree $\leq n$. By treating $\Z_p$ as a subset of $\Z$ ---
actually, on the computer, elements of $\Z_p$ are represented
by integers --- this is also a polynomial over $\Z$. Now,
calculate $f_a(p)$ giving the number of the field element $a$.
It follows that the elements of the prime field are represented by
$0$, $1$, \ldots, $p-1$. The number 0 represents the zero element,
and 1 represents the unit element.

If the field order is not too big, several field elements are packed
into one byte. Let $q$ be the field order and $m$ the largest natural
number with $q^m\leq 256$, i.e.
\[
	m := \lfloor 8/\log_2 q \rfloor
\]
Then, $m$ elements are packed into one byte using the
packing function:
\[
	\mbox{pack}(k_1,\ldots,k_m) = \sum_{i=0}^m k_iq^i
\]
Packing of field elements is used exclusively for rows (vectors),
not for poynomials or other data types.

The `big' version uses always 2 Bytes ({\tt unsigned short}) for field
elements. Non-zero elements are stored as their logarithms with
respect to a fixed generator, i.e. the unit element is represented by
the number 0. The zero element is represented by
the special value {\tt 0xFFFF}.

As a consequence of the different representations of field elements
in the `small' and `big' version, programs should never
\begin{itemize}
\item	assign numbers to variables of type {\tt FEL} or pass numbers
        to functions expecting an argument of type {\tt FEL}
\item	perform integer arithmetic on variables of type {\tt FEL}
\item	{\tt printf} or {\tt scanf} variables of type {\tt FEL}
\end{itemize}
Instead of using the literals 0 and 1 for the zero and unit element in
the field, which would produce wrong results with the `big' version,
you should use the following predefined constants:
\index{F_ZERO@{\tt F\_ZERO} constant}
\index{F_ONE@{\tt F\_ONE} constant}
\begin{center}
\begin{tabular}{|c|c|c|}
	\hline
	Name	& \multicolumn{2}{c|}{Value} \\
		&  `small' version & `big' version \\ \hline
	{\tt F\_ZERO}	& 0 & 0xFFFF \\
	{\tt F\_ONE}	& 1 & 0 \\
	\hline
\end{tabular}
\end{center}
In addition to these constants there are two functions,
{\tt zitof()} and {\tt zftoi()}, which provide a one-to-one mapping
between {\tt FEL} values and the integer numbers 0,\ldots,$q-1$
(see section \ref{sec:convert}).



\subsubsection{Packed vectors (Rows)}
% - - - - - - - - - - - - - - - - -
A (row) vector is stored in memory as an array of bytes. The memory
size of a row depends on the number of marks in the row and on the
field order. However, the size is always a multiple of
{\tt sizeof(long)}. Thus, there may be unused bytes at the end of a
row. The contents of these extra bytes (and even the contents of
unused bits in partially used bytes) is not defined. For this reason,
memory must be initialized before it is used, or else some functions
as `compare rows' may fail.

A single entries of a row is selected by its index where $1$
corresponds to the first entry. This differs from the C convention
of starting indexes with 0.


\subsubsection{Matrices}
%- - - - - - - - - -
A matrix is stored as a sequence of rows with no extra space between
them. The rows and columns of a matrix are numbered $1,2,\ldots n$.
Column vectors may be stored as matrices with one column but this is
very inefficient because each mark of the vector will occupy 4 Bytes.


\subsubsection{Permutations}
%- - - - - - - - - - - - -
Permutations operate on the set $\{1,2,\ldots,n\}$, where $n$ is the
degree. Internally, a permutation $\pi$ on $n$ points is stored as an
array of long integers containing the images ($1\pi,2\pi,\ldots,n\pi$).


\section{File formats}\label{sec:filefmt}
%---------------------
The format of readable files is described together with the ZPR and
ZCV programs in chapter \ref{chap:progs}.
Binary data files utilize the data format as described in section
\ref{sec:intdata}. However, rows are truncated to their actual
length. For example, a row with 17 entries over GF(125) on a machine
with ${\tt sizeof(long)}=4$ would occupy 20 bytes in memory but only
17 bytes in a data file.

At the beginning of the file there is a header
(3 Integers) containing the field parameter and two other values.
The meaning of these values is as follows:
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
field parameter 	     & 2nd value 	& 3rd value \\
\hline
$q > 1$: Matrix over $GF(q)$ & no.\ of rows	& no.\ of columns \\
-1: Permutation		     & no.\ of points& no.\ of permutations \\
\hline
\end{tabular}
\end{center}
The format of the header is machine independent (4 bytes per entry,
least significant byte first). Packed rows, too, are machine
independent, i.e., matrix files created with the small version
can be shared between different machines. Other data files are
in general not compatible between different machines.



\section{{\MeatAxe} library functions}
%-------------------------------------

\subsection{General functions}
%-----------------------------
\index{mtxinit@{\tt mtxinit()}}

\Synopsis %!xref! mtxinit
\begin{verbatim}
int mtxinit(void);
\end{verbatim}
\EndSynopsis

\Description
\verb"mtxinit()" initializes the library including finite field
arithmetic and file i/o functions. It must be called before any
other {\MeatAxe} library function. \verb"mtxinit()" returns a
version number. This version number is different for each
implementation of the arithmetic. Currently there are two versions,
a small one for fields up to GF(256) and a big version for field
orders up to $2^{16}$.


\subsection{Finite field arithmetic}
%-----------------------------------

\subsubsection{General} \label{sec:zzzvars}
%----------------------
\index{zfl@{\tt zfl}}
\index{zchar@{\tt zchar}}
\index{zgen@{\tt zgen}}
\index{znoc@{\tt znoc}}
\index{zerrno@{\tt zerrno}}
\index{field!selecting}
\index{row size!setting}
\index{zsetlen@{\tt zsetlen()}}


\Synopsis % !xref! zfl,zchar,zgen,znoc,zsetlen
\begin{verbatim}
long zfl, zchar;     /* Field order and characteristic */
FEL zgen;            /* Generator */
long znoc;           /* Number of columns for row ops */
void zsetlen(long field,long ncols);
\end{verbatim}
\EndSynopsis

\Description
\verb"zsetlen()" sets the current field to GF(\verb"field") and the
current row size to \verb"ncols". The row size is important for
row operations (see \ref{sec:rowops}). Many {\MeatAxe} library
functions require that you call \verb"zsetlen()" before they
can be used. If no field is set or if the current field is
different from GF(\verb"field"), the arithmetic table file is read
into memory. If it does not exist, \verb"zsetlen()" will try to run
the \verb"maketab" program in order to create the table file. If
this fails, too, the program stops. If only the row size changes,
the table file is not read again.

%If the field parameter is $-1$, \verb"zsetlen()" sets the
%row size for permutations of degree \verb"noc". This is used,
%for example, in connection with \verb"zseek()" to move around
%in a file containing multiple permutations.

There are some global variables which are used by the field
arithmetic and row operations.
\verb"zfl" is the current field order,
\verb"zchar" is the current characteristic,
\verb"zgen" is a generator for the current field, and
\verb"znoc" is the current row size (number of columns).

\noindent
{\em Warning:} Some of the library functions rely on the
fact that the variables listed above are modified only by
library functions. A program may use the value of {\tt zchar},
say, to find out the characteristic of the field currently in
use but it should not change the value of any of the variables.



\subsubsection{Basic field arithmetic}
%-------------------------------------
\index{arithmetic!finite fields}
\index{field arithmetic}
\index{zadd@{\tt zadd()}}
\index{zsub@{\tt zsub()}}
\index{zmul@{\tt zmul()}}
\index{zdiv@{\tt zdiv()}}

\Synopsis
\begin{verbatim}
FEL zadd(FEL a, FEL b);
FEL zsub(FEL a, FEL b);
FEL zmul(FEL a, FEL b);
FEL zdiv(FEL a, FEL b);
\end{verbatim}
\EndSynopsis

\Description
These functions perform basic arithmetic in finite fields.
\verb"zadd()" returns the sum of its arguments,
\verb"zsub()" returns ${\tt a}-{\tt b}$,
\verb"zmul()" returns the product of its arguments, and
\verb"zdiv()" returns ${\tt a}/{\tt b}$.
Before any of these functions can be used, a field must be
selected with \verb"zsetlen()".
Division by zero is recognized and results in program
termination. Except for this case, there is no check
that the arguments are valid field elements.


\subsubsection{Subfields}
%------------------------
\index{subfields}
\index{zembed@{\tt zembed()}}
\index{zrestrict@{\tt zrestrict()}}

In the {\MeatAxe} system there is a `standard' generator for
each finite field. The generator for the field currently in use
is available in the \verb"zgen" variable. Thus, if $a$ and $a'$ are the
{\MeatAxe} generators of GF($q$) and GF($q'$), respectively, and
$q'=q^n$, there is a `standard' embedding of GF($q$) into GF($q'$)
defined by $a\mapsto (a')^n$.
However, field elements which are identified under this embedding
are usually not represented by the same number. For this reason
there are two functions, \verb"zembed()" and \verb"zrestrict()",
which provide the embedding of subfields into the current field.
Note that the {\MeatAxe} is not well suited for calculations involving
different fields at the same time because of its table driven
arithmetics.


\Synopsis
\begin{verbatim}
FEL zembed(FEL a, long subfield)
FEL zrestrict(FEL a, long subfield)
\end{verbatim}
\EndSynopsis

\Description
\verb"zembed()" embeds an element of a subfield into the
current field.

\verb"zrestrict()" restricts a field element to a subfield.
The return value represents the same element (under the standard
identification explained above) but with respect to the subfield.
\verb"a" must be of the form \verb"zembed(g,subfield)". Otherwise
the result is undefined. For example, restricting from GF(8) to
GF(2) works only with the prime field elements, i.e., $0$ and $1$.
Note that you cannot use the return value of \verb"zrestrict()"
(for field arithmetic, say) until you change to the subfield
with \verb"zsetlen(subfield,...)".

Here is a short example.
The following code converts a vector over GF(3) to GF(9). The
{\MeatAxe} cannot handle two fields at the same time, so it is
necessary to unpack the row over GF(3), change to GF(27) and
pack the embedded elements in to a new row.
\begin{verbatim}
PTR row1, row2;
FEL buf[10];
...
zsetlen(3,10);
for (i = 1; i <= 10; ++i) buf[i-1] = zextract(row1,i);
zsetlen(27,10);
for (i = 1; i <= 10; ++i) zinsert(row2,i,zembed(buf[i-1],3));
\end{verbatim}


\subsection{Memory}
%------------------
\index{memory}
\index{zalloc@{\tt zalloc()}}
\index{zsize@{\tt zsize()}}
\index{zadvance@{\tt zadvance()}}

\Synopsis
\begin{verbatim}
PTR zalloc(long nrows);
size_t zsize(long nrows);
void zadvance(PTR *ptr, long nrows);
\end{verbatim}
\EndSynopsis

\Description
\verb"zalloc()" allocates memory for \verb"nrows" rows of the
current row size. The row size must have been specified previously
with \verb"zsetlen()". Memory allocated with
\verb"zalloc()" may be freed using \verb"free()".

\verb"zsize()" returns the number of bytes occupied by
\verb"nrows" rows of the current row size. The row size must have been
specified previously with \verb"zsetlen()".
This function can be used whenever you need to know the
size of a matrix or vector in bytes. Here are some examples:
\begin{verbatim}
PTR x, y;
memcpy(y,x,zsize(10));      /* Copy 10 rows from x to y */
if (memcmp(x,y,zsize(1))    /* Compare first row */
    printf("Identical!\n");
fwrite(x,zsize(1),5,f);     /* Write 5 rows to file f */
\end{verbatim}
{\em Note:} You should not allocate rows with
\verb"malloc(zsize(...))" because \verb"malloc()" does not
initialize memory. Instead, use \verb"zalloc()".

\verb"zadvance()" increments a pointer by \verb"nrows" rows. This
functions is typically used to step trough the rows of a matrix.
Before it can be used, the row size must have been set correctly
with \verb"zsetlen()". Here is an example:
\begin{verbatim}
PTR mat;
zsetlen(3,100);    /* GF(3), dimension=100 */
mat = zalloc(100); /* Allocate a 100x100 matrix */
zadvance(&mat,49); /* Increment by 49 rows */
\end{verbatim}
After this sequence, \verb"mat" points to the 50th row of the
matrix.

{\em Note:} As the C language uses call-by-value, the first
argument of \verb"zadvance()" is not a \verb"PTR" but a \verb"*PTR",
i.e., a pointer to a \verb"PTR"! If you want to use \verb"zadvance()"
on a \verb"PTR" variable, you must use the \verb"&" operator, as in
the example above. \verb"zadvance(mat,49)" would be an error, but
your compiler might not warn you about this, so be careful.



\subsection{Working with packed vectors}
%---------------------------------------
Logically, vectors are arrays of field elements. However, they
are stored internally in packed form, so you cannot access
entries with the usual bracket operator. Instead the {\MeatAxe}
library provides functions which store and read marks. A second
difference is that the first entry in a vector has index 1, not
0 as in C arrays.

\index{zinsert@{\tt zinsert()}}
\index{zextract@{\tt zextract()}}
\index{zfindpiv@{\tt zfindpiv()}}
\Synopsis
\begin{verbatim}
void zinsert(PTR row, long col, FEL mark);
FEL zextract(PTR row, long col);
long zfindpiv(PTR row,FEL *mark);
\end{verbatim}
\EndSynopsis

\Description
\verb"zinsert()" inserts the field element \verb"mark" at position
\verb"col" into \verb"row". Before this function can be used, a
field must be selected with \verb"zsetlen()". Once a field is
selected, \verb"zinsert()" works with any row, regardless of the
current row size. So, if you are
working with two rows of different size, you do not have to
call \verb"zsetlen()" prior to each \verb"zinsert()".

\noindent{\em Notes:}
\begin{enumerate}
\item
    There is no protection against writing beyond the end
    of a row. The user must assure that \verb"row" points to a
    row of at least \verb"col" columns. Otherwise your program
    may crash or produce undefined results.
\item
    You can use \verb"zinsert()" on matrices, but only for the
    first row. A construct like
\begin{verbatim}
zsetlen(3,10);         /* GF(3), dimension = 10 */
mat=zalloc(10);        /* Allocate 10 rows */
zinsert(mat,11,F_ONE); /* set mat[1,1]=1   ERROR!!! */
\end{verbatim}
    does not work because of the internal storage format for rows.
    Instead you should write
\begin{verbatim}
PTR x = mat;
zadvance(&x,1);
zinsert(x,1,F_ONE);    /* set mat[1,1]=1   O.K. */
\end{verbatim}
\item
    Packed rows must be initialized before they are used. Both
    \verb"zinsert()" and \verb"zextract()" (and many other row
    operations) will produce strange results if used with
    uninitialized rows. Memory is initialized
    automatically in the following cases: allocation with 
    \verb"zalloc()", copying a row with \verb"zmoverow()",
    reading a row from a file. A row can be initialized
    manually by multiplication with zero: \verb"zmulrow(ptr,F_ZERO)".
    The latter works even if no field has been selected. 
\end{enumerate}

\verb"zextract()" returns the entry at position \verb"col" of a
row.  Remember that \verb"col=1" and not \verb"col=0" corresponds
to the first entry and so on.  Like \verb"zinsert()", this function
does not depend on the
current row size. Reading beyond the end of a row will probably
not produce an error, but the result is undefined.

\verb"zfindpiv()" scans the vector \verb"row" and finds the first
non-zero mark. The mark is stored into \verb"mark" and its position
(counting from 1) is returned. If the whole vector is zero,
\verb"zfindpiv()" returns 0 and leaves \verb"mark" unchanged.


\subsection{Row operations}\label{sec:rowops}
%--------------------------
\index{row operations}
\index{zmoverow@{\tt zmoverow()}}
\index{zswaprow@{\tt zswaprow()}}
\index{zcmprow@{\tt zcmprow()}}
\index{zaddrow@{\tt zaddrow()}}
\index{zmulrow@{\tt zmulrow()}}
\index{zmaprow@{\tt zmaprow()}}
\index{zpermrow@{\tt zpermrow()}}


\Synopsis
\begin{verbatim}
void zmoverow(PTR dest, PTR src);
void zswaprow(PTR dest, PTR src);
void zcmprow(PTR dest, PTR src);
void zaddrow(PTR row1,PTR row2);
void zmulrow(PTR row,FEL mark);
void zaddmulrow(PTR row1,PTR row2,FEL f);
void zmaprow(PTR row,PTR mat,long nor,PTR result);
void zpermrow(PTR row,PTR perm,PTR result);
\end{verbatim}
\EndSynopsis

\Description
All row operations require row size to be specified previously.
This is done with \verb"zsetlen()".

\verb"zmoverow()" copies one row from \verb"src" to \verb"dest".
\verb"zswaprow()" exchanges the contents of two rows.
\verb"zcmprow()" compares two rows at \verb"src" and \verb"dest".
The return value is 0, if the two rows are identical, and
1 otherwise.

\verb"zaddrow()" adds \verb"row2" to \verb"row1".
\verb"zmulrow()" multiplies \verb"row" by the scalar \verb"mark".
Multiplying a row with zero (\verb"F_ZERO") initializes the
memory.
\verb"addmulrow()" adds a multiple of \verb"row2" to \verb"row1".
The cases \verb"f==F_ZERO" and \verb"f==F_ONE" are treated
specially: In the first case the function returns immediately,
and in the second case \verb"zaddrow()" is executed instead.

\verb"zmaprow()" multiplies the vector \verb"row" from the right by
the matrix \verb"mat" and stores the result into \verb"result".
\verb"nor" is the number of rows of the matrix which must coincide
with the size (number of columns) of the vector. The number of
columns in both \verb"mat" and \verb"result" is determined by the
current row size.
{\em Note:} \verb"result" must be different from \verb"row", but this
is not checked. For example, \verb"zmaprow(x,m,nrows,x)", produces no
error but the result is probably incorrect.

\verb"zpermrow" multiplies the vector \verb"row" from the right with
the permutation \verb"perm" and stores the result into \verb"result".
Multiplication of vectors by permutations is defined as follows:
If the permutation maps point $i$ to point $k$, then the $i$-ith
mark of the vector is stored in the $k$-th position of the
result.
{\em Note:} \verb"result" must be different from \verb"row", although
this is not checked.
For example, \verb"zpermrow(x,p,x)" does not produce an error
message, but the result is incorrect.



\subsection{Data conversion}\label{sec:convert}
%---------------------------
\index{data conversion}
\index{zftoi@{\tt zftoi()}}
\index{zitof@{\tt zitof()}}
\index{zftogap@{\tt zftogap()}}

The functions described in this section provide support for
external (non-{\MeatAxe}) data formats.
Currently there are two external data formats supported,
Integers and GAP format. GAP format is yet incomplete,
because you can convert from internal format to GAP format,
but not vice versa.


\Synopsis
\begin{verbatim}
long zftoi(FEL f);
FEL zitof(long i);
char *zftogap(FEL f);
\end{verbatim}
\EndSynopsis


\Description
\verb"zftoi()" converts a field element to an integer,
\verb"zitof()" converts an integer to a field element.
These two functions use a `canonical' respresentation of
field elements as integers which is different from the
internal representation. They should be used whenever field
elements are {\tt printf}'ed or \verb"scanf"'ed (For an example,
see the ZCV/ZPR pair of programs).  The integer assigned to the
field element ${\it f}$ is obtained by inserting
the characteristic $p$ into the polynomial which represents
$f$. As a consequence, the prime field GF$(p)$ is mapped onto
integer numbers $0$,\ldots,$p-1$.


\verb"zftogap()" takes a field element and returns the GAP
representation of this element. The return value is a pointer
to a static buffer which is overwritten on each call.



\subsection{Seed vector generator}
%---------------------------------
\index{seed vector generator}
\index{zpseed_vec@{\tt zpseed\_vec}}
\index{zpseed_init()@{\tt zpseed\_init()}}
\index{zpseed_make@{\tt zpseed\_make()}}
\index{zpseed_next()@{\tt zpseed\_next()}}


\Synopsis
\begin{verbatim}
PTR zpseed_vec;

int zpseed_init(PTR sbasis, long sdim);
long zpseed_make(long number);
zpseed_next();
\end{verbatim}
\EndSynopsis

\Description
The seed vector generator takes a basis and calculates
one representant of each one-dimensional subspace of the
space spanned by the basis vectors. Once a basis is fixed,
each seed vector has a unique number which is assigned as
follows: Let $b_1$,\ldots,$b_n$ be the basis and
$v=\lambda_1b_1+\ldots\lambda_nb_n$ a vector in the span.
The coefficients $\lambda_i\in\GF(q)$ are identified with
positive integers in the usual way and
\[
 N(v):=\lambda_1+\lambda_2q+\lambda_3q^2+\ldots\lambda_nq^{n-1}
\]
is the `number of $v$'. To avoid scalar multiples, the
leading coefficient is always one.

To use the seed vector generator you must first call
\verb"zpseed_init()".  \verb"sbasis" is the basis of the
seed space (i.e., a matrix) and \verb"sdim" specifies the
number of basis vectors. Remember that the row size must
be set before with \verb"zsetlen()".
\verb"sbasis" may be any basis, not necessarily in semi-echelon form.
It is not checked that the basis vectors are linearly independent. If
they are not, you will get seed vectors which are multiples of each
other or different number will produce the same vector.
There is no internal buffer for the basis. \verb"zpseed_init()" just
saves a pointer to the basis for internal use. For this reason,
you must not modify the basis after initialization.

Then, use \verb"zpseed_make()" to make a specific seed vector
or \verb"zpseed_next()" to get the next seed vector.
Multiple calls of \verb"zpseed_next()" will step through all seed
vectors.
Both functions store the seed vector in \verb"zpseed_vec" and return
its number. A return value of -1 indicates an error.
\verb"zpseed_make()" will not reject a number which corresponds to
a non-normalized seed vector.
If you call \verb"zpseed_make(N)", \verb"zpseed_next()" will continue
with the next normalized seed vector.



\subsection{File i/o}
%--------------------
\index{file i/o}
\index{zreadhdr@{\tt zreadhdr()}}
\index{zwritehdr@{\tt zwritehdr()}}
\index{zreadlong@{\tt zreadlong()}}
\index{zwritelong@{\tt zwritelong()}}
\index{zreadvec@{\tt zreadvec()}}
\index{zwritevec@{\tt zwritevec()}}
\index{zseek@{\tt zseek()}}


\Synopsis
\begin{verbatim}
FILE *zreadhdr(char *name,long *field,long *nrows,long *ncols);
FILE *zwritehdr(char *name,long field,long nrows,long ncols);
size_t zreadlong(FILE *f,long *buf,size_t n);
size_t zwritelong(FILE *f,long *buf,size_t n);
size_t zreadvec(FILE *f, PTR buf, size_t n);
size_t zwritevec(FILE *f, PTR buf, size_t n);
int zseek(FILE *f, long pos);
\end{verbatim}
\EndSynopsis

\Description
These functions are used for input/output operations on streams.
Before you can read from or write to a stream, it must be opened.
There are three functions which open a file: \verb"os_fopen()",
\verb"zreadhdr()", and \verb"zwritehdr()". \verb"os_fopen()" is
described in section \ref{sec:os}.

\verb"zreadhdr()" opens a data file for input and reads the file header.
The header is always 3 long integers which are stored in
into \verb"fl", \verb"nor" and \verb"noc". The exact meaning of these
three numbers depends on the file type. For a matrix they are
`field order', `number of rows' and `number of columns'.
\verb"zwritehdr()" opens a file for output and writes the file
header. If the file already exists, its contents are destroyed.
Unlike \verb"zopen()", these functions do {\em not} search in the
library directory if a file cannot be found.

\verb"zreadlong()" reads \verb"n" long integers from the file \verb"f"
into the array \verb"buf". \verb"zwritelong()" writes \verb"n"
integers from the array \verb"buf" to the file \verb"f". In both cases,
\verb"buf" must point to a memory area of at least
\verb"n*sizeof(long)" bytes and \verb"f" must be an open
file with the correct read/write mode. These functions read and
write long integers in a machine-independent way. Externally, each
number is stored as
a 4-byte integer with the least significant byte first and the most
significant byte last. Using these functions instead of \verb"fread()"
and \verb"fwrite()" makes your data files more portable between
different machines.
Both functions return the number of integers (not bytes)
successfully read/written. A return different from \verb"n" indicates
an error.
There are two restrictions when using these functions:
\begin{enumerate}
\item 
    The conversion to and from machine-independent involves several
    arithmetic operations for each number read/written. These functions
    are therefore much slower than \verb"fread()" or \verb"fwrite()".
\item
    The highest number which can be read/written is $2^{32}-1$, even
    if your machine's long integers are 64 bit wide.
\end{enumerate}

\verb"zreadvec()" and \verb"zwritevec()" are analogous to
\verb"zreadlong()/zwritelong()" but they work with packed vectors
or permutations. Here, $n$ ist the number of rows to read/write.
The row size must be set before with \verb"zsetlen()". 
The file format for permutations is machine-dependent.

\verb"zseek()" sets the read/write pointer of file \verb"f"
to position \verb"pos". I.e., the next read/write will access
the row number \verb"pos" (counting from 1). Use of \verb"zseek()"
is preferable to \verb"fseek()" because \verb"zseek()"
knows about {\MeatAxe} file headers and adjusts the file pointer
appropriately. If \verb"pos" is different from 1, the row size must
have been set before with \verb"zsetlen()". The return value is
0 on success or -1 on error.



\subsection{Gaussian elimination and related functions}
%------------------------------------------------------
\index{gaussian elimination}
\index{zmkpivot@{\tt zmkpivot()}}
\index{zcleanrow@{\tt zcleanrow()}}
\index{zcleanrow2@{\tt zcleanrow2()}}
\index{zmkechelon@{\tt zmkechelon()}}
\index{znullsp@{\tt znullsp()}}

The functions described in this section all perform Gaussian
elimination on matrices. They use low-level row operations to
add multiples of one row to another and swap rows. To keep track
of the pivot elements, i.e., the first non-zero entries in each
row, all functions use an array of (long) integers. The user must
supply this array via the \verb"piv" argument.

{\em Note:} The pivot element of the first row is stored in
\verb"piv[1]" instead of \verb"piv[0]". Thus the size of the pivot
table must always be $n+1$, wehere $n$ is the number of rows.
A matrix is said to be in
\begin{itemize}
\item {\em semi-echelon form} if each row contains a first
      nonzero element (pivot element), and all entries below
      this element are zero.
\item {\em normalized semi-echelon form} if it is in semi-echelon form
      and each pivot element is equal to 1.
\end{itemize}
In the {\MeatAxe}, matrices are often stored in semi-echelon form.
Many functions and programs expect their arguments to be in
semi-echelon form.

\Synopsis
\begin{verbatim}
int zmkpivot(PTR matrix, long nor, long *piv);
int zcleanrow(PTR row, PTR matrix, long nor, long *piv);
int zcleanrow2(PTR row,PTR matrix,long nor,long *piv,PTR row2);
int zmkechelon(PTR matrix, long nor, long *piv);
long znullsp(PTR matrix, long nor, long *piv, PTR nsp);
\end{verbatim}
\EndSynopsis

\Description
\verb"zmkpivot()" is used to find the pivot elements of a matrix
which is already in semi-echelon form. \verb"nor" is the number
of rows in \verb"matrix". The number of columns must have been set
previously with \verb"zsetlen()". \verb"piv" must be a pointer to an
array of at least \verb"nor+1" long integers. The pivot positions
are stored here, beginning with \verb"piv[1]" for the first row.
The return value is $0$ on success. If the matrix is not in
semi-echelon form, \verb"zerrno" is set to \verb"ERR_NOTECH" and
the function returns $-1$.

\verb"zcleanrow()" `cleans' a row with a matrix, i.e., it adds
suitable multiples of the rows of \verb"matrix" to \verb"row"
such that all pivot positions in \verb"row" are zero.
\verb"nor" is the number of rows in \verb"matrix". The number of
columns (for \verb"matrix" and \verb"row") must have been set
previously with \verb"zsetlen()". \verb"piv" is a pointer to the pivot
table of \verb"matrix". It can be generated with \verb"zmkpivot()".
The return value is always 0.

\verb"zcleanrow2()" acts exactly as \verb"zcleanrow()". In addition,
it stores the operations performed in \verb"row2".
\verb"row2" must be a row of at least \verb"nor" entries. It must
be initialized to zero by the caller, or the results are not defined.
On return, \verb"row2" contains the coefficients by which the rows
of \verb"matrix" were multiplied and then subtractes from \verb"row".
The return value is always 0.

\verb"zmkechelon()" converts a matrix to semi-echelon form and
builds a pivot table ready for use with \verb"zcleanrow()"..
\verb"matrix" is a matrix of \verb"nor" rows. The number of columns
must have been set with \verb"zsetlen()". \verb"piv" must be a pointer
to an array of at least \verb"nor+1" long integers.
On return, \verb"matrix" is in semi-echelon form. Zero rows are moved
to the end, and the number of non-zero rows (i.e., the rank) is
stored in \verb"piv[0]". The rest of the \verb"piv" array contains the
pivot table, beginning with \verb"piv[1]" for the first row.
The return value is the rank.


\verb"znullsp()" calculates the null-space of a matrix. The matrix
is passed as first argument (\verb"mat"), \verb"nor" is the number
of rows of the matrix, \verb"piv" must be a pointer to at least
\verb"nor+1" integers, and \verb"nsp" must be a pointer to a
matrix of dimension $\verb"nor"\times\verb"nor"$. On return, the
matrix is in semi-echelon form, its rank is stored in \verb"piv[0]",
but zero rows are {\em not} moved to the end. The rows of \verb"nsp"
with \verb"piv[i]==0" constitute a basis of the null-space in
semi-echelon form. The return value is the dimension of the null-space.


\subsection{Projection on the quotient}
%--------------------------------------
\index{quotient spaces}
\index{zquotinit@{\tt zquotinit()}}
\index{zquot@{\tt zquot()}}
\index{zquotop@{\tt zquotop()}}

\Synopsis
\begin{verbatim}
int zquotinit(PTR subspace, long dim, long *piv);
PTR zquot(PTR space, long dim);
PTR zquotop(PTR matrix);
\end{verbatim}
\EndSynopsis

\Description
Given any subspace (i.e., a matrix) these functions let you
project vectors onto the quotient by this subspace. The projection
is not 'canonical' but depends on the basis for the subspace.
Let $V=F^{n\times n}$ and $u_1,\ldots,u_s$ be a basis for the subspace
$U\leq V$. The basis, written as a matrix of row vectors, is assumed
to be in semi-echelon form. By looking at the pivot columns we can
define a `standard' basis $w_1,\ldots,w_q$ (with $s+q=n$) for the
quotient $V/U$ by taking all vectors with have a exactly one 1 at any
non-pivot position and are zero otherwise. The set $(u_1,\ldots,u_s,
w_1,\ldots,w_q)$ is a basis for $V$ and defines the decomposition
of any vector into subspace and quotient part.

\verb"zquotinit()" must be called first to initialize the pivot
table. \verb"subspace" must be a matrix in semi-echelon form,
and \verb"dim" is the number of rows of that matrix. Using the
notation from above, we have $n=$ current number of columns and
$s=\verb"dim"$. If a pivot
table for the matrix has already been built, it may be passed
as \verb"piv". A value of \verb"NULL" indicates that the table
should be built by \verb"zquotinit()". The return value is 0 on
success or -1 on error. Possible error codes (stored in
\verb"mtxerrno") are \verb"ERR_NOTECH" (matrix not in echelon
form) and \verb"ERR_NOMEM" (not enough memory).

\verb"zquot()" projects a vector or a whole subspace on the quotient.
\verb"space" must be a matrix with $n$ columns, and \verb"dim" is the
number of rows. The return value is a pointer to a matrix with
"\verb"dim" rows and $q$ columns containing the projections of the
input vectors.

\verb"zquotop()" calculates the action of a square matrix on the
quotient. Of course, this makes sense only if the subspace is invariant
under the matrix. However, this is not checked --- if the subspace is
not invariant, the results are undefined. The only parameter,
\verb"matrix", must be a pointer to a square matrix with the
same number of columns as the subspace. The return value is a pointer
to a square matrix operating on the qutient, or \verb"NULL" on error.



\subsection{Spin-up, split, and standard basis}
%----------------------------------------------
\index{spin up}
\index{splitting a module}

The functions in this section take a set of seed vectors and
calculate the closure of the vectors under a given set of
generators (matrices or permutations). The closure is the
smallest subspaces containing all seed vectors and being
invariant under the generators. If the closure is a proper
subspace, the action of the generators on both subspace and
quotient can be calculated. This is called splitting the module.


%- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\index{zspinup@{\tt zspinup()}}
\Synopsis
\begin{verbatim}
long zspinup(PTR space, long nseed, long *piv, PTR gen[],
  int ngen, int gentype);
\end{verbatim}
\EndSynopsis

\Description
This is a low-level function
which allocates no memory. \verb"space" must be a square matrix
of the current row size, and the seed vectors must be stored in the
first \verb"nseed" rows of the matrix. The seed vectors need not
be in echelon form. \verb"piv" must be a pointer
to an array of at least $n+1$ long integers, where $n$ is the size
of the matrix. This table need not be initialized. \verb"gen" is
an array of pointers to the generators which can be either
matrices or permutations. \verb"ngen" is the number of generators,
and \verb"gentype" must be either \verb"T_MATRIX" or \verb"T_PERM",
indicating the type of generators.

The return value is the dimension of the invariant subspace. On
return, a basis of the closure is stored in \verb"space", and
\verb"piv" contains a pivot table for this basis. A return value
of $-1$ indicates an error.


%- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\index{matspin@{\tt matspin()}}
\index{matspin_f@{\tt matspin\_f()}}
\Synopsis
\begin{verbatim}
matrix_t *matspin(matrix_t *seed, int ngen, matrix_t *gen[]);
matrix_t *matspin_f(matrix_t *seed, int ngen, matrix_t *gen[], 
  long *sdim);
\end{verbatim}
\EndSynopsis

\Description
These are high-level function wich operate on \verb"matrix_t"
objects.
\verb"matspin()" calculates the closure of a set of seed vectors
(\verb"seed") under \verb"ngen" matrices. \verb"matspin_f()"
does the same job, but the result is filled out with extra rows to 
make a non-singular square matrix. The dimension of the closure
is stored in \verb"sdim".

%- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\index{sbasis@{\tt sbasis()}}
\Synopsis
\begin{verbatim}
matrix_t *sbasis(matrix_t *seed, int ngen, matrix_t *gen[]);
\end{verbatim}
\EndSynopsis

\Description
This function takes one seed vector and spins it up 'canonically'.
The result, usually a basis for the whole space, consists of images
of the seed vector under products of the generators. It is not in
semi-echelon form. See the description of the ZSB program for more
details. 

Note: While the operation of this function is quite
similar to \verb"matspin()", it takes the double amount of menory.


%- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\index{split_t@{\tt split\_t}}
\index{split()@{\tt split()}}
\index{splfree()@{\tt splfree()}}
\Synopsis
\begin{verbatim}
typedef struct
{   int result;              /* 0 = not split, 1 = split */
    matrix_t *sub[MAXGEN];   /* Subspace */
    matrix_t *quot[MAXGEN];  /* Quotient */
    matrix_t *proj;
} split_t;

split_t *split(matrix_t *seed, int ngen, matrix_t *gen[], int tr);
void splfree _PL(split_t *s);
\end{verbatim}
\EndSynopsis

\Description
This function tries to split the module, given by \verb"ngen"
generators in \verb"gen", using seed vectors from a seed space.
\verb"seed" is the basis of the seed space. For each seed vector,
i.e., for a representative of each one dimensional subspace of
the seed space, the function calculates its closure under the
generators. This procedure stops if either a seed vector generates
a proper subspace or if there are no more seed vectors.

The function returns a pointer to a \verb"split_t" structure
containing the result of the split. \verb"result" is a flag
indicating if a proper submodule was found. If yes, \verb"sub"
and \verb"quot" contain the action of the generators on the
subspace and quotient, respectively, and \verb"proj" contains
the projection of the seed space on the quotient. The latter
may be used in further split attempts of the quotient.
   
What has been said above applies to the case \verb"tr=0". If
\verb"tr=1",
the functin operates in so-called `dual mode'. In this mode,
only one seed vector is examined, and the fields of the result
structure are not used except \verb"result". 

On each call to \verb"split()" a new \verb"split_t" structure
is allocated. \verb"splfree()" may be used to free such a
structure.



\subsection{Bit Strings}\label{sec:bitstrings}
%-----------------------
\index{bit strings}
The \verb"bitstring_t" type represents a string of 0's and 1'. You
may also think of it as a subset of $\{1,2,\ldots,N\}$, where
each 1 in the bit string means that the subset contains the
corresponding element.
Unlike the \verb"set_t" type (see section \ref{sec:sets}) bit
strings are static objects which cannot change size.

\index{bs_setlen@{\tt bs\_setlen()}}
\index{bs_alloc@{\tt bs\_alloc()}}
\index{bs_free@{\tt bs\_free()}}
\index{bs_read@{\tt bs\_read()}}
\index{bs_write@{\tt bs\_write()}}
\Synopsis
\begin{verbatim}
typedef struct { ... } bitstring_t;

void bs_setlen(int l);
bitstring_t *bs_alloc(void);
void bs_free(bitstring_t *b);
bitstring_t *bs_read(FILE *f);
void bs_write(FILE *f, bitstring_t *b);
\end{verbatim}
\EndSynopsis

\Description
\verb"bs_setlen()" sets the bit string length for subsequent
allocations and other bit string operations.
\verb"bs_alloc()" allocates a bit string and returns a pointer
to the new bit string, or \verb"NULL" on error occurs. The new
bit string is initially filled with zeroes.
\verb"bs_free()" frees a bit string.

\verb"bs_read()" reads a bit string from a file. \verb"bs_write()"
writes a bit string to a file. Before using these functions you
must set the bit string size with \verb"bs_setlen()".



\index{bs_reset@{\tt bs\_reset()}}
\index{bs_set@{\tt bs\_set()}}
\index{bs_clear@{\tt bs\_clear()}}
\index{bs_test@{\tt bs\_test()}}
\Synopsis
\begin{verbatim}
void bs_reset(bitstring_t *x);
void bs_set(bitstring_t *b, int i);
void bs_clear(bitstring_t *b, int i);
int bs_test(bitstring_t *b, int i);
\end{verbatim}
\EndSynopsis

\Description
\verb"bs_reset()" sets all positions of the bitstring \verb"x" to
zero. Note that this is {\em not} done automatically by \verb"bs_alloc()".
\verb"bs_set" sets bit number \verb"i" of the bit string \verb"b"
to 1. There is no check if \verb"i" is inside the bounds.
\verb"bs_clear" clears bit number \verb"i" of the bit string \verb"b".
\verb"bs_test" tests bit number \verb"i" of the bit string \verb"b".
The return value is 0 (bit cleared) or 1 (bit set).




\index{bs_cmp@{\tt bs\_cmp()}}
\index{bs_cpy@{\tt bs\_cpy()}}
\index{bs_and@{\tt bs\_and()}}
\index{bs_or@{\tt bs\_or()}}
\index{bs_minus@{\tt bs\_minus()}}
\index{bs_match@{\tt bs\_match()}}
\index{bs_issub@{\tt bs\_issub()}}
\Synopsis
\begin{verbatim}
int bs_cmp(bitstring_t *a, bitstring_t *b);
void bs_cpy(bitstring_t *a, bitstring_t *b);
void bs_and(bitstring_t *dest, bitstring_t *src);
void bs_or(bitstring_t *dest, bitstring_t *src);
void bs_minus(bitstring_t *dest, bitstring_t *src);
int bs_match(bitstring_t *x, bitstring_t *y);
int bs_issub(bitstring_t *a, bitstring_t *b);
\end{verbatim}
\EndSynopsis

\Description
\verb"bs_cmp()" compares two bit strings. The return value is 0 if
the two strings are equal and different from 0 otherwise.
\verb"a" and \verb"b" must be bit strings of equal length, or the
result is undefined.
\verb"bs_cpy()" copies the bit string \verb"src" to \verb"dest".
Both \verb"src" and \verb"dest" must be bit strings of equal
length.

\verb"bs_and()" computes the logical `and' of two bit strings.
\verb"bs_or()" computes the logical `or' of two bit strings.
\verb"bs_minus()" computes the (set theoretical) difference of two
bit strings, i.e., each bit in the result is set if and only if
it is set in \verb"dest" and cleared in \verb"src". All these functions
require \verb"src" and \verb"dest" to have equal size and store the
result in \verb"dest".

\verb"bs_match()" compares two bit strings of equal size looking for
bits which are set in both strings. The return value is 0 if there
are no matching bits, 1 if there is exactly one matching bit, and
2 if there are 2 or more matching bits.

\verb"bs_issub()" compares two bit strings and checks if \verb"a",
interpreted as a set, is a subset of \verb"b". The return value is
1 for yes (i.e., every bit which is set in \verb"x" is also set in
\verb"x") or 0 for no.



\subsection{Matrices}\label{sec:matrix}
%--------------------
\index{matrices}
\index{matrix operations}

\index{matrix_t@{\tt matrix\_t}}
\index{matalloc@{\tt matalloc()}}
\index{matid@{\tt matid()}}
\index{matfree@{\tt matfree()}}
\index{matdup@{\tt matdup()}}
\index{matmove@{\tt matmove()}}
\index{matextract@{\tt matextract()}}
\Synopsis
\begin{verbatim}
typedef struct { long fl, nor, noc; PTR d; } matrix_t;

matrix_t *matalloc(long fl, long nor, long noc);
void matfree(matrix_t *m);
matrix_t *matid(long fl, long nor);
matrix_t *matdup(matrix_t *src);
int  matmove(matrix_t *dest, matrix_t *src);
matrix_t *matextract(matrix_t *src, long first, long last);
\end{verbatim}
\EndSynopsis

\Description
Matrices are represented by the type \verb"matrix_t". \verb"fl",
\verb"nor" and \verb"fl" are the field, the number of rows and the
number of columns, respectively.

\verb"matalloc" creates a new matrix with \verb"nor" rows and
\verb"noc" columns over the field
GF(\verb"fl"). The return value is a pointer to the allocated
\verb"matrix_t" structure, or \verb"NULL" if there is not enough
memory. In the latter case, \verb"mtxerrno" is set to \verb"ERR_NOMEM".
\verb"matfree()" de-allocates a matrix which was allocated previously
with \verb"matalloc()". It frees the data area as well as the
\verb"matrix_t" structure itself. Thus, you must not use
\verb"matfree()" on variables of type \verb"matrix_t".
Indeed, you should never declare variables of type \verb"matrix_t"
but only pointers to \verb"matrix_t".

\verb"matid()" returns the identity matrix with \verb"nor" rows over
GF(\verb"fl"). A return value of \verb"NULL" indicates an error, and an
error code is stored in \verb"mtxerrno". Note that on each call to
\verb"matid()" a new matrix is allocated.

\verb"matdup()" duplicates a given matrix and returns the copy.
\verb"matmove()" copies a matrix from \verb"src" to \verb"dest".
\verb"matextract()" extracts rows \verb"first"--\verb"last" from
the matrix \verb"mat".
All these functions return \verb"NULL" if there is not enough memory.



%- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
\index{matread@{\tt matread()}}
\index{matwrite@{\tt matwrite()}}
\index{matload@{\tt matload()}}
\index{matsave@{\tt matsave()}}
\Synopsis
\begin{verbatim}
matrix_t *matread(FILE *f);
int matwrite(FILE *f, char *fn);
matrix_t *matload(char *fn);
int matsave(matrix_t *mat, char *fn);
\end{verbatim}
\EndSynopsis

\Description
There are four functions for reading and writing matrices:
\verb"matload()" opens a file given by its name, reads a single
matrix from this file and closes the file. This function
returns a pointer to the matrix or \verb"NULL" on error.
\verb"matread()" works similarly, but it takes a pointer to an
open file as argument, leaving all open/close operations to the
caller.  \verb"matsave()" and \verb"matwrite()" write a matrix
to a file. The return value is 0 on success or -1 on error.


%- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
\index{matrix inversion}
\index{matadd@{\tt matadd()}}
\index{matmul@{\tt matmul()}}
\index{mattr@{\tt mattr()}}
\index{matinv@{\tt matinv()}}
\index{matpower@{\tt matpower()}}
\index{zmatinv@{\tt zmatinv()}}
\Synopsis
\begin{verbatim}
matrix_t *matadd(matrix_t *dest, matrix_t *src);
matrix_t *matmul(matrix_t *dest, matrix_t *src);
matrix_t *mattr(matrix_t *src);
matrix_t *matinv(matrix_t *src);
matrix_t *matpower(matrix_t *mat, long n);
int zmatinv(PTR mat, PTR result);
\end{verbatim}
\EndSynopsis

\Description
\verb"matadd()" adds \verb"src" to \verb"dest". The matrices must be
over the same field and have the same size. \verb"matmul()" multiplies
\verb"dest" from the right with \verb"src". The matrices must be
compatible.  \verb"mattr()" calculates and returns the transpose of a
matrix.

\verb"matinv()" calculates and returns the inverse of a matrix. The
matrix must be non-singular, or otherwise the return value is
\verb"NULL".
\verb"matpower()" raises the matrix \verb"mat" the the \verb"n"-th
power.

\verb"zmatinv()" is a low-level, destructive matrix inversion.
Unlike \verb"matinv()", this function does not allocate a temporary
matrix.
Both \verb"mat" and \verb"result" must be square matrices, and
the row size must be set by the caller. \verb"result" need not
be initialized. A return value of 0 indicates success. In this
case, \verb"result" contains the inverse matrix. If the matrix is
singular, the function returns -1 and sets \verb"mtxerrno" to
\verb"ERR_DIV0". In any case the original matrix is destroyed.


%- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
\index{nullity@{\tt nullity()}}
\index{nullsp@{\tt nullsp()}}
\index{echelon@{\tt echelon()}}
\index{chkechelon@{\tt chkechelon()}}
\Synopsis
\begin{verbatim}
long nullity(matrix_t *mat);
matrix_t *nullsp(matrix_t *mat);
matrix_t *echelon(matrix_t *src);
int chkechelon(matrix_t *mat);
\end{verbatim}
\EndSynopsis

\Description
\verb"nullity()" calculates the nullity of a matrix. \verb"nullsp()"
returns the null-space (kernel) of a given matrix.  Note that both
function perform a Gaussian elimination on the matrix without
making a working copy. Thus the original matrix is destroyed.

\verb"echelon()" converts a matrix to echelon form by suitable row
operations. This function creates a new matrix and leaves the original
matrix intact. \verb"chkechelon()" checks if a given matrix is in
echelon form. The return value is 0 if the matrix is in echelon form
or 1 else.


%- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
\index{matorder@{\tt matorder()}}
\index{matquot@{\tt matquot()}}
\index{ycompare@{\tt ycompare()}}
\index{matspin@{\tt matspin()}}
\Synopsis
\begin{verbatim}
long matorder(matrix_t *mat);
matrix_t *matquot(matrix_t *subsp, matrix_t *mat);
int ycompare(matrix_t *m1, matrix_t *m2, long n);
matrix_t *matspin(matrix_t *seed, matrix_t *gen[], int ngen);
\end{verbatim}
\EndSynopsis


\Description
\verb"matorder()" calculates and returns the order of a matrix.
If the matrix is singular or not square, the order is not defined
and the function returns -1. This may also happen if the order is
very large or if the matrix has an order $> 1000$ on some cyclic
subspace.

\verb"matquot()" projects a matrix, \verb"mat", onto the quotient
by the space \verb"subsp".
\verb"ycompare()" compares two spaces, given by bases \verb"m1"
and \verb"m2". It is assumed that the first \verb"n" basis
vectors are a generating set, under some algebra, for the subspace.

\verb"matspin()" spins up \verb"seed" under the action of a set
of matrices. \verb"seed" may be any linearly independent set of
vectors. \verb"gen" is the set of matrices, and \verb"ngen" is the
number of matrices in \verb"gen".



\subsection{Permutations}\label{sec:perms}
%------------------------
\index{permutations}
\index{perm_t@{\tt perm\_t}}
\index{permalloc@{\tt permalloc()}}
\index{permfree@{\tt permfree()}}
\index{permdup@{\tt permdup()}}
\index{permmove@{\tt permmove()}}
\index{permread@{\tt permread()}}
\index{permwrite@{\tt permwrite()}}
\index{permload@{\tt permload()}}
\index{permsave@{\tt permsave()}}
\index{permmul@{\tt permmul()}}
\index{permorder@{\tt permorder()}}
\index{permpower@{\tt permpower()}}
\Synopsis
\begin{verbatim}
typedef struct { long deg; PTR d; } perm_t;

perm_t *permalloc(long deg);
void permfree(perm_t *m);
perm_t *permdup(perm_t *src);
perm_t *permmove(perm_t *dest, perm_t *src);
perm_t *permread(FILE *f);
int permwrite(FILE *f, perm_t *perm);
perm_t *permload(char *fn);
int permsave(perm_t *perm, char *fn);
perm_t *permmul(perm_t *dest, perm_t *src);
long permorder(perm_t *perm);
perm_t *permpower(perm_t *p, long n);
\end{verbatim}
\EndSynopsis

\Description
The \verb"perm_t" data type represents a permutation. \verb"deg"
is the degree and \verb"d" is a pointer to the permutation proper,
which is stored internally as an array of long integers. You should
never declare static variables of type \verb"perm_t". Instead, use
\verb"permalloc()" and \verb"permfree()" and work with pointers 
of type \verb"perm_t *".


\verb"permalloc()" creates a permutation of the specified degree.
The functions returns a pointer to the new permutation or \verb"NULL"
on error (\verb"mtxerrno=ERR_NOMEM").
\verb"permfree()" deletes a permutation and returns the memory to
the system. Do not use \verb"free()" on permutations because this
would only free the \verb"perm_t" structure but not the data buffer.

\verb"permdup()" creates a copy of an existing permutation. If
there is not enough memory for the copy, the return value is
\verb"NULL". \verb"permmove()" copies a permutation from \verb"src"
to \verb"dest".

There are four functions for reading and writing permutations:
\verb"permload()" opens a file given by its name, reads a single
permutation from this file and closes the file. This function
returns a pointer to the permutation or \verb"NULL" on error.
\verb"permread()" works similarly, but it takes a pointer to an
open file as argument, leaving all open/close operations to the
caller.  \verb"permsave()" and \verb"permwrite()" write a permutation
to a file. The return value is 0 on success or -1 on error.

\verb"permmul()" multiplies \verb"dest" from the right with
\verb"src" and stores the result in \verb"dest".

\verb"permorder()" calculates and returns the order of a permutation.

\verb"permpower()" calculates the n-th power of a permutation.


\subsection{Sets}\label{sec:sets}
%----------------
\index{sets}
\index{set_t@{\tt set\_t}}
\index{set_allocstrategy@{\tt set\_allocstrategy()}}
\index{set_alloc@{\tt set\_alloc()}}
\index{set_insert@{\tt set\_insert()}}
\index{set_contains@{\tt set\_contains()}}
\index{set_read@{\tt set\_read()}}
\index{set_write@{\tt set\_write()}}

\Synopsis
\begin{verbatim}
typedef struct { size_t len, max; long *buf; } set_t;

int set_allocstrategy(size_t first,size_t blocksize);
set_t *set_alloc(void);
void set_free(set_t *x);
int set_insert(set_t *set, long elem);
int set_contains(set_t *set, long elem);
set_t *set_read(FILE *f);
int set_write(FILE *f, set_t *set);
\end{verbatim}
\EndSynopsis

\Description
The type \verb"set_t" represents a set of (long) integers.
Internally, the set is stored as a sorted list. \verb"set_t"
should be used if the number of elements in the set is typically
much less than the elements themselves.
In other cases, when the number of elements is comparable to the
elements themselves, the \verb"bitstring_t" type (see section
\ref{sec:bitstrings}) may be more suitable.


\verb"set_allocstrategy()"  controls the memory allocation for
sets. In order to avoid \verb"malloc()" calls each time
an element is added to a set, memory is allocated in blocks.
When created by \verb"set_alloc()", a set has an initial size
up to which is can grow without further memory requests. The
initial size is set via the \verb"first" argument.
If the set has grown to its maximal size, adding a new element
causes the size to be incremented by a fixed value --- the block
size, and new memory is allocated with. The block
size is set via the \verb"blocksize" argument. It must also be
greater than 0.
The return value is 0 on success and -1 on error. An error means
that one of the arguments was zero or negative. In this case,
\verb"mtxerrno" is set to \verb"ERR_RANGE".

\verb"set_alloc()" allocates a new set and returns a pointer to
the allocated set. If there is not enough memory available,
\verb"mtxerrno" is set to \verb"ERR_NOMEM", and the function returns
\verb"NULL".

\verb"set_free()" frees an integer set. The argument must be a
\verb"set_t" structure which has previouly been allocated with
\verb"set_alloc()". Note that \verb"set_free()" expects a pointer
as its argument. Do not use \verb"set_free()" on variables of type
\verb"set_t"!

\verb"set_insert()" inserts an element into a set. The return value is
$0$ on success or $-1$ on error. In the latter case, \verb"mtxerrno" is
set to \verb"ERR_NOMEM", indicating that there is not enough memory.
\verb"set_contains()" checks if a given set contains a specific
element.  The return value is 0 for `no' and 1 for `yes'.

\verb"set_read()" reads a set from a file. It returns a pointer
to a \verb"set_t" structure which contains the set. On error, the
return value is \verb"NULL", and \verb"mtxerrno" is set to
\verb"ERR_NOMEM" (not enough memory) or \verb"ERR_FILEREAD" (error
reading file).
\verb"set_write()" writes a set to a file. The return value is
$0$ on success or $-1$ on error. In the latter case,
\verb"mtxerrno" is set to \verb"ERR_FILEWRITE".



\subsection{Polynomials}\label{sec:poly}
%-----------------------
\index{polynomials}

\subsubsection{General}
%----------------------
\index{poly_t@{\tt poly\_t}}
\index{polalloc@{\tt polalloc()}}
\index{polfree@{\tt polfree()}}
\index{poldup@{\tt poldup()}}
\index{polcmp@{\tt polcmp()}}
\Synopsis
\begin{verbatim}
typedef struct { long fl; long deg; size_t size; FEL *buf; } poly_t;

poly_t *polalloc(long fl, long degree);
void polfree(poly_t *x);
poly_t *poldup(poly_t *x);
int polcmp(poly_t *a, poly_t *b);
\end{verbatim}
\EndSynopsis

\Description
Poynomials are represented by the \verb"poly_t" structure. This
structure has four fields: \verb"fl" is the finite field, \verb"deg"
is the degree,
\verb"buf" is a pointer to an array of field elements --- the
coefficients --- and \verb"size" is the size of this array. The
\verb"size" field is used for internal puposes. You should never
modify this value directly.
The coefficients are stored in \verb"buf" as an (unpacked) array of
field elements in increasing order. Thus, \verb"buf[0]" is the
coefficient of $x^0$, and \verb"buf[deg]" is the leading coefficient.
Poynomials are always normalized, i.e., the leading coefficient is
non-zero. The zero polynomial is a special case, it is represented by
\verb"deg=-1".

Besides reading from a file (see below), there are two ways
to create new polynomials: \verb"polalloc()" returns the polynomial
$x^n$, with $n=\verb"degree"$, over GF(\verb"fl"). \verb"poldup()"
makes a copy of an existing polynomial and returns a pointer to the
copy. All functions return \verb"NULL" on error.

\verb"polfree()" frees a polynomial. You cannot use \verb"free()"
with polynomials, because the standard \verb"free()" function does
not know about \verb"poly_t"'s internal structure.

\verb"polcmp()" compares two polynomials. The return value is 0
if the polynomials are equal, $-1$ if $a<b$, or $1$ if $a>b$.
The order of polynomials is defined as follows: If $a$ and $b$
are over different fields, the polynomials over the larger field
is greater. Otherwise, if they have different degrees, the polynomial
with the larger degreee is greater. If both field and degree are
equal, the result of the comparison depends on the internal
representation of the field elements and does not have any 
significance.

\subsubsection{File I/O}
%-----------------------
\index{polread@{\tt polread()}}
\index{polwrite@{\tt polwrite()}}
\index{polprint@{\tt polprint()}}
\Synopsis
\begin{verbatim}
poly_t *polread(FILE *f);
int polwrite(FILE *f, poly_t *p);
void polprint(char *name, poly_t *p);
\end{verbatim}
\EndSynopsis

\Description
\verb"polprint()" prints a polynomial to the standard output.
\verb"polread()" reads a polynomial from a file. The return value is
a pointer to the polynomial or \verb"NULL" on error. \verb"polwrite()"
writes a polynomial to a file and returns 0 on success, or -1 on error.


\subsubsection{Arithmetic}
%-------------------------
\index{poladd@{\tt poladd()}}
\index{polmul@{\tt polmul()}}
\index{poldivmod@{\tt poldivmod()}}
\index{polmod@{\tt polmod()}}
\index{polshiftmod@{\tt polshiftmod()}}
\index{polderive@{\tt polderive()}}
\index{polgcd@{\tt polgcd()}}
\Synopsis
\begin{verbatim}
poly_t *poladd(poly_t *dest, poly_t *src);
poly_t *polmul(poly_t *dest, poly_t *src);
poly_t *poldivmod(poly_t *a, poly_t *b);
poly_t *polmod(poly_t *a, poly_t *b);
poly_t *polshiftmod(poly_t *p, long n, poly_t *q);
poly_t *polderive(poly_t *a);
poly_t *polgcd(poly_t *a, poly_t *b);
\end{verbatim}
\EndSynopsis

\Description
\verb"poladd()" and \verb"polmul()" perform polynomial addition and
multiplication. Both functions store the result in \verb"dest" and
return \verb"dest" as result.

\verb"poldivmod()" performs a polynomial division ($a/b$) and returns
the quotient. The remainder is stored in \verb"a", while \verb"b"
remains unchanged. \verb"polmod()" reduces \verb"a" modulo \verb$b$
and returns \verb$a$.

\verb"polshiftmod()" multiplies $p(x)$ by $x^n$ and reduces the result
modulo $q(x)$. This function is more effective than a combination
of \verb"polmul()" and "verb"polgcd()".

\verb"polderive()" derives a polynomial. The original polynomial is
overwritten, abd the return value is just a copy of \verb"a".

\verb"polgcd()" calculates the greatest common divisor of two
polynomials. Unlike the other arithmetic functions \verb"polgcd()" is
non-destructive, i.e., the polynomials passed as arguments
remain intact.


%- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\subsubsection{Conversion}
%-------------------------
\index{vec2pol@{\tt vec2pol()}}
\index{pol2vec@{\tt pol2vec()}}
\index{polpack@{\tt polpack()}}
\Synopsis
\begin{verbatim}
int vec2pol(PTR vec, poly_t *pol);
int pol2vec(poly_t *pol, PTR vec);
int polpack(poly_t *pol, PTR vec);
\end{verbatim}
\EndSynopsis

\Description
\verb"vec2pol()" and \verb"pol2vec()" convert between polynomials
and packed vectors. These functions are intended for calculations
with characteristic polynomials of matrices. The leading
coefficient is always assumed to be one and not stored in the
vector. Thus, polynomials of degree
$n$ correspond to vectors of length $n$. \verb"pol2vec()" stores
the coefficients of $x^0$
up to $x^{n-1}$ in the row and then divides the row by the leading
coefficient (if it is different from 1). \verb"vec2pol()" reads $n$
coefficients from the row and sets the leading coefficient to 1.

\verb"polpack()" stores the coefficients of a polynomial into a packed
row, starting with the coefficient of $x^0$ at column 1. On return,
the row size has changed to ${\rm degree}(n)+1$.


\subsubsection{Factorization}
%----------------------------
\index{factorization@{\tt factorization()}}
\Synopsis
\begin{verbatim}
typedef struct
{
    poly_t *p;	/* Irreducible factor */
    long n;	/* Multiplicity */
} factor_t;

factor_t *factorization(poly_t *pol);
\end{verbatim}
\EndSynopsis

\Description
\verb"factorization()" takes a polynomial and returns its
decomposition into irreducible factors. The result is a pointer
to an array of \verb"factor_t" structures. Each element of this
array contains an irreducible factor which is stored in \verb"p"
and its multiplicity in \verb"n". The factors are sorted by
ascending degree. The end of the list is marked by an entry with
\verb"p=NULL" and \verb"n=0".

The polynomial passed to \verb"factorization()" is not modified.
On each call, a new \verb"factor_t" array is allocated and
returned to the caller. If the factors are not needed any more,
the caller must free the array as follows:
\begin{verbatim}
    factor_t *factors, *f;
    factors = factorization(mypoly);
    ... 
    for (f = factors; f->n != 0; ++f)    /* Free the irred. factors */ 
        polfree(f->p);
    free(factors);                       /* Free the factors array */
\end{verbatim}



\subsection{Command line parsing}
%--------------------------------
\index{options!command line}
\index{command line parsing}
\index{help texts}
\index{proginfo_t@{\tt proginfo\_t}}
\index{opt_ind@{\tt opt\_ind}}
\index{opt_char@{\tt opt\_char}}
\index{opt_text@{\tt opt\_text}}
\index{opt_text_ptr@{\tt opt\_text\_ptr}}
\index{init_args@{\tt init\_args()}}
\index{zgetopt()@{\tt zgetopt()}}
\index{getint()@{\tt getint()}}

\Synopsis
\begin{verbatim}
typedef struct {
    char *name;
    char *shortdesc;
    char *rcsrev;
    char **helptext;
    } proginfo_t;

#define GETINT_ERR -12345
#define OPT_END -1

extern char opt_char;		/* Current option */
extern char opt_text[50];	/* Option text */
extern char *opt_text_ptr;	/* Current position in option text */
extern int opt_ind;		/* Index in argv[] list */

void initargs(int argc, char **argv, proginfo_t *pi);
int zgetopt(char *pattern);
long getint(void);
\end{verbatim}
\EndSynopsis

\Description
This set of functions provides support for command line parsing
and built-in help texts. The help text is displayed if the program
is called with the single argument \verb"help" or with the option
\verb"-help".

If you want to use these functions, your program must call
\verb"init_args()". This is usually done immediately after startup. 
\verb"init_args()" expects the command line in \verb"argc" and
\verb"argv", and a pointer to a structure containing additional
information. The meaning of the fields in this structure should be
clear from the example below.

\verb"zgetopt()" is very similar to \verb"getopt()". It scans the
command line for options (i.e., arguments beginning with `{\tt -}')
and returns options, one by one, until it reaches the first
non-option argument or the end of the command line.
\verb"pattern" is a list of valid options. Each option consists of
one character, optionally followed by a period indicating that
the option takes an argument.
The options \verb"-Q", \verb"-V" and \verb"-T" are handled
automatically by \verb"zgetopt()". These options need not be
specified in \verb"pattern".

\verb"zgetopt()" returns the option character or the special
value \verb"OPT_END" if there are no more options.
In addition, some global variables are set on return:
\begin{itemize}
\item
    \verb"opt_char" contains the option character.
\item
    \verb"opt_ind" contains the index of the argument to be read
    next. For example, if \verb"zgetopt()" return \verb"OPT_END",
    \verb"opt_ind" is the index of the first non-optional argument.
\item
    \verb"opt_text", an array of characters, contains the argument
    (if present).
\item
    \verb"opt_text_ptr" points to \verb"opt_text[0]".
\end{itemize}

This setting enables \verb"getint()" to access the argument
immediately after \verb"zgetopt()" returns. \verb"getint()"
expects \verb"opt_text_ptr" to point to a string of decimal
digits. It scans this string, returns the integer value,
and increments \verb"opt_text_ptr" to the character after the
last digit. If the argument is not a number in decimal notation
\verb"getint()" returns the value \verb"GETINT_ERR".

Here is an example:
\begin{verbatim}
static char *helptext[] = {
  "SYNTAX",
  "    dummy [-ab] [-x <First>-<Last>] <File> ...",
  "",
  "DESCRIPTION",
  "    This program does nothing.",
  NULL};
static proginfto_t pinfo =
  { "dummy", "Do Nothing", "$Revision 1.16$", helptext };

int main(int argc, char *argv[])
{
    init_args(argc, argv, &pinfo);
    while (zgetopt("abx:") != OPT_END)
    {   switch (opt_char)
        {   
            case 'a': ignore_a(); break;
	    case 'b': ignore_b(); break;
            case 'x':
                first = getint();
                if (*opt_text_ptr++ != '-') error();
                last = getint();
		break;
        }
    }
    ...
}
\end{verbatim}
In this example, the \verb"-x" option takes an argument of the
form {\it first}--{\it last}. After the first \verb"getint()"
\verb"opt_text_ptr" points to the `-' and must be incremented
for the next \verb"getint()" to work.


\subsection{Random numbers}
%--------------------------
\index{random numbers}
\index{rand_init@{\tt rand\_init()}}
\index{rand_next@{\tt rand\_next()}}
\index{rand_int@{\tt rand\_int()}}


\Synopsis
\begin{verbatim}
void rand_init(unsigned seed);
long rand_next(void);
unsigned rand_int(unsigned max);
\end{verbatim}
\EndSynopsis

\Description
These functions can be used to generate a sequence of
(pseudo-)random numbers. The period of this sequence is
very large, approximately $31(2^{31}-1)$.

\verb"rand_init()" initializes the random number generator with
a given `seed'. For each value of \verb"seed" a different sequence
of random numbers is generated. By default, the generator behaves
as if initialized with \verb"rand_init(0)".

\verb"rand_next()" returns the next random number.
\verb"rand_int()" returns a random number $x$ with
$0\leq x \leq$\verb"max".
Actually, \verb"rand_int()" calls \verb"rand_next()" and takes
the result modulo \verb"max". Hence \verb"rand_int(0)" will result
in a run-time error.




\subsection{OS dependent stuff}\label{sec:os}
%-------------------------------------------
The functions described in this section are the interface between
{\MeatAxe} programs and the operating system.


\subsubsection{File I/O}
%-----------------------
\index{os_mkfilename@{\tt os\_mkfilename()}}
\index{os_fopen@{\tt os\_fopen()}}
\index{os_fseek@{\tt os\_fseek()}}


\Synopsis
\begin{verbatim}
#define FM_READ 1
#define FM_CREATE 2
#define FM_APPEND 3
#define FM_TEXT 0x10
#define FM_LIB 0x20

char *os_mkfilename _PL((char *name));
FILE *os_fopen _PL((char *name, int mode));
int os_fseek _PL((FILE *f,long pos));
\end{verbatim}
\EndSynopsis


\Description
\verb"os_mkfilename()" converts any string into a valid file name.
\verb"os_fopen()" opens a file. \verb"mode" must be any of
\verb"FM_READ" (open for rading), 
\verb"FM_CREAT" (create a new file) or
\verb"FM_APPEND" (append to existing file or create a new file).
Additional flags may be or'ed to the mode:
\begin{center}
\begin{tabular}{lp{0.7\linewidth}}
\hline
Mode & Meaning \\
\hline
\verb"FM_LIB" & If the file does not exist in the current directory,
	look in the library directory. The library directory is
	defined either by the environment variable \verb"MTXLIB" or
	at compile-time by the symbol \verb"MTXLIB".\\
\verb"FM_TEXT" & Open in text mode. This flag must be used on some
	systems (e.g., MS-DOS) to open text files. By default, files
	are assumed to contain binary data.\\
\hline
\end{tabular}
\end{center}
\verb"os_fseek()" seeks to position \verb"pos". If $\verb"pos"\geq 0$,
it is interpreted as an obsolute address. A negative value of
\verb"pos" seeks to the end of file.



\subsubsection{CPU time}
%-----------------------
\index{CPU time}
\index{time limit}
\index{timeused@{\tt timeused()}}
\index{prtimes@{\tt prtimes()}}
\index{timelimit@{\tt timelimit()}}


\Synopsis
\begin{verbatim}
long os_timeused(void);
void os_timelimit(long nsecs);
void prtimes(void);
\end{verbatim}
\EndSynopsis


\Description
These function provide access to the CPU time used by the program.
\verb"os_timeused()" returns the CPU time in seconds.
\verb"prtimes()" prints a message containing the CPU time to stdout.
\verb"os_timelimit()" sets a limit for the CPU time in seconds.
This function is available only in the UNIX version. After the
specified time has been used the program will be stopped with
an error message.


\subsection{The word generator}\label{sec:words}
%------------------------------
\index{word generator}

Given a set of square matrices, the functions described below
calculate elements in the algebra generated by those matrices.
The word generator calculates elements in a `standard' sequence.
Each element has a unique integer, but not each integer has a
corresponding element.

\index{basis_t@{\tt basis\_t}}
\index{nextword@{\tt nextword()}}
\index{initbasis@{\tt initbasis()}}
\index{freebasis@{\tt freebasis()}}
\index{mkword@{\tt mkword()}}
\index{nameof@{\tt nameof()}}
\index{nextword@{\tt nextword()}}

\Synopsis
\begin{verbatim}
typedef struct {
    matrix_t *b[20];
    int ngen;
    matrix_t *w;
} basis_t;

long nextword(long w);
void initbasis(matrix_t *gen[], int ngen, basis_t *basis);
void freebasis(basis_t *basis);
void mkword(basis_t *b, long n);
char *nameof(basis_t *b,long n);
\end{verbatim}
\EndSynopsis

\Description
In order to use the word generator, you must declare a variable
of type \verb"basis_t". Then, call \verb"initbasis()" to
initialize the basis with your generators. Note that \verb"initbasis()"
expects a {\em pointer} as its last argument, i.e.
you must use the \verb"&" operator. Here is an example:
\begin{verbatim}
    matrix_t **mat;
    initbasis(mat,3,&mybasis);
\end{verbatim}
This would initialize the variable \verb"mybasis" (which has to
be of type \verb"basis_t") using three generators in
\verb"mat[0]", \verb"mat[0]" and  \verb"mat[0]".

Having initialized the \verb"basis_t" structure, the following
functions may be used to calculate algebra elements:
\begin{itemize}
\item
    \verb"nextword()" returns the next number in the
    `standard' sequence.
\item
    \verb"mkword()" calculates the element number \verb"n".
    The result is stored in \verb"basis.w". You may use
    this variable freely, provided you do not free it.
\item
    \verb"nameof()" returns a text representation of
    the word number \verb"n". The return value is a pointer
    to a static buffer which is overwritten on each call.
\end{itemize}
If you don't need the basis anymore, you should free it with
\verb"freebasis()".




\subsection{Sequences}\label{sec:seq}
%---------------------
\index{sequences}
\index{sequence_t@{\tt sequence\_t} data type}
\index{seq_alloc()@{\tt seq\_alloc()}}
\index{seq_free()@{\tt seq\_free()}}
\index{seq_insert()@{\tt seq\_insert()}}
\index{seq_remove()@{\tt seq\_remove()}}
\index{seq_read()@{\tt seq\_read()}}
\index{seq_write()@{\tt seq\_write()}}
\Synopsis
\begin{verbatim}
typedef struct {
    size_t len;
    void **buf;
} sequence_t;

sequence_t *seq_alloc(size_t size);
void seq_free(sequence_t *s);
int seq_insert(sequence_t *s, int pos, void *x);
int seq_remove(sequence_t *s, int pos);
sequence_t *seq_read(FILE *f);
int seq_write(FILE *f, sequence_t *s);
\end{verbatim}
\EndSynopsis


\Description
A sequence is a collection of (non-simple) {\MeatAxe} objects.
The members of a sequence may have different types and different
sizes. The members are in linear order, their number is
limited only by the amount of physical memory. Internally,
a sequence is represented by a \verb"sequence_t" structure.
\verb"len" is the length of the sequence, i.e., the
number of members, and \verb"buf" points to an array of
pointers to the members. The pointers als well as the
fields of \verb"sequence_t" are maintained automatically.
You should never change them directly.

As with all {\MeatAxe} data types, there are two functions
to create and destroy a squence. \verb"seq_alloc()" makes
a new, empty sequence. The \verb"size" parameter controls
the initial memory allocation for subsequent insert operations.
It may always bet set to zero --- the sequence grows automatically
if you add members. If you know in advance how many members the
sequence will eventually have, you may specify the size when 
you allocate the sequence. This avoids further memory allocations.
\verb"seq_free()" deletes a sequence, including all its
members.

\verb"seq_insert()" inserts a new member into a sequence. \verb"x"
must be a pointer to a non-simple {\MeatAxe} object as defined in
section \ref{sec:intdata}. The \verb"pos" parameter determines
where the new member is inserted. $0\leq\verb"pos"<\verb"s->len"$
means `insert into position \verb"pos"', any other value, negative
or greater than the sequence's length, means `append at the end'.
A return value of $-1$ indicates that there is not enough
memory for the insert operation.

\verb"seq_remove()" removes an object from a sequence and deletes the
object. \verb"pos" is the index of the object to remove. The first
object in a sequence has index 0.

\verb"seq_read()" reads a sequence from a file, and \verb"seq_write()"
writes a sequence to a file. 

{\em Notes:} In order to avoid memory corruption the following
rules must be obeyd when using sequences.
\begin{itemize}
\item 
  Only non-simple {\MeatAxe} objects may be inserted into sequences.
  For example, you may insert a sequence into another sequence, but
  you must not insert a packed row into a sequence.
\item
  Do not insert one object multiple times into the same sequence
  or into different sequences.
\item 
  Do not free, except with \verb"seq_free()" or \verb"seq_remove()",
  any object which belongs to a sequence.
\end{itemize}



\subsection{Miscellaneous}
%-------------------------
\index{greatest common divisor}

\index{gcd()@{\tt gcd()}}
\Synopsis
\begin{verbatim}
long gcd(long a, long b);
\end{verbatim}
\EndSynopsis


\Description
\verb"gcd()" returns the greatest common divisor of two integers.
If one or both arguments are negative, the result may be negative.
There is no error checking. If any of the arguments is zero,
\verb"gcd()" returns the other argument, which may be zero, too.



\subsection{Error handling}\label{sec:liberr}
%-----------------------
\index{error messages}
\index{errors in library calls}

\subsubsection{General remarks}
%---------------------------
\index{mtxerrno@{\tt mtxerrno}}
\index{mtxerraction@{\tt mtxerraction}}

\Synopsis
\begin{verbatim}
extern int mtxerrno;            /* Error code */
extern int mtxerraction;        /* Error action */
ERR_xxx                         /* mtxerrno values */
\end{verbatim}
\EndSynopsis

\Description
Most {\MeatAxe} library function have a special return value
which is reserved for reporting errors. This value is usually
\verb"NULL" if the function returns a pointer, or -1 if the
function returns an integer. Further information about the
type of error can be obtained by inspecting the error code,
which is stored in the global variable \verb"mtxerrno".
See below for a list all possible error codes.

The default action on errors is to store the error code in
\verb"mtxerrno" and return a special value to the
caller. This behaviour can be modified by setting the variable
\verb"mtxerraction". You may choose from three different error
actions:
\begin{center}
\begin{tabular}{|l|l|}
\hline
\verb"mtxerraction" & Meaning \\
\hline
0 & Set \verb"mtxerrno" and return special `error' value
    (default) \\
1 & As action 0 but also print an error message.\\
2 & Print error message and exit program immediately.\\
\hline
\end{tabular}
\end{center}
The last possibility, \verb"mtxerraction=2", is suitable for
debugging programs which do not always check the return
value from {\MeatAxe} library functions.


\subsubsection{Printing error messages}
%-----------------------------------
\index{mtxerror@{\tt mtxerror()}}
\index{errexit@{\tt errexit()}}
\Synopsis
\begin{verbatim}
void mtxerror(char *x);
void errexit(int errno, char *text);
\end{verbatim}
\EndSynopsis

\Description
The \verb"mtxerror()" function can be used to print a message after
an error occurred. This function works like the standard
\verb"perror()", i.e., it prints the argument followed by a
message depending on the value in \verb"mtxerrno". A typical
example might look like this:
\begin{verbatim}
     f = fopen("mat1","r");
     m1 = matread(f);
     if (m1 == NULL)  /* matread() failed ? */
     {
	 mtxerror("mat1");
	 exit(1);
     }
\end{verbatim}
This piece of code would produce the following error message
if \verb"mat1" cannot be read:
\msg{mat1: Error reading file.}

\verb"errexit()" prints an error message and stops the program. The
message depends on the value of \verb"code", which must be one of the
\verb"ERR_xxx" constants listed below. The only exception is
\verb"code=-1" which means `take the current value of \verb"mtxerrno"'.
The second argument is printed together with the error message.
Here is a short example:
\begin{verbatim}
    if (malloc(100000) == NULL)
	errexit("ERR_NOMEM,"malloc()");
    if (mat1->nor != mat2->noc)
	errexit(ERR_INCOMPAT,"Matrix 1 and Matrix2);
\end{verbatim}
This would produce the following messages:
\begin{verbatim}
malloc(): Not enough memory
Matrix 1 and Matrix 2: Objects are not compatible
\end{verbatim}


\subsubsection{Error codes}
%-----------------------
\index{error codes}
\index{ERR_xxx@{\tt ERR\_xxx} constants}

\paragraph{Command line errors}
%------------------------------
\begin{center}
\begin{tabular}{|l|p{0.7\linewidth}|}
\hline
Error code		& Meaning \\
\hline
\verb"ERR_BADUSAGE"	& Bad usage \\
\verb"ERR_OPTION"	& Unknown or badly formed option \\
\verb"ERR_NARGS"	& Illegal number of arguments singular matrix \\
\hline
\end{tabular}
\end{center}

\paragraph{Data type errors}
%---------------------------
\begin{center}
\begin{tabular}{|l|p{0.7\linewidth}|}
\hline
Error code		& Meaning \\
\hline
\verb"ERR_NOTMATRIX"	& Not a matrix\\
\verb"ERR_NOTPERM"	& Not a permutation\\
\verb"ERR_NOTPOLY"	& Not a polynomial\\
\hline
\end{tabular}
\end{center}

\paragraph{Resources and exceptions}
%-----------------------------------
\begin{center}
\begin{tabular}{|l|p{0.7\linewidth}|}
\hline
Error code		& Meaning \\
\hline
\verb"ERR_NOMEM"	& Out of memory \\
\verb"ERR_GAMEOVER"	& Time limit exceeded \\
\verb"ERR_DIV0"		& Division by zero or attempt to invert a
			  singular matrix \\
\hline
\end{tabular}
\end{center}


\paragraph{File errors}
%----------------------
\begin{center}
\begin{tabular}{|l|p{0.7\linewidth}|}
\hline
Error code		& Meaning \\
\hline
\verb"ERR_FILEOPEN"	& Could not open\\
\verb"ERR_FILEREAD"	& File read error\\
\verb"ERR_FILEWRITE"	& File write error\\
\verb"ERR_FILEFMT"	& File format error\\
\hline
\end{tabular}
\end{center}

\paragraph{Format errors}
%-----------------------
\begin{center}
\begin{tabular}{|l|p{0.7\linewidth}|}
\hline
Error code		& Meaning \\
\hline
\verb"ERR_BADARG"	& Bad argument \\
\verb"ERR_BADTYPE"	& Bad type \\
\verb"ERR_RANGE"	& Out of range \\
\verb"ERR_NOTECH"	& Matrix not in chelon form \\
\verb"ERR_NOTSQUARE"	& Matrix not square \\
\verb"ERR_INCOMPAT"	& Arguments are incompatible \\
\hline
\end{tabular}
\end{center}



