/****************************************************************************/
/*                                                                          */
/*                      Chaine de CAO & VLSI   Alliance                     */
/*                                                                          */
/*    Produit : synthetiseur logique                                        */
/*    Fichier : balance.c                                                   */
/*                                                                          */
/*    (c) copyright 1991 Laboratoire MASI equipe CAO & VLSI                 */
/*    Tous droits reserves                                                  */
/*    Support : e-mail cao-vlsi@masi.ibp.fr                                 */
/*                                                                          */
/*    Auteur(s) : L. Burgun                             le : 31/01/1992     */
/*                                                                          */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*    Modifie par :                                     le : ../../....     */
/*                                                                          */
/****************************************************************************/

#include MUT_H
#include LOG_H
#include BEH_H
#include "balance.h"
#include "../compil/lax_param.h"
#include "../synthe/sl_type.h"

void displayCarac1(expr,caracTH)
chain_list *expr;
pTH caracTH;
{
if (ATOM(expr))
   printf(" %d",searchTH(caracTH,expr));
else
   {
   printf(" (%s%d",operToChar(OPER(expr)),lengthExpr(expr));
   while (expr = CDR(expr))
         printf(" %d",searchTH(caracTH,CAR(expr)));
   printf(")");
   }
}

/*-------------------------------------------------------------------------
nonBalanceExpr: renvoie l'expression non balancee correspondant a une
             expression a decomposer. 
---------------------------------------------------------------------------
retour		: une expression
---------------------------------------------------------------------------*/
chain_list *nonBalanceExpr(beh,delaisTH,expr,echantil,grain)
befig_list *beh;
pTH delaisTH;
chain_list *expr;
int echantil, grain;
{
int len = lengthExpr(expr);

/*
printf("nonBal : grain = %d, echantil = %d\n ***",grain,echantil);
displayExpr(expr);
displayCarac1(expr,delaisTH); printf("\n");
*/
if (SL_TRACE)
   {
   if (!ATOM(expr)) 
      {
      printf("nonBalanceExpr : %s %d\n",operToChar(OPER(expr)), len);
      }
   }

if (len <= grain)
   {
   chain_list *ret = copyExpr(expr);

   calculDelaisExpr(beh,delaisTH,ret,0);
   return ret;
   }
else
   {
   int oper = OPER(expr);
   chain_list *exprAdd = createExpr(oper);
   chain_list *exprRet, *aux;
   chain_list *oldExpr = expr;
   int borne = echantil + searchTH(delaisTH,CADR(expr));

	/* creation d'une ss-expr avec le premier echantillon */
   while ((expr = CDR(expr)) && (searchTH(delaisTH,CAR(expr)) <= borne))
         addQExpr(exprAdd,copyExpr(CAR(expr)));

   if (lengthExpr(exprAdd) == 1)
      {
	/* cas ou un seul argument passe dans l'echantillon */
      addQExpr(exprAdd,copyExpr(CAR(expr)));
	/* on ajoute le deuxieme argument */
      expr = CDR(expr);
      }

/*
   printf("nonBal : expr echantillonnee\n"); 
   displayExpr(exprAdd);
*/

   if (lengthExpr(exprAdd) > grain)
      {
		/* si la ss-expr ne respecte pas le grain : decomp balancee */

      aux = balanceExpr(exprAdd,1,grain);
      }
    else
      aux = copyExpr(exprAdd);
    freeExpr(exprAdd);

   if (expr)
      {
	/* si tous les arguments de expr ne sont pas dans la ss-expr */

      exprRet = createExpr(oper);
      addHExpr(exprRet,aux);
      while(expr)
           {
           addQExpr(exprRet,copyExpr(CAR(expr)));
           expr = CDR(expr);
           }
      }
    else
      {
      exprRet = aux;
      }

   calculDelaisExpr(beh,delaisTH,exprRet,0);

/*
   printf("nonBal : apres calculDelais\n");
   displayExpr(exprRet);
   displayCarac1(exprRet,delaisTH); printf("\n");
*/

	/* appel recursif sur la nouvelle expression */
   return nonBalanceExpr(beh,delaisTH,exprRet,echantil,grain);
   }
}

