/*********************************************************************** * This file is part of the C Meat-Axe * Written by Michael Ringe * (C) Copyright 1992: Lehrstuhl D fuer Mathematik * RWTH Aachen * Aachen, Germany *********************************************************************** * $Source: /usd/mringe/mtx/src/RCS/meataxe.h,v $ * $Revision: 2.19 $ * $Date: 1994/03/14 09:44:28 $ *********************************************************************** * Header file for the MeatAxe library **********************************************************************/ #if !defined(__MEATAXE_INCLUDED) /* Include only once */ #define __MEATAXE_INCLUDED /* ------------------------------------------------------------------ The _PL macro for function prototypes ------------------------------------------------------------------ */ #if defined(__STDC__) # define _PL(s) s #else # define _PL(s) () #endif /* ------------------------------------------------------------------ Include some commonly used header files ------------------------------------------------------------------ */ #include #include #include "os.h" /* ------------------------------------------------------------------ MeatAxe data types ------------------------------------------------------------------ */ #define T_MATRIX 0 #define T_PERM 1 #define T_POLY 2 #define T_SET 3 #define T_BITS 4 #define T_SEQUENCE 20 /* ------------------------------------------------------------------ Some typedef's ------------------------------------------------------------------ */ typedef unsigned long Ulong; typedef unsigned short Ushort; typedef unsigned char Uchar; /* ------------------------------------------------------------------ Error codes ------------------------------------------------------------------ */ #define EXIT_OK 0 /* Exit code: normal end */ #define EXIT_ERR 1 /* error */ /* MeatAxe error codes */ #define ERR_NULL 0 /* */ #define ERR_NOMEM 1 /* Not enough memory */ #define ERR_GAMEOVER 2 /* Time limit exceeded */ #define ERR_DIV0 8 /* Division by 0 or singular Matrix */ #define ERR_FILE 20 /* File errors */ #define ERR_FILEOPEN 21 /* Could not open */ #define ERR_FILEREAD 22 /* Read error */ #define ERR_FILEWRITE 23 /* Write error */ #define ERR_FILEFMT 24 /* Bad format */ #define ERR_NFILES 25 /* Too many files */ #define ERR_EOF 26 /* Unexpected EOF */ #define ERR_ARGS 30 /* Arguments */ #define ERR_BADARG 31 /* Bad argument */ #define ERR_BADTYPE 32 /* Bad type */ #define ERR_RANGE 33 /* Out of range */ #define ERR_NOTECH 34 /* Matrix not in chelon form */ #define ERR_NOTSQUARE 35 /* Matrix not square */ #define ERR_INCOMPAT 36 /* Arguments are incompatible */ #define ERR_USAGE 40 #define ERR_BADUSAGE 41 /* Bad command line */ #define ERR_OPTION 42 /* Bad usage of option */ #define ERR_NARGS 43 /* Bad number of arguments */ #define ERR_NOTMATRIX 51 /* Not a matrix */ #define ERR_NOTPOLY 52 /* Not a polynomial */ #define ERR_NOTPERM 53 /* Not a permutation */ /* ------------------------------------------------------------------ Model dependent constants and types. ------------------------------------------------------------------ */ #if defined(BIG) #define ZZZVERSION (0x1000 | 6) typedef unsigned short *PTR; typedef unsigned short FEL; #define F_ZERO 0xFFFF #define F_ONE ((FEL)0) #else #define ZZZVERSION 6 typedef unsigned char *PTR; typedef unsigned char FEL; #define F_ZERO ((FEL)0) #define F_ONE ((FEL)1) #endif /* ------------------------------------------------------------------ Some constants ------------------------------------------------------------------ */ #define MAXFILES 10 /* Max. number of files */ /* ------------------------------------------------------------------ Global variables ------------------------------------------------------------------ */ extern long zfl, zchar; /* Field order and characteristic */ extern FEL zgen; /* Generator */ extern long znoc; /* Number of columns for row ops */ extern long BPR, LPR; /* Used internally */ /* ------------------------------------------------------------------ zzz functions (zzz.c) ------------------------------------------------------------------ */ int mtxinit _PL((void)); void zsetlen _PL((long field, long ncols)); FEL zembed _PL((FEL a, long subfield)); FEL zrestrict _PL((FEL a, long subfield)); size_t zsize _PL((long nrows)); PTR zalloc _PL((long NROWS)); void zadvance _PL((PTR *ptr, long nrows)); void zinsert _PL((PTR row, long col, FEL mark)); FEL zextract _PL((PTR row, long col)); long zfindpiv _PL((PTR row, FEL *mark)); void zmoverow _PL((PTR dest, PTR src)); void zswaprow _PL((PTR dest, PTR src)); int zcmprow _PL((PTR dest, PTR src)); void zaddrow _PL((PTR row1, PTR row2)); void zmulrow _PL((PTR row, FEL mark)); void zaddmulrow _PL((PTR row1, PTR row2, FEL f)); void zmaprow _PL((PTR row, PTR matrix, long nor, PTR result)); void zpermrow _PL((PTR row, PTR perm, PTR result)); FEL zitof _PL((long l)); long zftoi _PL((FEL f)); /* ------------------------------------------------------------------ ZZZ functions implemented as macros: zadd(), zsub(), zmul(), zdiv() ------------------------------------------------------------------ */ #if defined(BIG) FEL zadd _PL((FEL a,FEL b)); FEL zsub _PL((FEL a,FEL b)); FEL zmul _PL((FEL a,FEL b)); FEL zdiv _PL((FEL a,FEL b)); #else extern FEL tmult[256][256]; extern FEL tadd[256][256]; extern FEL taddinv[256], tmultinv[256]; #define zadd(a,b) ((FEL)tadd[(unsigned char)a][(unsigned char)b]) #define zmul(a,b) ((FEL)tmult[(unsigned char)a][(unsigned char)b]) #define zsub(a,b) ((FEL)tadd[(unsigned char)a][taddinv[\ (unsigned char)b]]) #define zdiv(a,b) ((FEL)tmult[(unsigned char)a][tmultinv[\ (unsigned char)b]]) #endif /* ------------------------------------------------------------------ zzz <--> GAP conversion (zgap.c) ------------------------------------------------------------------ */ char *zftogap _PL((FEL f)); /* ------------------------------------------------------------------ Bitstring operations (zbitstr.c) ------------------------------------------------------------------ */ typedef struct { Ushort id; /* always = T_BITS */ char dummy[sizeof(long)-sizeof(Ushort)]; unsigned char buf[1]; } bitstring_t; extern size_t bs_size; void bs_print _PL((bitstring_t *b)); char *bs_desc _PL((bitstring_t *b)); void bs_setlen _PL((int l)); void bs_reset _PL((bitstring_t *x)); bitstring_t *bs_alloc _PL((void)); void bs_free _PL((bitstring_t *b)); void bs_set _PL((bitstring_t *b, int i)); void bs_clear _PL((bitstring_t *b, int i)); int bs_test _PL((bitstring_t *b, int i)); bitstring_t *bs_read _PL((FILE *f)); int bs_write _PL((FILE *f, bitstring_t *b)); void bs_and _PL((bitstring_t *dest, bitstring_t *src)); void bs_minus _PL((bitstring_t *dest, bitstring_t *src)); void bs_or _PL((bitstring_t *dest, bitstring_t *src)); int bs_match _PL((bitstring_t *x, bitstring_t *y)); int bs_issub _PL((bitstring_t *a, bitstring_t *b)); int bs_cmp _PL((bitstring_t *a, bitstring_t *b)); void bs_cpy _PL((bitstring_t *a, bitstring_t *b)); /* ------------------------------------------------------------------ File i/o (zfile.c) ------------------------------------------------------------------ */ size_t zreadlong _PL((FILE *f, long *buf, size_t n)); size_t zwritelong _PL((FILE *f, long *buf, size_t n)); size_t zreadvec _PL((FILE *f, PTR buf, size_t n)); size_t zwritevec _PL((FILE *f, PTR buf, size_t n)); int zseek _PL((FILE *f, long pos)); FILE *zreadhdr _PL((char *name, long *fld, long *nor, long *noc)); FILE *zwritehdr _PL((char *name, long fld, long nor, long noc)); /* ------------------------------------------------------------------ Gauss elimination and related functions (zgauss.c, znullsp.c, zmatinv.c) ------------------------------------------------------------------ */ int zmkpivot _PL((PTR matrix, long nor, long *piv)); long zmkechelon _PL((PTR matrix, long nor, long *piv)); int zcleanrow _PL((PTR row, PTR matrix, long nor, long *piv)); int zcleanrow2 _PL((PTR row,PTR matrix,long nor,long *piv,PTR row2)); long znullsp _PL((PTR matrix, long nor, long *piv, PTR nsp)); int zmatinv _PL((PTR mat, PTR result)); /* ------------------------------------------------------------------ Projection on the quotient (zquot.c) ------------------------------------------------------------------ */ int zquotinit _PL((PTR subspace, long dim, long *piv)); PTR zquot _PL((PTR space, long dim)); PTR zquotop _PL((PTR matrix)); /* ------------------------------------------------------------------ Spin-up (zspin.c) ------------------------------------------------------------------ */ long zspinup _PL((PTR space, long nseed, long *piv, PTR gen[], int ngen, int gentype)); /* ------------------------------------------------------------------ Seed vector generation (zpseed.c) ------------------------------------------------------------------ */ extern PTR zpseed_vec; /* The seed vector */ void zpseed_free _PL((void)); int zpseed_init _PL((long sdim, PTR sbasis)); long zpseed_make _PL((long num)); long zpseed_next _PL((void)); /* ------------------------------------------------------------------ Command line parsing (args.h) ------------------------------------------------------------------ */ 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 _PL((int argc, char **argv, proginfo_t *pi)); int zgetopt _PL((char *pattern)); long getint _PL((void)); /* ------------------------------------------------------------------ Messages (message.c) ------------------------------------------------------------------ */ extern int mtxerrno; extern int mtxerraction; void mtxerror _PL((char *text)); void errexit _PL((int code, char *text)); int errhandler _PL((int errno, char *errfile, int errline)); #define MTXFAIL(errcode,retval) \ { errhandler(errcode,__FILE__,__LINE__); return (retval); } #define FATAL(msg)\ (fprintf(stderr,"\n%s(%d): %s.\n",__FILE__,__LINE__,msg),exit(1)) extern int msg_level; #define MSG0 (msg_level >= 0) #define MSG1 (msg_level >= 1) #define MSG2 (msg_level >= 2) #define MSG3 (msg_level >= 3) #define MESSAGE(level,args)\ (msg_level>=(level) ? ( printf args , fflush(stdout), 1) : 0 ) /* ------------------------------------------------------------------ CPU time (prtimes.c) ------------------------------------------------------------------ */ long timeused _PL((void)); void prtimes _PL((void)); void timelimit _PL((long nsecs)); /* ------------------------------------------------------------------ Random numbers (random.c) ------------------------------------------------------------------ */ void rand_init _PL((unsigned seed)); long int rand_next _PL((void)); #define rand_int(max) ((unsigned int) rand_next() % (max)) /* ------------------------------------------------------------------ Miscellaneous ------------------------------------------------------------------ */ long gcd _PL((long a, long b)); /* ------------------------------------------------------------------ Matrices ------------------------------------------------------------------ */ typedef struct { Ushort id; /* Always = T_MATRIX */ long fl, nor, noc; /* Field, #rows, #columns */ PTR d; /* Pointer to data area */ } matrix_t; void matprint _PL((char *name, matrix_t *p)); char *matdesc _PL((matrix_t *s)); matrix_t *matalloc _PL((long fl, long nor, long noc)); matrix_t *matid _PL((long fl, long nor)); void matfree _PL((matrix_t *m)); matrix_t *matdup _PL((matrix_t *src)); int matmove _PL((matrix_t *dest, matrix_t *src)); matrix_t *matextract _PL((matrix_t *src, long first, long last)); matrix_t *matread _PL((FILE *f)); int matwrite _PL((FILE *f, matrix_t *mat)); matrix_t *matload _PL((char *fn)); int matsave _PL((matrix_t *mat, char *fn)); matrix_t *matadd _PL((matrix_t *dest, matrix_t *src)); matrix_t *matmul _PL((matrix_t *dest, matrix_t *src)); matrix_t *mattr _PL((matrix_t *src)); matrix_t *matinv _PL((matrix_t *src)); long nullity _PL((matrix_t *mat)); matrix_t *nullsp _PL((matrix_t *mat)); matrix_t *echelon _PL((matrix_t *src)); int chkechelon _PL((matrix_t *mat)); matrix_t *matpower _PL((matrix_t *mat, long n)); long matorder _PL((matrix_t *mat)); matrix_t *matquot _PL((matrix_t *subsp, matrix_t *mat)); /* ------------------------------------------------------------------ ycomp.c ------------------------------------------------------------------ */ int ycompare _PL((matrix_t *m1, matrix_t *m2, long n)); /* ------------------------------------------------------------------ yspin.c ------------------------------------------------------------------ */ matrix_t *matspin _PL((matrix_t *seed, int ngen, matrix_t *gen[])); matrix_t *matspin_f _PL((matrix_t *seed, int ngen, matrix_t *gen[], long *sdim)); /* ------------------------------------------------------------------ permutations ------------------------------------------------------------------ */ typedef struct { Ushort id; /* Always = T_PERM */ long deg; PTR d; } perm_t; char *permdesc _PL((perm_t *s)); perm_t *permalloc _PL((long deg)); void permfree _PL((perm_t *m)); perm_t *permdup _PL((perm_t *src)); perm_t *permmove _PL((perm_t *dest, perm_t *src)); perm_t *permread _PL((FILE *f)); int permwrite _PL((FILE *f, perm_t *perm)); perm_t *permload _PL((char *fn)); int permsave _PL((perm_t *perm, char *fn)); perm_t *permmul _PL((perm_t *dest, perm_t *src)); long permorder _PL((perm_t *perm)); perm_t *permpower _PL((perm_t *p, long n)); /* ------------------------------------------------------------------ polynomials ------------------------------------------------------------------ */ typedef struct { Ushort id; /* Always = T_POLY */ long fl; long deg; size_t size; /* deg <= size-1 */ FEL *buf; } poly_t; char *poldesc _PL((poly_t *s)); poly_t *polalloc _PL((long fl, long degree)); void polfree _PL((poly_t *x)); poly_t *poldup _PL((poly_t *x)); poly_t *poladd _PL((poly_t *dest, poly_t *src)); poly_t *polmul _PL((poly_t *dest, poly_t *src)); poly_t *poldivmod _PL((poly_t *a, poly_t *b)); poly_t *polmod _PL((poly_t *a, poly_t *b)); void polprint _PL((char *name, poly_t *p)); poly_t *polread _PL((FILE *f)); int polwrite _PL((FILE *f, poly_t *p)); int polcmp _PL((poly_t *a, poly_t *b)); poly_t *polgcd _PL((poly_t *a, poly_t *b)); poly_t *polderive _PL((poly_t *p)); int vec2pol _PL((PTR vec, poly_t *pol)); int pol2vec _PL((poly_t *pol, PTR vec)); int polpack _PL((poly_t *pol, PTR vec)); poly_t *polshiftmod _PL((poly_t *p, long n, poly_t *q)); /* ------------------------------------------------------------------ Berlekamp factorization (berlekmp.c) ------------------------------------------------------------------ */ typedef struct { poly_t *p; /* Irreducible factor */ long n; /* Multiplicity */ } factor_t; factor_t *factorization _PL((poly_t *pol)); /* ------------------------------------------------------------------ Sets (ysets.c) ------------------------------------------------------------------ */ typedef struct { Ushort id; /* Always = T_SET */ size_t len, max; long *buf; } set_t; int set_allocstrategy _PL((size_t first,size_t blocksize)); char *set_desc _PL((set_t *s)); set_t *set_alloc _PL((void)); void set_free _PL((set_t *x)); int set_insert _PL((set_t *set, long elem)); int set_contains _PL((set_t *set, long elem)); set_t *set_read _PL((FILE *f)); int set_write _PL((FILE *f, set_t *set)); /* ------------------------------------------------------------------ Sequences (sequence.c) ------------------------------------------------------------------ */ typedef struct { Ushort id; /* Always = T_SEQUENCE */ size_t len, max; void **buf; } sequence_t; char *seq_desc _PL((sequence_t *s)); sequence_t *seq_alloc _PL((size_t size)); void seq_free _PL((sequence_t *x)); int seq_insert _PL((sequence_t *s, int pos, void *x)); int seq_remove _PL((sequence_t *s, int pos)); sequence_t *seq_read _PL((FILE *f)); int seq_write _PL((FILE *f, sequence_t *x)); /* ------------------------------------------------------------------ MeatAxe object methods ------------------------------------------------------------------ */ void mtx_free _PL((void *x)); char *mtx_getmane _PL((void *x)); char *mtx_getdesc _PL((void *x)); void *mtx_read _PL((FILE *f)); int mtx_write _PL((FILE *f, void *x)); #endif /* !defined(__MEATAXE_INCLUDED) */