
/***********************************************************************


        Copyright (C) 1991,
        Virginia Polytechnic Institute & State University


        This program was originally written by Mr. Hyung K. Lee
        under the supervision of Dr. Dong S. Ha, in the Bradley
        Department of Electrical Engineering, VPI&SU, in 1991.

        This program is released for research use only. This program,
        or any derivative thereof, may not be reproduced nor used
        for any commercial product without the written permission
        of the authors.

        For detailed information, please contact to

        Dr. Dong S. Ha
        Bradley Department of Electrical Engineering
        Virginia Polytechnic Institute & State University
        Blacksburg, VA 24061

        Ph.: (540) 231-4942
        Fax: (540) 231-3362
        E-Mail: ha@vt.edu
        Web: http://www.ee.vt.edu/ha

***********************************************************************/

/**************************** HISTORY **********************************

	atalanta, fsim and soprano: version 1.1

	Original: H. K. Lee, 10/5/1992

       
        Updated:Changed output display, M. Chan, 3/8/1996 
		Added flexiblities on reading cct name, M. Chan, 4/10/1996 

***********************************************************************/

/*----------------------------------------------------------------- 
	filename read_cct.c
	Reads a netlist file written in ISCAS89 benchmark netlist
        format.

	list all modifications below:
	original:  10/5/1992	Hyung K. Lee   compiled and checked
-------------------------------------------------------------------*/
#include <stdio.h>
#include "atpg.h"

#define EOS '\0'

extern void fatalerror(), exit();
extern void InitHash();
extern HASHPTR FindHash(), Find_and_Insert_Hash();
extern HASHPTR InsertHash();

HASHPTR symbol_tbl[HASHSIZE];
int *flip_flops;
int maxfout=0;
GATEPTR begnet=(GATEPTR)NULL;

#define NOT_ALLOCATED (-1)	/* index of non-allocated gate */
#define is_white_space(c) (c==' ' || c=='\n'|| c=='\t')
#define is_delimiter(c) (c=='=' || c==',' || c=='(' || c==')')
#define is_valid(c) ((c>='0' && c<='9') || \
		     (c>='A' && c<='Z') || \
		     (c>='a' && c<='z') || \
		     (c=='_') || \
		     (c=='.'))
#define is_comment(c) (c=='#')

/*------getsymbol--------------------------------------------------
	reads next symbol from the given circuit file
	inputs : file	the name of input file
	outputs: s	symbol string output
		 returns delimiter following symbol
		 =   gate name
		 (   gate type
		 ,   input signal --- will be continued
		 )   input --- end of input
-------------------------------------------------------------------*/
char getsymbol(file,s)
FILE *file; char s[];
{
   char c;
   int n=0;
   int comm=0;

   while((c=getc(file))!=EOF) {
      if(is_comment(c)) { comm=1; continue; }
      if(comm==1) {
         if(c=='\n') comm=0;
         continue;
      }
      if(is_white_space(c)) continue;
      if(is_delimiter(c)) break;
      if(is_valid(c)) s[n++]=c;
      else fatalerror(CIRCUITERROR);
   }
   s[n]=EOS;
   return(c);
}