/*-------------------------------------------------------------------------
changeOperRecExpr: change les operateurs d'une expression par oper. 
---------------------------------------------------------------------------
retour		: une expression
---------------------------------------------------------------------------*/
void changeOperRecExpr(expr,oper)
chain_list *expr;
int oper;
{
if (!ATOM(expr))
   {
   changeOperExpr(expr,oper);
   while (expr = CDR(expr))
      changeOperRecExpr(CAR(expr),oper);
   }
}

/*-------------------------------------------------------------------------
hashBalance: hachage pour la decomposition balancee.
---------------------------------------------------------------------------
retour		: une cle de hachage
---------------------------------------------------------------------------*/
int hashBalance(optim,grain,arity)
int optim,grain,arity;
{
return (arity + 100*grain + 1000*optim);
}

/*-------------------------------------------------------------------------
decBalExpr: renvoie l'expression balancee pour une arite ne
            figurant pas dans pTHBalance.
---------------------------------------------------------------------------
retour		: une expression
---------------------------------------------------------------------------*/
chain_list *decBalExpr(expr,optim,grain)
chain_list *expr;
int optim,grain;
{
int arity = lengthExpr(expr);
int div = arity / grain;
int mod = arity % grain;
int oper = OPER(expr);
chain_list *ret = createExpr(oper);
int nbSsexpr, nbElts;

expr = CDR(expr);

if (SL_TRACE) 
   printf("decBalExpr : arity = %d, grain = %d, div = %d, mod = %d\n",arity,grain,div,mod);
	/* creation de grain ss-expr */
for(nbSsexpr = 0; nbSsexpr < grain; nbSsexpr++)
   {
   chain_list *ssExpr = createExpr(oper);

		/* dans chaque ss-expr, ajout de div elts */
   for(nbElts = 0; nbElts < div; nbElts++)
      {
      addQExpr(ssExpr,copyExpr(CAR(expr)));
      expr = CDR(expr);
      }

		/* s'il reste des elts, ajout de 1 par ss-expr */
   if (mod > 0)
      {
      addQExpr(ssExpr,copyExpr(CAR(expr)));
      mod--;
      expr = CDR(expr);
      }

   if (lengthExpr(ssExpr) > grain)
      {
		/* la ss-expr ne respecte pas le grain */

      chain_list *ssExprBal;

      if (lengthExpr(ssExpr) > MAXBALANCETH)
		/* la solution n'est pas dans pTHBalance : appel recursif */
         ssExprBal = decBalExpr(ssExpr,optim,grain);
      else
		/* la solution est dans pTHBalance */
         ssExprBal = balanceExpr(ssExpr,optim,grain);

      freeExpr(ssExpr);
      addQExpr(ret,ssExprBal);
      }
   else
      addQExpr(ret,ssExpr);
   }
return ret;
}

