/****************************************************************************/
/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit : synthetiseur logique                                        */
/*    Fichier : decomp.c                                                    */
/*                                                                          */
/*    (c) copyright 1991 Laboratoire MASI equipe CAO & VLSI                 */
/*    Tous droits reserves                                                  */
/*    Support : e-mail cao-vlsi@masi.ibp.fr                                 */
/*                                                                          */
/*    Auteur(s) :     P. Allegre                        le : 30/08/91       */
/*                                                                          */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/****************************************************************************/

#include <stdio.h>
#include MUT_H
#include LOG_H
#include BEH_H
#include "../compil/lax_param.h"
#include "../synthe/sl_type.h"
#include "types.h"
#include "oper.h"
#include "util.h"
#include "cout.h"
#include "mapper.h"
#include "moteur.h"
#include "decomp.h"
#include "compile.h"
#include "regles.h"
#define ORDRE 0

chain_list *balance(abl)
chain_list *abl;
{
chain_list *listeOp = searchObj(operToChar(OPER(abl)),mappSys->cell_hash);
chain_list *ablSol1,*ablSol2 = NULL;
int maxSol1 = 0;
short inv = 0;

if (SL_TRACE == 3) {printf("balance :");displayArite(abl);printf("\n");}
  if (!listeOp)
  {
     inv = 1;
     listeOp = searchObj(operToChar(invOper(OPER(abl))),mappSys->cell_hash);
  }
  if (listeOp && (inv == 1))
  {
  chain_list *aux = inversArg(abl);
     freeExpr(abl);		/* ajoute le 25/06/92 */
     abl = moinsNot(aux);
     freeExpr(aux);
  }
  if (!listeOp)
  {
	printf("Impossible decomposition : \n");
	displayExpr(abl);
	exit(-1);
  }
  ablSol1 = balanceMax(listeOp,abl,0,&maxSol1,inv);
if (SL_TRACE == 3)
{printf("balance : sol1 =");displayArite(ablSol1);printf("=%d\n",cout(ablSol1));}
/* 12/10/93 */
  if ((maxSol1 != 0) && (maxSol1 != 2))
  {
  int arite = lengthExpr(abl),max = maxSol1-1;

     if ((arite%maxSol1 > 0) && /*(arite%max == 0) &&*/
/* test existence cell arite maxSol1-1 */
	 (testObj(gensym(operToChar(OPER(abl),max)),'c')) &&
/* est-ce que cela vaut le cout ? */
	 ((arite/maxSol1 + arite%maxSol1) >= 
          (arite/max + (arite%max > max-2 ? max - arite%max : arite%max))))
        max = max;
     else max = maxSol1;
	/*maxSol1 = searchMax(listeOp,maxSol1);*/
     if (max == maxSol1)
     {
        freechain(listeOp);
        return ablSol1;
     }
     else ablSol2 = balanceMax(listeOp,abl,max,&maxSol1,inv);
if (SL_TRACE == 3)
{printf("balance : sol2 =");displayArite(ablSol2);printf("=%d\n",cout(ablSol2));}
  }
  else 
  {
     freechain(listeOp);
     return ablSol1;
  }
  if (cout(ablSol1) > cout(ablSol2) && cout(ablSol2) >= 0)
  {
        freechain(listeOp);
	freeExpr(ablSol1);
	return ablSol2;
  }
  freechain(listeOp);
  freeExpr(ablSol2);
  return ablSol1;
}

chain_list *decomp(expr)
chain_list *expr;
{
int oper = OPER(expr);
chain_list *retour = copyExpr(expr);

   /* on evite de faire du travail en double (CPU) */
   if ((oper > 9) || (ARITE(expr) == 2)) 
   {
      return polarite(retour);
   }
   if (oper != NOT) CAR(retour)->DATA = (void *)invOper(oper);
   if (oper == NOT || operToCell(expr) || operToCell(retour))
   {
      freeExpr(retour);
      retour = expr;
   }
   else 
   {
   int deltaCour = mappSys->delta;

      freeExpr(retour);
      if (!searchObj(operToChar(oper),mappSys->cell_hash) &&
          !searchObj(operToChar(invOper(oper)),mappSys->cell_hash))
	 return expr;
      if (SL_OPTIM == 0)
      {
        sortExpr(expr,delais,0);
        deltaCour = delais(CADR(expr));
      }
      if ((oper == NAND) || (oper == NOR) || (oper == NXOR))
      {
	chain_list *aux1 = inversArg(expr);
	chain_list *aux2 = moinsNot(aux1);
	chain_list *echant;

	freeExpr(expr);		/*ajoute le 30/10*/
	freeExpr(aux1);
	addArite(aux2);
	printf("-");
	echant = echantil(aux2,deltaCour);
	freeExpr(aux2);
	aux1 = inversArg(echant);
	freeExpr(echant);
	retour = moinsNot(aux1);
	freeExpr(aux1);
	addArite(retour);
      }
      else
      {
      chain_list *aux = copyExpr(expr);

        CAR(aux)->DATA = (void *)invOper(OPER(expr));
        if (operToCell(aux))
           retour = expr;
        else
        {
/*
	printf("*");
*/
	   retour =  echantil(expr,deltaCour);
	   freeExpr(expr);		/*ajoute le 30/10*/
        }
        freeExpr(aux);
      }
   }
return polarite(retour);
}

