/* quine_mcclusky.c 
         digital circuit minimization
         input: boolean equation or truth table or minterms
         output: prime implicants and equation

   build:   bison calc_eqn.y
            gcc -o qm quine_mcclusky.c calc_eqn.tab.c -lm

   run:     qm -n 4 -m -i minterms4.dat > minterms4.out


 Copyright (C) 2002 Free Software Foundation, Inc.
 qm is free software;  you can redistribute it and/or modify it under 
 terms of the GNU General Public License as published  by the Free
 Software Foundation; either version 2, or (at your option) any later
 version.  qm is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY;  without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 General Public License for more details. You should have received a
 copy of the GNU General Public License distributed with qm;
 see file COPYING. If not, write to the Free Software Foundation,
 59 Temple Place - Suite 330,  Boston, MA 02111-1307, USA.                             */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

static void usage(); /* command line usage */
static void  readtt(unsigned char *gt, int ng, int *gti, FILE *infile);
static void readeqn(unsigned char *gt, int ng, int *gti, FILE *infile);
static void readmin(unsigned char *gt, int ng, int *gti, FILE *infile);
static void printgt(unsigned char *gt, int ng, int gti);
static void countgt(unsigned char *gt, int ng, int gti);
static void  sortgt(unsigned char *gt, int ng, int *gti);  
static void printvhdl(unsigned char *pi, int ng, int pii, FILE *outfile);
static void printveri(unsigned char *pi, int ng, int pii, FILE *outfile);
static void heapsort( void *base, int nmemb, int size,
                      int (*compar)(void *, void *) );

extern int yyparse(void);    /* provided in  calc_eqn.tab.c  file     */
int regs[26];                /* load with possible minterm            */
char line[32767];            /* load with Verilog equation, translate */
int eqn_result;              /* returned value of equation at minterm */
int line_index;              /* zero before each call to yyparse      */

