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


        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: version 1.0 and version 1.1

	Original: H. K. Lee, 8/15/1990
	Updated: H. K. Lee, 8/15/1991

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

/*-----------------------------------------------------------------
	file name: define_fault_list.c
	This file constructs fault list after collapsing equivalent
	faults.
-------------------------------------------------------------------*/
#include <stdio.h>
#include "atpg.h"

extern char  rptmode;
extern HASHPTR symbol_tbl[];
extern HASHPTR FindHash();
extern void fatalerror();

/*	set_all_fault_list
	Sets up the fault list data structure.
	Equivalent faults are collapsed.
*/
int set_all_fault_list(nog,nstem,stem)
int nog,nstem;
GATEPTR *stem;
{
   register GATEPTR g;
   register FAULTPTR p;
   register int i,j;
   FAULTPTR current;
   ftype f;
   int nfault,n;

   nfault=0;
   current=(FAULTPTR)malloc(sizeof(FAULTTYPE));
   current->next=NULL;

   for(i=0;i<nog;i++) {

      /* input line faults */
      g=net[i];
      g->pfault=current;
      g->nfault=0;

      /* if the input of the gate has more than one fanouts, 
	 add a s-a-1 for each AND/NAND,
	     a s-a-0 for each OR/NOR and
	     a s-a-0 and s-a-1 for other gates. */

      if(g->ninput>1) {
	 f=(g->fn==AND||g->fn==NAND) ? INsa1 : INsa0;
	 for(j=0;j<g->ninput;j++) {
	    if(g->inlis[j]->noutput>1) {
	       p=(FAULTPTR)malloc(sizeof(FAULTTYPE));
	       p->faulty_gate=g;
	       p->fault=f;
	       p->faulty_line=j;
	       p->next=NULL;
	       nfault++; g->nfault++;
	       current->next=p;
	       if(current==g->pfault) p->previous=p;
	       else p->previous=current;
	       current=p;
	       /* case of high level gates */
	       if(g->fn>PI) {
	          ALLOCATE(p,FAULTTYPE,1);
	          p->faulty_gate=g;
	          p->fault=(f==INsa1) ? INsa0 : INsa1;
	          p->faulty_line=j;
	          p->next=NULL;
	          nfault++; g->nfault++;
	          current->next=p;
	          if(current==g->pfault) p->previous=p;
	          else p->previous=current;
	          current=p;
	       }
	    }
         }
      }

      /* output fault assignment:
	 add s-a-1 and s-a-0 faults for each fanout stem or
	 primary output. */
      if(g->noutput==1 && g->outlis[0]->ninput>1) {
	 f=(g->outlis[0]->fn==AND||g->outlis[0]->fn==NAND) ?
	   OUTsa1 : OUTsa0;
	 ALLOCATE(p,FAULTTYPE,1);
	 p->faulty_gate=g;
	 p->fault=f;
	 p->faulty_line=OUTFAULT;
	 p->next=NULL;
	 nfault++; g->nfault++;
	 current->next=p;
	 if(current==g->pfault) p->previous=p;
	 else p->previous=current;
	 current=p;
	 /* case of high level gates */
	 if(g->outlis[0]->fn>PI) {
	    p=(FAULTPTR)malloc(sizeof(FAULTTYPE));
	    p->faulty_gate=g;
	    p->fault=(f==OUTsa1) ? OUTsa0 : OUTsa1;
	    p->faulty_line=OUTFAULT;
	    p->next=NULL;
	    nfault++; g->nfault++;
	    current->next=p;
	    if(current==g->pfault) p->previous=p;
	    else p->previous=current;
	    current=p;
         }
      }
      else if((g->noutput>1)|| g->po) {
	 p=(FAULTPTR)malloc(sizeof(FAULTTYPE));
	 p->faulty_gate=g;
	 p->fault=OUTsa1;
	 p->faulty_line=OUTFAULT;
	 p->next=NULL;
	 nfault++; g->nfault++;
	 current->next=p;
	 if(current==g->pfault) p->previous=p;
	 else p->previous=current;
	 current=p;
	 p=(FAULTPTR)malloc(sizeof(FAULTTYPE));
	 p->faulty_gate=g;
	 p->fault=OUTsa0;
	 p->faulty_line=OUTFAULT;
	 p->next=NULL;
	 nfault++; g->nfault++;
	 current->next=p;
	 if(current==g->pfault) p->previous=p;
	 else p->previous=current;
	 current=p;
      }

      current=g->pfault;
      if(g->pfault->next==NULL) g->pfault=NULL;
      else g->pfault=current->next;
      current->next=NULL;
   }	/* end for */

   free((char *)current);

   /* create the fault_list and
      enumerate faults in each fanout free region */
   fault_list.list=(FAULTPTR *)malloc((unsigned)(sizeof(FAULTPTR)*nfault));
   clear(fault_list); clear(stack);
   for(i=nstem-1;i>=0;i--) {
      push(stack,stem[i]);
      n=1;
      while(!is_empty(stack)) {
	 g=pop(stack);
	 for(p=g->pfault;p!=NULL;p=p->next) 
	    { push(fault_list,p); n++; }
	 for(j=0;j<g->ninput;j++)
	    if(g->inlis[j]->noutput==1) push(stack,g->inlis[j]);
      }
      stem[i]->dfault=(FAULTPTR *)malloc((unsigned)(n*sizeof(FAULTPTR)));
   }

   if(nfault==fault_list.last+1) return(nfault);
   else return(-1);
}