/*-------------------------------------------------------------------------
balanceExpr: renvoie l'expression balancee correspondant a une
             expression a decomposer. 
---------------------------------------------------------------------------
retour		: une expression
---------------------------------------------------------------------------*/
chain_list *balanceExpr(expr,optim,grain)
chain_list *expr;
int optim,grain;
{
int val;
chain_list *ret;
int arity = lengthExpr(expr);

if (arity > MAXBALANCETH)
	/* l'arite de expr est superieur aux elts de pTHBalance */
   return decBalExpr(expr,optim,grain);

	/* recherche de la solution dans pTHBalance */

val = searchTH(pTHBalance,hashBalance(optim,grain,arity));
if (val != EMPTYTH)
   {
   ret = copyExpr((chain_list *) val);
   if (OPER(expr) == OR)
      changeOperRecExpr(ret,OR);
   if (numberAtomExpr(ret) != lengthExpr(expr))
      {
      printf("decBoolExpr : error - bad decomposition\n");
      displayExpr(expr);
      displayExpr(ret);
      exit(-1);
      }
   filtreExpr(ret,expr);
   return ret;
   }
printf("balanceExpr : error - bad arguments, arity = %d, optim = %d, grain = %d\n",arity,optim,grain);
displayExpr(expr);
exit(-1);
}     
/*-------------------------------------------------------------------------
initializeBalance: initialise une table de hachage dans laquelle
                   on a associe un triplet d'argument de decom-
                   position a une expression balancee.
---------------------------------------------------------------------------
retour		: une expression
---------------------------------------------------------------------------*/
void initializeBalance()
{

		/* variable globale initialisee */

pTHBalance = createTH(200);

		/* arite = 3 */

addTH(pTHBalance,
      hashBalance(0,2,3),
      charToExpr (
           "(and (and x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(1,2,3),
      charToExpr (
           "(and (and x x) x)"
      ));

		/* arite = 4 */
addTH(pTHBalance,
      hashBalance(0,2,4),
      charToExpr (
           "(and (and x x) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,4),
      charToExpr (
           "(and (and x x) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,4),
      charToExpr (
           "(and (and x x) x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,3,4),
      charToExpr (
           "(and (and x x) (and x x))"
      ));

		/* arite = 5 */
addTH(pTHBalance,
      hashBalance(0,2,5),
      charToExpr (
           "(and (and (and x x) x) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,5),
      charToExpr (
           "(and (and (and x x) x) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,5),
      charToExpr (
           "(and (and x x x) x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,3,5),
      charToExpr (
           "(and (and x x) (and x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(0,4,5),
      charToExpr (
           "(and (and x x) x x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,4,5),
      charToExpr (
           "(and (and x x x) (and x x))"
      ));

		/* arite = 6 */

addTH(pTHBalance,
      hashBalance(0,2,6),
      charToExpr (
           "(and (and (and x x) (and x x)) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,6),
      charToExpr (
           "(and (and (and x x) (and x x)) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,6),
      charToExpr (
           "(and (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,6),
      charToExpr (
           "(and (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,4,6),
      charToExpr (
           "(and (and x x x) x x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,4,6),
      charToExpr (
           "(and (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,5,6),
      charToExpr (
           "(and (and x x) x x x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,5,6),
      charToExpr (
           "(and (and x x x) (and x x x))"
      ));

			/* arite = 7 */


addTH(pTHBalance,
      hashBalance(0,2,7),
      charToExpr (
           "(and (and (and x x) (and x x)) (and (and x x) x))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,7),
      charToExpr (
           "(and (and (and x x) (and x x)) (and (and x x) x))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,7),
      charToExpr (
           "(and (and x x x) (and x x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(1,3,7),
      charToExpr (
           "(and (and x x x) (and x x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(0,4,7),
      charToExpr (
           "(and (and x x x x) x x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,4,7),
      charToExpr (
           "(and (and x x x) (and x x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(0,5,7),
      charToExpr (
           "(and (and x x x) x x x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,5,7),
      charToExpr (
           "(and (and x x x) (and x x x) x)"
      ));

			/* arite = 8 */
addTH(pTHBalance,
      hashBalance(0,2,8),
      charToExpr (
           "(and (and (and x x) (and x x)) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,8),
      charToExpr (
           "(and (and (and x x) (and x x)) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,8),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,8),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,4,8),
      charToExpr (
           "(and (and x x x x) (and x x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,4,8),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,5,8),
      charToExpr (
           "(and (and x x x x) x x x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,5,8),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x))"
      ));

			/* arite = 9 */
addTH(pTHBalance,
      hashBalance(0,2,9),
      charToExpr (
           "(and (and (and (and x x) x) (and x x)) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,9),
      charToExpr (
           "(and (and (and (and x x) x) (and x x)) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,9),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,9),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,4,9),
      charToExpr (
           "(and (and x x x x) (and x x x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(1,4,9),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,5,9),
      charToExpr (
           "(and (and x x x x x) x x x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,5,9),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x x))"
      ));


			/* arite = 10 */
addTH(pTHBalance,
      hashBalance(0,2,10),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and x x)) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,10),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and x x)) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,10),
      charToExpr (
           "(and (and (and x x) x x) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,10),
      charToExpr (
           "(and (and (and x x x) (and x x x)) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,4,10),
      charToExpr (
           "(and (and x x x x) (and x x x x) x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,4,10),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(0,5,10),
      charToExpr (
           "(and (and x x x x x) (and x x x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,5,10),
      charToExpr (
           "(and (and x x x) (and x x x) (and x x x) x)"
      ));

			/* arite = 11 */
addTH(pTHBalance,
      hashBalance(0,2,11),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) x)) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,11),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) x)) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,11),
      charToExpr (
           "(and (and (and x x x) x x) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,11),
      charToExpr (
           "(and (and (and x x x) (and x x x)) (and (and x x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,4,11),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,4,11),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,5,11),
      charToExpr (
           "(and (and x x x x x) (and x x x x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(1,5,11),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x))"
      ));


			/* arite = 12 */
addTH(pTHBalance,
      hashBalance(0,2,12),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,12),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and x x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,12),
      charToExpr (
           "(and (and (and x x x) (and x x x)) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,12),
      charToExpr (
           "(and (and (and x x x) (and x x x)) (and (and x x x) (and x x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,4,12),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,4,12),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,5,12),
      charToExpr (
           "(and (and x x x x x) (and x x x x x) x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,5,12),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x))"
      ));

			/* arite = 13 */
addTH(pTHBalance,
      hashBalance(0,2,13),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and (and x x) x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,13),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and (and x x) x) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,13),
      charToExpr (
           "(and (and (and x x x) (and x x x) x) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,13),
      charToExpr (
           "(and (and (and x x x) (and x x x)) (and (and x x x) (and x x x)) x)"
      ));
addTH(pTHBalance,
      hashBalance(0,4,13),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(1,4,13),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) x)"
      ));
addTH(pTHBalance,
      hashBalance(0,5,13),
      charToExpr (
           "(and (and x x x x x) (and x x x x x) x x x)"
      ));
addTH(pTHBalance,
      hashBalance(1,5,13),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) x)"
      ));


			/* arite = 14 */
addTH(pTHBalance,
      hashBalance(0,2,14),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and (and x x) (and x x)) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,14),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and (and x x) (and x x)) (and x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,14),
      charToExpr (
           "(and (and (and x x x) (and x x x) (and x x)) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,14),
      charToExpr (
           "(and (and (and x x x) (and x x x) (and x x)) (and (and x x x) (and x x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,4,14),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) (and x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,4,14),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,5,14),
      charToExpr (
           "(and (and x x x x x) (and x x x x x) (and x x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,5,14),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x) (and x x x))"
      ));

			/* arite = 15 */
addTH(pTHBalance,
      hashBalance(0,2,15),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and (and x x) (and x x)) (and (and x x) x)))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,15),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and (and x x) (and x x)) (and (and x x) x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,15),
      charToExpr (
           "(and (and (and x x x) (and x x x) (and x x x)) (and x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,15),
      charToExpr (
           "(and (and (and x x x) (and x x x) (and x x x)) (and (and x x x) (and x x x)))"
      ));
addTH(pTHBalance,
      hashBalance(0,4,15),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,4,15),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) (and x x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,5,15),
      charToExpr (
           "(and (and x x x x x) (and x x x x x) (and x x x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,5,15),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) (and x x x))"
      ));


			/* arite = 16 */
addTH(pTHBalance,
      hashBalance(0,2,16),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and (and x x) (and x x)) (and (and x x) (and x x))))"
      ));
addTH(pTHBalance,
      hashBalance(1,2,16),
      charToExpr (
           "(and (and (and (and x x) (and x x)) (and (and x x) (and x x))) (and (and (and x x) (and x x)) (and (and x x) (and x x))))"
      ));
addTH(pTHBalance,
      hashBalance(0,3,16),
      charToExpr (
           "(and (and (and x x x) (and x x x) (and x x x)) (and (and x x x) (and x x x) x))"
      ));
addTH(pTHBalance,
      hashBalance(1,3,16),
      charToExpr (
           "(and (and (and x x x) (and x x x) (and x x x)) (and (and x x x) (and x x x) x))"
      ));
addTH(pTHBalance,
      hashBalance(0,4,16),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) (and x x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,4,16),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) (and x x x x))"
      ));
