/* Reporting the basic information of ISCAS85 Benchmark */

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

#define		max_name	30
#define		max_fanin	20
#define		max_fanout	140
#define		max_Ltype	30
#define		max_PI		6000
#define		max_PO		1500
#define         CALLOC(n,x)     ((x *)calloc(n,sizeof(x)))

typedef char StrType[max_name];

typedef enum logictype LogicType;
enum logictype	{	
	pi,
	ai2,	ai3,	ai4,	ai5,	ai6,
	oi2,	oi3,	oi4,	oi5,	oi6,	i1,		xnor,	xor,
	aoi21,	aoi22,	aoi211,	aoi221,	aoi222,	aoi31,	aoi32,	aoi33,
	oai21,	oai22,	oai211,	oai221,	oai222,	oai31,	oai32,	oai33};
char Ltype[max_Ltype][7] = {
	"pi",
	"ai2",   "ai3",   "ai4",    "ai5",    "ai6",
	"oi2",   "oi3",   "oi4",    "oi5",    "oi6",    "i1",    "xnor",  "xor",
	"aoi21", "aoi22", "aoi211", "aoi221", "aoi222", "aoi31", "aoi32", "aoi33",
	"oai21", "oai22", "oai211", "oai221", "oai222", "oai31", "oai32", "oai33"};

typedef enum linevalue LineValue;
enum linevalue  {v0, v1, vx};

typedef struct gate_struct GateType;
struct gate_struct  {
	LogicType		type;
	char			name[10];
	int			fanin, fanout,lead[max_fanout];
	GateType		*in[max_fanin], *out[max_fanout], *root;
	LineValue		val[2]; };

typedef struct gate_list GateList;
struct gate_list {
	GateType		*gate;
	GateList		*next; };

GateType	*PI[max_PI], *PO[max_PO],*SI[max_PI], *SO[max_PO];
int		PI_num=0, PO_num=0,SI_num=0, SO_num=0,gate_num;

char	iscas[11][5]={"17", "432", "499", "880", "1355", "1908", "2670", "3540",
		"5315", "6288", "7552"};

