Upper bounds on Weight Hierarchies of Extremal Non-Chain Codes

A Study in a Projective Geometry

Thesis for the degree of Candidatus Scientiarum

Industrial and Applied Mathematics and Informatics Applicable Algebra and Coding Theory

Hans Georg Schaathun

20th December 1998

Department of Informatics

Universitas Bergensis

Book II: The book of source code

Contents

1 Common header files 3 2 Projective Geometry 7

2.1 The simple representation . . . . . . . . . . . . . . . . . . . . . . 7 2.2 The coordinate representation . . . . . . . . . . . . . . . . . . . . 10 2.3 The complete incidence structure . . . . . . . . . . . . . . . . . . 15

3 Value Assignments 25 3.1 The basic modules . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Complex modules . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4 Other common modules 49 5 gen 53 6 vsh 61 7 Auxiliary programmes 73 8 PID check 79 Index 82 \underline{CONTENTS}

2

Chapter 1

Common header files

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: common.h,v 5.0 1998/12/20 00:23:58 georg Exp $ */  2

3

#include <unistd.h>  4
#include <stdlib.h>  5
#include <stdio.h>  6
#include <sys/types.h>  7
#include <sys/stat.h>  8
#include <fcntl.h>  9
#include <strings.h>  10
#include <time.h>  11
#include <sys/times.h>  12
#include <limits.h>  13
#include <libgen.h>  14
#include <hgd.h>  15
#include <errno.h>  16

17

#include "gen.h"  18

#include "errors.h"  19

#include "aux.h"  20

21

#if SYSTEM == alpha  22
# define cftime(s,p,t) strcpy ( s, ctime ( t ) )  23
#endif  24

25

#define TRUE  1  26
#define FALSE 0  27
#define SUCCESS 0  28
#define TERM 1  29
#define ECHO 1<<1  30

31

#define min(a,b) ( ( a<b ) ? a : b )  32
#define max(a,b) ( ( a>b ) ? a : b )  33

34

/* End of common.h */  35
/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: gen.h,v 5.0 1998/12/20 00:24:09 georg Exp $ */  2

3

/* Config options */  4
#define ALLOW FIX  5
#define DEF ALARM 0  6

7

CHAPTER 1. COMMON HEADER FILES

/* Version numbers and other identification of programmes */  8
#define GEN VERSION "4.1"  9
#define VSH VERSION "4.2"  10
#define GEN NAME  "gen"  11
#define VDG NAME  "vdg"  12
#define VSH NAME  "vsh"  13
#define PGC NAME  "pgc"  14
#define PID NAME  "pidcheck"  15
#define PGT NAME  "pgtest"  16
#define GEN COMPILE DATE ", " TIME  17

18

/* External programmes */  19

#define mta  "/usr/lib/sendmail"  20

21

/* Array and string sizes. */  22
#define MAX DIM 8 23
#define FILE NAME L 24  24
#define PATH NAME L 128  25
#define CALL STRING L 128  26
#define TIME STRING L 40  27
#define LINE LENGTH 160  28

29

/* Backup Control */  30
#define MIN BCINT 65536  /* = 2^16 */  31
#define DEF BCINT 16777216  /* = 2^24 */  32
#define DEF BCEXT ".bc"  33
#define DEF BCBCEXT "˜ "  34

35

/* Default nice values */  36
#ifdef DEBUG  37
# define DEF NICE 0 38
# define DEF CNICE 0  39
# define CC DEBUG "+DEBUG" 40
#else  41
# define DEF NICE 19 42
# define DEF CNICE 6  43
# define CC DEBUG "-DEBUG" 44
#endif  45

46

#define CC DEFINES  CC DEBUG  47

48

/* File identification strings */  49
/* Keep support for VT FILEID VT1vt */  50
#define VT FILEID  "VT2vt"  51
#define PG FILEID  "PG1.6pg"  52

53

/* Default File Names */  54
#ifndef PG DIR  55

# define PG DIR  "/Home/stud/georg/inf/coding/gen/data/pg"  56

#endif  57
#define GEN OUTFILE  "gen:output"  58
#define GEN BOUTFILE  "gen:binary"  59
#define GEN INFILE  "pgc:output"  60
#define GEN ACTFILE  "active"  61
#define GEN PASFILE  "passive"  62
#define GEN RESTART  "restart"  63
#define DEF SIGBFILE  "gen:signalexit"  64
#define VAL STATUSFILE "gen:status"  65
#define VSH CONF  "vsh.config"  66

67

/* Special macroes */  68
#define StatusReport(a) val statusreport (a)  69

/* End of gen.h */  71

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: errors.h,v 5.0 1998/12/20 00:24:01 georg Exp $ */  2

3

#define ENO OK  0  4
#define ERR USE  "Usage Error",  2  5
#define ENO USE  2  6

#define ERR FLAGS  "Usage Error: Incompatible flags.", 2  7
#define ERR BCINT  "Minimum backup interval is 1024.", 2  8

#define ENO SIG  4  9
#define ENO INT  5  10

#define ERR DATA  "Lacking mandatory data", 6  11
#define ERR NOGF  "No support for Galois Fields larger than 5", 8  12

13

#define ERR MEM  "Could not allocate memory", 16  14

#define ENO MEM  16  15
#define ERR OVERFLOW "Number overflow",  17  16

#define ERR BUF  "Buffer overflow",  18  17

#define ENO BUF  18  18

19 20

#define ERR FOPEN  "Could not open file: ", 32  21

#define ENO FOPEN  32  22

#define ERR FFORMAT "Illegal file format",  33  23
#define ERR LOCKFAIL "Failed to creat lockfile", 34  24

25

#define ERR IMP  "Feature not implemented", 128  26

#define ENO IMP  128  27
#define ERR PROG  "Fatal bug",  129  28

29

/* End of errors.h */  30

CHAPTER 1. COMMON HEADER FILES 6

Chapter 2

Projective Geometry

2.1 The simple representation

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pg.h,v 5.0 1998/12/20 00:24:43 georg Exp $ */  2

3

#define pg maxel 65534  4
#define pg noel 65535  5

6

typedef unsigned short t ps; /* Subspace by number */  7
typedef unsigned char t pdim; /* Parameter of a projective geometry */  8

9

/* Projective Geometry */  10
typedef struct s pg {  11
t pdim k, q; /* The dimension of the geometry */  12
t ps  ptno[MAX DIM];  13
t ps  elno[MAX DIM];  14
t ps  theta[MAX DIM][MAX DIM];  15
/* Lookup tables for number of points and subspaces. **  16
** See the macroes below. */ 17
t ps ****ps;  18
/* Incidence structure: ps[i][j][k][l] = m, means that **  19
** (i+j+1)-space #m is the l’th superspace of i-space #k. */  20
} t pg;  21

22

t pg *pg load ( FILE *stream );  23
/* Constructor: Load geometry from file */  24
void pg del ( t pg *pg );  25
/* Destructor: Deallocate memory */ 26
t pg *pg alloc ( t pdim k, t pdim q );  27
/* Allocate memory (used by constructors, incl. pg create in the **  28
** pginit module. */ 29
t ps pg brack ( t pdim q, t ps r, t ps s );  30
/* Compute [r-s,r] /[1,s] */  31
int pg dimprint ( FILE *fs, t pdim k, t pdim q ) ;  32
/* Print counts of subspaces and points in PG(k,q) */  33
unsigned long pg igs ( int q, int p ) ;  34
/* Compute a geomtric series of integer values without calling pow(3). **  35
** i.e. compute Q(p) = q^0+q^1+q^2+…+q^p.  */  36

37

#define pg q(q,i)  pg igs (q,i)  38
/* Compatibility alias for pg igs() */  39

40

CHAPTER 2. PROJECTIVE GEOMETRY

/* Costly macros */  41
#define pg q pow (q, i) ( ( pow ( q, i+1 ) − 1 ) / ( q − 1 ) )  42
/* Compute Q(i) */  43
#define pg elno(q,k,d) pg brack ( q, k+1, d+1 )  44
/* Compute the number of d-spaces */  45
#define pg theta(r,s,k,q) pg brack ( q, k−(r), k−(s) )  46
/* Compute \chi (r,s;k,q) */  47

48

/* Looking up the same values in tables */  49
#define pg eln(pg,i) ( pg−>elno[i] ) 50
/* Return the number of d-spaces, i.e. get pg elno() from a lookup table. */  51
#define pg qpow(pg,i) ( pg−>ptno[i] ) 52
/* Return Q(i), i.e. the number of points in an i-space, **  53
** from a lookup table. */ 54
#define pg thet(pg,r,s) ( pg−>theta[r][s] )  55
/* Look up the number of s-spaces through any particular r-space. */  56

57

/* End: pg.h */  58
/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pg.c,v 5.0 1998/12/20 00:24:40 georg Exp $ */  2

3

/* The constructing functions are in the pginit module. */  4

5

#include "common.h"  6

7

#include "pg.h"  8

#include "aux.h"  9

10

/* Constructors */  11
t pg *pg load ( FILE *stream ) {  12
t ps g, gm, h, hm, i = 0, im, j, jm;  13
t pg *pg;  14
t pdim k, q;  15

16

while ( 0 != PG FILEID[i] ) {  17
if ( PG FILEID[i++] != getc ( stream ) ) ErrEx ( ERR FFORMAT );  18
};  19

20

k = getc ( stream );  21
q = getc ( stream );  22

23

pg = pg alloc ( k, q );  24

25

for ( gm = pg−>k−1, g = 0; g < gm; ++g ) {  26
im = pg eln ( pg, g );  27
for ( hm = pg−>k−g−1, h = 0; h < hm; ++h ) {  28
jm = pg thet ( pg, g, g+h+1 );  29
for ( i = 0; i < im; ++i ) {  30
for ( j = 0; j < jm; ++j ) pg−>ps[g][h][i][j] = getshort ( stream );  31
};  32
};  33
};  34

35

return ( pg );  36
}  37

38

/* Destructor */  39
void pg del ( t pg *pg ) {  40
t ps g, gm, h, hm, i, im;  41

42

2.1. THE SIMPLE REPRESENTATION

for ( gm = pg−>k−1, g = 0; g < gm; ++g ) {  43
im = pg eln ( pg, g );  44
for ( hm = pg−>k−g−2, h = 0; h < hm; ++h ) {  45
for ( i = 0; i < im; ++i ) free ( pg−>ps[g][h][i] );  46
free ( pg−>ps[g][h] );  47
};  48
free ( pg−>ps[g] );  49
};  50

51

free ( pg−>ps );  52
free ( pg );  53

54

}  55

56

/* Allocate memory (subroutine for the constructors). */  57
t pg *pg alloc ( t pdim k, t pdim q ) {  58
t pg *pg;  /* pointer to be returned */  59
char h;  /* loop index */  60
t ps i, j, g, /* loop indices */  61
jm, gm; /* upper bounds for loop indices */  62

63

/* Allocate memory and insert the parameters for the size of the geometry. */  64
pg = getmem ( sizeof ( t pg ) );  65
pg−>k = k; pg−>q = q;  66
pg−>ps = getmem ( (k−1)*sizeof (void*) );  67

68

/* Precompute the number of m-spaces for each m, and the theta function. */  69
for ( gm = k, g = 0; g <= gm; g++ ) {  70
pg−>elno[g] = pg elno (q,k,g);  71
pg−>ptno[g] = pg q (q,g);  72
for ( h = g; h++ < gm; ) {  73
pg−>theta[g][h] = pg theta ( g, h, k, q );  74
};  75
};  76

77

/* Allocate the arrays. */  78
for ( h = 0; h < k − 1; h++ ) {  79
pg−>ps[h] = getmem ( ( k − h − 1 )*sizeof (void*) );  80
jm = pg eln ( pg, h );  81
for ( i = 0; i < k − h − 1; i++ ) {  82
gm = pg thet ( pg, h, h+i+1 ) ;  83
pg−>ps[h][i] = getmem ( jm*sizeof (void*) );  84
for ( j = 0; j < jm; j++ ) {  85
pg−>ps[h][i][j] = getmem ( gm*sizeof ( t ps ) );  86
for ( g=0; g < gm; ++g ) pg−>ps[h][i][j][g] = pg noel;  87
};  88
};  89
};  90

91

return ( pg );  92
}  93

94

unsigned long pg igs ( int q, int p ) {  95
unsigned int i;  96
unsigned long t = 1, s = 1;  97
for ( i = 1; i <= p; ++i ) {  98
t *= q; /* Get the next power of q. */  99
s += t; /* Add a power of q to the sum. */  100
}  101
return ( s );  102
}  103

104

CHAPTER 2. PROJECTIVE GEOMETRY

t ps pg brack ( t pdim q, t ps r, t ps s ) {  105
unsigned long a = 1;  106
char i;  107
for ( i = 0; i < s; ++i ) {  108
/* We take the risk to compute pg igs(q,i) twice for some values of i. **  109
** The overhead is probably not a great problem, anyway. */ 110
a *= pg igs ( q, r − s + i );  111
a /= pg igs ( q, i );  112
};  113
if ( a > pg maxel ) ErrEx ( ERR OVERFLOW );  114
return ( a );  115
}  116

117

int pg dimprint ( FILE *fs, t pdim k, t pdim q ) {  118
int i;  119
for ( i = 0; i < k; ++i ) {  120
fprintf ( fs, "#%i: %i\n", i, pg elno ( q, k, i ) );  121
};  122
return ( 0 );  123
}  124

125

/* End of pg.c */  126

2.2 The coordinate representation

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: gf.h,v 5.0 1998/12/20 00:24:16 georg Exp $ */  2

3

/* Arithmetric functions in small Galois Fields. */  4

5

char gf mult ( char a, char b, char q ) ;  6
/* Compute a*b in GF(q) */  7
char gf add ( char a, char b, char q ) ;  8
/* Compute a+b in GF(q) */  9
char gf inv ( char a, char q ) ;  10
/* Compute the multiplicative inverse of a in GF(q) */  11

12

/* End of gf.h */  13

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: gf.c,v 5.0 1998/12/20 00:24:13 georg Exp $ */  2

3

/* Arithmetric functions in small Galois Fields. */  4

5

#include "common.h"  6

7

char gf mult ( char a, char b, char q ) {  8
static char t[4][4] =  9
{ { 0, 0, 0, 0 },  10
{ 0, 1, 2, 3 },  11
{ 0, 2, 3, 1 },  12
{ 0, 3, 1, 2 } };  13
if ( ( 6 == q) | | ( q > 7 ) | | ( q < 2 ) ) ErrExit ( ERR NOGF );  14
/* If q is prime, we use arithmetics modulo q. */  15
return ( ( q == 4 ) ? t[a][b] : ( a * b % q ) );  16
}  17

18

char gf add ( char a, char b, char q ) {  19
static char t[4][4] =  20

2.2. THE COORDINATE REPRESENTATION

{ { 0, 1, 2, 3 },  21
{ 1, 0, 3, 2 },  22
{ 2, 3, 0, 1 },  23
{ 3, 2, 1, 0 } };  24
if ( ( 6 == q) | | ( q > 7 ) | | ( q < 2 ) ) ErrExit ( ERR NOGF );  25
/* If q is prime, we use arithmetics modulo q. */  26
return ( ( q == 4 ) ? t[a][b] : ( ( a + b ) % q ) );  27
}  28

29

char gf inv ( char a, char q ) {  30
static char t[6][7] =  31
{ { 0, 1, −1, −1, −1, −1, −1 },  32
{ 0, 1, 2, −1, −1, −1, −1 },  33
{ 0, 1, 3, 2, −1, −1, −1 },  34
{ 0, 1, 3, 2, 4, −1, −1 },  35
{ −1, −1, −1, −1, −1, −1, −1 },  36
{ 0, 1, 4, 5, 2, 3, 6 } };  37
if ( ( 6 == q) | | ( q > 7 ) | | ( q < 2 ) ) ErrExit ( ERR NOGF );  38
return ( t[q−2][a] );  39
}  40

41

/* End of gf.c */  42

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: points.h,v 5.0 1998/12/20 00:25:23 georg Exp $ */  2

3

typedef t pdim *t pt; /* Coordinates of a point */  4

5

t pt pt init ( t pdim k ) ;  6
/* Constructor: allocate memory for a point in a k-dimensional geometry */  7
#define pt del(pt) free(pt)  8
/* Destructor: deallocate memory */  9

10

int pt add ( t pt a, t pt b, t pdim k, t pdim q ) ;  11
/* Add the points a,b in GF(q)^{k+1} */  12
int pt mult ( t pt a, int c, t pdim k, t pdim q ) ;  13
/* Multiply the point a by the scalar b in GF(q)^{k+1} */  14
t ps pt getno ( t pt a, t pdim k, t pdim q ) ;  15
/* Get the number representation of the point a in PG(k,q) */  16
int pt fromno ( t pt a, t ps pt, t pdim k, t pdim q ) ;  17
/* Put the coordinate representation of point pt in PG(k,q) in a */  18

19

#define pt normalize(c,k,q) ( 2==q ? 0 : pt norm(c,k,q) )  20
int pt norm ( t pt c, t pdim k, t pdim q ) ; 21
/* Normalize the coordinate representation, c, i.e. make **  22
** sure that the first non-zero coordinate is 1.  **  23
** The macro saves some time if q=2.  */  24

25

long pt qpow ( t pdim q, int e );  26
/* Return q^e, by looking up in a static array which is computed **  27
** the first time a power of a particular value of q is requested. */  28

29

void pt print  ( t pt pt, FILE *stream, t pdim k, t pdim q ) ;  30
/* Print the point to stream, showing the coordinate representation. */  31
int pt fromstr ( t pt c, char *pt ) ;  32
/* Convert the ASCII string pt to internal coordinate representation. **  33
** Each coordinate position correspond to one digit in the string. */  34

35

/* End of points.h */  36

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: points.c,v 5.0 1998/12/20 00:25:20 georg Exp $ */  2

3

#include "common.h"  4

#include "pg.h"  5

#include "points.h"  6

#include "gf.h"  7

#include "aux.h"  8

9

static t ps pt vno ( t pt c, t pdim k, t pdim q ) ;  10
/* Auxiliary function for pt getno(). */  11
static void pt nov ( t pt c, t pdim k, t pdim q, t ps pt ) ;  12
/* Auxiliary function for pt fromno(). */  13

14

int pt add ( t pt a, t pt b, t pdim k, t pdim q ) {  15
register int i;  16
for ( i=0; i <= k; ++i ) a[i] = gf add ( a[i], b[i], q );  17
return ( 0 );  18
}  19

20

int pt mult ( t pt a, int c, t pdim k, t pdim q ) {  21
register int i;  22
for ( i=0; i <= k; ++i ) a[i] = gf mult ( a[i], c, q );  23
return ( 0 );  24
}  25

26

t ps pt getno ( t pt c, t pdim k, t pdim q ) {  27
return ( ( k == 0 ) ? ( c[0] == 0 ? pg noel : 0 ) : (  28
( c[0] == 0 ) ? pt getno ( c+1, k−1, q )  29
: pt vno ( c+1, k, q ) + pg q ( q, k−1 ) + 1 ) );  30
}  31

32

t ps pt vno ( t pt c, t pdim k, t pdim q ) {  33
register t ps i = 0;  34
while ( k−− > 0 ) {  35
i += *(c++)*pt qpow ( q, k );  36
};  37
return ( i − 1 );  38
}  39

40

int pt fromno ( t pt c, t ps pt, t pdim k, t pdim q ) {  41
register int i;  42
if ( k > 0 ) {  43
if ( pt >= ( i = pg q ( q, k−1 ) ) ) {  44
*c = 1;  45
/* A non-zero coordinate is placed, ** 46
** do the rest as if it were a Euclidean geometry. */  47
pt nov ( c+1, k, q, pt−i );  48
} else {  49
*c = 0;  50
/* Only non-zero coordinates so far, recurse for the remaining. */  51
pt fromno ( c+1, pt, k−1, q );  52
};  53
} else {  54
/* This is the last coordinate, that one has to be one. */  55
*c = 1;  56
};  57
}  58

59

void pt nov ( t pt c, t pdim k, t pdim q, t ps pt ) {  60
register int i;  61
if ( k > 0 )  62

2.2. THE COORDINATE REPRESENTATION

if ( pt >= ( i = pt qpow ( q, k−1 ) ) ) {  63
*c = pt/i;  64
pt nov ( c+1, k−1, q, pt−((*c)*i) );  65
} else {  66
*c = 0;  67
pt nov ( c+1, k−1, q, pt );  68
};  69
}  70

71

t pt pt init ( t pdim k ) {  72
t pt pt;  73
register int i;  74
pt = getmem ( (k+1)*sizeof (t pdim) );  75
for ( i=0; i <= k; ++i ) pt[i] = 0;  76
return ( pt );  77
}  78

79

/* pt norm normalizes the representation *c of a projective point, **  80
** so that the first nonzero coordinate is equal to 1. */ 81
int pt norm ( t pt c, t pdim k, t pdim q ) {  82
register unsigned char i = 0, b;  83

84

while ( c[i] == 0 && i++ < k ) {};  85
b = gf inv(c[i], q);  86
c[i] = 1;  87
while ( i++ < k ) c[i] = gf mult (c[i],b,q);  88
return ( 0 );  89
}  90

