/********************************************************************
*                                                                   *
* Laboratoire MASI CAO-VLSI, UPMC, Copyright 1991 1992 1993 1994    *
*                                                                   *
* Software support Email : cao-vlsi@masi.ibp.fr                     *
*                                                                   *
* Authors : Zouina AKTOUF &                                         *
*           El Arabi RHOMARI &                                      *
*           Jose MARTINS DOS SANTOS                                 *
*                                                                   *
* Supervision & Modifications : Lotfi BEN AMMAR                     *
*                                                                   *
********************************************************************/
/*********************************************************************************
*                      Fichier: optiplace_R.c                                    *
*       version : 3.0                                                            *
*       date    : 19/03/92                                                       *
*********************************************************************************/
#include "dpr_R.h"

/********************************************************
*                fonction        longsig()		*
* calculer et pas remplir la longueur d'un signal       *
********************************************************/
 long		 longsig(ptsig,coll,colr)
 SIGNAL		*ptsig;
 int             coll,colr;

 {
 chain_list	*ptccol,*ptclincon,*ptccon;
 CONNECTOR       *ptcon;
 int		 colmin=0,colmax=0,colcour;
 long             lsig=0;

 ptccol = ptsig->COL;
 if (ptccol)
    {
    colmin = ((COLUMN *)ptccol->DATA)->INDEX;
    colmax = colmin;
    }
 for (ptccol=ptsig->COL;ptccol;ptccol=ptccol->NEXT)
     {
     colcour = ((COLUMN *)ptccol->DATA)->INDEX;
     colmin = (colmin>colcour) ? colcour : colmin;
     colmax = (colcour>colmax) ? colcour : colmax;
     }
 if (ptsig->USER) /* c.a.d signal ayant un connecteur pere non place */
    {
    if ((colmin-coll) < (colr-colmax))
       {
       lsig = colmax - coll;
       }
    else
       {
       lsig = colr - colmin;
       }
    }
 else /* c.a.d signal ayant tous ces connecteurs places */
    {
    lsig = colmax - colmin;
    }
 return(lsig);
 }

/********************************************************
*                fonction        longsigs()		*
* calcule la somme des longueurs de tous les signaux    *
********************************************************/
 long longsigs(ptfig,coll,colr)
 FIGURE	*ptfig;
 int     coll,colr;

 {
 chain_list	*ptcsig;
 SIGNAL		*ptsig;
 char            *vdd,*vss;
 long		lsigs=0;
 long		lsig=0;

 vdd=namealloc("vdd");
 vss=namealloc("vss");

 for (ptcsig=ptfig->SIG;ptcsig;ptcsig=ptcsig->NEXT)
     {
     ptsig = (SIGNAL *)ptcsig->DATA;
     if (strncmp(ptsig->NAME,vdd,3)&&strncmp(ptsig->NAME,vss,3))
        {
        lsig = longsig(ptsig,coll,colr);
        ptsig->WIDTH = lsig;
        lsigs = lsigs + lsig;
        }
     }
 return(lsigs);
 }

/********************************************************
*                fonction        exchange()		*
* echange deux colonnes                                 *
********************************************************/
 FIGURE	*exchange(ptfig,ptccoll,ptccolr)

 chain_list	*ptccoll;
 chain_list	*ptccolr;
 FIGURE	        *ptfig;

 {
 chain_list	*ptccollprec = NULL;
 chain_list	*ptccolrprec = NULL;
 chain_list	*ptc;
 chain_list	*ptctmp;
 COLUMN		*ptcolr;
 COLUMN		*ptcoll;
 int		 index;

 for (ptc=ptfig->COL;ptc;ptc=ptc->NEXT)
     {
     if (ptc->NEXT==ptccoll)
        ptccollprec = ptc;
     else
        if (ptc->NEXT==ptccolr)
           ptccolrprec=ptc;
     }

 if (!ptccollprec)
    {
    printf("BUG: There is a problem in column exchange!!\n");
    exit(6);
    }
 if (!ptccolrprec)
    {
    printf("BUG: There is a problem in column exchange!!\n");
    exit(6);
    }

 ptccolrprec->NEXT = ptccoll;
 ptccollprec->NEXT = ptccolr;
 ptctmp = ptccoll->NEXT;
 ptccoll->NEXT = ptccolr->NEXT;
 ptccolr->NEXT = ptctmp;

 ptcoll = (COLUMN *)ptccoll->DATA;
 ptcolr = (COLUMN *)ptccolr->DATA;
 index = ptcoll->INDEX;
 ptcoll->INDEX = ptcolr->INDEX;
 ptcolr->INDEX = index;

 return (ptfig);
 }

