/* Bgp-atoms.c Copyright (c) Geoff Huston, 2003, gih@telstra.net */
/*
 * Version 1.0
 *  7 April 2003
 *
 *
 * Make:
 *   gcc -o bgp-atoms bgp-atoms.c
 *
 * Invoke
 *   bgp-atoms <route-views-show-ip-bgp-dump> <report-directory>
 *
 * Outputs:
 *   Entries:   <number of FIB table entries>
 *   Paths:     <number of unique paths>
 *   Fib Paths: <number of unique paths used in the FIB>
 *   Atoms:     <number of routing atoms>
 *
 *   <report-directory>/as.txt
 *      per AS report of transit, orrgin, peer and connectivity degree
 *   <report-directory>/asdeg.txt
 *      per degree reports of number of ASes with each degree
 *   <report-directory>/aslk.txt
 *      report of AS link pairings
 *   <report-directory>/asp.txt
 *      report of AS paths
 *   <report-directory>/atoms.txt
 *      report of atoms
 */

#include <stdio.h>
#include <string.h>
#include <ctype.h>


    /* the default  peer inclusion threshold - a peer is included into consideration
     * if it announces at least THRESHOLD % of the total number of prefixes
     * in the bgp file
     */

#define THRESHOLD  80
#define NPEERS     100
#define NCACHE     150

int debug          = 0 ;
int thresh         = 0 ;
int peer_count     = 0 ;
int new_atom       = 0 ;
int atom_count     = 0 ;
int fib_path_count = 0 ;
int total_path_count = 0 ;
int entry_count    = 0 ;
int cutoff         = 0 ;
int ecount         = 0 ;
int icount         = 0 ;
int usefract       = 0 ;
char *exclude[100] ;
char *include[100] ;
float fraction ;
char *out_file_dir  = "/tmp";

    /* peers is a structure for each peer
     * asn   - the as number of the peer
     * nh    - the nexthop address of the peer
     * count - the number of entries advbertised by this peer
     * nxt   - single linked list
     *
     * peer_lists - head of single linked list
     * peer_list  - array of pointers to peers where count > threshold
     */

struct peers {
  int asn ;
  char nh[16];
  int count ;
  int bcount ;
  int pathcount;
  struct aspaths **patharray;
  int patharray_size;
  struct aspaths *paths;
  struct peers *nxt;
  } *peer_lists, *peer_list[NPEERS] ;


struct aspaths {
  char *asp;
  unsigned int index;
  struct aspaths *l;
  struct aspaths *r;
  } *asph = 0;

    /* atom is a structure for each routing atom
     * pathindex - an array of path numbers, ordered by neighbour as/nexthop 
     *             (the index is the peer_list index)
     * addrcount - the number of entries associated with this atom
     * adp       - pointer to list of addresses that share this atom
     * nxt       - single linked list
     *
     * atom_list - head of single linked list
     */

struct aspairs {
  unsigned int aspair ;
  int counter ;
  struct aspairs *l, *r;
} *pairsh = 0 ;

struct atom {
  int *pathindex;
  int addrcount ;
  struct addr *adp;
  struct atom *nxt ;
  } *atom_list = 0;
  

    /* addr is a structure for each address prefix in an atom
     * address - the address string
     * nxt     - single linked list
     */

struct addr {
  char *address;
  struct addr *nxt;
  };


    /* addressatom is a structure for each address
     * address     - address prefix
     * aspathindex - array of path numbers, ordered by neighbour as/nexthop
     *               (the index is the peer_list index)
     *
     * current_address - current address / path set being assembled
     */

      
struct addressatom {
  char *address;
  int *aspathindex;
  } current_address = {0,0};



struct fib_path {
  char *fib_pth;
  struct fib_path *l,*r;
  } *fib_paths = 0 ;

char *pathcache[NCACHE] ;
char *nhpcache[NCACHE] ;
int pathcachenumber[NCACHE];
int pathcacheindex;
int cache_size;
int cache_index  = 0 ;
char *last_alloc = 0;

struct as {
  int as ;
  int peer ;
  int transit ;
  int origin ;
  int indegree ;
  int outdegree ;
  int degree ;
  struct as *l, *r ;
} *ash = 0 ;


int total_as_count = 0 ;
int total_stub_count = 0 ;

