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


        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

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

	fsim: version 1.1

	Changed Parser and added on-line manual: H. K. Lee, 10/5/1992

	Now, fsim accepts the circuit written in the netlist format
	of ISCAS89 benchmark circuits as well as the netlist format of
	ISCAS85 benchmark circuits.

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

/*----------------------------------------------------------------------
	atpg.h
	Defines global data structure for fsim.
-----------------------------------------------------------------------*/

/* Parameters: defines maximum storates */
#define	MAXGATE		50000	/* maximum number of gates */
#define	MAXFAULT	100000	/* maximum number of faults */
#define	MAXPI		2500	/* maximum number of primary inputs */
#define	MAXPO		2500	/* maximum number of primary outputs */
#define	MAXFIN		15	/* maximum number of fanin lines */
#define	MAXFOUT		15	/* maximum number of fanout lines */
#define	MAXLINE		150000	/* size of a line */
#define HASHSIZE	19999
#define	MAXGTYPE	7	/* number of gate types */
#define	MAXLEVEL	5	/* number of logic levels */
#define	MAXBUF		400	/* number of buffers for backtrace */
#define	MAXOBJ		1000
#define	MAXTREE		400
#define	MAXTEST		1000
#define	MAXSTRING	200
#define	INFINITY	999999

/* circuit netlist format */
#define ISCAS85         '5'
#define ISCAS89         '9'
 
/* error messages */
#define NUMERRORS       10      /* number of error message */
#define NOERROR         0
#define EOFERROR        1
#define CIRCUITERROR    2
#define MEMORYERROR     3
#define HASHERROR       4
#define FAULTERROR      5

/* status */
#define GOOD 1
#define EMPTY (-1)
#define mod %
#define UNDETECTED 0
#define DETECTED 1
#define REDUNDANT 2
#define PROCESSED 3
#define OUTFAULT (-1)

/* typedef enum {AND,OR,NAND,NOR,PI,XOR} function; */
typedef int function;
#define AND 0
#define NAND 1
#define OR  2
#define NOR 3
#define PI 4
#define XOR 5
#define XNOR 6

#define DFF     7
#define PO      20

/* typedef enum {ZERO,ONE,X,D,DBAR} level; */
typedef unsigned level;
#define ZERO 0
#define ONE  1
#define X    2
#define D    3
#define DBAR 4

/* typedef enum {INsa0,INsa1,OUTsa0,OUTsa1} ftype; */
typedef unsigned ftype;
#define INsa0 0
#define INsa1 1
#define OUTsa0 2
#define OUTsa1 3

/* typedef enum {FALSE,TRUE} boolean; */
typedef int boolean;
#define FALSE 0
#define TRUE 1

typedef int status;

typedef struct GATE *GATEPTR;
typedef struct link *LINKPTR;
typedef struct FAULT *FAULTPTR;
 
typedef struct HASH *HASHPTR;   /* added for ISCAS89 netlist */
typedef struct HASH {
   int key;                     /* variable of the given symbol */
   int index;                   /* index of the GATE structure */
   GATEPTR pnode;
   struct HASH *next;           /* next string */
   char *symbol;                /* symbolic name */
} HASHTYPE;

typedef struct link {
	GATEPTR ngate;
	struct link *next;
} LINKTYPE;

/* netlist data structure */
typedef struct GATE {
	int gid;		/* internal identification */
	int index;		/* gate number of the netlist */
	function fn;		/* type of gate */
	int ninput;		/* number of fanins */
	struct GATE **inlis;	/* fan-in list */
	int noutput;		/* number of fan-outs */
	struct GATE **outlis;	/* fan-out list */
	level output;		/* fault free value */
	level output1;		/* faulty value */
	boolean ichange,	/* flag for input change */
	        po,		/* primary output */
		freach;		/* reached from faulty gate */
	int dpi,dpo;		/* distance from PIs and POs */
	int numzero,numone;	/* expected number of zeros and ones */
	LINKPTR u_path;		/* next unique path */
	int cont0,cont1;	/* 0 and 1 controllability */
	int fos; int nfault;	/* fanout stem */
	level cobserve;		/* local detectability of dominator gate */
	level observe;		/* local/global observation flag */
	FAULTPTR pfault;	/* fault list */
	FAULTPTR *dfault;	/* storage for detectable faults */
        HASHPTR symbol;         /* added for ISCAS89 netlist */
	GATEPTR next;
} GATETYPE;

/* fault data structure */
typedef struct FAULT {
	GATEPTR faulty_gate;	/* faulty gate */
	ftype fault;		/* fault type */
	int faulty_line;	/* faulty input, -1 if output fault */
	struct FAULT *next;	/* pointer to next fault */
	struct FAULT *previous;	/* pointer to previous fault */
	boolean covered;	/* detected or not */
	boolean observe;	/* detectability */
} FAULTTYPE;

typedef struct EVENT {
	int last;
	GATEPTR *list;
} EVENTTYPE,*EVENTPTR;

GATEPTR *net;		/* circuit structure */
int *primaryin,*primaryout;
int *headlines;

struct FLIST {
	int last;
	FAULTPTR *list;
} fault_list;

int *depth_array;
EVENTPTR event_lis;		/* pointer to event list */
EVENTTYPE stack;		/* stack for backtracing */
EVENTTYPE free_gates,		/* list for fault free evaluation */
	  faulty_gates,		/* list of faulty gates */
	  eval_gates,		/* list of stems */
	  active_stems;		/* list of active stems */
GATEPTR *dynamic_stack;
int nsstack,ndstack;

char line[81];			/* output line */

/* files */
char *malloc();
FILE *fopen(),*circuit,*test,*outfile,*logfile;
int mac_i;

/* macros */
#define set(var) (var=TRUE)
#define reset(var) (var=FALSE)

/* macros for set operation LIFO stack */
#define push(s,ele) s.list[++(s.last)]=ele
#define pop(s) s.list[(s.last)--]
#define delete_last(s) --(s.last)
#define delete(s,i) s.list[i]=s.list[(s.last)--]
#define clear(s) s.last=EMPTY
#define swap(s,i,j,el)	el=s.list[j]; \
			s.list[j]=s.list[i]; \
			s.list[i]=el;
#define is_empty(s) (s.last<=EMPTY)

#define max(a,b) (a>b) ? a : b
#define min(a,b) (a>b) ? b : a

/* Decralations for parallel bit operation */
#define BITSIZE 32		/* size of a word */
#define ALL0 0
#define ALL1 (~0)
#define MASK1 (~(ALL1<<1))

/* Global variables for bit operation ----
   should be initialized at the first line of main program.  */
level all_one;
level bitmask[BITSIZE];
status update_flag;
status update_flag2;
int ntestp;

/* variables for occurrence test of subroutines */
long niter[20];

double sttime;

/********** Macros for memory menagement **********/
char *malloc(), *calloc(), *realloc();
 
#define MALLOC(type,number) \
(type *)malloc((unsigned)(sizeof(type)*(number)))
#define MFREE(pointer) \
{ if((pointer)!=NULL) free((char *)pointer); }
#define ALLOCATE(pointer,type,number) \
if((pointer=MALLOC(type,number))==NULL) fatalerror(MEMORYERROR)
#define CALLOCATE(pointer,type,number) \
if((pointer=CALLOC(type,number))==NULL) fatalerror(MEMORYERROR)
 