/********************************************************/
main(argc, argv)
  int   argc;
  char  *argv[];
{
FILE		*tdlf;
char		filename[20], str[150], temp[150], *tok;
int		h,i,j,k,l,m,n,x,a,b,c;
GateType	*p, *q, *r;
GateList	*Hg, *Lg, *Tg;


for(h=0;h<11;h++) {
	strcpy(filename,"c");
	strcat(filename,iscas[h]);
	printf("%5s ",filename);
	strcat(filename,"dag.tdl");
	if((tdlf=fopen(filename,"r"))==NULL){
		printf(" cannot be open!\n"); break;}

	do{	fgets(str,150,tdlf);
		sscanf(str,"%s      : C %d",temp,&i);
	}while( strcmp(temp,"MODULE") );

	do{ 	fgets(str,150,tdlf);
		tok=strtok(str,",;: ");
	}while(strcmp(tok,"INPUTS"));

	Hg=NULL;

	fgets(str,150,tdlf);
	tok=strtok(str,",;: ");
	while(strcmp(tok,"OUTPUTS")){
		if((PI[PI_num]=CALLOC(1,GateType))==NULL) mem_err();
		strcpy(PI[PI_num]->name, tok);
		PI[PI_num]->type=pi;
		PI[PI_num]->val[1]=vx;
		PI[PI_num]->fanout=0;

		if((Lg=CALLOC(1,GateList))==NULL) mem_err();
		Lg->next=NULL;
		Lg->gate=PI[PI_num++];
		if(Hg==NULL)	Hg=Lg;
		else	Tg->next=Lg;
		Tg=Lg;
		fgets(str,150,tdlf);
		tok=strtok(str,",;: ");
	}

	fgets(str,150,tdlf);
	tok=strtok(str,",;: ");
	while(strcmp(tok,"DESCRIPTION")) {
		if((PO[PO_num]=CALLOC(1,GateType))==NULL) mem_err();
		strcpy(PO[PO_num]->name, tok);
		PO[PO_num]->fanout=0;
		PO[PO_num]->val[1]=vx;
		if((Tg->next=CALLOC(1,GateList))==NULL) mem_err();
		Tg=Tg->next;
		Tg->next=NULL;
		Tg->gate=PO[PO_num++];
		fgets(str,150,tdlf);
		tok=strtok(str,",;: ");
	}

	do{	fgets(str,150,tdlf);
		tok=strtok(str,",;: ");
	} while(strcmp(tok,"DEFINE"));

	x=0;
	gate_num=0;
	fgets(str,150,tdlf);
	tok=strtok(str,"s:; ");
	while(strcmp(tok,"END")) {
		k=-1;
		while(strcmp(tok,Ltype[++k]));
		tok=strtok(NULL,"=");
		tok=strtok(NULL,")");
		i=-1;
	
		gate_num++;
		while(++i<PO_num) if(!strcmp(PO[i]->name,tok)) break;
		if(i==PO_num) {
			if((p=CALLOC(1,GateType))==NULL) mem_err();
			strcpy(p->name,tok);
			p->fanout=0;
			p->val[1]=vx;
			if((Tg->next=CALLOC(1,GateList))==NULL) mem_err();
			Tg=Tg->next;
			Tg->next=NULL;
			Tg->gate=p;
		}

	  	else	p=PO[i];
		p->type=k;
		if(k==xor||k==xnor) x++;

		tok=strtok(NULL,"(");
		tok=strtok(NULL,"=");
		tok=strtok(NULL,",); ");
		while(tok!=NULL) {
			Lg=Hg;
			while(Lg!=NULL) {
				if(!strcmp(Lg->gate->name,tok)) break;
				Lg=Lg->next;
			} 
			if(Lg==NULL) {printf("Error: %s is not a DAG.\n", filename); exit(1);}
			Lg->gate->lead[Lg->gate->fanout]=p->fanin;
			p->in[p->fanin++]=Lg->gate;
			Lg->gate->out[Lg->gate->fanout++]=p;
			tok=strtok(NULL,"=");
			tok=strtok(NULL,",); ");
		}
	
		fgets(str,150,tdlf);
		tok=strtok(str,"s:; ");
	}
	fclose(tdlf);

	a=PI_num;
	b=PO_num;
	
	Lg=Hg;
	i=0;
	l=0;
	while(Lg!=NULL){
		if(Lg->gate->type!=pi) i++;
		if(Lg->gate->fanout>l) l=Lg->gate->fanout;
		Lg=Lg->next;	
	}
	
	
	for(i=0;i<PO_num;i++) cutoff(PO[i],PO[i],v1);
	for(i=0;i<SO_num;i++) cutoff(SO[i],SO[i],v1);
	
	n=10000;
	m=0;
	k=0;
	for(i=0;i<PO_num;i++) {
		j=gate_count(PO[i]);
		k+=j;
		if(j>m) m=j;
		if(j<n) n=j;
	}
	for(i=0;i<SO_num;i++) {
		j=gate_count(SO[i]);
		k+=j;
		if(j>m) m=j;
		if(j<n) n=j;
	}

	printf("Circuit  &  PI  &  PO  & All  & XnOR & Part & pmin & pmax & pavg  & fanout_max\n");
	printf("%8s & %4d & %4d & %4d & %4d & %4d & %4d & %4d & %5.2f & %d \n", iscas[h], a, b, k, x, SO_num+PO_num, n, m, (float)k/(SO_num+PO_num), l);


	/*
	printf("PO-Tree:\n");
	for(i=0	;i<PO_num;i++) {traversal(PO[i]); printf("\n");}
	printf("\n");
	printf("Internal Tree:\n");
	for(i=0;i<SO_num;i++) {traversal(SO[i]); printf("\n");}
	printf("\n");


	for(i=SO_num-1;i>=0;i--){
		if(SO[i]->val[1]==vx) set_tree(SO[i],v1);		
		c=1;
		for(j=1;j<SO[i]->fanout;j++)
			if(SO[i]->out[j]->val[0]!=SO[i]->out[0]->val[0]||SO[i]->out[j]->val[1]!=vx) {
				c=0;
				break;
			}
		if(c){
			for(j=0;j<SO[i]->fanout;j++){
				if(SO[i]->out[j]->val[1]==vx){
					p=SO[i]->out[j]->root;
					if(SO[i]->val[1]==SO[i]->out[j]->val[0]) set_tree(p,1-p->val[0]);
					else set_tree(p,p->val[0]);
				}
				free(SO[i]->out[j]->in[SO[i]->lead[j]]);
				SO[i]->out[j]->in[SO[i]->lead[j]]=SO[i];			
			}
			SO[i]=NULL;
		}
	}

	n=10000;
	m=0;
	c=0;
	for(i=0;i<PO_num;i++) {
		j=dag_gate_count(PO[i]);
		if(j>m) m=j;
		if(j<n) n=j;
	}
	for(i=0;i<SO_num;i++) if(SO[i]!=NULL) {
		c++;
		j=dag_gate_count(SO[i]);
		if(j>m) m=j;
		if(j<n) n=j;
	}
	printf("Circuit  &  PI  &  PO  & All  & XnOR & Part & pmin & pmax & pavg  & fanout_max\n");
	*/
	
	printf("%8s & %4d & %4d & %4d & %4d & %4d & %4d & %4d & %5.2f & %d \n", iscas[h], a, b, k, x, c+PO_num, n, m, (float)k/(c+PO_num), l);

	/*
	printf("PO-Tree:\n");
	for(i=0;i<PO_num;i++) {traversal(PO[i]); printf("\n");}
	printf("\n");
	printf(	"Internal Tree:\n");
	for(i=0;i<SO_num;i++) if(SO[i]!=NULL) {traversal(SO[i]); printf("\n");}
	printf("\n");
	*/	
	}
}	