int main(int argc, char *argv[])
{
  int i;              /* index into argv, etc */
  int j;              /* general counter */
  int k;              /* general counter */
  int m;              /* bit position */
  int n=0;            /* number of variables */
  int tt=0;           /* truth table input */
  int eqn=0;          /* equation input */
  int mint=0;         /* minterm input */
  int debug=0;        /* debug print flag */
  char inname[128];   /* input file name */
  FILE *infile;       /* input file handle */
  char outname[128];  /* output file name */
  FILE *outfile;      /* output file handle */
  int ng;             /* size of gt entry, group+n+cov */
  int n2n;            /* 2^n */
  int room;           /* ng*ng*n2n */
  unsigned char *gt;  /* group table */
  unsigned char *gtn; /* group table next */
  int gti;            /* group table index */
  int gtni;           /* group table next index */
  unsigned char *pi;  /* prime implicant table */
  int pii=0;          /* prime implicant index */
  int gix[25];        /* index of group start */
  int gixn;           /* number of group start */
  int gixc;           /* group ones count */
  int diffcnt;        /* number of bits different */
  int prev;           /* pervious term used */
  unsigned char gtdiff[24]; /* difference term with '-' */

  printf("Quine McClusky digital circuit minimization V1.0\n");

  /* initialize */
  inname[0]='\0';
  outname[0]='\0';

  /* read options */

  if(argc < 2) usage();
  /* collect [options] */
  for( i=1; i<argc; i++){
    if( !strcmp("--help", argv[i]) || !strcmp("-h", argv[i])){
      usage();
    }
    if( !strcmp("-n", argv[i]) || !strcmp("-n", argv[i])){
      if( ++i>=argc) usage();
      n = atoi(argv[i]);
      continue;
    }
    if( !strcmp("-input", argv[i]) || !strcmp("-i", argv[i])){
      if( ++i>=argc) usage();
      strcpy(inname, argv[i]);
      continue;
    }
    if( !strcmp("-output", argv[i]) || !strcmp("-o", argv[i])){
      if( ++i>=argc) usage();
      strcpy(outname, argv[i]);
      continue;
    }
    if( !strcmp("-tt", argv[i]) || !strcmp("-t", argv[i])){
      tt++;
      continue;
    }
    if( !strcmp("-eqn", argv[i]) || !strcmp("-e", argv[i])){
      eqn++;
      continue;
    }
    if( !strcmp("-min", argv[i]) || !strcmp("-m", argv[i])){
      mint++;
      continue;
    }
    if( !strcmp("-debug", argv[i]) || !strcmp("-d", argv[i])){
      debug++;
      continue;
    }
    usage();
  } /* end of read options */

  /* error checking: n, one type, input file */
  if(n<2 || n>24) {printf("n=%d, out of range 2..24 \n", n); exit(0);}
  if(inname[0]=='\0') {printf("-i <input file name> required \n"); exit(0);}
  infile=fopen(inname, "r");
  if(infile==NULL) {printf("could not open input file %s \n", inname); exit(0);}
  if((tt+eqn+mint)!=1) {printf("select one input file type \n"); exit(0);}
  outfile=stdout;
  if(outname[0]!='\0'){
    outfile=fopen(outname, "w");
    if(outfile==NULL) {printf("could not open output file %s \n", outname);
                       exit(0);}
  }

  ng=n+2;
  n2n=pow(2,n);
  room=ng*ng*n2n;
  if(debug)
    printf("asking for three %d byte arrays, %d rows \n", room, ng*n2n);
  gt= (unsigned char *)malloc(room);
  if(gt==NULL) {printf("malloc failed on gt, exiting.\n"); exit(1);}
  gtn=(unsigned char *)malloc(room);
  if(gtn==NULL) {printf("malloc failed on gtn, exiting.\n"); exit(1);}
  pi=(unsigned char *)malloc(room);
  if(pi==NULL) {printf("malloc failed on pi, exiting.\n"); exit(1);}

  /* get minterms */
  if(tt)    readtt(gt, ng, &gti, infile);
  if(eqn)  readeqn(gt, ng, &gti, infile);
  if(mint) readmin(gt, ng, &gti, infile);
  if(debug||tt||eqn) {printf("initial minterms \n"); printgt(gt, ng, gti);}

  /* start reduction loop */
reduce:
  /* count 1's in minterms, general, include "-" */
  countgt(gt, ng, gti);
  if(debug) {printf("count ones \n"); printgt(gt, ng, gti);}

  /* sort minterms */
  sortgt(gt, ng, &gti);  
  if(debug) {printf("sorted in groups \n"); printgt(gt, ng, gti);}

  /* construct next table, start finalized if none combined */
  gixn=0;
  gix[0]=0;
  gixc=gt[0];
  gt[gti*ng]=-1;
  for(j=1; j<gti+1; j++){
    if(gt[j*ng]!=gixc){
      gixc=gt[j*ng];
      gixn++;
      gix[gixn]=j;
    }
  }
  if(debug){
    for(i=0; i<gixn+1; i++) printf("gix[%d]=%d \n", i, gix[i]);
    printf("\n");
  }

  gtni=0;    /* for putting combined entry into gtn, stop if zero */
  for(k=0; k<gixn-1; k++){
    for(i=gix[k]; i<gix[k+1]; i++){
      for(j=gix[k+1]; j<gix[k+2]; j++){
	  /* compare gt[i*ng row] to gt[j*ng row] differ in one bit (not '-')
             promote to gtn and mark both covered */
	diffcnt=0;
        for(m=1; m<ng-1; m++){
	  gtdiff[m]=gt[i*ng+m];
	  if(gt[i*ng+m]!=gt[j*ng+m]) {diffcnt++; gtdiff[m]='-';}
	}
        if(diffcnt==1){
	  gt[i*ng+ng-1]=1; /* mark covered */
	  gt[j*ng+ng-1]=1;
          for(m=1; m<ng-1; m++){
	    gtn[gtni*ng+m]=gtdiff[m];
          }
	  gtn[gtni*ng]=0;
	  gtn[gtni*ng+ng-1]=0;
          gtni++;
	}
      }
    }
  }
  if(gtni>room) {printf("exceeded internal storage gtni=%d\n",gtni); exit(1);}
  if(debug) {printf("gt groups covered \n"); printgt(gt, ng, gti);}
  if(debug) {printf("gtn groups \n"); printgt(gtn, ng, gtni);}
  
  /* save not covered into prime implicant table */
  for(j=0; j<gti; j++){
    if(gt[j*ng+ng-1]==0){
      for(m=1; m<ng; m++) pi[pii*ng+m]=gt[j*ng+m];
      pi[pii*ng]=0;
      pii++;
    }
  }
  if(pii>room) {printf("exceeded internal storage pii=%d\n",pii); exit(1);}
  if(debug) {printf("prime implicants \n"); printgt(pi, ng, pii);}

  /* copy combined into minterms table gtn into gt*/
  for(j=0; j<gtni; j++){
    for(i=1; i<ng-1; i++) gt[j*ng+i]=gtn[j*ng+i];
    gt[j*ng]=0;
    gt[j*ng+ng-1]=0;
  }
  gti=gtni;
  /* loop to start reduction loop */
  if(gtni>0) goto reduce;

  /* start finalize */
  /* print final prime implicants */
  if(debug) {printf("raw pi \n"); printgt(pi, ng, pii);}
  sortgt(pi, ng, &pii);

  printf("final prime implicants \n");
  printgt(pi, ng, pii);

  /* output VHDL statement */
  printvhdl(pi, ng, pii, outfile);

  /* output Verilog statement */
  printveri(pi, ng, pii, outfile);


  return 0;
}