91

void pt print  ( t pt pt, FILE *stream, t pdim k, t pdim q ) {  92
t ps i;  93
fprintf ( stream, "( " );  94
for ( i = 0; i < k; ++ i ) fprintf ( stream, "%i, ", pt[i] );  95
fprintf ( stream, "%i )", pt[k] );  96
}  97

98

void pt noprint ( t ps ps, FILE *stream, t pdim k, t pdim q ) {  99
char pt[12];  100
fprintf ( stream, "%i ", ps );  101
pt fromno ( (t pt)pt, ps, k, q );  102
pt print ( (t pt)pt, stream, k, q );  103
}  104

105

int pt fromstr ( t pt c, char *pt ) {  106
t pdim i;  107
for ( i = 0; pt[i] != 0; ++i ) c[i] = pt[i] − '0';  108
return ( 0 );  109
}  110

111

long pt qpow ( t pdim b, int e ) {  112
static int q[MAX DIM] = { 1, 0 };  113
/* The static array stores powers of q[1]. If powers of a new base b, **  114
** not equal to q[1], the array is recomputed; but that should not **  115
** occur very frequently. */ 116
int i;  117
if ( q[1] == b ) return ( q[e] );  118
for ( i = 0; ++i < MAX DIM; ) q[i] = q[i−1]*b;  119
return ( q[e] );  120
}  121

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1

/* $Id: base.h,v 5.0 1998/12/20 00:23:55 georg Exp $ */  2

3

typedef struct s bas {  4
t pdim m; /* The dimension of the basis. */  5
t ps *bas; /* Array of points for the basis. */  6
} t bas;  7

8

t ps bas comb ( t bas *bas, t ps d, t pdim k, t pdim q ) ;  9
/* Form a linear combination of points. */  10

11

t bas *bas init ( t pdim m ) ;  12
/* Constructor: allocate memory, initialize each point with pg noel */  13

14

t bas *bas copy ( t pdim m, t bas *bas ) ;  15
/* Constructor, as many points as possible are copied from bas. **  16
** The first points are used if bas has greater dimension than m. **  17
** The remaining points are initialized to pg noel.  */  18

19

#define bas del(b) ( free ( b−>bas ), free ( b ) )  20
/* Destructor: deallocate memory */  21

22

/* End of base.h */  23

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: base.c,v 5.0 1998/12/20 00:23:54 georg Exp $ */  2

3

#include "common.h"  4

5

#include "aux.h"  6

#include "pg.h"  7

#include "points.h"  8
#include "base.h"  9

10

t ps bas comb ( t bas *bas, t ps d, t pdim k, t pdim q ) {  11
t pt a,b;  12
t ps pt;  13
int i, e;  14
a = pt init ( k );  15
b = pt init ( k );  16
for ( i = 0; i <= bas−>m; ++i ) {  17
e = d % q;  18
d = d / q;  19
if ( e ) {  20
pt fromno ( b, bas−>bas[i], k, q );  21
pt mult ( b, e, k, q );  22
pt add ( a, b, k, q );  23
};  24
};  25

26

pt normalize (a, k, q);  27
pt = pt getno(a, k, q);  28
pt del ( a ); pt del ( b );  29
return ( pt );  30
}  31

32

t bas *bas init ( t pdim m ) {  33
t bas *bas;  34
int i;  35
bas = getmem (sizeof(t bas));  36
bas−>m = m;  37
bas−>bas = getmem ( (m+1)*sizeof (t ps) );  38

2.3. THE COMPLETE INCIDENCE STRUCTURE

for ( i=0; i <= m; ++i ) bas−>bas[i] = pg noel;  39
return ( bas );  40
}  41

42

t bas *bas copy ( t pdim m, t bas *bas ) {  43
t bas *b;  44
int i;  45
b = bas init ( m );  46
m = min ( m, bas−>m );  47
for ( i=0; i <= m; ++ i ) b−>bas[i] = bas−>bas[i];  48
return ( b );  49
}  50

51

/* End of base.c */  52

2.3 The complete incidence structure

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: subspace.h,v 5.0 1998/12/20 00:25:54 georg Exp $ */  2

3

#include "base.h"  4

5

#define msp in(p,b)  b−>pt[p]  6

7

typedef struct s msp {  8
t bas *bas;  9
/* The basis */  10
char *pt;  11
/* A boolean array of all points, stating TRUE if the point */  12
/* is in the space, FALSE if not. */ 13
} t msp;  14

15

t msp *msp init ( t bas *bas, t pdim k, t pdim q );  16
/* Constructor: create a new subspace by spanning the given basis bas */  17
/* in PG(k,q). */ 18
#define msp del(sp) (bas del(sp−>bas), pt del(sp−>pt), free ( sp ))  19
/* Destructor: deallocate memory. */  20
char msp subset ( t msp *a, t msp *b );  21
/* Return TRUE if a is a subspace of b. */  22
void msp print ( t msp *sp, FILE *stream, t pdim k, t pdim q ) ;  23
/* List all points in sp by coordinate representation. */  24

25

/* End of subspace.h */  26

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: subspace.c,v 5.0 1998/12/20 00:25:51 georg Exp $ */  2

3

#include "common.h"  4

5 6

#include "pg.h"  7

#include "points.h"  8
#include "subspace.h"  9

#include "aux.h"  10

11

t msp *msp init ( t bas *bas, t pdim k, t pdim q ) {  12
t msp *sp;  13
t ps ptno, i, imax;  14

15

sp  = getmem ( sizeof (t msp) );  16
ptno = pg q (q,k);  17
sp−>bas = bas;  18
sp−>pt = getmem ( ptno*sizeof (char) );  19

20

for ( i=0; i < ptno; ++i ) sp−>pt[i] = 0;  21

22

imax = pt qpow ( q, bas−>m + 1 );  23
for ( i=1; i < imax; ++i ) sp−>pt[bas comb( bas, i, k, q )] = 1;  24

25

return ( sp );  26
}  27

28

char msp subset ( t msp *a, t msp *b ) {  29
int i;  30
for ( i = 0; i <= a−>bas−>m; i++ ) {  31
/* If one point in the basis of a is not in b, a is not in b. */  32
if ( ! msp in ( a−>bas−>bas[i], b ) ) return ( FALSE );  33
};  34
/* The basis of a is in b, so a is in b. */  35
return ( TRUE );  36
}  37

38

void msp print ( t msp *sp, FILE *stream, t pdim k, t pdim q ) {  39
t ps ptno, i, imax;  40
t pdim c[12];  41

42

ptno = pg q (q,k);  43
for ( i = 0; i < ptno; ++i )  44
if ( msp in(i,sp) ) {  45
fprintf ( stream, "%i ", i );  46
pt fromno ( c, i, k, q );  47
pt print ( c, stream, k, q );  48
putc ( '\n', stream );  49
};  50
}  51

52

/* End of subspace.c */  53

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pgmsp.h,v 5.0 1998/12/20 00:25:03 georg Exp $ */  2

3

#include "pg.h"  4

#include "subspace.h"  5

6

/* Collection of subspaces */  7
typedef struct s s {  8
t msp ***s;  9
/* s[i][j] is a pointer to a t msp for the j’th i-space. */  10
} t s;  11

12

t ps pg get ( t pg *pg, int arg[ ], int argno ) ;  13
/* Get the subspace spanned by the points in arg */  14

15

/* Function to create ASCII prints. */  16
char pg print ( FILE *stream, t pg *pg );  17
/* Print the entire data structure. (Debug purposes) */  18
char pg sprint ( FILE *stream, t pg *pg );  19
/* Print a list of subspaces for each space. (Debug purposes) */  20
char pg pprint ( FILE *stream, t pg *pg );  21
/* Print a list of points for each space. (Debug purposes) */  22

2.3. THE COMPLETE INCIDENCE STRUCTURE

23

char pg ssprint ( FILE *stream, t pg *pg,  24
t pdim dim1, t pdim dim2, t ps ps ) ;  25
/* Print all dim2-spaces being a sub-/superset of dim1-space #ps */  26
char pg space ( FILE *stream, t pg *pg, t pdim dim, t ps ps ) ;  27
/* Print all points in a given subspace */  28

29

/* Operations on t s */  30
t s *s init ( t pdim k, t pdim q );  31
/* Constructor: create the t s struct, and initialize the array **  32
** with (t msp*) NULL pointers. The t msp structs are created **  33
** pg create() */ 34
int s del ( t s *s, t pdim k, t pdim q );  35
/* Destructor: deallocate memory */  36
int s print ( t s *s, FILE *stream, t pdim k, t pdim q ) ;  37
/* Print the entire representation. (For debug purposes.) */  38

39

/* End: pgmsp.h */  40
/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pgmsp.c,v 5.0 1998/12/20 00:25:01 georg Exp $ */  2

3

#include "common.h"  4
#include "pgmsp.h"  5
#include "points.h"  6

7

t s *sp = NULL;  8

9

/* Static functions */  10
static char pg supprint ( FILE *stream, t pg *pg,  11
t pdim dim, t pdim supdim, t ps ps ) ;  12
/* Print all superspaces of a given dimension for a given subspace */  13
static char pg subprint ( FILE *stream, t pg *pg,  14
t pdim dim, t pdim subdim, t ps ps ) ;  15
/* Print all subspaces of a given dimension for a given subspace */  16
static t ps pg auxget ( t pg *pg, t pdim m, t ps s, t ps p ) ;  17
/* Find an m+1-space through m-space #s and point #p */  18

19

/* t s (subspaces) */  20

21

t s *s init ( t pdim k, t pdim q ) {  22
t s *s;  23
t ps elno, h, i;  24

25

s  = getmem ( sizeof (t s) );  26
s−>s = getmem ( k*sizeof(void*) );  27

28

for ( h = 0; h < k; ++h ) {  29
elno = pg elno ( q,k,h );  30
s−>s[h] = getmem ( elno*sizeof(void*) );  31
for ( i = 0; i < elno; ++i ) s−>s[h][i] = (t msp*) NULL;  32
};  33
return ( s );  34
}  35

36

int s del ( t s *s, t pdim k, t pdim q ) {  37
t ps elno, h,i;  38

39

for ( h = 0; h < k; ++h ) {  40
elno = pg elno ( q,k,h );  41
for ( i = 0; i < elno; ++i ) {  42

CHAPTER 2. PROJECTIVE GEOMETRY

msp del ( s−>s[h][i] );  43
free ( s−>s[h][i] );  44
};  45
free ( s−>s[h] );  46
};  47

48

free ( s−>s );  49
free ( s );  50
return ( 0 );  51
}  52

53

int s print ( t s *s, FILE *stream, t pdim k, t pdim q ) {  54
t ps i, elno; t pdim m;  55
fprintf ( stream, "Points:\n" );  56
elno = pg elno ( q, k, 0 );  57
for ( i=0; i < elno; ) {  58
pt noprint ( i++, stream, k, q );  59
putc ( '\n', stream );  60
};  61
for ( m=0; m++ < k−1; ) {  62
fprintf ( stream, "%i-spaces:\n", m );  63
elno = pg elno ( q, k, m );  64
for ( i=0; i < elno; ++i ) {  65
fprintf ( stream, "%i-space #%i:\n", m, i );  66
msp print ( s−>s[m][i], stream, k, q );  67
};  68
};  69
return ( 0 );  70
}  71

72

/* functions on t pg */  73
t ps pg auxget ( t pg *pg, t pdim m, t ps s, t ps p ) {  74
/* Optimise using a t s struct. */  75
int i, im, j, jm;  76
im = pg theta ( m, m+1, pg−>k, pg−>q );  77
jm = pg theta ( 0, m+1, pg−>k, pg−>q );  78
/* Consider the im m+1-spaces through m-space #s */  79
for ( i = 0; i < im; ++i ) {  80
/* Consider the jm m+1-spaces through point #p */  81
for ( j = 0; j < jm; ++j ) {  82
if ( pg−>ps[m][0][s][i] == pg−>ps[0][m][p][j] )  83
return ( pg−>ps[m][0][s][i] );  84
}  85
}  86
return ( pg noel ); /* No proper space found. */  87
}  88

89

/* Span a space by points */  90
t ps pg get ( t pg *pg, int arg[ ], int argno ) {  91
int i, j, im, jm, m, tmp, p;  92
t ps s;  93

94

s = arg[−−argno];  95
/* argno is now the (assumed) dimension of the subspace */  96

97

for ( m = 0; m < argno; ++m ) {  98
if ( pg noel == ( s = pg auxget( pg, m, s, arg[m] ) ) )  99
return ( pg noel );  100
};  101
return ( s );  102
}  103

104

/* File printing */  105
char pg print ( FILE *stream, t pg *pg ) {  106
t ps g, gm, h, hm, i, im;  107

108

for ( gm = pg−>k−1, g = 0; g < gm; ++g ) {  109
im = pg elno ( pg−>q, pg−>k, g );  110
for ( hm = pg−>k−g−1, h = 0; h < hm; ++h ) {  111
for ( i = 0; i < im; ++i ) pg supprint ( stream, pg, g, g+h+1, i );  112
};  113
};  114
return ( 0 );  115
}  116

117

char pg supprint ( FILE *stream, t pg *pg,  118
t pdim dim, t pdim supdim, t ps ps ) {  119
t ps j, jm;  120
jm = pg theta ( dim, supdim, pg−>k, pg−>q );  121

fprintf ( stream, "%i-spaces including %i-space #%i:\n", supdim, dim, ps );  122

supdim −= dim + 1;  123
for ( j = 0; j < jm; ++j ) {  124
fprintf ( stream, "%i", pg−>ps[dim][supdim][ps][j] );  125
if ( 9 == j % 10 ) putc ( '\n', stream ) ;  126
else putc ( '\t', stream );  127
};  128
putc ( '\n', stream );  129
}  130

131

char pg subprint ( FILE *stream, t pg *pg,  132
t pdim dim, t pdim subdim, t ps ps ) {  133
t ps j, jm; char c;  134
extern t s *sp;  135
t msp *ss;  136

137

ss = sp−>s[dim][ps];  138
jm = pg elno ( pg−>q, pg−>k, subdim );  139
fprintf ( stream, "%i-spaces in %i-space #%i:\n", subdim, dim, ps );  140
for ( c = j = 0; j < jm; ++j ) {  141
if ( msp subset ( sp−>s[subdim][j], ss ) ) {  142
/* Print the subspace number and separating white space. */  143
fprintf ( stream, "%i%c", j, (9==c++?(c=0,'\n'):'\t') );  144
};  145
};  146
if ( c != 0 ) putc ( '\n', stream );  147
}  148

149

char pg ssprint ( FILE *stream, t pg *pg,  150
t pdim dim1, t pdim dim2, t ps ps ) {  151
return (  152
( dim1 < dim2 ? pg subprint : pg supprint )( stream, pg, dim2, dim1, ps )  153
);  154
}  155

156

char pg pprint ( FILE *stream, t pg *pg ) {  157
t ps g, gm, i, im;  158

159

for ( gm = pg−>k−1, g = 0; g < gm; ++g ) {  160
im = pg elno ( pg−>q, pg−>k, g+1 );  161
for ( i = 0; i < im; ++i ) {  162
pg space ( stream, pg, g+1, i );  163
};  164
};  165
return ( 0 );  166

}  167

168

char pg space ( FILE *stream, t pg *pg, t pdim dim, t ps ps ) {  169
t ps j, jm, h, hm, c;  170
hm = pg theta ( 0, dim, pg−>k, pg−>q );  171
jm = pg elno ( pg−>q, pg−>k, 0 );  172
if ( 0 == dim ) {  173
fprintf ( stream, "Point #%i.\n", ps );  174
return ( FALSE );  175
};  176
fprintf ( stream, "Points in %i-space #%i:\n", dim−−, ps );  177
for ( c = j = 0; j < jm; ++j ) {  178
for ( h = 0; h < hm; ++h ) {  179
if ( pg−>ps[0][dim][j][h] == ps ) {  180
fprintf ( stream, "%i", j );  181
if ( 9 == c++ ) {  182
c = 0;  183
putc ( '\n', stream );  184
} else {  185
putc ( '\t', stream );  186
};  187
};  188
};  189
};  190
putc ( '\n', stream );  191
return ( TRUE );  192
}  193

194

char pg sprint ( FILE *stream, t pg *pg ) {  195
t ps g, gm, i, im;  196
for ( gm = pg−>k−1, g = 0; g < gm; ++g ) {  197
im = pg elno ( pg−>q, pg−>k, g+1 );  198
for ( i = 0; i < im; ++i ) pg subprint ( stream, pg, g+1, g, i );  199
};  200
return ( 0 );  201
}  202

203

/* End of pgmsp.c */  204

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pginit.h,v 5.0 1998/12/20 00:24:57 georg Exp $ */  2

3

#include "pgmsp.h"  4

5

/* Point Queue */  6
typedef struct s ptq {  7
t ps size, next;  8
char *pt;  9
} t ptq;  10

11

/* Operations on t pg */  12
#define pg init(k,q) pg create(k,q,NULL)  13
t pg *pg create ( t pdim k, t pdim q, t s *s );  14
/* Constructor: allocate memory and build the geometry. ** 15
** If s is NULL pg create builds its own t s struct, which **  16
** is deleted after use. Otherwise s is used and it remains **  17
** intact. */ 18
char pg dump ( FILE *stream, t pg *pg );  19
/* Store the geometry on a binary file */  20

21

/* Operations on t ptq */  22

t ptq *ptq alloc ( t ps size );  23
/* Constructor: allocate memory */  24
#define ptq init(s) ptq reinit ( ptq alloc ( s ) )  25
/* Constructor: create a queue with all points in it */  26
t ptq *ptq reinit ( t ptq *ptq );  27
/* Reinitialize: put all points in the queue */  28
#define ptq del(ptq) (free ( ptq−>pt ), free ( ptq ))  29
/* Destructor: deallocate memory */  30
void ptq rmset ( t ptq *ptq, t msp *sp );  31
/* remove all points in sp from the queue */  32
t ps ptq extract ( t ptq *ptq );  33
/* return the next point which is removed from the queue */  34
#define ptq empty(ptq) ( ptq−>next == ptq−>size ) 35
/* Return TRUE if the queue is empty */  36
#define ptq remove(ptq,p) ( ptq−>pt[p] = FALSE )  37
/* Remove a single point from the queue */  38

39

/* End: pginit.h */  40

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pginit.c,v 5.0 1998/12/20 00:24:52 georg Exp $ */  2

3

#include "common.h"  4

5

#include "pginit.h"  6
#include "points.h"  7

8

/* Constructor */  9
t pg *pg create ( t pdim k, t pdim q, t s *ps ) {  10
t pg *pg; /* Return value */  11
t ptq *ptq;  12
t s *s; /**/ 13
t pdim m;  14
t ps  e, f, g, gm, h, i, j, ptno, elno, pt;  15
t ps  melno, helno;  16
t bas *bas;  17

18

pg = pg alloc ( k, q );  /* Allocate memory */  19
ptno = pg elno ( q, k, 0 );  /* No. of points */  20

21

/* Allocate auxilliary storage */  22
s = ( NULL == ps ) ? s init ( k, q ) : ps;  23
ptq = ptq alloc ( ptno );  24

25

/* Make the Q(i) function table */  26
for ( gm = pg−>k, g = 0; g <= gm; ) {  27
pg−>ptno[g++] = pg q ( pg−>q, g );  28
};  29

30

/* Creating points */  31
for ( i = 0; i < ptno; ++i ) {  32
bas = bas init ( 0 );  33
*(bas−>bas) = i;  34
s−>s[0][i] = msp init ( bas, k, q );  35
};  36

37

/* Creating (m+1)-spaces, m >= 0 */  38
for ( m = 0; m < k−1; ++m ) {  39
elno = pg elno ( q, k, m ); /* No. of m-spaces */ 40
j = 0;  41
gm = pg theta ( m, m+1, k, q );  42

/* No. of m+1-dimensional superspaces for a given m-space */  43

44

/* Creating superspaces of m-space #i */  45
for ( i = 0; i < elno; ++i ) {  46
ptq reinit (ptq);  47
/* ptq represents the set of all points */  48
ptq rmset ( ptq, s−>s[m][i] );  49
/* All points in m-space #i are removed from ptq */  50

51

for ( g = 0; g < gm && pg−>ps[m][0][i][g] != pg noel; ) {  52
ptq rmset ( ptq, s−>s[m+1][pg−>ps[m][0][i][g++]] );  53
}; /* Any point is removed if it is in a m+1-space already created */  54
/* as a superspace of m-space #1; also g superspaces are  */  55
/* already found, we will find the g^th one.  */  56

57

while ( pg noel != ( pt = ptq extract ( ptq ) ) ) {  58
bas = bas copy ( m+1, s−>s[m][i]−>bas );  59
bas−>bas[m+1] = pt;  60
s−>s[m+1][j] = msp init ( bas, k, q );  61
/* span an m+1-space by taking m+1 points spanning m-space #i */  62
/* and one point from ptq.  */  63

64

ptq rmset ( ptq, s−>s[m+1][j] );  65
/* Remove from ptq the points in the newly created m+1-space. */  66

67

for ( e=i+1; e < elno; ++e ) {  68
if ( msp subset ( s−>s[m][e], s−>s[m+1][j] ) ) {  69
/* m-space #e is also in m+1-space #j */  70
for ( f=0; pg−>ps[m][0][e][f] != pg noel &&  71
pg−>ps[m][0][e][f] != j ; ++f ) {};  72
/* f superspaces of m-space #e was found before m+1-space #j. */  73
pg−>ps[m][0][e][f] = j;  74
/* This is the f^th superspace of m-space #e. */  75
};  76
};  77
pg−>ps[m][0][i][g++] = j++;  78
/* Of course, m+1-space #j is a superspace of m-space #i; */  79
/* by definition. */ 80
}; /* [while] ptq is now the empty set */  81
Invariant ( g == gm ) ;  82
/* We are supposed to have found g superspaces of dimension */  83
/* m+1 of m-space #i. */ 84
};  85
Invariant ( j == pg elno ( q, k, m + 1 ) ) ;  86
/* We have found j m+1-spaces — */ 87
/* hopefully, that’s the correct number. */  88
};  89

90

/* Find for each m-space, s, the l-spaces, l > m+1, having s as a subspace */  91
for ( m = 0; m < k−2; ++m ) {  92
melno = pg elno ( q, k, m );  93
for ( h = 0; h++ < k−2−m; ) {  94
helno = pg elno ( q, k, m+h+1 );  95
gm = pg theta ( m, m+h+1, k, q );  96
for ( i = 0; i < melno; ++i ) {  97
for ( g = j = 0; j < helno; ++j ) {  98
if ( msp subset ( s−>s[m][i], s−>s[m+h+1][j] ) ) {  99
Invariant ( g < gm );  100
pg−>ps[m][h][i][g++] = j;  101
};  102
};  103
};  104

};  105
};  106

107

/* Deallocate auxilliary storage */  108
if ( NULL == ps ) s del ( s, k, q );  109
ptq del ( ptq );  110

111

return ( pg );  112
}  113