struct degree {
  int degree ;
  int count ;
  struct degree *n ;
} *ind = 0, *outd = 0, *totd = 0, *stubd = 0 ;


  
void
add_fib_path(aspath, fib_path_ptr)
  char *aspath ;
  struct fib_path *fib_path_ptr ;
  {
  struct fib_path *tmp ;
  int i;
  if (!fib_path_ptr) {
    tmp = fib_paths = (struct fib_path *) malloc(sizeof *tmp);
    }
  else {
    i = strcmp(aspath,fib_path_ptr->fib_pth);
    if (!i) return ;
    if (i < 0) {
      if (fib_path_ptr->l) return(add_fib_path(aspath,fib_path_ptr->l));
      tmp = fib_path_ptr->l = (struct fib_path *) malloc(sizeof *tmp);
      }
    else {
      if (fib_path_ptr->r) return(add_fib_path(aspath,fib_path_ptr->r));
      tmp = fib_path_ptr->r = (struct fib_path *) malloc(sizeof *tmp);
      }
    }
  tmp->fib_pth = (char *) malloc(strlen(aspath) + 1) ;
  strcpy(tmp->fib_pth,aspath);
  tmp-> r = tmp->l = 0 ;
  ++fib_path_count;
  }  



    /* new_prefix
     * set up a new instance of an address atom to associate with a path set
     * reset new_atom to indicate that this may not be a new atom
     */

new_prefix(lastaddr) 
     char *lastaddr;
  {
  int i;

  if (!current_address.aspathindex) {
    current_address.aspathindex = (int *) malloc((sizeof *current_address.aspathindex) * peer_count);
    }
  if (!current_address.address) {
    current_address.address = (char *) malloc(256);
    }
  strcpy(current_address.address,lastaddr);
  for (i = 0 ; i < peer_count; ++i)
    current_address.aspathindex[i] = 0;
  new_atom = 0;
  }


    /* normalize
     * convert an as path string by removing AS SET constructions and removing
     * duplicate AS numbers
     * no as path syntax checking is performed
     */

char *
normalize(aspath,nhp)
     char *aspath;
     char *nhp;
  {
  int i;
  char *cp = aspath ;
  int as;
  int lastas;
  int aspathlist[50];
  int aspathindex = 0 ;


    /* check if this path string has already been processed and if so 
     * return the normalized string
     */

  pathcacheindex = 100;
  if (cache_size) {
    for (i = 0 ; i < cache_size; ++i)
      if ((!strcmp(aspath,pathcache[i])) && (!strcmp(nhp,nhpcache[i]))) {
        pathcacheindex = i ;
        return(pathcache[i]);
        }
    }

  while (*cp) {
    while (*cp && (!isdigit(*cp))) ++cp;
    if (*cp) {
      as = atoi(cp);
      if (as != lastas) {
        lastas = as;
        aspathlist[aspathindex++] = as;
        }
      }
    while (*cp && (isdigit(*cp))) ++cp;
    }
  if (!aspathindex) return("");
  if (last_alloc) free(last_alloc);
  last_alloc = cp = (char *) malloc((aspathindex + 1) * 6);
  for (i = 0 ; i < aspathindex; ++i) {
    sprintf(cp,"%d ",aspathlist[i]);
    cp += strlen(cp);
    }
  *--cp = '\0';
  cp = last_alloc;
  if (cache_size < NCACHE) ++cache_size ;
  if (pathcache[cache_index]) {
    free(pathcache[cache_index]);
    free(nhpcache[cache_index]);
    }
  pathcache[cache_index] = (char *) malloc(strlen(cp) + 1);
  strcpy(pathcache[cache_index],cp);
  nhpcache[cache_index] = (char *) malloc(strlen(nhp) + 1);
  strcpy(nhpcache[cache_index],nhp);
  pathcachenumber[cache_index] = 0;
  pathcacheindex = cache_index;
  cache_index = (cache_index + 1) % NCACHE;
  return(cp);
  }