static void usage(){
  printf("usage: qm [options] \n");
  printf("  [options]  can be: \n");
  printf("  -n       or -n  <number of variables>  \n");
  printf("  -input   or -i  <input file name> \n");
  printf("  -output  or -o  <output file name> \n");
  printf("  -tt      or -t   (truth table input) \n");
  printf("  -eqn     or -e   (equation input) \n");
  printf("  -min     or -m   (minterm input) \n");
  printf("  -debug   or -d   (print each stage, debug) \n");
  printf("  -help    or -h   (gets this output) \n");
  exit(0); /* program ends, user invokes again with improved command line */
} /* end usage */

/* read an input file of truth table into a gt table */
static void  readtt(unsigned char *gt, int ng, int *gti, FILE *infile)
{
  int i;
  int j=0;
  int k=0;
  int count=0;
  char mark=0;
  char line[256];
  int debug=0;

  fgets(line, 256, infile);
  if(debug) printf("readtt %s\n", line);
  if(line[0]!='\0') sscanf(line, " %c ", &mark);
                                      /* skip lines not starting 0 or 1 */
  while(!(mark=='0'||mark=='1')){
    fgets(line, 256, infile);
    if(debug) printf("readtt %s\n", line);
    if(line[0]!='\0') sscanf(line, " %c ", &mark); 
  }

  gt[j*ng]=0;
  for(i=1; i<ng-1; i++){
    /* sscanf(line, " %c ", &gt[j*ng+i]); */
    while(!(line[k]=='0'||line[k]=='1')&&k<254){
      k++;
    }
    gt[j*ng+i]=line[k];
    k++;
    if(debug) printf("readtt %c\n", gt[j*ng+i]);
    count++;
  }
  /* sscanf(line, " %c ", &mark); skip any mark and get output bit */ 
  while(!(line[k]=='0'||line[k]=='1')&&k<254){
    k++;
  }
  mark=line[k];
  if(debug) printf("readtt %c\n", mark);
  gt[j*ng+ng-1]=0;
  if(mark=='1') j++; /* skip truth table entries that are zero */
  else          count=count-(ng-2);
  if(debug) printf("j=%d, count=%d\n", j, count);

  while(!feof(infile)){ /* after first line */
    gt[j*ng]=0;
    for(i=1; i<ng-1; i++){
      fscanf(infile, " %c ", &gt[j*ng+i]); 
      if(debug) printf("readtt %c\n", gt[j*ng+i]);
      if(!(gt[j*ng+i]=='0'||gt[j*ng+i]=='1')){
	printf("bad character in input file, not 0 or 1, exiting.\n");
        exit(1);
      }
      count++;
    }
    fscanf(infile, " %c ", &mark); /* skip any mark and get output bit */ 
    if(debug) printf("readtt %c\n", mark);
    while(!(mark=='0'||mark=='1')){
      fscanf(infile, " %c ", &mark); 
      if(debug) printf("readtt %c\n", mark);
    }
    gt[j*ng+ng-1]=0;
    if(mark=='1') j++; /* skip truth table entries that are zero */
    else          count=count-(ng-2);
    if(debug) printf("j=%d, count=%d\n", j, count);
  }
  *gti=j;
  gt[j*ng]=0;
  if((count%j)!=0){
    printf("bad number of 1's and 0's in input file, exiting.\n");
    printf("readtt read %d minterms, %d total characters\n", j, count);
  }
} /* end readtt */

