/********************************************************************
*                                                                   *
* 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                     *
*                                                                   *
********************************************************************/
#include "dpr_R.h"

DPP_SPACE *tab[MAXLIN][MAXCOL];
DPP_DATAPATH *ptdatapath;
int WL;
int DENSITY;
int DEPASS;
int interne[3];

/*************************************************************************/
/*     Calcul de  la longueur totale des  signaux                        */    
/*************************************************************************/
long totalsiglengh(pt)
DPP_DATAPATH *pt;
{
long lenghtsigs=0;
chain_list *ptcsig=NULL;
DPP_SIGNAL *ptsig=NULL;

for(ptcsig=pt->SIG;ptcsig;ptcsig=ptcsig->NEXT)
   {
   ptsig = (DPP_SIGNAL *)ptcsig->DATA;
   lenghtsigs = lenghtsigs + (ptsig->width);
   }
return(lenghtsigs);
}

/******************************************************************/
/*           Fonction siglengh():Longueur des signaux             */
/*                               d'une colonne                       */
/******************************************************************/
int siglengh(j, lig)
int j;
int lig;
{
DPP_SPACE *ptspace;
struct chain *ptsig=NULL;
DPP_SIGNAL *ptcsig=NULL;
int lengh=0;
int i=0;

for(i=0;i<lig;i++)
   {
    ptspace=tab[i][j];
    if(ptspace !=NULL)
      {
      for(ptsig=ptspace->SIG;ptsig;ptsig=ptsig->NEXT)
         {
         ptcsig=(DPP_SIGNAL *)ptsig->DATA;
        /*printf("sig_name:%s\n",ptcsig->NAME);*/
         if(ptcsig->COMPUTE ==1)
           {
           lengh=(lengh + ptcsig->width);
           ptcsig->COMPUTE=0;/*ne pas compter la longeur de ce signal s'il
                               apparait une 2eme fois dans la colonne*/
           }
         }
      }
   }
/* Remise a jour du champ COMPUTE pour chaque signal */
for(i=0;i<lig;i++)
   {
    ptspace=tab[i][j];
    if(ptspace !=NULL)
      {
      for(ptsig=ptspace->SIG;ptsig;ptsig=ptsig->NEXT)
         {
         ptcsig=(DPP_SIGNAL *)ptsig->DATA;
         ptcsig->COMPUTE=1;
         }
      }
   }
return(lengh);
}
/******************************************************************/
/*       Fonction siglengh_perm():Longueur des signaux        */
/*                               d'une colonne apres permutation. */
/******************************************************************/
int siglengh_perm(j, lig)
int j;
int lig;
{
DPP_SPACE *ptspace;
struct chain *ptsig=NULL;
DPP_SIGNAL *ptcsig=NULL;
int lengh=0;
int i=0;

for(i=0;i<lig;i++)
   {
    ptspace=tab[i][j];
    if(ptspace !=NULL)
      {
      for(ptsig=ptspace->SIG;ptsig;ptsig=ptsig->NEXT)
         {
         ptcsig=(DPP_SIGNAL *)ptsig->DATA;
         if(ptcsig->COMPUTE ==1)
           {
           lengh=(lengh + ptcsig->TMP_width);
           ptcsig->COMPUTE=0;/*ne pas compter la longeur de ce signal s'il
                               apparait une 2eme fois dans la colonne*/
           }
         }
      }
   }
/* Remise a jour du champ COMPUTE pour chaque signal */
for(i=0;i<lig;i++)
   {
    ptspace=tab[i][j];
    if(ptspace !=NULL)
      {
      for(ptsig=ptspace->SIG;ptsig;ptsig=ptsig->NEXT)
         {
         ptcsig=(DPP_SIGNAL *)ptsig->DATA;
         ptcsig->COMPUTE=1;
         }
      }
   }
return(lengh);
}

/******************************************************************/
/*          Calcul du minimum de 2 index                          */ 
/******************************************************************/
int mini(i,j)
int i,j;
{
int minimum=0;

if (i<j)
   minimum = i;
else
   minimum = j;

return(minimum);
}

/******************************************************************/
/*          Calcul du maximum de 2 index                          */ 
/******************************************************************/
int maxi(i,j)
int i,j;
{
int maximum=0;

if (i>j)
   maximum = i;
else
   maximum=j;

return(maximum);
}