114

/* File dumping */  115
char pg dump ( FILE *stream, t pg *pg ) {  116
t ps g, gm, h, hm, i, im, j, jm;  117
fprintf ( stream, PG FILEID );  118
putc ( pg−>k, stream );  119
putc ( pg−>q, stream );  120

121

for ( gm = pg−>k−1, g = 0; g < gm; ++g ) {  122
im = pg elno ( pg−>q, pg−>k, g );  123
for ( hm = pg−>k−g−1, h = 0; h < hm; ++h ) {  124
jm = pg theta ( g, g+h+1, pg−>k, pg−>q );  125
for ( i = 0; i < im; ++i ) {  126
for ( j = 0; j < jm; ++j ) putshort ( stream, pg−>ps[g][h][i][j] );  127
};  128
};  129
};  130
return ( 0 );  131
}  132

133

/* End of pginit.c */  134

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pgaux.c,v 5.0 1998/12/20 00:24:47 georg Exp $ */  2

3

#include "common.h"  4

5

#include "pginit.h"  6
#include "points.h"  7

8

/* Point queue */  9
t ptq *ptq alloc ( t ps size ) {  10
t ptq *ptq;  11
ptq = getmem ( sizeof ( t ptq ) );  12
ptq−>size = size;  13
ptq−>pt = getmem ( size + 1 );  14
return ( ptq );  15
}  16

17

t ptq *ptq reinit ( t ptq *ptq ) {  18
static t ps i;  19
ptq−>pt[ptq−>size] = 0;  20
ptq−>next = 0;  21
for ( i = 0; i < ptq−>size; ++i ) ptq−>pt[i] = TRUE;  22
return ( ptq );  23
}  24

25

void ptq rmset ( t ptq *ptq, t msp *sp ) {  26
static int i ;  27
Invariant ( sp != NULL );  28
for ( i=0; i < ptq−>size; ++i ) {  29
if ( msp in (i,sp) )  30

ptq remove ( ptq, i );  31
};  32
}  33

34

t ps ptq extract ( t ptq *ptq ) {  35
while ( ( ! ptq empty (ptq) ) && ( ptq−>pt[ptq−>next] == FALSE ) )  36
++(ptq−>next);  37
return ( ptq empty(ptq) ? pg noel : (ptq−>next)++ );  38
}  39

40

/* End: pgaux.c */  41

Chapter 3

Value Assignments

3.1 The basic modules

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: val.h,v 5.0 1998/12/20 00:26:00 georg Exp $ */  2

3

#include "valaux.h"  4

#define NO MORE VAL  0  5
#define RET VAL  1  6
#define val noclass  255  7
#define val novalue  255  8
#define V ALLOCN  64*1024  9

10

/* t v is a value assignment with a classification. */  11
typedef struct s v {  12
t pg *pg; /* The projective geometry used */  13
t class class; /* The class number */  14
t value *val; /* The values for each point */  15
char  ok; /* true if the assignment is correctly classified */  16
t ds  ds; /* The difference sequence */  17
} t v;  18

19

/* t val stores the value assigment of all subspaces. */  20
typedef struct s val {  21
t pg *pg; /* The projective space */ 22
t value **val; /* The values */  23
#ifdef ALLOW FIX  24
char *fix; /* Flag for fixed values */ 25
#endif  26
t mval **m;  /* The maximum values */  27
t v  *v;  /* Pointer to a classification of the value assignment */  28
t value  total; /* The total value summed over all points */  29
t class nclass; /* The number of possible classes. */  30
} t val;  31

32

/* Functions on t val */  33

34

#define val valprint(s,val) (fprintf( s, ";\n"), v valprint( s,val−>v ), 1)  35
/* Print value assignment and classification */  36

37

t val *val allocfor ( t pg *pg, t v *v );  38
/* Make a t val instance using the instance of t v */  39

40

t val *val clear ( t val *val, t value initvalue );  41

CHAPTER 3. VALUE ASSIGNMENTS

/* Initialize the value assignment with a specified initvalue. */  42

43

#define val reinit(v) ( val clear ( v, val novalue ) )  44
/* Initialize: no points have any value yet */  45

46

t val *val stepinit ( t val *val, t value del ) ;  47
/* Initialize the assignment for val stepval(). */  48

49

void val del  ( t val *v );  50
/* Dispose the memory */  51

52

#define val class(v) val getclass ( v, NULL )  53
t class val getclass ( const t val *v, FILE *fs );  54
/* Get the class number of the assignment. */  55

56

t ds *val ds  ( t val *v );  57
/* Get the difference sequence from the assignment. */  58

59

char val stepval ( t val *v );  60
/* Step to the next value assignment permitted. */  61

62

char val stepclass ( t val *v, t class c );  63
/* Step to the next permitted value assignment of the given class. */  64

65

t val *val load  ( FILE *stream, t pg *pg ) ;  66
/* Load from binary file, this is only used by vt load(), and it **  67
** does not load the fix array member.  */  68

69

int  val dump  ( FILE *stream, t val *v ) ;  70
/* Write to binary file, this is only used by vt dump(), and it **  71
** does not write the fix array member.  */  72

73

t v *val freev  ( t val *val ) ;  74
/* Make a copy of the t v struct field */  75

76

char val assign ( t val *val, FILE *in ) ;  77
/* Assign values read from file */  78

79

void val sumval ( t val *v );  80
/* Compute the subspace values */  81

82

void val statusreport ( t val *v );  83
/* Write a status report */  84

85

void val fixdump ( FILE *stream, t val *val );  86
void val fixload ( FILE *stream, t val *val );  87
/* Dump and load the fix array member, used in vt load()/vt dump(). */  88

89

#define val classprint(val,f)  v classprint(f,val−>v)  90
/* Print the class number and difference sequence */  91

92

#define val alloc(p) val allocfor(p,NULL )  93
/* Allocate memory for a t val */  94

95

#define val init(pg) (val reinit(val alloc(pg)))  96
/* Allocate memory and initialise a t val */  97

98

#define val nextv(v) ( ( NO MORE VAL == val stepval ( v ) ) ? NULL : v−>v )  99
/* Step to the next value assignment and return the t v representation */  100

101

#define val vprint(s,a) ( v print ( s, a−>v ) )  102
/* Print the value assignment */  103

3.1. THE BASIC MODULES

104

#define val classify(p) (void)( val class(p), val ds(p), v cert( p−>v ) )  105
/* Compute the class number and difference sequence */  106

107

/* Macroes to set and fix values of points. */  108
#ifdef ALLOW FIX  109
# define val set(vv,p,a) ( vv−>v−>val[p] = a, vv−>fix[p] = TRUE )  110
# define val setval(vv,p,a) ( vv−>v−>val[p] = a )  111
# define val fix(v,c)  ( v−>fix[c] )  112
# define val fixit(v,c)  ( v−>fix[c] = TRUE )  113
#else  114
# define mode f TRUE 115
# define val fix(v,c) FALSE  116
#endif  117

118

/* Functions on t v */  119
t v *v alloc ( t pg *pg, t value *val ) ;  120
/* Constructor: allocate memory */  121
char v dump ( FILE *stream, t v *v ) ;  122
/* Store the struct on a binary file */  123
t v *v load ( FILE *stream, t pg *pg ) ;  124
/* Load the struct from a binary file */  125
int v compare ( const void *a, const void *b ) ; 126
/* Compare the to value assignments by their classification. **  127
** To be used with tsearch(3). */ 128
char v valprint ( FILE *stream, t v *v ) ;  129
/* Print value assignment in ASCII */  130
#define v print(f,v) ( v classprint(f,v) && v valprint(f,v) )  131
/* Print class number, difference sequence and values in ASCII */  132
char v classprint ( FILE *out, t v *v ) ;  133
/* Print the classification (class number and DS) in ASCII */  134
#define v ok(v) ( v−>ok ) 135
/* Return true if the classification is up to date. */  136
#define v reinit(v) ( v−>ok = 0 )  137
/* Claim that the classification is not up to date. */  138
#define v cert(v) ( v−>ok = 1 )  139
/* Claim that the classification is up to date. */  140

141

/* End of val.h */  142
/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: val.c,v 5.0 1998/12/20 00:25:56 georg Exp $ */  2

3

#include "common.h"  4

5

#include "pg.h"  6

#include "val.h"  7
#include "aux.h"  8

9

static char val auxchain ( const t val *v, t pdim m, t ps ps );  10
/* Recursive validation of the chain condition */  11

12

static char val chained ( const t val *v );  13
/* Check the chain condition */  14

15

static void val nullsums ( t val *v );  16
/* Nullify subspace values */  17

18

/* Constructor */  19
t val *val allocfor ( t pg *pg, t v *v ) {  20
t pdim m;  21

t ps elno;  22
t class i;  23
t val *val;  24

25

val = getmem ( sizeof(t val) );  26

27

val−>v  = ( v == NULL ? ( v alloc( pg, NULL ) ) : v );  28
val−>pg  = pg;  29
val−>val = getmem ( (pg−>k)*sizeof (void*) );  30
val−>m = getmem ( (pg−>k)*sizeof (void*) ); 31
*(val−>val) = val−>v−>val;  32
val−>m[0] = mval init ( pg noel );  33
#ifdef ALLOW FIX  34
val−>fix = getmem ( pg eln ( pg, 0 ) );  35
#endif  36
for ( m=1; m < pg−>k; ++m ) {  37
val−>m[m] = mval init ( pg noel );  38
elno = pg eln ( pg, m ); 39
val−>val[m] = getmem ( elno*sizeof (t value) );  40
};  41

42

for ( val−>nclass = i = 0; i < pg−>k; ++i ) val−>nclass += i;  43
val−>nclass = 1<<val−>nclass;  44

45

return ( val );  46
} /* val allocfor() */  47

48

/* Store on binary file. */  49
int val dump ( FILE *stream, t val *v ) {  50
putc ( v−>pg−>k, stream );  51
putc ( v−>pg−>q, stream );  52
v cert ( v−>v ); /* Cheating: escape invariant test in v dump (). */  53
v dump ( stream, v−>v );  54
return ( 1 );  55
} /* val dump() */  56

57

/* Constructor: Load from binary file. */  58
t val *val load ( FILE *stream, t pg *pg ) {  59
t val *val;  60
t pdim k, q;  61
char InFile[PATH NAME L];  62
FILE *InStream;  63
k = getc ( stream ); q = getc ( stream );  64
if ( NULL == pg ) {  65
sprintf ( InFile, "%s/pg(%i,%i)", PG DIR, k, q );  66
InStream = fileopen ( InFile, "rb" );  67
pg = pg load ( InStream );  68
fclose ( InStream );  69
};  70
val = val allocfor ( pg, v load ( stream, pg ) );  71
v reinit ( val−>v );  72
val sumval ( val ); /* Sum the values of subspaces. */ 73
val classify ( val ); /* Classify the initial value assignment */  74
return ( val );  75
} /* val load() */  76

77

/* Release the value assignment from auxilliary data structure (by copying). */  78
t v *val freev ( t val *val ) {  79
t v *v;  80
t ps ptno, i;  81

82

v = val−>v; /* Get a pointer to the t v struct */  83

3.1. THE BASIC MODULES

ptno = pg qpow ( val−>pg, val−>pg−>k );  84

85

/* Make a new t v struct for val */  86
v reinit ( ( val−>v = v alloc ( val−>pg, NULL ) ) );  87
/* Copy data from v to val->v */  88
for ( i=0; i<ptno; ++i ) {  89
val−>v−>val[i] = v−>val[i];  90
};  91
/* Incorporate the value assignment in the val array of t val */  92
val−>val[0] = val−>v−>val;  93

94

return ( v );  95
} /* val freev() */  96

97

/* Reinitialize */  98
t val *val clear ( t val *val, t value initvalue ) {  99
t pdim m;  100
t ps i, elno;  101
val−>total = 0;  102
for ( m=0; m < val−>pg−>k−1; ++m ) {  103
elno = pg eln ( val−>pg, m );  104
#ifdef ALLOW FIX  105
if ( 0 == m ) for ( i=0; i < elno; ++i ) val−>fix[i] = FALSE;  106
#endif  107
for ( i=0; i < elno; ++i ) val−>val[m][i] = initvalue;  108
mval reinit ( val−>m[m] );  109
};  110
v reinit ( val−>v );  111
val nullsums ( val );  112

113

return ( val );  114
} /* val clear */  115

116

t val *val stepinit ( t val *val, t value del ) {  117
t pdim m;  118
t ps i, elno;  119

120

val clear ( val, 0 );  121

122

*(val−>v−>val) = del;  123
for ( m=0; m < val−>pg−>k; ) val−>v−>val[pg qpow(val−>pg,m++)] = 1;  124

125

val sumval ( val );  /* Sum the values of subspaces. */  126
val classify ( val ); /* Classify the initial value assignment */  127

128

return ( val );  129
} /* val stepinit() */  130

131

/* Destructor */  132
void val del ( t val *v ) {  133
t pdim m;  134
if ( NULL == v ) return ;  135
for ( m=0; m < v−>pg−>k−1; ++m ) {  136
mval del ( v−>m[m] );  137
free ( v−>val[m] );  138
};  139
free ( v−>val );  140
free ( v−>m );  141
free ( v );  142
} /* val del */  143

144

/* Classify (part 1) */  145

t class val getclass ( const t val *v, FILE *fs ) {  146
t cond cond = 0;  147
t pdim m,l;  148
t ps i, j, jmax;  149
if ( v ok ( v−>v ) ) return ( v−>v−>class );  150
v−>v−>class = 0;  151
for ( m=0; m < v−>pg−>k − 1; ++m ) {  152
for ( l = m+1; l < v−>pg−>k; ++l ) {  153
jmax = pg thet(v−>pg,m,l);  154
mval reset(v−>m[m]);  155
while ( pg noel != ( i = mval next(v−>m[m]) ) ) {  156
for ( j = 0; j < jmax; ++j ) {  157
if ( v−>val[l][v−>pg−>ps[m][l−m−1][i][j]] == v−>m[l]−>v ) {  158
if ( NULL != fs ) {  159

          fprintf ( fs, "%i-space #%i is in %i-space #%i.\n",  160

m, i, l, v−>pg−>ps[m][l−m−1][i][j] );  161
} else {  162
j = jmax;  163
};  164
mval nomore(v−>m[m]);  165
v−>v−>class = ( v−>v−>class | ( 1 << cond ) );  166
};  167
};  168
};  169
++cond;  170
};  171
};  172

173

if ( ( v−>v−>class == v−>nclass − 1 ) && val chained ( v ) )  174
v−>v−>class = v−>nclass;  175
return ( v−>v−>class );  176
} /* val getclass */  177

178

/* Classify (part 2) */  179
t ds *val ds ( t val *val ) {  180
register t pdim i;  181
register t value s = 0;  182

183

if ( v ok ( val−>v ) ) return ( &val−>v−>ds );  184
for ( i=0; i < val−>pg−>k; ++i ) {  185
s += ( val−>v−>ds.delta[i] = ( val−>m[i]−>v − s ) );  186
};  187
val−>v−>ds.delta[val−>pg−>k] = val−>total − s;  188
return ( &val−>v−>ds );  189
} /* val ds */  190

191

/* Step to the next possible value assignment. */  192
char val stepval ( t val *v ) {  193
t ps maxc, lst;  194
register t ps c;  195
t value max;  196
t pdim m;  197
t ps i, elno;  198

199

c = lst = pg qpow(v−>pg,v−>pg−>k) − 1;  200
max = v−>v−>val[maxc = pg qpow(v−>pg, m = v−>pg−>k−1)];  201

202

while ( val fix ( v, c ) | | ( v−>v−>val[c]++ >= max ) ) {  203
if ( −−c == 0 ) return ( NO MORE VAL );  204
if ( m == 0 ) {  205
max = v−>v−>val[maxc = c − 1];  206
/* Assume at least one point with lower value. */  207

if ( ( c == v−>pg−>q ) && ( max == v−>v−>val[0] ) ) −−max;  208
} else if ( c == maxc ) {  209
max = v−>v−>val[maxc = pg qpow(v−>pg, −−m)];  210
};  211
};  212

213

if ( c < lst ) {  214
/* Recompute all subspace values. */  215
maxc = pg qpow(v−>pg, ++m);  216

217

while ( c++ < lst ) {  218
if ( ! val fix (v,c) ) {  219
if ( c == maxc ) {  220
maxc = pg qpow(v−>pg, ++m);  221
v−>v−>val[c] = 1;  222
} else {  223
v−>v−>val[c] = 0;  224
};  225
};  226
};  227

228

v reinit ( v−>v );  229
val sumval ( v ); /* Sum values for subspaces */ 230
} else {  231
/* Only one point has increased value; increase value of subspaces **  232
** including that point. */ 233
for ( m=0; m < v−>pg−>k; ++m ) mval reinit ( v−>m[m] );  234

235

++v−>total;  236
for ( m = 0; m++ < v−>pg−>k−1; )  237
for ( elno = pg thet(v−>pg,0,m), i=0; i < elno; ++i )  238
++v−>val[m][v−>pg−>ps[0][m−1][c][i]];  239

240

for ( m = 0; m < v−>pg−>k; ++m )  241
for ( elno = pg eln( v−>pg, m ), i = 0; i < elno; ++i )  242
mval add ( v−>m[m], i, v−>val[m][i] );  243
};  244
val classify ( v );  245

246

return ( RET VAL );  247
} /* val stepval() */  248

249

/* Reset the value of each m-space, m > 0, to zero. */  250
void val nullsums ( t val *v ) {  251
register t pdim m = 0;  252
register t ps i, elno;  253

254

v−>total = 0;  255
for ( m=0; m < v−>pg−>k; ++m ) mval reinit ( v−>m[m] );  256
for ( m=0; m++ < v−>pg−>k−1; ) {  257
elno = pg eln ( v−>pg, m );  258
for ( i=0; i < elno; ) v−>val[m][i++] = 0;  259
};  260
return ;  261
} /* val nullsums */  262

263

/* Evaluate the weight of each m-space, m > 0 */  264
void val sumval ( t val *v ) {  265
t pdim m;  266
t ps p, i, ptno, elno;  267

268

val nullsums ( v ); /* Reinitialize */  269

CHAPTER 3. VALUE ASSIGNMENTS

270

for ( ptno = pg qpow ( v−>pg, v−>pg−>k ), p = 0; p < ptno; ++p ) {  271
if ( 0 != v−>val[0][p] ) {  272
v−>total += v−>val[0][p];  273
for ( m = 0; m++ < v−>pg−>k−1; ) {  274
for ( elno = pg thet(v−>pg,0,m), i=0; i < elno; ++i ) {  275
v−>val[m][v−>pg−>ps[0][m−1][p][i]] += v−>val[0][p];  276
};  277
};  278
};  279
};  280

281

for ( m = 0; m < v−>pg−>k; ++m ) {  282
for ( elno = pg eln( v−>pg, m ), i = 0; i < elno; ++i ) {  283
mval add ( v−>m[m], i, v−>val[m][i] );  284
};  285
};  286

287

return ;  288
} /* val sumval */  289

290

