/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit :  Synthetiseur de FSM                                       */
/*    Fichier :  syf_asp.c                                                  */
/*                                                                          */
/*    (c) copyright 1992 Laboratoire MASI equipe CAO & VLSI                 */
/*    Tous droits reserves                                                  */
/*    Support : e-mail cao-vlsi@masi.ibp.fr                                 */
/*                                                                          */
/*    Auteur(s) :  C. Sarwary                            le : 15/03/1992     */
/*                                                                          */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/***************************************************************************/

#include <stdio.h>
#include <math.h>
#include MUT_H
#include LOG_H
#include "../beh104/beh104.h"
#include "syf_auto.h"
#include "syf_must.h"
#include "../util/util.h"
#include "syf_asp.h"
#include "syf_beh2fsm.h"

extern int syf_rom, syf_pseudorom ;
/*-----------------------------------------------------------------------------
nc_genGroup	: Genere des goupes d'etats selon le motif donne.
---------------------------------------------
parametres	: int motif : FUSION -> regroupement des etats permettant
				une fusion .
			    : FACT -> regroupement des etats permettant
				une factorisation .
--------------------------------------------
return		: liste des groupes generes .
------------------------------------------------------------------------------*/
p_groupe aspNcode(tabPoidEtat)
int *tabPoidEtat;
{
p_groupe *tabGrp ;
p_groupe orderGroup;
pTrans trans, trans2 ;
chain_list *listGrp ;
chain_list *head ;
int *tabState ;
pState state;
pNode bdd1, bdd2 ;
int i,j;
int  *tabPoidGroup, *tabCode ;
int *tabPoidFutur;


/**** Pour le moment seulement la fusion ******/
if(!(tabState = (int *)mbkalloc(sizeof(int) * autoSys->numberState)))
	{
	printf("nc_genGroup : allocation impossible\n") ;
	exit(-1) ;
	}

state = autoSys->state ;
listGrp = NULL ;
for(i = 0; i < autoSys->numberState; i++)
	{
	head = NULL ;
	trans = state->trans ;
	for(j = 0; j < autoSys->numberState; j++)
		*(tabState + j) = EMPTY ;
	while(trans)
		{
		if(!existInt(tabState,trans->sPlabel))
			{
			bdd1 = trans->bdd ;
			trans2 = trans ;
			while(trans2)
				{
				if(!existInt(tabState,trans2->sPlabel))
					{
					bdd2 = trans2->bdd ;
					if(bdd1 == bdd2)
						{
						head = addchain(head,trans2->sPlabel) ;	
						addTabInt(tabState,trans2->sPlabel) ;
						}	
					}
				trans2 = trans2->next ;
				}
			if(head != NULL && head->NEXT != NULL)
				listGrp = addchain(listGrp,head) ;
			}
		trans= trans->next ;
		}
	state++ ;
	}
/*
head = NULL ;
for(i = 0; i < autoSys->numberOut; i++)
	{
	state = autoSys->state ;
	out = state->locOut ;
	for(k = 0; k < i; k++)
		out = out->next ;
	outBdd = out->bdd ;
	for(j = 0; j < autoSys->numberState; j++)
		{
		out2 = state->locOut ;
		for(k = 0; k < i; k++)
			out2 = out2->next ;
		if(outBdd == out2->bdd)
			head = addchain(head,state->label) ;	
		state++ ;
		}
	}
*/
/*nc_displayGrp(listGrp) ;*/
tabGrp = chain_list2group(listGrp) ;
tabPoidEtat = asp_poidEtat() ;
tabPoidGroup = asp_poidGroup(tabGrp,tabPoidEtat) ;
/*tabCode = asp_codage(tabGrp,tabPoidGroup) ;*/
     orderGroup = asp_order(tabGrp, tabPoidGroup);

return(orderGroup) ;
}
/*-----------------------------------------------------------------------------
asp_addStackGroup : ajoute nouveau groupe correspondant au STACK, 
---------------------------------------------
parametres	: pteur sur table des groupes .
--------------------------------------------
return		: nouveau table de groupe .
------------------------------------------------------------------------------*/
asp_addStackGroup(tabGroup)
p_groupe **tabGroup ;
{
p_groupe groupReturnState = NULL ;
pStack stack;
p_groupe *tabG ;

stack = autoSys->stack;
  while(stack)
   {
   if (stack->ctrl == PUSH)
   	  groupReturnState= addTogroup(groupReturnState,stack->returnStatelabel) ;
   stack = stack->next;
   }
tabG = *tabGroup ;
while(*tabG)
	tabG++ ;

*(tabG) = groupReturnState;
*(tabG + 1) = NULL;
}

/*-----------------------------------------------------------------------------
asp_addStackPoid : ajoute le poid correspondant au STACK, 
					Le cout d'un mux 1 parmi 3 = 6.
					Le cout d'un bascule D = 1.
					Le cout d'un registre M/S = 2.
---------------------------------------------
parametres	: pteur table des poids .
--------------------------------------------
return		: nouveau table de poid .
------------------------------------------------------------------------------*/
asp_addStackPoid(tabPoid)
int **tabPoid ;
{
int *tabP ;
int coutReg ;
int numBitFix, poidStack ;

tabP = *tabPoid ;
while(*tabP)
	tabP++ ;

if(autoSys->typeReg == REG_D)
	coutReg = 1 ;
else
	coutReg = 2 ;
numBitFix = numStatePush() ;
/*printf("NUMBITFIX : %d\n",numBitFix) ;*/
poidStack = autoSys->sizeStack * numBitFix*(6 + coutReg) ;

*tabP = poidStack ;
*(tabP + 1) = 0 ;
}