/*	add_fault
	Add a fault to the linked list of each gate.
*/
void add_fault(f)
FAULTPTR f;
{
   GATEPTR gut; FAULTPTR p;

   gut=f->faulty_gate;
   if(gut->pfault==NULL) {
      gut->pfault=f;
      f->previous=f;
      gut->nfault=1;
   }
   else {
      p=gut->pfault;
      while(p->next!=NULL) p=p->next;
      p->next=f;
      f->previous=p;
      gut->nfault++;
   }
   f->next=NULL;
}

/*	restore_detected_fault_list
	Restores the fault list for test compaction.
	Does not restore redundant faults.
*/
int restore_detected_fault_list(nof)
int nof;
{
   register FAULTPTR f;
   register int i,n;

   n=0;
   for(i=0;i<nof;i++) {
      f=fault_list.list[i];
      if(f->covered==DETECTED) {
	 f->covered=UNDETECTED;
	 add_fault(f);
	 n++;
      }
   }
   return(n);
}

/*	restore_all_fault_list
	Restores the fault list for resimulation of faults.
	Restores all faults including redundant faults.
*/
/*
int restore_all_fault_list()
{
   register int i;

   for(i=0;i<=fault_list.last;i++) {
      add_fault(fault_list.list[i]);
      fault_list.list[i]->covered=UNDETECTED;
   }
   return(fault_list.last+1);
}
*/

/*	check_redundant_faults
	Identifies redundant faults in which more than two inputs of
	a gate are connected to one gate simultaneously and deletes
	the faults from the fault list.

	Input: nog, the number of gates of the circuit
	Output: number of identified redundant faults
	Note: ichange flags of all gates should be reset to 0
	      prior to call this function.
*/

/* macro to delete a fault */
#define delete_fault(fal) \
if(fal->previous==fal) { \
   fal->faulty_gate->pfault=fal->next; \
   if(fal->next!=NULL) fal->next->previous=fal->next; \
} else { \
   fal->previous->next=fal->next; \
   if(fal->next!=NULL) fal->next->previous=fal->previous; \
}

int check_redundant_faults(nog)
int nog;
{
   register int i, j;
   int n;
   register GATEPTR gut;
   FAULTPTR f;

   n=0;
   for(i=0;i<nog;i++)
      if(net[i]->noutput>1) {
	 gut=net[i];
	 for(j=0;j<gut->noutput;j++) (gut->outlis[j]->ichange)++;
	 for(j=0;j<gut->noutput;j++) {
	    if(gut->outlis[j]->ichange>1)
	       for(f=gut->outlis[j]->pfault;f!=NULL;f=f->next)
		  if(f->faulty_line>=0)
		     if(f->faulty_gate->inlis[f->faulty_line]==gut) {
			f->covered=REDUNDANT;
			if(--f->faulty_gate->nfault>0) {delete_fault(f);}
			n++;
		     }
	    reset(gut->outlis[j]->ichange);
	 }
      }
   return(n);
}


/*******************************************************************
The following routines are used to read fault directory.
The file format is the same as that of ISCAS89 fault list file.
**********************************************************************/