/* Check for the chain condition. */  291
char val chained ( const t val *v ) {  292
t pdim m=0;  293
t ps i;  294
mval reset( v−>m[m] );  295
while ( pg noel != ( i = mval next(v−>m[0]) ) ) {  296
if ( val auxchain ( v, 0, i ) ) return ( TRUE );  297
};  298
return ( FALSE );  299
} /* val chained() */  300

301

/* Auxilliary function for val chained(). */  302
char val auxchain ( const t val *v, t pdim m, t ps ps ) {  303
t ps j, jmax;  304
if ( m == v−>pg−>k − 1 ) return ( TRUE );  305
jmax = pg thet ( v−>pg, m, m+1 );  306
for ( j = 0; j < jmax; ++j ) {  307
if ( ( v−>val[m+1][v−>pg−>ps[m][0][ps][j]] == v−>m[m+1]−>v ) &&  308
val auxchain( v, m+1, v−>pg−>ps[m][0][ps][j] ) ) return ( TRUE );  309
};  310
return ( FALSE );  311
} /* val auxchain() */  312

313

/* Step to next value assignment in the specified class. */  314
char val stepclass ( t val *v, t class c ) {  315
char r;  316
r = val stepval ( v );  317
while ( ( RET VAL == r ) && ( val class ( v ) != c ) ) r = val stepval ( v );  318
return ( r );  319
} /* val stepclass() */  320

321

void val statusreport ( t val *v ) {  322
static long val repno = 0; /* Counter for the reports. */  323
FILE *stream;  324
extern char *StatusFile;  325
/* We use a global variable for the file name, so that this can **  326
** be used from a signal handler(SIG USR1).  */  327

328

stream = fileopen ( StatusFile, (0 == val repno++ ? "w" : "a") );  329
fprintf ( stream, "Status Report no.: %i\n", val repno );  330
val vprint ( stream, v );  331

fclose ( stream );  332
} /* val statusreport() */  333

334

void val fixdump ( FILE *stream, t val *val ) {  335
t ps ptno, i;  336
ptno = pg qpow ( val−>pg, val−>pg−>k );  337
for ( i=0; i < ptno; ++i ) {  338
#ifdef ALLOW FIX  339
val−>fix[i] = getc ( stream );  340
#endif  341
};  342
return ;  343
} /* val fixdump() */  344

345

void val fixload ( FILE *stream, t val *val ) {  346
t ps ptno, i;  347
ptno = pg qpow ( val−>pg, val−>pg−>k );  348
for ( i=0; i < ptno; ++i ) {  349
#ifdef ALLOW FIX  350
putc ( val−>fix[i], stream );  351
#else  352
putc ( 0, stream );  353
#endif  354
};  355
return ;  356
} /* val fixload() */  357

358

/* End of val.c */  359

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: valv.c,v 5.0 1998/12/20 00:26:20 georg Exp $ */  2

3

#include "common.h"  4

5

#include "pg.h"  6

#include "val.h"  7
#include "aux.h"  8

9

unsigned long v allocn = V ALLOCN;  10

11

t v *v alloc ( t pg *pg, t value *val ) {  12
/* Warning: This function does not enable deallocation of memory. */  13
static void *v first, *v next, *v last;  14
static int v size = −1;  15
t v *v;  16

17

/* If called with pg == NULL, we reinitialize */  18
if ( NULL == pg ) { v size = −1; return ( NULL ); };  19

20

/* If v size hasn’t been set we have to set it now. */  21
if ( v size < 0 ) {  22
int tmp;  23
v size = sizeof ( t v ) + pg−>ptno[pg−>k]*sizeof ( t value );  24
if ( tmp = ( v size % sizeof ( void* ) ) ) v size += sizeof (void*) − tmp;  25
v first = NULL;  26
};  27

28

if ( ( NULL == v first ) | |  29
(long)( v next = (char*) v next + v size ) >= (long)v last ) {  30
v first = v next = getmem ( v size*v allocn );  31
v last = (char*) v first + v size*v allocn;  32

CHAPTER 3. VALUE ASSIGNMENTS

};  33
v = (t v*) v next;  34
v−>pg = pg;  35
v−>val = ( ( NULL == val ) ?  36
(t value*) ( (char*) v next + sizeof (t v) ) : val );  37
return ( v );  38
}  39

40

char v classprint ( FILE *out, t v *v ) {  41
Invariant ( v ok ( v ) );  42
fprintf ( out, "#%i ", v−>class );  43
ds print ( out, &v−>ds, v−>pg−>k );  44
putc ( '\n', out );  45

46

return ( v ok ( v ) );  47
}  48

49

char v valprint ( FILE *stream, t v *v ) {  50
t ps i=0, elno;  51

52

elno = pg qpow ( v−>pg, v−>pg−>k );  53
while ( i < elno ) {  54
fprintf ( stream, "%i", v−>val[i++] );  55
putc ( ( ( 0 == ( i % 10 ) ) ? '\n' : '\t' ), stream );  56
};  57
if ( 0 != ( i % 10 ) ) putc ( '\n', stream );  58

59

return ( v ok ( v ) );  60
}  61

62

char v dump ( FILE *stream, t v *v ) {  63
int i, ptno;  64
Invariant ( v ok ( v ) );  65
putc ( v−>class, stream );  66
for ( i=0; i <= v−>pg−>k; ++i ) putshort ( stream, v−>ds.delta[i] );  67
ptno = pg qpow ( v−>pg, v−>pg−>k );  68
for ( i=0; i < ptno; ++i ) putc ( v−>val[i], stream );  69
return ( 1 );  70
}  71

72

t v *v load ( FILE *stream, t pg *pg ) {  73
t v *v;  74
t ps ptno;  75
int i;  76

77

v = v alloc ( pg, NULL );  78
if ( (t class)EOF == ( v−>class = getc ( stream ) ) ) return ( NULL );  79

80

for ( i=0; i <= pg−>k; ++i ) v−>ds.delta[i] = getshort ( stream );  81
ptno = pg qpow ( pg, pg−>k );  82
for ( i=0; i < ptno; ++i ) v−>val[i] = getc ( stream );  83
v cert ( v );  84

85

return ( v );  86
}  87

88

int v compare ( const void *a, const void *b ) {  89
t pdim i;  90
t v *v, *w;  91

92

v = ((t v*) a); w = ((t v*) b);  93

94

3.1. THE BASIC MODULES

Invariant ( v ok ( v ) && v ok ( w ) );  95
Invariant ( v−>pg−>k == w−>pg−>k );  96

97

if ( v−>class < w−>class ) return ( −1 );  98
if ( v−>class > w−>class ) return ( 1 );  99
for ( i=0; i <= v−>pg−>k; ++i ) {  100
if ( v−>ds.delta[i] < w−>ds.delta[i] ) return ( −1 );  101
if ( v−>ds.delta[i] > w−>ds.delta[i] ) return ( 1 );  102
};  103
return ( 0 );  104
}  105

106

/* End of valv.c */  107
/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: valaux.h,v 5.0 1998/12/20 00:26:11 georg Exp $ */  2

3

#include "stack.h"  4

5

/* Type defs */  6
typedef unsigned short t value;  7
/* Warning: t value is frequently handled as char. */  8
typedef unsigned short t class;  9
/* Warning: t class may be handled as char. */  10
typedef unsigned char t cond;  11

12

/* Structs */  13
typedef struct s mval {  14
t stack *s; /* A set of points having this value. */  15
t value v; /* The value. */ 16
} t mval;  17

18

/* t ds is a difference sequence. */  19
typedef struct s ds {  20
t value delta[MAX DIM];  21
} t ds;  22

23

/* Functions on t mval */  24
t mval *mval alloc ( t ps size );  25
/* Allocate memory for a t mval. */  26
void mval print ( FILE *stream, t mval *mv ) ;  27
/* Print the value, and the list of points on the given stream. */  28
#define mval del(mv) ( stk del(mv−>s), free(mv) ) 29
/* Destructor: dispose the memory */  30
#define mval reinit(mv) ( stk reinit ( mv−>s ), mv−>v = 0, mv )  31
/* Reinitialize: the value is zero, with no points. */  32
#define mval add(mv,pt,val) \  33
( ( val > mv−>v ) ? \  34
( mv−>v = val, stk replace ( mv−>s, pt ) ) : \  35
( ( val == mv−>v ) ? stk push ( mv−>s, pt ) : 0 ) )  36
/* If the point has greater value, let it replace all existing points, **  37
** and update the value, otherwise add the point if it has the same value */  38
#define mval init(s) ( mval reinit ( mval alloc ( s ) ) )  39
/* Constructor: Create and initialize the t mval */  40
#define mval reset(v) ( stk reset(v−>s) )  41
/* Reset the stack. Next time we inspect an point, we get the top-most. */  42
#define mval next(v) ( stk next(v−>s) )  43
/* Return the next point, without changing the stack. */  44
#define mval nomore(v) ( v−>s−>current = 0 )  45
/* TRUE if there are no more points to inspect with mval next */  46

47

/* Functions on t ds */  48
#define ds alloc(k) ( (t ds*) getmem ( sizeof (t ds) ) )  49
/* Allocate memory for the t ds. */  50
char ds print ( FILE *stream, t ds *ds, t pdim k ); 51
/* Print the difference sequence on the given stream. */  52

53

/* End of valaux.h */  54

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: valaux.c,v 5.0 1998/12/20 00:26:06 georg Exp $ */  2

3

#include "common.h"  4

#include "pg.h"  5

#include "valaux.h"  6

7

/* mval struct */  8
t mval *mval alloc ( t ps size ) {  9
t mval *mv;  10
mv = getmem ( sizeof ( t mval ) ) ;  11
mv−>s = stk alloc ( size );  12
return ( mv );  13
}  14

15

void mval print ( FILE *stream, t mval *mv ) {  16
char c = 0;  17
stk reset ( mv−>s );  18
fprintf ( stream, "[%i]:", mv−>v );  19
while ( stk more ( mv−>s ) ) {  20
fprintf ( stream, ( 8 == c++ ? "\n\t%i" : "\t%i" ), stk next ( mv−>s ) );  21
};  22
putc ( '\n', stream );  23
return ;  24
}  25

26

/* ds struct */  27
char ds print ( FILE *stream, t ds *ds, t pdim k ) {  28
t pdim i;  29
Invariant ( k > 0 );  30
fprintf ( stream, "( %i", ds−>delta[i=0] );  31
while ( i++ < k ) fprintf ( stream, ", %i", ds−>delta[i] );  32
fprintf ( stream, " )" );  33
return ( 1 );  34
}  35

36

/* End of valaux.c */  37

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: vtree.h,v 5.0 1998/12/20 00:26:34 georg Exp $ */  2

3

extern FILE *vt stream; /* Temporary pointer for macroes. */  4

5

typedef struct s vt {  6
void *root; /* The root of the binary search tree */  7
t val *val; /* Related data structure for the current value assignment. */  8
} t vt;  9

10

t vt *vt finfo ( FILE *stream ) ;  11
/* Print the dimension of the Projectiv Space used in the file stream. */  12

13

void vt insert ( t val *val, t vt *vt ) ;  14

/* Insert a value assignment in the tree. */  15

16

#define vt backup(f,t) ( vt dump(vt stream = fileopen (f,"wb"), t ), \  17
fclose (vt stream) )  18
void vt dump ( FILE *stream, t vt *vt ) ;  19
/* Store the valueassignments in binary format. */  20

21

void vt printbyclass ( char *FileName, t vt *vt ) ;  22
/* Print the valueassignments in ascii format sorted by class. */  23

24

t vt *vt readbackup ( const char *FileName, const t pg *pg ) ;  25
t vt *vt load ( FILE *stream, t vt *vt, t pg *pg ) ;  26
/* Load a tree of value assignmnents from the given file. */  27

28

void vt del ( t vt *vt ) ;  29
/* Elliminate the tree. */  30

31

t vt *vt init ( t val *val ) ;  32
/* Create a new and empty tree for value assignments. */  33

34

/* End of vtree.h */  35

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: vtree.c,v 5.0 1998/12/20 00:26:31 georg Exp $ */  2

3

/* Object file for storing different value assignments up to equivalence **  4
** in a binary search tree.  */  5

6

#include "common.h"  7

8

#include <search.h>  9

10

#include "pg.h"  11
#include "val.h"  12

#include "vtree.h"  13

#include "aux.h"  14

15

/* Global variables */  16
FILE *vt stream;  17
static char *vt file;  18
static t class cc;  19

20

/* Static function declarations */  21
static void vt walkbackup ( const void *val, VISIT v, int n ) ; 22
/* Make an binary dump of the node, used by vt dump(). */  23
static void vt walkprintbyclass ( const void *val, VISIT v, int n ) ;  24
/* Make an ASCII print of the node, used by vt printbyclass(). */  25

26

/* Functions */  27
void vt insert ( t val *val, t vt *vt ) {  28
if ( ( NULL != vt−>root ) &&  29
( NULL != tfind ( val−>v, &(vt−>root), &v compare ) ) ) return ;  30
tsearch ( val−>v, &(vt−>root), &v compare );  31
Invariant ( v ok ( val−>v ) );  32
val freev ( val );  33
return ;  34
}  35

36

t vt *vt init ( t val *val ) {  37
t vt *vt;  38
vt = getmem ( sizeof (t vt) );  39

vt−>root = NULL;  40
vt−>val = val;  41
return ( vt );  42
}  43

44

void vt printbyclass ( char *FileName, t vt *vt ) {  45
extern FILE *vt stream;  46
extern char *vt file;  47
vt file = FileName;  48
twalk ( vt−>root, &vt walkprintbyclass );  49
fclose ( vt stream );  50
return ;  51
}  52

53

void vt walkprintbyclass ( const void *val, VISIT v, int n ) {  54
/* Auxiliary function for vt printbyclass(). */  55
extern FILE *vt stream;  56
extern char *vt file;  57
extern t class cc;  58
static char FileName[FILE NAME L];  59
t v *vv;  60

61

vv = *(t v**) val;  62
Invariant ( v ok ( vv ) ) ;  63

64

if ( ( v == preorder ) | | ( v == endorder ) ) return ;  65
if ( ( vv−>class > cc ) | | ( vt stream == NULL ) ) {  66
cc = vv−>class;  67
fclose ( vt stream );  68
sprintf ( FileName, "%s:%i", vt file, cc );  69
vt stream = fileopen ( FileName, "w" );  70

  fprintf ( vt stream, "PG(%i,%i): d = %i, class %i:\n",  71

vv−>pg−>k, vv−>pg−>q, vv−>ds.delta[0], cc );  72
};  73
v print ( vt stream, vv );  74
return ;  75
}  76

77

t vt *vt finfo ( FILE *stream ) {  78
int i = 0;  79
t pdim k, q;  80
while ( 0 != VT FILEID[i] ) {  81
if ( VT FILEID[i++] != getc ( stream ) ) ErrEx ( ERR FFORMAT );  82
};  83
k = getc ( stream ); q = getc ( stream );  84
printf ( "k = %i, q = %i\n", k, q );  85
}  86

87

t vt *vt load ( FILE *stream, t vt *vt, t pg *pg ) {  88
t v *v;  89
int i = 0;  90
char fver = 2, c;  91
if ( vt == NULL ) vt = vt init ( NULL );  92
while ( 0 != VT FILEID[i] ) {  93
if ( VT FILEID[i++] != ( c = getc ( stream ) ) )  94
if ( isdigit ( c ) ) fver = c − '0';  95
else ErrEx ( ERR FFORMAT );  96
};  97
if ( ( fver < 1 ) | | ( fver > 2 ) ) ErrEx ( ERR FFORMAT );  98
vt−>val = val load ( stream, pg );  99
if ( 2 == fver ) val fixload ( stream, vt−>val );  100
while ( 0 == feof ( stream ) &&  101

NULL != ( v = v load ( stream, vt−>val−>pg ) ) ) {  102
tsearch ( v, &(vt−>root), &v compare );  103
};  104
return ( vt );  105
}  106

107

void vt dump ( FILE *stream, t vt *vt ) {  108
extern FILE *vt stream;  109
vt stream = stream;  110
fprintf ( vt stream, VT FILEID );  111
val dump ( stream, vt−>val );  112
val fixdump ( stream, vt−>val );  113
twalk ( vt−>root, &vt walkbackup );  114
return ;  115
}  116

117

t vt *vt readbackup ( const char *FileName, const t pg *pg ) {  118
extern FILE *vt stream;  119
t vt *vt;  120
vt stream = fileopen ( FileName, "w" );  121
ErrEx ( ERR IMP );  122
fclose ( vt stream );  123
return ( vt );  124
}  125

126

void vt walkbackup ( const void *val, VISIT v, int n ) {  127
/* Auxiliary function for vt backup. */  128
extern char *vt file;  129
v dump ( vt stream, *(t v**) val );  130
return ;  131
}  132

133

void vt del ( t vt *vt ) {  134
/* Only one tree is allocated, so we don’t bother to deallocate it. */  135
return ;  136
}  137

138

/* End: vtree.c */  139

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: stack.h,v 5.0 1998/12/20 00:25:48 georg Exp $ */  2

3

/* This defines a quasi-stack to store a set of points. */  4
/* In addition to ordinary stack operations, one can travers the **  5
** stack from top to bottom, without popping elements. */ 6
/* One can also discard all elements and insert a single new one. */  7

8

typedef struct s stack {  9
unsigned char size, /* Current size */  10
msize, /* Maximum size */  11
current; /* Current element with respect to traversing */  12
t ps *ps; /* Array for the elements */ 13
} t stack;  14

15

/* Allocation and deallocation. */  16
t stack *stk init ( unsigned char size );  17
/* Constructor: allocate memory, for a stack of maximum size size. */  18
void stk del ( t stack *stack ); 19
/* Destructor: deallocate memory */  20
#define stk alloc(s) stk init(s)  21
/* allocate memory */  22

#define stk reinit(s) ( s−>size = 0 )  23
/* empty the stacke */  24

25

/* Basic stack operations: pop and push. */  26
#define stk pop(stk) ( stk empty(stk) ? pg noel : stk−>ps[−−(stk−>size)] )  27
#define stk push(stk,c) ( stk full(stk)? 0: ( stk−>ps[(stk−>size)++] = c, 1 ) )  28

29

/* Observators */  30
#define stk empty(stk) ( 0 == stk−>size )  31
/* True if the stack is empty. */  32
#define stk full(stk) ( stk−>size >= stk−>msize )  33
/* True if the stack is full. */  34
#define stk more(stk) ( 0 != stk−>current )  35
/* True if stk next can return an element. */  36

37

/* Traversing */  38
#define stk reset(s) ( s−>current = s−>size )  39
/* Reset the stack. Next time we inspect an element, we get the top-most. */  40
#define stk next(stk) ( stk more(stk) ? stk−>ps[−−(stk−>current)] : pg noel )  41
/* Return the next element, without changing the stack. */  42

43

/**/  44
#define stk replace(stk,c) ( stk−>size = 1, stk−>ps[0] = c, 1 )  45
/* Replace all elements by a single new element. */  46

47

/* end of stack.h */  48

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: stack.c,v 5.0 1998/12/20 00:25:43 georg Exp $ */  2

3

#include "common.h"  4

#include "pg.h"  5

#include "stack.h"  6
#include "aux.h"  7

8

t stack *stk init ( unsigned char size ) {  9
t stack *stk;  10
stk = getmem ( sizeof (t stack) );  11
stk−>size = 0;  12
stk−>msize = size;  13
stk−>ps = getmem ( size*sizeof (t ps) );  14
return ( stk );  15
}  16

17

void  stk del  ( t stack  *stack ) {  18
free ( stack−>ps );  19
free ( stack );  20
}  21

22

/* End of stack.c */  23

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: valex.l,v 5.0 1998/12/20 00:26:13 georg Exp $ */  2

3

/* Parser for value assignments */  4

5

%option prefix="yyval_"  6
%option noyywrap  7
%option stack  8
%option 7bit  9

3.1. THE BASIC MODULES

10

%{  11

12

/* Include */  13

#include "common.h"  14

#include "pg.h"  15
#include "val.h"  16

17

/* Internal variables */  18
static t val *val;  19

20

%}  21

22

/* Character classes */  23

24

COMMENT #  25
HEAD ;  26

CHAR [a-zA-Z0-9_]  27
NAME [a-zA-Z]  28
LETTER [a-zA-Z_]  29

WORD {LETTER}{CHAR}*  30
DIGIT [0-9]  31
NUMBER [0-9]+  32
WHITE [ \t\n]  33
FIX  "*"  34

35

/* Keywords */  36

37

C FIX  @fix  38
C VERBOSE @verbose  39
C END @end 40
C ENDFILE @endfile  41

42

%x assign  43
%s ex val  44

45

%%  46

47

%{  48
static t ps pt;  49
static char verbose = TRUE, fixall, *asp;  50
%}  51

52

{COMMENT}.*\n  { /* Ignore comments */ }  53
{WHITE}+  { /* Ignore whitespace */ }  54

55

/* The header marks the start of the assignment. */  56
<INITIAL>{HEAD}.*\n {  57
if ( verbose ) printf ( "New value assignment:\n%s", yytext );  58
BEGIN ( ex val ) ;  59
fixall = FALSE; pt = 0; }  60