/*-----------------------------------------------------------------------------
asp_genGroup	: Genere des goupes d'etats .
---------------------------------------------
parametres	: rien .
--------------------------------------------
return		: tables des groupes generes .
------------------------------------------------------------------------------*/
p_groupe *asp_genGroup()
{
p_groupe *pGroup ;
p_groupe *group ;
pState state;
pStack stack;
pTrans trans;
pLocOut locOut;
int i;

if(!(pGroup = (p_groupe *) mbkalloc(NB_GROUP * sizeof(p_groupe))))
	{
	printf("asp.c, asp_genGroup : allocation impossible\n") ;
	exit(-1) ;
	}

for(i = 0; i < NB_GROUP; i++)
	*(pGroup+i) = NULL ;
state = autoSys->state ;
group = pGroup + autoSys->numberOut;
numberGroup = autoSys->numberOut;

if(autoSys->stack)
{
stack = autoSys->stack;
          *group = NULL;
          *(group+1) = NULL;
  while(stack)
   {
      if(stack->ctrl == PUSH)
       *(group)= addTogroup(*group,stack->curentStatelabel) ;
      else if (stack->ctrl == POP)
       *(group+1)= addTogroup(*(group+1),stack->curentStatelabel) ;
     stack = stack->next;
   }
group = group +2;
     numberGroup += 2;
     numberGroup += 2;/*1 pour Stack, et 1 pour assurer */
}

for(i=0; i < autoSys->numberState; i++)
	{
    *group = NULL;
	trans = state->trans ;
	while(trans)
		{
        if (trans->sPlabel !=-1)
        	{
	    	*group = addTogroup(*group,trans->sPlabel) ;
        	}
        trans = trans->next;
       	}
	if(!syf_rom)
		{
        locOut = state->locOut;
        while(locOut)
           	{
			if(syf_pseudorom)
				{
				trans = state->trans ;
				while(trans)
					{
        			if (trans->sPlabel !=-1)
	    				*(pGroup + locOut->label)=addTogroup(*(pGroup + locOut->label),trans->sPlabel);
        			trans = trans->next;
       				}
				}
			else
	    		*(pGroup + locOut->label)= addTogroup(*(pGroup + locOut->label),i) ;
           	locOut = locOut->next;
           	}
		}
        group++ ;
        numberGroup ++;
        state++;
        }
	if(numberGroup > NB_GROUP)
		{
		printf("syf : numberGroup > NB_GROUP\n") ;/* changer dans ce cas la
											valeur define NB_GROUP */
		exit(-1) ;
		}
return(pGroup) ;
}
/*-----------------------------------------------------------------------------
asp_orderGroupElement	: ordonne les goupes d'etats .
---------------------------------------------
parametres	: pGroup,tabPoidEtat .
--------------------------------------------
return		: tables des groupes ordonnes .
------------------------------------------------------------------------------*/
p_groupe *asp_orderGroupElement(pGroup,tabPoidEtat)
p_groupe *pGroup;
int *tabPoidEtat;
{
int i;

for(i=0; i < numberGroup; i++)
{
pGroup[i] = asp_orderGroup(pGroup[i],tabPoidEtat);
}
return(pGroup);
}
/*-----------------------------------------------------------------------------
asp_poidEtat	: Genere la tabole des poids des Etats .
---------------------------------------------
parametres	: rien .
--------------------------------------------
return		: tables des groupes generes .
------------------------------------------------------------------------------*/
int *asp_poidEtat()
{
int *tabPoidEtat ,i;
pState state;

if(!(tabPoidEtat = (int *)mbkalloc((autoSys->numberState +1) * sizeof(int))))
	{
	printf("asp.c : allocation impossible\n") ;
	exit(-1) ;
	}

state = autoSys->state ;
for(i = 0; i< autoSys->numberState; i++)
  {
  *(tabPoidEtat + i) = numberAtomExpr(state->abl) ; 
   state++;
  }
return(tabPoidEtat) ;
}

/*-----------------------------------------------------------------------------
asp_poidGroup	: Genere la tabole des poids des Groupes .
---------------------------------------------
parametres	: pointeur sur la table des groupes .
		  pointeur sur la table des poids des etats .
--------------------------------------------
return		: tables des groupes generes .
------------------------------------------------------------------------------*/
int *asp_poidGroup(pGroup,tabPoidEtat)
p_groupe *pGroup;
int *tabPoidEtat;
{
int *tabPoidGroup ;
int i, nbEtatG ;
p_groupe group;

if(!(tabPoidGroup = (int *) mbkalloc(numberGroup * sizeof(int))))
	{
	printf("asp.c : allocation impossible\n") ;
	exit(-1) ;
	}

  for(i = 0; i< numberGroup; i++)
   {
   nbEtatG = 0 ;
   tabPoidGroup[i] = 0 ;
   group = pGroup[i];
    while(group)
    { 
    nbEtatG++ ;
    tabPoidGroup[i] += tabPoidEtat[group->label] ;
    group = group->next;
    if(group == NULL)
		tabPoidGroup[i] = tabPoidGroup[i]/nbEtatG ;
	/*printf("Groupe : %d, poid : %d\n",i, tabPoidGroup[i]) ;*/
    }
   }
/*asp_displayGroupPoid(pGroup,tabPoidGroup) ;*/
return(tabPoidGroup);
}

/*-----------------------------------------------------------------------------
asp_codage	: effectue le codage .
---------------------------------------------
parametres	: la table des groupes et la table de leurs poids .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
int *asp_codage(pGroup,tabPoidGroup)
p_groupe *pGroup;
int *tabPoidGroup;
{
p_groupe orderedGroup;
p_groupe orderedG;
p_groupe group;
int remainBit;
int numBit;
int *tabCode;
pCode code;
pCode dc;
int codeVal;
int Val;
int i,k;

numBit = autoSys->numberReg ;
/*
printf("bit[%d] = %d\n",numBit,bit[numBit]) ;
*/
if(!(tabCode = (int *) mbkalloc(bit[numBit] * sizeof(int))))
        {
        printf("asp.c : not enough memory\n") ;
        exit(-1) ;
        }

     orderedGroup = asp_order(pGroup, tabPoidGroup);

code = autoSys->code;
/*
for(i = 0; i < autoSys->numberState; i++)
	printf("%d : code->%d\n",i,(code + i)->code) ;
*/
 for(remainBit = numBit; remainBit > 0; remainBit--)
 {
   orderedG = orderedGroup;
     for(i = 0; i < bit[numBit]; i++)
       tabCode[i] = 0;
   i = 0;
   while((orderedG)&&(i < bit[numBit - 1]))
   {
     group = pGroup[orderedG->label];
      while((group)&&(i < bit[numBit - 1]))
      {
        codeVal = (code + group->label)->code;
        if ((codeVal < bit[numBit - remainBit])&&
            (tabCode[codeVal] < bit[remainBit -1]))
        {
         (code + group->label)->code += bit[numBit - remainBit];
         tabCode[codeVal]++;
         i++;
        } 
       group = group->next;
     }
     orderedG = orderedG->next; 
   }
 }