/*------gatetype: returns type of the gate symbol------*/
int gatetype(symbol)
char *symbol;
{
   int fn;

   if(strcmp(symbol,"NOT") == 0) fn=NAND;
   else if(strcmp(symbol,"AND") == 0) fn=AND;
   else if(strcmp(symbol,"NAND") == 0) fn=NAND;
   else if(strcmp(symbol,"OR")== 0) fn=OR;
   else if(strcmp(symbol,"NOR") == 0) fn=NOR;
   else if(strcmp(symbol,"DFF") == 0) fn=DFF;
   else if(strcmp(symbol,"XOR") == 0) fn=XOR;
   else if(strcmp(symbol,"XNOR") == 0) fn=XNOR;
   else if(strcmp(symbol,"BUFF") == 0) fn=AND;
   else if(strcmp(symbol,"BUF") == 0) fn=AND;
   else if(strcmp(symbol,"INPUT") == 0) fn=PI;
   else if(strcmp(symbol,"OUTPUT") == 0) fn=PO;
   else if(strcmp(symbol,"not") == 0) fn=NAND;
   else if(strcmp(symbol,"and") == 0) fn=AND;
   else if(strcmp(symbol,"nand") == 0) fn=NAND;
   else if(strcmp(symbol,"or")== 0) fn=OR;
   else if(strcmp(symbol,"nor") == 0) fn=NOR;
   else if(strcmp(symbol,"dff") == 0) fn=DFF;
   else if(strcmp(symbol,"xor") == 0) fn=XOR;
   else if(strcmp(symbol,"xnor") == 0) fn=XNOR;
   else if(strcmp(symbol,"buff") == 0) fn=AND;
   else if(strcmp(symbol,"buf") == 0) fn=AND;
   else if(strcmp(symbol,"input") == 0) fn=PI;
   else if(strcmp(symbol,"output") == 0) fn=PO;
   else fn=(-1);

   return(fn);
}

char *spc_to_und(buf)
char *buf;
{
   int i=0;
   while (buf[i] == ' ') buf++;
   
   while (buf[i] != '\0') {
     if (buf[i] == ' ') buf[i] = '_';
     i++;
   }
   return (buf);
} 

#define get_string(file,string) \
if(fscanf(file,"%s",string)<GOOD) fatalerror(CIRCUITERROR)