int
add_to_tree(pthptr,asp,peer)
     struct aspaths *pthptr;
     char *asp;
     struct peers *peer;
  {
  int i;
  int ss;
  struct aspaths **sav;

  i = strcmp(pthptr->asp,asp);
  if (!i) {
    return(pthptr->index);
    }
  if (i < 0) {
    if (pthptr->l) return(add_to_tree(pthptr->l,asp,peer));
    ++total_path_count ;
    pthptr->l = (struct aspaths *) malloc(sizeof *pthptr);
    pthptr->l->l = pthptr->l->r  = 0;
    pthptr->l->asp = (char *) malloc(strlen(asp) + 1);
    strcpy(pthptr->l->asp,asp);
    pthptr->l->index = ++peer->pathcount;
    if (peer->pathcount >= peer->patharray_size) {
      sav = peer->patharray;
      ss = peer->patharray_size;
      peer->patharray_size += 1000;
      peer->patharray = (struct aspaths **) malloc((sizeof peer->patharray) * peer->patharray_size);
      for (i = 0 ; i < ss ; ++i) {
        peer->patharray[i] = sav[i];
        }
      free(sav);
      }
    peer->patharray[peer->pathcount] = pthptr->l;
    new_atom = 1;
    pathcachenumber[pathcacheindex] = peer->pathcount;
    return(peer->pathcount);
    }
  if (pthptr->r) return(add_to_tree(pthptr->r,asp,peer));
  ++total_path_count ;
  pthptr->r = (struct aspaths *) malloc(sizeof *pthptr);
  pthptr->r->l = pthptr->r->r = 0;
  pthptr->r->asp = (char *) malloc(strlen(asp) + 1);
  strcpy(pthptr->r->asp,asp);
  pthptr->r->index = ++peer->pathcount;
  if (peer->pathcount >= peer->patharray_size) {
    sav = peer->patharray;
    ss = peer->patharray_size;
    peer->patharray_size += 1000;
    peer->patharray = (struct aspaths **) malloc((sizeof peer->patharray) * peer->patharray_size);
    for (i = 0 ; i < ss ; ++i) {
      peer->patharray[i] = sav[i];
      }
    free(sav);
    }
  peer->patharray[peer->pathcount] = pthptr->r;
  new_atom = 1;
  pathcachenumber[pathcacheindex] = peer->pathcount;
  return(peer->pathcount);
  }

struct as *
getas(asn,p)
     int asn ;
     struct as **p ;
{
  struct as *tmp = *p;
  
  if (!tmp) {
    tmp = (struct as *) malloc(sizeof *tmp) ;
    tmp->as = asn ;
    tmp->peer = tmp->transit = tmp->origin = tmp->indegree = tmp->outdegree = tmp->degree = 0;
    tmp->l = tmp->r = 0 ;
    *p = tmp ;
    return(tmp) ;
    }
  if (asn == tmp->as) return(tmp) ;
  if (asn < tmp->as) return(getas(asn,&(tmp->l))) ;
  return(getas(asn,&(tmp->r))) ;
}

print_paths(p,f)
     struct aspaths *p ;
     FILE *f;
{
  if (!p) return ;
  if (p->l) print_paths(p->l,f) ;
  fprintf(f,"%d\t%s\n",p->index,p->asp) ;
  if (p->r) print_paths(p->r,f) ;
}

print_degrees(f)
     FILE *f;
{
  int degree ;
  struct degree *t ;
  int tc ;

  while (ind || outd || totd || stubd) {
    if (ind) degree = ind->degree ;
    else if (outd) degree = outd->degree ;
    else if (totd) degree = totd->degree ;
    else if (stubd) degree = stubd->degree ;
    if (outd && (outd->degree < degree)) degree = outd->degree ;
    if (totd && (totd->degree < degree)) degree = totd->degree ;
    if (stubd && (stubd->degree < degree)) degree = totd->degree ;

    fprintf(f,"%d\t",degree) ;

    fprintf(f,"IN\t");
    if (ind) {
      if (ind->degree == degree)
        fprintf(f,"%d\t%6.4f\t",ind->count, ((ind->count / (float) total_as_count) * 100.0));
      else
        fprintf(f,"0\t0.0\t") ;
      t = ind ;
      tc = 0 ;
      while (t) {
        tc += t->count ;
        t = t->n ;
        }
      fprintf(f,"%d\t%6.4f\t",tc,((tc / (float) total_as_count) * 100.0)) ;
      if (ind->degree == degree) ind = ind->n ;
      }
    else 
      fprintf(f,"0\t0.0\t0\t0.0\t") ;
      
    fprintf(f,"OUT\t");
    if (outd) {
      if (outd->degree == degree)
        fprintf(f,"%d\t%6.4f\t",outd->count, ((outd->count / (float) total_as_count) * 100.0));
      else
        fprintf(f,"0\t0.0\t") ;
      t = outd ;
      tc = 0 ;
      while (t) {
        tc += t->count ;
        t = t->n ;
        }
      fprintf(f,"%d\t%6.4f\t",tc,((tc / (float) total_as_count) * 100.0)) ;
      if (outd->degree == degree) outd = outd->n ;
      }
    else 
      fprintf(f,"0\t0.0\t0\t0.0\t") ;
      
    fprintf(f,"TOT\t");
    if (totd) {
      if (totd->degree == degree)
        fprintf(f,"%d\t%6.4f\t",totd->count, ((totd->count / (float) total_as_count) * 100.0));
      else
        fprintf(f,"0\t0.0\t") ;
      t = totd ;
      tc = 0 ;
      while (t) {
        tc += t->count ;
        t = t->n ;
        }
      fprintf(f,"%d\t%6.4f\t",tc,((tc / (float) total_as_count) * 100.0)) ;
      if (totd->degree == degree) totd = totd->n ;
      }
    else 
      fprintf(f,"0\t0.0\t0\t0.0\t") ;

    fprintf(f,"STUB\t");
    if (stubd) {
      if (stubd->degree == degree)
        fprintf(f,"%d\t%6.4f\t",stubd->count, ((stubd->count / (float) total_stub_count) * 100.0));
      else
        fprintf(f,"0\t0.0\t") ;
      t = stubd ;
      tc = 0 ;
      while (t) {
        tc += t->count ;
        t = t->n ;
        }
      fprintf(f,"%d\t%6.4f\n",tc,((tc / (float) total_stub_count) * 100.0)) ;
      if (stubd->degree == degree) stubd = stubd->n ;
      }
    else 
      fprintf(f,"0\t0.0\t0\t0.0\n") ;
    }
}

