%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This file is part of the C Meat-Axe. % % Written by Michael Ringe % % (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 $ab$. 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 -] ...", "", "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}