/*------read_circuit-------------------------------------------------
        Reads a circuit file.
	The netlist format is the same as that of ISCAS89 benchmark
	netlists except that:

            1) The first line should start with # followed by
	       the name of the circuit, and
            2) Comment lines which starts with # can be inserted
	       in any part of the circuit netlist.

	Constructs basic data stuructures
        and allocates necessary memory spaces.

	Users should provide the following information;
	1. index field : identification of gates (same as array index)
	2. fn        : gate type
	3. ninput    : number of fan-in lines
	4. inlis     : list of fan-in lines
	5. noutput   : number of fan-out lines
	6. outlis    : list of fan-out lines
	7. name	     : pointer to the hash table

	inputs: circuit input file (circuit)
	outputs: data structures

	Note: The circuit description is topologically sorted  in the
	      levelized order after parsing.
	Laveling order: primary input starts 0 to n-1  (n inputs)
			flip/flops starts n to n+m-1   (m f/f)
			gate starts n+m to n+m+l-1     (l gates)
---------------------------------------------------------------------*/
int read_circuit(name,nog,nopi,nopo,noff)
char name[]; int *nog, *nopi, *nopo, *noff;
{
   register int i,j;
   register char c;
   register GATEPTR cg;
   register HASHPTR hp;
   int int_nog,int_nopi,int_nopo,int_noff;
   char symbol[MAXSTRING];
   char buf[MAXSTRING], *bufptr;  /* store a line of text */
   int fn, nofanin;
   int net_size;
   GATETYPE *pg;
   GATEPTR pfanin[MAXFIN+1000];
   GATEPTR po_gates[MAXPO+1000];

   /* The first line should start with # followed by
      the name of the circuit */
   while((c=getc(circuit)) != EOF)
      if(c=='#' || c=='\n') break;
   if(c==EOF) return((-1));
   if(c=='#') {
     if (!fgets(buf, MAXSTRING, circuit)) 
        fatalerror(CIRCUITERROR);
     buf[strlen(buf)-1] = '\0';
     bufptr = spc_to_und(buf);
     strcpy(name, bufptr);
              }

   InitHash(symbol_tbl,HASHSIZE);

   /* Pass 1:
	Adds the gate symbols to symbol_tbl[] and
	counts # of gates, pi's, po's, ff's
   */
   int_nopi=int_nopo=int_noff=int_nog=0;
   nofanin=0;
   begnet=(GATEPTR)NULL;

   while((c=getsymbol(circuit,symbol)) != EOF) {
      switch(c) {
      case '=' :	/* name of a new gate */
	 hp=Find_and_Insert_Hash(symbol_tbl,HASHSIZE,symbol,0);
         if((cg=hp->pnode) == NULL) {
            ALLOCATE(cg, GATETYPE, 1);
            hp->pnode = cg;
            cg->symbol = hp;
            cg->next = begnet;
	    cg->po = 0;
            begnet = cg;
         }
	 break;
      case '(' :			/* gate type */
         if((fn=gatetype(symbol)) < 0) {
            fprintf(stderr,"Error: Gate type %s is not valid\n",symbol);
            return(-1);
         }
         break;
      case ',':                         /* fanin list */
         hp=Find_and_Insert_Hash(symbol_tbl,HASHSIZE,symbol,0);
         if((pg=hp->pnode) == NULL) {
            ALLOCATE(pg, GATETYPE, 1);
            hp->pnode = pg;
            pg->symbol = hp;
            pg->gid = (-1);
	    pg->po = 0;
            pg->next = begnet;
            begnet = pg;
         }
         pfanin[nofanin++]=pg;
         break;
      case ')':	/* fanin list */
         hp=Find_and_Insert_Hash(symbol_tbl,HASHSIZE,symbol,0);
         if((pg=hp->pnode) == NULL) {
            ALLOCATE(pg, GATETYPE, 1);
            hp->pnode = pg;
            pg->symbol = hp;
            pg->gid = (-1);
	    pg->po = 0;
            pg->next = begnet;
            begnet = pg;
         }
         switch(fn) {
         case PI:
            int_nopi++;
            pg->gid = int_nog++;
            pg->ninput=0;
            pg->inlis=(GATEPTR *)NULL;
            pg->fn=PI;
            pg->noutput=0;
            pg->outlis=(GATEPTR *)NULL;
            break;
         case PO:
            po_gates[int_nopo++] = pg;
            break;
         default:
            pfanin[nofanin++] = pg;
            if(fn==DFF) int_noff++;
            if(cg==NULL) {
               fprintf(stderr,"Syntax error in the circuit file\n");
               return(-1);
            }
            cg->gid = int_nog++;
            cg->fn=fn;
            if((cg->ninput=nofanin) == 0) cg->inlis=NULL;
            else { ALLOCATE(cg->inlis,GATEPTR,cg->ninput); }
            for(i=0; i<nofanin; i++) cg->inlis[i]=pfanin[i];
            cg->noutput=0;
            cg->outlis=(GATEPTR *)NULL;
 
            nofanin=0;
            cg = (GATEPTR) NULL;
            break;
         }
      }
   }

   /* Pass 2: Construct the circuit data structure */
   net_size=int_nog+int_nopo+int_noff;
   if(int_nog > MAXGATE) {
      fprintf(stderr,"The number of gates exceeds MAXGATE %d\n",MAXGATE);
      fprintf(stderr,"Increase the parameter MAXGATE in atpg.h ");
      fprintf(stderr,"to more than %d\n",int_nog);
      exit(0);
   }
   if(int_nopi > MAXPI) {
      fprintf(stderr,"The number of primary inputs exceeds MAXPI %d\n",MAXPI);
      fprintf(stderr,"Increase the parameter MAXPI in atpg.h ");
      fprintf(stderr,"to more than %d\n",int_nopi);
      exit(0);
   }
   if(int_nopo > MAXPO) {
      fprintf(stderr,"The number of primary outputs exceeds MAXPO %d\n",MAXPO);
      fprintf(stderr,"Increase the parameter MAXPO in atpg.h ");
      fprintf(stderr,"to more than %d\n",int_nog);
      exit(0);
   }
   if(int_noff > 0) {
      fprintf(stderr,"Flip-flops exist in the circuit.\n");
      fprintf(stderr,"Please check the circuit netlist.\n",int_nog);
      fprintf(stderr,"Bye.\n",int_nog);
      exit(0);
   }

   ALLOCATE(net,GATEPTR,net_size);
   ALLOCATE(primaryin,int,int_nopi);
   ALLOCATE(primaryout,int,int_nopo);
   ALLOCATE(headlines,int,int_nopi);
 
   *nog=*nopi=*nopo=*noff=0;
   for(cg=begnet; cg!=NULL; cg=cg->next) {
      if(cg->gid < 0) {
         fprintf(stderr,"Error: Undefined symbol %s\n",cg->symbol->symbol);
         return(-1);
      }
      net[cg->gid] = cg;
      (*nog)++;
   }
   for(i=*nog; i<net_size; i++) net[i]=(GATEPTR)NULL;
 
   if(*nog != int_nog) {
      fprintf(stderr,"Error in read_circuit\n");
      return(-1);
   }

/*
   for(i=0; i<*nog; i++) {
      cg=net[i];
      printf("net %d: %s ",cg->gid, cg->symbol->symbol);
      printf("noin=%d ",cg->ninput);
      printf("noout=%d ",cg->noutput);
      for(j=0; j<cg->ninput; j++)
         printf("%s ",cg->inlis[j]->symbol->symbol);
      printf("\n");
   }
*/

   /* Pass 3: Compute fanout list */
   for(i=0; i<*nog; i++) {
      cg=net[i];
#ifdef LEARNFLG
      cg->plearn=NULL;
#endif
      for(j=0; j<cg->ninput; j++) cg->inlis[j]->noutput++;
      switch(cg->fn) {
      case PI: primaryin[(*nopi)++] = i; break;
      case DFF: flip_flops[(*noff)++] = i; break;
      }
   }
   for(i=0; i<int_nopo; i++) {
      primaryout[(*nopo)++]=po_gates[i]->gid;
      po_gates[i]->po = TRUE;
   }
   for(i=0; i<*nog; i++) {
      cg=net[i];
      if(cg->noutput>0) {
         if(maxfout<cg->noutput) maxfout=cg->noutput;
	 ALLOCATE(cg->outlis, GATEPTR, cg->noutput);
         cg->noutput=0;
      }
   }
 
   for(i=0; i<*nog; i++) {
      cg=net[i];
      for(j=0;j<cg->ninput;j++)
         cg->inlis[j]->outlis[(cg->inlis[j]->noutput)++]=cg;
   }

/*
   for(i=0; i<*nog; i++) {
      cg=net[i];
      printf("net %d: %s ",cg->gid,cg->symbol->symbol);
      printf("noin=%d noout=%d po=%d ",cg->ninput, cg->noutput, cg->po);
      for(j=0;j<cg->noutput;j++) {
         pg=cg->outlis[j];
         printf("%s ",pg->symbol->symbol);
         for(int_nopi=0; int_nopi<pg->ninput; int_nopi++)
	    if(pg->inlis[int_nopi]==cg) break;
	 if(int_nopi == pg->ninput)
	    printf("Error from %s",pg->symbol->symbol);
      }
      printf("\n");
   }
*/

   if(int_nog==*nog) return(*nog);
   else return(-1);
}

