#include <stdlib.h>
#include <stdio.h>
#include <time.h>


// I've written a little parser to read in a multilinear boolean polynomial f
// i.e. just a sum of monomials with no coefficients, degree 1 in each variable,
// ending with EOF or ; e.g. x1+x2*x3+x2*x4*x5+1;  or  y3*y4+y1+y2;
// Variables have to start with one letter and be numbered from 1 not 0.
// The parser skips spaces and new lines.
// Text following a # character is ignored
//
// The main program then factors f over F2 and prints out the factors.
//
// Compile using
//    cc -O3 -c MULMOD10.c
//    cc -O3 -o facpoly MULMOD10.o facpoly.c
//
// Unix command line usage is   facpoly n file   
// where n is the number of variables and file is a text file.
//
// Example if the file foo contains
//    x1*x3*x4+x2*x3*x4+x1*x3+x1*x4+x2*x3
//    +x2*x4+x3*x4+x3+x4;
// then
//    ./facpoly 4 foo
// outputs
//   f1 := x1+x2+1;
//   f2 := x3*x4+x3+x4;
//
// Note, the monomial content is returned as a single factor.
// Example if the file foo contains
//   x2*x1*x3+x2*x3*x4;
// the monomial content is x2*x3 and the output is
//   f1 := x4+x1;
//   f2 := x2*x3;
//
// Author Michael Monagan 2024
// Copyright Michael Monagan 2024.


#define ULONG unsigned long
#define DEBUGgetsym 0
        

typedef struct poly {
    int n;  // number of variables
    int t;  // number of terms
    ULONG *terms; // bit vector
} poly;


typedef struct listpoly {
    poly * f;
    struct listpoly *next;
} listpoly;


ULONG *array64u( int n );
poly *newpoly(int n, int t);
void setbit(int x, ULONG *X);
int termsize(int n);
poly *resizepoly(poly *f, int s);
void printpoly( poly *f, char x );
void sortpoly(poly* f);
listpoly* facpoly( poly *f );


int isletter( char c ) { return( c>='a' && c<='z' || c>='A' && c<='Z' ); }
int isnumber( char c ) { return( c>='0' && c<='9' ); }

char lastch; // last character read
int symbol; // last symbol parsed
char variable; // main variable
#define MAXSIZE 1024
char buffer[MAXSIZE]; // for fgets
int bindex; // index into buffer

char fgetchar(FILE *fp) {
    char c;
    extern char buffer[];
    extern int bindex;
    if( bindex==MAXSIZE-1 || buffer[bindex]==0  ) {
        if( fgets(buffer,MAXSIZE,fp) == NULL ) return EOF;
        bindex = 0;
    }
    if( buffer[bindex]==EOF ) return EOF;
    c = buffer[bindex];
    bindex ++;
    if( c=='#' ) {
        //printf("#%c\n",buffer[bindex]);
        while( buffer[bindex]!=EOF && buffer[bindex]!='\n' ) {
           bindex ++;
           if( bindex==MAXSIZE-1 ) {
              if( fgets(buffer,MAXSIZE,fp) == NULL ) return EOF;
              bindex = 0;
           }
        }
        if( buffer[bindex]==EOF ) return EOF;
        bindex ++;
        return fgetchar( fp );
    }
    return c;
}

void readinit(FILE *fp) {
// initialize the state for reading from the file
    extern int bindex;
    extern char lastch;
    bindex = MAXSIZE-1; // to cause a first read from the file
    lastch = fgetchar(fp); // read the first character
}

void generror(FILE *fp, char * s) {
    extern char lastch;
    printf("generror: expecting %s but got %c\n",s,lastch);
    fclose(fp);
    exit(1);
}

#define PLUS -1
#define STAR -2
#define ONE -3
#define STOP 0