code = autoSys->code;
for(i = 0; i< autoSys->numberState; i++)
{
  code->code = (code->code)^(bit[numBit]-1);
  code++;
}
tabCode = makeTabCode(tabCode);
return(tabCode);
}

/*-----------------------------------------------------------------------------
asp_order	: cree une liste de groupes selon l'ordre de complexite max.
---------------------------------------------
parametres	: la table des groupes , la table des poids .
--------------------------------------------
return		: la liste ordonee .
------------------------------------------------------------------------------*/
p_groupe asp_order(pGroup, tabPoidGroup)
p_groupe *pGroup;
int *tabPoidGroup;
{
p_groupe group;
p_groupe groupAux;
p_groupe orderedGroup;
int i, FIN=0;

orderedGroup = addTogroup(NULL, 0);
for( i = 1; i < numberGroup; i++)
  {
  FIN =0;
   group = orderedGroup;
      if ( tabPoidGroup[i] > tabPoidGroup[group->label]) 
      {
      orderedGroup = addTogroup(orderedGroup, i);
      FIN =1;
      }
    while((group->next)&&(FIN == 0))
    {   
      if ( tabPoidGroup[i] > tabPoidGroup[group->next->label]) 
      { 
        group->next = addTogroup(group->next, i);
        FIN = 1;
      }
     else   group = group->next; 
    }
  if ( FIN == 0) 
      group->next = addTogroup(NULL,i); 
  }
return(orderedGroup);
}      


/*-----------------------------------------------------------------------------
asp_orderGroup	: ordonne une liste d'elements selon l'ordre de complexite max.
---------------------------------------------
parametres	: le groupe , la table des poids .
--------------------------------------------
return		: la liste ordonee .
------------------------------------------------------------------------------*/
p_groupe asp_orderGroup(InorderedGroup, tabPoidElement)
p_groupe InorderedGroup;
int *tabPoidElement;
{
p_groupe group;
p_groupe orderedGroup;
int  FIN=0;

if(!InorderedGroup)
      return(NULL);

orderedGroup = addTogroup(NULL, InorderedGroup->label);
 InorderedGroup = InorderedGroup->next;
 while(InorderedGroup)
  {
  FIN =0;
   group = orderedGroup;
      if ( tabPoidElement[InorderedGroup->label] > tabPoidElement[group->label]) 
      {
      orderedGroup = addTogroup(orderedGroup, InorderedGroup->label);
      FIN =1;
      }
    while((group->next)&&(FIN == 0))
    {   
      if ( tabPoidElement[InorderedGroup->label] > tabPoidElement[(group->next)->label]) 
      { 
        group->next = addTogroup(group->next, InorderedGroup->label);
        FIN = 1;
      }
     else   group = group->next; 
    }
  if ( FIN == 0) 
      group->next = addTogroup(NULL,InorderedGroup->label); 
  InorderedGroup = InorderedGroup->next;
  }
return(orderedGroup);
}      

/*-----------------------------------------------------------------------------
asp	: fonction de codage selon ASP.
---------------------------------------------
parametres	: rien .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
void asp(ORDER,AME)
int ORDER;
int AME;
{
p_groupe *pGroup;
p_groupe Se;
int *tabPoidEtat;
int *tabPoidFutur;
int *tabPoidGroup;
 int *tabCode;
 int selectLabel,i;
 int *nwS,*nwO;
int *we;

if(!(nwS = (int *)mbkalloc((autoSys->numberState + 1)*(autoSys->numberState +1)  * sizeof(int ))))
   {
   printf("allocation impossible \n");
   exit(-1);
   }
if(!(nwO = (int *)mbkalloc((autoSys->numberState + 1)*(autoSys->numberOut) * sizeof(int ))))
   {
   printf("allocation impossible \n");
   exit(-1);
   }

 autoSys->dc  = autoSys->code + autoSys->numberState;
tabPoidEtat = asp_poidEtat();
/*asp_displayPoidEtats(tabPoidEtat) ;*/
pGroup = asp_genGroup();
if (ORDER == 1)
	pGroup = asp_orderGroupElement(pGroup,tabPoidEtat);
tabPoidGroup = asp_poidGroup(pGroup,tabPoidEtat);

/*
asp_displayGroupPoid(pGroup,tabPoidGroup) ;
asp_addStackGroup(&pGroup) ;
asp_displayGroupPoid(pGroup,tabPoidGroup) ;
asp_addStackPoid(&tabPoidGroup) ;
asp_displayGroupPoid(pGroup,tabPoidGroup) ;
*/

tabCode = asp_codage(pGroup,tabPoidGroup);
/*asp_displayGroupPoid(pGroup,tabPoidGroup) ;*/
if(AME)
{
printf("State Encoding amelioration\n");
mustPoids(nwS,nwO);
we = mustCalcul(nwS,nwO);
tabPoidFutur = PoidsFutur();
for(i=0; i< AME; i++)
{
Se = stateGeneration();
while(Se)
 {
 selectLabel = codeModification(we,tabPoidEtat,tabPoidFutur,tabCode,Se);
 Se = delFromgroup(Se,selectLabel);
 }
  printf("fin du %dieme iteration\n",i);
 }
}
}
      