/*------levelize: 
	topologically sorts the circuit in the levelized order------*/
int levelize(net, n, nopi, nopo, noff, stack)
GATEPTR *net; int n, nopi, nopo, noff; GATEPTR *stack;
{
   register int i, int_nog;
   register GATEPTR *first, *last;
   register GATEPTR ele, next;
   int G_index=0;
   int maxlevel=(-1);

   /* initialize */
   for(i=0; i<n; i++)
      if((ele=net[i]) != NULL) {
	 ele->ichange=ele->ninput;
	 ele->dpi=(-1);
      }

   first=last=stack;	/* empty stack */

   /* Find gates with indegree=0 */
   for(i=0; i<nopi; i++) {
      ele=net[primaryin[i]];
      ele->ichange=0;
      *last++=ele;
      primaryin[i]=G_index++;
   }
   for(i=0; i<noff; i++) {
      ele=net[flip_flops[i]];
      ele->ichange=0;
      *last++=ele;
      flip_flops[i]=G_index++;
   }

   /* levelize */
   G_index=0;
   int_nog=0;
   while(first != last) {
      int_nog++;
      ele=*first++;
      ele->gid=G_index++;
      if( ++(ele->dpi) > maxlevel) maxlevel=ele->dpi;
      for(i=0; i<ele->noutput; i++)
	 if((next=ele->outlis[i]) != NULL)
	    if(next->ichange > 0) {
	       if(--(next->ichange) == 0) *last++=next;
	       next->dpi = ele->dpi;
	    }
   }

   /* check for levelization */
   if(int_nog != n) {
      fprintf(stderr,"Error in circuit file.\n");
      fprintf(stderr,"Some gates are not reachable from PIs.\n");
      for(i=0; i<n; i++) {
         ele=net[i];
         if(ele->ichange>0 || ele->dpi<0) {
            fprintf(stderr,"*** Unreachable gate from an input:");
	    fprintf(stderr,"%d'th element %s\n",ele->gid,
	            ele->symbol->symbol);
         }
      }
      return(-1);
   }

   for(i=0; i<nopo; i++)	/* primaryout */
      primaryout[i]=net[primaryout[i]]->gid;

   /* sort gates by gid */
   for(i=0; i<n; ) {
      if(i==net[i]->gid) i++;
      else {			/* swap net[i] and net[net[i]->gid] */
	 ele=net[i];
	 net[i]=net[ele->gid];
	 net[ele->gid]=ele;
      }
   }

   return(maxlevel+1);
}