int getsym( FILE *fp ) {
// Read the next symbol from the file.
// It must be one of the integer 1, a variable, +, *, \n, ; or EOF.
// The return value is an econding of these.
// If the integer 1 return ONE, if + return PLUS, if * return STAR, if ; or EOF return STOP
// If it is a variable e.g. x123 return the integer 123
    extern char lastch;
    extern int symbol;
    int n;
    while( lastch==' ' || lastch=='\n' ) lastch = fgetchar(fp); // skip over blanks and newlines
    if( lastch==EOF || lastch==';' ) { symbol = STOP; return STOP; }
    if( lastch=='1') { lastch = fgetchar(fp); symbol = ONE; return ONE; }
    if( lastch=='+') { lastch = fgetchar(fp); symbol = PLUS; return PLUS; }
    if( lastch=='*') { lastch = fgetchar(fp); symbol = STAR; return STAR; }
    if( isletter(lastch) ) {
        if( variable=='0' ) variable = lastch;
        if( lastch!=variable ) generror(fp,"unexpected variable");
        lastch = fgetchar(fp);
        if( lastch<'1' || lastch>'9' ) generror(fp,"1-9");
        n = lastch-'0';
        lastch = fgetchar(fp);
        while( isnumber(lastch) ) { n = 10*n+lastch-'0'; lastch = fgetchar(fp); }
        //printf("getsym: var=x%d lastch=%c\n",n,lastch);
        symbol = n; return n;
    }
    printf("getsym: unexpected character %c\n",lastch);
    fclose(fp);
    exit(1);
}
    
void readterm(FILE *fp, int n, ULONG *X)
// read a term (monomial) and store it in the bit vector X of length n
// e.g. if n=5 and x1*x3*x4 is read then X[0] = 13 = 1+4+8
{
    extern int symbol;
    int y,i,q,m;

    m = termsize(n);
    for( i=0; i<m; i++ ) X[i] = 0; // zero it out
    
    y = getsym(fp);
    if( !(y==ONE || y>0) ) { generror(fp,"expecting a term"); exit(1); }
    if( y>n ) { printf("variable out of range %c%d\n",variable,y); fclose(fp); exit(1); }
    if( DEBUGgetsym ) if( y==ONE ) printf("1"); else printf("x%d",y);
    if( y>0 ) setbit(y-1,X);

    y = getsym(fp);
    while( y==STAR ) {
        if( DEBUGgetsym ) printf("*");
        y = getsym(fp);
        if( !(y==ONE || y>0) ) { printf("expecting a term %d\n",y); exit(1); }
        if( DEBUGgetsym ) if( y==ONE ) printf("1"); else printf("x%d",y);
        if( y>n ) { printf("variable out of range %c%d\n",variable,y); fclose(fp); exit(1); }
        if( y>0 ) setbit(y-1,X);
        y = getsym(fp);
    }
    return;
}
 

poly * readpoly(FILE *fp,int n) {
    extern int symbol;
    extern char variable;
    poly *f;
    ULONG *A;
    int k,t,m;
    f = newpoly(n,1);
    A = f->terms;
    m = termsize(n);
    t = 1;
    readterm(fp,n,A);
    for( k=1; symbol==PLUS; k++ ) {
        if( DEBUGgetsym ) printf("\n");
        if( DEBUGgetsym ) printf("+");
        if( k==t ) { t = 2*t; f = resizepoly(f,t); A = f->terms; }
        readterm(fp,n,A+k*m);
    }
    if( symbol!=STOP ) generror(fp,"EOF");
    f->t = k;
    if( DEBUGgetsym ) printf(";\n");
    sortpoly(f);
    return f;
}
    

int main(int argc, char*argv[])
{
    extern ULONG seed;
    extern ULONG mult;
    extern ULONG counter;
    extern char variable;
    int k,numvars;
    clock_t st,tt;

    seed = 1;
    mult = 6364136223846793003lu;

    if( argc!=3 ) { printf("variable count and file name required\n"); exit(1); }

    sscanf(argv[1],"%d",&numvars);

    char *filename = argv[2];
    FILE *fp = fopen(filename, "r");
    if (fp == NULL)
    {
        printf("Error: could not open file %s", filename);
        exit(1);
    }

    printf("n=%d file=%s\n",numvars,argv[2]);

    variable = '0';
    readinit(fp);
    poly *f = readpoly(fp,numvars);
    printf("#f = %d\n",f->t);

    counter = 0;
    st = clock();
    listpoly *F = facpoly(f);
    tt = clock();

    printf("time = %8.3fs\n",(tt-st)/1000000.0);

    for( k=1; F!=NULL; k++ ) {
        printf("f%d := ",k);
        printpoly(F->f,variable);
        F = F->next;
    }

    fclose(fp); // close the file
    return 0;
}