meataxe.h

/* ============================= C MeatAxe ==================================
   File:        $Id: meataxe.h,v 1.3 2007-09-03 21:35:22 mringe Exp $
   Comment:     MeatAxe library external interfaces.
   --------------------------------------------------------------------------
   (C) Copyright 2004 Michael Ringe, Lehrstuhl D fuer Mathematik,
   RWTH Aachen, Germany  <mringe@math.rwth-aachen.de>
   This program is free software; see the file COPYING for details.
   ========================================================================== */

#ifndef MEATAXE_H_INCLUDED
#define MEATAXE_H_INCLUDED

#include <stdio.h>
#include <stdarg.h>

#if defined GCC
#define MTX_PRINTF_ATTRIBUTE(f,v) __attribute__((format(printf,f,v)))
#else
#define MTX_PRINTF_ATTRIBUTE(f,v)
#endif

#define FM_READ     0x01        
#define FM_CREATE   0x02        
#define FM_APPEND   0x03        
#define FM_TEXT     0x10
#define FM_LIB      0x20
#define FM_NOERROR  0x40

int SysCreateDirectory(const char *name);
int SysGetPid();
void SysInit(void);
void *SysMalloc(size_t nbytes);
FILE *SysFopen(const char *name, int mode);
void SysFree(void *x);
int SysFseek(FILE *f,long pos);
int SysFseekRelative(FILE *file, long distance);
void *SysRealloc(void *buf, size_t nbytes);
int SysReadLong32(FILE *f, long *buf, int n);
#define SysReadLong SysReadLong32
int SysReadLongX(FILE *f, long *buf, int n);
int SysRemoveDirectory(const char *name);
int SysRemoveFile(const char *name);
void SysSetTimeLimit(long nsecs);
long SysTimeUsed(void);
int SysWriteLong32(FILE *f, const long *buf, int n);
#define SysWriteLong SysWriteLong32
int SysWriteLongX(FILE *f, const long *buf, int n);

#define ALLOC(type) ((type *) SysMalloc(sizeof(type)))
#define NALLOC(type,n) ((type *) SysMalloc((size_t)(n) * sizeof(type)))
#define NREALLOC(x,type,n)\
        ((type *) SysRealloc(x,(size_t)(n) * sizeof(type)))
#define FREE(x) SysFree(x)

/* ---------------------------------------------------------------------------------------------- */

/* Data types and constants
   ------------------------ */

#if ZZZ==0

typedef unsigned char FEL;              
typedef FEL *PTR;                       
#define FF_ZERO ((FEL)0)                
#define FF_ONE ((FEL)1)                 
#define ZZZVERSION 6

#elif ZZZ==1

typedef unsigned short FEL;
typedef unsigned short *PTR;
#define FF_ZERO ((FEL)0xFFFF)
#define FF_ONE ((FEL)0)
#define ZZZVERSION 0x101

#else

#error "ZZZ undefined"

#endif

/* Kernel variables and functions
   ------------------------------ */

extern int FfOrder;             
extern int FfChar;              
extern FEL FfGen;               
extern int FfNoc;               
extern size_t FfCurrentRowSize;
extern int FfCurrentRowSizeIo;
extern int MPB;         
extern int LPR;         
/* Arithmetic */
FEL FfAdd(FEL a, FEL b);
FEL FfSub(FEL a, FEL b);
FEL FfMul(FEL a, FEL b);
FEL FfDiv(FEL a, FEL b);
FEL FfNeg(FEL a);
FEL FfInv(FEL a);

int FfMakeTables(int field);
int FfSetField(int field);
int FfSetNoc(int noc);


void FfAddMulRow(PTR dest, PTR src, FEL f);
void FfAddMulRowPartial(PTR dest, PTR src, FEL f, int first, int len);
PTR FfAddRow(PTR dest, PTR src);
PTR FfAddRowPartial(PTR dest, PTR src, int first, int len);
PTR FfSubRow(PTR dest, PTR src);
PTR FfSubRowPartial(PTR dest, PTR src, int first, int len);
PTR FfSubRowPartialReverse(PTR dest, PTR src, int first, int len);
PTR FfAlloc(int nor);
int FfCmpRows(PTR p1, PTR p2);
void FfCleanRow(PTR row, PTR matrix, int nor, const int *piv);
int FfCleanRow2(PTR row, PTR matrix, int nor, const int *piv, PTR row2);
int FfCleanRowAndRepeat(PTR row, PTR mat, int nor, const int *piv,
    PTR row2, PTR mat2);