/******************************************************************/
/*           Fonction min_index():min des indices des colonnes    */
/******************************************************************/
int min_index(ptsig)
DPP_SIGNAL *ptsig;
{
chain_list *ptcol=NULL;
int colo=0;
int min=0;

ptcol=ptsig->COL;
colo=(int)ptcol->DATA;
min=colo;

for(ptcol=ptcol->NEXT;ptcol;ptcol=ptcol->NEXT)
   { 
   colo=(int)ptcol->DATA;
   if(colo < min)
     {
     min=colo;
     } 
   } 
return(min);
}
/******************************************************************/
/*         max_index():max des indices des colonnes du signal     */
/******************************************************************/
int max_index(ptsig)
DPP_SIGNAL *ptsig;
{
chain_list *ptcol=NULL;
int colo=0;
int max=0;

ptcol=ptsig->COL;
colo=(int)ptcol->DATA;
max=colo;

for(ptcol=ptcol->NEXT;ptcol;ptcol=ptcol->NEXT)
   { 
   colo=(int)ptcol->DATA;
   if(colo > max)
     {
     max=colo;
     } 
   } 
return(max);
} 
/******************************************************************/
/*       update_j():Mise a jour liste des colonnes                  */
/******************************************************************/
void update_j(k, col, ptsig)
int k, col;
DPP_SIGNAL *ptsig;
{
chain_list *ptcol=NULL;
int colo=0;

if(k > (col+1)-k)
   {
   for(ptcol=ptsig->COL;ptcol;ptcol=ptcol->NEXT)
      { 
      colo=(int)ptcol->DATA;
      if(colo==0)
        {
        ptcol->DATA=((void *)(col+1)); 
        }
      }
   }
}
/*********************************************************************/
/*       update_k():Mise a jour de la liste des colonnes             */
/*                  d'un signal rattache a un connecteur de la figure*/ 
/********************************************************************/
void update_k(j, col, ptsig)
int j, col;
DPP_SIGNAL *ptsig;
{
chain_list *ptcol=NULL;
int colo=0;

if(j < (col+1)-j)
   {
   for(ptcol=ptsig->COL;ptcol;ptcol=ptcol->NEXT)
      { 
      colo=(int)ptcol->DATA;
      if(colo==col+1)
        {
        ptcol->DATA=((void *)0);
        }
      }
   }
}
/***********************************************************************/
/* is_min():Mise a jour de l'index min de colonne dans la liste des col */
/*          d'un signal rattache a un connecteur de la figure          */ 
/***********************************************************************/
int is_min(j, col, ptsig)
int j, col;
DPP_SIGNAL *ptsig;
{
chain_list *ptcol=NULL;
int colo=0;
int ind=0, flag=0;

if (j<(col+1)-j)
   {
   for(ptcol=ptsig->COL;ptcol;ptcol=ptcol->NEXT)
      { 
      colo=(int)ptcol->DATA;
      if (colo==col+1)
         {
         ind=0; 
         flag=1;
         }
      else
         if (flag==0)
            {
            ind=1; 
            }
      }
   }
else
   { 
   ind=1;
   } 
return(ind);
}
/***********************************************************************/
/* is_max():Mise a jour de l'index max de colonne dans la liste des col */
/*          d'un signal rattache a un connecteur de la figure          */ 
/***********************************************************************/
int is_max(k, col, ptsig)
int k, col;
DPP_SIGNAL *ptsig;
{
chain_list *ptcol=NULL;
int colo=0;
int ind=0, flag=0; 

if(k>(col+1)-k)
   {
   for(ptcol=ptsig->COL;ptcol;ptcol=ptcol->NEXT)
      { 
      colo=(int)ptcol->DATA;
      if (colo==0)
         {
         ind=0; 
         flag=1;
         }
      else
         if (flag==0)
            {
            ind=1;
            }
      }
   }
else
   { 
   ind=1;
   } 
return(ind);
}
/******************************************************************/
/*       insert_new_sig():Remplacer l'indice j par l'indice k     */
/*                        dans la liste des indices des colonnes  */
/******************************************************************/
void insert_new_index(ptsig, old_index, new_index)
DPP_SIGNAL *ptsig;
int old_index;
int new_index;
{
chain_list *column=NULL;
chain_list *pt=NULL;
int colo=0;
int flag=0;

/*Le nouvel index se trouve t-il deja dans la liste?*/
for(column=ptsig->COL;column;column=column->NEXT)
   {
   colo=(int)column->DATA;
   if(colo==new_index)
     {                
     flag=1;
     }
   }

/*Le nouvel index ne se trouve pas dans la liste,donc remplacer*/
/*l'ancien index par le nouveau.                               */
if(flag==0)
   {
   for(column=ptsig->COL;column;column=column->NEXT)
      {
      colo=(int)column->DATA;
      if(colo==old_index)
        {
        pt=column;
        pt->DATA=((void *)new_index);
        }
     }
   }
}
/******************************************************************/
/*         new_width():nouvelles longueurs des signaux apres      */
/*                     permutations.                              */
/******************************************************************/
int new_width(ptsig, j, k)
DPP_SIGNAL *ptsig;
int j;
int k;
{
chain_list *column=NULL;
int colo=0;
int width=0;
int mincol=MAXCOL;
int maxcol=-1;

for(column=ptsig->COL;column;column=column->NEXT)
   {
   colo=(int)column->DATA;
   if(colo==j)
     {
     mincol=mini(mincol,k);
     maxcol=maxi(maxcol,k);
     }
   else if(colo==k)
     {
     mincol=mini(mincol,j);
     maxcol=maxi(maxcol,j);
     }
   else 
     {
     mincol=mini(mincol,colo);
     maxcol=maxi(maxcol,colo);
     }
   }
ptsig->TMP_MIN_COL=mincol;
width=(maxcol - mincol);
return(width);
}
/******************************************************************/
/*           update_signals_k():Mise a jour des champs TMP_MIN_COL*/
/*                              et TMP_width.                     */
/******************************************************************/
void update_signals(j, k, lig)
int j;
int k;
int lig;
{
int i=0;
DPP_SPACE      *ptspace=NULL;
chain_list *sig=NULL;
DPP_SIGNAL     *ptsig=NULL;

/* Mise a jour des signaux de la colonne j */
for(i=0;i<lig;i++)
   {
   ptspace=tab[i][j];
   if(ptspace!=NULL)
     {
     for(sig=ptspace->SIG;sig;sig=sig->NEXT)
        {
        ptsig=(DPP_SIGNAL  *)sig->DATA;
        ptsig->TMP_MIN_COL=ptsig->MIN_COL;
        ptsig->TMP_width=ptsig->width;
        }
     }
   }
/* Mise a jour des signaux de la colonne k */
for(i=0;i<lig;i++)
   {
   ptspace=tab[i][k];
   if(ptspace!=NULL)
     {
     for(sig=ptspace->SIG;sig;sig=sig->NEXT)
        {
        ptsig=(DPP_SIGNAL  *)sig->DATA;
        ptsig->TMP_MIN_COL=ptsig->MIN_COL;
        ptsig->TMP_width=ptsig->width;
        }
     }
   }
}
/******************************************************************/
/*           Fonction dpp_permut():permutation des colonnes           */
/******************************************************************/
void dpp_permut(j,k,lig,col)
int j,k,lig,col;
{
int i, max=0, min=0;
DPP_SPACE *ptspace1=NULL;
DPP_SPACE *ptspace2=NULL;
chain_list *sig=NULL;
chain_list *column=NULL;
DPP_SIGNAL *ptsig=NULL;
DPP_SIGNAL *ptsig2=NULL;
int colo=0;
int width1=0, width2=0;

/*Nouveau width pour tous  les signaux de la colonne j permutee avec*/
/*la colonne k*/                                 
/*printf("PERMUTATION DE %d ET DE %d\n",j,k);*/
for(i=0;i<lig;i++)
   {
   ptspace1=tab[i][j];
   if(ptspace1!=NULL)
     {
     for(sig=ptspace1->SIG;sig;sig=sig->NEXT)
        {
        ptsig = (DPP_SIGNAL *)sig->DATA;
        /*printf("sig_name:%s\n",ptsig->NAME);*/
        if(ptsig->width!=0)
          {
          if(is_max(k,col,ptsig)==0)
            { 
            max = col + 1;
            insert_new_index(ptsig,0,max);
            width1 = new_width(ptsig,j,k);
            insert_new_index(ptsig,max,0);/*Remettre l'index initial*/
            }
          else
            {
            width1 = new_width(ptsig,j,k);
            }
          ptsig->TMP_width = width1;
          }
        }
     }
   }

/*Nouveau width pour tous  les signaux de la colonne k permutee avec*/
/*la colonne j*/
for(i=0;i<lig;i++)
   {
   ptspace2=tab[i][k];
   if(ptspace2!=NULL)
     {
     for(sig=ptspace2->SIG;sig;sig=sig->NEXT)
        {
        ptsig = (DPP_SIGNAL *)sig->DATA; 
        /*printf("sig_name:%s\n",ptsig->NAME);*/
        if(ptsig->width!=0)
          {
          if(is_min(j,col,ptsig)==0)
            {
            insert_new_index(ptsig,col+1,0);
            width2 = new_width(ptsig,j,k);
            insert_new_index(ptsig,0,col+1);/*Remettre l'index initial*/
            }
          else
            {
            width2 = new_width(ptsig,j,k);
            }
          ptsig->TMP_width = width2;
          }
        }
     }
   }
}
/******************************************************************/
/*       real_permut():permutation effective des colonnes         */
/*                     avec mise a jour des indices               */
/******************************************************************/
void real_permut(j, k, lig, col)
int j, k, lig, col;
{
int        i=0;
DPP_SPACE      *ptspace1=NULL;
DPP_SPACE      *ptspace2=NULL;
DPP_SPACE      *ptspace=NULL;
DPP_SPACE      *ptemp=NULL;
chain_list *sig=NULL;
chain_list *column=NULL;
DPP_SIGNAL     *signal=NULL;
int aux=0;
int colo=0;

/* Echange des indices des colonnes j et k             */
/* Et mise a jour de la liste des indices de colonnes  */
/* pour les signaux concernes.                         */

for(i=0;i<lig;i++)
   {
   ptspace=tab[i][j];
   if(ptspace!=NULL)
     {
     ptspace->J=k;
     for(sig=ptspace->SIG;sig;sig=sig->NEXT)
        {
        signal=(DPP_SIGNAL *)sig->DATA;
        /*printf("sig_name:%s\n",signal->NAME);*/
        update_j(k, col, signal);
        insert_new_index(signal, j, k);
        signal->MIN_COL=min_index(signal);
        signal->TMP_MIN_COL=signal->MIN_COL;
        signal->width=signal->TMP_width;
        }
     }
   }
	
for(i=0;i<lig;i++)
   {
   ptspace=tab[i][k];
   if(ptspace!=NULL)
     {
     ptspace->J=j;
     for(sig=ptspace->SIG;sig;sig=sig->NEXT)
        {
        signal=(DPP_SIGNAL *)sig->DATA;
        /*printf("sig_name:%s\n",signal->NAME);*/
        update_k(j, col, signal);
        insert_new_index(signal,k,j);
        signal->MIN_COL=min_index(signal);
        signal->TMP_MIN_COL=signal->MIN_COL;
        signal->width=signal->TMP_width;
        }
     }
   }

/* Permutation des elements un par un */
for(i=0;i<lig;i++)
   {
   ptspace1=tab[i][j];
   ptspace2=tab[i][k];
   if(ptspace1!=NULL || ptspace2!=NULL)
     {
     ptemp=tab[i][j];
     tab[i][j]=tab[i][k];
     tab[i][k]=ptemp;
     }
   }
}
/******************************************************************/
/*            test():test de la fonction real_permut()           */
/******************************************************************/
void test(lig, col)
int lig;
int col;
{
int i=0,j=0,k=0;
int flag=1;

for(j=1;j<=col;j++)
   {
   for(k=j+1;k<=col;k++)
      {
      /*real_permut(j, k, lig, col);*/
      flag = routable(j,k,lig,col); 
      }
   }
}
/******************************************************************/
/*     init_tab():Ecriture de la configuration initiale dans      */
/*                le tableau de sauvegarde et initialisation du   */       
/*                tableau des resultats intermediaires.           */
/******************************************************************/
void init_tab(lig,col)
int lig;
int col;
{
int j=0;
int i=0;
int capa=0;
int dens=0;
int maxdens=0;
int ovrf=0;
int maxovrf=0;

for(i=0;i<3;i++)
   {
   interne[i]=0;
   }

for(j=1;j<=col;j++)
   {
   capa = capacity(j,lig,col);
   dens = density(j);
   if (dens > maxdens)
      maxdens = dens;
   ovrf = dens - capa;
   if (ovrf > maxovrf)
      maxovrf = ovrf;
   }

printf("++++++++++++++++++++++++++++\n");
WL = totalsiglengh(ptdatapath);
DENSITY = maxdens;
DEPASS = maxovrf;
if (DEPASS==0)
   printf("Routable Initial Configuration\n");
else
   printf("Non Routable Initial Configuration\n");
printf("Initial total Wire Length      (WL): %ld\n",WL);
printf("Initial maximum Track Density  (TD): %ld\n",DENSITY);
printf("Initial maximum Track Overflow (TO): %ld\n",DEPASS);
printf("++++++++++++++++++++++++++++\n");
}