addTH(pTHBalance,
      hashBalance(0,5,16),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) (and x x x x))"
      ));
addTH(pTHBalance,
      hashBalance(1,5,16),
      charToExpr (
           "(and (and x x x x) (and x x x x) (and x x x x) (and x x x x))"
      ));
}

/*-------------------------------------------------------------------------
filtreExpr:  associe chaque var de expr1 (x) a expr2 
---------------------------------------------------------------------------
retour		: rien. 
---------------------------------------------------------------------------*/
void filtreExpr(expr1,expr2)
chain_list *expr1,*expr2;
{
int i;

if (ATOM(expr1))
   {
   printf("filtreExpr : error - bad decomposition : ATOM %s\n",VALUE_ATOM(expr1));
   exit(-1);
   }
while (expr1 = CDR(expr1))
   {
   if (ATOM(CAR(expr1)))
      {
      freeExpr(CAR(expr1));
      if (!CDR(expr2))
         {
         printf("filtreExpr : error - bad decomposition\n");
         exit(-1);
         }
      expr1->DATA = (void *) copyExpr(CADR(expr2));
      expr2 = CDR(expr2);
      }
   else
      {
      i = numberAtomExpr(CAR(expr1));
      filtreExpr(CAR(expr1),expr2);
      for (;i>0;i--)
          {
          expr2 = CDR(expr2);
          }
      }
   }
}