void FfCopyRow(PTR dest, PTR src);
FEL FfEmbed(FEL a, int subfield);
FEL FfExtract(PTR row, int col);
void FfExtractColumn(PTR mat,int nor,int col,PTR result);
int FfFindPivot(PTR row, FEL *mark);
void FfFree(PTR x);
FEL FfFromInt(int l);
PTR FfGetPtr(PTR base, int row);
void FfInsert(PTR row, int col, FEL mark);
void FfMulRow(PTR row, FEL mark);
FILE *FfReadHeader(const char *name, int *fld, int *nor, int *noc);
int FfReadRows(FILE *f, PTR buf, int n);
FEL FfRestrict(FEL a, int subfield);
size_t FfRowSize(int noc);
FEL FfScalarProduct(PTR a, PTR b);
int FfSeekRow(FILE *f, int pos);
int FfStepPtr(PTR *x);
void FfSwapRows(PTR dest, PTR src);
const char *FfToGap(FEL f);
int FfToInt(FEL f);
size_t FfTrueRowSize(int noc);
FILE *FfWriteHeader(const char *name, int fld, int nor, int noc);
int FfWriteRows(FILE *f, PTR buf, int n);


/* --------------------------------------------------------------------------
   Macro versions of kernel functions
   -------------------------------------------------------------------------- */


#if ZZZ==0

extern FEL mtx_tmult[256][256];  
extern FEL mtx_tadd[256][256];   
extern FEL mtx_taddinv[256];     
extern FEL mtx_tmultinv[256];    
extern FEL mtx_tffirst[256][2];  
extern FEL mtx_textract[8][256]; 
extern FEL mtx_tnull[8][256];
extern FEL mtx_tinsert[8][256];  
extern long mtx_embedord[4];
extern FEL mtx_embed[4][16];
extern FEL mtx_restrict[4][256];

#define FfAdd(a,b) ((FEL)mtx_tadd[(int)(unsigned char)a][(int)(unsigned char)b])
#define FfDiv(a,b) FfMul((a),FfInv(b))
#define FfInv(a) (mtx_tmultinv[(int)(unsigned char)a])
#define FfMul(a,b) ((FEL)mtx_tmult[(int)(unsigned char)a][(int)(unsigned char)b])
#define FfNeg(a) (mtx_taddinv[(int)(unsigned char)a])
#define FfSub(a,b) FfAdd((a),FfNeg(b))

#elif ZZZ==1

#define FfExtract(row,col) ((FEL)((row)[(col)-1]))
#define FfInsert(row,col,mark) ((void)((row)[(col)-1] = mark))


#endif

/* ------------------------------------------------------------------
   Other low-level functions (zzz2.c)
   ------------------------------------------------------------------ */

void FfMapRow(PTR row, PTR matrix, int nor, PTR result);
void FfPermRow(PTR row, const long *perm, PTR result);
int FfSumAndIntersection(PTR wrk1, int *nor1, int *nor2, PTR wrk2, int *piv);


/* ------------------------------------------------------------------
   Library initialization and cleanup
   ------------------------------------------------------------------ */

extern int Mtx_IsInitialized;
extern int Mtx_IsX86;
extern int MtxOpt_UseOldWordGenerator;

int MtxInitLibrary();
void MtxCleanupLibrary();


typedef struct {
    char *S;    
} String;

String StrAlloc(size_t initial_capacity);
void StrFree(String *s);
void StrAppend(String *s, const char *text);
MTX_PRINTF_ATTRIBUTE(2,3)
void StrAppendF(String *s, const char *fmt, ...);
MTX_PRINTF_ATTRIBUTE(2,3)
void StrPrintF(String *s, const char *fmt, ...);

/* ------------------------------------------------------------------
   Application framework
   ------------------------------------------------------------------ */

extern char MtxBinDir[1024];    
extern char MtxLibDir[1024];    
#define APP_MAX_ARGS 50

typedef struct
{
    const char *Name;           
    const char *Description;    
    const char *Help;           
} MtxApplicationInfo_t;


typedef struct
{
    MtxApplicationInfo_t const *AppInfo;        
    int OrigArgC;                               
    const char **OrigArgV;                      
    int ArgC;                                   
    const char **ArgV;                          
    int OptEnd;                                 
    unsigned long IsDone[APP_MAX_ARGS];         
    const char *OptArg;                         
    int OptInd;                                 
    char TempDirName[200];                      
} MtxApplication_t;