/* read an input file, equation, into a gt table */
static void readeqn(unsigned char *gt, int ng, int *gti, FILE *infile)
{
  int i;
  int j;
  int k;
  int m;
  int n2n;
  int n;
  int debug=0;
  int gtn=0;   /* will become gti upon exit */
  int reject;  /* parse error */

  n=ng-2;
  n2n=pow(2,n);
  /* read equation from file */
  i=0;
  while(!feof(infile)){ /* read equation */
    line[i]=fgetc(infile);
    if(line[i]==EOF){
      line[i]='\0';
      break;
    }
    if(line[i]=='\0') continue;
    if(line[i]=='\n') continue;
    if(line[i]==' ') continue;
    if(line[i]=='\t') continue;
    i++;
  }
  line[i]='\0';

  /* lex the string to just the equation in "Verilog" form */
  if(debug) printf("raw line=%s\n",line);
  i=0;
  j=0;
  while(line[i]!='\0'){
    if(line[i]=='=') break;
    i++;
  }
  if(line[i]=='\0') { printf("no equal sign in equation, exiting\n"); exit(1);}
  while(line[i]!='\0'){
    i++;
    if(line[i]==' ') continue;
    if((line[i]  =='o'||line[i]  =='O')&&
       (line[i+1]=='r'||line[i+1]=='R')){
      i++;
      line[i]='|';
    }
    if((line[i]  =='a'||line[i]  =='A')&&
       (line[i+1]=='n'||line[i+1]=='N')&&
       (line[i+2]=='d'||line[i+2]=='D')){
      i++;
      i++;
      line[i]='&';
    }
    if((line[i]  =='n'||line[i]  =='N')&&
       (line[i+1]=='o'||line[i+1]=='O')&&
       (line[i+2]=='t'||line[i+2]=='T')){
      i++;
      i++;
      line[i]='~';
    }
    if((line[i]  =='x'||line[i]  =='X')&&
       (line[i+1]=='o'||line[i+1]=='O')&&
       (line[i+2]=='r'||line[i+2]=='R')){
      i++;
      i++;
      line[i]='^';
    }
    line[j]=line[i];
    j++;
  }
  line[j]='\0';
  if(debug) printf("lex'd line=%s\n",line);

  for(i=0; i<n2n; i++)
  {
    k=i;
    for(j=0; j<n; j++){ /* set up min term */
      regs[n-j-1]=0;
      if(k%2==1) regs[n-j-1]=1;
      k=k/2;
    }
    if(debug) printf("evaluating for %d %d %d %d \n", regs[0], regs[1], regs[2], regs[3]);
    line_index=0;
    reject = yyparse();
    if(reject)
    {
      printf("bad equation, parsing failed, exiting \n");
      exit(1);
    }
    else
    {
      if(debug) printf("minterm computed eqn_result=%d \n", eqn_result);
      if(eqn_result){
        gt[gtn*ng]=0;
        gt[gtn*ng+ng-1]=0;
        for(m=1; m<ng-1; m++)
        {
          gt[gtn*ng+m]=regs[m-1]+'0';
        }
        gtn++;
      }
    }
  }
  *gti=gtn;
} /* end readeqn */