61

{C VERBOSE}=  { asp = &verbose; yy push state ( assign ); }  62
<ex val>{C FIX}= { asp = &fixall; yy push state ( assign ); }  63
<assign>{NUMBER} { *asp = atoi ( yytext ); yy pop state (); }  64

65

/* Setting the point number for the next assignment */  66
<ex val>{NUMBER}/: { pt = atoi ( yytext ); input (); }  67

68

/* Assigning value */  69
<ex val>{NUMBER}/({WHITE}|{FIX}) {  70
if ( fixall ) { val set ( val, pt, atoi ( yytext ) ); ++pt; }  71

else val setval ( val, pt++, atoi ( yytext ) ); }  72

73

/* Assigning no value */  74
<ex val>−/({WHITE}|{FIX}) { val setval ( val, pt++, val novalue ); }  75

76

/* Fix value */  77
<ex val>{FIX}  { val fixit ( val, pt − 1 ); }  78

79

/* A new head indicates the end of the current set of assignments. */  80
<ex val>{HEAD} { 81
if ( verbose ) printf ( "End of assignment.\n" );  82
unput ( ’;’ ); BEGIN ( INITIAL ); return ( 0 ); }  83
/* Explicit end of current value assignment. */  84
<ex val>{C END} { 85
if ( verbose ) printf ( "End of assignment.\n" );  86
BEGIN ( INITIAL ); return ( 0 ); }  87

88

/* End of input */  89
<ex val><<EOF>>  { BEGIN ( INITIAL ); return ( 0 ); }  90
{C ENDFILE}  { BEGIN ( INITIAL ); return ( 0 ); }  91
<INITIAL><<EOF>>  { return ( EOF ); }  92
<INITIAL>{C ENDFILE} { return ( EOF ); }  93

94

/* Don’t accept garble within value assignments. */  95
<ex val>.  { fprintf ( stderr,  96

                  "Syntax error reading value assignments:\n%s\n",  97

yytext ); }  98

99

<INITIAL>.  { /* Do ignore garble outside value assignments. */ }  100

101

%%  102

103

/* val assign() takes parameters to initialize global variables before **  104
** running yy lex(). */ 105
char val assign ( t val *v, FILE *fs ) {  106
yyin = fs;  107
val = v;  108
return ( yylex () );  109
}  110

111

/* End of lex.l */  112

3.2 Complex modules

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pgval.h,v 5.0 1998/12/20 00:25:13 georg Exp $ */  2

3

#include "pginit.h"  4

5

#define FIX NOTE  " *"  6

#define DIGIT  "0123456789-"  7

#define pv pprint(fs,p) fprintf ( fs, "%4d:%c%c", p, \  8
DIGIT[val novalue == val−>v−>val[p] ? 10 : val−>v−>val[p]], \  9
FIX NOTE[val−>fix[p]] )  10
/* Print a string representing a point and its value. */  11

12

void pv init ( t pdim k, t pdim q ) ;  13
/* Reinitilise global variables. */  14

15

void pv sprint ( FILE *stream, t pdim dim, t ps ps ) ;  16

3.2. COMPLEX MODULES

/* Print a subspace and the values for each point */  17
void pv printall ( FILE *s, t pdim d ) ;  18
/* Print all d-spaces and the values for each point */  19
void pv print ( FILE *stream ) ;  20
/* Print values for each point (valex format). */  21
int pv fixcount ( ) ;  22
/* Count fixed values. */  23
char pv ssprint ( FILE *stream, t pdim dim1, t pdim dim2, t ps ps ) ;  24
/* Print all dim1-spaces being sub- or superset of dim2-space ps,  25
** with values.  */  26

27

/* end of pgval.h */  28

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pgval.c,v 5.0 1998/12/20 00:25:11 georg Exp $ */  2

3

#include "common.h"  4
#include "pgval.h"  5
#include "val.h"  6

7

static char pv supprint ( FILE *stream, t pdim dim, t pdim subdim, t ps ps ) ;  8
static char pv subprint ( FILE *stream, t pdim dim, t pdim subdim, t ps ps ) ;  9

10

t val *val = NULL;  11
t pg *pg = NULL;  12
t pdim pg dim=4, pg order=2; /* PG parameters */  13

14

void pv printall ( FILE *s, t pdim d ) {  15
int elno, i;  16
extern t pg *pg;  17
elno = pg eln ( pg, d );  18
for ( i = 0; i < elno; ++i ) pv sprint ( s, d, i );  19
}  20

21

void pv sprint ( FILE *stream, t pdim dim, t ps ps ) {  22
int elno, i, tab;  23
extern t val *val;  24
extern t pg *pg;  25
extern t s *sp;  26
extern t pdim pg dim;  27
char *msp;  28

29

if ( dim >= pg dim ) { return; }; /* Sanity check */  30

31

/* Print a header with number and value for the space. */  32
fprintf ( stream, "%i-space[%4i] (%i):", dim, ps, val−>val[dim][ps] );  33
tab = 2; /* This is the current tab position. */  34

35

/* The boolean array indicating the points in the subspace */  36
msp = sp−>s[dim][ps]−>pt;  37
/* The number of points in the subspace. */  38
elno = pg qpow ( pg, pg−>k );  39
/* For each point */  40
for ( i = 0; i < elno; ++i ) {  41
/* If it is in the subspace */  42
if ( msp[i] == TRUE ) {  43
putc ( '\t', stream );  44
/* Print its number and value */  45
pv pprint ( stream, i );  46
/* On the last tab position, put a line feed. */  47
if ( 0 == ( ++tab % 9 ) ) putc ( '\n', stream );  48

}  49
};  50
/* If we’re in the midle of a line, put a line feed. */  51
if ( ( tab % 9 ) != 0 ) putc ( '\n', stream );  52
return ;  53
}  54

55

void pv print ( FILE *stream ) {  56
extern t pg *pg;  57
extern t val *val;  58
t ps i=0, elno;  59

60

fprintf ( stream, ";\n" ); /* Print header */  61
elno = pg qpow ( pg, pg−>k );  62
while ( i < elno ) {  63
pv pprint ( stream, i ); ++i;  64
putc ( ( ( 0 == ( i % 10 ) ) ? '\n' : '\t' ), stream );  65
};  66
if ( 0 != ( i % 10 ) ) putc ( '\n', stream );  67
return ;  68
}  69

70

void pv init ( t pdim k, t pdim q ) {  71
extern t val *val;  72
extern t pg *pg;  73
extern t s *sp;  74
extern t pdim pg dim, pg order;  75
if ( NULL != sp ) s del ( sp, pg dim, pg order ) ;  76
if ( NULL != pg ) pg del ( pg ) ;  77
if ( NULL != val ) val del ( val ) ;  78
v alloc ( NULL, 0 ); /* Reinitalize for a new geometry. */  79
pg dim = k;  80
pg order = q;  81
sp = s init ( pg dim, pg order );  82
pg = pg create ( pg dim, pg order, sp );  83
val = val init ( pg );  84
}  85

86

int pv fixcount ( ) {  87
extern t val *val;  88
extern t pg *pg;  89
int elno, i = 0, r = 0;  90
elno = pg qpow ( pg, pg−>k );  91
while ( i < elno ) {  92
if ( val−>fix[i++] ) ++r;  93
};  94
return ( r );  95
}  96

97

char pv ssprint ( FILE *stream, t pdim dim1, t pdim dim2, t ps ps ) {  98
return (  99
( dim1 < dim2 ? pv subprint : pv supprint )( stream, dim2, dim1, ps )  100
);  101
}  102

103

char pv supprint ( FILE *stream, t pdim dim, t pdim subdim, t ps ps ) {  104
return ( ENO IMP ) ;  105
}  106

107

char pv subprint ( FILE *stream, t pdim dim, t pdim subdim, t ps ps ) {  108
int h, hm, j, jm, c;  109
jm = pg elno ( pg−>q, pg−>k, dim );  110

hm = pg theta ( subdim, dim, pg−>k, pg−>q );  111
fprintf ( stream, "%i-spaces in %i-space #%i:\n", subdim, dim, ps );  112
for ( c = j = 0; j < jm; ++j ) {  113
for ( h = 0; h < hm; ++h ) {  114
if ( pg−>ps[subdim][dim−subdim−1][j][h] == ps ) {  115
pv sprint ( stream, subdim, j );  116
};  117
};  118
};  119
putc ( '\n', stream );  120
}  121

122

/* end of pgval.c */  123

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: valmsp.h,v 5.0 1998/12/20 00:26:18 georg Exp $ */  2

3

#include "val.h"  4

5

#define NO FIXCHANGE −1  6
#define NO CHANGE  0  7
#define IGN FIX  1  8
#define IGN VAL  2  9
#define DO CHANGE  (IGN FIX|IGN VAL)  10

11

char val spaceval ( t pdim dim, t ps ps, signed short v,  12
char change, char fix ) ;  13
/* Assign the same value to all points in a dim-space. If change is */  14
/* NO CHANGE only points with current value val novalue is changed. */  15
/* If v is negative, the value isn’t changed, but values may still be */  16
/* fixed. */ 17
#define val spacefix(d,p) val spaceval ( d, p, −1, DO CHANGE, TRUE );  18
#define val spaceunfix(d,p) val spaceval ( d, p, −1, DO CHANGE, FALSE );  19

20

t ps val incprobe ( FILE *fs, char inc ) ;  21
/* Try and increase the value of all non-fixed points, without **  22
** changing the class.  */  23

24

/* End of valmsp.h */  25

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: valmsp.c,v 5.0 1998/12/20 00:26:15 georg Exp $ */  2

3

#include "common.h"  4
#include "pginit.h"  5
#include "valmsp.h"  6

7

char val spaceval ( t pdim dim, t ps ps, signed short v,  8
char change, char fix ) {  9
int elno, i;  10
extern t val *val;  11
extern t pg *pg;  12
extern t s *sp;  13
extern t pdim pg dim;  14
char *msp;  15

16

if ( pg dim != dim ) msp = sp−>s[dim][ps]−>pt;  17
elno = pg qpow ( pg, pg dim );  18
/* We loop to check all possible points. */  19
for ( i = 0; i < elno; ++i ) {  20

if ( ( ( pg dim == dim ) | | ( msp[i] == TRUE ) ) &&  21
( ( val−>v−>val[i] == val novalue ) | | (change&IGN VAL) ) &&  22
( ( val−>fix[i] == FALSE ) | | (change&IGN FIX) ) ) {  23
/* If expression:  24
** line 1) if the point is in the given space  25
** line 2) if it has a value, or we may change an existing values  26
** line 3) if the value isn’t fixed or we are allowed to ignore it */  27
if ( v >= 0 ) val−>v−>val[i] = v;  28
if ( NO FIXCHANGE != fix ) val−>fix[i] = fix;  29
}  30
}  31
}  32

33

/* Try to increase values without changing class */  34
t ps val incprobe ( FILE *fs, char inc ) {  35
int class, fixit = 0;  36
t ps ptno, i, r = 0;  37
extern t val *val;  38
extern t pg *pg;  39
extern t pdim pg dim;  40

41

/* If inc is 0, we use an increment of 1, and fix values we cannot  42
** increase. */  43
if ( 0 == inc ) { ++fixit; ++inc; };  44

45

/* Classify the assignment. */  46
val sumval ( val );  47
v reinit ( val−>v );  48
class = val class ( val );  49

50

ptno = pg qpow ( pg, pg dim );  51
/* For each point */  52
for ( i = 0; i < ptno; ++i ) {  53
/* If the value isn’t fixed */  54
if ( val−>fix[i] == FALSE ) {  55
val−>v−>val[i] += inc; /* Try an increament */  56
val sumval ( val );  57
if ( class != val class ( val ) ) {  58
/* If the class has changed, undo the change in the value */  59
val−>v−>val[i] −= inc;  60
if ( fixit ) val−>fix[i] = TRUE;  61
} else {  62
++r;  63
if ( NULL != fs )  64

      fprintf ( fs, "Increasing value of point #%i.\n", i );  65

};  66
};  67
};  68
return ( r ); /* Return the number of increased values. */  69
}  70

71 72

/* End of valmsp.c */  73

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: nametab.h,v 5.0 1998/12/20 00:24:33 georg Exp $ */  2

3

#include "common.h"  4
#include "pginit.h"  5

6

#define POINT NO 26  7

#define SPACE NO 26  8

9

typedef struct s ntab {  10
t ps point[POINT NO];  11
t pdim sdim[SPACE NO];  12
t ps space[SPACE NO];  13
} t ntab;  14

15

void nt init () ;  16
/* Initialise name tables. */  17
int nt lookup ( char name, int out[ ] ) ;  18
/* Resolve the symbolic name, and insert the result in out. **  19
** Return the number of integers inserted.  **  20
** out[ ] is usually a argument vector in the lex module  */  21
char nt sdef ( char name, t pdim m, t ps p ) ;  22
/* Define a symbolic name for a subspace. */  23
char nt pdef ( char name, t ps p ) ;  24
/* Define a symbolic name for a point. */  25
char nt line ( char name, t ps a, t ps b ) ;  26
/* Define a symbolic names for a points on a line. */  27

28

/* End of nametab.h */  29

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: nametab.c,v 5.0 1998/12/20 00:24:32 georg Exp $ */  2

3

#include "nametab.h"  4

5

static t ntab ntab;  6

7

void nt init () {  8
int i;  9
extern t pg *pg;  10
extern t pdim pg dim;  11
for ( i = 0; i < POINT NO; ) ntab.point[i++] = pg noel;  12
for ( i = 0; i < SPACE NO; ) ntab.space[i++] = pg noel;  13
nt pdef ( 'A', 0 );  14
for ( i = 0; i < pg dim; ++i ) nt pdef ( 'B' + i, pg qpow ( pg, i ) );  15
}  16

17

char nt line ( char name, t ps a, t ps b ) {  18
t ps s;  19
char *msp;  20
int i, imax, arg[2];  21
extern t s *sp;  22
extern t pg *pg;  23
extern t pdim pg dim;  24

25

arg[0] = a;  26
arg[1] = b;  27
s = pg get ( pg, arg, 2 );  28
msp = sp−>s[1][s]−>pt;  29

30

if ( pg noel == s ) {  31

  fprintf ( stderr, "Error: no such subspace.\n" );  32

return ( FALSE );  33
};  34

35

imax = pg qpow ( pg, pg dim );  36
for ( i = 0; i < imax; ++i ) {  37
if ( ( a != i ) && ( b != i ) && ( msp[i] == TRUE ) ) {  38

if ( ! nt pdef ( name++, i ) ) return ( FALSE );  39
}  40
}  41
return ( TRUE );  42
}  43

44

int nt lookup ( char name, int out[ ] ) {  45
if ( isupper ( name ) ) {  46
name −= 'A' − 1;  47
if ( pg noel == ntab.point[name] ) return ( 0 );  48
out[0] = ntab.point[name];  49
return ( 1 );  50
} else if ( islower ( name ) ) {  51
name −= 'a' − 1;  52
if ( pg noel == ntab.space[name] ) return ( 0 );  53
out[0] = ntab.sdim[name];  54
out[1] = ntab.space[name];  55
return ( 2 );  56
};  57
return ( 0 );  58
}  59

60

char nt pdef ( char name, t ps p ) {  61
if ( isupper ( name ) ) {  62
name −= 'A' − 1;  63
ntab.point[name] = p;  64
return ( 1 );  65
};  66
return ( 0 );  67
}  68

69

char nt sdef ( char name, t pdim m, t ps p ) {  70
if ( islower ( name ) ) {  71
name −= 'a' − 1;  72
ntab.sdim[name] = m;  73
ntab.space[name] = p;  74
return ( 1 );  75
};  76
return ( 0 );  77
}  78

79

/* End of nametab.c */  80

Chapter 4

Other common modules

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: aux.h,v 5.0 1998/12/20 00:23:52 georg Exp $ */  2

3

/* Auxilliary file functions */  4
char freadline ( FILE *stream, char *b ) ;  5
/* Read a line of characters from stream into b. */  6
short getshort ( FILE *stream ) ;  7
/* Read a short variable from stream */  8
#define putshort(s,n) ( putc ( (n)%256, s ), putc ( (n) >> 8, s ), 0 )  9
/* Write a short variable to stream */  10

11

void PrintHelp ();  12
/* Print a help message. (Not very useful implementation.) */  13
void PrintVersion ();  14
/* Print version and compile information. */  15
void ErrorUsage ();  16
/* Print an error message and make a clean exit. */  17

18

char fid verify ( FILE *stream, const char *id ) ;  19
/* Read the file ID from stream and check that it matches id. **  20
** Exit on failure.  */  21

22

int MailNote ( char *msg ) ;  23
/* Mail diagnostics to the operating user. */  24

25

extern void *aux p; /* Aux. variable for macros. */  26
extern FILE *aux s; /* Aux. variable for macros. */  27

28

#define getmem(s) ( ( ( aux p = malloc ( s ) ) == NULL ) ? \  29
(void *) ErrEx ( ERR MEM ) : aux p )  30
/* Allocate memory, exit on failure */  31
#define fileopen(f,m) ( ( aux s = fopen (f,m) ) == NULL ? \  32
(FILE*) ErrExDbl (ERR FOPEN,f) : aux s )  33
/* Open file, exit on failure */  34

35

#define CMD TEE "/usr/bin/tee"  36

/* Name of the tee programme */  37
void tee func ( const char *teeFile, char *opt ) ;  38
/* Fork out a tee process. teeFile is the name of the file given **  39
** to tee(1), and opt are options passed to tee.  */  40
#define tee(a)  tee func ( a, NULL )  41
/* Use tee to write stdout to file a, in adition to the existing stdout. */  42
#define tee append(a) tee func ( a, "-a" )  43
/* Use tee to append stdout to file a, in adition to the existing stdout. */  44

CHAPTER 4. OTHER COMMON MODULES

45

/* End of aux.h */  46
/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: aux.c,v 5.0 1998/12/20 00:23:51 georg Exp $ */  2

3

#include "common.h"  4
#include "aux.h"  5

6

void *aux p;  7
FILE *aux s;  8

9

/* Auxilliary file functions */  10
short getshort ( FILE *stream ) {  11
register short c;  12
c = getc ( stream );  13
c += getc ( stream ) << 8;  14
if ( feof ( stream ) ) c = EOF;  15
return ( c );  16
}  17

18

char freadline ( FILE *stream, char *b ) {  19
char c;  20
while ( ( EOF != ( c = getc ( stream ) ) ) ) {  21
if ( '\n' == c ) { *b = 0; return ( c ); };  22
*(b++) = c;  23
};  24
return ( *b = EOF );  25
}  26

27

void PrintHelp () {  28
printf ( "RTFM\n" );  29
}  30

31

void PrintVersion () {  32
extern char *RealName, *MyVersion, *CompileDate, *MyPathName;  33
printf ( "%s %s\n", RealName, MyVersion );  34
printf ( "Compiled %s.\n", CompileDate );  35
printf ( "Running from %s.\n", MyPathName );  36

printf ( "Compile options: %s.\n", CC DEFINES );  37

}  38

39

int MailNote ( char *msg ) {  40
char mtext[2048], timeString[TIME STRING L], timeUsed[16];  41
extern char *MyName, *UserName, *HostName,  42
*MyVersion, *CompileDate,  43
*MailTo, CallString[ ], timeStart[ ];  44
time t theTime;  45
unsigned long hour, min, sec;  46
int mta in[2], mta out[2], i;  47

48

/* Calculate time in hours, minutes and seconds. */  49
sec = (unsigned long)(clock()/CLOCKS PER SEC);  50
min = (unsigned long)(sec/60);  51
sec = sec % 60;  52
hour = (unsigned long)(min/60);  53
min = min % 60;  54

55

/* Make a string showing the time used. */  56
sprintf ( timeUsed, "%i:%2i:%2i", hour, min, sec );  57
for ( i = 0; timeUsed[++i] != 0; ) {  58

if ( timeUsed[i] == ' ' ) timeUsed[i] = '0';  59
};  60

61

/* Fork and call sendmail */  62
pipe ( mta in );  63
if ( 0 == fork () ) {  64
close ( 0 );  65
dup ( mta in[0] );  66
close ( mta in[0] );  67
close ( mta in[1] );  68
execlp ( mta, mta, MailTo, NULL );  69
} else {  70
close ( mta in[0] );  71
time ( &theTime );  72
cftime ( timeString, NULL, &theTime );  73
sprintf ( mtext,  74

  "From: %s (%s@%s)\nTo: %s\nDate: %sSubject: Output from %s@%s\n\n"  75
  "The following command has just finished on %s.\n%s\n\n%s\n\n"  76
  "Start: %sEnd: %s\nThe CPU time used is: %s\n\n"  77
  "The executable was version %s, compiled %s.\n",  78

UserName, MyName, HostName, UserName, timeString, MyName,  79
HostName, HostName, CallString, msg, timeStart, timeString, timeUsed,  80
MyVersion, CompileDate  81
);  82
write ( mta in[1], mtext, strlen ( mtext ) );  83
close ( mta in[1] );  84
};  85
}  86

87