MtxApplication_t *AppAlloc(MtxApplicationInfo_t const *ai, int argc, const char **argv);
int AppFree(MtxApplication_t *a);
int AppGetOption(MtxApplication_t *app, const char *spec);
int AppGetCountedOption(MtxApplication_t *app, const char *spec);
const char *AppGetTextOption(MtxApplication_t *app, const char *spec,
    const char *dflt);
int AppGetIntOption(MtxApplication_t *app, const char *spec, int dflt,
    int min, int max);
int AppGetArguments(MtxApplication_t *app, int min_argc, int max_argc);
const char *AppCreateTempDir(MtxApplication_t *app);

#define MTX_COMMON_OPTIONS_SYNTAX \
    "[<Options>]"

#define MTX_COMMON_OPTIONS_DESCRIPTION \
    "    -Q ...................... Quiet, no messages\n" \
    "    -V ...................... Verbose, more messages\n" \
    "    -T <MaxTime> ............ Set CPU time limit [s]\n"

/* ------------------------------------------------------------------
   Messages and error handling
   ------------------------------------------------------------------ */
                                /* Error message codes (%E arguments) */
#define MTX_ERR_NOMEM       1   
#define MTX_ERR_GAME_OVER   2   
#define MTX_ERR_DIV0        8   
#define MTX_ERR_FILEFMT     24  
#define MTX_ERR_BADARG      31  
#define MTX_ERR_RANGE       33  
#define MTX_ERR_NOTECH      34  
#define MTX_ERR_NOTSQUARE   35  
#define MTX_ERR_INCOMPAT    36  
#define MTX_ERR_BADUSAGE    41  
#define MTX_ERR_OPTION      42  
#define MTX_ERR_NARGS       43  
#define MTX_ERR_NOTMATRIX   51  
#define MTX_ERR_NOTPERM     53  
typedef struct
{
        const char *Name;               
        const char *BaseName;   
}
MtxFileInfo_t;

typedef struct
{
        const MtxFileInfo_t *FileInfo;  
        int LineNo;                                             
        const char *Text;                               
}
MtxErrorRecord_t;

typedef void MtxErrorHandler_t(const MtxErrorRecord_t *);

#define MTX_DEFINE_FILE_INFO \
    static MtxFileInfo_t Mtx_ThisFile = { __FILE__, NULL };

int MtxError(MtxFileInfo_t *fi, int line, const char *text, ...);
MtxErrorHandler_t *MtxSetErrorHandler(MtxErrorHandler_t *h);


#define MTX_ERROR(msg) MtxError(&Mtx_ThisFile,__LINE__,msg)
#define MTX_ERROR1(msg,a1) MtxError(&Mtx_ThisFile,__LINE__,msg,a1)
#define MTX_ERROR2(msg,a1,a2) MtxError(&Mtx_ThisFile,__LINE__,msg,a1,a2)
#define MTX_ERROR3(msg,a1,a2,a3) MtxError(&Mtx_ThisFile,__LINE__,msg,a1,a2,a3)
#define MTX_ERROR4(msg,a1,a2,a3,a4) MtxError(&Mtx_ThisFile,__LINE__,\
    msg,a1,a2,a3,a4)
#define MTX_ERROR5(msg,a1,a2,a3,a4,a5) MtxError(&Mtx_ThisFile,__LINE__,\
    msg,a1,a2,a3,a4,a5)
#define MTX_ERROR7(msg,a1,a2,a3,a4,a5,a6,a7) MtxError(&Mtx_ThisFile,__LINE__,\
    msg,a1,a2,a3,a4,a5,a6,a7)