void
add_one_degree(d,p)
  int d;
  struct degree **p;
{
  struct degree *tmp = *p;

  if (!tmp) {
    tmp = (struct degree *) malloc(sizeof *tmp);
    tmp->degree = d;
    tmp->count = 1 ;
    tmp->n = 0 ;
    *p = tmp ;
    return ;
    }
  if (d < tmp->degree) {
    tmp = (struct degree *) malloc(sizeof *tmp);
    tmp->degree = d;
    tmp->count = 1 ;
    tmp->n = *p ;
    *p = tmp ;
    return ;
    }
  if (d == tmp->degree) {
    ++tmp->count ;
    return ;
    }
  add_one_degree(d,&tmp->n) ;
}

void
printas(p,f) 
     struct as *p ;
     FILE *f ;
{
  if (!p) return ;
  if (p->l) printas(p->l,f) ;
  fprintf(f,"%d %d %d %d %d %d %d %d\n",
	  p->as,(p->transit + p->origin),p->peer,p->transit,p->origin,
          p->degree,p->indegree,p->outdegree);

  ++total_as_count ;
  add_one_degree(p->indegree,&ind) ;
  add_one_degree(p->outdegree,&outd) ;
  add_one_degree(p->degree,&totd) ;
  if (!p->outdegree) {
    ++total_stub_count;
    add_one_degree(p->indegree,&stubd);
    }


  if (p->r) printas(p->r,f) ;
}


void
print_pairs(ptr,f)
     struct aspairs *ptr ;
     FILE *f;
{
  if (!ptr) return ;
  if (ptr->l) print_pairs(ptr->l,f) ;
  fprintf(f,"%u - %u : %d\n",((ptr->aspair) >> 16),((ptr->aspair) & 65535),ptr->counter) ;
  if (ptr->r) print_pairs(ptr->r,f) ;
}

void
add_pair(p,ptr) 
     unsigned int p ;
     struct aspairs **ptr ;
{
  struct aspairs *tmp = *ptr ;

  if (!tmp) {
    tmp = (struct aspairs *) malloc(sizeof *tmp) ;
    tmp->aspair = p ;
    tmp->counter = 1 ;
    tmp->l = tmp->r = 0 ;
    *ptr = tmp ;
    return ;
    }
  if (p < tmp->aspair) return(add_pair(p,&(tmp->l))) ;
  if (p > tmp->aspair) return(add_pair(p,&(tmp->r)));
  ++tmp->counter ;
}

analyze_ases(asp)
     char *asp ;
{
  struct aspaths *tmp = asph ;
  int i, l ;
  int fnd = 1 ;
  int asn[50] ;
  struct as *as_p, *pas_p ;
  char *cp ;


  if (!tmp)
    asph = tmp = (struct aspaths *) malloc(sizeof *tmp) ;
  else {
    while (fnd) {
      if ((i = strcmp(asp,tmp->asp)) < 0) {
        if (tmp->l) tmp = tmp->l ;
        else {
          tmp->l = (struct aspaths *) malloc(sizeof *tmp) ;
          tmp = tmp->l;
          fnd = 0 ;
	  }
        }
      else if (i > 0) {
        if (tmp->r) tmp = tmp->r ;
        else {
          tmp->r = (struct aspaths *) malloc(sizeof *tmp) ;
          tmp = tmp->r;
          fnd = 0 ;
	  }
        }
      else return(++tmp->index) ; 
      }
    }
  tmp->l = tmp->r = 0 ;
  tmp->index = 1 ;
  tmp->asp = strdup(asp) ;
  
  l = -1 ;
  cp = asp ;
  while (cp && isdigit(*cp)) {
    asn[++l] = atoi(cp) ;
    if (cp = strchr(cp,' '))
      while (isspace(*cp)) ++cp ;
    }
  pas_p = 0 ;
  for (i = 0 ; i <= l ; ++i) {
    as_p = getas(asn[i],&ash);
    if (!i && l) ++as_p->peer ;
    if (i == l) ++as_p->origin ;
    if (i && (i < l)) ++as_p->transit ;
    if (i) {
      ++as_p->indegree ;
      ++as_p->degree ;
      ++pas_p->outdegree ;
      ++pas_p->degree ;
      }
    if (i)
      add_pair(((asn[i-1] << 16) + asn[i]),&pairsh) ;
    pas_p = as_p ;
    }
}


  /*
   * locate_path
   * 
   * return the index number of the path
   * If the path is in the processing cache (last NCACHE entries) then used a cached answer
   * If the peer has no associated paths, then associate an initial path with the peer
   * else start up a search through the peer's path list to see if this path has already
   * been processed
   */