/****************************************************************/
/*               Calcul de la densite du circuit                */   
/****************************************************************/
int density(j)
int j;
{
int i;
int dens=0;
DPP_SPACE *ptspace=NULL;
DPP_SIGNAL *sig=NULL;
chain_list *ptsig=NULL;

for(ptsig=ptdatapath->SIG;ptsig;ptsig=ptsig->NEXT)
    {
     sig=(DPP_SIGNAL *)ptsig->DATA;
     if(sig->TMP_width !=0)
       {
       if(j==(sig->TMP_MIN_COL))
         {
         dens++;
         }
       else if(j==(sig->TMP_MIN_COL + sig->TMP_width)) 
         {
         dens++;
         }
       else if((j < (sig->TMP_MIN_COL + sig->TMP_width)) && 
              ( j > sig->TMP_MIN_COL))
         {
         dens=dens+2;
         }
       }
     }
return(dens);
}
  
/****************************************************************/
/*               Calcul de la densite max d'une colonne         */   
/****************************************************************/
int capacity(j,lig,col)
int j;
int lig;
int col;
{
int i;
int jcour;
int max=0;
int cap=0;
DPP_SPACE *ptspace;
DPP_SPACE *ptspacecour;

for(i=0;i<lig;i++)
   {
   ptspace = tab[i][j];
   if (ptspace!=NULL)
      {
      cap = cap + ptspace->TRACK_CAPACITY;
      }
   else
      {
      for(jcour=1;jcour<=col;jcour++)
         {
         ptspacecour = tab[i][jcour];
         if (ptspacecour!=NULL)
            {
            if (ptspacecour->TRACK_CAPACITY>max)
               max = ptspacecour->TRACK_CAPACITY;
            }
         }
      cap = cap + max;
      }
   }
return(cap);
}

