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


        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 **********************************

	fsim: version 1.0 & version 1.1

	Original: H. K. Lee, 8/15/1990
	Updated: H. K. Lee, 8/15/1991
        Changed Parser and added on-line manual, H. K. Lee, 10/5/1992

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

/*--------------------------------------------------------------------- 
	filename io.c
	This file constructs necessary data structures for
	atalanta, fsim and soprano.
-----------------------------------------------------------------------*/

#include <stdio.h>
#include <sys/types.h>
#include <sys/timeb.h>
#include <time.h>
#include "atpg.h"

#define NULL 0

extern char *strcpy();

int lineindex[MAXLINE];
char namelist[MAXGATE][10];

/*	circin
	Reads an input circuit file and constructs internal
	data stuructures.

	The following information of the netlist is set in circin:
	1. gid 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. po        : set if the gate is a primary output

	Inputs: circuit input file (circuit)
	Outputs: data structures and
	     nog: number of gate
	     nopi: number of primary inputs
	     nopout: number of primary outputs

	Note: Circuit format is the same as ISCAS85 benchmark circuits.
	      The circuit description should be topologically sorted,
	      All gates are re-numbered in sequential order from
              0 to nog-1.
*/
boolean circin(nog,nopi,nopout)
int *nog,*nopi,*nopout;
{
   int i,j;
   int lineno,nfout,nfin;
   int currentline=0;
   int inputs[20];
   char name[10],gtype[5],fromline[10];

   *nog = 0;
   *nopi = 0;
   *nopout = 0;

   ALLOCATE(net, GATEPTR, MAXGATE);
   ALLOCATE(primaryin, int, MAXPI);
   ALLOCATE(primaryout, int, MAXPO);

   while(fscanf(circuit,"%80s",line) != EOF) {
      if(line[0] == '*') fgets(line,80,circuit); /* comment lines */
      else {
	 /* read gate descriptions in the order of
	    line_number, label, gtype, # of fanout, # of fanin */
	 sscanf(line,"%5d",&lineno);
	 fscanf(circuit,"%9s%5s",name,gtype);
	 if(strcmp(gtype,"from") == 0)		/* fan-out branch */
	    fscanf(circuit,"%9s",fromline);
	 else
	    fscanf(circuit,"%d%d",&nfout,&nfin);
	 while(getc(circuit)!='\n');

	 /* if gate type is from, search fanin lines 
	   and skip fanout lines from the gate list */
	 if(strcmp(gtype,"from") == 0) {
	    for(i=currentline;i>=0;i--)
		if(strcmp(fromline,namelist[i])==0) {
		   lineindex[lineno]=net[i]->gid;
		   break;
		}
	 }

	 /* else, construct gate structutes */
	 else {
	    strcpy(namelist[currentline],name);	/* store label */
	    net[currentline]=(GATEPTR)(malloc(sizeof(GATETYPE)));
	    lineindex[lineno]=currentline;
	    net[currentline]->gid = currentline;/* internal netlist */
	    net[currentline]->index = lineno;	/* actual netlist */
	    net[currentline]->ninput = nfin;
	    if(nfin != 0) net[currentline]->inlis=
		 (GATEPTR *)(malloc((unsigned)(sizeof(GATEPTR)*nfin)));
	    net[currentline]->noutput = nfout;
	    if(nfout != 0) {
		net[currentline]->outlis=
		(GATEPTR *)(malloc((unsigned)(sizeof(GATEPTR)*nfout)));
		for(i=0;i<nfout;i++) net[currentline]->outlis[i]=NULL;
	    }
	    if(strcmp(gtype,"inpt") == 0) {
		net[currentline]->fn = PI;
		primaryin[*nopi] = currentline;
		(*nopi)++;
	    }
	    else {
		if(strcmp(gtype,"and") == 0) net[currentline]->fn=AND;
		else if(strcmp(gtype,"nand") == 0) net[currentline]->fn=NAND;
		else if(strcmp(gtype,"or")== 0) net[currentline]->fn=OR;
		else if(strcmp(gtype,"nor") == 0) net[currentline]->fn=NOR;
		else if(strcmp(gtype,"not") == 0) net[currentline]->fn=NAND;
		else if(strcmp(gtype,"xor") == 0) net[currentline]->fn=XOR;
		else if(strcmp(gtype,"buff") == 0) net[currentline]->fn=AND;
		else if(strcmp(gtype,"buf") == 0) net[currentline]->fn=AND;
		else if(strcmp(gtype,"xnor") == 0) net[currentline]->fn=XNOR;
		else { return(FALSE); }

		/* get intput list */
		for(i=0;i<nfin;i++) fscanf(circuit,"%6d",&inputs[i]);
		fgets(line,80,circuit);

		/* convert input index into internal and check fan-out list */
		for(i=0;i<nfin;i++) {
		   net[currentline]->inlis[i]=net[lineindex[inputs[i]]];
		   for(j=0;j<net[lineindex[inputs[i]]]->noutput;j++)
		      if(net[lineindex[inputs[i]]]->outlis[j]==NULL) {
			 net[lineindex[inputs[i]]]->outlis[j]=net[currentline];
			 break;
		      }
		}
	     }
	     if(nfout == 0) {
		primaryout[*nopout] = currentline;
	        net[currentline]->po=TRUE;
		(*nopout)++;
	     }
	     else net[currentline]->po=FALSE;
	     currentline++;
	  }
      }
   }
   *nog = currentline;
   return(TRUE);
}