char fid verify ( FILE *stream, const char *id ) {  88
int i = 0;  89
while ( 0 != id[i] ) {  90
if ( id[i++] != getc ( stream ) ) return ( FALSE );  91
}  92
return ( TRUE );  93
}  94

95

void tee func ( const char *teeFile, char *opt ) {  96
int mta in[2];  97
pipe ( mta in );  98
if ( 0 == fork () ) {  99
close ( 0 );  100
dup ( mta in[0] );  101
close ( mta in[0] );  102
close ( mta in[1] );  103
if ( NULL == teeFile ) {  104
execlp ( CMD TEE, CMD TEE, NULL );  105
} else if ( NULL == opt ) {  106
execlp ( CMD TEE, CMD TEE, teeFile, NULL );  107
} else {  108
execlp ( CMD TEE, CMD TEE, opt, teeFile, NULL );  109
}  110
} else {  111
close ( 1 );  112
dup ( mta in[1] );  113
close ( mta in[0] );  114
close ( mta in[1] );  115
};  116
}  117

118

void ErrorUsage () {  119
extern char *MyPathName;  120

CHAPTER 4. OTHER COMMON MODULES

fprintf ( stderr, "%s -h for help.\n", MyPathName );  121
exit ( 2 );  122
}  123

124

/* End of aux.c */  125

Chapter 5

gen

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: gen.c,v 5.0 1998/12/20 00:24:03 georg Exp $ */  2

3

/* main function for gen(1)  **  4
** gen creates and classifies value assigments  **  5
** defining error correcting codes.  */  6

7

#include "common.h"  8

9

#include <signal.h>  10

11

#include "aux.h"  12
#include "pg.h"  13
#include "val.h"  14

#include "vtree.h"  15
#include "signal.h"  16

17

#define ARGS  "a:B:b:c:d:efhk:m:n:O:p:q:sS:tT:vw:x"  18

19

/* Global Variables */  20
char *MyName, *MyPathName,  /* The programme name from argument no. 0 */ 21
*UserName, *HostName,  /* Environment. */  22
*RealName = GEN NAME,  /* The real name of the programme */  23
CallString[CALL STRING L], /* The entire command call with arguments */  24
*MyVersion = GEN VERSION, /* Programme version number. */  25
*CompileDate = GEN COMPILE, /* Date of compilation. */  26
*MailTo, *StatusFile = VAL STATUSFILE,  27
*SignalBackUpFile = DEF SIGBFILE,  28
timeStart[TIME STRING L];  29
t pdim pg dim=4, pg order=2; /* PG parameters */  30
t vt *vt = NULL;  31
pid t child, pid;  32
t val *val = NULL;  33
t pg *pg = NULL;  34

35

int main ( int argc, char *argv[ ] ) {  36

37

/* External variable declarations. */  38
extern t pdim pg dim, pg order;  /* PG parameters */  39
extern char *optarg;  /* for getopt(3) */  40
extern int optind, opterr, optopt;  /* for getopt(3) */  41
extern t vt *vt;  /* Data structure */  42
extern t val *val;  /* Data structure */  43

CHAPTER 5. GEN

extern t pg *pg;  /* Data structure */  44

45

/* Internal variable declarations. */  46
#ifdef ALLOW FIX  47
char mode f = FALSE;  48
#endif  49
char f, n = DEF NICE, w = DEF CNICE, /* Option flag */  50
mode e = TRUE, mode x = TRUE, mode s = FALSE,  51
moreval = RET VAL;  52
t value d=2;  /* \delta 0 */  53
t class c=val noclass;  /* Class number */  54
int i;  /* Index counter */  55
unsigned long bc = 0, b = DEF BCINT, /* Backup control. */  56
a = DEF ALARM; /* Alarm */ 57
char *OutFile = GEN OUTFILE, *InFile = NULL, FileName[FILE NAME L],  58
*TreeFile = NULL, *InitFile = NULL,  59
*BOutFile = GEN BOUTFILE, *BackUpFile = NULL,  60
CBackUpFile[FILE NAME L], BBackUpFile[FILE NAME L], *cpt;  61
char rflags[24] = { 0 };  62
FILE *InStream, *actfile;  63
time t theTime;  64

65

/* General signal handling */  66
signal ( SIGCHLD, SIG IGN ); /* Do not create zombie children. */  67
signal ( SIGHUP, SIG IGN ); /* Ignore Hangup */  68

69

/* Clock initialization. */  70
clock ();  71
time ( &theTime );  72
cftime ( timeStart, NULL, &theTime );  73

74

/* Parsing argument 0. */  75
MyPathName = *argv;  76
MyName = basename ( MyPathName );  77

78

/* Environment parsing. */  79
MailTo = UserName = getenv ( "USER" );  80
HostName = getenv ( "HOST" );  81
pid = getpid ();  82

83

/* Option parsing. */  84
while ( −1 != ( f = getopt( argc, argv, ARGS ) ) )  85
switch (f) {  86
case 'a': a = atoi(optarg); break;  87
case 'b': b = atoi(optarg); break;  88
case 'c': c = atoi(optarg);  89
strcat ( rflags, "-c " );  90
strcat ( rflags, optarg );  91
strcat ( rflags, " " );  92
break;  93
case 'd': d = atoi(optarg); break;  94
case 'e': mode e = FALSE;  95
strcat ( rflags, "-e " );  96
break;  97
case 'k': pg dim = atoi(optarg); break;  98
case 'm': MailTo = optarg; break;  99
case 'n': n = atoi(optarg); break;  100
#ifdef ALLOW FIX  101
case 'f': mode f = TRUE; break;  102
#endif  103
case 'p': InFile = optarg; break;  104
case 'q': pg order = atoi(optarg); break;  105

case 'w': w = atoi(optarg); break;  106
case 'x': mode x = FALSE; break;  107
case 's': mode s = TRUE; break;  108
case 'S': mode s = TRUE; StatusFile = optarg; break;  109
case 'T': TreeFile = optarg; break;  110
case 'B': BackUpFile = optarg; break;  111
case 'O': BOutFile = optarg; break;  112
case 't': break;  113
case 'h': PrintHelp(); exit (1); break;  114
case 'v': PrintVersion(); exit (1); break;  115
default: ErrorUsage(); exit (1);  116
} /* switch */  117

118

/* Nice and signals */  119
nice ( n );  120
alarm ( 60*a );  121
SignalHandling ();  122

123

/* Complete the argument parsing. */  124
if ( ( ! mode f ) && ( optind != argc ) ) ErrorUsage();  125
if ( b < MIN BCINT ) ErrEx ( ERR BCINT ); /* Sanity check. */  126
cpt = CallString;  127
for ( i=0; i < argc; ++i ) {  128
sprintf ( cpt, "%s ", argv[i] );  129
cpt += 1 + strlen ( argv[i] );  130
};  131

132

GetData ( TreeFile, InFile );  133

134

/* Create backup files and file names. */  135
if ( BackUpFile == NULL ) {  136
sprintf ( CBackUpFile, "%s%s", OutFile, DEF BCEXT );  137
BackUpFile = CBackUpFile;  138
};  139
sprintf ( BBackUpFile, "%s%s", BackUpFile, DEF BCBCEXT );  140
unlink ( BBackUpFile ); /* Remove secondary backupfile. */  141
/* creat ( BackUpFile, 0600 ); */  142

143

/* Create act file in current directory. */  144
actfile = fileopen ( GEN ACTFILE, "w" );  145
strcat ( rflags, "-T" );  146
fprintf ( actfile, "GEN_HOST=%s\n", HostName );  147
fprintf ( actfile, "GEN_USER=%s\n", UserName );  148
fprintf ( actfile, "GEN_PID=%i\n", pid );  149
fprintf ( actfile, "GEN_CMD=%s\n", CallString );  150
fprintf ( actfile, "GEN_GEN=%s\n", MyPathName );  151
fprintf ( actfile, "GEN_FLAGS=%s\n", rflags );  152
fprintf ( actfile, "GEN_BC=%s\n", BackUpFile );  153
fclose ( actfile );  154

155

/* Generate the value assignments. */  156
if ( NULL == TreeFile ) val stepinit ( val, d );  157

158

if ( mode f ) {  159
/* Assign values given on the command line. */  160
while ( optind < argc ) {  161
char *p, *a;  162
a = p = argv[optind++];  163
while ( *(++a) != ':' ) {};  164
*(a++) = 0;  165
val set ( val, atoi (p), atoi (a) );  166
};  167

val sumval (val);  168
val classify (val);  169
};  170

171

if ( mode s ) StatusReport(val);  172

173

/* If we search only for a certain class, we step forward to an **  174
** assignment of the correct class. */ 175
if ( ( c != val noclass ) && ( c != val class ( val ) ) )  176
moreval = val stepclass (val,c);  177

178

/* The search loop. */  179
while ( NO MORE VAL != moreval ) {  180
/* Insert the value assignment in the tree. */  181
if ( mode e | | ( val class( val ) < val−>nclass ) ) vt insert( val, vt );  182

183

/* Make regular backups. */  184
if ( bc++ > b ) {  185
if ( ( 0 == link ( BackUpFile, BBackUpFile ) ) &&  186
/* Make secondary backup. */  187
( 0 == ( child = fork() ) ) ) { /* Fork to backup. */  188
DefaultSignals ();  189
nice ( w );  /* Renice child. */  190
unlink ( BackUpFile );  /* Create primary backup file. */  191
vt backup ( BackUpFile, vt );  /* Make backup. */  192
unlink ( BBackUpFile );  /* Remove secondary backup. */  193
if ( mode s ) StatusReport ( val ); /* Report the level of progress. */  194
exit ( 0 ); /* Exit backup child. */ 195
};  196
bc = 0;  197
}; /* if ( bc++ > b ) */  198
/* Step to the next value assignment */  199
moreval = ( val noclass == c ? val stepval (val) :  200
val stepclass (val,c) );  201
}; /* while */  202
vt backup ( BOutFile, vt );  /* binary output */  203

204

/* Notification by mail. */  205

if ( mode x ) MailNote ( "The programme exited normally.\n" );  206

207

/* Deallocate memory and exit */  208
vt del ( vt );  209
pg del ( pg );  210
val del ( val );  211
rename ( GEN ACTFILE, GEN PASFILE );  212
exit ( 0 );  213
}  214

215

/* end of gen.c */  216

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: prep.h,v 5.0 1998/12/20 00:25:31 georg Exp $ */  2

3

void GetData ( char *TreeFile, char *InFile ) ;  4
/* Allocate memory and load data from file */  5

6

/* End of prep.h */  7

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: prep.c,v 5.0 1998/12/20 00:25:27 georg Exp $ */  2

#include "common.h"  4

#include "pg.h"  5

#include "val.h"  6
#include "vtree.h"  7
#include "aux.h"  8
#include "prep.h"  9

10

void GetData ( char *TreeFile, char *InFile ) {  11
extern t pdim pg order, pg dim;  12
extern t val *val;  13
extern t pg *pg;  14
extern t vt *vt;  15
FILE *InStream;  16
if ( NULL == TreeFile ) {  17
/* Load the Geometry */  18
if ( NULL == InFile ) {  19
InFile = getmem ( PATH NAME L );  20
sprintf ( InFile, "%s/pg(%i,%i)", PG DIR, pg dim, pg order );  21
};  22
InStream = fileopen ( InFile, "rb" );  23
pg = pg load ( InStream );  24
fclose ( InStream );  25
/* Allocate memory */  26
val = val init ( pg );  27
vt = vt init ( val );  28
} else {  29
/* Load the Tree. */  30
InStream = fileopen ( TreeFile, "rb" );  31
vt = vt load ( InStream, NULL, pg );  32
fclose ( InStream );  33
val = vt−>val;  34
pg = val−>pg;  35
};  36

37

pg dim = pg−>k; pg order = pg−>q;  38
}  39

40

/* End of prep.h */  41

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: signal.h,v 5.0 1998/12/20 00:25:40 georg Exp $ */  2

3

void CleanExit ( int sig ) ;  4
/* Dump the data and exit cleanly (for SIGINT, SIGTERM, et c.). */  5
void CoreExit ( int sig ) ;  6
/* Dump the data and exit using abort(3) to create a core dump. **  7
** (for SIGBUS, SIGSEGV, et c.). */  8
void SignalHandling ( void ) ;  9
/* Set up the standard set of signal handlers. */  10
void DefaultSignals ( void ) ;  11
/* Set up normal signal handlers, i.e. handle with SIG DFL. */  12

13

/* End of signal.h */  14

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: signal.c,v 5.0 1998/12/20 00:25:34 georg Exp $ */  2

3

#include "common.h"  4
#include "aux.h"  5

#include "pg.h"  6

#include "val.h"  7
#include "vtree.h"  8

#include <sys/types.h>  9
#include <signal.h>  10

11

static void sig statusreport ( int sig ) ;  12
/* Write a status report using the function StatusReport(). */  13

14

void CleanExit ( int sig ) {  15
extern t vt *vt;  16
extern char *SignalBackUpFile;  17
char msg[128];  18

sprintf ( msg, "The programme caught signal %i.\n", sig );  19

MailNote ( msg );  20
vt backup ( SignalBackUpFile, vt );  21
exit ( ENO INT ) ;  22
}  23

24

void CoreExit ( int sig ) {  25
extern t vt *vt;  26
extern char *SignalBackUpFile;  27
char msg[128];  28

sprintf ( msg, "The programme caught signal %i.\n", sig );  29

MailNote ( msg );  30
vt backup ( SignalBackUpFile, vt );  31
abort ();  32
}  33

34

void sig statusreport ( int sig ) {  35
extern t val *val;  36
StatusReport ( val );  37
signal ( sig, &sig statusreport );  38
return ;  39
}  40

41

void DefaultSignals ( void ) {  42
signal ( SIGINT, SIG DFL );  43
signal ( SIGTERM, SIG DFL );  44
signal ( SIGQUIT, SIG DFL );  45
signal ( SIGALRM, SIG DFL );  46

47

signal ( SIGUSR1, SIG DFL );  48

49

signal ( SIGSEGV, SIG DFL );  50
signal ( SIGBUS, SIG DFL );  51
signal ( SIGILL, SIG DFL );  52
signal ( SIGFPE, SIG DFL );  53
signal ( SIGSYS, SIG DFL );  54
}  55

56

void SignalHandling ( void ) {  57
signal ( SIGINT, &CleanExit );  58
signal ( SIGTERM, &CleanExit );  59
signal ( SIGQUIT, &CleanExit );  60
signal ( SIGALRM, &CleanExit );  61

62

signal ( SIGUSR1, &sig statusreport );  63

64

signal ( SIGSEGV, &CoreExit );  65
signal ( SIGBUS, &CoreExit );  66
signal ( SIGILL, &CoreExit );  67

signal ( SIGFPE, &CoreExit );  68
signal ( SIGSYS, &CoreExit );  69
}  70

71

/* End of signal.c */  72

CHAPTER 5. GEN 60

Chapter 6

vsh

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: vsh.h,v 5.0 1998/12/20 00:26:29 georg Exp $ */  2

3

int parse ( FILE *in, char term ) ;  4

5

/* end of vsh.h */  6
/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: vsh.c,v 5.0 1998/12/20 00:26:25 georg Exp $ */  2

3

/* main function for vsh(1), the value shell.  **  4
** Interactive programme to classify value assignments */  5

6

#include "common.h"  7

8

#include <signal.h>  9

10

#include "pginit.h"  11

#include "val.h"  12

#include "vtree.h"  13

#include "vsh.h"  14

15

#define VSH ARGS "bek:nq:t:vhi"  16

17

/* Global Variables */  18
char *MyName, *MyPathName,  /* The programme name from argument no. 0 */ 19
*RealName = VSH NAME, /* The real name of the programme */ 20
CallString[CALL STRING L], /* The entire command call with arguments */  21
*UserName, *HostName, /* Environment. */ 22
*MyVersion = VSH VERSION, /* Programme version number. */  23
*CompileDate = GEN COMPILE, /* Date of compilation. */  24
*MailTo, *StatusFile = VAL STATUSFILE,  25
timeStart[TIME STRING L];  26
t vt *vt = NULL;  27
pid t child;  28

29

int main ( int argc, char *argv[ ] ) {  30

31

/* External variable declarations. */  32
extern t pdim pg dim, pg order;  /* PG parameters */  33
extern char *optarg;  /* for getopt(3) */  34
extern int optind, opterr, optopt;  /* for getopt(3) */  35
extern t vt *vt;  /* Data structure */  36

CHAPTER 6. VSH

extern t val *val;  /* Data structure */  37
extern t pg *pg;  /* Data structure */  38
extern t s *sp;  /* Data structure */  39
extern unsigned long v allocn;  40

41

/* Internal variable declarations. */  42
int i; /* Index counter */ 43
char *SFile = NULL, *InFile = NULL, FileName[FILE NAME L],  44
*TreeFile = NULL, *InitFile = NULL,  45
*BOutFile = GEN BOUTFILE, *BackUpFile = NULL,  46
CBackUpFile[FILE NAME L], BBackUpFile[FILE NAME L], *cpt;  47
char f, mode e = FALSE, mode i = TERM;  48
FILE *fs;  49
time t theTime;  50

51

/* Parsing argument 0. */  52
MyPathName = *argv;  53
MyName = basename ( MyPathName );  54

55

/* Variable initialisation. */  56
v allocn = 1; /* Allocate memory for one assignment at a time. */  57
pg dim = 0;  58
mode i = isatty ( 0 ); /* Initialise the flag indicating interactivity */  59

60

/* Option parsing. */  61
while ( −1 != ( f = getopt( argc, argv, VSH ARGS ) ) )  62
switch (f) {  63
case 'b': mode i = 0; break;  64
case 'k': pg dim = atoi ( optarg ); break;  65
case 'q': pg order = atoi ( optarg ); break;  66
case 'h': PrintHelp(); exit (1); break;  67
case 'e': mode e = ECHO; break;  68
case 'i': mode i = TERM; break;  69
case 'n': mode e = 0; break;  70
case 'v': PrintVersion(); exit (1); break;  71
default: ErrorUsage(); exit (1);  72
} /* switch */  73

74

/* Initialise the global variables (pg, val, sp) */  75
if ( pg dim > 0 ) pv init ( pg dim, pg order );  76

77

if ( argc == optind ) { /* No file name is given. */  78
/* Read a config file */  79
if ( NULL != ( fs = fopen ( VSH CONF, "r" ) ) ) {  80
parse ( fs, 0 );  81
fclose ( fs );  82
};  83
parse ( stdin, mode i|mode e );  84
} else { /* Read commands from file */  85
fs = fileopen ( argv[optind], "r" );  86
parse ( fs, mode e );  87
fclose ( fs );  88
};  89

90

exit ( 0 );  91
}  92

93

/* end of vsh.c */  94

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: lex.l,v 5.0 1998/12/20 00:24:18 georg Exp $ */  2

/* Lexical parser for vsh(1) */  4

5

%{  6

7

/* Configurable section */  8
#define MAX STR L 64  9
#define MAX ARG  6  10

11

/* Include */  12

#include "common.h"  13

#include "aux.h"  14

#include "pgval.h"  15

#include "vsh.h"  16

#include "valmsp.h"  17

#include <string.h>  18

19

/* Internal macros */  20
#define prompt(n) ( terminal ? fprintf ( stdout, "vsh:%i> ", n ) : 0 ),\  21
BEGIN (INITIAL)  22
#define NO IMP  ( fprintf ( stderr, \  23

                   "Sorry, I haven't learnt how to do that, yet.\n" ) )  24

25

/* Enumerate all commands */  26
enum { C LOG, C OPEN, C UNLOG, C CLOSE, C MAX, C EVAL, C VEVAL,  27
C CLEAR, C SUBVAL, C PVP, C PALL, C PRINT, C VER, C FIX, C COUNT, 28
C SPFIX,  29
C HELP, C CLASS, C NEXT, C SPACE, C SUBP, C SUB, C SET, C SPAN,  30
C SPDEF, C SDEF, C PDEF, C ECHO, C NOECHO, C SETFIX,  31
C LINE,  32
C NECHO, C ECHO, C SP,  33
C QPROB, C MPROB, C PROBE,  34
C PG, C SOURCE, C CSET, C SPSET, C VAL, C GET };  35

36

/* Static C identifiers. */  37
static void execute ( int c );  38
/* Handle commands without arguments. */  39
static void strcmd ( int c, const char *s );  40
/* Handle commands with string argument. */  41
static void intcmd ( int c, int arg[], int argno );  42
/* Handle commands with integer arguments. */  43
static int source ( const char *f ) ;  44
/* Read commands from file. */  45
static char arglim ( int no, int mx, int mn ) ;  46
/* Check that the number of argument no correct. Print an error **  47
** message otherwise.  */  48

49

static YY BUFFER STATE mbuf; /* Main buffer */  50
static FILE *valfile,  /* The file used by open/next/close */  51
*outfile;  /* Usually equal to stdout */  52
static char terminal;  /* True if reading from stdin. */  53
static char name;  /* The identifier argument for pdef etc. */  54
static char echo;  /* True if commands should be echoed. */  55

56

%}  57

58