int 
locate_path(peer,asp)
     struct peers *peer;
     char *asp;
  {
  if (pathcachenumber[pathcacheindex]) {
    return(pathcachenumber[pathcacheindex]);
    }
  if (!peer->pathcount) {
    peer->paths = (struct aspaths *) malloc(sizeof *peer->paths);
    peer->paths->l = peer->paths->r = 0;
    peer->paths->asp = (char *) malloc(strlen(asp) + 1);
    strcpy(peer->paths->asp,asp);
    peer->paths->index = ++peer->pathcount;
    peer->patharray = (struct aspaths **) malloc((sizeof *peer->patharray) * 1000);
    peer->patharray_size = 1000;
    peer->patharray[peer->pathcount] = peer->paths;
    new_atom = 1;
    pathcachenumber[pathcacheindex] = peer->pathcount;
    return(peer->pathcount);
    }
  return(add_to_tree(peer->paths,asp,peer));  
  }


  /* 
   * add_path
   *
   * Add a new path to the address atom being assembled
   * First find if the peer is part of the qualifying peer set
   * If so then normalize the path (by eliminating prepending and
   * expanding AS sets) and then locate the index of this part in the
   * peer data structure
   */

void
add_path(asn,nhp,aspath)
     int asn;
     char *nhp;
     char *aspath;
  {
  int peer = 0;
  int found = 0 ;
  char *asp;
  int save_new_atom;

  while ((!found) && (peer < peer_count)) {
    found = ((peer_list[peer]->asn == asn) && (!strcmp(peer_list[peer]->nh,nhp)));
    if (!found) ++peer;
    }
  asp = normalize(aspath,nhp);
  analyze_ases(asp) ;
  if (peer >= peer_count) return;
  current_address.aspathindex[peer] = locate_path(peer_list[peer],asp);
  }
          


  /* 
   * add_to_atomset
   *
   * Once all the paths associated with an advertised address have been collated
   * it is then necessary to add this advertisement to the atom set.
   * 
   * If any of the per-peer paths are new, then the atom is new and no search is
   * necessary.
   *
   * If all the paths are not new then a search of the existing atom list, using
   * an atom comparison routine is required.
   */

void
add_to_atomset()
  {
  struct atom *tmp = atom_list;
  struct addr *adptr;
  int i;
  int match;

  if (new_atom) {
    tmp = (struct atom *) malloc(sizeof *tmp);
    tmp->pathindex = (int *) malloc((sizeof *tmp->pathindex) * peer_count);
    for (i = 0 ; i < peer_count; ++i)
      tmp->pathindex[i] = current_address.aspathindex[i];
    tmp->addrcount = 1;
    tmp->nxt = atom_list ;
    atom_list = tmp;
    tmp->adp = (struct addr *) malloc(sizeof *tmp->adp);
    tmp->adp->address = (char *) malloc(strlen(current_address.address) + 1) ;
    strcpy(tmp->adp->address,current_address.address);
    tmp->adp->nxt = 0;
    ++atom_count;
    return;
    }
  while (tmp) {
    match = 1 ;
    i = 0 ;
    while (match && (i < peer_count)) {
      if (tmp->pathindex[i] != current_address.aspathindex[i]) match = 0 ;
      ++i;
      }
    if (match) {
      ++tmp->addrcount;
      adptr = (struct addr *) malloc(sizeof *adptr);
      adptr->address = (char *) malloc(strlen(current_address.address) + 1) ;
      strcpy(adptr->address,current_address.address);
      adptr->nxt = tmp->adp;
      tmp->adp = adptr;
      return;
      }
    else tmp= tmp->nxt;
    }
  new_atom  = 1 ;
  add_to_atomset();  
  }



  /*
   * substr
   *
   * return TRUE is s1 is a substring of s2
   */