/*-------------------------------------------------------------------------
decompBoolExpr:  applique la decomposition booleenne sur une expression.
---------------------------------------------------------------------------
retour		: une expression
---------------------------------------------------------------------------*/
chain_list *decompBoolExpr(beh,caracTH,expr,optim,dejaTraite,grain)
befig_list *beh;
pTH caracTH;
chain_list *expr;
int optim;
pTH dejaTraite;
int grain;
{
chain_list *balance;
chain_list *ret;

if (ATOM(expr))
   {
   beaux_list *aux;
 
   if (!strcmp(VALUE_ATOM(expr),"'0'") || !strcmp(VALUE_ATOM(expr),"'1'"))
      return copyExpr(expr);

   if (searchTH(dejaTraite,VALUE_ATOM(expr)) != EMPTYTH)
      return copyExpr(expr);

                /* descente recursive dans la befig */

   aux = beh->BEAUX;
   while (aux && strcmp(aux->NAME,VALUE_ATOM(expr)))
        aux = aux->NEXT;

   addTH(dejaTraite,VALUE_ATOM(expr),1);
   if (!aux)
      return copyExpr(expr);
   else
      {
      chain_list *abl = decompBoolExpr(beh,caracTH,aux->ABL,optim,dejaTraite,grain);
      freeExpr(aux->ABL);
      aux->ABL = abl;
      return copyExpr(expr);
      }
   }

if (lengthExpr(expr) <= grain)
   {
   ret = createExpr(OPER(expr));
   while (expr = CDR(expr))
      addQExpr(ret,decompBoolExpr(beh,caracTH,CAR(expr),
               optim,dejaTraite,grain));
   return ret;
   }

if (optim == 1)
   {
   int echantil;
		/* optimisation en delais */
		/* decomposition non balancee */

   switch (grain)
       {
       case 2 : echantil =  600; break;
       case 3 : echantil =  700; break;
       case 4 : echantil =  800; break;
       case 5 : echantil = 1000; break;
       }

   balance = nonBalanceExpr(beh,caracTH,expr,echantil,grain);

   if (SL_TRACE) 
      {
      printf("apres nonBalanceExpr :\n");
      displayExpr(balance);
      }
   }
else
   {
		/* optimisation en surface */
		/* decomposition balancee */

   balance = balanceExpr(expr,optim,grain);

   if (SL_TRACE)
       {
       printf("apres balanceExpr :\n"); 
       displayExpr(balance);
       }
   }
		/* tri des variables de expr */

		/* filtrage */
		/* balance est modifie physiquement */

ret = decompBoolExpr(beh,caracTH,balance,optim,dejaTraite,grain);

return(ret);
}