/****************************************************************/
/*               Routabilite du circuit                         */   
/****************************************************************/
int routable(j,k,lig,col)
int j;
int k;
int lig;
int col;
{
int  c=0;
int  l=0;
int  flag=1;
int  capa=0;
int  dens=0;
int  maxdens=0;
int  ovrf=0;
int  maxovrf=0;

for(c=j;c<=k;c++)
   {
   capa = capacity(c,lig,col);
   dens = density(c);
   ovrf = dens - capa;
   if (dens > maxdens)
      maxdens = dens;
   if (ovrf > maxovrf)
      maxovrf = ovrf;
   }
interne[1] = maxdens;
interne[2] = maxovrf;
if (maxovrf>0)
   flag=0;
return(flag);
}

/*******************************************************************/
/*           Fonction opti1():permutation et optimisation          */
/*           tant qu'on gagne, on permute les colonnes             */
/*******************************************************************/
void opti1(lig, col)
int lig;
int col;
{
int index=0, c=0;
int i, j, k;
int left_sig=0;
int left_sig_perm=0;
int right_sig=0;
int right_sig_perm=0;
int gain=0;
int flag=1;
int ind=1;
int root=0;

init_tab(lig,col);  /*Ecriture de la configuration initiale
                       dans le tableau de sauvegarde */

while (flag==1)
  {
  flag=0;
  for(j=1;j<col;j++)
     {
     for(k=j+1;k<=col;k++)
        {
        left_sig = siglengh(j,lig);
        right_sig = siglengh(k,lig);
        dpp_permut(j,k,lig,col);
        if (routable(j,k,lig,col)==1)
           {
           left_sig_perm = siglengh_perm(j,lig);
           right_sig_perm = siglengh_perm(k,lig);
           gain = ((left_sig+right_sig)-(left_sig_perm+right_sig_perm));
           if (gain>0)
              {
              flag=1;
              real_permut(j,k,lig,col);
              WL = totalsiglengh(ptdatapath);
              DENSITY = interne[1];
              DEPASS = interne[2];
              printf("Routable Configuration\n");
              printf("Total Wire Length      (WL): %ld\n",WL);
              printf("Maximum Track Density  (TD): %ld\n",DENSITY);
              printf("Maximum Track Overflow (TO): %ld\n",DEPASS);
              printf("++++++++++++++++++++++++++++\n");
              }
           }
        else /* non routable */
           {
           if (interne[2] < DEPASS)
              {
              flag=1;
              real_permut(j,k,lig,col);
              WL = totalsiglengh(ptdatapath);
              DENSITY = interne[1];
              DEPASS = interne[2];
              printf("Non Routable Configuration\n");
              printf("Total Wire Length      (WL): %ld\n",WL);
              printf("Maximum Track Density  (TD): %ld\n",DENSITY);
              printf("Maximum Track Overflow (TO): %ld\n",DEPASS);
              printf("++++++++++++++++++++++++++++\n");
              }
           }
        /*Mise a jour de TMP_MIN_COL et TMP_width*/
        update_signals(j,k,lig);
        }
     }
  }
}