/*	set_cct_parameters
	Initializes net structures (dpi).
	Allocates space for event_list and objectives.
*/
int set_cct_parameters(nog,npi)
int nog, npi;
{
   register int i,j,depth;
   int maxdpi=0;

   for(i=0;i<nog;i++) {
      depth=(-1);
      if(net[i]->fn != PI)
	 for(j=0;j<net[i]->ninput;j++) {
	    depth=max(net[i]->inlis[j]->dpi,depth);
         }
      net[i]->dpi=depth+1;
      maxdpi=max(net[i]->dpi,maxdpi);
   }

   /* Allocate memory for event_list and reset event counters. */
   maxdpi++;
   event_lis=(EVENTPTR)malloc((unsigned)(sizeof(EVENTTYPE)*maxdpi));
   depth_array=(int *)malloc((unsigned)(sizeof(int)*maxdpi));
   for(i=0;i<maxdpi;i++) event_lis[i].last=0;

   /* Count the number of gates in each depth on the event_list. */
   for(i=nog-1;i>=0;i--) (event_lis[net[i]->dpi].last)++;

   /* Allocate space for each event list. */
   for(i=0;i<maxdpi;i++) {
      event_lis[i].list=
	 (GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*event_lis[i].last));
      depth_array[i]=event_lis[i].last;
      clear(event_lis[i]);
   }

   /* Alloacate space for sets. */
   if(stack.list == NULL)
      stack.list=(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog));
   faulty_gates.list=(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog));
   free_gates.list=(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog));
   eval_gates.list=(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog));
   active_stems.list=(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog));

   return(maxdpi);
}

/*	allocate_dynamic_buffers
	Allocates dynamic buffers.
*/
boolean allocate_dynamic_buffers(nog)
int nog;
{
   if((faulty_gates.list=
	(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog)))==NULL) 
      return(FALSE);
   if((free_gates.list=
	(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog)))==NULL) 
      return(FALSE);
   if((eval_gates.list=
	(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog)))==NULL) 
      return(FALSE);
   if((active_stems.list=
	(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog)))==NULL) 
      return(FALSE);
   if((dynamic_stack=
	(GATEPTR *)malloc((unsigned)(sizeof(GATEPTR)*nog)))==NULL) 
      return(FALSE);
   return(TRUE);
}


#define Dschedule_output(gut,cnt,Dfrontier,tempgate) \
	for(cnt=0;cnt<gut->noutput;cnt++) { \
	   tempgate=gut->outlis[cnt]; \
	   if(!tempgate->ichange) { \
	      push(event_lis[tempgate->dpi],tempgate); \
	      Dfrontier++; \
	      set(tempgate->ichange); \
	}}