chain_list *searchObj(name,pTab)
char *name;
pTH pTab;
{
int i;
pElemTH pEl=pTab->pElem;
chain_list *liste = NULL;

for (i=0;i<pTab->length;i++)
    {
    if ((pEl->value != VIDETH) && (pEl->value != DELETETH))
       if (!strncmp(name,pEl->key,strlen(name)))
	liste = addchain(liste,(char *)pEl->value);
    pEl++;
    }
return liste;
}

short searchMax(liste,n)
chain_list *liste;
short n;
{
short m = 0,ar;
chain_list *l;

for(l = liste;l;l = l->NEXT)
	{
	if (OPER(((cellList *)l->DATA)->val_abl->VALABL) == NOT)
	   ar = ARITE(CADR(((cellList *)l->DATA)->val_abl->VALABL));
	else
	   ar = ARITE(((cellList *)l->DATA)->val_abl->VALABL);
	if (ar > m)
	  if (n) 
	     if (ar <  n)
		m = ar;
	     else m = m;
	  else m = ar;
	}
return m;
}

char *eltNeutre(operateur)
short operateur;
{
switch (operateur)
	{
	case AND : return nameUn;
	case OR  :;
	case XOR : return nameZero;
	}
}

chain_list *decomposition(abl,n,max,plus,inverse)
chain_list *abl;
short n,max,plus,inverse;

{
short i,oper = OPER(abl);
chain_list *ablSol = createExpr(oper),*args = CDR(abl);
ptype_list *sol;

for(i=1;i <= n;i++)
	{
	chain_list *ablAux = createExpr(oper);
	short a;

	for(a = 1;a <= max;a++)
		{
		addHExpr(ablAux,copyExpr(CAR(args)));
		args = CDR(args);
		}
	addArite(ablAux);
	ablAux = triVar(ablAux);
	if (inverse)
	{
        chain_list *inv = invExpr(ablAux);

	   sol = evalue(inv);
           freeExpr(inv);		/*30/10*/
	   ablAux = CAR(sol);
	   libere(CDR(sol),sol);
	}
	addHExpr(ablSol,ablAux);
	}
   if (plus)
   {
	chain_list *a;
	
	if (testObj(gensym(operToChar(oper),n + plus),'c'))
		for(a = args;a;a= a->NEXT)
			addHExpr(ablSol,copyExpr(CAR(a)));
        else
          if (testObj(gensym(operToChar(oper),plus),'c'))
	     {
		chain_list *ablAux = createExpr(oper);

		for(a = args;a;a= a->NEXT)
			addHExpr(ablAux,copyExpr(CAR(a)));
		if (inverse)
		{
        	chain_list *inv = invExpr(ablAux);

		   sol = evalue(inv);
                   freeExpr(inv);		/*30/10*/
		   ablAux = CAR(sol);
	           libere(CDR(sol),sol);
		}
                addHExpr(ablSol,ablAux);
	     }
	   else
		for(a = args;a;a= a->NEXT)
			addHExpr(ablSol,copyExpr(CAR(a)));
   } 
   addArite(ablSol);
   ablSol = triVar(ablSol);
   if (inverse)
   {
   chain_list *inv = invExpr(ablSol);

      sol = evalue(inv);
      freeExpr(inv);		/*30/10*/
      ablSol = CAR(sol);
      libere(CDR(sol),sol);
      return ablSol;
   }
   else return ablSol;
}

