MeatAxe  2.4
meataxe.h
1 /* ============================= C MeatAxe ==================================
2  File: $Id: meataxe.h,v 1.3 2007-09-03 21:35:22 mringe Exp $
3  Comment: MeatAxe library external interfaces.
4  --------------------------------------------------------------------------
5  (C) Copyright 2004 Michael Ringe, Lehrstuhl D fuer Mathematik,
6  RWTH Aachen, Germany <mringe@math.rwth-aachen.de>
7  This program is free software; see the file COPYING for details.
8  ========================================================================== */
9 
10 #ifndef MEATAXE_H_INCLUDED
11 #define MEATAXE_H_INCLUDED
12 
13 #include <stdio.h>
14 #include <stdarg.h>
15 
16 #define MTX_VERSION "2.4"
17 
18 #if defined GCC
19 #define MTX_PRINTF_ATTRIBUTE(f,v) __attribute__((format(printf,f,v)))
20 #else
21 #define MTX_PRINTF_ATTRIBUTE(f,v)
22 #endif
23 
24 extern char *MtxVersion;
30 #define FM_READ 0x01
31 #define FM_CREATE 0x02
32 #define FM_APPEND 0x03
33 #define FM_TEXT 0x10
34 #define FM_LIB 0x20
35 #define FM_NOERROR 0x40
36 
40 int SysCreateDirectory(const char *name);
41 int SysGetPid();
42 void SysInit(void);
43 void *SysMalloc(size_t nbytes);
44 FILE *SysFopen(const char *name, int mode);
45 void SysFree(void *x);
46 int SysFseek(FILE *f,long pos);
47 int SysFseekRelative(FILE *file, long distance);
48 void *SysRealloc(void *buf, size_t nbytes);
49 int SysReadLong32(FILE *f, long *buf, int n);
50 #define SysReadLong SysReadLong32
51 int SysReadLongX(FILE *f, long *buf, int n);
52 int SysRemoveDirectory(const char *name);
53 int SysRemoveFile(const char *name);
54 void SysSetTimeLimit(long nsecs);
55 long SysTimeUsed(void);
56 int SysWriteLong32(FILE *f, const long *buf, int n);
57 #define SysWriteLong SysWriteLong32
58 int SysWriteLongX(FILE *f, const long *buf, int n);
59 
60 #define ALLOC(type) ((type *) SysMalloc(sizeof(type)))
61 #define NALLOC(type,n) ((type *) SysMalloc((size_t)(n) * sizeof(type)))
62 #define NREALLOC(x,type,n)\
63  ((type *) SysRealloc(x,(size_t)(n) * sizeof(type)))
64 #define FREE(x) SysFree(x)
65 
70 /* ---------------------------------------------------------------------------------------------- */
71 
77 /* Data types and constants
78  ------------------------ */
79 
80 #if ZZZ==0
81 
82 typedef unsigned char FEL;
83 typedef FEL *PTR;
84 #define FF_ZERO ((FEL)0)
85 #define FF_ONE ((FEL)1)
86 #define ZZZVERSION 6
87 
88 #elif ZZZ==1
89 
90 typedef unsigned short FEL;
91 typedef unsigned short *PTR;
92 #define FF_ZERO ((FEL)0xFFFF)
93 #define FF_ONE ((FEL)0)
94 #define ZZZVERSION 0x101
95 
96 #else
97 
98 #error "ZZZ undefined"
99 
100 #endif
101 
102 /* Kernel variables and functions
103  ------------------------------ */
104 
105 extern int FfOrder;
106 extern int FfChar;
107 extern FEL FfGen;
108 extern int FfNoc;
109 extern size_t FfCurrentRowSize;
110 
111 
112 /* Arithmetic */
113 FEL FfAdd(FEL a, FEL b);
114 FEL FfSub(FEL a, FEL b);
115 FEL FfMul(FEL a, FEL b);
116 FEL FfDiv(FEL a, FEL b);
117 FEL FfNeg(FEL a);
118 FEL FfInv(FEL a);
119 
120 int FfMakeTables(int field);
121 int FfSetField(int field);
122 int FfSetNoc(int noc);
123 
124 
125 void FfAddMulRow(PTR dest, PTR src, FEL f);
126 PTR FfAddRow(PTR dest, PTR src);
127 PTR FfAddRowPartial(PTR dest, PTR src, int first, int len);
128 PTR FfAlloc(int nor);
129 int FfCmpRows(PTR p1, PTR p2);
130 void FfCleanRow(PTR row, PTR matrix, int nor, const int *piv);
131 void FfCleanRow2(PTR row, PTR matrix, int nor, const int *piv, PTR row2);
132 void FfCleanRowAndRepeat(PTR row, PTR mat, int nor, const int *piv,
133  PTR row2, PTR mat2);
134 void FfCopyRow(PTR dest, PTR src);
135 FEL FfEmbed(FEL a, int subfield);
136 FEL FfExtract(PTR row, int col);
137 void FfExtractColumn(PTR mat,int nor,int col,PTR result);
138 int FfFindPivot(PTR row, FEL *mark);
139 void FfFree(PTR x);
140 FEL FfFromInt(int l);
141 PTR FfGetPtr(PTR base, int row);
142 void FfInsert(PTR row, int col, FEL mark);
143 void FfMulRow(PTR row, FEL mark);
144 FILE *FfReadHeader(const char *name, int *fld, int *nor, int *noc);
145 int FfReadRows(FILE *f, PTR buf, int n);
146 FEL FfRestrict(FEL a, int subfield);
147 size_t FfRowSize(int noc);
148 FEL FfScalarProduct(PTR a, PTR b);
149 int FfSeekRow(FILE *f, int pos);
150 int FfStepPtr(PTR *x);
151 void FfSwapRows(PTR dest, PTR src);
152 const char *FfToGap(FEL f);
153 int FfToInt(FEL f);
154 size_t FfTrueRowSize(int noc);
155 FILE *FfWriteHeader(const char *name, int fld, int nor, int noc);
156 int FfWriteRows(FILE *f, PTR buf, int n);
157 
158 
159 /* --------------------------------------------------------------------------
160  Macro versions of kernel functions
161  -------------------------------------------------------------------------- */
162 
163 
164 #if ZZZ==0
165 
166 extern FEL mtx_tmult[256][256];
167 extern FEL mtx_tadd[256][256];
168 extern FEL mtx_taddinv[256], mtx_tmultinv[256];
169 extern FEL mtx_tffirst[256][2];
170 extern FEL mtx_textract[8][256];
171 extern FEL mtx_tnull[8][256];
172 extern FEL mtx_tinsert[8][256];
173 extern long mtx_embedord[4];
174 extern FEL mtx_embed[4][16];
175 extern FEL mtx_restrict[4][256];
176 
177 #define FfAdd(a,b) ((FEL)mtx_tadd[(int)(unsigned char)a][(int)(unsigned char)b])
178 #define FfDiv(a,b) FfMul((a),FfInv(b))
179 #define FfInv(a) (mtx_tmultinv[(int)(unsigned char)a])
180 #define FfMul(a,b) ((FEL)mtx_tmult[(int)(unsigned char)a][(int)(unsigned char)b])
181 #define FfNeg(a) (mtx_taddinv[(int)(unsigned char)a])
182 #define FfSub(a,b) FfAdd((a),FfNeg(b))
183 
184 #elif ZZZ==1
185 
186 #define FfExtract(row,col) ((FEL)((row)[(col)-1]))
187 #define FfInsert(row,col,mark) ((void)((row)[(col)-1] = mark))
188 
189 
190 #endif
191 
194 /* ------------------------------------------------------------------
195  Other low-level functions (zzz2.c)
196  ------------------------------------------------------------------ */
197 
198 void FfMapRow(PTR row, PTR matrix, int nor, PTR result);
199 void FfPermRow(PTR row, const long *perm, PTR result);
200 int FfSumAndIntersection(PTR wrk1, int *nor1, int *nor2, PTR wrk2, int *piv);
201 
202 
203 /* ------------------------------------------------------------------
204  Library initialization and cleanup
205  ------------------------------------------------------------------ */
206 
207 extern int Mtx_IsInitialized;
208 extern int Mtx_IsX86;
209 extern int MtxOpt_UseOldWordGenerator;
210 
211 int MtxInitLibrary();
212 void MtxCleanupLibrary();
213 
214 
228 typedef struct {
229  char *S; /* pointer to NUL terminated string */
230 } String;
231 
232 String StrAlloc(size_t initial_capacity);
233 void StrFree(String *s);
234 void StrAppend(String *s, const char *text);
235 MTX_PRINTF_ATTRIBUTE(2,3)
236 void StrAppendF(String *s, const char *fmt, ...);
237 MTX_PRINTF_ATTRIBUTE(2,3)
238 void StrPrintF(String *s, const char *fmt, ...);
239 
245 /* ------------------------------------------------------------------
246  Application framework
247  ------------------------------------------------------------------ */
248 
249 extern char MtxBinDir[]; /* MeatAxe library directory */
250 extern char MtxLibDir[]; /* MeatAxe program directory */
251 
252 #define APP_MAX_ARGS 50
253 
275 typedef struct
276 {
277  const char *Name;
278  const char *Description;
279  const char *Help;
281 
282 
283 
284 
291 typedef struct
292 {
294  int OrigArgC;
295  const char **OrigArgV;
296  int ArgC;
297  const char **ArgV;
298  int OptEnd;
299  unsigned long IsDone[APP_MAX_ARGS];
300  const char *OptArg;
301  int OptInd;
302  char TempDirName[200];
304 
305 
306 MtxApplication_t *AppAlloc(MtxApplicationInfo_t const *ai, int argc, const char **argv);
307 int AppFree(MtxApplication_t *a);
308 int AppGetOption(MtxApplication_t *app, const char *spec);
309 int AppGetCountedOption(MtxApplication_t *app, const char *spec);
310 const char *AppGetTextOption(MtxApplication_t *app, const char *spec,
311  const char *dflt);
312 int AppGetIntOption(MtxApplication_t *app, const char *spec, int dflt,
313  int min, int max);
314 int AppGetArguments(MtxApplication_t *app, int min_argc, int max_argc);
315 const char *AppCreateTempDir(MtxApplication_t *app);
316 
317 #define MTX_COMMON_OPTIONS_SYNTAX \
318  "[<Options>]"
319 
320 #define MTX_COMMON_OPTIONS_DESCRIPTION \
321  " -Q ...................... Quiet, no messages\n" \
322  " -V ...................... Verbose, more messages\n" \
323  " -T <MaxTime> ............ Set CPU time limit [s]\n"
324 
325 
326 /* ------------------------------------------------------------------
327  Messages and error handling
328  ------------------------------------------------------------------ */
329  /* Error message codes (%E arguments) */
330 #define MTX_ERR_NOMEM 1 /* Not enough memory */
331 #define MTX_ERR_GAME_OVER 2 /* Time limit exceeded */
332 #define MTX_ERR_DIV0 8 /* Division by 0 or singular Matrix */
333 #define MTX_ERR_FILEFMT 24 /* Bad format */
334 #define MTX_ERR_BADARG 31 /* Bad argument */
335 #define MTX_ERR_RANGE 33 /* Out of range */
336 #define MTX_ERR_NOTECH 34 /* Matrix not in chelon form */
337 #define MTX_ERR_NOTSQUARE 35 /* Matrix not square */
338 #define MTX_ERR_INCOMPAT 36 /* Arguments are incompatible */
339 #define MTX_ERR_BADUSAGE 41 /* Bad command line */
340 #define MTX_ERR_OPTION 42 /* Bad usage of option */
341 #define MTX_ERR_NARGS 43 /* Bad number of arguments */
342 #define MTX_ERR_NOTMATRIX 51 /* Not a matrix */
343 #define MTX_ERR_NOTPERM 53 /* Not a permutation */
344 
345 
346 
350 typedef struct { const char *Name; const char *BaseName; } MtxFileInfo_t;
351 
355 typedef struct { const MtxFileInfo_t *FileInfo; int LineNo; const char *Text; }
357 
358 typedef void MtxErrorHandler_t(const MtxErrorRecord_t *);
359 
360 #define MTX_DEFINE_FILE_INFO \
361  static MtxFileInfo_t Mtx_ThisFile = { __FILE__, NULL };
362 
363 int MtxError(MtxFileInfo_t *fi, int line, const char *text, ...);
364 MtxErrorHandler_t *MtxSetErrorHandler(MtxErrorHandler_t *h);
365 
366 
367 #define MTX_ERROR(msg) MtxError(&Mtx_ThisFile,__LINE__,msg)
368 #define MTX_ERROR1(msg,a1) MtxError(&Mtx_ThisFile,__LINE__,msg,a1)
369 #define MTX_ERROR2(msg,a1,a2) MtxError(&Mtx_ThisFile,__LINE__,msg,a1,a2)
370 #define MTX_ERROR3(msg,a1,a2,a3) MtxError(&Mtx_ThisFile,__LINE__,msg,a1,a2,a3)
371 #define MTX_ERROR4(msg,a1,a2,a3,a4) MtxError(&Mtx_ThisFile,__LINE__,\
372  msg,a1,a2,a3,a4)
373 #define MTX_ERROR5(msg,a1,a2,a3,a4,a5) MtxError(&Mtx_ThisFile,__LINE__,\
374  msg,a1,a2,a3,a4,a5)
375 #define MTX_ERROR7(msg,a1,a2,a3,a4,a5,a6,a7) MtxError(&Mtx_ThisFile,__LINE__,\
376  msg,a1,a2,a3,a4,a5,a6,a7)
377 
378 
379 #define MTX_VERIFY(e) ((void)((e) ||\
380  MtxError(&Mtx_ThisFile,__LINE__,"Assertion failed: %s",#e)))
381 
382 #ifdef _DEBUG
383 #define DEBUG 1
384 #endif
385 
386 #ifdef DEBUG
387 #define MTX_ASSERT(e) MTX_VERIFY(e)
388 #else
389 #define MTX_ASSERT(e)
390 #undef PARANOID
391 #endif
392 
393 
394 
395 /* ------------------------------------------------------------------
396  Messages
397  ------------------------------------------------------------------ */
398 
399 int MtxFormatMessage(char *buf, int bufsize, const char *msg, va_list al);
400 int MtxPrintMessage(FILE *f, const char *fmt, ...);
401 
402 extern int MtxMessageLevel;
403 #define MSG0 (MtxMessageLevel >= 0)
404 #define MSG1 (MtxMessageLevel >= 1)
405 #define MSG2 (MtxMessageLevel >= 2)
406 #define MSG3 (MtxMessageLevel >= 3)
407 #define MSG4 (MtxMessageLevel >= 4)
408 #define MESSAGE(level,args)\
409  (MtxMessageLevel>=(level) ? ( printf args , fflush(stdout), 1) : 0 )
410 
411 
412 /* ------------------------------------------------------------------
413  Miscellaneous
414  ------------------------------------------------------------------ */
415 
416 void MtxRandomInit(unsigned seed);
417 long int MtxRandom(void);
418 int MtxRandomInt(int max);
419 long gcd(long a, long b);
420 long lcm(long a, long b);
421 
422 
423 /* ------------------------------------------------------------------
424  Structured text files (stfXXX.c)
425  ------------------------------------------------------------------ */
426 
431 typedef struct
432 {
433  FILE *File;
434  char *LineBuf;
435  char *GetPtr;
437  int OutPos;
438  int LineNo;
439 } StfData;
440 
441 int StfClose(StfData *f);
442 StfData *StfOpen(const char *name, int mode);
443 
444 int StfPut(StfData *f, const char *text);
445 int StfPutInt(StfData *f, int value);
446 int StfPutString(StfData *f, const char *text);
447 int StfPutVector(StfData *f, int size, const int *value);
448 int StfBeginEntry(StfData *f, const char *name);
449 int StfEndEntry(StfData *f);
450 int StfWriteValue(StfData *f, const char *name, const char *value);
451 int StfWriteInt(StfData *f, const char *name, int value);
452 int StfWriteString(StfData *f, const char *name, const char *value);
453 int StfWriteVector(StfData *f, const char *name, int size, const int *value);
454 
455 int StfReadLine(StfData *f);
456 const char *StfGetName(StfData *f);
457 int StfGetInt(StfData *f, int *buf);
458 int StfGetString(StfData *f, char *buf, size_t bufsize);
459 int StfMatch(StfData *f, const char *pattern);
460 int StfGetVector(StfData *f, int *bufsize, int *buf);
461 
462 
463 /* ------------------------------------------------------------------
464  MeatAxe files
465  ------------------------------------------------------------------ */
466 
470 typedef struct
471 {
472  unsigned long Magic;
473  int Field;
474  int Nor;
475  int Noc;
476  FILE *File;
477  char *Name;
478 } MtxFile_t;
479 
480 int MfIsValid(const MtxFile_t *file);
481 MtxFile_t *MfOpen(const char *name);
482 MtxFile_t *MfCreate(const char *name, int field, int nor, int noc);
483 int MfClose(MtxFile_t *file);
484 int MfReadLong(MtxFile_t *f, long *buf, int nrows);
485 int MfReadRows(MtxFile_t *f, PTR buf, int nrows);
486 int MfWriteLong(MtxFile_t *f, const long *buf, int count);
487 int MfWriteRows(MtxFile_t *f, PTR buf, int nrows);
488 
489 
490 /* ---------------------------------------------------------------------------------------------- */
491 
492 typedef struct
493 {
494  unsigned long Magic;
495  int Field;
496  int Nor;
497  int Noc;
499  size_t RowSize;
500  int *PivotTable;
501 } Matrix_t;
502 
503 Matrix_t *MatAdd(Matrix_t *dest, const Matrix_t *src);
504 Matrix_t *MatAddMul(Matrix_t *dest, const Matrix_t *src, FEL coeff);
505 Matrix_t *MatAlloc(int field, int nor, int noc);
506 int MatClean(Matrix_t *mat, const Matrix_t *sub);
507 int MatCompare(const Matrix_t *a, const Matrix_t *b);
508 int MatCopyRegion(Matrix_t *dest, int destrow, int destcol,
509  const Matrix_t *src, int row1, int col1, int nrows, int ncols);
510 Matrix_t *MatCut(const Matrix_t *src, int row1, int col1, int nrows, int ncols);
511 Matrix_t *MatCutRows(const Matrix_t *src, int row1, int nrows);
512 Matrix_t *MatDup(const Matrix_t *src);
513 int MatEchelonize(Matrix_t *mat);
514 int MatFree(Matrix_t *mat);
515 PTR MatGetPtr(const Matrix_t *mat, int row);
516 Matrix_t *MatId(int fl, int nor);
517 Matrix_t *MatInverse(const Matrix_t *src);
518 int MatIsValid(const Matrix_t *m);
519 Matrix_t *MatLoad(const char *fn);
520 Matrix_t *MatMul(Matrix_t *dest, const Matrix_t *src);
521 Matrix_t *MatMulScalar(Matrix_t *dest, FEL coeff);
522 long MatNullity(const Matrix_t *mat);
523 long MatNullity__(Matrix_t *mat);
524 Matrix_t *MatNullSpace(const Matrix_t *mat);
525 Matrix_t *MatNullSpace_(Matrix_t *mat, int flags);
527 int MatOrder(const Matrix_t *mat);
528 int MatPivotize(Matrix_t *mat);
529 Matrix_t *MatPower(const Matrix_t *mat, long n);
530 void MatPrint(const char *name, const Matrix_t *m);
531 Matrix_t *MatRead(FILE *f);
532 int MatSave(const Matrix_t *mat, const char *fn);
533 FEL MatTrace(const Matrix_t *mat);
534 Matrix_t *MatTransposed(const Matrix_t *src);
535 int MatWrite(const Matrix_t *mat, FILE *f);
536 
537 /* For internal use only */
538 void Mat_DeletePivotTable(Matrix_t *mat);
539 
540 
541 
542 /* ------------------------------------------------------------------
543  Greased matrices
544  ------------------------------------------------------------------ */
545 
551 typedef struct {
552  long ***tabs; /* tables for different remainders
553  of byte numbers mod grrows */
554  int *nrvals; /* number of values produced by each table */
555  int nrtabs; /* number of tables used */
557 
558 const GrExtractionTable_t *GrGetExtractionTable(int fl,int grrows);
559 
560 
565 typedef struct
566 {
567  unsigned long Magic;
568  int Field, Nor, Noc;
569  int GrRows; /* Grease level (# of rows, 0=no grease) */
570  int GrBlockSize; /* Vectors per block (= Field^GrRows) */
571  int NumVecs; /* Total number of vectors in <PrecalcData> */
572  PTR PrecalcData; /* Precalculated data */
573  const GrExtractionTable_t
574  *ExtrTab; /* Extraction table */
575  int MPB; /* Number of marks per byte */
577 
578 void GrMapRow(PTR v,GreasedMatrix_t *M, PTR w);
579 GreasedMatrix_t *GrMatAlloc(const Matrix_t *m, int gr_rows);
580 int GrMatFree(GreasedMatrix_t *mat);
581 int GrMatIsValid(const GreasedMatrix_t *mat);
582 
583 
584 
585 /* ------------------------------------------------------------------
586  Permutations
587  ------------------------------------------------------------------ */
588 
590 typedef struct
591 {
592  unsigned long Magic;
593  int Degree;
594  long *Data;
595 } Perm_t;
596 
597 
598 Perm_t *PermAlloc(int deg);
599 int PermCompare(const Perm_t *a, const Perm_t *b);
600 Perm_t *PermDup(const Perm_t *src);
601 int PermFree(Perm_t *p);
602 Perm_t *PermInverse(const Perm_t *src);
603 int PermIsValid(const Perm_t *p);
604 Perm_t *PermLoad(const char *fn);
605 Perm_t *PermMul(Perm_t *dest, const Perm_t *src);
606 int PermOrder(const Perm_t *perm);
607 void PermPrint(const char *name, const Perm_t *perm);
608 Perm_t *PermPower(const Perm_t *p, int n);
609 Perm_t *PermRead(FILE *f);
610 int PermSave(const Perm_t *perm, const char *fn);
611 int PermWrite(const Perm_t *perm, FILE *f);
612 
613 void Perm_ConvertOld(long *data, int len);
614 
615 /* ------------------------------------------------------------------
616  Polynomials
617  ------------------------------------------------------------------ */
618 
619 typedef struct
620 {
621  unsigned long Magic;
622  int Field;
623  int Degree;
624  FEL *Data;
626  int BufSize;
627 }
628 Poly_t;
629 
630 
631 Poly_t *PolAdd(Poly_t *dest, const Poly_t *src);
632 Poly_t *PolAlloc(int fl, int n);
633 int PolCompare(const Poly_t *a, const Poly_t *b);
634 Poly_t *PolDerive(Poly_t *pol);
635 Poly_t *PolDivMod(Poly_t *a, const Poly_t *b);
636 Poly_t *PolDup(const Poly_t *p);
637 int PolFree(Poly_t *p);
638 Poly_t *PolGcd(const Poly_t *a, const Poly_t *b);
639 int PolGcdEx(const Poly_t *a, const Poly_t *b, Poly_t **result);
640 int PolIsValid(const Poly_t *p);
641 Poly_t *PolMod(Poly_t *a, const Poly_t *b);
642 void Pol_Normalize(Poly_t *p);
643 Poly_t *PolLoad(const char *fn);
644 Poly_t *PolMul(Poly_t *dest, const Poly_t *src);
645 void PolPrint(char *name, const Poly_t *p);
646 Poly_t *PolRead(FILE *f);
647 int PolSave(const Poly_t *pol, const char *fn);
648 int PolWrite(const Poly_t *p, FILE *f);
649 
650 
651 
652 /* ------------------------------------------------------------------
653  Factored polynomials
654  ------------------------------------------------------------------ */
655 
656 typedef struct
657 {
658  unsigned long Magic;
659  int NFactors;
660  int BufSize;
662  int *Mult;
663 } FPoly_t;
664 
665 FPoly_t *FpAlloc();
666 int FpFree(FPoly_t *x);
667 int FpIsValid(const FPoly_t *p);
668 FPoly_t *FpMul(FPoly_t *dest, const FPoly_t *src);
669 FPoly_t *FpMulP(FPoly_t *dest, const Poly_t *src, int pwr);
670 int FpPrint(const char *name, const FPoly_t *p);
671 
672 /* ---------------------------------------------------------------------------------------------- */
673 
674 typedef struct
675 {
676  unsigned long Magic;
677  int Size;
678  int BufSize;
679  long Data[1];
681 } BitString_t;
683 BitString_t *BsAlloc(int size);
684 int BsAnd(BitString_t *dest, const BitString_t *src);
685 int BsClear(BitString_t *bs, int i);
686 int BsClearAll(BitString_t *bs);
687 int BsCompare(const BitString_t *a, const BitString_t *b);
688 BitString_t *BsCopy(BitString_t *dest, const BitString_t *src);
689 BitString_t *BsDup(const BitString_t *src);
690 int BsFree(BitString_t *bs);
691 int BsIntersectionCount(const BitString_t *a, const BitString_t *b);
692 int BsIsSub(const BitString_t *a, const BitString_t *b);
693 int BsIsValid(const BitString_t *bs);
694 int BsMinus(BitString_t *dest, const BitString_t *src);
695 int BsOr(BitString_t *dest, const BitString_t *src);
696 void BsPrint(const char *name, const BitString_t *bs);
697 BitString_t *BsRead(FILE *f);
698 int BsSet(BitString_t *bs, int i);
699 int BsTest(const BitString_t *bs, int i);
700 int BsWrite(BitString_t *bs, FILE *f);
701 
702 #ifndef DEBUG
703 
704 #define BS_BPL (sizeof(long) * 8)
705 #define BsSet(bs,i) ((bs)->Data[(i) / BS_BPL] |= 1L << ((i) % BS_BPL))
706 #define BsClear(bs,i) ((bs)->Data[(i) / BS_BPL] &= ~(1L << ((i) % BS_BPL)))
707 #define BsTest(bs,i) (((bs)->Data[(i) / BS_BPL] & (1L << ((i) % BS_BPL))) != 0 ? 1 : 0)
708 
709 #endif
710 
711 
712 /* ------------------------------------------------------------------
713  Sets
714  ------------------------------------------------------------------ */
715 
716 typedef struct
717 {
718  unsigned long Magic;
719  int Size;
720  int BufSize;
721  long *Data;
722 } Set_t;
723 
724 
725 Set_t *SetAlloc();
726 int SetContains(const Set_t *set, long elem);
727 Set_t *SetDup(const Set_t *s);
728 int SetFree(Set_t *x);
729 int SetInsert(Set_t *set, long elem);
730 int SetIsValid(const Set_t *s);
731 int SetPrint(char *name, const Set_t *s);
732 
733 
734 /* ------------------------------------------------------------------
735  Integer matrices
736  ------------------------------------------------------------------ */
737 
738 typedef struct
739 {
740  unsigned long Magic;
741  int Nor;
742  int Noc;
743  long *Data;
744 } IntMatrix_t;
745 
746 IntMatrix_t *ImatAlloc(int nor, int noc);
747 int ImatFree(IntMatrix_t *mat);
748 int ImatIsValid(const IntMatrix_t *m);
749 IntMatrix_t *ImatLoad(const char *fn);
750 IntMatrix_t *ImatRead(FILE *f);
751 int ImatSave(const IntMatrix_t *mat, const char *file_name);
752 int ImatWrite(const IntMatrix_t *mat, FILE *f);
753 
754 
755 /* --------------------------------------------------------------------------
756  Polymorphic objects
757  -------------------------------------------------------------------------- */
758 
759 void *XDup(void *a);
760 int XIsCompatible(void *a, void *b);
761 void XFree(void *a);
762 void *XInverse(void *a);
763 void *XLoad(const char *fn);
764 void XMul(void *a, void *b);
765 long XOrder(void *a);
766 void *XPower(void *a, int n);
767 int XSave(void *a, const char *fn);
768 
769 
770 
771 
772 
773 
774 
775 /* --------------------------------------------------------------------------
776  Matrix sets
777  -------------------------------------------------------------------------- */
778 
783 typedef struct
784 {
785  Matrix_t *Matrix;
786  int PivRow;
787  int PivCol;
788  FEL PivMark;
790 
791 
795 typedef struct {
796  unsigned long Magic;
797  int Len;
798  MatrixSetElement_t *List;
799 } MatrixSet_t;
800 
802 int MsClean(const MatrixSet_t *set, Matrix_t *mat);
803 int MsCleanAndAppend(MatrixSet_t *set, Matrix_t *mat);
804 int MsFree(MatrixSet_t *set);
805 int MsIsValid(const MatrixSet_t *set);
806 
807 
808 
809 /* --------------------------------------------------------------------------
810  Matrix representations
811  -------------------------------------------------------------------------- */
812 
813 typedef struct
814 {
815  unsigned long Magic;
816  int NGen;
817  Matrix_t **Gen;
818 } MatRep_t;
819 
820 #define MR_COPY_GENERATORS 0x0001
821 
822 int MrAddGenerator(MatRep_t *rep, Matrix_t *gen, int flags);
823 MatRep_t *MrAlloc(int ngen, Matrix_t **gen, int flags);
824 int MrChangeBasis(MatRep_t *rep, const Matrix_t *trans);
825 int MrIsValid(const MatRep_t *rep);
826 int MrFree(MatRep_t *rep);
827 MatRep_t *MrLoad(const char *basename, int ngen);
828 int MrSave(const MatRep_t *rep, const char *basename);
829 MatRep_t *MrTransposed(const MatRep_t *rep);
830 
831 
832 
833 /* ------------------------------------------------------------------
834  The word generator
835  ------------------------------------------------------------------ */
836 
837 typedef struct
838 {
839  const MatRep_t *Rep;
840  Matrix_t *Basis[8];
841  int N2[8];
842  int *Description;
843 } WgData_t;
844 
845 
846 WgData_t *WgAlloc(const MatRep_t *rep);
847 int *WgDescribeWord(WgData_t *b, long n);
848 int WgFree(WgData_t *b);
849 Matrix_t *WgMakeWord(WgData_t *b, long n);
850 void WgMakeFingerPrint(WgData_t *b, int fp[6]);
851 const char *WgSymbolicName(WgData_t *b, long n);
852 
853 
854 
855 
856 
857 /* ------------------------------------------------------------------
858  Spin-up, Split, Quotients, etc.
859  ------------------------------------------------------------------ */
860 
861 #define SF_FIRST 0x0001 /* Try only the first seed vector */
862 #define SF_EACH 0x0002 /* Try each seed vector */
863 #define SF_MAKE 0x0004 /* Try all 1-dimensional subspaces */
864 #define SF_SUB 0x0010 /* Try until finding a proper subspace */
865 #define SF_CYCLIC 0x0020 /* Try until finding a cyclic vector */
866 #define SF_COMBINE 0x0040 /* Combine the spans */
867 #define SF_SEED_MASK 0x000F
868 #define SF_MODE_MASK 0x00F0
869 #define SF_STD 0x0100 /* Spin up 'canonically' */
870 
871 Matrix_t *QProjection(const Matrix_t *subspace, const Matrix_t *vectors);
872 Matrix_t *QAction(const Matrix_t *sub, const Matrix_t *gen);
873 Matrix_t *SAction(const Matrix_t *sub, const Matrix_t *gen);
874 
875 typedef struct
876 {
877  int MaxSubspaceDimension;
878  int MaxTries;
879  int Result;
880 } SpinUpInfo_t;
881 
882 int SpinUpInfoInit(SpinUpInfo_t *info);
883 Matrix_t *SpinUp(const Matrix_t *seed, const MatRep_t *rep, int flags,
884  IntMatrix_t **script, SpinUpInfo_t *info);
885 Matrix_t *SpinUpWithScript(const Matrix_t *seed, const MatRep_t *rep,
886  const IntMatrix_t *script);
887 int Split(Matrix_t *subspace, const MatRep_t *rep,
888  MatRep_t **sub, MatRep_t **quot);
889 
890 int ConvertSpinUpScript(IntMatrix_t *script);
891 
892 Matrix_t *SpinUpWithPermutations(const Matrix_t *seed, int ngen,
893  const Perm_t **gen, int flags, IntMatrix_t **script, SpinUpInfo_t *info);
894 
895 
896 /* ------------------------------------------------------------------
897  Seed vector generator
898  ------------------------------------------------------------------ */
899 
900 long MakeSeedVector(const Matrix_t *basis, long lastno, PTR vec);
901 
902 
903 
904 /* ------------------------------------------------------------------
905  Miscellaneous algorithms
906  ------------------------------------------------------------------ */
907 
908 Matrix_t *MatInsert_(Matrix_t *mat, const Poly_t *pol);
909 Matrix_t *MatInsert(const Matrix_t *mat, const Poly_t *pol);
910 int IsSubspace(const Matrix_t *sub, const Matrix_t *space, int ngen);
911 
912 Matrix_t *MatTensor(const Matrix_t *m1, const Matrix_t *m2);
913 int MatrixToVector(const Matrix_t *mat, Matrix_t *vecs, int n);
914 Matrix_t *VectorToMatrix(Matrix_t *vecs, int n, int noc);
915 Matrix_t *TensorMap(Matrix_t *vec, const Matrix_t *a, const Matrix_t *b);
916 
917 int StablePower(const Matrix_t *mat, int *pwr, Matrix_t **ker);
918 int StablePower_(Matrix_t *mat, int *pwr, Matrix_t **ker);
919 
920 
921 
922 /* ------------------------------------------------------------------
923  Polynomial factorization (Berlekamp algorithm)
924  ------------------------------------------------------------------ */
925 
926 FPoly_t *Factorization(const Poly_t *pol);
927 
928 
929 
930 /* ------------------------------------------------------------------
931  Characteristic and minimal polynomials (charpol.c, minpol.c)
932  ------------------------------------------------------------------ */
933 
934 extern long CharPolSeed;
935 Poly_t *CharPolFactor(const Matrix_t *mat);
936 FPoly_t *CharPol(const Matrix_t *mat);
938 FPoly_t *MinPol(Matrix_t *mat);
939 
940 
941 
942 /* ------------------------------------------------------------------
943  The lattice package
944  ------------------------------------------------------------------ */
950 #define MAXGEN 20 /* Max. number of generators */
951 #define LAT_MAXCF 200 /* Max. number of composition factors */
952 #define MAXCYCL 30000 /* Max. number of cyclic submodules */
953 #define MAXDOTL 90000 /* Max. number of dotted lines */
954 #define MAXNSUB 20000 /* Max. number of submodules */
955 #define LAT_MAXBASENAME 100
956 
957 typedef struct
958 {
959  long dim, num, mult;
960  long idword; /* Identifying word */
961  Poly_t *idpol;
962  long peakword; /* Peak word */
963  Poly_t *peakpol;
964  long nmount; /* Number of mountains */
965  long ndotl; /* Number of dotted lines */
966  long spl; /* Degree of splitting field */
967 }
968 CfInfo;
969 
970 typedef struct
971 {
972  char BaseName[LAT_MAXBASENAME];
973  int Field;
974  int NGen;
975  int NCf;
976  CfInfo Cf[LAT_MAXCF];
977  int NSocles;
978  int *Socle;
979  int NHeads;
980  int *Head;
981 } Lat_Info;
982 
983 int Lat_ReadInfo(Lat_Info *li, const char *basename);
984 int Lat_WriteInfo(const Lat_Info *li);
985 const char *Lat_CfName(const Lat_Info *li, int cf);
986 int Lat_AddHead(Lat_Info *li, int *mult);
987 int Lat_AddSocle(Lat_Info *li, int *mult);
988 
989 
990 #define LAT_RG_INVERT 0x0001 /* Invert generators */
991 #define LAT_RG_TRANSPOSE 0x0002 /* Transpose generators */
992 #define LAT_RG_STD 0x0004 /* Use standard form */
993 
994 MatRep_t *Lat_ReadCfGens(Lat_Info *info, int cf, int flags);
995 
1001 /* ------------------------------------------------------------------
1002  Tensor condensation package
1003  ------------------------------------------------------------------ */
1004 
1013 typedef struct
1014 {
1015  char NameM[LAT_MAXBASENAME];
1016  char NameN[LAT_MAXBASENAME];
1017  int Dim;
1018  int NCf;
1019  int CfIndex[2][LAT_MAXCF];
1020 } TkData_t;
1021 
1022 int TK_ReadInfo(TkData_t *tki, const char *name);
1023 int TK_WriteInfo(TkData_t *tki, const char *name);
1024 
1025 
1026 
1027 
1028 /* !!!!!!!!!!!!!!! 2.3 STUFF below !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
1029 /* !!!!!!!!!!!!!!! 2.3 STUFF below !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
1030 /* !!!!!!!!!!!!!!! 2.3 STUFF below !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
1031 
1032 
1033 
1034 /* ------------------------------------------------------------------
1035  Return codes
1036  ------------------------------------------------------------------ */
1037 
1038 #define EXIT_OK 0 /* Exit code: normal end */
1039 #define EXIT_ERR 1 /* error */
1040 
1041 
1042 
1043 /* ------------------------------------------------------------------
1044  Function operating on representations and vector spaces
1045  ------------------------------------------------------------------ */
1046 
1047 int IsIsomorphic(const MatRep_t *rep1, const CfInfo *info1,
1048  const MatRep_t *rep2, Matrix_t **trans, int use_pw);
1049 int MakeEndomorphisms(const MatRep_t *rep, const Matrix_t *nsp,
1050  Matrix_t *endo[]);
1051 Matrix_t *HomogeneousPart(MatRep_t *m, MatRep_t *s, Matrix_t *npw,
1052  const IntMatrix_t *op, int dimends);
1053 
1054 
1055 
1056 /* ------------------------------------------------------------------
1057  Lattice drawing functions
1058  ------------------------------------------------------------------ */
1059 
1063 typedef struct
1064 {
1065  double PosX, PosY; /* Position [0..1] */
1066  unsigned long UserData; /* User-defined attributes */
1067  int Layer; /* Layer number */
1068  double Score; /* Used in optimization */
1069  int ScoreCount;
1070 } LdNode_t;
1071 
1075 typedef struct
1076 {
1077  int NNodes;
1078  LdNode_t *Nodes;
1079  int *IsSub; /* Incidence relation, <NNodes> * <NNodes> entries */
1080  int *LayerNo; /* Layer numbers */
1081  int NLayers;
1082 } LdLattice_t;
1083 
1084 #define LD_ISSUB(l,i,k) ((l)->IsSub[(i) * (l)->NNodes + (k)])
1085 
1086 LdLattice_t *LdAlloc(int num_nodes);
1087 int LdFree(LdLattice_t *l);
1088 int LdAddIncidence(LdLattice_t *lat, int sub, int sup);
1089 int LdSetPositions(LdLattice_t *l);
1090 
1091 
1092 
1093 
1094 /* OLD STUFF */
1095 int ChangeBasisOLD(const Matrix_t *M, int ngen, const Matrix_t *gen[],
1096  Matrix_t *newgen[]);
1097 
1098 
1099 #endif /* !defined(_MEATAXE_H_) */
1100 
1101 

MeatAxe 2.4 documentation, generated on Fri Jul 20 2012 20:45:04