1 #ifndef GROUP 2 #define GROUP 3 4 /* File group.h. File to be included with all permutation group theoretic 5 functions. Defines constants and types relating to permutation groups. 6 Also defines some convenient macros. 7 8 Certain preprocessor symbols must, or may, be defined on the compilation 9 command line. Of the symbols below, INT_SIZE is always required; the others 10 are sometime required, or desirable: 11 12 INT_SIZE d -- Here d is the number of bits in type int (usually 13 16 or 32). 14 15 EBCDIC -- Must be defined if the system uses EBCDIC (rather 16 than ASCII) to represent characters. 17 18 PERIOD_TO_BLANK -- If defined, periods in a file name are translated 19 to blanks. This option is present primarily 20 for use with CMS. It allows, for example, 21 a file named PSP82 GROUP A1 to be entered 22 in the form PSP82.GROUP.A1. 23 24 LONG_EXTERNAL_NAMES -- Should be defined if the compiler and linker 25 support external names (31 characters). 26 27 EXTRA_LARGE -- If defined, the compiler represents points using 28 type int rather than type short or unsigned short. 29 This permits permutation groups of high degree but 30 increases memory requirements considerably. This 31 option is intended for C compilers in which 32 sizeof(int) = 4. 33 34 SIGNED -- Assuming EXTRA_LARGE is not defined, defining 35 signed causes points to be represented using 36 type short rather than type unsigned short. This 37 reduces the maximum degree for permutations groups 38 but speeds up the algorithm significantly on some 39 machines (e.g., IBM 3090). 40 41 NOFLOAT -- Causes generation of code performing no floating 42 point operations. Useful primarily in cases 43 where the C compiler generates code requiring a 44 coprocessor when floating point arithmetic is 45 used. 46 47 TICK -- A value of CLK_TCK to be used in place of the 48 value defined in the header file time.h. This 49 is needed in the NOFLOAT option is chosen and if 50 CLK_TCK is given as a floating point quantity 51 (e.g., 18.2 in Turbo C for the IBM PC). It is 52 also needed if an alternate CPU time function 53 is specified. 54 55 CPU_TIME timeFunc -- If defined, timeFunc must be the name of a user- 56 supplied function for measuring CPU time. If 57 not defined, the C function clock() is used. 58 (This function is required on the SUN/3 since 59 the clock function wraps around after less than 60 an hour.) 61 62 DEFAULT_MAX_BASE_SIZE b -- Here b is a default bound on the size of the base for 63 permutation groups. It is 62 by default. Larger 64 values of b increase memory requirements slightly 65 and may increase execution time very slightly. 66 This default value may be overridden by 67 means of the -mb option. 68 69 MAX_NAME_LENGTH n -- Here n is the number of characters allowed in 70 the name of a group, permutation, set, or 71 partition. Default is 16. Large values may 72 cause problems with output. 73 74 MAX_FILE_ NAME_LENGTH m -- Here m is the number of characters allowed in 75 any file name (including path information. 76 The default is 60. 77 78 79 For some compilers, it may be necessary to insert code unique to that compiler. 80 In this case, a special symbol identifying the machine and compiler 81 (e.g., IBM_CMS_WATERLOOC for Waterloo C on the IBM 370) should be defined, 82 and the special code should be in the body of an #if directive specifying 83 that special symbol. */ 84 85 #include <limits.h> 86 87 #include "leon_config.h" 88 #define INT_SIZE SIZEOF_INT<<3 89 90 #ifdef CPU_TIME 91 #define ALT_TIME_HEADER 92 #else 93 #define CPU_TIME clock 94 #endif 95 96 #ifndef LONG_EXTERNAL_NAMES 97 #include "extname.h" 98 #endif 99 100 #define Unsigned unsigned 101 #define UnsignedS unsigned 102 #define MAX_INT UINT_MAX 103 #define SCANF_Int_FORMAT "%u" 104 105 #ifndef MAX_NAME_LENGTH 106 #define MAX_NAME_LENGTH 256 107 #endif 108 109 #ifndef MAX_FILE_NAME_LENGTH 110 #define MAX_FILE_NAME_LENGTH 256 111 #endif 112 113 #ifndef DEFAULT_MAX_BASE_SIZE 114 #define DEFAULT_MAX_BASE_SIZE 62 115 #endif 116 117 118 #ifndef MAX_CODE_LENGTH 119 #define MAX_CODE_LENGTH 128 120 #endif 121 122 #define MAX_REFINEMENT_PARMS 3 123 #define MAX_FAMILY_PARMS 6 124 #define MAX_PRIME_FACTORS 30 125 #define MAX_EXTRA 10 126 127 #define SYMMETRIC_GROUP_CHAR '#' 128 #define IS_SYMMETRIC(g) ((g)->name[0] == SYMMETRIC_GROUP_CHAR) 129 #define ERROR_RETURN_CODE 15 130 #define MAX_COSET_REP_PRINT 300 131 132 133 #define TRUE 1 134 #define FALSE 0 135 #define BOOLEAN Unsigned 136 137 #define IRREDUCIBLE MAX_INT 138 #define UNKNOWN MAX_INT 139 140 #define MIN(x,y) ( ((x) < (y)) ? (x) : (y) ) 141 #define MAX(x,y) ( ((x) > (y)) ? (x) : (y) ) 142 #define ABS(x) ( ((x) < 0) ? (-(x)) : (x) ) 143 144 #define FIRST_IN_ORBIT ((Permutation *) 1) 145 146 #define EXCHANGE(x,y,temp) {temp = x; x = y; y = temp;} 147 148 #define ERROR(function,message) \ 149 errorMessage( __FILE__, __LINE__, function, message); 150 151 #define ERROR1i(function,message1,intParm,message2) \ 152 errorMessage1i( __FILE__, __LINE__, function, message1, intParm, message2); 153 154 #define ERROR1s(function,message1,strParm,message2) \ 155 errorMessage1s( __FILE__, __LINE__, function, message1, strParm, message2); 156 157 158 #define ESSENTIAL_AT_LEVEL(perm,level) essentialAtLevel( perm, level) 159 #define ESSENTIAL_BELOW_LEVEL(perm,level) essentialBelowLevel( perm, level) 160 #define ESSENTIAL_ABOVE_LEVEL(perm,level) essentialAboveLevel( perm, level) 161 #define MAKE_ESSENTIAL_AT_LEVEL(perm,level) makeEssentialAtLevel( perm, level) 162 #define MAKE_NOT_ESSENTIAL_AT_LEVEL(perm,level) \ 163 makeNotEssentialAtLevel( perm, level) 164 #define MAKE_NOT_ESSENTIAL_ATABOV_LEVEL(perm,level) \ 165 makeNotEssentialAtAboveLevel( perm, level) 166 #define MAKE_NOT_ESSENTIAL_ALL(perm) makeNotEssentialAll( perm) 167 #define MAKE_UNKNOWN_ESSENTIAL(perm) makeUnknownEssential( perm) 168 #define COPY_ESSENTIAL(newPerm,oldPerm) copyEssential( newPerm, oldPerm) 169 170 #define RPQ_SIZE( rpq) rpq->size 171 #define RPQ_CLEAR( rpq) rpq->size = 0; 172 173 174 #ifdef EXTRA_LARGE 175 #define XLARGE TRUE 176 #endif 177 #ifndef EXTRA_LARGE 178 #define XLARGE FALSE 179 #endif 180 181 #ifdef SIGNED 182 #define SGND TRUE 183 #endif 184 #ifndef SIGNED 185 #define SGND FALSE 186 #endif 187 188 #ifdef NOFLOAT 189 #define NFLT TRUE 190 #endif 191 #ifndef NOFLOAT 192 #define NFLT FALSE 193 #endif 194 195 #ifndef CLK_TCK 196 #define CLK_TCK CLOCKS_PER_SEC 197 #endif 198 199 typedef struct { 200 int mbs, mnl, mpf, mrp, mfp, me, xl, sg, nf; 201 } CompileOptions; 202 203 #ifndef MAIN 204 void checkCompileOptions( 205 char *localFileName, 206 CompileOptions *mainOpts, 207 CompileOptions *localOpts); 208 #endif 209 210 #define CHECK(fileName) \ 211 void x##fileName( CompileOptions *mainOptsPtr) \ 212 { CompileOptions localOpts = { DEFAULT_MAX_BASE_SIZE, MAX_NAME_LENGTH, \ 213 MAX_PRIME_FACTORS, \ 214 MAX_REFINEMENT_PARMS, MAX_FAMILY_PARMS, \ 215 MAX_EXTRA, XLARGE, SGND, NFLT}; \ 216 checkCompileOptions( __FILE__, mainOptsPtr, &localOpts); \ 217 } 218 219 220 extern unsigned long bitSetAt[32]; 221 extern unsigned long bitSetBelow[33]; 222 223 224 typedef 225 enum { 226 PERM_GROUP, PERMUTATION, POINT_SET, PARTITION, DESIGN, MATRIX_01, 227 BINARY_CODE, INVALID_OBJECT 228 } ObjectType; 229 230 typedef struct { 231 Unsigned noOfFactors; 232 UnsignedS prime[MAX_PRIME_FACTORS+1]; 233 UnsignedS exponent[MAX_PRIME_FACTORS+1]; 234 } FactoredInt; 235 236 struct Word; 237 struct OccurenceOfGen; 238 239 typedef 240 struct Permutation { 241 char name[MAX_NAME_LENGTH+1]; 242 UnsignedS degree; 243 UnsignedS *image; /* Alloc (degree+2)*sizeof(UnsignedS). */ 244 UnsignedS *invImage; /* Alloc (degree+2)*sizeof(UnsignedS). */ 245 Unsigned level; 246 unsigned long *essential; 247 struct Permutation *invPermutation; 248 struct Permutation *next, 249 *last; 250 struct Permutation *xNext, 251 *xLast; 252 struct Word *word; /* Alloc (MWLENGTH+2)*sizeof(Word *). */ 253 struct OccurenceOfGen *occurHeader; 254 } Permutation; 255 256 typedef 257 struct Word { 258 Unsigned length; 259 Permutation **position; 260 } Word; 261 262 typedef 263 struct Relator { 264 Unsigned length; 265 Unsigned level; 266 Permutation **rel; 267 Unsigned **fRel; 268 Unsigned **bRel; 269 struct Relator *next; 270 struct Relator *last; 271 } Relator; 272 273 typedef 274 struct OccurenceOfGen { 275 Relator *r; 276 Unsigned relLength; 277 Unsigned level; 278 Unsigned **fRelStart; 279 Unsigned **bRelFinish; 280 struct OccurenceOfGen *next; 281 } OccurenceOfGen; 282 283 typedef 284 struct SplitSize { 285 Unsigned oldCellSize; 286 Unsigned newCellSize; 287 } SplitSize; 288 289 typedef 290 enum { 291 cycleFormat, 292 imageFormat, 293 binaryFormat, 294 cayleyLibraryFormat, 295 cayleyReadFormat 296 } PermFormat; 297 298 typedef /* Note below MBS denotes */ 299 struct PermGroup { /* MAX_BASE_SIZE. */ 300 char name[MAX_NAME_LENGTH+1]; 301 Unsigned degree; 302 Unsigned baseSize; 303 FactoredInt *order; /* Alloc sizeof(FactoredInt). */ 304 UnsignedS *base; /* Alloc (MBS+2)*sizeof(UnsignedS). */ 305 UnsignedS *basicOrbLen; /* Alloc (MBS+2)*sizeof(UnsignedS). */ 306 UnsignedS **basicOrbit; /* Alloc (MBS+2)*sizeof(UnsignedS **). */ 307 Permutation ***schreierVec; /* Alloc (MBS+2)*sizeof(Permutation***).*/ 308 UnsignedS **completeOrbit; /* Alloc (MBS+2)*sizeof(UnsignedS **). */ 309 UnsignedS **orbNumberOfPt; /* Alloc (MBS+2)*sizeof(UnsignedS **). */ 310 UnsignedS **startOfOrbitNo; /* Alloc (MBS+2)*sizeof(UnsignedS **). */ 311 Permutation *generator; 312 UnsignedS *omega; /* Alloc (degree+2)*sizeof(UnsignedS). */ 313 UnsignedS *invOmega; /* Alloc (degree+2)*sizeof(UnsignedS). */ 314 PermFormat printFormat; 315 Relator *relator; 316 } PermGroup; 317 318 typedef 319 struct Partition { 320 char name[MAX_NAME_LENGTH+1]; 321 Unsigned degree; 322 UnsignedS *pointList; /* Alloc (degree+2)*sizeof(UnsignedS). */ 323 UnsignedS *invPointList; /* Alloc (degree+2)*sizeof(UnsignedS). */ 324 UnsignedS *cellNumber; /* Alloc (degree+2)*sizeof(UnsignedS). */ 325 UnsignedS *startCell; /* Alloc (degree+2)*sizeof(UnsignedS). */ 326 } Partition; 327 328 typedef 329 struct PartitionStack { 330 Unsigned height; 331 Unsigned degree; 332 UnsignedS *pointList; /* Allocate (degree+2)*sizeof(UnsignedS). */ 333 UnsignedS *invPointList; /* Allocate (degree+2)*sizeof(UnsignedS). */ 334 UnsignedS *cellNumber; /* Allocate (degree+2)*sizeof(UnsignedS). */ 335 UnsignedS *parent; /* Allocate (degree+2)*sizeof(UnsignedS). */ 336 UnsignedS *startCell; /* Allocate (degree+2)*sizeof(UnsignedS). */ 337 UnsignedS *cellSize; /* Allocate (degree+2)*sizeof(UnsignedS). */ 338 } PartitionStack; 339 340 typedef 341 struct CellPartitionStack { 342 Partition *basePartn; 343 Unsigned height; 344 Unsigned cellCount; 345 UnsignedS *cellList; /* Alloc (cellCount+2)*sizeof(UnsignedS). */ 346 UnsignedS *invCellList; /* Alloc (cellCount+2)*sizeof(UnsignedS). */ 347 UnsignedS *cellGroupNumber; /* Alloc (cellCount+2)*sizeof(UnsignedS). */ 348 UnsignedS *parentGroup; /* Alloc (cellCount+2)*sizeof(UnsignedS). */ 349 UnsignedS *startCellGroup; /* Alloc (cellCount+2)*sizeof(UnsignedS). */ 350 UnsignedS *cellGroupSize; /* Alloc (cellCount+2)*sizeof(UnsignedS). */ 351 UnsignedS *totalGroupSize; /* Alloc (cellCount+2)*sizeof(UnsignedS). */ 352 } CellPartitionStack; 353 354 typedef 355 union { 356 Unsigned intParm; 357 void *ptrParm; 358 } RefinementParm; 359 360 typedef SplitSize RefinementMapping( 361 const RefinementParm familyParm[], 362 const RefinementParm refnParm[], 363 PartitionStack *const UpsilonStack); 364 365 typedef struct { 366 RefinementMapping *refine; 367 RefinementParm familyParm_L[MAX_FAMILY_PARMS]; 368 RefinementParm familyParm_R[MAX_FAMILY_PARMS]; 369 } RefinementFamily; 370 371 typedef struct { 372 RefinementFamily *family; 373 RefinementParm refnParm[MAX_REFINEMENT_PARMS]; 374 } Refinement; 375 376 typedef struct { 377 Refinement refn; 378 long priority; 379 } RefinementPriorityPair; 380 381 typedef RefinementPriorityPair ReducChkFn( 382 const RefinementFamily *family, 383 const PartitionStack *const UpsilonStack); 384 385 /* R-base notation is as in "Perm Grp Algs...". Note fields omega, invOmega, 386 alpha are not included here, but are set in the structure for the 387 containing group. */ 388 typedef /* Note below MBS denotes */ 389 struct { /* MAX_BASE_SIZE. */ 390 Unsigned ell; 391 Unsigned k; 392 Unsigned degree; 393 Refinement *aAA; /* Alloc (degree+2) * sizeof(Refinement).*/ 394 PartitionStack *PsiStack; /* Alloc sizeof(PartitionStack). */ 395 UnsignedS *n_; /* Alloc (MBS+2)*sizeof(UnsignedS). */ 396 UnsignedS *p_; /* Alloc (MBS+2)*sizeof(UnsignedS). */ 397 UnsignedS *alphaHat; /* Alloc (MBS+2)*sizeof(UnsignedS). */ 398 UnsignedS *a_; /* Alloc (degree+2)*sizeof(UnsignedS). */ 399 UnsignedS *b_; /* Alloc (degree+2)*sizeof(UnsignedS). */ 400 UnsignedS *omega; /* Alloc (degree+2)*sizeof(UnsignedS). */ 401 UnsignedS *invOmega; /* Alloc (degree+2)*sizeof(UnsignedS). */ 402 } RBase; 403 404 typedef 405 struct PointSet { 406 char name[MAX_NAME_LENGTH+1]; 407 Unsigned size; 408 Unsigned degree; 409 UnsignedS *pointList; /* Alloc (degree+2)*sizeof(UnsignedS). */ 410 char *inSet; /* Alloc (degree+2)*sizeof(char) */ 411 } PointSet; 412 413 typedef 414 struct { 415 Unsigned size; 416 Unsigned degree; 417 Unsigned maxSize; 418 UnsignedS *pointList; /* Alloc (maxSize+2)*sizeof(UnsignedS). */ 419 } RPriorityQueue; 420 421 typedef BOOLEAN Property( const Permutation *const); 422 423 typedef struct { 424 Unsigned maxBaseSize; 425 Unsigned maxDegree; 426 Unsigned maxWordLength; 427 BOOLEAN statistics; 428 BOOLEAN inform; 429 BOOLEAN strongMinDCosetCheck; 430 BOOLEAN compress; 431 Unsigned maxStrongGens; 432 Unsigned maxBaseChangeLevel; 433 Unsigned idealBasicCellSize; 434 Unsigned trimSGenSetToSize; 435 Unsigned writeConjPerm; 436 Unsigned restrictedDegree; /* For informCosetRep only. */ 437 void (*altInformCosetRep)( Permutation *y); 438 Unsigned alphaHat1; 439 char genNamePrefix[8]; 440 char outputFileMode[3]; 441 char *groupOrderMessage; 442 char *cosetRepMessage; 443 char *noCosetRepMessage; 444 } GroupOptions; 445 446 typedef struct { 447 unsigned long initialSeed; 448 Unsigned minWordLengthIncrement; 449 Unsigned maxWordLengthIncrement; 450 Unsigned stopAfter; 451 BOOLEAN reduceGenOrder; 452 Unsigned rejectNonInvols; 453 Unsigned rejectHighOrder; 454 BOOLEAN onlyEssentialInitGens; 455 BOOLEAN onlyEssentialAddedGens; 456 } RandomSchreierOptions; 457 458 typedef struct { 459 char refnType; 460 PermGroup *leftGroup; 461 PermGroup *rightGroup; 462 } SpecialRefinementDescriptor; 463 464 typedef struct { 465 UnsignedS **revWord; 466 UnsignedS **invWord; 467 UnsignedS *lengthAtLevel; /* alloc (MAX_BASE_SIZE+2) * sizeof(UnsignedS) */ 468 } THatWordType; 469 470 typedef char FieldElement; 471 472 typedef struct { 473 char name[MAX_NAME_LENGTH+1]; 474 Unsigned size; 475 Unsigned characteristic; 476 Unsigned exponent; 477 char **sum; 478 char **dif; 479 char **prod; 480 char *inv; 481 } Field; 482 483 typedef struct { 484 char name[MAX_NAME_LENGTH+1]; 485 Unsigned setSize; 486 Field *field; 487 Unsigned numberOfRows; 488 Unsigned numberOfCols; 489 char **entry; 490 Unsigned *unused; 491 } Matrix_01; 492 493 typedef struct { 494 char name[MAX_NAME_LENGTH+1]; 495 Unsigned fieldSize; 496 Field *field; 497 Unsigned dimension; 498 Unsigned length; 499 char **basis; 500 Unsigned *infoSet; 501 } Code; 502 503 typedef struct { 504 Unsigned cellCount; 505 CellPartitionStack *xPsiStack; 506 CellPartitionStack *xUpsilonStack; 507 Refinement *xRRR; 508 void (*cstExtraRBase)(Unsigned level); 509 UnsignedS *applyAfter; 510 UnsignedS *xA_; 511 UnsignedS *xB_; 512 } ExtraDomain; 513 514 #endif 515