#define MTX_VERIFY(e) ((void)((e) ||\
    MtxError(&Mtx_ThisFile,__LINE__,"Assertion failed: %s",#e)))

#ifdef _DEBUG
#define DEBUG 1
#endif

#ifdef DEBUG
#define MTX_ASSERT(e) MTX_VERIFY(e)
#else
#define MTX_ASSERT(e)
#undef PARANOID
#endif



/* ------------------------------------------------------------------
   Messages
   ------------------------------------------------------------------ */

int MtxFormatMessage(char *buf, int bufsize, const char *msg, va_list al);
int MtxPrintMessage(FILE *f, const char *fmt, ...);

extern int MtxMessageLevel;
#define MSG0 (MtxMessageLevel >= 0)
#define MSG1 (MtxMessageLevel >= 1)
#define MSG2 (MtxMessageLevel >= 2)
#define MSG3 (MtxMessageLevel >= 3)
#define MSG4 (MtxMessageLevel >= 4)
#define MESSAGE(level,args)\
  (MtxMessageLevel>=(level) ? ( printf args , fflush(stdout), 1) : 0 )

/* ------------------------------------------------------------------
   Miscellaneous
   ------------------------------------------------------------------ */

void MtxRandomInit(unsigned seed);
long int MtxRandom(void);
int MtxRandomInt(int max);
long gcd(long a, long b);
long lcm(long a, long b);


/* ------------------------------------------------------------------
   Structured text files (stfXXX.c)
   ------------------------------------------------------------------ */

typedef struct
{
    FILE *File;         
    char *LineBuf;      
    char *GetPtr;       
    int LineBufSize;    
    int OutPos;         
    int LineNo;         
} StfData;

int StfClose(StfData *f);
StfData *StfOpen(const char *name, int mode);

int StfPut(StfData *f, const char *text);
int StfPutInt(StfData *f, int value);
int StfPutString(StfData *f, const char *text);
int StfPutVector(StfData *f, int size, const int *value);
int StfBeginEntry(StfData *f, const char *name);
int StfEndEntry(StfData *f);
int StfWriteValue(StfData *f, const char *name, const char *value);
int StfWriteInt(StfData *f, const char *name, int value);
int StfWriteString(StfData *f, const char *name, const char *value);
int StfWriteVector(StfData *f, const char *name, int size, const int *value);

int StfReadLine(StfData *f);
const char *StfGetName(StfData *f);
int StfGetInt(StfData *f, int *buf);
int StfGetString(StfData *f, char *buf, size_t bufsize);
int StfMatch(StfData *f, const char *pattern);
int StfGetVector(StfData *f, int *bufsize, int *buf);

/* ------------------------------------------------------------------
   MeatAxe files
   ------------------------------------------------------------------ */

typedef struct
{
    unsigned long Magic;        
    int Field;                  
    int Nor;                    
    int Noc;                    
    FILE *File;                 
    char *Name;                 
} MtxFile_t;

int MfIsValid(const MtxFile_t *file);
MtxFile_t *MfOpen(const char *name);
MtxFile_t *MfCreate(const char *name, int field, int nor, int noc);
int MfClose(MtxFile_t *file);
int MfReadLong(MtxFile_t *f, long *buf, int nrows);
int MfReadRows(MtxFile_t *f, PTR buf, int nrows);
int MfWriteLong(MtxFile_t *f, const long *buf, int count);
int MfWriteRows(MtxFile_t *f, PTR buf, int nrows);


/* ---------------------------------------------------------------------------------------------- */

typedef struct
{
    unsigned long Magic;
    int Field;          
    int Nor;            
    int Noc;            
    PTR Data;           
    size_t RowSize;     
    int *PivotTable;    
} Matrix_t;

Matrix_t *MatAdd(Matrix_t *dest, const Matrix_t *src);
Matrix_t *MatAddMul(Matrix_t *dest, const Matrix_t *src, FEL coeff);
Matrix_t *MatAlloc(int field, int nor, int noc);
int MatClean(Matrix_t *mat, const Matrix_t *sub);
int MatCompare(const Matrix_t *a, const Matrix_t *b);
int MatCopyRegion(Matrix_t *dest, int destrow, int destcol,
    const Matrix_t *src, int row1, int col1, int nrows, int ncols);
Matrix_t *MatCut(const Matrix_t *src, int row1, int col1, int nrows, int ncols);
Matrix_t *MatCutRows(const Matrix_t *src, int row1, int nrows);
Matrix_t *MatDup(const Matrix_t *src);
int MatEchelonize(Matrix_t *mat);
int MatFree(Matrix_t *mat);
PTR MatGetPtr(const Matrix_t *mat, int row);
Matrix_t *MatId(int fl, int nor);
Matrix_t *MatInverse(const Matrix_t *src);
int MatIsValid(const Matrix_t *m);
Matrix_t *MatLoad(const char *fn);
Matrix_t *MatMul(Matrix_t *dest, const Matrix_t *src);
Matrix_t *MatMulScalar(Matrix_t *dest, FEL coeff);
Matrix_t *MatMulStrassen(Matrix_t *dest, const Matrix_t *A, const Matrix_t *B);
void StrassenSetCutoff(size_t size);
long MatNullity(const Matrix_t *mat);
long MatNullity__(Matrix_t *mat);
Matrix_t *MatNullSpace(const Matrix_t *mat);
Matrix_t *MatNullSpace_(Matrix_t *mat, int flags);
Matrix_t *MatNullSpace__(Matrix_t *mat);
int MatOrder(const Matrix_t *mat);
int MatPivotize(Matrix_t *mat);
Matrix_t *MatPower(const Matrix_t *mat, long n);
void MatPrint(const char *name, const Matrix_t *m);
Matrix_t *MatRead(FILE *f);
int MatSave(const Matrix_t *mat, const char *fn);
FEL MatTrace(const Matrix_t *mat);
Matrix_t *MatTransposed(const Matrix_t *src);
int MatWrite(const Matrix_t *mat, FILE *f);

/* For internal use only */
void Mat_DeletePivotTable(Matrix_t *mat);



/* ------------------------------------------------------------------
   Greased matrices
   ------------------------------------------------------------------ */

typedef struct {
    long ***tabs; 
    int *nrvals;  
    int nrtabs;   
} GrExtractionTable_t;

const GrExtractionTable_t *GrGetExtractionTable(int fl,int grrows);


typedef struct
{
    unsigned long Magic; 
    int Field;                  
    int Nor;                    
    int Noc;                    
    int GrRows;                 
    int GrBlockSize;    
    int NumVecs;                
    PTR PrecalcData;    
    const GrExtractionTable_t *ExtrTab;         
    int MPB;                    
} GreasedMatrix_t;

void GrMapRow(PTR v,GreasedMatrix_t *M, PTR w);
GreasedMatrix_t *GrMatAlloc(const Matrix_t *m, int gr_rows);
int GrMatFree(GreasedMatrix_t *mat);
int GrMatIsValid(const GreasedMatrix_t *mat);

/* ------------------------------------------------------------------
   Permutations
   ------------------------------------------------------------------ */

typedef struct
{
    unsigned long Magic;  
    int Degree;           
    long *Data;           
} Perm_t;


Perm_t *PermAlloc(int deg);
int PermCompare(const Perm_t *a, const Perm_t *b);
Perm_t *PermDup(const Perm_t *src);
int PermFree(Perm_t *p);
Perm_t *PermInverse(const Perm_t *src);
int PermIsValid(const Perm_t *p);
Perm_t *PermLoad(const char *fn);
Perm_t *PermMul(Perm_t *dest, const Perm_t *src);
int PermOrder(const Perm_t *perm);
void PermPrint(const char *name, const Perm_t *perm);
Perm_t *PermPower(const Perm_t *p, int n);
Perm_t *PermRead(FILE *f);
int PermSave(const Perm_t *perm, const char *fn);
int PermWrite(const Perm_t *perm, FILE *f);

void Perm_ConvertOld(long *data, int len);

/* ------------------------------------------------------------------
   Polynomials
   ------------------------------------------------------------------ */

typedef struct
{
    unsigned long Magic;
    int Field;          
    int Degree;         
    FEL *Data;          
    int BufSize;        
}
Poly_t;


Poly_t *PolAdd(Poly_t *dest, const Poly_t *src);
Poly_t *PolAlloc(int fl, int n);
int PolCompare(const Poly_t *a, const Poly_t *b);
Poly_t *PolDerive(Poly_t *pol);
Poly_t *PolDivMod(Poly_t *a, const Poly_t *b);
Poly_t *PolDup(const Poly_t *p);
int PolFree(Poly_t *p);
Poly_t *PolGcd(const Poly_t *a, const Poly_t *b);
int PolGcdEx(const Poly_t *a, const Poly_t *b, Poly_t **result);
int PolIsValid(const Poly_t *p);
Poly_t *PolMod(Poly_t *a, const Poly_t *b);
void Pol_Normalize(Poly_t *p);
Poly_t *PolLoad(const char *fn);
Poly_t *PolMul(Poly_t *dest, const Poly_t *src);
void PolPrint(char *name, const Poly_t *p);
Poly_t *PolRead(FILE *f);
int PolSave(const Poly_t *pol, const char *fn);
int PolWrite(const Poly_t *p, FILE *f);

/* ------------------------------------------------------------------
   Factored polynomials
   ------------------------------------------------------------------ */

typedef struct
{
    unsigned long Magic;
    int NFactors;       
    int BufSize;        
    Poly_t **Factor;    
    int *Mult;          
} FPoly_t;

FPoly_t *FpAlloc();
int FpFree(FPoly_t *x);
int FpIsValid(const FPoly_t *p);
FPoly_t *FpMul(FPoly_t *dest, const FPoly_t *src);
FPoly_t *FpMulP(FPoly_t *dest, const Poly_t *src, int pwr);
int FpPrint(const char *name, const FPoly_t *p);

/* ---------------------------------------------------------------------------------------------- */

typedef struct
{
    unsigned long Magic;  
    int Size;             
    int BufSize;          
    long Data[1];         
} BitString_t;            
BitString_t *BsAlloc(int size);
int BsAnd(BitString_t *dest, const BitString_t *src);
int BsClear(BitString_t *bs, int i);
int BsClearAll(BitString_t *bs);
int BsCompare(const BitString_t *a, const BitString_t *b);
BitString_t *BsCopy(BitString_t *dest, const BitString_t *src);
BitString_t *BsDup(const BitString_t *src);
int BsFree(BitString_t *bs);
int BsIntersectionCount(const BitString_t *a, const BitString_t *b);
int BsIsSub(const BitString_t *a, const BitString_t *b);
int BsIsValid(const BitString_t *bs);
int BsMinus(BitString_t *dest, const BitString_t *src);
int BsOr(BitString_t *dest, const BitString_t *src);
void BsPrint(const char *name, const BitString_t *bs);
BitString_t *BsRead(FILE *f);
int BsSet(BitString_t *bs, int i);
int BsTest(const BitString_t *bs, int i);
int BsWrite(BitString_t *bs, FILE *f);

#ifndef DEBUG

#define BS_BPL (sizeof(long) * 8)
#define BsSet(bs,i) ((bs)->Data[(i) / BS_BPL] |= 1L << ((i) % BS_BPL))
#define BsClear(bs,i) ((bs)->Data[(i) / BS_BPL] &= ~(1L << ((i) % BS_BPL)))
#define BsTest(bs,i) (((bs)->Data[(i) / BS_BPL] & (1L << ((i) % BS_BPL))) != 0 ? 1 : 0)

#endif


/* ------------------------------------------------------------------
   Sets
   ------------------------------------------------------------------ */

typedef struct
{
    unsigned long Magic;        
    int Size;                   
    int BufSize;                
    long *Data;                 
} Set_t;


Set_t *SetAlloc();
int SetContains(const Set_t *set, long elem);
Set_t *SetDup(const Set_t *s);
int SetFree(Set_t *x);
int SetInsert(Set_t *set, long elem);
int SetIsValid(const Set_t *s);
int SetPrint(char *name, const Set_t *s);


/* ------------------------------------------------------------------
   Integer matrices
   ------------------------------------------------------------------ */

typedef struct
{
    unsigned long Magic;
    int Nor;    
    int Noc;    
    long *Data; 
} IntMatrix_t;

IntMatrix_t *ImatAlloc(int nor, int noc);
int ImatFree(IntMatrix_t *mat);
int ImatIsValid(const IntMatrix_t *m);
IntMatrix_t *ImatLoad(const char *fn);
IntMatrix_t *ImatRead(FILE *f);
int ImatSave(const IntMatrix_t *mat, const char *file_name);
int ImatWrite(const IntMatrix_t *mat, FILE *f);


/* --------------------------------------------------------------------------
   Polymorphic objects
   -------------------------------------------------------------------------- */

void *XDup(void *a);
int XIsCompatible(void *a, void *b);
void XFree(void *a);
void *XInverse(void *a);
void *XLoad(const char *fn);
void XMul(void *a, void *b);
long XOrder(void *a);
void *XPower(void *a, int n);
int XSave(void *a, const char *fn);







/* --------------------------------------------------------------------------
   Matrix sets
   -------------------------------------------------------------------------- */

typedef struct
{
    Matrix_t *Matrix;
    int PivRow;
    int PivCol;
    FEL PivMark;
} MatrixSetElement_t;


typedef struct {
    unsigned long Magic;
    int Len;
    MatrixSetElement_t *List;
} MatrixSet_t;

MatrixSet_t *MsAlloc();
int MsClean(const MatrixSet_t *set, Matrix_t *mat);
int MsCleanAndAppend(MatrixSet_t *set, Matrix_t *mat);
int MsFree(MatrixSet_t *set);
int MsIsValid(const MatrixSet_t *set);



/* --------------------------------------------------------------------------
   Matrix representations
   -------------------------------------------------------------------------- */

typedef struct
{
    unsigned long Magic;
    int NGen;
    Matrix_t **Gen;
} MatRep_t;

#define MR_COPY_GENERATORS  0x0001

int MrAddGenerator(MatRep_t *rep, Matrix_t *gen, int flags);
MatRep_t *MrAlloc(int ngen, Matrix_t **gen, int flags);
int MrChangeBasis(MatRep_t *rep, const Matrix_t *trans);
int MrIsValid(const MatRep_t *rep);
int MrFree(MatRep_t *rep);
MatRep_t *MrLoad(const char *basename, int ngen);
int MrSave(const MatRep_t *rep, const char *basename);
MatRep_t *MrTransposed(const MatRep_t *rep);



/* ------------------------------------------------------------------
   The word generator
   ------------------------------------------------------------------ */

typedef struct
{
    const MatRep_t *Rep;        
    Matrix_t *Basis[8];         
    int N2[8];                  
    int *Description;           
} WgData_t;


WgData_t *WgAlloc(const MatRep_t *rep);
int *WgDescribeWord(WgData_t *b, long n);
int WgFree(WgData_t *b);
Matrix_t *WgMakeWord(WgData_t *b, long n);
void WgMakeFingerPrint(WgData_t *b, int fp[6]);
const char *WgSymbolicName(WgData_t *b, long n);





/* ------------------------------------------------------------------
   Spin-up, Split, Quotients, etc.
   ------------------------------------------------------------------ */

#define SF_FIRST        0x0001  /* Try only the first seed vector */
#define SF_EACH         0x0002  /* Try each seed vector */
#define SF_MAKE         0x0004  /* Try all 1-dimensional subspaces */
#define SF_SUB          0x0010  /* Try until finding a proper subspace */
#define SF_CYCLIC       0x0020  /* Try until finding a cyclic vector */
#define SF_COMBINE      0x0040  /* Combine the spans */
#define SF_SEED_MASK    0x000F
#define SF_MODE_MASK    0x00F0
#define SF_STD          0x0100  /* Spin up 'canonically' */

Matrix_t *QProjection(const Matrix_t *subspace, const Matrix_t *vectors);
Matrix_t *QAction(const Matrix_t *sub, const Matrix_t *gen);
Matrix_t *SAction(const Matrix_t *sub, const Matrix_t *gen);

typedef struct
{
    int MaxSubspaceDimension;
    int MaxTries;
    int Result;
} SpinUpInfo_t;

int SpinUpInfoInit(SpinUpInfo_t *info);
Matrix_t *SpinUp(const Matrix_t *seed, const MatRep_t *rep, int flags,
    IntMatrix_t **script, SpinUpInfo_t *info);
Matrix_t *SpinUpWithScript(const Matrix_t *seed, const MatRep_t *rep,
    const IntMatrix_t *script);
int Split(Matrix_t *subspace, const MatRep_t *rep,
          MatRep_t **sub, MatRep_t **quot);

int ConvertSpinUpScript(IntMatrix_t *script);

Matrix_t *SpinUpWithPermutations(const Matrix_t *seed, int ngen,
    const Perm_t **gen, int flags, IntMatrix_t **script, SpinUpInfo_t *info);


/* ------------------------------------------------------------------
   Seed vector generator
   ------------------------------------------------------------------ */

long MakeSeedVector(const Matrix_t *basis, long lastno, PTR vec);



/* ------------------------------------------------------------------
   Miscellaneous algorithms
   ------------------------------------------------------------------ */

Matrix_t *MatInsert_(Matrix_t *mat, const Poly_t *pol);
Matrix_t *MatInsert(const Matrix_t *mat, const Poly_t *pol);
int IsSubspace(const Matrix_t *sub, const Matrix_t *space, int ngen);

Matrix_t *MatTensor(const Matrix_t *m1, const Matrix_t *m2);
int MatrixToVector(const Matrix_t *mat, Matrix_t *vecs, int n);
Matrix_t *VectorToMatrix(Matrix_t *vecs, int n, int noc);
Matrix_t *TensorMap(Matrix_t *vec, const Matrix_t *a, const Matrix_t *b);

int StablePower(const Matrix_t *mat, int *pwr, Matrix_t **ker);
int StablePower_(Matrix_t *mat, int *pwr, Matrix_t **ker);



/* ------------------------------------------------------------------
   Polynomial factorization (Berlekamp algorithm)
   ------------------------------------------------------------------ */

FPoly_t *Factorization(const Poly_t *pol);



/* ------------------------------------------------------------------
   Characteristic and minimal polynomials (charpol.c, minpol.c)
   ------------------------------------------------------------------ */

extern long CharPolSeed;
Poly_t *CharPolFactor(const Matrix_t *mat);
FPoly_t *CharPol(const Matrix_t *mat);
Poly_t *MinPolFactor(Matrix_t *mat);
FPoly_t *MinPol(Matrix_t *mat);



/* ------------------------------------------------------------------
   The lattice package
   ------------------------------------------------------------------ */
#define MAXGEN 20       /* Max. number of generators */
#define LAT_MAXCF 200   /* Max. number of composition factors */
#define MAXCYCL 30000   /* Max. number of cyclic submodules */
#define MAXDOTL 90000   /* Max. number of dotted lines */
#define MAXNSUB 20000   /* Max. number of submodules */
#define LAT_MAXBASENAME 100

typedef struct
{
    long dim, num, mult;
    long idword;                
    Poly_t *idpol;
    long peakword;              
    Poly_t *peakpol;
    long nmount;                
    long ndotl;                 
    long spl;                   
}
CfInfo;

typedef struct
{
    char BaseName[LAT_MAXBASENAME];     
    int Field;                          
    int NGen;                           
    int NCf;                            
    CfInfo Cf[LAT_MAXCF];               
    int NSocles;                        
    int *Socle;                         
    int NHeads;                         
    int *Head;                          
} Lat_Info;

int Lat_ReadInfo(Lat_Info *li, const char *basename);
int Lat_WriteInfo(const Lat_Info *li);
const char *Lat_CfName(const Lat_Info *li, int cf);
int Lat_AddHead(Lat_Info *li, int *mult);
int Lat_AddSocle(Lat_Info *li, int *mult);


#define LAT_RG_INVERT           0x0001  /* Invert generators */
#define LAT_RG_TRANSPOSE        0x0002  /* Transpose generators */
#define LAT_RG_STD              0x0004  /* Use standard form */

MatRep_t *Lat_ReadCfGens(Lat_Info *info, int cf, int flags);

/* ------------------------------------------------------------------
   Tensor condensation package
   ------------------------------------------------------------------ */

typedef struct
{
    char NameM[LAT_MAXBASENAME];        
    char NameN[LAT_MAXBASENAME];        
    int Dim;                            
    int NCf;                            
    int CfIndex[2][LAT_MAXCF];          
} TkData_t;

int TK_ReadInfo(TkData_t *tki, const char *name);
int TK_WriteInfo(TkData_t *tki, const char *name);




/* !!!!!!!!!!!!!!! 2.3 STUFF below !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
/* !!!!!!!!!!!!!!! 2.3 STUFF below !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
/* !!!!!!!!!!!!!!! 2.3 STUFF below !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */



/* ------------------------------------------------------------------
   Return codes
   ------------------------------------------------------------------ */

#define EXIT_OK         0       /* Exit code: normal end */
#define EXIT_ERR        1       /*            error */



/* ------------------------------------------------------------------
   Function operating on representations and vector spaces
   ------------------------------------------------------------------ */

int IsIsomorphic(const MatRep_t *rep1, const CfInfo *info1,
    const MatRep_t *rep2, Matrix_t  **trans, int use_pw);
int MakeEndomorphisms(const MatRep_t *rep, const Matrix_t *nsp,
    Matrix_t *endo[]);
Matrix_t *HomogeneousPart(MatRep_t *m, MatRep_t *s, Matrix_t *npw,
    const IntMatrix_t *op, int dimends);



/* ------------------------------------------------------------------
   Lattice drawing functions
   ------------------------------------------------------------------ */

typedef struct
{
    double PosX, PosY;          /* Position [0..1] */
    unsigned long UserData;     /* User-defined attributes */
    int Layer;                  /* Layer number */
    double Score;               /* Used in optimization */
    int ScoreCount;
} LdNode_t;

typedef struct
{
    int NNodes;
    LdNode_t *Nodes;
    int *IsSub;         /* Incidence relation, <NNodes> * <NNodes> entries */
    int *LayerNo;       /* Layer numbers */
    int NLayers;
} LdLattice_t;

#define LD_ISSUB(l,i,k) ((l)->IsSub[(i) * (l)->NNodes + (k)])

LdLattice_t *LdAlloc(int num_nodes);
int LdFree(LdLattice_t *l);
int LdAddIncidence(LdLattice_t *lat, int sub, int sup);
int LdSetPositions(LdLattice_t *l);

int ChangeBasis(const Matrix_t *M, int ngen, const Matrix_t *gen[],
        Matrix_t *newgen[]);


#endif  /* !defined(_MEATAXE_H_) */