int *makeTabCode(tabCode)
int *tabCode;
{
int i,numBit;
int dcLabelState;
pCode code;

numBit = autoSys->numberReg ;

 code = autoSys->code;
 
 for(i = 0; i< bit[numBit];i++)
  tabCode[i] = bit[numBit];  

 for(i=0; i< autoSys->numberState;i++)
  {
  /*
  printf("%d : %d\n",i,(code + i)->code) ;
  fflush(stdout) ;
 	*/ 
  tabCode[(code + i)->code] = i;  
  }
 dcLabelState = autoSys->numberState;
 i =0;
 while((dcLabelState< bit[numBit])&&(i<bit[numBit]))
 {
  if (tabCode[i] == bit[numBit]) 
     {
      tabCode[i] = dcLabelState;
      (code+dcLabelState)->code = i;
      dcLabelState++;
     }
  i++;
}
  return(tabCode);
}
/*-----------------------------------------------------------------------------
asp_displayPoidEtats : visualise le poid de tous les etats.
---------------------------------------------
parametres	: table des poids .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
asp_displayPoidEtats(tabPoid)
int *tabPoid;
{
int i ;

printf("*********** DISPLAY TABPOID **************\n") ;
for(i = 0; i < autoSys->numberState; i++)
	printf("%s; poid : %d\n",(autoSys->state + i)->name,*(tabPoid + i)) ;
printf("*********** FIN DISPLAY TABPOID **************\n") ;
}
/*-----------------------------------------------------------------------------
asp_displayGroup : visualise les groupes.
---------------------------------------------
parametres	: table des groupes, table des poids .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
asp_displayGroupPoid(tabGroup,tabPoid)
p_groupe *tabGroup ;
int *tabPoid ;
{
p_groupe group ;
p_groupe gState ;
int i =0 ;

printf("*********** DISPLAY TABGROUP **************\n") ;
group = tabGroup[0] ;
while(group)
	{
	gState = group ;
	printf("Groupe : %d; POID : %d\n",i,*(tabPoid + i)) ;
	while(gState)
		{
		printf("\t%s\n",(autoSys->state + gState->label)->name) ;
		gState = gState->next ;
		}
	i++ ;
	group = tabGroup[i] ;
	}
printf("*********** FIN DISPLAY TABGROUP **************\n") ;
}
/*-----------------------------------------------------------------------------
numStatePush : donne le numBit de nombre d'etats susceptible d'etre mis 
				dans la pile.
			*********** ATTENTION **********
				Si il y a un seul etat susceptible d'etre mis dans la pile
				on renvoie 0, ce qui vaut dire que le poid de la pile est
				nul.
---------------------------------------------
parametres	: rien .
--------------------------------------------
return		: le nombre d'etats. .
------------------------------------------------------------------------------*/
int numStatePush()
{
pStack stack ;
int label, numState, numBit ;
chain_list *listLab, *addLab() ;

numState = 0 ;
listLab = NULL ;
stack = autoSys->stack ;
while(stack)
	{
	/*printf("entree , STACK numBit\n") ;*/
	if(stack->ctrl == PUSH)
		{
		label =  stack->returnStatelabel ;
		listLab = addLab(listLab,label,&numState) ;
		}
	stack = stack->next ;
	}
if(numState == 1)/***** si un seul etats dans la pile poid = 0 *****/
	return(0) ;
numBit = NUMBER_BIT(numState) ;
return(autoSys->numberReg - numBit) ;
}
/*-----------------------------------------------------------------------------
addLab 		: ajout un label dans une chaine list, si il n'y est pas deja
			  incremente le nombre de label.
---------------------------------------------
parametres	: rien .
--------------------------------------------
return		: le nombre d'etats. .
------------------------------------------------------------------------------*/
chain_list *addLab(listLab,label,number)
chain_list *listLab;
int label ;
int *number ;
{
chain_list *list ;

list = listLab ;
while(listLab)
	{
	if((int)listLab->DATA == label)
		{
		return(list) ;
		}
	listLab = listLab->NEXT ;
	}
list = addchain(list,label) ;
(*number)++ ;
/*printf("number : %d\n",*number) ;*/
return(list) ;
}
/*-----------------------------------------------------------------------------
optimCodForStack : optimise un codage deja effectue' pour tenir compte de
					pile . 
---------------------------------------------
parametres	: circuit .
--------------------------------------------
return		: table de label des etats .
------------------------------------------------------------------------------*/
optimCodForStack(pC)
pCircuit pC ;
{
int comBitMax,comBit ;
int numStatePush,i,j,changePossible ;
chain_list *listPush,*givPushState() ;
int **tabStateBit ;
int **nCodState ;
unsigned int *tabCout ;
int numStateBit() ;
int b, numSBit ;
unsigned int *givCoutForEach() ;
int *givCoutForEachPerState() ;
unsigned int initCout ;
int change,mode ;


listPush = givPushState(&numStatePush) ;
if(syf_trace)
	{
	printf("numStatePush : %d\n",numStatePush) ;
	printf("******* Les etats de PUSH\n *********") ;
	displayListState(listPush) ;
	fflush(stdout) ;
	}
if(numStatePush == 1)
	return ;
tabStateBit = (int **)mbkalloc(sizeof(int *) * (2 * autoSys->numberReg +1)) ;
for(i = 0; i < 2 * autoSys->numberReg; i++)
	{
	*(tabStateBit + i)=(int *)mbkalloc((sizeof(int))*((autoSys->numberState) + 1));
	for(j = 0; j < ((autoSys->numberState)+1); j++)
		{
		*((*(tabStateBit+i))+j) = -1 ;
		}
	}
comBitMax = (autoSys->numberReg) - (NUMBER_BIT(numStatePush)) ;
makeTabForEachBit(tabStateBit,listPush,&comBit) ;
if(syf_trace)
	{
	printf("comBitMax : %d, comBit : %d\n",comBitMax,comBit) ;
	printf("**** LES ETATS DE PUSH PAR ORDRE DE BIT A CHANGER FINAL*****\n") ;
	displayTabStateBit(tabStateBit) ;
	fflush(stdout) ;
	}

if(comBit == comBitMax)
	{
	if(syf_trace)
		printf("******** Codage deja optimal pour la pile *********\n") ;
	return ;
	}


nCodState = (int **)mbkalloc(sizeof(int *) * autoSys->numberReg) ;
for(i = 0; i < autoSys->numberReg; i++)
	{
	*(nCodState+i)=(int *)mbkalloc(sizeof(int) * (autoSys->numberState+1));
	for(j = 0; j < (autoSys->numberState+1);j++)
		{
		*(*(nCodState+i)+j) = -1 ;
		}
	}

for(b = 0; b < autoSys->numberReg; b++)
	{
	if(*(tabStateBit + b) != NULL)
		{
		numSBit = numStateBit(*(tabStateBit + b));
		j = 1 ;
		for(i = 0; i < numSBit && j; i++)
			{
			*(*(nCodState + b)+i)=givOtherCodState(listPush,*(*(tabStateBit+b)+i),b);
			if(*(*(nCodState + b) + i) == -1)
				{/* code existe deja dans les etats de push */
				j = 0 ;
				*(tabStateBit + b) = NULL ;
				}
			}

			/*
		if(changePossible)
			{
			printf("CHANGEMENTS POSSIBLES :\n") ;
			for(i = 0; i < numSBit; i++)
				printf("%s -> %s\n",(autoSys->state + *(*(tabStateBit+b)+i))->name,(autoSys->state + nCodState[i])->name) ;
			}
			*/
			/*
		printf("changePossible : %d\n",changePossible) ;
		if(changePossible)
			{
			printf("change\n") ;
			for(i = 0; i < numSBit; i++)
				changeCod(nCodState[i],*(*(tabStateBit+b)+i)) ;
			comBit++ ;
			printf("fin change\n") ;
			}
			*/	
		}
	}
	/**** a faire autant de fois qu'il y a de comBit ****/
if(syf_trace)
	{
	printf("*********** tables Des nouveuax codes ***********\n") ;
	displayTabStateBit(nCodState) ;
	fflush(stdout) ;
	}
i = 0 ;
while(comBit <= comBitMax && i < autoSys->numberReg)
	{
	/*tabCout = givCoutForEachPerState(tabStateBit,nCodState,&initCout) ;
	mode = 0 ;*/
	tabCout = givCoutForEach(tabStateBit,nCodState,&initCout,pC) ;
	mode = 1 ;
	if(syf_trace)
		printf("cout initial : %u\n",initCout) ;
	change = changeBestCod(tabCout,tabStateBit,nCodState,initCout,mode) ;
	if(change)
		comBit++ ;
	i++ ;
	}
}
/*-----------------------------------------------------------------------------
changeBestCod : Choisit le changement de code de cout minimum et effectue
				le changement.
---------------------------------------------
parametres	: table des couts, table de table des codes1, et table de code2 .
--------------------------------------------
return		: 1 si changement, 0 sinon .
------------------------------------------------------------------------------*/
changeBestCod(tabCout,tab1,tab2,initCout,mode)
unsigned int *tabCout ;
int **tab1, **tab2 ;
unsigned int initCout ;
int mode ;
{
/* Cette fonction n'est pas utilisable pour le cout en entier obtenu par 
givCoutPerState() refaire une autre fonction pour cette derniere. */
int i, j ;
unsigned int couti ;
unsigned int cout ;
int coutStack ;

coutStack = givStackWeight() ;
coutStack = coutStack/5 ;
if(mode == 1)
	cout = initCout + coutStack ;
else
	cout = coutStack ;

/* momentanement le cout de stack est divise par 5 c'est du au 
decalage du calcul des poids */
if(syf_trace)
	{
	printf("stack cost : %d\n",coutStack) ;
	printf("initial cost : %u\n",cout) ;
	}

j = -1 ;
for(i = 0; i < autoSys->numberReg; i++)
	if(tabCout[i] != 0 && tabCout[i] < cout)
		{
		couti = tabCout[i] ;
		j = i ;
		break ;
		}
for(; i < autoSys->numberReg; i++)
	if(tabCout[i] <= couti && tabCout[i] < cout && tabCout[i] != 0)
		{
		couti = tabCout[i] ;
		j = i ;
		}

if(j == -1)
	{
	if(syf_trace)
	   printf("******* No optimisation possible for stack **********\n") ;
	return(0) ;
	}
i = 0 ;
while(*(tab1[j] + i) != -1)
	{
	changeCod(*(tab1[j] + i),*(tab2[j] + i)) ;
	i++ ;
	}
/*#ifndef ARCHI_PC*/
free(tab1[j]) ;
/*#endif*/
tab1[j] = NULL ;
return(1) ;
}
/*-----------------------------------------------------------------------------
changeCod : change deux code entre eux.
---------------------------------------------
parametres	: les 2 codes .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
changeCod(state1, state2)
int state1, state2;
{
int code1;

if(syf_trace)
	{
	printf("--->Change Codes : st1 : %s, code = %d, st2 : %s, code = %d\n",
			(autoSys->state + state1)->name, (autoSys->code + state1)->code, 
			(autoSys->state + state2)->name, (autoSys->code + state2)->code) ;
	fflush(stdout) ;
	}
code1 = ((autoSys->code) + state1)->code ;
((autoSys->code) + state1)->code = ((autoSys->code) + state2)->code ;
((autoSys->code) + state2)->code = code1 ;
}
/*-----------------------------------------------------------------------------
givCoutForEachPerState : Calcule le cout pour chaque changement de codage 
						 demande' et renvoie la table des couts. et le cout initial.
---------------------------------------------
parametres	: tab1 : table de table des etats a changer.
			  tab2 : table de table des etats de change.
			  pointeur sur le cout initial a remplir.
--------------------------------------------
return		: table des couts .
------------------------------------------------------------------------------*/
int *givCoutForEachPerState(tab1, tab2, initialCout)
int **tab1, **tab2, *initialCout ;
{
int i,cout ;
int *tabCout ;
int *tabCod ;
int *state1, *state2 ;
int *tabPoidEtat;
int *tabPoidFutur;
int *nwS,*nwO;
int *wi;
int *givTabCod() ;

nwS = (int *)mbkalloc((autoSys->numberState +1 )*(autoSys->numberState +1)  * sizeof(int )) ;
nwO = (int *)mbkalloc((autoSys->numberState + 1)*(autoSys->numberOut) * sizeof(int )) ;
 
mustPoids(nwS,nwO) ;
wi = mustCalcul(nwS,nwO) ;
tabPoidFutur = PoidsFutur() ;
tabPoidEtat = asp_poidEtat() ;

tabCod = givTabCod() ;
*initialCout = 0 ;
*initialCout = calculCout(wi,tabPoidEtat,tabPoidFutur) ;

if(!(tabCout = (int *)mbkalloc(sizeof(int) * autoSys->numberReg)))
	{
	printf("givCoutForEach : allocation impossible\n") ;
	exit(-1) ;
	}
for(i = 0; i < autoSys->numberReg; i++)
	{
	tabCout[i] = -1 ;
	}

for(i = 0; i < autoSys->numberReg; i++)
	{
	state1 = *(tab1 + i) ;
	state2 = *(tab2 + i) ;
	if(state1 != NULL)
		{
		/*printf("state1 : %d, state2 : %d\n",*state1,*state2) ;*/
		while(*state1 != -1)
			{
			if(*state2 != -1)
				{
				 cout = tabCout[i] ;
				tabCout[i] += calculCoutState(wi,tabPoidEtat,tabPoidFutur,*state1,*state2,tabCod) ;
				if(tabCout[i] == cout)
					tabCout[i]-- ;
			/*	printf("cout[%d]= %d,changement entre : %s,%s\n",i,tabCout[i],(autoSys->state + (*state1))->name,(autoSys->state + (*state2))->name) ;*/
				}
			else
				{
				printf("Error : givCoutForEach\n") ;
				fflush(stdout) ;
				exit(-1) ;
				}
			state1++ ;
			state2++ ;
			}
		}
	}
for(i = 0; i < autoSys->numberReg; i++)
	printf("cout[%d] : %d\n",i,tabCout[i]) ;

return(tabCout) ;
}
/*-----------------------------------------------------------------------------
givCoutForEach : Calcule le cout total de l'automate pour chaque changement de 
				 codage demande' et renvoie la table des couts. et le cout 
				 initial.
---------------------------------------------
parametres	: tab1 : table de table des etats a changer.
			  tab2 : table de table des etats de change.
			  pointeur sur le cout initial a remplir.
--------------------------------------------
return		: table des couts .
------------------------------------------------------------------------------*/
unsigned int *givCoutForEach(tab1, tab2, initialCout)
int **tab1, **tab2;
unsigned int *initialCout ;
{
int i ;
unsigned int *tabCout ;
int *state1, *state2 ;
int *tabPoidEtat;
int *tabPoidFutur;
int *nwS,*nwO;
int *wi;

if(syf_trace)
	printf("----- givCoutForEach -----\n") ;
nwS = (int *)mbkalloc((autoSys->numberState +1 )*(autoSys->numberState +1)  * sizeof(int )) ;
nwO = (int *)mbkalloc((autoSys->numberState + 1)*(autoSys->numberOut) * sizeof(int )) ;

mustPoids(nwS,nwO) ;
wi = mustCalcul(nwS,nwO) ;
tabPoidFutur = PoidsFutur() ;
tabPoidEtat = asp_poidEtat() ;

*initialCout = 0 ;
/**initialCout = calculCout(wi,tabPoidEtat,tabPoidFutur) ;*/
*initialCout = constructBehGivCost(0) ;

tabCout = (unsigned int *)mbkalloc(sizeof(unsigned int) * autoSys->numberReg) ;
for(i = 0; i < autoSys->numberReg; i++)
	{
	tabCout[i] = 0 ;
	}
if(syf_trace)
  {
  for(i = 0; i < autoSys->numberReg; i++)
	{
	printf("cout[%d] = %u\n",i,tabCout[i]) ;
	}
  }
for(i = 0; i < autoSys->numberReg; i++)
	{
	state1 = *(tab1 + i) ;
	state2 = *(tab2 + i) ;
	if(state1 != NULL)
		{
		/*printf("state1 : %d, state2 : %d\n",*state1,*state2) ;*/
		while(*state1 != -1)
			{
			if(*state2 != -1)
				{
				changeCod(*state1,*state2) ;
				}
			else
				{
				printf("Error : givCoutForEach\n") ;
				exit(-1) ;
				}
			state1++ ;
			state2++ ;
			}
		state1 = *(tab1 + i) ;
		state2 = *(tab2 + i) ;
		if(*state1 != -1)
			{
			/*tabCout[i] = calculCout(wi,tabPoidEtat,tabPoidFutur) ;*/
			tabCout[i] = constructBehGivCost(0) ;
			}
		while(*state1 != -1)
			{
			if(*state2 != -1)
				{
				changeCod(*state1,*state2) ;
				}
			else
				{
				printf("Error : givCoutForEach\n") ;
				exit(-1) ;
				}
			state1++ ;
			state2++ ;
			}
		}
	}
if(syf_trace)
  for(i = 0; i < autoSys->numberReg; i++)
	printf("cout[%d] : %u\n",i,tabCout[i]) ;

return(tabCout) ;
}