int set_dominator(nog,maxdpi)
int nog,maxdpi;
{
   register int i,j;
   register GATEPTR gut;
   GATEPTR Dominator,g;
   int gate_count;
   int ndominator=0;

   for(i=nog-1;i>=0;i--) {
      gut=net[i];
      if(gut->noutput<=1) gut->u_path=NULL;
      else {
         gate_count=0;
         Dschedule_output(gut,j,gate_count,g);
	 for(j=gut->dpi+1;j<maxdpi;j++)
	    while(!is_empty(event_lis[j])) {
	       Dominator=pop(event_lis[j]);
	       reset(Dominator->ichange);
	       if(gate_count<=0) continue;
	       gate_count--;
	       if(gate_count==0) {
		  gut->u_path=(LINKPTR)malloc(sizeof(LINKTYPE));
	          gut->u_path->ngate=Dominator;
	          ndominator++;
		  break;
	       }
	       if(Dominator->noutput==0) {
		  gut->u_path=NULL;
		  gate_count=0;
	       }
	       else if(Dominator->noutput>1) {
		  if(Dominator->u_path==NULL) {
		     gut->u_path=NULL;
		     gate_count=0;
		  }
		  else {
		     g=Dominator->u_path->ngate;
		     if(!g->ichange) {
			push(event_lis[g->dpi],g);
			set(g->ichange);
			gate_count++;
		     }
		  }
	       }
	       else if(!Dominator->outlis[0]->ichange) {
		  g=Dominator->outlis[0];
		  push(event_lis[g->dpi],g);
		  set(g->ichange);
		  gate_count++;
	       }
           }
     }
   }
   return(ndominator);
}

/*	set_unique_path
	For every fanout stem which has a dominator,
	this function finds the unique path.
*/
#define setfreach(gate,number) gate->freach=number
#define is_reached(gate,number) gate->freach==number

void set_unique_path(nog,maxdpi)
int nog,maxdpi;
{
   register int i,j;
   register GATEPTR gut, g;
   int k, count;
   LINKPTR p;

   for(i=nog-1;i>=0;i--) {
      gut=net[i];
      if(gut->u_path==NULL) continue;
      count=0;
      setfreach(gut,i);

      for(j=0;j<gut->noutput;j++) {
	 g=gut->outlis[j];
	 if(!g->ichange) {
	    push(event_lis[g->dpi],g);
	    set(g->ichange);
	    count++;
	 }
      }
      for(j=gut->dpi+1;j<maxdpi;j++) {
	 while(!is_empty(event_lis[j])) {
	    gut=pop(event_lis[j]);
	    reset(gut->ichange);
	    setfreach(gut,i);
	    count--;
	    if(count==0) {
	       p=net[i]->u_path;
	       for(k=0;k<gut->ninput;k++) {
		  g=gut->inlis[k];
		  if(is_reached(g,i)) {
		     p->next=(LINKPTR)malloc(sizeof(LINKTYPE));
		     p=p->next;
		     p->ngate=g;
		     p->next=NULL;
		  }
	       }
	       break;
	    }
	    for(k=0;k<gut->noutput;k++) {
	       g=gut->outlis[k];
	       if(!g->ichange) {
		  push(event_lis[g->dpi],g);
		  set(g->ichange);
		  count++;
	       }
	    }
	 }
      }
   }
}

/*	setfanoutstem
	Identifies fanout stems and builds fanout free region.
*/
void setfanoutstem(nog,stem,nstem)
int nog,nstem;
GATEPTR *stem;
{
   register int i,j;
   register GATEPTR p;

   j=0;
   for(i=0;i<nog;i++) 
      if((net[i]->noutput>1) || net[i]->po) {
	 stem[j++]=net[i];
      }
   clear(stack);
   if(j != nstem) { printf("Error in setfanoutstem\n"); exit(0); }
   for(i=0;i<nstem;i++) {
      push(stack,stem[i]);
      while(!is_empty(stack)) {
	 p=pop(stack);
	 p->fos=stem[i]->gid;
	 for(j=0;j<p->ninput;j++) {
	    if(p->inlis[j]->noutput==1) push(stack,p->inlis[j]);
	 }
      }
   }
}

/*	gettime
	Gets CPU time used by the program.
*/
void gettime(usertime,systemtime,total)
double *usertime;
double *systemtime;
double *total;
{
/*   *usertime=(double)utime/60.0;
   *systemtime=(double)stime/60.0; */
   *total=(double)0;
}
