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

/***************************************************
 * August 2000: added support for vcg. Use command:
  xvcg -psoutput cc<dim>.ps -landscape cc<dim>.vcg

   Printing the gateways table on one page for dim=6
  a2ps  -o 6.ps -r --columns=1 -f 6 6.table
****************************************************/

/********************************************************
 * This program is for hypercube now.
 * It could be easily adjusted for 3D torus, mesh, ring
 * The back-routing works for any network topology:
 *    one must provide the gateway table for
 *    i->j, where i < j. For i > j the Backtrack code
 *    below will do the job.


**********************************************************/
#define IPOFFSET  0    /* offset for ip numbers */
#define OFFSET    1    /* for now it works only for eth0 -> outside;
                           should be used in combination with MAXIF, for general cases */
#define MAXIF     6    /* How many interfaces we have in a box */

FILE *out, *vcg ;

int main(int argc, char *argv[])

{

  int k, me, dim, i, j, z, mnd, knd, dnd, dif, gw, gwx, gwy, o, pgw ;
  char t[10];
  void start_int(), add_int(), end_int() ;

  if (argc<2){ printf("Specify parameter for hypercube dimension!\n");exit(-1); }

  dim = atoi(argv[1]) ;

  sprintf(t,"cc%d.vcg",dim);
  vcg = fopen(t,"w");
  fprintf(vcg,"graph: {\ndisplay_edge_labels: yes\n");

  printf("    ");   /* print header: */
  for ( i = 1; i <= pow2(dim); i++ ) printf("%3d",i+IPOFFSET) ; printf("\n    ");
  for ( i = 1; i <= 3*pow2(dim); i++) printf("-"); ; printf("\n");

  for ( i = 1; i <= pow2(dim); i++ ){
    printf("%3d:",i+IPOFFSET); start_int(i,dim) ;
    for (j = 1; j <= pow2(dim); j++ ){
      gw = gates(i,j,dim) ; /* if > 0 => i<j */
      if (gw == -2){  /* Backtrack this one: */
	gwx = j ; o = i ;
	for (k=0;k<dim;k++){
          if ( o > gwx ) gwy = gates(gwx,o,dim) ;
          else gwy = gates(o,gwx,dim);
          if (gwy == -1){ gw = gwx;  goto finish ;}
          if ((gwy ==  0) || (gwy == -2)){
            printf("This is going nowhere...\n");exit(-5);
          }
          gwx = gwy ;
        }
      }
    finish:
      pgw = gw ; if (gw > 0) pgw = gw + IPOFFSET ;
      printf("%3d",pgw); add_int(i,j,gw,dim);
    }
    printf("\n"); end_int() ;
  }
  fprintf(vcg,"}\n"); fclose(vcg);
}

int pow2(int x)
{
  if (x >= 0) return 1 << x ; else return 0 ;
}

int connected(int me, int k, int dim)
{
  int j, c, u, t, s ;

  /* Check if me and k are connected: returns 1, else 0 */

  c = 0 ;
  for (j=0;j<dim;j++){
    t = (me-1)&(1<<j) ; s=1 ; if (t>0)s=-1 ;
    u = me + s*pow2(j);
    if ( k == u ) c = 1 ;
  }
  return c ;
}

int subspace(int i, int j, int dim)

/*
*********************************************************************************
*
*   Looks for all the subspaces of subdimension sd for a given dimension dim. 
*
*   We are making only upper right part of the connection matrix:
*   i < j always!
*
*   The main rule to define gateways in the hypercube of dimension dim is:
*   Find the highest possible subdimension sd in which
*   i and j are in different subspaces. Then the gateway is:
*   gw(i -> j) = i + pow2(sd)
*
*   sd runs from dim-1 to 1. There are no GWs in 1-D cube.
*
*********************************************************************************
*/