/*-----------------------------------------------------------------------------
makeTabForEachBit : cree une table de table des etats qui ont le bit eme
							b identiques. 
							*(tab[0] + 0) = E3
							*(tab[0] + 1) = E5
							*(tab[0] + 2) = E2
							E3, E5, E2 ont le 0 eme bit ou a '1', ou a '0'.
							tab[i] = NULL si tous les etats ont en commun 
							le i eme bit.
---------------------------------------------
parametres	: liste des etats .
--------------------------------------------
return		: table de table des etats .
------------------------------------------------------------------------------*/
makeTabForEachBit(tab,listState,comBit)
int **tab ;
chain_list  *listState ;
int *comBit ;
{
int i,j,l,k ;
pCode cod ;
int *tabState ;
chain_list  *state ;

cod = autoSys->code ;

for(i = 0; i < autoSys->numberReg; i++)
	{
	j = 0;
	k = 0;
	state = listState ;
	while(state)
		{
		if(((cod + (int)state->DATA)->code) & bit[i])
			{
			*(*(tab+ 2*i) + j) = (int)state->DATA ;
			/*printf("*** ajout de %d dans list des '1',bit : %d, adr : %d, donnee : %d\n",(int)state->DATA,i,*(tab+2*i) +j, *(*(tab+2*i)+j)) ;	*/
			j++ ;
			}
		else
			{
			*(*(tab+ 2*i+1) + k) = (int)state->DATA ;
			/*printf("*** ajout de %d dans list des '0',bit : %d\n",(int)state->DATA,i) ;*/		
			k++ ;
			}
		state = state->NEXT ;
		}
	}
if(syf_trace)
	{
	printf("**** LES ETATS DE PUSH PAR ORDRE DE BIT A CHANGER INITIAL*****\n") ;
	displayTabStateBit(tab,autoSys->numberState) ;
	fflush(stdout) ;
	}
*comBit = reduceTab(tab) ;
}
/*-----------------------------------------------------------------------------
reduceTab : reduit la table en eliminant une recurrence sur deux : la 
					plus grande.
					exple
						tab[0] = E3, E2
						tab[1] = E5
					signifie le bit 0 de E3 et E2 vaut '1'.Et le bit 0 de E5 '0'
					on elimine E3 et E2 de la table.
---------------------------------------------
parametres	: la table de table des etats .
--------------------------------------------
return		: le nombre de bit commun dans tous les etats .
------------------------------------------------------------------------------*/
reduceTab(tab)
int  **tab ;
{
int comBit ;
int i ;
int zero, one ;
int *state0, *state1 ;


comBit = 0 ;
for(i = 0; i < autoSys->numberReg; i++)
	{
	state0 = tab[2*i] ;
	state1 = tab[2*i+1] ;
	zero = 0 ;
	one = 0 ;
		while(*state0 != -1)
			{
			/*printf("ST0 : %d\n",*state0) ;*/
			zero++ ;
			state0++ ;
			}
		while(*state1 != -1)
			{
			/*printf("ST1 : %d\n",*state1) ;*/
			one++ ;
			state1++ ;
			}
	if(zero == 0 || one == 0)
		{
		/*free(tab[2*i]) ; Surtout pas de free entraine des bugs*/
		tab[2*i] = NULL ;
		comBit++ ;
		}
	else
		if(zero > one)
			{
			/*free(tab[2*i]) ; Surtout pas de free entraine des bugs*/
			tab[2*i] = tab[2*i+1] ;
			}
	}
for(i = 1; i < 2 * autoSys->numberReg; i = i + 2)
	{
	/*free(tab[(i+1)/2]) ; Surtout pas de free entraine des bugs*/
	tab[(i+1)/2] = tab[i+1] ;
	}
return(comBit) ;
}
/*-----------------------------------------------------------------------------
numStateBit : donne le nombre des etats dans une table de label des etats. 
				et leur nombre par parametre.
---------------------------------------------
parametres	: table des etats .
--------------------------------------------
return		: le nombre .
------------------------------------------------------------------------------*/
int numStateBit(tabState)
int *tabState ;
{
int i ;
int *tab ;

tab = tabState ;
i = 0;
while(*tab != -1)
	{
	i++ ;
	tab++ ;
	}
return(i) ;
}
/*-----------------------------------------------------------------------------
givOtherCodState :	inverse le bit 'bit' du code de state, si ce nouveau code
					n'existe pas dans list, renvoie l'etat, sinon renvoie -1.
---------------------------------------------
parametres	: list des etats, l'etat  atraiter, le bit .
--------------------------------------------
return		: l'etat ou -1 .
------------------------------------------------------------------------------*/
givOtherCodState(listState,state,b)
chain_list *listState ;
int state ;
int b ;
{
pCode sCod ;
int nState ;
int cod ;
int nCod ;
int i ;
chain_list *list ;

cod = ((autoSys->code)+state)->code ;
/*printf("state:%s,cod : %d,bit : %d\n",(autoSys->state +state)->name,cod,b);*/
if(cod & bit[b])
	nCod = cod - bit[b] ;
else
	nCod = cod + bit[b] ;

nState = -2 ;
sCod = autoSys->code ;
for(i = 0; i < NUMBER_CODE(autoSys->numberState); i++)
	{
	if(nCod == sCod->code)
		{
		/*printf("TROUVEE\n") ;
		printf("cod : %d\n",(autoSys->code + i)->code) ;*/
		nState = i ;
		break ;
		}
	sCod++ ;
	/*printf("nState = %d\n",nState) ;*/
	}
/*printf("nState : %d\n",nState) ;
printf("change,state: %s,cod : %d\n",(autoSys->state + nState)->name,nCod) ;**/

list = listState ;
while(list)
	{
	if((int)list->DATA == nState)
		return(-1) ;
	list = list->NEXT ;
	}
return(nState) ;
}
/*-----------------------------------------------------------------------------
givPushState : donne la liste des etats susceptibles d 'etre mis dans la pile. 
				et leur nombre par parametre.
---------------------------------------------
parametres	: nombre d'etats  de push a remplir .
--------------------------------------------
return		: table de label des etats .
------------------------------------------------------------------------------*/
chain_list *givPushState(numState)
int *numState ;
{
pStack stack ;
int label, numBit ;
chain_list *listLab, *addLab() ;

*numState = 0 ;
listLab = NULL ;
stack = autoSys->stack ;
while(stack)
	{
	/*printf("entree , STACK numBit\n") ;*/
	if(stack->ctrl == PUSH)
		{
		label =  stack->returnStatelabel ;
		listLab = addLab(listLab,label,numState) ;
		}
	stack = stack->next ;
	}
return(listLab) ;
}
/*-----------------------------------------------------------------------------
givTabCod : donne la table des codes a partir de la structure autoSys->code. 
---------------------------------------------
parametres	: rien .
--------------------------------------------
return		: table des codes .
------------------------------------------------------------------------------*/
int *givTabCod()
{
int num,i ;
int *tab ;
pCode tabCod ;

num = NUMBER_CODE(autoSys->numberState);
tab = (int *)mbkalloc(sizeof(int) * num) ;

tabCod = autoSys->code ;
for(i = 0; i < num; i++)
	{
	tab[i] = tabCod->code ;
	tabCod++ ;
	}
return(tab) ;
}
/*-----------------------------------------------------------------------------
displayListState : visualise une liste d'etats. 
---------------------------------------------
parametres	: list d'etats .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
displayListState(listState)
chain_list *listState ;
{
int i ;
chain_list *list = listState ;

printf("************* LISTE DES ETATS ****************\n") ;
i = 0;
while(list)
	{
	printf("Etat[%d] : %s. cod : %d\n",i,((autoSys->state) + (int)list->DATA)->name,((autoSys->code) + (int)list->DATA)->code) ;
	list = list->NEXT ;
	i++ ;
	}
printf("************* FIN DE LISTE DES ETATS ****************\n") ;
}
/*-----------------------------------------------------------------------------
displayTabStateBit : visualise un tableau de tableau d'etats. 
---------------------------------------------
parametres	: tableau de tableau d'etats .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
displayTabStateBit(tab)
int **tab ;
{
int i, j ;
int *tabState ;

fflush(stdout) ;
printf("************* TABLEAU DE TABLEAU DES ETATS ****************\n") ;
for(i = 0; i < autoSys->numberReg; i++)
	{
	tabState = *(tab + i) ;
	printf("tab[%d] : \n",i) ;
	if(tabState)
		for(j = 0; j < autoSys->numberState; j++)
			{
			if(*(tabState + j) != -1)
				if(*(tabState + j) >= autoSys->numberState)
					printf("\t*. code : %d\n",((autoSys->code) + *(tabState+j))->code) ;
				else
					printf("\t%s. code : %d\n",((autoSys->state) + *(tabState+j))->name,((autoSys->code) + *(tabState+j))->code) ;
			else
				printf("\t-1\n") ;
			fflush(stdout) ;
			}
	else
		printf("\tNULL\n") ;
	}
printf("************* FIN DE TABLEAU DE TABLEAU DES ETATS ****************\n") ;
}
/*-----------------------------------------------------------------------------
displayTabState : visualise un tableau d'etats. 
---------------------------------------------
parametres	: tableau d'etats .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
displayTabState(tabState,bitMax)
int *tabState ;
int bitMax ;
{
int i ;

printf("************* TABLE DES ETATS ****************\n") ;
for(i = 0; i< bitMax * autoSys->numberState; i++)
	{
	if(tabState[i] != -1)
		printf("Etat[%d] : %s. cod : %d\n",i,((autoSys->state) + tabState[i])->name,((autoSys->code) +tabState[i])->code) ;
	else
		printf("Etat[%d] : -1\n",i) ;
		
	}
printf("************* FIN DE LISTE DES ETATS ****************\n") ;
}
/*-----------------------------------------------------------------------------
givStackWeight : donne le poid correspondant au STACK, 
					Le cout d'un mux 1 parmi 3 = 9.
					Le cout d'un registre = 6.
---------------------------------------------
parametres	: rien .
--------------------------------------------
return		: le poid .
------------------------------------------------------------------------------*/
givStackWeight()
{
int coutReg ;
int coutMux ;
int poidStack ;

if(autoSys->typeReg == REG_D)
	coutReg = 6 ;
else
	coutReg = 4 ;
coutMux = 8 ;

poidStack = autoSys->sizeStack * (coutMux + coutReg) ;

return(poidStack) ;
}
/*-----------------------------------------------------------------------------
constructBehGivCost : construit le befig et estime le cout .
---------------------------------------------
parametres	: mode : 1--> Eliminate Secondary variables, else keep that .
--------------------------------------------
return		: le cout .
------------------------------------------------------------------------------*/
constructBehGivCost(mode)
int mode ;
{
pCircuit pC ;
int litRed ;
syf_befig_list *beh, *auto2beh() ;
pCircuit makeCctBeh() ;
int savFlag ;

pC = NULL ;

if(syf_trace)
	printf("----- constructBehGivCost ------\n") ;
if(flagPile)
	ctrl2Abl() ;
code2Abl() ;
if(autoSys->typeReg == REG_D)
	{
	genRegD() ;
	/*genStackD() ;*/
	}
else
	{
	genReg() ;
	/*genStack() ;*/
	}
savFlag = flagPile ;
flagPile = 0;
if(mode)
	destroyAuxAuto() ;
beh = auto2beh(pC) ;
/*syf_displayBehMap(beh) ;*/
if(savFlag)
	completBerinBeh(beh) ;
pC = makeCctBeh(beh,0,syf_trace) ;
/*
syf_mapCarExprBeh(beh,simplif10Expr) ;
syf_mapCarExprBeh(beh,simplifNotExpr) ;
syf_createAuxBeh(beh) ;
*/
minimBehAbl(beh,syf_trace) ;
flagPile = savFlag ;
syf_coutAblBeh(beh,&litRed,0) ;
/*litRed = coutBehAuto(beh) ;*/
if(syf_trace)
	printf("----- end of constructBehGivCost ------\n") ;
destroyCct(beh->CIRCUI) ;
(void)syf_beh_delbefig(beh,beh,'Y') ;
return(litRed) ;
}
/*-----------------------------------------------------------------------------
displayTab  : visualise un tableau d'entiers. 
---------------------------------------------
parametres	: tableau d'entiers .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
displayTab(tab)
int *tab ;
{
int i ;

printf("************* TABLE ****************\n") ;
for(i =0; i< autoSys->numberState; i++)
	printf("tab[%d] : %d\n",i,tab[i]) ;
printf("************* FIN DE TABLE ****************\n") ;
}
/*-----------------------------------------------------------------------------
completBerinBeh  : complete la liste des berin de beh en ajoutant les 
				   registres correspondant au stack. 
---------------------------------------------
parametres	: beh .
--------------------------------------------
return		: rien .
------------------------------------------------------------------------------*/
completBerinBeh(beh)
syf_befig_list *beh;
{
int i, j;
char name[30] ;
syf_berin_list *bein ;

bein = beh->BERIN ;
for(i = 0; i < autoSys->sizeStack ; i++)
  for(j = 0; j < autoSys->numberReg ; j++)
	{
	sprintf(name,"%s_%d",STACK_NAME[i],j) ;
	bein=syf_beh_addberin(bein,name,'I','B',0) ;
	}
bein=syf_beh_addberin(bein,"pop",'I','B',0) ;
bein=syf_beh_addberin(bein,"push",'I','B',0) ;
bein=syf_beh_addberin(bein,"nop",'I','B',0) ;
 beh->BERIN = bein;
}    