/********************************************************
*                fonction        localgain()	     	*
********************************************************/
 int      localgain(ptcoll,ptcolr,coll,colr)
 COLUMN	*ptcoll;
 COLUMN	*ptcolr;
 int     coll,colr;

 {
 long		 lsigsl=0;
 long		 lsigsr=0;
 long		 lsigspermr=0;
 long		 lsigsperml=0;
 int		 index;
 chain_list	*ptcsig;
 SIGNAL		*ptsig;
 char            *vdd,*vss;

 vdd = namealloc("vdd");
 vss = namealloc("vss");

 for (ptcsig=ptcoll->SIG;ptcsig;ptcsig=ptcsig->NEXT)
     {
     ptsig = (SIGNAL *)ptcsig->DATA;
     if (strncmp(ptsig->NAME,vdd,3)&&strncmp(ptsig->NAME,vss,3))
        {
        lsigsl = lsigsl + ptsig->WIDTH;
        }
     }

 for (ptcsig=ptcolr->SIG;ptcsig;ptcsig=ptcsig->NEXT)
     {
     ptsig = (SIGNAL *)ptcsig->DATA;
     if (strncmp(ptsig->NAME,vdd,3)&&strncmp(ptsig->NAME,vss,3))
        {
        lsigsr = lsigsr + ptsig->WIDTH;
        }
     }

/* permutation des deux indices des colonnes */
 index = ptcoll->INDEX;
 ptcoll->INDEX = ptcolr->INDEX;
 ptcolr->INDEX = index;

 for (ptcsig=ptcoll->SIG;ptcsig;ptcsig=ptcsig->NEXT)
     {
     ptsig = (SIGNAL *)ptcsig->DATA;
     if (strncmp(ptsig->NAME,vdd,3)&&strncmp(ptsig->NAME,vss,3))
        {
        lsigsperml = lsigsperml + longsig(ptsig,coll,colr);
        }
     }

 for (ptcsig=ptcolr->SIG;ptcsig;ptcsig=ptcsig->NEXT)
     {
     ptsig = (SIGNAL*)ptcsig->DATA;
     if (strncmp(ptsig->NAME,vdd,3)&&strncmp(ptsig->NAME,vss,3))
        {
        lsigspermr = lsigspermr + longsig(ptsig,coll,colr);
        }
     }

/* comme avant permutation */
 index = ptcoll->INDEX;
 ptcoll->INDEX = ptcolr->INDEX;
 ptcolr->INDEX = index;

 return((lsigsr+lsigsl)-(lsigspermr+lsigsperml));

 }

/********************************************************
*                fonction        permut()		*
********************************************************/
 int      permut(ptfig,coll,colr)
 FIGURE	*ptfig;
 int     coll,colr;

 {
 int		 gainloc,lsigs,gaintotal=0;
 chain_list	*ptccoll,*ptccolr;
 chain_list	*ptccollbest,*ptccolrbest;
 chain_list	*ptccol,*ptccolendO;
 COLUMN		*ptcoll,*ptcolr;
 int		 gainbest=0;

 for (ptccol=ptfig->COL;ptccol;ptccol=ptccol->NEXT)
     {
     if (((COLUMN *)ptccol->DATA)->TYPE=='O')
        ptccolendO = ptccol;
     }

 for (ptccoll=ptfig->COL;ptccoll->NEXT!=ptccolendO;ptccoll=ptccoll->NEXT)
     {
     ptcoll = (COLUMN *)ptccoll->DATA;
     if (ptcoll->TYPE=='O')
        {
        for (ptccolr=ptccoll->NEXT;ptccolr;ptccolr=ptccolr->NEXT)
            {
            ptcolr = (COLUMN *)ptccolr->DATA;
            if (ptcolr->TYPE=='O')
               {
               gainloc = localgain(ptcoll,ptcolr,coll,colr);
               if (gainloc>gainbest)
                  {
                  ptccollbest = ptccoll;
                  ptccolrbest = ptccolr;
                  gainbest = gainloc;
                  }
               }
            }
        }
     }
 if (gainbest>0)
    {
    ptfig = exchange(ptfig,ptccollbest,ptccolrbest);
    }
 gaintotal=gainbest;
 return (gaintotal);
 }

