/*
+-------------------------------------+
| Fibonacci to Galois NLFSR optimizer |
| v1.1 - March 23, 2009               |
|                                     |
| Jean-Michel Chabloz                 |
| chabloz@kth.se                      |
| KTH, Stockholm, Sweden              |
+-------------------------------------+
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define MAX_INPUT_SIZE 1024  /* maximum number of characters in the input string */
#define XOR_WEIGHT 2         /* weight of the XOR compared to AND */
#define FREEBINS_WEIGHT 1    /* importance given to the number of free bins while choosing which product should be placed next */
#define AHCOST_WEIGHT 1      /* importance given to the average hypotetical cost while choosing which product should be placed next */
#define PLACEMENT 1          /* 1 to activate deterministic AHCOST-FREEBINS placement, 0 to deactivate */
#define RANDOMPLACEMENT 0    /* 1 to activate random placement, 0 to deactivate */
#define INTPOSTPLACEMENT 1   /* 1 to activate intelligent postplacement, 0 to deactivate */
#define TECHNOLOGY 1         /* 0 - no critical path estimation, 1 - TSMC 90 nm */
#define VERBOSE 1            /* 1 for verbose output, 0 for non-verbose output */

typedef struct 
  {
  int nterms;
  int *terms;
  int min_bin;
  double cost;
  int bin;
  int freebins;
  double ahcost;
  }
prod;

typedef struct
  {
  int nprods;
  int allowed;
  }
bin;

/* function prototypes */
int print_galois(prod*, bin*, int, int);
double calculate_cost(int, int, prod*, bin*, int);
int main(void);

/* prints to screen the Galois configuration */
int print_galois(prod* products, bin* bins, int nprods, int nbins)
  {
  int index;
  int i;
  int j;
  int k;
  int first;
  int elements;
  first=1;
  for(i=nbins;i>=0;i--)
    {
    elements=0;
    for(k=0;k<nprods;k++)
      if(products[k].bin==i)
        elements++;
    if(elements>0)
      {
      printf("f%d =",i);
      if(i<nbins)
        printf(" x%d",i+1);
      for(index=0;index<nprods;index++)
        if((products[index].bin==i))
          {
          if(first)
            {
            printf(" ");
            first=0;
            }
          else
            {
            printf(" + ");
            }
          for(j=0;j<products[index].nterms;j++)
            printf("x%d", products[index].terms[j]+i-nbins);
          }
      printf("\n");
      }
    }

  printf("\n");

  for(i=nbins;i>=0;i--)
    {
    elements=0;
    for(k=0;k<nprods;k++)
      if(products[k].bin==i)
        elements++;
    if(elements>0)
      {
      if(i!=nbins)
        elements++;
      //printf("f%d: %d products, cost %.2f\n",i,elements,calculate_cost(nprods,nbins,products,bins,i));
      }
    }
  return 1;
  }

/* calculates the cost of a single bin by doing a two-input AND/XOR optimal synthesis */
double calculate_cost(int np, int nb, prod* products, bin* bins, int bin_id)
  {
  int i;
  int j;
  int iter;
  int best1;
  int best2;
  int nprods;

  double* costs;

  nprods=bins[bin_id].nprods;

  costs=(double*)malloc((nprods)*sizeof(double));

  if(bin_id==nb)
    j=0;
  else
    {
    costs[0]=0;
    j=1;
    }

  for(i=0;i<np;i++)
    if(products[i].bin==bin_id)
      {
      costs[j]=products[i].cost;
      j++;
      }

  if(nprods==0)
    return 0;

  if(nprods==1)
    return costs[0];

  for(iter=0;iter<nprods-1;iter++)
    {
    best1=-1;
    best2=-1;
    for(i=0;i<nprods;i++)
      if(costs[i]>=0)
        {
        if(best1==-1)
          best1=i;
        else
          {
          if( (best1!=-1) && (best2==-1) )
            {
            if(costs[best1]<=costs[i])
              best2=i;
            else
              {
              best2=best1;
              best1=i;
              }
            }
          else
            {
            if( (costs[i]<=costs[best1]) )
              {
              best2=best1;
              best1=i;
              }
            else
              if( (costs[i]>costs[best1]) && (costs[i]<costs[best2]))
                best2=i;
            }
          }
        }
    costs[best2]+=XOR_WEIGHT;
    costs[best1]=-1;
    }
  return costs[best2];
  }