/*------add_PO-------------------------------------------------------
        adds a PO gate at each primary output
        should be called before levelize()

        modified by Hyung K Lee  3/12/1996
--------------------------------------------------------------------*/
int add_PO(net,nog,nopo)
GATEPTR *net;
int nog, nopo;
{
   register int i,j;
   GATEPTR gut,last,*outlist;
   char name[MAXSTRING];
   int nodummy=0;

   for(i=0;i<nopo;i++) {
      gut=net[primaryout[i]];
      if (!gut->po) {
         fprintf(stderr,"Netlist error: gate %s should be a PO\n",
                 gut->symbol->symbol);
         exit(0);
      }
      if (gut->noutput==0) continue;
      if((last=net[nog])==NULL) ALLOCATE(last,GATETYPE,1);
      last->index=nog;
      /* last->fn=PO; */
      last->fn=AND;
      last->ninput=1;
      ALLOCATE(last->inlis,GATEPTR,1);
      last->inlis[0]=gut;
      last->noutput=0;
      last->outlis=NULL;
      last->po = 1;
      strcpy(name,gut->symbol->symbol);
      strcat(name,"_PO");
      while((last->symbol=FindHash(symbol_tbl,HASHSIZE,name,0))
         != NULL) strcat(name,"_PO");
      if((last->symbol=InsertHash(symbol_tbl,HASHSIZE,name,0))
         == NULL) fatalerror(HASHERROR);
      else last->symbol->pnode=last;

      outlist=gut->outlis;
      ALLOCATE(gut->outlis,GATEPTR,gut->noutput+1);
      for(j=0;j<gut->noutput;j++) gut->outlis[j]=outlist[j];
      gut->outlis[gut->noutput]=last;
      gut->noutput+=1;
      gut->po = 0;

      primaryout[i]=nog;
      net[nog++]=last;
      if(outlist!=NULL) MFREE(outlist);
      nodummy++;
   }

   return(nodummy);
}