int 
substr(s1, s2)
  char *s1; char *s2;
  {
  int l = strlen(s1);

  while (s2 = strchr(s2, *s1)) {
    if (!strncmp(s1,s2,l)) return(1) ;
    if (!*(++s2)) return(0) ;
    }
  return(0) ;
  }



  /*
   * chop
   *
   * remove trailing aspath detritus from the aspath string
   */

void
chop(s)
  char *s ;
  {
  int i = strlen(s) - 1 ;

  while ((i >= 0)
          && (isspace(s[i]) ||
              (s[i] == '\n') ||
              (s[i] == '\r') ||
              (s[i] == 'i') ||
              (s[i] == 'e') ||
              (s[i] == '?'))) {
    s[i--] = '\0';
    }
  }




  /*
   * add_peer
   *
   * this is a pass 1 routine called for each advertisement entry
   * in the dump file.
   * A peer is defined as a couplet of a neighbour AS and a next hop IP address
   * This routing locates a peer entry with a matching AS and next hop address
   * and then increments its advertisement count.
   */

void
add_peer(as, nhp,psize)
  int  as;
  char *nhp;
  int psize;
{
  struct peers *tmp = peer_lists ;
  struct peers *lst = 0;

  if (debug > 1) 
    printf("  add_peer %d %s /%d\n",as,nhp,psize) ;

  while ((tmp) && (!((tmp->asn == as) && !strcmp(tmp->nh,nhp)))) {
    lst = tmp ;
    tmp = tmp->nxt ;
    }
  if (tmp) {
    ++tmp->count ;
    if (psize <= 24) ++tmp->bcount ;
    return ;
    }
  tmp = (struct peers *) malloc(sizeof *tmp) ;
  tmp->asn = as;
  strcpy(tmp->nh,nhp);
  tmp->count = 1;
  tmp->bcount = (psize <= 24) ? 1 : 0;
  tmp->pathcount = 0 ;
  tmp->paths = 0 ;
  tmp->nxt = 0 ;
  if (lst) lst->nxt = tmp ;
  else peer_lists = tmp ;
}

  /*
   * set_full_peers
   *
   * find the max number of advertisements from each peering session, and then select 
   * all peering sessions where the advertisement count is within THRESHOLD% of the
   * maximum value
   *
   * peer_count is the number of selected peering sessions
   * peer_list is an array of pointers to selected peer records
   */

void
set_full_peers()
  {
  struct peers *tmp = peer_lists ;
  int maxv = 0 ;  
  int bmaxv = 0 ;  
  int i ;
  int excl ;

  while (tmp) {
    excl = 0 ;
    for (i = 0 ; i < ecount; ++i) 
      if (!strcmp(tmp->nh,exclude[i])) {
        i = ecount ;
        tmp->count = tmp->bcount = 0 ;
        excl = 1 ;
	}
    if (!excl) {
      if (tmp->count > maxv) maxv = tmp->count ;
      if (tmp->bcount > bmaxv) bmaxv = tmp->bcount ;
      }
    tmp = tmp->nxt;
    }

  if (usefract)
    fraction = (bmaxv * fraction) ;
    
  if (icount + ecount + cutoff + usefract) {
    tmp = peer_lists ;
    while (tmp) {
      if (cutoff && (tmp->bcount >= cutoff)) 
        peer_list[peer_count++] = tmp ;
      else if (usefract && (tmp->bcount > fraction))
        peer_list[peer_count++] = tmp ;
      else if (icount && tmp->bcount) {
        for (i = 0 ; i < icount; ++i) 
          if (!strcmp(tmp->nh,include[i])) {
            i = icount ;
            peer_list[peer_count++] = tmp ;
	    }
        }
      tmp = tmp->nxt;
      }
    return ;
    }

  thresh = (maxv * THRESHOLD) / 100 ;
  tmp = peer_lists ;
  while (tmp) {
    if (tmp->count < thresh) tmp->count = 0 ;
    else {
      peer_list[peer_count++] = tmp ;
      }
    tmp = tmp->nxt;
    }
  }