/* read an input file of minterms into a gt table */
static void readmin(unsigned char *gt, int ng, int *gti, FILE *infile)
{
  int i;
  int j=0;
  int count=0;

  while(!feof(infile)){
    gt[j*ng]=0;
    for(i=1; i<ng-1; i++){
      fscanf(infile, " %c ", &gt[j*ng+i]); 
      if(!(gt[j*ng+i]=='0'||gt[j*ng+i]=='1'||gt[j*ng+i]=='-')){
	printf("bad character in input file, not 0, 1 or - , exiting.\n");
        exit(1);
      }
      count++;
    }
    gt[j*ng+ng-1]=0;
    j++;
  }
  *gti=j;
  gt[j*ng]=0;
  if((count%j)!=0){
    printf("bad number of 1's and 0's in input file, exiting.\n");
    printf("readmin read %d minterms, %d total characters\n", j, count);
  }
} /* readmin */

/* print a standard format gt table */
static void printgt(unsigned char *gt, int ng, int gti)
{
  int i;
  int j;
  printf("gr ");
  for(i=1; i<ng-1; i++){
    printf("%c ",'a'+i-1);
  }
  printf(" cv \n");

  for(j=0; j<gti; j++){
    printf("%d  ", gt[j*ng]);
    for(i=1; i<ng-1; i++){
      printf("%c ", gt[j*ng+i]);
    }
    printf(" %d \n", gt[j*ng+ng-1]);
  }
  printf("\n");
} /* end printgt */

/* countgt  count and fill in number of 1's in a gt table */
static void countgt(unsigned char *gt, int ng, int gti)
{
  int i;
  int j;

  for(j=0; j<gti; j++){
    gt[j*ng]=0;
    for(i=1; i<ng-1; i++){
      if(gt[j*ng+i]=='1') gt[j*ng]++;
    }
  }
} /* end countgt */

/* compare function needed by sortgt, used by heapsort */
static int compar(void * elem1, void * elem2)
{
    if(strcmp(elem1,elem2)>0) return 1;
    return 0;
} /* end compar */

/* sortgt  sort and compress out duplicates from a gt format table */
static void  sortgt(unsigned char *gt, int ng, int *gti)
{
  int j;
  int offs=0;
  int m;
  int ok;

  /* printf("enter sortgt with ng=%d, gti=%d\n", ng, *gti); */
  heapsort (gt, *gti, ng, compar);
  /* remove duplicates */
  j=0;
  while(j+offs<*gti){
    ok=0;
    for(m=1; m<ng-1; m++){
	if(gt[j*ng+m]!=gt[(j+1)*ng+m]) {ok=1; break;}
    }
    if(!ok)offs++;
    else j++;
    if(offs>0){
      for(m=0; m<ng; m++) gt[(j+1)*ng+m]=gt[(j+1+offs)*ng+m]; 
    }
  }
  *gti=*gti-offs;
  /* printf("leave sortgt with offs=%d, gti=%d\n", offs, *gti); */
} /* end sortgt */

/* printvhdl  print a VHDL concurrent signal statement */
static void printvhdl(unsigned char *pi, int ng, int pii, FILE * outfile)
{
  int j;
  int m;
  int prev;

  fprintf(outfile, "out <= \n");
  for(j=0; j<pii; j++){
    prev=0;
    if(pi[j*ng+1]=='-')       fprintf(outfile, "  (      ");
    else if(pi[j*ng+1]=='1') {fprintf(outfile, "  (    %c ", 'a'); prev=1;}
    else                     {fprintf(outfile, "  (not %c ", 'a'); prev=1;}
    for(m=2; m<ng-1; m++){
      if(pi[j*ng+m]=='-'){
        fprintf(outfile, "          ");
      }
      else if(pi[j*ng+m]=='1'){
        if(prev) fprintf(outfile, "and     %c ", 'a'+m-1);
        else     fprintf(outfile, "        %c ", 'a'+m-1);
        prev=1;
      }
      else{
        if(prev) fprintf(outfile, "and not %c ", 'a'+m-1);
        else     fprintf(outfile, "    not %c ", 'a'+m-1);
        prev=1;
      }
    }
    if(j==pii-1) fprintf(outfile, ");\n");
    else         fprintf(outfile, ") or\n");
  }
  fprintf(outfile, "\n");
} /* end printvhdl */