/********************************************************
*            fonction        optiplace()		*
********************************************************/
 int     optiplace(ptfig)
 FIGURE	*ptfig;

 {
 char        *vdd,*vss;
 int          i=0;
 int          colmin=MAXINT,colmax=0,colcour;
 long         lengthsigs=0,gaintotal=1;
 long         xcol_pere;
 COLUMN	     *ptcol;
 SIGNAL      *ptsig;
 chain_list  *ptccol;
 chain_list  *ptcsig;
 chain_list  *ptccoll=NULL;
 chain_list  *ptccolr=NULL;
 COLUMN      *ptcoll=NULL;
 COLUMN      *ptcolr=NULL;
 chain_list  *ptccon=NULL;
 CONNECTOR   *ptcon=NULL;
 POSSIBILITY *ptpos=NULL;
 int          flagperm;

 vdd = namealloc("vdd");
 vss = namealloc("vss");

 ptccoll = ptfig->COL;
 for (ptccolr=ptccoll;ptccolr->NEXT;ptccolr=ptccolr->NEXT);
 ptcoll = (COLUMN *)ptccoll->DATA;
 ptcolr = (COLUMN *)ptccolr->DATA;

/* marquage des signaux externes auxquels sont connectes les     */
/* connecteurs du pere non places par le concepteur              */
 
 for (ptccon=ptfig->CON;ptccon;ptccon=ptccon->NEXT)
     {
     ptcon = (CONNECTOR *)ptccon->DATA;
     ptpos = (POSSIBILITY *)ptcon->POS->DATA;
     if ((!ptcon->COL)&&(ptpos->ACCES==ORIENTX)) /* c.a.d DF con non place */
        {
        ptsig = (SIGNAL *)ptcon->SIG->DATA;
        ptsig->USER = addchain(ptsig->USER,(void *)'X');
        if ((ptsig->MIN_COL-ptcoll->INDEX)< 
            (ptcolr->INDEX-ptsig->MIN_COL-ptsig->WIDTH))
           {
           ptsig->WIDTH = ptsig->MIN_COL + ptsig->WIDTH - ptcoll->INDEX;
           }
        else
           {
           ptsig->WIDTH = ptcolr->INDEX -
           ((ptsig->MIN_COL==MAXINT) ? ptcolr->INDEX : ptsig->MIN_COL);
           }
        }
     }

/* calcul de la longueur totale initiale */
 for (ptcsig=ptfig->SIG;ptcsig;ptcsig=ptcsig->NEXT)
     {
     ptsig=(SIGNAL *)ptcsig->DATA;
     if (strncmp(ptsig->NAME,vdd,3)&&strncmp(ptsig->NAME,vss,3))
        {
        /*printf("-----------------------------\n");
        printf("name: %s\n",ptsig->NAME);
        printf("index: %ld\n",ptsig->INDEX);
        printf("mincol: %ld\n",ptsig->MIN_COL);
        printf("width: %ld\n",ptsig->WIDTH);*/
        lengthsigs = lengthsigs + ptsig->WIDTH;
        /*printf("totalwidth: %ld\n",lengthsigs);*/
        }
     }

/* iteration sur d'eventuelles permutations de colonnes*/
 while (gaintotal>0)
       {
       printf("-----------------------------\n");
       printf("totalwidth before: %ld\n",lengthsigs);
       i++;
       gaintotal = permut(ptfig,ptcoll->INDEX,ptcolr->INDEX);
       lengthsigs = longsigs(ptfig,ptcoll->INDEX,ptcolr->INDEX);
       printf("totalwidth after : %ld\n",lengthsigs);
       }

/* mise a jour du nom et de l'ordonnee des differentes colonnes si permutes */
 if (i!=1)
    {
    xcol_pere=((COLUMN *)ptfig->COL->DATA)->X;
    for (ptccol=ptfig->COL;ptccol;ptccol=ptccol->NEXT)
        {
        ptcol = (COLUMN *)ptccol->DATA;
        if (ptcol->TYPE == 'O')
           ptcol->NAME = nameindex("DPR_O",ptcol->INDEX);
        else
           if (ptcol->TYPE == 'C')
              ptcol->NAME = nameindex("DPR_C",ptcol->INDEX);
           else
              if (ptcol->TYPE == 'R')
                 ptcol->NAME = nameindex("DPR_R",ptcol->INDEX);
              else
                 if (ptcol->TYPE == 'L')
                    ptcol->NAME = nameindex("DPR_L",ptcol->INDEX);
        ptcol->X = xcol_pere;
        xcol_pere = xcol_pere + ptcol->WIDTH;
        }
    flagperm = 1;
    }
 else
    {
    flagperm = 0;
    }

/* mise a jour de MIN_COL et WIDTH des differents signaux */
 for (ptcsig=ptfig->SIG;ptcsig;ptcsig=ptcsig->NEXT)
     {
     ptsig = (SIGNAL *)ptcsig->DATA;
     if (strncmp(ptsig->NAME,vdd,3)&&strncmp(ptsig->NAME,vss,3))
        {
        colmax = 0;
        colmin = MAXINT;
        for (ptccol=ptsig->COL;ptccol;ptccol=ptccol->NEXT)
            {
            colcour = ((COLUMN *)ptccol->DATA)->INDEX;
            colmin = (colmin>colcour) ? colcour : colmin;
            colmax = (colcour>colmax) ? colcour : colmax;
            }
        ptsig->MIN_COL = colmin;
        ptsig->WIDTH = colmax - colmin;
        }
     }

 return(flagperm);
 }