/*-------------------------------------------------------------------------
decompBoolBeh	: decompose les operateur d'arite trop grande. 
---------------------------------------------------------------------------
retour		: void 
---------------------------------------------------------------------------*/
void decompBoolBeh(beh,optim,delais,optimPO,tp,tn)
befig_list *beh;
int optim;
ptype_list *delais;
chain_list *optimPO;
int tp,tn;
{
beout_list *out;
bereg_list *reg;
bebus_list *bus;
bebux_list *bux;
biabl_list *biabl;
pTH caracTH; 
pTH dejaTraite;
int val,delaisMoyen;
pTH caracBeh();
chain_list *expr;
int grain,grain_optim;

		/* calcul du grain */

		/* a correler avec tn_max et tp_max ? */

if (optim == 0)
   grain = 5;

if (optim == 1 || optim == 2)
   grain = 4;

if (optim > 2)
   grain = 3;

if (grain > tp)
   grain = tp;

if (grain > tn)
   grain = tn;

grain_optim = 3;

if (grain_optim > tp)
   grain_optim = tp;

if (grain_optim > tn)
   grain_optim = tn;

initializeBalance();

caracTH = caracBeh(beh,delais,0);
dejaTraite = createTH(100);

		/* ----- a correler avec le mode d'optimisation */

delaisMoyen = delaisCarac(caracTH,optim);

	/* parcours des expressions - decomposition booleenne */

		/* cones optimises en delais */

out = beh->BEOUT;
while (out)
   {
   if (out->ABL)
      {
      int del;

      if ((del = searchTH(caracTH,out->ABL)) > delaisMoyen ||
          memberChain(out->NAME,optimPO))
         {
/*
	 printf("optimisation en delais : %s\n",out->NAME);
*/
         expr = decompBoolExpr(beh,caracTH,out->ABL,1,dejaTraite,grain_optim);
 
        /* remise a jour de caracTH avec le nouvel ABL */
         addTH(caracTH,expr,del);

         freeExpr(out->ABL);
         out->ABL = expr;
         }
      }
   out = out->NEXT;
   }

reg = beh->BEREG;
while (reg)
   {  
   biabl = reg->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
         int del;

         if ((del = searchTH(caracTH,biabl->CNDABL)) > delaisMoyen ||
             memberChain(reg->NAME,optimPO))
            {
            expr = decompBoolExpr(beh,caracTH,biabl->CNDABL,1,dejaTraite,grain_optim);
                 
            /* remise a jour de caracTH avec le nouvel ABL */
            addTH(caracTH,expr,del);
 
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
         if ((del = searchTH(caracTH,biabl->VALABL)) > delaisMoyen ||
             memberChain(reg->NAME,optimPO))
            {
            expr = decompBoolExpr(beh,caracTH,biabl->VALABL,1,dejaTraite,grain_optim);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
            }
         }
      biabl = biabl->NEXT;
      }
   reg = reg->NEXT;
   }  
      

bus = beh->BEBUS;
while (bus)
   {  
   biabl = bus->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
	 int del;

	 if ((del = searchTH(caracTH,biabl->CNDABL)) > delaisMoyen ||
             memberChain(bus->NAME,optimPO))
            {
            expr = decompBoolExpr(beh,caracTH,biabl->CNDABL,1,dejaTraite,grain_optim);

            /* remise a jour de caracTH avec le nouvel ABL */
            addTH(caracTH,expr,del);

            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
         if ((del = searchTH(caracTH,biabl->VALABL)) > delaisMoyen ||
             memberChain(bus->NAME,optimPO))
            {
            expr = decompBoolExpr(beh,caracTH,biabl->VALABL,1,dejaTraite,grain_optim);

            /* remise a jour de caracTH avec le nouvel ABL */
            addTH(caracTH,expr,del);

            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
            }
         }
      biabl = biabl->NEXT;
      }
   bus = bus->NEXT;
   }  