void
print_atoms(f) 
     FILE *f;
{
  int i = 0 ;
  int p ;
  int index;
  struct atom *al = atom_list;
  struct peers *pl;
  struct aspaths *ap;
  struct addr *ad;

  while (al) {
    ++i;
    fprintf(f,"Atom %d\n",i) ;
    fprintf(f,"  %d Address prefixes\n",al->addrcount);

    fprintf(f,"  Address Prefixes in this atom:\n") ;
    ad = al->adp;
    while (ad) {
      fprintf(f,"    %s\n",ad->address);
      ad = ad->nxt;
      }
    fprintf(f,"  Path Spec:\n") ;
    for (p = 0 ; p < peer_count ; ++p) {
      fprintf(f,"    Peer %d: ",p);
      pl = peer_list[p];
      if (index = al->pathindex[p]) {
        if (ap = pl->patharray[index])
          fprintf(f,"%s %s\n",pl->nh,ap->asp);
        else
          fprintf(f,"%s %d - NO PATH PTR\n",pl->nh,pl->asn);
        }
      else {
        fprintf(f,"%s %d - NO PATH\n",pl->nh,pl->asn);
        }        
      }
    fprintf(f,"\n");
    al = al->nxt;
    }
  }


  /*
   * read_file
   *
   * routing to scan a cisco bgp dump file and call ancillary routines to process each
   * routing entry.
   * the file assumes that it is an exact log of a "show ip bgp" session and the parser
   * looks for a line starting "show" to trigger the first part of the parser, and then
   * looks for a cisco column header line to start address and path scanning
   * ("   Network   Next Hop    Metric  LocPrf Weight Path")
   */

int
read_file(in_file,pass)
     char *in_file;
     int pass;
  {
  FILE *fi ;
  int  parse_header = 0 ;
  int  rib_count    = 0 ;
  int  pathoffset ;
  int  as;
  int  csize ;
  int  lastsize = 8 ;
  char inl[256] ;
  char *aspath ;
  char *cp ;
  char *nhp ;
  char *addr ;
  char lastaddr[256] ;

  *lastaddr = '\0';
  if (!(fi = fopen(in_file,"r"))) return(0);
  while (fgets(inl,255,fi) && (parse_header < 2)) {
    if (debug > 1) printf("%s",inl) ;
    if (!rib_count) {
      if (!strncmp(inl,"show",4)) parse_header = 1 ;
      }

    if (parse_header) {
      if (!substr("Prf",inl)) continue ;
      parse_header = 0 ;
      continue ;
      }

    if (strchr(inl,'#')) {
      parse_header= 2 ;
      continue ;
      }

    if (debug > 1) printf("  Rib +1\n") ;
    ++rib_count ;

    pathoffset = 0 ;
    while (!isspace(inl[19 + pathoffset])) ++pathoffset ;
    aspath = &inl[61 + pathoffset] ;
    chop(aspath) ;

    nhp = &inl[20 + pathoffset] ;
    if (cp = strchr(nhp,' ')) *cp = '\0';

    if (cp = strchr(aspath,' ')) {
      *cp = '\0';
      as = atoi(aspath);
      *cp = ' ';
      addr = &inl[3] ;
      if (cp = strchr(addr,' ')) *cp =  '\0';
      chop(addr);
      if (!*addr) 
        csize = lastsize;
      else if (cp = strchr(addr,'/'))
        csize = atoi(++cp);
      else {
        csize = atoi(addr) ;
        if (csize < 128) csize = 8 ;
        else if (csize < 192) csize = 16;
        else csize = 24;
        }
      lastsize = csize;
      if (pass == 1) 
        add_peer(as,nhp,csize);
      if (pass == 2) {
        if (!*addr)
          add_path(as,nhp,aspath) ;
        else {
          if (current_address.address) add_to_atomset() ;
          strcpy(lastaddr,addr) ;
          new_prefix(lastaddr) ;
          add_path(as,nhp,aspath) ;
	  }
        if (inl[1] == '>') {
          ++entry_count;
          add_fib_path(aspath, fib_paths);
	  }
        }
      }
    }
  fclose(fi);
  return(rib_count);
  }


  /*
   * report_summ
   *
   * report on totals in terms of number of entries, number of unique paths
   * used in the FIB (selected paths) and the number of atoms
   */

report_summ()
  {
  printf("Entries:   %d\n",entry_count);
  printf("Paths:     %d\n",total_path_count);
  printf("Fib Paths: %d\n",fib_path_count);
  printf("Atoms:     %d\n",atom_count);
  }



  /*
   * main routine
   *
   * The program uses a double pass through the dump file
   * The first pass counts the number of address prefixes
   * announced by each peer
   * The threshold is then used to select a core set of peers
   * who are announcing a "full" set of prefixes
   * The file is scanned a second time and the paths from each of
   * the selected peers are used to create atom sets
   */