chain_list *balanceMax(listeOp,abl,max,maxretour,inverse)
chain_list *listeOp;
chain_list *abl;
int max,*maxretour;
short inverse;
{
short oper = OPER(abl);
int arite = lengthExpr(abl);
chain_list *sol1;
int ariteSol = 0,maxi = 0,maxSol1;


  if (SL_TRACE == 3)
  {printf("balanceMax -->  ");displayArite(abl);printf("\n");
   for (sol1=CDR(abl);sol1;sol1=CDR(sol1))
      printf("%d ",delais(CAR(sol1))); printf("\n");}

  if (!max)
  {
     max = searchMax(listeOp,0);
     while (max > arite) 
	{
	maxi = max;
	max = searchMax(listeOp,max);
	}
  }
  maxSol1 = max;
  *maxretour = maxSol1;
  if ((max == 0) || (max == arite))
  {
     if (inverse)
     {
     chain_list *inv = invExpr(copyExpr(abl));
     ptype_list *sol = evalue(inv);

        freeExpr(inv);		/*30/10*/
        sol1 = CAR(sol);
        libere(CDR(sol),sol);
     }
     else 
     {
        sol1 = copyExpr(abl);
        addArite(sol1);
     }
     if (max == arite) return sol1;
  }
  else sol1 = decomposition(abl,arite/max,max,arite%max,inverse);

   ariteSol = inverse ? lengthExpr(CADR(sol1)) : ARITE(sol1);
   if (!max)
   {
      int i;

      for(i = maxi - ariteSol;i;i--)
	   addQExpr(inverse ? CADR(sol1) : sol1,createATOM(eltNeutre(oper)));
   }
   else
   {
      if ((ariteSol > max) && !testObj(gensym(operToChar(oper),ariteSol),'c')) 
      {
        chain_list *sol2;	/* 03/11 */

        sortExpr(sol1,delais,1);
	sol2 = balanceMax(listeOp,inverse ? CADR(sol1) : sol1,max,&max,inverse);
        freeExpr(sol1);
        sol1 = sol2;
      }
      if (ariteSol < max)
	if (!testObj(gensym(operToChar(oper),ariteSol),'c'))
	{
   	int maxi,i;

  	   while (max > ariteSol)
	   {
		maxi = max;
		max = searchMax(listeOp,max);
	   }
	   if (!max)
	    for(i = maxi - ariteSol;i;i--)
		addQExpr(inverse ? CADR(sol1) : sol1,createATOM(eltNeutre(oper)));
	   else
 	     sol1 = decomposition(inverse ? CADR(sol1) : sol1,ariteSol/max,max,ariteSol%max,inverse);
	}
   }
if (SL_TRACE == 3)
{printf("balanceMax <--  "); displayArite(sol1);printf("\n");}
return sol1;
}

/* version recursive de la decomposition non balancee */

chain_list *echantil(exp,delta)
chain_list *exp;
int delta;
{
short oper = OPER(exp);
chain_list *expNew;
int arite;

addArite(exp);
arite = ARITE(exp);
if (arite < 3) return copyExpr(exp);

if (!testObj(gensym(operToChar(oper),arite),'c'))
	{
             /* la cellule n'existe pas */

	int borne;
	chain_list *args;
	chain_list *expBal = createExpr(oper);
        chain_list *expBis;

		/* tri en delais croissants */
	sortExpr(exp,delais,1);

        args = exp;
	borne = delta + delais(CADR(args));
        
	while ((args  = CDR(args)) && (delais(CAR(args)) <= borne))
		addQExpr(expBal,copyExpr(CAR(args)));


	if (lengthExpr(expBal) == 1)
	{
	   freeExpr(expBal);
	   return echantil(exp,delta+mappSys->delta);
	}

	if (args)
		{
			/* s'il reste des arguments */
	        chain_list *a;

		expBis = createExpr(oper);
		addHExpr(expBis,balance(expBal));

		for(a = args;a;a = CDR(a))
			addQExpr(expBis,copyExpr(CAR(a)));
		}
	else 
	{
		expBis = balance(expBal);
        	freeExpr(expBal);		/* 30/10 */
	}
	expNew = echantil(expBis,delta+mappSys->delta);
	freeExpr(expBis);
	}
else
	expNew = copyExpr(exp);
return triVar(expNew);
}

void permutVar(exp,envel)
chain_list *exp,*envel;
{
int niv = profExpr(envel);
chain_list *aux = exp,*env = envel;
int funcNormExpr();

   if (niv)
   {
      if (!ATOM(envel) && ARITE(envel))
      {
         sort2Expr(exp,delais,funcNorm2,ORDRE,1);
      }
      while ((aux = CDR(aux)) && (env = CDR(env)))
	permutVar(CAR(aux),CAR(env));
   }
}

chain_list *triVar(exp)
chain_list *exp;

{
cellList *cell;
chain_list *expr,*aux;
int funcNormExpr();

   if (!ATOM (exp))
   {
      cell = operToCell(exp);
      if (!cell) return exp;
      if (cell->type == 'l') 
         if (ARITE(exp) == 1)
         {
         chain_list *bidule = CADR(exp);

            bidule = triVar(bidule);
 	    ((exp->NEXT)->DATA) = (void *)bidule;
         }
         else
	 {
	 Alist *ent = cell->entrees;

	    initAlist(exp,ent);
	    expr = remplace(cell->val_abl->VALABL,ent);
	    resetAlist(ent,1);
	    permutVar(expr,cell->envel);
	    if (!filtre(cell->envel,expr,ent))
	    {
		printf("triVar :");
	 	displayArite(cell->envel);printf("\n");
	 	displayArite(expr);printf("\n");
	    	exit(-1);
	     }
	    aux = createExpr(OPER(exp));
	    do
		addQExpr(aux,ent->ptChain);
	    while (ent = CDR(ent));
	    addArite(aux);
	    freeExpr(exp);
	    freeExpr(expr);
	    return(aux);
         }
   }
   return exp;
}