/*******************************************************************/
/*           Fonction opti2():permutation et optimisation          */
/*           on gagne => on permute et on recommence               */
/*******************************************************************/
void opti2(lig, col)
int lig;
int col;
{
int index=0, c=0;
int i, j, k;
int left_sig=0;
int left_sig_perm=0;
int right_sig=0;
int right_sig_perm=0;
int gain=0;
int flag=1;
int ind=1;
int root=0;

init_tab(lig,col);  /*Ecriture de la configuration initiale
                       dans le tableau de sauvegarde */

while (flag==1)
  {
  flag=0;
  for(j=1;j<col;j++)
     {
     for(k=j+1;k<=col;k++)
        {
        left_sig = siglengh(j,lig);
        right_sig = siglengh(k,lig);
        dpp_permut(j,k,lig,col);
        if (routable(j,k,lig,col)==1)
           {
           left_sig_perm = siglengh_perm(j,lig);
           right_sig_perm = siglengh_perm(k,lig);
           gain = ((left_sig+right_sig)-(left_sig_perm+right_sig_perm));
           if (gain>0)
              {
              flag=1;
              real_permut(j,k,lig,col);
              WL = totalsiglengh(ptdatapath);
              DENSITY = interne[1];
              DEPASS = interne[2];
              printf("Routable Configuration\n");
              printf("Total Wire Length      (WL): %ld\n",WL);
              printf("Maximum Track Density  (TD): %ld\n",DENSITY);
              printf("Maximum Track Overflow (TO): %ld\n",DEPASS);
              printf("++++++++++++++++++++++++++++\n");
              break;
              }
           }
        else /* non routable */
           {
           if (interne[2] < DEPASS)
              {
              flag=1;
              real_permut(j,k,lig,col);
              WL = totalsiglengh(ptdatapath);
              DENSITY = interne[1];
              DEPASS = interne[2];
              printf("Non Routable Configuration\n");
              printf("Total Wire Length      (WL): %ld\n",WL);
              printf("Maximum Track Density  (TD): %ld\n",DENSITY);
              printf("Maximum Track Overflow (TO): %ld\n",DEPASS);
              printf("++++++++++++++++++++++++++++\n");
              break;
              }
           }
        /*Mise a jour de TMP_MIN_COL et TMP_width*/
        update_signals(j,k,lig);
        }
     if (flag==1)
        break;
     }
  }
}