int
main(argc, argv)
  int argc; 
  char *argv[];
  {
  int  i;
  int  arg ;
  int  argerr       = 0 ;
  int  arg_index    = 1 ;
  char in_file[256];
  char otf[256];
  FILE *f ;
  int report_ases = 1 ;
  int report_degrees = 1 ;
  int report_paths = 1 ;
  int report_aspairs = 1 ;
  int report_atoms = 1 ;


  for (arg = 1; arg < argc; arg++) {
    if (argv[arg][0] == '-'){
      switch(argv[arg][1]){
      case 'c':
        if ((++arg < argc) && (isdigit(argv[arg][0])))
          cutoff = atoi(argv[arg]) ;
        else 
          argerr = 1 ;
        break ;
      case 'd':
        debug = 1;
        if ((++arg < argc) && (isdigit(argv[arg][0])))
          debug = atoi(argv[arg]) ;
	if (debug > 2) argerr = 1 ;
        break;
      case 'e':
        if (++arg < argc)
          exclude[ecount++] = strdup(argv[arg]) ;
	else 
          argerr = 1 ;
        break ;
      case 'i':
        if (++arg < argc)
          include[icount++] = strdup(argv[arg]) ;
	else 
          argerr = 1 ;
        break ;
      case 'f':
        if ((++arg < argc) && sscanf(argv[arg],"%f",&fraction)) {
          if (fraction > 1.0) {
            argerr = 1 ;
	    }
	  }
	else 
          argerr = 1 ; 
        break ;
      case 'x':
        switch(argv[arg][2]) {
	  case 'a':
            report_ases = 0 ;
            break ;
	  case 'd':
            report_degrees = 0 ;
            break ;
	  case 'p':
            report_paths = 0 ;
            break ;
  	  case 'r':
	    report_aspairs = 0 ;
            break ;
	  case 't':
            report_atoms = 0 ;
	    break ;
  	  default:
            argerr = 1 ;
            continue ;
	  }

        break ;
      default:
        argerr = 1;
        break;
        }
      continue;
      }
    if (arg_index == 1) {
      strcpy(in_file,argv[arg]);
      ++arg_index ;
      }
    else if (arg_index == 2) {
      out_file_dir = strdup(argv[arg]);
      if (out_file_dir[strlen(out_file_dir) - 1] == '\\')
        out_file_dir[strlen(out_file_dir) - 1] = '\0';
      ++arg_index ;
      }
    }

  if (argerr) {
    printf("Usage: bgp-atoms [switches] bgpdump\n\n");
    printf("    <bgpdump>  is the filename of an ascii text output of a \"show ip bgp\"\n");
    printf("               command on a cisco router.\n");
    printf("    e.g. bgp-atoms bgptable.txt\n\n");
    return(1);
    }

  for (i = 0 ; i < NCACHE ; ++i) pathcache[i] = 0;
  if (!read_file(in_file,1)) { 
    printf("Cannot read %s\n",in_file) ;
    exit(1);
    }
  set_full_peers() ;
  if (!read_file(in_file,2)) {
    printf("Cannot re-read %s\n",in_file) ;
    exit(1);
    }

  if (report_ases) {
    sprintf(otf,"%s/as.txt",out_file_dir) ;
    if (f = fopen(otf,"w")) {
      fprintf(f,"# AS   Transit+Origin  Peer  Transit  Origin  Degree  Indegree  Outdegree\n") ;
      printas(ash,f);
      fclose(f);
      }
    }
  if (report_degrees) {
    sprintf(otf,"%s/asdeg.txt",out_file_dir) ;
    if (f = fopen(otf,"w")) {
      fprintf(f,"# degree   INdegree  ASCount %ASes N>=degree %ASes>=degree  ");
      fprintf(f,"OUTdegree  ASCount %ASes N>=degree %ASes>=degree  ");
      fprintf(f,"Degree  ASCount %ASes N>=degree %ASes>=degree  ");
      fprintf(f,"STUBdegree  ASCount %ASes N>=degree %ASes>=degree\n");
      print_degrees(f);
      fclose(f);
      }
    }
  if (report_aspairs) {
    sprintf(otf,"%s/aslk.txt",out_file_dir) ;
    if (f = fopen(otf,"w")) {
      fprintf(f,"# AS1 - AS2 : count\n") ;
      print_pairs(pairsh,f);
      fclose(f);
      }
    }
  if (report_paths) { 
    sprintf(otf,"%s/asp.txt",out_file_dir) ;
    if (f = fopen(otf,"w")) {
      fprintf(f,"# Count    ASPath\n") ;
      print_paths(asph,f);
      fclose(f);
      }
    }

  if (report_atoms) {
    sprintf(otf,"%s/atoms.txt",out_file_dir) ;
    if (f = fopen(otf,"w")) {
      print_atoms(f) ;
      fclose(f);
      }
    }
  report_summ() ;
}