int main(void)
  {
  bin *bins;
  prod *products;
  char func[MAX_INPUT_SIZE];
  char* unallowed_pos_ptr;
  char* func_ptr;
  char* func_start;
  int unallowed_pos;
  char op;
  int nbins;
  int nprods;
  int i,j;
  int firstn;
  int secondn;
  int tau;
  int min;
  int max;
  int max_freebins;
  double max_ahcost;
  double max_tcost;
  int unplaced_prods;
  double cost;
  double min_cost;
  int priority_bin;
  int priority_prod;
  double max_cost;
  int oldbin;
  double oldcost;
  int moved;
  int worth;
  int r;
  int ok;
  int movedsome;
  double aft_org_cost;
  double aft_dst_cost;

  /* get fibonacci form and unallowed positions from user */
  printf("--------------------------------------------------------------------------------\n");
  printf("Fibonacci to Galois NLFSR transformation - v1.1 - march 23, 2009\n");
  printf("--------------------------------------------------------------------------------\n");
  printf("Enter the feedback function of a Fibonacci NLFSR followed by indexes\n");
  printf("of bits which should not have a feedback in the Galois configuration\n");
  printf("(if there are such) specified with commas and dashes. For example:\n\n");
  printf("f23=x0+x3+x5+x9+x15+x17+x23+x1x4+x3x7+x2x4x6 r=0-14,16-20,22\n\n");
  printf("specifies a 24-bit Fibonacci NLFSR and puts restrictions of bits\n");
  printf("0-14, 16-20 and 22 in the Galois configuration.\n\n");
  //printf("If you have no restriction on bits of the Galois configuration, your input will be:\n");
  //printf("f23=x0+x3+x5+x9+x15+x17+x23+x1x4+x3x7+x2x4x6\n\n");

  scanf("%[^\n]s",func);

  unallowed_pos_ptr=func;
  while(((*unallowed_pos_ptr)!='r')&&((*unallowed_pos_ptr)!='\0'))
    unallowed_pos_ptr++;
  if((*unallowed_pos_ptr)=='r')
    {
    *(unallowed_pos_ptr-1)='\0';
    unallowed_pos_ptr+=2;
    unallowed_pos=1;
    }
  else
    unallowed_pos=0;

  /* creation of the bins */  
  sscanf(func,"%c%d", &op, &nbins);
  bins=(bin*)malloc((nbins+1)*sizeof(bin));
  for(i=0;i<=nbins;i++)
    {
    bins[i].nprods=1;
    bins[i].allowed=1;
    }
   bins[nbins].nprods=0;

  func_start=func;

  /* advancing func_ptr until it reaches the beginning of the expression */
  while((*func_start)!='x')
    func_start++;

  /* calculation of the number of products */
  func_ptr=func_start;
  nprods=1;
  while((*func_ptr)!='\0')
    {
    if((*func_ptr)=='+')
      nprods++;
    func_ptr++;
    }

  /* creation of the products structure */
  products=(prod*)malloc(nprods*sizeof(prod));

  /* calculate the number of terms in all products */
  func_ptr=func_start;
  i=0;
  products[i].nterms=0;
  while((*func_ptr)!='\0')
    {
    if((*func_ptr)=='+')
      {
      i++;
      products[i].nterms=0;
      }
    if((*func_ptr)=='x')
      products[i].nterms++;
    func_ptr++;
    }

  /* fill the data structure with terms */
  func_ptr=func_start;
  i=0;
  j=0;
  products[i].terms=(int*)malloc((products[0].nterms)*sizeof(int));
  while((*func_ptr)!='\0')
    {
    if((*func_ptr)=='+')
      {
      i++;
      products[i].terms=(int*)malloc((products[i].nterms)*sizeof(int));
      j=0;
      }
    if((*func_ptr)=='x')
      {
      sscanf(func_ptr+1, "%d", &(products[i].terms[j]) );
      j++;
      }
    func_ptr++;
    }

  if(unallowed_pos)
    {
    while((*unallowed_pos_ptr)!='\0')
      {
      sscanf(unallowed_pos_ptr, "%d", &firstn);
      while(((*unallowed_pos_ptr)!=',')&&((*unallowed_pos_ptr)!='-')&&((*unallowed_pos_ptr)!='\0'))
        unallowed_pos_ptr++;
      bins[firstn].allowed=0;
      if((*unallowed_pos_ptr)=='-')
        {
        sscanf((unallowed_pos_ptr+1),"%d",&secondn);
        while(((*unallowed_pos_ptr)!=',')&&((*unallowed_pos_ptr)!='-')&&((*unallowed_pos_ptr)!='\0'))
          unallowed_pos_ptr++;
        for(i=(firstn+1);i<=secondn;i++)
          bins[i].allowed=0;
        }
      unallowed_pos_ptr++;
      }
    }
    
  /* calculate tau */
  tau=0;
  for(i=0;i<nprods;i++)
    {
    if(products[i].nterms>1)
      {
      min=products[i].terms[0];
      max=products[i].terms[0];
      for(j=1;j<products[i].nterms;j++)
        {
        if(products[i].terms[j]<min)
          min=products[i].terms[j];
        if(products[i].terms[j]>max)
          max=products[i].terms[j];
        }
      if(tau<(max-min))
        tau=(max-min);
      }
    }

  for(i=0;i<nprods;i++)
    {
    products[i].cost=ceil(log(products[i].nterms)/log(2));
    products[i].bin=-1;
    min=products[i].terms[0];
    for(j=0;j<products[i].nterms;j++)
      if(min>products[i].terms[j])
        min=products[i].terms[j];
    if((nbins-min)<tau)
      products[i].min_bin=tau;
    else
      products[i].min_bin=(nbins-min);
    }

  for(i=0;i<nprods;i++)
    {
    products[i].freebins=0;
    for(j=nbins;j>=products[i].min_bin;j--)
      if(bins[j].allowed)
        products[i].freebins++;
    }

  //if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
  //if(VERBOSE) printf("Found %d products, tau is %d\n",nprods, tau);

  /* ------------------------------------ */
  /*    Deterministic Initial placement   */
  /* ------------------------------------ */

if(PLACEMENT)
{

  unplaced_prods=nprods;

  //if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
  //if(VERBOSE) printf("Placing all products with a single allowed position\n");
  for(i=0;i<nprods;i++)
    if(products[i].freebins==1)
      {
      products[i].bin=nbins;
      bins[nbins].nprods++;
      unplaced_prods--;
     // if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
      //if(VERBOSE) printf("Product %d has been placed in f%d\n\n",i, products[i].bin);
      //if(VERBOSE) print_galois(products, bins, nprods, nbins);
      }

  //if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
  //if(VERBOSE) printf("Starting the placement algorithm\n");

  for(;unplaced_prods>0;unplaced_prods--)
    {

    /* calculate average hypothetical costs, worst average hypotetical cost and worst free bins*/
    max_ahcost=-1;
    max_freebins=nbins;
    for(i=0;i<nprods;i++)
      if(products[i].bin==-1)
        {
        products[i].ahcost=0;
        for(j=nbins;j>=products[i].min_bin;j--)
          if(bins[j].allowed)
            {
            products[i].bin=j;
            bins[j].nprods++;
            products[i].ahcost+=calculate_cost(nprods,nbins,products,bins,j);
            bins[j].nprods--;
            }
        products[i].ahcost=(products[i].ahcost/(products[i].freebins));
        if(products[i].ahcost>max_ahcost)
          max_ahcost=products[i].ahcost;
        if(products[i].freebins<max_freebins)
          max_freebins=products[i].freebins;
        products[i].bin=-1;
        }

    /* determine the priority product based on its average hypotetical cost and the number of free bins */
    max_tcost=-1;
    for(i=0;i<nprods;i++)
      if( (products[i].bin==-1) && ((products[i].ahcost/max_ahcost)*AHCOST_WEIGHT + (max_freebins/products[i].freebins)*FREEBINS_WEIGHT > max_tcost) )
        {
        max_tcost=(products[i].ahcost/max_ahcost)*AHCOST_WEIGHT + (max_freebins/products[i].freebins)*FREEBINS_WEIGHT;
        priority_prod=i;
        }

    /* place the priority product in the best bin */
    for(i=nbins;i>=products[priority_prod].min_bin;i--)
      if(bins[i].allowed)
        {
        oldbin=products[priority_prod].bin;
        products[priority_prod].bin=i;
        bins[i].nprods++;
        cost=calculate_cost(nprods,nbins,products,bins,i);
        bins[i].nprods--;
        products[priority_prod].bin=oldbin;
        if(i==nbins)
          {
          min_cost=cost;
          products[priority_prod].bin=i;
          }
        if(cost<=min_cost)
          {
          min_cost=cost;
          products[priority_prod].bin=i;
          }
        }

    (bins[products[priority_prod].bin].nprods)++;

    //if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
    //if(VERBOSE) printf("Product %d has been placed in f%d\n\n",priority_prod, products[priority_prod].bin);
    //if(VERBOSE) print_galois(products, bins, nprods, nbins);
    }

}

  /* ------------------------------------ */
  /*       Random Initial placement       */
  /* ------------------------------------ */

if(RANDOMPLACEMENT)
{

  //if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
  //if(VERBOSE) printf("Starting Random placement                                                       \n");

  srand(time(NULL));
    
  for(i=0;(i<nprods);i++)
    {
    ok=0;
    while(!ok)
      {
      r=rand()%nbins+1;
      if( (bins[r].allowed) && (r>=products[i].min_bin) )
        ok=1;
      }
    products[i].bin=r;
    bins[r].nprods++;

    //if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
    //if(VERBOSE) printf("Product %d has been placed in f%d\n\n",i, products[i].bin);
    //if(VERBOSE) print_galois(products, bins, nprods, nbins);
    }
}

  /* ------------------------------------ */
  /*     Post-placement optimization      */
  /* ------------------------------------ */

if(INTPOSTPLACEMENT)
{

  //if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
  //if(VERBOSE) printf("Starting postplacement optimization                                             \n");

  movedsome=1;
  while(movedsome)
    {
    movedsome=0;

    /* calculate maximum bin cost */
    max_cost=-1;
    for(i=0;i<=nbins;i++)
      if((bins[i].allowed) && (calculate_cost(nprods,nbins,products,bins,i)>max_cost) )
          max_cost=calculate_cost(nprods,nbins,products,bins,i);

    for(priority_bin=nbins;priority_bin>0;priority_bin--)
      if(bins[priority_bin].allowed && (calculate_cost(nprods,nbins,products,bins,priority_bin)==max_cost))
        {
        moved=0;

        /* look for a critical product that would improve the critical path in the worst bins if moved */
        for(i=0;(i<=nprods)&&(!moved);i++)
          if(products[i].bin==priority_bin)
            {
            oldbin=products[i].bin;
            products[i].bin=-1;
            bins[oldbin].nprods--;
            worth=(calculate_cost(nprods,nbins,products,bins,priority_bin)<max_cost);
            products[i].bin=oldbin;
            bins[oldbin].nprods++;
            if(worth)
              {

              /* Try to swap the product with another one */
              for(j=0;(j<nprods)&&(!moved);j++)
                if( (products[i].bin!=products[j].bin) && (products[i].bin>=products[j].min_bin) && (products[j].bin>=products[i].min_bin))
                  {
                  products[i].bin=products[j].bin;
                  products[j].bin=oldbin;
                  aft_dst_cost=calculate_cost(nprods,nbins,products,bins,products[i].bin);
                  aft_org_cost=calculate_cost(nprods,nbins,products,bins,oldbin);
                  if((aft_dst_cost<max_cost)&&(aft_org_cost<max_cost))
                    {
                    moved=1;
                    movedsome=1;
                    if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
                    if(VERBOSE) printf("Product %d in f%d has been swapped with product %d in f%d\n\n",i,products[j].bin,j,products[i].bin);
                    if(VERBOSE) print_galois(products, bins, nprods, nbins);
                    }
                  else
                    {
                    products[j].bin=products[i].bin;
                    products[i].bin=oldbin;
                    }
                  }

              /* If swapping failed, try to move the product to another bin */
              for(j=nbins;(j>0)&&(!moved);j--)
                if((j!=oldbin) && (bins[j].allowed) && (j>=products[i].min_bin) && (calculate_cost(nprods,nbins,products,bins,j)<max_cost))
                  {
                  oldcost=calculate_cost(nprods,nbins,products,bins,j);
                  bins[oldbin].nprods--;
                  bins[j].nprods++;
                  products[i].bin=j;
                  if(calculate_cost(nprods,nbins,products,bins,j)<max_cost)
                    {
                    moved=1;
                    movedsome=1;
                    if(VERBOSE) printf("--------------------------------------------------------------------------------\n");
                    if(VERBOSE) printf("Product %d has been moved from f%d to f%d\n\n",i,oldbin,j);
                    if(VERBOSE) print_galois(products, bins, nprods, nbins);
                    }
                  else
                    {
                    products[i].bin=oldbin;
                    bins[j].nprods--;
                    bins[oldbin].nprods++;
                    }
                  }
              }
            }
        }
    }
}

  //printf("--------------------------------------------------------------------------------\n");
  printf("\nGalois configuration with the shortest critical path:\n");  
  print_galois(products, bins, nprods, nbins);

  max_cost=-1;
  for(i=nbins;i>=0;i--)
    if(calculate_cost(nprods,nbins,products,bins,i)>max_cost)
      max_cost=calculate_cost(nprods,nbins,products,bins,i);

  /* calculating the cost in the fibonacci form */
  for(i=0;i<nprods;i++)
    products[i].bin=nbins;
  bins[nbins].nprods=nprods;

  //printf("--------------------------------------------------------------------------------\n");
  printf("Estimated throughput improvement for TSMC 90 nm technology is %.2f times\n",(calculate_cost(nprods,nbins,products,bins,nbins)*33.51 + 74.15) / (max_cost*33.51 + 74.15));

if(TECHNOLOGY==1)
{
  //printf("--------------------------------------------------------------------------------\n");
  //printf("The estimated critical path for TSMC 90 nm technology is %.0f ps (%.2f GHz)\n\n",max_cost*33.51 + 74.15, 1000/(max_cost*33.51+74.15));
}

  return 1;
  }