/* printveri  print a Verilog behavioral statement */
static void printveri(unsigned char *pi, int ng, int pii, FILE * outfile)
{
  int j;
  int m;
  int prev;

  fprintf(outfile, "out = \n");
  for(j=0; j<pii; j++){
    prev=0;
    if(pi[j*ng+1]=='-')       fprintf(outfile, "  (   ");
    else if(pi[j*ng+1]=='1') {fprintf(outfile, "  ( %c ", 'a'); prev=1;}
    else                     {fprintf(outfile, "  (~%c ", 'a'); prev=1;}
    for(m=2; m<ng-1; m++){
      if(pi[j*ng+m]=='-'){
        fprintf(outfile, "     ");
      }
      else if(pi[j*ng+m]=='1'){
        if(prev) fprintf(outfile, "&  %c ", 'a'+m-1);
        else     fprintf(outfile, "   %c ", 'a'+m-1);
        prev=1;
      }
      else{
        if(prev) fprintf(outfile, "& ~%c ", 'a'+m-1);
        else     fprintf(outfile, "  ~%c ", 'a'+m-1);
        prev=1;
      }
    }
    if(j==pii-1) fprintf(outfile, ");\n");
    else         fprintf(outfile, ") |\n");
  }
  fprintf(outfile, "\n");
} /* end printveri */


/* heapsort            a fast  n log2 n  sort              */
/*                     user provides a comparison function */
/* heapsort code, starting with a function prototype of a utility routine */
static void remake_heap (char *array_val, int parent_index ,int last_index, 
                         int (*compar)(void *, void *),
                         void *item_temp, int size);

void heapsort ( void *base, int nmemb, int size, int (*compar)(void *, void *)){
    char *array_val = (void *)base;
    int last_parent_pos = ( nmemb - 2 ) / 2;     
    int last_parent_index = last_parent_pos;
    char *item_temp = (void *)malloc(size*sizeof(char));
    int index_val;

    /* heapsort main code */
    if(nmemb <= 1) return;

    for(index_val=last_parent_index;index_val>=0;index_val--)
        remake_heap( array_val, index_val, nmemb-1, compar, item_temp, size );

    memcpy(item_temp,array_val,size); 
    memcpy(array_val,&array_val[(nmemb-1)*size],size);
    memcpy(&array_val[(nmemb-1)*size],item_temp,size);
    for(index_val=nmemb-2;index_val>0;index_val--){
      remake_heap( array_val, 0, index_val, compar, item_temp, size );
      memcpy(item_temp,array_val,size); 
      memcpy(array_val,&array_val[index_val*size],size);
      memcpy(&array_val[index_val*size],item_temp,size);
    }
} /* end heapsort */

static void remake_heap (char *array_val, int parent_index ,int last_index, 
                         int (*compar)(void *, void *),
                         void *item_temp, int size) {
      int last_parent_pos = ( last_index - 1 ) / 2;     
      int last_parent_index = last_parent_pos;
      int l_child;
      int r_child;
      int max_child_index;
      int parent_temp = parent_index;

      /* code for remake_heap */
      for(;;){
        if( parent_temp > last_parent_index ) break;
        l_child = parent_temp * 2 + 1;
        if( l_child == last_index) {
          max_child_index = l_child;
        }
        else {
          r_child = l_child+1;
          if((*compar)(&array_val[l_child*size],&array_val[r_child*size])>0) {
            max_child_index = l_child;
          }
          else {
            max_child_index = r_child;
          }
        }
        if((*compar)(&array_val[max_child_index*size],
                  &array_val[parent_temp*size])>0) {
          memcpy(item_temp,&array_val[max_child_index*size],size); 
          memcpy(&array_val[max_child_index*size],&array_val[parent_temp*size]
                  ,size);
          memcpy(&array_val[parent_temp*size],item_temp,size);
          parent_temp = max_child_index;
        }
        else {
          break;
        }
      }
} /* end remake_heap */