/* Character classes */  59

60

COMMENT #  61
VCOM :  62
QUO  ["]  63

CHAR [a-zA-Z0-9_.]  64

CHAPTER 6. VSH

NAME [a-zA-Z]  65
LETTER [a-zA-Z_]  66

WORD {LETTER}{CHAR}*  67
DIGIT [0-9]  68
NUMBER [0-9]+  69
WHITE [ \t]  70

71

/* Command names and aliases. Aliases are not documented,  72
** only the main command name is. Names starting with an  73
** underscore are reserved for testing, and not documented. */  74

75

C CLASS class|\.  76
C CLEAR clear|cv  77
C CLOSE (close|unopen)  78
C COUNT count  79
C CSET cset  80
C ECHO echo|"+"  81
C EVAL eval(uate)?  82
C FIX fix  83
C SPFIX spfix  84
C GET get  85
C HELP help|\?  86
C LINE line  87
C LOG log|>  88
C MAX max(val)?  89
C MPROB mp(robe)?  90
C NEXT n(ext)?|readval  91
C NOECHO noecho|"-"  92
C OPEN open  93
C PALL p(rint)?all  94
C PDEF pd(ef)?  95
C PG pg 96
C PRINT print  97
C PROBE probe  98
C PVP p(vp)?  99
C QPROB qp(robe)?  100
C QUIT (quit|q|exit|x)  101
C SDEF sd(ef)?  102
C SET set  103
C SETFIX sf|setfix  104
C SHELL sh(ell)?|!  105
C SOURCE source|<  106
C SPACE space  107
C SPAN span  108
C SPDEF spd(ef)?  109
C SPSET spset  110
C SUB (sub|subspace|sup|superspace)  111
C SUBP subp(rint)?  112
C SUBVAL subval|sp  113
C UNLOG unlog  114
C VAL val|"="  115
C VER ver(sion)?  116
C VEVAL veval(uate)?|classify  117

118

/* Undocumented commands for testing */  119

120

C NECHO necho  121
C ECHO echo  122
C SP  sp  123

124

/* Start conditions */  125

126

%x quote shell  127
%s unquote ex string cmd str S QUIT no arg IGNORE ex int def  128

129

%%  130

131

%{  132
static int cmdno = 0; /* Counter for the prompt */ 133
static int arg[MAX_ARG], cmd, argno = 0; /* Command and arguments */  134
static char str[MAX_STR_L];  /* String arguments for command */  135

136

prompt ( ++cmdno ); /* Print the initial prompt */  137
%}  138

139

^.+\n  { if ( echo ) fprintf (outfile, "%s", yytext ); REJECT; }  140

141

{WHITE}+  { /* Ignore white space */ }  142

143

<INITIAL>\n  { if ( echo ) putc ( ’\n’, outfile ); prompt ( cmdno );  144
/* ignore empty lines */ }  145

146

<S QUIT>\n  { return ( 0 ); /* exit */ }  147

148

<INITIAL><<EOF>> { putc ( ’\n’, stderr ); return ( 0 ) ; /* exit */ }  149

150

<<EOF>>  { fprintf ( stderr, "Error: Unexpected end of file.\n" );  151

return ( 1 ); }  152

153

<INITIAL>{C QUIT} { BEGIN ( S QUIT ); }  154

155

/* Handling define commands */  156

157

<INITIAL>{C LINE} { cmd = C LINE; BEGIN ( def ); }  158
<INITIAL>{C PDEF} { cmd = C PDEF; BEGIN ( def ); }  159
<INITIAL>{C SPDEF} { cmd = C SPDEF; BEGIN ( def ); }  160
<INITIAL>{C SDEF} { cmd = C SDEF; BEGIN ( def ); }  161
<def>{NAME}  { name = yytext[0]; BEGIN ( ex int ); }  162
<def>.  {  163

   fprintf ( stderr, "Error: expecting name to define.\n" );  164

}  165

166

/* Handling commands with no argument */  167

168

<INITIAL>{C MPROB} { cmd = C MPROB; BEGIN ( no arg ); }  169
<INITIAL>{C UNLOG} { cmd = C UNLOG; BEGIN ( no arg ); }  170
<INITIAL>{C COUNT} { cmd = C COUNT; BEGIN ( no arg ); }  171
<INITIAL>{C PRINT} { cmd = C PRINT; BEGIN ( no arg ); }  172
<INITIAL>{C PVP} { cmd = C PVP; BEGIN ( no arg ); }  173
<INITIAL>{C VER} { cmd = C VER; BEGIN ( no arg ); }  174
<INITIAL>{C HELP} { cmd = C HELP; BEGIN ( no arg ); }  175
<INITIAL>{C CLOSE} { cmd = C CLOSE; BEGIN ( no arg ); }  176
<INITIAL>{C EVAL} { cmd = C EVAL; BEGIN ( no arg ); }  177
<INITIAL>{C VEVAL} { cmd = C VEVAL; BEGIN ( no arg ); }  178
<INITIAL>{C CLASS} { cmd = C CLASS; BEGIN ( no arg ); }  179
<INITIAL>{C NEXT} { cmd = C NEXT; BEGIN ( no arg ); }  180
<INITIAL>{C CLEAR} { cmd = C CLEAR; BEGIN ( no arg ); }  181
<INITIAL>{C ECHO} { cmd = C ECHO; BEGIN ( no arg ); }  182
<INITIAL>{C NOECHO} { cmd = C NOECHO; BEGIN ( no arg ); }  183

184

<no arg>\n  { execute ( cmd ); prompt ( ++cmdno ); }  185

186

<S QUIT,no arg,cmd str>. {  187

   fprintf ( stderr, "Error: Trailing characters.\n" );  188

prompt ( cmdno );  189
}  190

191

/* Handling commands with string argument */  192

193

<INITIAL>{C LOG}  { cmd = C LOG; BEGIN ( ex string ); }  194
<INITIAL>{C OPEN} { cmd = C OPEN; BEGIN ( ex string ); }  195
<INITIAL>{C ECHO} { cmd = C ECHO; BEGIN ( ex string ); }  196
<INITIAL>{C SOURCE} { cmd = C SOURCE; BEGIN ( ex string ); }  197
<INITIAL>{C SP}  { cmd = C SP; BEGIN ( ex string ); }  198

199

<ex string>\n  {  200

  fprintf ( stderr, "Error: Expecting string argument.\n" );  201

prompt ( cmdno );  202
}  203

204

<ex string>{QUO} { BEGIN ( quote ); }  205

206

<ex string>{WORD} { strcpy ( str, yytext ); BEGIN ( cmd str ); }  207

208

<quote>\n  { fprintf ( stderr, "Error: Unmatched quote.\n" ); }  209

210

<quote>.*/{QUO} { strcpy ( str, yytext ); BEGIN ( unquote ); }  211

212

<unquote>{QUO}  { BEGIN ( cmd str ); }  213

214

<cmd str>\n  { strcmd ( cmd, str ); prompt ( ++cmdno ); }  215

216

<INITIAL>{C SHELL} { BEGIN ( shell ); }  217
<shell>.*\n  { system ( yytext ); prompt ( ++cmdno ); }  218

219

/* Handling commands with integer arguments */  220

221

<INITIAL>{C PALL} { cmd = C PALL; BEGIN ( ex int ); }  222
<INITIAL>{C SPACE} { cmd = C SPACE; BEGIN ( ex int ); }  223
<INITIAL>{C SUB} { cmd = C SUB; BEGIN ( ex int ); }  224
<INITIAL>{C SUBP} { cmd = C SUBP; BEGIN ( ex int ); }  225
<INITIAL>{C SET} { cmd = C SET; BEGIN ( ex int ); }  226
<INITIAL>{C SETFIX} { cmd = C SETFIX; BEGIN ( ex int ); }  227
<INITIAL>{C SPSET} { cmd = C SPSET; BEGIN ( ex int ); }  228
<INITIAL>{C SPFIX} { cmd = C SPFIX; BEGIN ( ex int ); }  229
<INITIAL>{C CSET} { cmd = C CSET; BEGIN ( ex int ); }  230
<INITIAL>{C GET} { cmd = C GET; BEGIN ( ex int ); }  231
<INITIAL>{C SPAN} { cmd = C SPAN; BEGIN ( ex int ); }  232
<INITIAL>{C VAL} { cmd = C VAL; BEGIN ( ex int ); }  233
<INITIAL>{C SUBVAL} { cmd = C SUBVAL; BEGIN ( ex int ); }  234
<INITIAL>{C MAX} { cmd = C MAX; BEGIN ( ex int ); }  235
<INITIAL>{C PG} { cmd = C PG; BEGIN ( ex int ); } 236
<INITIAL>{C FIX} { cmd = C FIX; BEGIN ( ex int ); }  237
<INITIAL>{C PROBE} { cmd = C PROBE; BEGIN ( ex int ); }  238
<INITIAL>{C QPROB} { cmd = C QPROB; BEGIN ( ex int ); }  239
<INITIAL>{C NECHO} { cmd = C NECHO; BEGIN ( ex int ); }  240

241

<ex int>{NUMBER} { arg[argno++] = atoi ( yytext ); }  242
<ex int>{NAME}  { argno += nt lookup ( yytext[0], arg + argno ); }  243

244

<ex int>\n  { intcmd ( cmd, arg, argno );  245
argno = 0; prompt ( ++cmdno ); }  246

247

<ex int>.  {  248

   fprintf ( stderr, "Error: expecting integer.\n" );  249

prompt ( cmdno );  250

}  251

252

/* Ignoring comments and white space */  253

254

{COMMENT}.*\n  { prompt ( cmdno ); }  255
{VCOM}.*\n  { if ( ! echo ) fprintf ( outfile, "%s", yytext );  256
prompt ( cmdno ); }  257

258

<INITIAL>{WORD} {  259

fprintf ( stderr, "Error: Unknown command: %s.\n", yytext );  260

BEGIN ( IGNORE ); }  261

262

<IGNORE>.*\n  { prompt ( cmdno ); }  263

264

%%  265

266

int parse ( FILE *in, char term ) {  267
extern char terminal;  268
int r;  269
terminal = term&TERM;  270
echo = term&ECHO;  271
yy switch to buffer ( mbuf = yy create buffer ( in, YY BUF SIZE ) );  272
outfile = stdout;  273
r = yylex ();  274
yy delete buffer ( mbuf );  275
return ( r ) ;  276
}  277

278

static int source ( const char *f ) {  279
FILE *s;  280
YY BUFFER STATE b, ob;  281
char t;  282
extern char terminal;  283

284

/* Open the file */  285
if ( NULL == ( s = fopen ( f, "r" ) ) ) {  286

  fprintf ( stderr, "File %s does not exist.\n", f );  287

return ( ENO FOPEN );  288
}  289

290

/* Don’t print the prompt while sourcing files. */  291
t = terminal; terminal = 0;  292

293

ob = YY CURRENT BUFFER; /* Store a pointer to the old buffer */  294
b = yy create buffer ( s, YY BUF SIZE ); /* Create buffer */  295
yy switch to buffer ( b );  /* Switch to the new buffer */  296
yylex ();  /* Parse the buffer */  297
yy delete buffer ( b ); /* Deleta the buffer */  298
fclose ( s );  /* Close the file */  299
terminal = t;  /* Reset the flag to indicate if we want a prompt */  300
yy switch to buffer ( ob ); /* Return to the old buffer */  301
return ( 0 );  302
}  303

304

void execute ( int c ) {  305
extern t val *val;  306
switch ( c ) {  307
case C ECHO: echo = TRUE; break;  308
case C NOECHO: echo = FALSE; break;  309
case C MPROB:  310
while ( 0 < val incprobe ( NULL, 0 ) ) {};  311
break;  312

CHAPTER 6. VSH

case C CLEAR:  313
nt init ();  314
val clear ( val, val novalue );  315
break;  316
case C PVP:  317
pv print ( outfile );  318
break;  319
case C PRINT:  320
val valprint ( outfile, val );  321
break;  322
case C VEVAL:  323
val sumval ( val );  324
v reinit ( val−>v );  325
val getclass ( val, outfile );  326
val ds ( val );  327
val classprint ( val, outfile );  328
break;  329
case C EVAL:  330
val sumval ( val );  331
v reinit ( val−>v );  332
val class ( val );  333
val ds ( val );  334
val classprint ( val, outfile );  335
break;  336
case C CLOSE:  337
if ( NULL != valfile ) fclose ( valfile );  338
break;  339
case C CLASS:  340
val classprint ( val, outfile );  341
break;  342
case C NEXT:  343
if ( NULL == valfile ) {  344

  fprintf ( stderr, "Sorry, I have no file to read from.\n" );  345

return;  346
};  347
if ( EOF == val assign ( val, ( NULL == valfile ? stdin : valfile ) ) ) {  348
fclose ( valfile );  349

  fprintf ( stderr, "EOF, closing file.\n" );  350

};  351
v reinit ( val−>v );  352
val sumval ( val );  353
val classify ( val );  354
break;  355
case C COUNT:  356
fprintf ( outfile, "%i fixed values.\n", pv fixcount() );  357
break;  358
case C UNLOG:  359
if ( outfile != stdout ) fclose ( outfile );  360
outfile = stdout;  361
break;  362
case C VER:  363
PrintVersion();  364
break;  365
case C HELP:  366

fprintf ( stderr, "Sorry, you have to read the man page.\n" );  367

break;  368
default:  369
NO IMP ;  370
break;  371
}  372
}  373

374

void strcmd ( int c, const char *s ) {  375
FILE *fs;  376
extern t s *sp;  377
extern t pdim pg dim, pg order;  378
switch ( c ) {  379
case C SOURCE:  380
source ( s );  381
break;  382
case C OPEN:  383
if ( NULL != valfile ) fclose ( valfile );  384
valfile = fileopen ( s, "r" );  385
break;  386
case C LOG:  387
outfile = fileopen ( s, "a" );  388
break;  389
case C ECHO:  390
fprintf ( outfile, "%s\n", s );  391
break;  392
case C SP:  393
if ( NULL == ( fs = fopen ( s, "w" ) ) ) {  394

   fprintf ( stderr, "Could not open file %s.\n", s );  395

return ;  396
}  397
s print ( sp, fs, pg dim, pg order );  398
fclose ( fs );  399
break;  400
default:  401
NO IMP ;  402
break;  403
}  404
}  405

406

char arglim ( int no, int mx, int mn ) {  407
if ( no < mn ) {  408

fprintf ( stderr, "Error: Too few arguments.\n" );  409

return ( −1 );  410
}  411
if ( no > mx ) {  412

fprintf ( stderr, "Error: Too many arguments.\n" );  413

return ( 1 );  414
}  415
return ( 0 );  416
}  417

418

void intcmd ( int c, int arg[], int argno ) {  419
extern t pg *pg;  420
extern t val *val;  421
extern t pdim pg dim;  422
static int i;  423
t ps subspace;  424
switch ( c ) {  425
case C PALL:  426
if ( arglim ( argno, 1, 0 ) ) return ;  427
if ( argno == 0 ) arg[0] = 1;  428
pv printall ( outfile, arg[0] );  429
break;  430
case C QPROB:  431
if ( arglim ( argno, 1, 0 ) ) return ;  432
if ( argno == 0 ) arg[0] = 0;  433
val incprobe ( NULL, arg[0] );  434
break;  435
case C PROBE:  436

if ( arglim ( argno, 1, 0 ) ) return ;  437
if ( argno == 0 ) arg[0] = 0;  438
val incprobe ( outfile, arg[0] );  439
break;  440
case C LINE:  441
if ( arglim ( argno, 2, 2 ) ) return ;  442
if ( ! nt line ( name, arg[0], arg[1] ) )  443

  fprintf ( stderr, "Error defining points.\n" );  444

break;  445
case C PDEF:  446
if ( arglim ( argno, 1, 1 ) ) return ;  447
if ( ! nt pdef ( name, arg[0] ) )  448

  fprintf ( stderr, "Error defining point.\n" );  449

break;  450
case C SDEF:  451
if ( arglim ( argno, 2, 2 ) ) return ;  452
if ( ! nt sdef ( name, arg[0], arg[1] ) )  453

  fprintf ( stderr, "Error defining subspace.\n" );  454

break;  455
case C SUBVAL:  456
if ( arglim ( argno, 2, 2 ) ) return ;  457
pv sprint ( outfile, arg[0], arg[1] );  458
break;  459
case C VAL:  460
for ( i = 0; i < argno; ) {  461
pv pprint ( outfile, arg[i] );  462
putc ( ++i % 10 == 0 ? ’\n’ : ’\t’, outfile );  463
};  464
if ( i % 10 != 0 ) putc ( ’\n’, outfile );  465
break;  466
case C SPDEF:  467
subspace = pg get ( pg, arg, argno );  468
if ( pg noel == subspace ) {  469

  fprintf ( stderr, "Error: no such subspace.\n" );  470

} else {  471
if ( ! nt sdef ( name, argno−1, subspace ) )  472

   fprintf ( stderr, "Error defining subspace.\n" );  473

};  474
break;  475
case C SPAN:  476
subspace = pg get ( pg, arg, argno );  477
if ( pg noel == subspace ) {  478

  fprintf ( stderr, "Error: no such subspace.\n" );  479

} else {  480
pv sprint ( outfile, argno − 1, subspace );  481
};  482
break;  483
case C GET:  484
subspace = pg get ( pg, arg, argno );  485
if ( pg noel == subspace ) {  486

  fprintf ( stderr, "Error: no such subspace.\n" );  487

} else {  488
pg space ( outfile, pg, argno − 1, subspace );  489
};  490
break;  491
case C SUBP:  492
if ( arglim ( argno, 3, 3 ) ) return ;  493
if ( arg[0] == arg[1] ) {  494
fprintf ( stderr,  495

          "Error: Arg 1 and Arg 2 are supposed to be different.\n" );  496

return ;  497
};  498

if ( ENO IMP == pv ssprint ( outfile, arg[0], arg[1], arg[2] ) ) NO IMP ;  499
break;  500
case C SUB:  501
if ( arglim ( argno, 3, 3 ) ) return ;  502
if ( arg[0] == arg[1] ) {  503
fprintf ( stderr,  504

          "Error: Arg 1 and Arg 2 are supposed to be different.\n" );  505

return ;  506
};  507
pg ssprint ( outfile, pg, arg[0], arg[1], arg[2] );  508
break;  509
case C SPFIX:  510
if ( arglim ( argno, 3, 2 ) ) return ;  511
if ( ( argno > 2 ) && ( arg[2] == 0 ) )  512
val spaceunfix ( arg[0], arg[1] )  513
else  514
val spacefix ( arg[0], arg[1] );  515
break;  516
case C FIX:  517
if ( arglim ( argno, 1, 1 ) ) return ;  518
val fixit ( val, arg[0] );  519
break;  520
case C MAX:  521
if ( arglim ( argno, 1, 1 ) ) return ;  522
if ( arg[0] >= pg dim ) {  523
fprintf ( stderr,  524

          "Error: k = %i, no subspaces of dimension %i exists.\n",  525

pg dim, arg[0] );  526
return ;  527
};  528
mval print ( outfile, val−>m[arg[0]] );  529
break;  530
case C SPACE:  531
if ( arglim ( argno, 2, 2 ) ) return ;  532
pg space ( outfile, pg, arg[0], arg[1] );  533
break;  534
case C SETFIX:  535
if ( arglim ( argno, 2, 2 ) ) return ;  536
val set ( val, arg[0], arg[1] );  537
break;  538
case C SET:  539
if ( arglim ( argno, 2, 2 ) ) return ;  540
val setval ( val, arg[0], arg[1] );  541
break;  542
case C SPSET:  543
if ( arglim ( argno, 5, 3 ) ) return ;  544
if ( argno < 4 ) arg[3] = NO CHANGE;  545
if ( argno < 5 ) arg[4] = TRUE;  546
val spaceval ( arg[0], arg[1], arg[2], arg[3], arg[4] );  547
break;  548
case C CSET:  549
if ( arglim ( argno, 5, 3 ) ) return ;  550
if ( argno < 4 ) arg[3] = DO CHANGE;  551
if ( argno < 5 ) arg[4] = NO FIXCHANGE;  552
val spaceval ( arg[0], arg[1], arg[2], arg[3], arg[4] );  553
break;  554
case C PG:  555
if ( arglim ( argno, 2, 2 ) ) return ;  556
pv init ( arg[0], arg[1] );  557
break;  558
case C NECHO:  559
fprintf ( outfile, "I have %i arguments.\n", argno );  560

while ( argno−− > 0 ) {  561
fprintf ( outfile, "Arg. #%i is %i.\n", argno, arg[argno] );  562
};  563
break;  564
default:  565
NO IMP ;  566
break;  567
}  568
return ;  569
}  570

571

/* End of lex.l */  572

Chapter 7

Auxiliary programmes

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pgc.c,v 5.0 1998/12/20 00:24:50 georg Exp $ */  2

3

/* main function for pgc(1)  **  4
** pgc creates a projective geometry and stores all **  5
** incidence relations.  */  6

7

#include "common.h"  8

9 10

#include "pginit.h"  11
#include "points.h"  12

#include "aux.h"  13

#include "prep.h"  14

15

#define ARGS  "dhk:m:n:o:q:v"  16

#define PGC OUTFILE "pgc:output"  17
#ifdef DEBUG  18
# define PGC DEBUG FILE "pgc:debugfile"  19
#endif  20

21

/* Global Variables */  22
char *MyName, *MyPathName,  /* The programme name from argument no. 0 */ 23
*UserName, *HostName,  /* Environment. */  24
*RealName = PGC NAME,  /* The real name of the programme */  25
CallString[CALL STRING L], /* The entire command call with arguments */  26
*MyVersion = GEN VERSION, /* Programme version number. */  27
*CompileDate = GEN COMPILE, /* Date of compilation. */  28
*MailTo,  29
*SignalBackUpFile = DEF SIGBFILE,  30
timeStart[TIME STRING L];  31
t pdim k=4, q=2; /* PG parameters */ 32
int lfd;  33

34

int main ( int argc, char *argv[ ] ) {  35
extern char *optarg;  36
extern int optind, opterr, optopt;  37
signed char m=0, f, i, c = 0, *arg;  38
t pdim k=4, q=2;  39
signed char mode d = 0;  40
char *OutFile = PGC OUTFILE, coord[12], *S File = NULL;  41
char filename[FILE NAME L];  42
FILE *OutStream;  43

CHAPTER 7. AUXILIARY PROGRAMMES

t pg *pg;  44
t msp *sp;  45
t s *s;  46
t bas *bas;  47

48

MyName = *argv;  49

50

while ( −1 != ( f = getopt( argc, argv, ARGS ) ) )  51
switch (f) {  52
case 'q': q = atoi(optarg); break;  53
case 'k': k = atoi(optarg); break;  54
case 'o': OutFile = optarg; break;  55
case 'd': ++mode d; break;  56
case 'h': PrintHelp(); exit (1); break;  57
case 'v': PrintVersion(); exit (1); break;  58
default: ErrorUsage(); exit (1);  59
}  60

61

if ( mode d ) exit ( pg dimprint ( stdout, k, q ) );  62

63

pg = pg init ( k, q );  64
OutStream = fileopen ( OutFile, "w" );  65
pg dump ( OutStream, pg );  66
fclose ( OutStream );  67
pg del ( pg );  68
exit ( 0 );  69
}  70

71

/* End of pgc.c */  72

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: vdg.c,v 5.0 1998/12/20 00:26:23 georg Exp $ */  2

3

#include "common.h"  4

5

#include "aux.h"  6

#include "pg.h"  7

#include "val.h"  8
#include "vtree.h"  9

10

#define ARGS  "CghPv"  11

12

/* Global Variables */  13
char *MyName, *MyPathName,  /* The programme name from argument no. 0 */ 14
*UserName, *HostName,  /* Environment. */  15
*RealName = GEN NAME,  /* The real name of the programme */  16
CallString[CALL STRING L], /* The entire command call with arguments */  17
*MyVersion = GEN VERSION, /* Programme version number. */  18
*CompileDate = GEN COMPILE, /* Date of compilation. */  19
*MailTo, *StatusFile = VAL STATUSFILE,  20
timeStart[TIME STRING L];  21
t vt *vt = NULL;  22
t pdim pg dim=4, pg order=2; /* PG parameters */  23
t pg *pg = NULL;  24
t val *val = NULL;  25

26

int main ( int argc, char *argv[ ] ) {  27

28

/* External variable declarations. */  29
extern char *optarg;  /* for getopt(3) */  30
extern int optind, opterr, optopt;  /* for getopt(3) */  31

extern t vt *vt;  /* Data structure */  32
extern t pg *pg;  /* Data structure */  33
extern t val *val;  34
extern unsigned long v allocn;  35

36

/* Internal variable declarations. */  37
char f, mode = 0;  38
char *OutFile = GEN OUTFILE, *InFile = NULL, FileName[FILE NAME L];  39
FILE *InStream;  40

41

v allocn = 1; /* Allocate memory for one assignment at a time. */  42

43

/* Parsing argument 0. */  44
MyPathName = *argv;  45
MyName = basename ( MyPathName );  46

47

/* Option parsing. */  48
while ( −1 != ( f = getopt( argc, argv, ARGS ) ) )  49
switch (f) {  50
case 'C': case 'P': case 'g':  51
if ( mode != 0 ) ErrEx ( ERR FLAGS );  52
mode = f;  53
break;  54
case 'h': PrintHelp(); exit (1); break;  55
case 'k': pg dim = atoi(optarg); break;  56
case 'q': pg order = atoi(optarg); break;  57
case 'v': PrintVersion(); exit (1); break;  58
default: ErrorUsage(); exit (1);  59
} /* switch */  60

61

/* Argument parsing. */  62
if ( argc > optind ) InFile = argv[optind++];  63
if ( argc > optind ) OutFile = argv[optind++];  64
if ( argc > optind ) ErrorUsage () ;  65

66

/* Working */  67
switch ( mode ) {  68
case 'P': /* Print info about the file */  69
if ( NULL == InFile ) ErrorUsage() ;  70
InStream = fileopen ( InFile, "rb" );  71
vt finfo ( InStream );  72
fclose ( InStream );  73
exit ( 0 );  74
break;  75
case 'g': /* Read a valex file and classify the assignments. */  76
GetData ( NULL, NULL );  77
InStream = ( NULL == InFile ? stdin : fileopen ( InFile, "r" ) );  78
while ( EOF != val assign ( val, InStream ) )  79
val classprint ( val, stdout );  80
StatusReport ( val );  81
fclose ( InStream );  82
exit ( 0 );  83
break;  84
case 'C': /* Translate the output from gen(1). */  85
if ( NULL == InFile ) ErrorUsage () ;  86
GetData ( InFile, NULL );  87
vt printbyclass ( OutFile, vt ); /* ASCII output */  88
vt del ( vt );  89
exit ( 0 );  90
break;  91
};  92

93

ErrorUsage ();  94
exit ( 255 );  95
}  96

97

/* end of vdg.c */  98

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pgtest.c,v 5.0 1998/12/20 00:25:05 georg Exp $ */  2

3

#include "common.h"  4
#include "pginit.h"  5
#include "points.h"  6
#include "aux.h"  7

#include "gf.h"  8

9

#define ARGS  "b:c:C:ghk:n:q:stvwxyz"  10

11

/* Global Variables */  12
char *MyName, *MyPathName,  /* The programme name from argument no. 0 */ 13
*UserName, *HostName,  /* Environment. */  14
*RealName = PGT NAME,  /* The real name of the programme */  15
CallString[CALL STRING L], /* The entire command call with arguments */  16
*MyVersion = GEN VERSION, /* Programme version number. */  17
*CompileDate = GEN COMPILE, /* Date of compilation. */  18
*MailTo,  19
*SignalBackUpFile = DEF SIGBFILE,  20
timeStart[TIME STRING L];  21
unsigned char k=4, q=2, m=0, n=0;  22

23

int main ( int argc, char *argv[ ] ) {  24
extern char *optarg;  25
extern int optind, opterr, optopt;  26
signed char m=0, f, i, gea, geb, r, s, modeval;  27
char *modestr, coord[12], mode = 0, *infile, *outfile;  28
FILE *stream;  29
t ps pt;  30
t pg *pg;  31
t bas *bas;  32
t msp *sp;  33

34

MyName = *argv;  35

36

/* Parsing options */  37
optarg = 0;  38
while ( −1 != ( f = getopt( argc, argv, ARGS ) ) )  39
switch (f) {  40
case 'q': q = atoi(optarg); break;  41
case 'k': k = atoi(optarg); break;  42
case 'c':  43
if ( mode ) ErrEx ( ERR FLAGS ) ;  44
mode = f;  45
modestr = optarg;  46
break;  47
case 'n': case 'b': case 'C':  48
if ( mode ) ErrEx ( ERR FLAGS ) ;  49
mode = f;  50
modeval = atoi(optarg);  51
break;  52
case 'h': PrintHelp(); exit (1); break;  53
case 'v': PrintVersion(); exit (1); break;  54
case 'g': case 's': case 't': case 'x': case 'y': case 'z': case 'w':  55

if ( mode ) ErrEx ( ERR FLAGS ) ;  56
mode = f;  57
break;  58
default: ErrorUsage(); exit ( 1 ) ;  59
}  60

61

/* Executing */  62
switch ( mode ) {  63
case 'x': case 'y': case 'z': case 'w':  64
/* Translate a file from pgc to readable output (different formats) */  65
infile = argv[optind++];  66
outfile = argv[optind++];  67
if ( stream = fopen ( infile, "rb" ) ) {  68
pg = pg load ( stream );  69
fclose ( stream );  70
} else {  71
ErrEx ( ERR FOPEN );  72
};  73
if ( stream = fopen ( outfile, "wb" ) ) {  74
switch ( mode ) {  75
case 'w': pg pprint (stream,pg); break;  76
case 'x': pg print (stream,pg); break;  77
case 'y': pg dump (stream,pg); break;  78
case 'z': pg sprint (stream,pg); break;  79
}  80
fclose ( stream );  81
} else {  82
ErrEx ( ERR FOPEN );  83
};  84
exit ( 0 );  85
case 'g': /* Test Galois Field arithmetrics. */  86
gea = atoi ( argv[optind++] );  87
geb = atoi ( argv[optind++] );  88
printf ( "%i*%i=%i; %i, %i\n", gea, geb, gf mult ( gea, geb, q ),  89
gf inv ( gea, q ), gf inv ( geb, q ) );  90
exit ( 0 );  91
case 't': /* Test the pg theta() function */  92
r = atoi ( argv[optind++] );  93
s = atoi ( argv[optind++] );  94
printf ( "\\theta ( %i, %i; %i, %i ) = %i\n", r,s,k,q, pg theta(r,s,k,q) );  95
exit ( 0 );  96
case 'c': /* Test the mapping between representations of points. */  97
pt fromstr ( (t pt)coord, modestr );  98

printf ( "Coordinates: ( " );  99

for ( i = 0; i < k; ++ i ) printf ( "%i, ", coord[i] );  100
printf ( "%i )\n", coord[k] );  101
printf ( "Point no. %i\n", pt getno ( (t pt)coord, k, q ) );  102
exit ( 0 );  103
case 'n': /* Test the pg elno() functions. */  104
printf ( "\\phi ( %i; %i, %i ) = %i\n", modeval,k,q, pg elno(q,k,modeval) );  105
exit ( 0 );  106
case 's': case 'b': /* Test bas comb() and msp init() */  107
m = argc − optind − 1 ;  108
bas = bas init ( m );  109

110

while ( optind < argc ) {  111
pt fromstr ( (t pt)coord, argv[optind++] );  112
bas−>bas[m−−] = pt getno ( (t pt)coord, k, q );  113
};  114

115

if ( mode == 's' ) {  116
sp = msp init ( bas, k, q );  117

msp print ( sp, stdout, k, q );  118
} else {  119
pt = bas comb ( bas, modeval, k, q ) ;  120
pt fromno ( (t pt)coord, pt, k, q );  121
printf ( "%i ", pt );  122
pt print ( (t pt)coord, stdout, k, q );  123
putchar ( '\n' );  124
};  125

126

exit ( 0 );  127
case 'C': /* Test the mapping between representations of points. */  128
pt fromno ( (t pt)coord, modeval, k, q );  129

printf ( "Coordinates: ( " );  130

for ( i = 0; i < k; ++ i ) printf ( "%i, ", coord[i] );  131
printf ( "%i )\n", coord[k] );  132
exit ( 0 );  133
};  134

135

exit ( 1 ); /* We are not supposed to reach this line. */  136
}  137

138

/* End of pgtest.c */  139

Chapter 8

PID check

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: pidcheck.c,v 5.0 1998/12/20 00:25:17 georg Exp $ */  2

3

/* The pidcheck(1) programme reads an active file, like that left **  4
** by gen(1), and checks whether the programme is still running. **  5
** If it is not, it restarts it.  */  6

7

#include <sys/types.h>  8
#include <signal.h>  9
#include <sys/procset.h>  10
#include <stdio.h>  11

#include "common.h"  12

#include "gen.h"  13

#include "logenv.h"  14

15

#define MAX ARG 12  16

17

int main ( int argc, char *argv[ ] ) {  18
char CallString[CALL STRING L],  19
*BackUpFile,  20
BUFbuf[FILE NAME L], BBackUpFile[FILE NAME L];  21
char *genargv[MAX ARG], *actfile, *dir;  22
char verbose = 0, i;  23
FILE *f;  24
extern char *gen host, *gen arg, *gen gen, *gen flags, *gen bc;  25
extern pid t gen pid;  26

27

/* Argument parsing */  28
if ( 0 == strcmp ( "-v", argv[1] ) ) { ++verbose; −−argc; ++argv; }  29
if ( 2 != argc ) {  30
fprintf ( stderr, "Usage: %s [-v] directory.\n", argv[0] );  31
exit ( ENO USE );  32
}  33

34

/* Finding the directory and the active file. */  35
actfile = GEN ACTFILE;  36
dir = argv[1];  37
chdir ( dir );  38

39

/* Read the active file. */  40
switch ( envfile ( actfile ) ) {  41
case ENO MEM: ErrEx ( ERR MEM ); break;  42
case ENO FOPEN: ErrEx ( ERR FOPEN ); break;  43
};  44

CHAPTER 8. PID CHECK

45

if ( NULL == gen gen ) { ErrEx ( ERR DATA ); }; /* Sanity Check */  46

47

/* Check if the process is running, by sending SIGNAL 0. */  48
if ( 0 == sigsend ( P PID, gen pid, 0 ) ) {  49
/* Diagnostic messages and exit. */  50
if ( verbose ) printf ( "%s was still running.\n", gen gen );  51
exit ( ENO OK );  52
}  53

54

/* Create the argument vector. */  55
genargv[0] = gen gen;  56
if ( verbose ) printf ( "%s\n", gen flags );  57
if ( NULL != gen flags ) {  58
i = 1;  59
if ( *gen flags != 0 ) genargv[i++] = gen flags;  60
while ( *gen flags != 0 ) {  61
if ( *gen flags == ' ' ) {  62
*(gen flags++) = 0;  63
genargv[i++] = gen flags;  64
};  65
++gen flags;  66
};  67
};  68
genargv[i++] = GEN RESTART;  69
genargv[i] = NULL;  70

71

/* Verbose messages */  72
if ( verbose ) printf ( "Restarting %s\n", gen gen );  73

74

/* Find the backup file for restart. */  75
if ( gen bc == NULL )  76
sprintf ( BackUpFile = BUFbuf, "%s%s", GEN OUTFILE, DEF BCEXT );  77
else BackUpFile = gen bc;  78
sprintf ( BBackUpFile, "%s%s", BackUpFile, DEF BCBCEXT );  79
if ( NULL != ( f = fopen ( BBackUpFile, "r" ) ) ) {  80
fclose ( f );  81
unlink ( BackUpFile );  82
rename ( BBackUpFile, GEN RESTART );  83
} else {  84
rename ( BackUpFile, GEN RESTART );  85
};  86

87

/* Diagnostic messages */  88
printf ( "%s, starting:\n", argv[0] );  89
for ( i = 0; genargv[i] != NULL; )  90
printf ( "%s ", genargv[i++] );  91
putchar ( '\n' );  92

93

execv ( gen gen, genargv ); /* Restart */  94
}  95

96

/* End of pidcheck.c */  97
/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: logenv.h,v 5.0 1998/12/20 00:24:26 georg Exp $ */  2

3

/* The logenv module is primarily used by pidcheck(1). */  4

5

char envenv ( ) ;  6
/* Parse the environment to get the information usually found in the **  7

** active file of gen (1).  */  8
char envfile ( char *f ) ;  9
/* Parse the active file left by gen(1). */  10

11

/* End of logenv.h */  12

/* (C) 1998: Hans Georg Schaathun <georg@ii.uib.no> */  1
/* $Id: logenv.c,v 5.0 1998/12/20 00:24:24 georg Exp $ */  2

3

#include <sys/types.h>  4
#include <stdio.h>  5
#include <stdlib.h>  6
#include <hgd.h>  7

#include "errors.h"  8
#include "gen.h"  9
#include "logenv.h"  10

11

#define FIVE "    "  12
#define ENV SPACE "\0" FIVE FIVE FIVE FIVE  13
#define TAB '\t' 14
#define SPACE ' '  15
#define NEWLINE '\n'  16
#define ENV L CALL STRING L  17

18

char *gen host, *gen arg, *gen gen, *gen cmd, *gen user, *gen bc, *gen flags,  19
*UserName;  20
pid t gen pid;  21

22

char envfile ( char *f ) {  23
FILE *s;  24
static char *e, c;  25
short i;  26

27

if ( NULL == ( s = fopen ( f, "r" ) ) ) return ( ENO FOPEN );  28
i = 0;  29
while ( EOF != ( c = getc ( s ) ) ) {  30
if ( 0 == i ) e = malloc ( ENV L );  31
switch ( c ) {  32
case NEWLINE:  33
e[i] = 0;  34
if ( 0 != putenv ( e ) ) return ( ENO MEM ) ;  35
i = 0;  36
break;  37
default:  38
e[i++] = c;  39
}  40
}  41
envenv ();  42
}  43

44

char envenv ( ) {  45
char *e;  46
UserName = getenv ( "USER" );  47
gen host = getenv ( "GEN_HOST" );  48
gen user = getenv ( "GEN_USER" );  49
gen cmd = getenv ( "GEN_CMD" );  50
gen gen = getenv ( "GEN_GEN" );  51
gen bc = getenv ( "GEN_BC" );  52
gen flags = getenv ( "GEN_FLAGS" );  53
if ( NULL == UserName ) {  54
char s[32];  55

CHAPTER 8. PID CHECK

sprintf ( s, "USER=%s", gen host );  56
putenv ( s );  57
};  58
gen pid = ( NULL == ( e = getenv ( "GEN_PID" ) ) ? −1 : atoi ( e ) ) ;  59
}  60

61

/* End of logenv.c */  62

Index

arglim, 69

bas_comb, 14 bas_copy, 15 bas_init, 14

C_CLOSE, 64 C_QUIT, 64 C_SUB, 64 CleanExit, 58 CoreExit, 58

DefaultSignals, 58 ds_print, 36

envenv, 81 envfile, 81 ErrEx, 49 ErrExDbl, 49 ErrorUsage, 51 eval, 64 execute, 67

fclose, 37 fid_verify, 51 freadline, 50

GetData, 57 getshort, 50 gf_add, 10 gf_inv, 11 gf_mult, 10

intcmd, 69

MailNote, 50 main, 53, 61, 73, 74, 76, 79 max, 64 mp, 64 msp_init, 15 msp_print, 16 msp_subset, 16 mval_alloc, 36 mval_print, 36

n, 64 nt_init, 47 nt_line, 47 nt_lookup, 48 nt_pdef, 48 nt_sdef, 48

p, 64 parse, 67 pd, 64 pg_alloc, 9 pg_auxget, 18 pg_brack, 10 pg_create, 21 pg_del, 8 pg_dimprint, 10 pg_dump, 23 pg_get, 18 pg_igs, 9 pg_load, 8 pg_pprint, 19 pg_print, 19 pg_space, 20 pg_sprint, 20 pg_ssprint, 17, 19 pg_subprint, 17, 19 pg_supprint, 17, 19 PrintHelp, 50 PrintVersion, 50 pt_add, 12 pt_fromno, 12 pt_fromstr, 13 pt_getno, 12 pt_init, 13 pt_mult, 12 pt_noprint, 13 pt_norm, 13 pt_nov, 12 \underline{INDEX}

pt_print, 13 pt_qpow, 13 pt_vno, 12 ptq_alloc, 23 ptq_extract, 24 ptq_reinit, 23 ptq_rmset, 23 pv_fixcount, 44 pv_init, 44 pv_print, 44 pv_printall, 43 pv_sprint, 43 pv_ssprint, 44 pv_subprint, 44 pv_supprint, 44

qp, 64

s_del, 17 s_init, 17 s_print, 18 sd, 64 sh, 64 sig_statusreport, 58 SignalHandling, 58 source, 67 spd, 64 stk_del, 40 stk_init, 40 stk_push, 35 stk_replace, 35 strcmd, 69 subp, 64

tee_func, 51

v_alloc, 33 v_classprint, 34 v_compare, 34 v_dump, 34 v_load, 34 v_valprint, 34 val_allocfor, 27 val_assign, 42 val_auxchain, 32 val_chained, 32 val_clear, 29 val_del, 29 val_ds, 30 val_dump, 28 val_fixdump, 33 val_fixload, 33 val_freev, 28 val_getclass, 30 val_incprobe, 46 val_load, 28 val_nullsums, 31 val_spaceval, 45 val_statusreport, 32 val_stepclass, 32 val_stepinit, 29 val_stepval, 30 val_sumval, 31 ver, 64 veval, 64 vt_del, 39 vt_dump, 39 vt_finfo, 38 vt_init, 37 vt_insert, 37 vt_load, 38 vt_printbyclass, 38 vt_readbackup, 39 vt_walkbackup, 39 vt_walkprintbyclass, 38