set_tree(p,v)
GateType *p;
LineValue v;
{
int i;

p->val[1]=v;
if(p->type!=pi) for(i=0;i<p->fanin;i++){
	set_tree(p->in[i],1-v);
}
return(0);
}






cutoff(r,g,v)
GateType *r,*g;
LineValue v;
{
int i,j;
char subname[3];
GateType *p, *q;

strcpy(subname,".?");
g->val[0]=v;
g->root=r;
if(g->type!=pi) for(i=0;i<g->fanin;i++){
	p=g->in[i];
	if(p->fanout>1) {
		for(j=0;j<p->fanout;j++) {
			if((q=CALLOC(1,GateType))==NULL) mem_err();
			q->type=pi;
			q->root=r;
			q->val[0]=1-v;
			q->val[1]=vx;
			subname[1]=(char)('1'+j);
			strcpy(q->name,p->name);
			strcat(q->name,subname);
			q->fanout=1;
			p->out[j]->in[p->lead[j]]=q;
			SI[SI_num++]=q;
		}
		if(p->type!=pi) SO[SO_num++]=p;
	}
	else  cutoff(r,p,1-v);
}
return(0);
}


traversal(g)
GateType *g;
{
int	i;

if(g==NULL) {printf("NULL pointer "); return(0);}
printf("%s:%d",g->name,g->val[0]);
if(g->type!=pi) {
	printf("(");
	for(i=0;i<g->fanin;i++) {
		traversal(g->in[i]);
		if(i<g->fanin-1) printf(",");
	}
	printf(")");
}
return(0);
}


int gate_count(g)
GateType *g;
{
int	i, sum;

sum=0;
if(g==NULL) {printf("NULL pointer "); return(0);}
if(g->type!=pi) {
	sum=1;
	for(i=0;i<g->fanin;i++) {
		sum+=gate_count(g->in[i]);
	}
}
return(sum);
}


int dag_gate_count(g)
GateType *g;
{
int	i, sum;

sum=0;
if(g==NULL) {printf("NULL pointer "); return(0);}
if(g->type!=pi&&g->val[0]!=vx) {
	sum=1;
	g->val[0]=vx;
	for(i=0;i<g->fanin;i++) {
		sum+=dag_gate_count(g->in[i]);
	}
}
return(sum);
}


subfile()
{
int 	i;
char	filename[20];
FILE	*fp;

for(i=0;i<PO_num;i++){
	strcpy(filename,PO[i]->name);
	strcat(filename,".tdl");
	if((fp=fopen(filename,"w"))==NULL) {
		printf("Create File Error!\n");
		exit(1);
	}
	printf("Creating Fan-out Free Tree: %s\n", filename); /*
	fprintf(fp,"MODULE      : %s;\n", PO[i]->name); */
	fprintf(fp,"MODULE      : C 17;\n");
	fprintf(fp,"INPUTS      :\n");
	selectleaf(PO[i]);
	printleaf(fp);
	fprintf(fp,"OUTPUTS     :\n");
	fprintf(fp,"  %s;\n",PO[i]->name);
	fprintf(fp,"DESCRIPTION : TDL file partitioned;\n");
	fprintf(fp,"USE         :\nDEFINE      :\n");
	print_netlist(fp,PO[i]);
	fprintf(fp,"END         : MODULE;\n");
	fclose(fp);
}
return(0);
}

selectleaf(g)
GateType 	*g;
{
int	i;

if(g->type==pi) g->type=-1;
else for(i=0;i<g->fanin;i++) selectleaf(g->in[i]);
return(0);
}

printleaf(fp)
FILE	*fp;
{
int	i,j;

j=0;
for(i=0;i<PI_num;i++) if(PI[i]->type==-1) {
	PI[i]->type=pi;
	if(j) fprintf(fp,",\n");
	fprintf(fp,"%s",PI[i]->name);
	j=1;
}
fprintf(fp,";\n");
return(0);
}


print_netlist(fp,g)
GateType	*g;
FILE		*fp;
{
int	i;

fprintf(fp,"%ss_%s(q=%s) = %ss(",Ltype[g->type],g->name,g->name,Ltype[g->type]);
for(i=0;i<g->fanin;i++) {
	fprintf(fp,"i%d=%s",i,g->in[i]->name);
	if(i<g->fanin-1) fprintf(fp,",");
}	
fprintf(fp,");\n");
for(i=0;i<g->fanin;i++) if(g->in[i]->type!=pi) print_netlist(fp,g->in[i]);
return(0);
}

mem_err()
{
printf("Not enough memory.\n");
}