#define is_white_space(c) (c==' ' || c=='-' || c=='\t' || c=='\n')
#define is_head_symbol(c) (c=='/' || c=='>')
#define is_valid(c) ((c>='0' && c<='9') || \
		     (c>='A' && c<='Z') || \
		     (c>='a' && c<='z') || \
		     (c=='_'))

/*------getfaultsymbol-------------------------------------------------
	reads next symbol from the given fault file
	inputs : file	the name of input file
	outputs: s	symbol string output
        returns head character of s unless EOF is encountered.
-------------------------------------------------------------------*/
#define	EOS	'\0'

char getfaultsymbol(file,s)
FILE *file; char s[];
{
   char c;
   int n=0;
   status valid=FALSE;

   while((c=getc(file))!=EOF) {
      if(is_white_space(c)) { if(valid) break; else continue; }
      if(is_head_symbol(c)) { s[n++]=c; continue; }
      if(is_valid(c)) { s[n++]=c; set(valid); }
      else fatalerror(FAULTERROR);
   }
   s[n]=EOS;
   if(c==EOF) return(c); else return(s[0]);
}


/*------readfaults------------------------------------------------
	reads fault list and constructs fault list data structure
	inputs: file	fault directory file
	outputs: fault list
------------------------------------------------------------------*/
int readfaults(file,nog,nstem,stem)
FILE *file; int nog,nstem; GATEPTR *stem;
{
   GATEPTR gut;
   FAULTPTR f;
   int from,to,line,type;
   HASHPTR h;
   int i, j;
   char c;
   char s[MAXSTRING];
   int nfault, n;

   nfault=0;
   for(i=0; i<nog; i++) {
      gut=net[i];
      gut->pfault=(FAULTPTR)NULL;
      gut->nfault=0;
   }

   while(getfaultsymbol(file,s)!=EOF) {
      if(is_valid(s[0])) {
	 if((h=FindHash(symbol_tbl,HASHSIZE,s,0))==NULL) {
	    fprintf(stderr,"Error in fault file:");
	    fprintf(stderr,"%s is not defined\n",s);
	    fatalerror(FAULTERROR);
	 }
	 if((to=h->pnode->gid) < 0) fatalerror(FAULTERROR);
	 gut=net[to];
	 line=(-1);
      } else if(s[0]=='>') {
	 from=to;
	 if((h=FindHash(symbol_tbl,HASHSIZE,&s[1],0))==NULL) {
	    fprintf(stderr,"Error in fault file:");
	    fprintf(stderr,"%s is not defined\n",s);
	    fatalerror(FAULTERROR);
	 }
	 if((to=h->pnode->gid)<0) fatalerror(FAULTERROR);
	 gut=net[to];
	 for(i=0;i<gut->ninput;i++)
	    if(gut->inlis[i]->gid==from) { line=i; break; }
      } else if(s[0]=='/') {
	 if(s[1]=='1') type=OUTsa1; else type=OUTsa0;
	 if(line >= 0)
	    type = (type==OUTsa1) ? INsa1 : INsa0;

	 ALLOCATE(f,FAULTTYPE,1);
	 f->faulty_gate=gut;
	 f->faulty_line=line;
	 f->fault=type;
	 f->previous=f;
	 if((f->next=gut->pfault) != NULL) f->next->previous=f;
	 gut->pfault=f;
         nfault++;
         gut->nfault++;
/*       while((c=getc(file)) != '\n') if(c==EOF) break; */
      } else fatalerror(FAULTERROR);
   }

   /* create the fault_list and
      enumerate faults in each fanout free region */
   fault_list.list=(FAULTPTR *)malloc((unsigned)(sizeof(FAULTPTR)*nfault));
   clear(fault_list);
   clear(stack);
   for(i=nstem-1;i>=0;i--) {
      push(stack,stem[i]);
      n=1;
      while(!is_empty(stack)) {
         gut=pop(stack);
         for(f=gut->pfault;f!=NULL;f=f->next)
            { push(fault_list,f); n++; }
         for(j=0;j<gut->ninput;j++)
            if(gut->inlis[j]->noutput==1) push(stack,gut->inlis[j]);
      }
      stem[i]->dfault=(FAULTPTR *)malloc((unsigned)(n*sizeof(FAULTPTR)));
   }
 
   if(nfault==fault_list.last+1) return(nfault);
   else return(-1);
}