{
  int sd, k, flag, submin, submax;

  sd = dim ;

  while( sd-- > 0 ){                         /*  Subdimensions loop */
    for (k = 0; k < pow2(dim - sd);k++){     /*  Subspaces loop */
      submin = k*pow2(sd)+1 ;                /*  Define limits for this subspace */
      submax = (k+1)*pow2(sd) ;
      /* if i and j are not in the same subspace at this subdimension then return */
      if ((i >= submin) && (i <= submax) && (j > submax)) return sd ;
    }
  }
  printf("IMPOSSIBLE: Both (%d,%d) are in the same subspace for all subdimensions!\n",i,j);
  exit(-3);
}

int gates(int i, int j, int dim)
     /*
      * This one is only for forward gateways (i<j)
      *   gates definitions:
      *   -2: Not defined;
      *   -1: directly connected;
      *    0: self host;
      *   >0: gateway between hosts i -> j
      */
{
  int gw;

  gw = -2 ;
  if ( i == j ) gw = 0 ;
  else if (connected(i,j,dim) == 1) gw = -1 ;
  else if ( i < j ) gw = i + pow2(subspace(i,j,dim)) ;

  return gw ;
}

void start_int(int i, int dim)
{
  char fname[100]; int k;

  /* Opens the interfaces file for node i.
   * Also defines all interfaces for node i (ifconfig) */

  fprintf(vcg,"node: { title: \"%d\" }\n",i+IPOFFSET);

  sprintf(fname,"interfaces-v%d",i+IPOFFSET);
  out = fopen(fname,"w");
  fprintf(out,"iface lo inet loopback\n");
  for(k=0;k<MAXIF;k++){      /* k is for interface number */
    if (k == (OFFSET - 1)){
      fprintf(out,"iface eth%d inet static\n",k);
      fprintf(out,"   address 10.40.%d.%d\n",k,i+IPOFFSET);
      fprintf(out,"   network 10.40.%d.0\n",k);
      fprintf(out,"   netmask 255.255.255.0\n");
      fprintf(out,"   broadcast 10.40.%d.255\n",k);
      fprintf(out,"   gateway 10.40.0.254\n");
      fprintf(out,"\n");
    }
    else {
      fprintf(out,"iface eth%d inet static\n",k);
      fprintf(out,"   address 10.40.%d.%d\n",k,i+IPOFFSET);
      fprintf(out,"   network 10.40.%d.0\n",k);
      fprintf(out,"   netmask 255.255.255.0\n");
      fprintf(out,"   broadcast 10.40.%d.255\n",k);
      fprintf(out,"\n");
    }
  }
}

void add_int(int i, int j, int gw, int dim)
{
  int k, l ;

  /* Writes routing table element (route command) from node i to node j */

  if (gw == 0) return ;

  if (gw == -1){ /* This is for directly connected nodes */
    if(i<j) l = subspace(i,j,dim) + OFFSET;  /* l is the dimension by which node */
    if(i>j) l = subspace(j,i,dim) + OFFSET;  /* j is reached in a shortest path */
    if(i<j)
      fprintf(vcg,"edge: { sourcename: \"%d\" targetname: \"%d\" label: \"eth%d\"}\n",i+IPOFFSET,j+IPOFFSET,l);

    for(k=OFFSET; k<dim+OFFSET; k++)
      fprintf(out,"   up route add -host 10.40.%d.%d eth%d\n",k,j+IPOFFSET,l);
    return ;
  }

  /* l is the dimension by which node j is reached in a shortest path */
  if(i<gw) l = subspace(i,gw,dim) + OFFSET;
  if(i>gw) l = subspace(gw,i,dim) + OFFSET;

  for(k=OFFSET; k<dim+OFFSET; k++){
    fprintf(out,"   up route add -host 10.40.%d.%d gw 10.40.%d.%d\n",
            k,j+IPOFFSET,l,gw+IPOFFSET);
  }
}

void end_int()
{
  fclose(out);
}