bux = beh->BEBUX;
while (bux)
   {  
   biabl = bux->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
	 int del;

	 if ((del = searchTH(caracTH,biabl->CNDABL)) > delaisMoyen ||
             memberChain(bux->NAME,optimPO))
            {
            expr = decompBoolExpr(beh,caracTH,biabl->CNDABL,1,dejaTraite,grain_optim);

            /* remise a jour de caracTH avec le nouvel ABL */
            addTH(caracTH,expr,del);

            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
            }
         if ((del = searchTH(caracTH,biabl->VALABL)) > delaisMoyen ||
             memberChain(bux->NAME,optimPO))
            {
            expr = decompBoolExpr(beh,caracTH,biabl->VALABL,1,dejaTraite,grain_optim);

            /* remise a jour de caracTH avec le nouvel ABL */
            addTH(caracTH,expr,del);

            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
            }
         }
      biabl = biabl->NEXT;
      }
   bux = bux->NEXT;
   }  


		/* cones optimises en surface */

out = beh->BEOUT;
while (out)
   {
   if (out->ABL)
      {
      val = searchTH(caracTH,out->ABL);
      if (val != EMPTYTH && val  <= delaisMoyen
           && !memberChain(out->NAME,optimPO))
	 {
/*
	 printf("optimisation en surface : %s\n",out->NAME);
*/
         expr = decompBoolExpr(beh,caracTH,out->ABL,0,dejaTraite,grain);
         freeExpr(out->ABL);
         out->ABL = expr;
	 }
      }
   out = out->NEXT;
   }

reg = beh->BEREG;
while (reg)
   {  
   biabl = reg->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
         val = searchTH(caracTH,biabl->CNDABL);
         if (val != EMPTYTH && val  <= delaisMoyen
             && !memberChain(reg->NAME,optimPO))
	    {
            expr = decompBoolExpr(beh,caracTH,biabl->CNDABL,0,dejaTraite,grain);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
	 if (val != EMPTYTH && val  <= delaisMoyen
             && !memberChain(reg->NAME,optimPO))
	    {
            expr = decompBoolExpr(beh,caracTH,biabl->VALABL,0,dejaTraite,grain);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
	    }
         }
      biabl = biabl->NEXT;
      }
   reg = reg->NEXT;
   }  
      
bus = beh->BEBUS;
while (bus)
   {  
   biabl = bus->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
         val = searchTH(caracTH,biabl->CNDABL);
	 if (val != EMPTYTH && val  <= delaisMoyen
             && !memberChain(bus->NAME,optimPO))
	    {
            expr = decompBoolExpr(beh,caracTH,biabl->CNDABL,0,dejaTraite,grain);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
	 if (val != EMPTYTH && val  <= delaisMoyen
             && !memberChain(bus->NAME,optimPO))
	    {
            expr = decompBoolExpr(beh,caracTH,biabl->VALABL,0,dejaTraite,grain);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
	    }
         }
      biabl = biabl->NEXT;
      }
   bus = bus->NEXT;
   }  

bux = beh->BEBUX;
while (bux)
   {  
   biabl = bux->BIABL;
   while (biabl)
      {
      if (biabl->CNDABL && biabl->VALABL)
         {
         val = searchTH(caracTH,biabl->CNDABL);
	 if (val != EMPTYTH && val  <= delaisMoyen
             && !memberChain(bux->NAME,optimPO))
	    {
            expr = decompBoolExpr(beh,caracTH,biabl->CNDABL,0,dejaTraite,grain);
            freeExpr(biabl->CNDABL);
            biabl->CNDABL = expr;
	    }
         val = searchTH(caracTH,biabl->VALABL);
	 if (val != EMPTYTH && val  <= delaisMoyen
             && !memberChain(bux->NAME,optimPO))
	    {
            expr = decompBoolExpr(beh,caracTH,biabl->VALABL,0,dejaTraite,grain);
            freeExpr(biabl->VALABL);
            biabl->VALABL = expr;
	    }
         }
      biabl = biabl->NEXT;
      }
   bux = bux->NEXT;
   }  



destroyTH(caracTH);
destroyTH(dejaTraite);

if (SL_TRACE)
   displayBeh(beh,1);
}     
