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

#define max(a,b)   (((a) > (b)) ? (a) : (b))

        /* Parameters, default simulation parameters */

        /* -d delegated.txt - the name of the combined RIR registry delegation file */
char *delegated_file = "delegated.txt" ;

        /* size of the allocation block (as a prefix length) */
int ianablock = 12 ;

        /* name of the RIR to track in terms of delegations */
char *selectrir = "arin" ;

        /* start point of V4 delegations (in units of months prior to today) */
int start_date = 37 ;

        /* percent probablity that the allocation is to a new RIR */
int new_alloc = 23 ;

        /* average amount of time until re-allocation (fraction of a year) */
float re_alloc = 0.9 ;

        /* address management algorithm */
int sparse = 2; 
char *algorithm[] = {"sequential","sparse","rate_sparse"} ;

        /* report - verbosity */ 
int verbosity = 0 ;
char *vbexp[] = {"terse","Summary with headers","Per-Allocation details","Per-Allocation plus running summary","V4 Delegation records + per allocation"};

/* new variables: */
/* size of subnet id field  - default is 16  - min is 0, max is 16 */
int subnet_length = 16 ;

/* size of interface identifier id  - default is 64 - min is 0, max is 64 */
int interface_length = 64 ;

/* HD Ratio  - default is 0.8 - min is 0.1, max is 0.99 */
double hd_ratio = 0.8 ;

/* NAT factor - default is 0 - min is 0, max is 100 */
double nat_factor = 0.0 ;

/* minimum allocation - default is 16 bits */
int minimum_allocation = 16 ;

/* IPv4 allocation density metric */
float ipv4_alloc = 0.8 ;

        /* Constants */

        /* minimum allocation unit (prefix length) */
int min_size ; 


        /* Counters */
        
        /* allocation failure count */
int failures = 0 ;

        /* fragmented allocation coiunt */
int frags =0 ;

       
        /* global vars */

        /* current working date */
float ddate ;

        /* record processing counter */
int maxseq = 0 ;

int v4dist[33] ;
int v6dist[65];

        /* structure for each LIR */
struct lir {
  int lir_num ;                       /* index number */
  float rate ;                        /* current allocation run rate */
  int ready ;                         /* selection flag for window selection */
  unsigned long long slash32 ;                       /* current allocated address counter */
  unsigned long long  next_amount ;                   /* preferred next allocation size */
  unsigned long long deficit ;                       /* used if over-allocation was necessary */
  float next_date ;                   /* date for next allocation */
  unsigned long long  last_allocation_size ;          /* last allocation size */
  float first_allocation_date ;       /* first allocation date - used for rate calculation */
  int frag_count ;                    /* number of fragmentary address allocations */
  struct address *ablock ;            /* current active address block */
  struct lir *nxt ;                   /* linked list */
} *lirs = 0, **lirps;

        /* structure for each address allocation window */
struct address
{
  unsigned long long start_addr ;          /* start address */
  unsigned long mask_size ;           /* prefix mask size */
  unsigned long long block_size ;          /* block size (/32 units) */
  unsigned long long allocated ;           /* amount allocated in the window */
  unsigned long long free ;                /* amount free in the window */
  struct lir *block_owner ;           /* pointer to owning LIR */
  struct address *nxt ;               /* linkled list */
} *address = 0 ;

        /* function templates */        
extern int read_delegated();
extern void init_addresses();
extern void run_delegations();
extern void pool_status(double) ;
extern double prefix(unsigned long long) ;
extern double random_age() ;
extern void usage() ;
extern char *optarg;
extern int optind;
extern int optopt;
extern int opterr;
extern int optreset;
extern int getopt(int argc, char * const *argv, const char *optstring);
extern int allocate(int, struct lir *,unsigned long long, double);
extern int linear_allocate(int, struct lir *,unsigned long long,double);
extern int sparse_allocate(int, struct lir *,unsigned long long,double);
extern int rate_sparse_allocate(int,struct lir *,unsigned long long,double);
extern int add_frags(int,struct lir *,unsigned long long,double);

        /* HD ratio tralslation table - Amount of end customers per prefix allocation point, starting at a /32 */
/*
unsigned long int hdsizes[24] = {7131,12416,21618,37640,65536,114104,198668,345901,602248,1048576,
  1825676,3178688,5534417,9635980,16777216,29210829,50859008,88550676,154175683,268435456, 467373274,
  813744135,1416810830,2466810933UL};
*/
double hdsizes[24];

        /* dynamic arrays used to store selected delegation sequence for replay into V6 management system */
float *dates;
unsigned int *allocs;
char **records ;

        /* Main block */
main(int argc, char **argv) 
{
  int ch ;
  double n, max ;
  int i, j ;
  int print_table = 0 ;

  check_date(&start_date);
  opterr = 0 ;
  while ((ch = getopt(argc,argv,"a:d:h:l:i:m:n:p:r:s:tv:z: ")) != -1)
    switch (ch) {
      case 'a':
        if (!strncmp(optarg,algorithm[1],strlen(optarg))) sparse = 1 ;
        else if (!strncmp(optarg,algorithm[2],strlen(optarg))) sparse = 2 ;
        else if (!strncmp(optarg,algorithm[0],strlen(optarg))) sparse = 0 ;
        else usage() ;
        break ;
      case 'd':
        delegated_file = (char *) strdup(optarg) ;
        break ;
      case 'h':
	hd_ratio = atof(optarg);
        if ((hd_ratio <= 0.0) || (hd_ratio > 100.0)) usage() ;
        break ;
      case 'i':
        ianablock = atoi(optarg) ;
        if ((ianablock < 2) || (ianablock > 32)) usage() ;
        break ;
      case 'l':
        subnet_length = atoi(optarg) ;
        if ((subnet_length < 0) || (subnet_length > 32)) usage() ;
        break ;
      case 'm':
	start_date = atoi(optarg) ;
        if (!check_date(&start_date)) usage() ;
        break ;
      case 'n':
	nat_factor = atof(optarg) ;
        if ((nat_factor < 0.0) || (nat_factor > 10.0)) usage() ;
        break ;
      case 'p':
        new_alloc = atoi(optarg)  ;
        if ((new_alloc < 1) || (new_alloc > 99)) usage() ;
        break ;
      case 'r':
        re_alloc = (float) (atoi(optarg) / 12.0) ;
	if ((re_alloc < 0.1) || (re_alloc > 4.0)) usage() ;
        break ;
      case 's':
        selectrir = (char *) strdup(optarg) ;
        if (strcmp(selectrir,"all") && strcmp(selectrir,"afrinic") && strcmp(selectrir,"arin") && strcmp(selectrir,"apnic") && strcmp(selectrir,"ripencc") && strcmp(selectrir,"lacnic"))
          usage() ;
	break;
      case 't':
        print_table = 1 ;
        break ;
      case 'v':
        verbosity = atoi(optarg) ;
        break ;
      case 'z':
        minimum_allocation = atoi(optarg) ;
        if ((minimum_allocation < 2) || (minimum_allocation > 32)) usage() ;
        break ;
      case '?':
      default:
        usage();
      }

  min_size = 128 - interface_length - subnet_length - minimum_allocation ;

  if (verbosity > 0) {
    printf("Address Management algorithm: -a %s\n",algorithm[sparse]) ;
    printf("IPv4 Delegation Log File:     -d %s\n",delegated_file) ;
    printf("HD-Ratio:                     -h %4.2f\n",hd_ratio) ;
    printf("Address Block Size:           -i /%d\n",ianablock) ;
    printf("Subnet ID Length:             -l %d\n",subnet_length);
    printf("Start Date for simulation:    -m %d\n",start_date) ;
    printf("NAT factor:                   -n %4.2f\n",nat_factor) ;
    printf("Probability of new LIR (%%):   -p %d\n",new_alloc);
    printf("Allocation lifetime (yrs):    -r %5.2f \n",re_alloc) ;
    printf("Selected RIR                  -s %s\n",selectrir) ;
    printf("Verbosity Level:              -v %d   %s\n",verbosity,vbexp[verbosity]) ;
    printf("Minimum Allocation Size:      -z %d\n",minimum_allocation) ;
    }

  if ((hd_ratio > 0.0) && (hd_ratio < 1.0)) {
    for (i = 0 ; i < 24 ; ++i) {
      hdsizes[i] = pow(pow(2.0,((double) (i + minimum_allocation))),hd_ratio) ;
      }
    }
  else if (hd_ratio > 1.0) {
    int step ;
    int exp ;
    double density_percentage ;

    step = (int) hd_ratio ;
    density_percentage = hd_ratio - ((int) hd_ratio) ;
    for (i = 0 ; i < 24 ; ++i) {
      exp = ((i + minimum_allocation - 2) / step) + 1 ;
      hdsizes[i] = pow(2.0,((double) (i + minimum_allocation))) * pow(density_percentage,(double) exp) ;
      }
    }

  for (i = 0 ; i < 32 ; ++i) v4dist[i] = 0 ;

  for (i = 0 ; i < 64 ; ++i) v6dist[i] = 0 ;
  if (print_table) {
    for (print_table = 24 ; print_table > 6 ; --print_table) {
      printf("  /%-2d    ",print_table) ;
      i = (1 << (32 - print_table)) ;
      n = (i * ipv4_alloc) ;
      n += n * nat_factor ;
      j = n ;
      printf("  %8d  ",j) ;
      i = 0 ;
      while ((i < 24) && (j > hdsizes[i])) ++i ;
      j = min_size - i ;
      printf("  /%d\n",j) ;
      }
    }
  read_delegated() ;
  init_addresses() ;
  if (verbosity > 0)
    printf("Registry Transaction Count:   %d\n\n",maxseq) ;
  run_delegations() ;  
  pool_status(ddate) ;

  if (verbosity > 0) print_dist() ;

}


/*=======================================================================*/

int
read_delegated()
{
  FILE *f ;
  char *c ;
  char inb[512] ;
  char rir[128],cc[128],typ[128],addr[128],sts[128] ;
  int i;
  unsigned int v4size ;
  unsigned int date ;
  unsigned int size ;
  unsigned int v4m ;
  unsigned int v6m ;
  double psize ;

  struct d_rec {
    int date ;
    float fdate ;
    char *d_rir ;
    unsigned int size ;
    unsigned int alloc ;
    struct d_rec *nxt ;
  } *d_list = 0, *tmp, *tmp1, *tmp2 ;

  if (!(f = fopen(delegated_file,"r"))) return(0) ;

  while (fgets(inb,511,f)) {
    while (c = strchr(inb,'|')) *c = ' ' ;
    sscanf(inb,"%s %s %s %s %d %d %s",rir,cc,typ,addr,&v4size,&date,sts) ;

    //    printf("cc=%s rir=%s date=%d %d -> %s",cc,rir,date, start_date,inb) ;
    if (!strcmp(cc,"ZZ")) continue ;
    if (date < start_date) continue ;
    if ((!strcmp(selectrir,"all")) || (!strcmp(rir,selectrir))) {

      //printf("GOT %s\n",rir) ;

      ++maxseq ;
      tmp = (struct d_rec *) malloc(sizeof *tmp) ;
      tmp->date = date ;
      tmp->d_rir = strdup(rir) ;
      tmp->size = size ;
      size = (date / 10000) ;
      tmp->fdate = size + (((date % 10000) / 100.00) / 12.0) ;

      size = ceil(log(v4size) / log(2.0)) ;
      v4m = 32 - size ;
      ++v4dist[v4m] ;
      psize = (double) (v4size * ipv4_alloc) ;
      psize += (psize * nat_factor) ;
      i = 0 ;
      while ((i < 24) && (psize > hdsizes[i])) ++i ;
      tmp->alloc = min_size - i;
      v6m = min_size - i ;
      ++v6dist[v6m] ;
      tmp->alloc = v6m ;
      tmp->nxt = 0 ;

      tmp->nxt = 0 ;
      if (!(tmp1 = d_list)) d_list = tmp ;
      else {
        tmp2 = 0 ;
        while ((tmp1) && (tmp1->date < tmp->date)) {
          tmp2 = tmp1 ;
          tmp1 = tmp1->nxt ;
	  }
        tmp->nxt = tmp1 ;
        if (tmp2) tmp2->nxt = tmp ;
        else d_list = tmp ;
        }
      }
    }
  fclose(f) ;
  ++maxseq ;
  dates = (float *) malloc(maxseq * (sizeof *dates)) ;
  allocs = (int *) malloc(maxseq * (sizeof *allocs)) ;
  lirps = (struct lir **) malloc(maxseq * (sizeof *lirps)) ;
  if (verbosity > 3) records = (char **)malloc(maxseq * (sizeof *records)) ;
  i = 0 ;
  tmp = d_list ;
  while (tmp) {
    if (i < maxseq) {
      dates[i] = tmp->fdate ;
      allocs[i] = tmp->alloc ;
      ++i ;
      }
    tmp1 = tmp ;
    tmp = tmp->nxt ;
    free(tmp1) ;
    }
  maxseq = i ;
}

void
init_addresses()
 {
  address = (struct address *) malloc(sizeof *address) ;
  address->start_addr = 0 ;
  address->mask_size = 0 ;
  address->block_size = (1ULL << ((min_size - ianablock) - address->mask_size)) ;
  address->allocated = 0;
  address->free = address->block_size ;
  address->block_owner = 0 ;
  address->nxt = 0 ;
 }

void
run_delegations()
 {
  int i = 0 ;
  int spin ;
  int lir_count = 0;
  int av ;
  int rcount = 0 ;
  int ecount = 0 ;
  int nspin = 1 ;
  unsigned long long minv = 0 ;
  unsigned long long minvc = 0 ;
  unsigned int size ;
  unsigned long long nsize ;
  struct lir *tmp ;

  srand(time(0)) ;
  spin = rand() % 1000 ;
  for (i = 0 ; i < spin ; ++i) random() ;

  for (i = 0 ; i < maxseq ; ++i) {

    ddate = dates[i] ;
    size = allocs[i] ;


    spin = random() % 100  ;

    nsize = (1 << (min_size - size)) ;


    if (verbosity > 3) printf("\n%s",records[i]) ;
    if (verbosity > 1) printf("%5.2f, /%d (%03uq):",ddate, size, nsize) ;

    if (spin > new_alloc) {
      rcount = ecount = 0 ;
      nspin = 1 ;
      minv = minvc = 0 ;
     
      if (verbosity > 1) printf("[add] ") ;
      tmp = lirs ;
      while (tmp) {
        if (nsize <= tmp->deficit) {
          tmp->deficit -= nsize ;
          if (verbosity > 1) printf("^LIR:%d Reduce overalloc by %qu from %qu to %qu",
				    tmp->lir_num, nsize, tmp->deficit + nsize, tmp->deficit) ;
          ecount = rcount = nspin = 0 ;
          tmp = 0 ;
	  }
        else {
          if ((ddate > tmp->next_date) && (nsize <= tmp->next_amount)) {
            tmp->ready = tmp->next_amount - nsize ;
            if (!minv) { minv = tmp->ready ; minvc = 1 ; }
            else if (tmp->ready == minv) ++minvc ;
            if (tmp->ready < minv) { minv = tmp->ready ; minvc = 1 ; }
            ++rcount ;
            if (nsize == tmp->next_amount) {
              ++ecount ;
              tmp->ready = -1 ;
	      }
	    }
          else tmp->ready = 0 ;
          tmp->rate = tmp->slash32 / ((tmp->next_date > ddate ? tmp->next_date : ddate) - tmp->first_allocation_date);
          tmp = tmp->nxt ;
          }
        }
      if (ecount) {
        if (ecount > 1) nspin = random() % ecount ;
        else nspin = 0 ;

        tmp = lirs ;
        while (tmp) {
          if (tmp->ready == -1) {
            if (!nspin) {
              if (verbosity > 1) printf("=LIR:%d (date=%5.2f) ",tmp->lir_num,tmp->next_date) ;
              tmp->slash32 += nsize ;
              tmp->next_amount = tmp->slash32 ;
              tmp->next_date = ddate + re_alloc + random_age() ;
              tmp->rate = tmp->slash32 / (ddate - tmp->first_allocation_date + 1.0);
	      lirps[i] = tmp ;

              if (!(av = allocate(1,tmp,tmp->slash32/2,ddate))) {
                if (verbosity > 1) printf(" FRAG") ;
                add_frags(1,tmp,tmp->slash32/2,ddate) ;
	        }
              else if (av > 1) {
                if (verbosity > 1) printf(" FRAG:1") ;
	        ++frags ;
	        }
	      else if (verbosity > 1) {
                printf(" ok: %u -> %u",tmp->slash32 - nsize, tmp->slash32) ;
	        }
              tmp = 0 ;
	      }
            --nspin ;
	    }
          if (tmp) tmp = tmp->nxt ;
	  }
	}
      else if (rcount) {
        if (minvc > 1) nspin = random() % minvc ;
        else nspin = 0 ;
        tmp = lirs ;
        while (tmp) {
          if (tmp->ready == minv) {
            if (!nspin) {
              int alloc ;

              if (verbosity > 1) printf("vLIR:%d (date=%5.2f) ",tmp->lir_num,tmp->next_date) ;
              if (sparse) {
                tmp->deficit = tmp->next_amount - nsize ;
                alloc = tmp->next_amount ;
                tmp->slash32 += tmp->next_amount ;
                tmp->next_amount = tmp->slash32 ;
                tmp->next_date = ddate + re_alloc + random_age() ;
	        }
              else {
                alloc = nsize ;
                tmp->slash32 += nsize ;
                tmp->next_amount -= nsize ;
	        }
              tmp->rate = tmp->slash32 / (ddate - tmp->first_allocation_date + 1.0);
	      lirps[i] = tmp ;

              if (!(av = allocate(1,tmp,alloc,ddate))) {
                if (verbosity > 1) printf(" FRAG") ;
                add_frags(1,tmp,alloc,ddate) ;
	        }
              else if (av > 1) {
                if (verbosity > 1) printf(" FRAG:1") ;
                //printf("Fragmentation for LIR - allocation of /%5.2f\n",prefix(tmp->slash32/2)) ;
	        ++frags ;
	        }
              else if (verbosity > 1) {
                printf(" ok: %u -> %u (%d)",tmp->slash32-alloc, tmp->slash32,nsize) ;
	        }
              tmp = 0;
	      }
            --nspin ;
	    }
          if (tmp) tmp = tmp->nxt ;
	  }
	}
      else if (nspin) {
        // printf(" xx\n") ;
          if (verbosity > 1) printf("-none ") ;
          spin = 0 ;
          } 
      }

    if (spin <= new_alloc) {
      if (verbosity > 1) printf("[new] ") ;
      /* this is a new allocation - set up a new LIR */
      tmp = (struct lir*) malloc(sizeof *tmp) ;
      tmp->lir_num = ++lir_count ;
      tmp->slash32 = nsize ;
      tmp->rate = tmp->slash32 ;
      tmp->deficit = 0 ;
      tmp->next_amount = tmp->slash32 ;
      tmp->next_date = ddate + re_alloc + random_age() ;
      tmp->last_allocation_size = tmp->slash32 ;
      tmp->first_allocation_date = ddate ;
      tmp->frag_count = 0 ;
      tmp->nxt = lirs ;
      lirs = tmp ;
      lirps[i] = lirs;
      // printf("%8.2f New Allocation: %d to %d\n",ddate,size,lir_count) ;
      if (verbosity > 1) printf("-LIR:%d (date=%5.2f) ",tmp->lir_num,ddate) ;
    
      if (!(av = allocate(0,lirs,lirs->slash32,ddate))) {
	if (verbosity > 1) printf(" FRAG") ;
         add_frags(0,lirs,lirs->slash32,ddate) ;
	 }
       else if (av > 1) {
         if (verbosity > 1) printf(" FRAG:1") ;
         //printf("Fragmentation for LIR - allocation of /%5.2f\n",prefix(lirs->slash32/2)) ;
	 ++frags ;
	 }
       else if (verbosity > 1) {
         printf(" ok: %u -> %u",0, tmp->slash32) ;
         }
      }
    if (verbosity > 1) printf("\n") ;
    if ((verbosity > 2) || (verbosity < 0)) pool_status(ddate) ;
    }
}

void
pool_status(double ddate)
{
  struct address *tmp = address ;
  unsigned long long pool_size = 0, alloctot = 0, totw = 0 ;
  int num_windows = 0 ;
  unsigned long long lgst_hole = 0 ;
  struct lir *lptr = lirs ;
  int numlirs = 0 ;
  char *format ;
  static int occupancy  = 0 ;
  static int lastmonth = -1 ;
  static int monthcount = -1 ;
  int month ;
  while (lptr) {
    ++numlirs ; 
    lptr = lptr->nxt ;
    }

  while (tmp) {
    pool_size += tmp->block_size ;
    alloctot += tmp->allocated ;
    if (tmp->block_owner) {
      totw += tmp->free ;     
      ++num_windows ;
      }
    if (tmp->free > lgst_hole) lgst_hole = tmp->free ;
    tmp = tmp->nxt ;
    }

  if (verbosity < 1) {
    format = "%5.2f %4.2f %4.2f %u %u %4.2f %5.2f %4.2f %5.2f %d %d %d\n";
    if (!verbosity)
        printf(format,
         (float) occupancy,
         prefix(pool_size),
         prefix(alloctot), num_windows,
	 numlirs ,
	 prefix(lgst_hole),
         (float) ((alloctot / (float) pool_size) * 100.0),
         prefix((unsigned long long) (alloctot / num_windows)), 
         prefix((unsigned long long) (totw / num_windows)),
         frags, failures, maxseq) ;
    if (verbosity == -1) {
      if (((alloctot * 100)  / pool_size) >= (occupancy)) {
        printf(format,
         (float) occupancy,
         prefix(pool_size),
         prefix(alloctot), num_windows,
	 numlirs ,
	 prefix(lgst_hole),
         (float) ((alloctot / (float) pool_size) * 100.0),
         prefix((unsigned long long) (alloctot / num_windows)), 
         prefix((unsigned long long) (totw / num_windows)),
         frags, failures, maxseq) ;
        occupancy += 10 ;
        if (occupancy > 100) exit(0) ;
        }
      }
    if (verbosity == -2) {
      month = (((int) (ddate * 100)) % 100) * 0.12 ;
      if (month != lastmonth) {
        format = "%d %5.2f %4.2f %4.2f %u %u %4.2f %5.2f %4.2f %5.2f %d %d %d\n";
        printf(format,
             ++monthcount,
	     ddate,
             prefix(pool_size),
             prefix(alloctot), num_windows,
	     numlirs ,
	     prefix(lgst_hole),
             (float) ((alloctot / (float) pool_size) * 100.0),
             prefix((unsigned long long) (alloctot / num_windows)), 
             prefix((unsigned long long) (totw / num_windows)),
             frags, failures, maxseq) ;
        lastmonth = month ;
        }
      }
    return ;
    }

      
  if (verbosity > 0) format = "\nPool Size:\t\t\t/%4.2f\nAllocation Total:\t\t/%4.2f\nNumber of Allocation Windows:\t%u\nNumber of LIRs:\t\t\t%u\nLargest Open Allocation Window:\t/%4.2f\nPercent Occupancy:\t\t%5.2f%%\nAverage Allocation Size:\t/%4.2f\nAverage Free Window Size:\t/%5.2f\nFragmented Allocations:\t\t%d\nNum of Failed Allocations:\t%d\nTransaction Count:\t\t%d\n";
  else format = "%4.2f %4.2f %u %u %4.2f %5.2f %4.2f %5.2f %d %d %d\n";
  printf("pool = %qu\n",pool_size) ;
  printf(format,
         prefix(pool_size),
         prefix(alloctot), num_windows,
	 numlirs ,
	 prefix(lgst_hole),
         (float) ((alloctot / (float) pool_size) * 100.0),
         prefix((unsigned long long) (alloctot / num_windows)), 
         prefix((unsigned long long) (totw / num_windows)),
         frags, failures, maxseq) ;
  

}


print_dist()
{
  int i ;
  int sz = 32;

  if (min_size > 32) sz = min_size ;
  printf("Mask ") ;
  for (i = 8 ; i <= sz ; ++i) printf(" %4d",i) ;
  printf("\n") ;
  printf("V4   ") ;
  for (i = 8 ; i <= 32 ; ++i) printf(" %4d",v4dist[i]) ;
  printf("\n") ;
  printf("V6   ") ;
  for (i = 8 ; i <= min_size ; ++i) printf(" %4d",v6dist[i]) ;
  printf("\n") ;
  
}

/*===================================================*/

void 
usage()
{
  printf(" \n Args: \n  -a sparse \n  -a ratesparse \n  -a sequential \n") ;
  printf("      Select the address managmenet algorithm to use	\n") ;
  printf("      default is -a ratesparse \n") ;
  printf(" \n") ;
  printf("  -d file\n") ;
  printf("      Select the delegation log file\n") ;
  printf("  \n") ;
  printf("  -h hd-ratio\n") ;
  printf("      Select the HD-Ratio value (default 0.8, min 0.1, max 0.99)\n") ;
  printf("  \n") ;
  printf("  -i n \n") ;
  printf("      Select the address block size as a /n \n") ;
  printf("      n should be between 2 and 32 \n") ;
  printf("      default is -i 12 \n") ;
  printf(" \n") ;
  printf("  -l subnet-id_length\n") ;
  printf("    Select the length of the subnet ID field (default 16, min 0, max 32)\n") ;
  printf("  \n") ;
  printf("  -m date \n") ;
  printf("      Selects the date to start the simulation. Format is yyyymmdd \n") ;
  printf("      Values between 1 and 120 for date are interested as months \n") ;
  printf("      -m 12 is equivalent to the last twleve months \n") ;
  printf("      default is -m 36 \n") ;
  printf(" \n") ;
  printf("  -n nat-factor\n") ;
  printf("    Selects the NAT factor where size = size + (size * nat_factor)\n") ;
  printf("    (default 0.0, max 10.0)\n") ;
  printf("  \n") ;
  printf("  -p probability_val \n") ;
  printf("      Selects the probability that an allocation refers to a new LIR \n") ;
  printf("      n is a value between 1 and 99 \n") ;
  printf("      default is -p 22 \n") ;
  printf(" \n") ;
  printf("  -r months \n") ;
  printf("      Number of months over which the initial allocation is notionally \n") ;
  printf("      evaluated. This is an average value, where the simulation randomizes \n") ;
  printf("      the value per LIR to a period between 6 months shorter and 18 months \n") ;
  printf("      longer than this average value. \n") ;
  printf("      default is -r 11 \n") ;
  printf(" \n") ;
  printf("  -s rir \n") ;
  printf("      Select a RIR for the simulation \n") ;
  printf("      possible values are: arin apnic ripcncc lacnic all\n") ;
  printf(" \n") ;
  printf("  -v n \n") ;
  printf("      Select verbosity level \n") ;
  printf("      default is 0 \n") ;
  printf("      Values:\n") ;
  printf("       -2 print out a summary of the allocation pool on a monthly basis\n") ;
  printf("       -1 print out a summary of the allocation pool for each 10%% shift in allocation density\n") ;
  printf("        0  print out a summary of the allocation pool at the end of the simulation\n") ;
  printf("        1 print out a more verbose summary\n") ;
  printf("        2 print out each allocation transaction\n") ;
  printf("        3 print out each allocation transaction and a summary of the pool after each transaction\n") ;
  printf("        4 print out the V4 transaction, the equiv v6 transaction and a summary of the pool\n") ;
  printf(" \n") ;
  printf("  -z min-alloc_size\n") ;
  printf("      Select minimum allocation size (default = 16, min = 2, max = 32\n") ;
  printf("  \n") ;
  exit(1) ;
}


int
check_date(int *date) 
{
  time_t t;
  struct tm* lt ;
  int year, month, day ;
 
  t = time(0) ;
  lt = localtime(&t) ;

  if (*date < 120) {
    year = *date / 12 ;
    month = *date % 12 ;
    lt->tm_mon -= month ;
    if (lt->tm_mon < 0) { lt->tm_mon += 12 ; ++year ; } ;
    lt->tm_year -= year ;
    t = mktime(lt) ;
    lt = localtime(&t) ;
    *date = ((lt->tm_year + 1900) * 10000) + ((lt->tm_mon + 1) * 100) + lt->tm_mday ;
    return(1) ;
    }  
  year = (*date / 10000) ;
  month = (*date / 100) % 100 ;
  day = *date % 100 ;
  if ((day < 1) || (day > 31)) return(0) ;
  if ((month < 0) || (month > 12)) return(0) ;
  if ((year < 1983) || (year > (lt->tm_year + 1900))) return(0) ;
  if ((((lt->tm_year + 1900) * 10000) + ((lt->tm_mon + 1) * 100) + lt->tm_mday) < *date) return(0) ;
  
  return(1) ;
}

int
add_frags(int expansion,struct lir *lirptr,unsigned long long slash32s,double ddate)
{
  unsigned long long unit = slash32s ;
  int av ;
  int fc = 0 ;

  ++frags ;
  while (slash32s) {
    if (av = allocate(expansion,lirptr,unit,ddate)) {
      if (av > 1) ++fc ;
      slash32s -= unit ;
      if (slash32s <= 0) { if (verbosity > 1) printf(":%d ",fc); return(1) ; }
      expansion = 1 ;
      while (unit > slash32s) unit = unit / 2 ;
      }
    else {
      if (unit <= 1) {
        ++failures ;
        return(0) ;
        }
      unit = unit / 2 ;
      }
    }

}


double
prefix(unsigned long long span)
{
  double tmp ;
  double size ;

  if (!span) return(0) ;
  tmp = span ;
  size = log(span) ;
  size = size / log(2.0) ;
  return(min_size - size) ;

  //  return(32 - log((double) span)/log(2.0));
}


double
random_age()
{
  int age ;
  double float_adj ;

  age = random() % 100 ;

  if (age < 40)
    return(float_adj = 0 - (0.5 * (age / 40.0))) ;
  if (age > 55) {
    age -= 55  ;
    return(float_adj = 2.0 * (age / 45.0)) ;
    }
  return(0.0);   
}


int
rate_sparse_allocate(int expansion, struct lir *lirptr,unsigned long long slash32s,double ddate)
{
  struct address *tmp, *tmp1 ;
  int i = 0 ;
  struct address *splitpoint = 0 ;
  float lir_lifetime, new_lifetime, lt, split_lt ;
  int rtnvalue = 1 ;
  int factor = 2 ;

  /* the first allocation just splits up the address block */

  if (!address->block_owner) {
    address->block_owner = lirptr ;
    address->allocated = slash32s ;
    address->free -= slash32s ;
    lirptr->ablock = address ;
    return(rtnvalue) ;
    }

  /* if this is an expansion of an existing window, and there is space, then 
     perform the expansion */

  if (expansion) {
    tmp = address ;
    while (tmp) {
      if (tmp->block_owner == lirptr) {
        if (tmp->free >= slash32s) {
          tmp->free -= slash32s ;
          tmp->allocated += slash32s ;
          return(rtnvalue) ;
	  }
        }
      tmp = tmp->nxt ;
      }
    ++rtnvalue ;
    factor = 1 ;
    }

  

    /* find all blocks where the open allocation window is at lease twice as large 
       as the local block */
    /* use the rate algorithm to find the 'best' block */
    /* split the block in half */
     
  split_lt = 0 ;
  splitpoint = 0 ;
  tmp = address ;
  while (tmp) {
    if ((tmp->free >= tmp->allocated) && (tmp->free >= (slash32s * factor))) {
      lir_lifetime = ((tmp->block_size / 2) - tmp->allocated) / tmp->block_owner->rate ;
      new_lifetime = (tmp->block_size / 2) / slash32s ;
      lt = lir_lifetime < new_lifetime ? lir_lifetime : new_lifetime ;
      if (lt > split_lt) {
        split_lt = lt ;
        splitpoint = tmp ;
        }
      }
    tmp = tmp->nxt ;
    }

  if (tmp = splitpoint) {

  //  printf(" SPLIT %d\n" ,slash32s) ;

  /* now split this in two */    
    tmp1 = (struct address *) malloc(sizeof *tmp1) ;
    tmp1->nxt = tmp->nxt ;
    tmp->nxt = tmp1 ;


    ++tmp->mask_size ;
    tmp->block_size = tmp->block_size / 2 ;
    tmp->free -= tmp->block_size ;
  
    tmp1->start_addr = tmp->start_addr + tmp->block_size ;
    tmp1->mask_size = tmp->mask_size;
    tmp1->block_size = tmp->block_size ;
    tmp1->allocated = slash32s ;
    tmp1->free = tmp1->block_size - tmp1->allocated ;
    tmp1->block_owner = lirptr ;
    lirptr->ablock = tmp1 ;
    ++lirptr->frag_count ;
    return(rtnvalue) ;
    }
  /* about to fail - lets see if there is ANY window at all left at this point  */
  tmp = address ;
  tmp1 = 0 ;
  factor = 0 ;
  while (tmp) {
    if (tmp->free >= slash32s) {
      if (tmp->free > factor) {
        tmp1 = tmp ;
        factor = tmp->free ;
        }
      }
    tmp = tmp->nxt ;
    }
  if (tmp = tmp1) {
    tmp1 = (struct address *) malloc(sizeof *tmp1) ;
    tmp1->nxt = tmp->nxt ;
    tmp->nxt = tmp1 ;
    tmp1->block_size = slash32s ;
    tmp1->start_addr = tmp->start_addr + tmp->block_size - slash32s ;
    tmp->block_size -= slash32s ;
    tmp->free -= slash32s ;
    tmp1->allocated = slash32s ;
    tmp1->free = tmp1->block_size - tmp1->allocated ;
    tmp1->block_owner = lirptr ;
    lirptr->ablock = tmp1 ;
    ++lirptr->frag_count ;
    return(rtnvalue) ;
    }
  return(0) ;

}


int
sparse_allocate(int expansion, struct lir *lirptr,unsigned long long slash32s,double ddate)
{
  struct address *tmp, *tmp1 ;
  int i = 0 ;
  struct address *splitpoint = 0 ;
  float lir_lifetime, new_lifetime, lt, split_lt ;
  int rtnvalue = 1 ;
  int factor = 2 ;
  static unsigned long c_alloc_size = 0 ;

  if (!address->block_owner) {
    address->block_owner = lirptr ;
    address->allocated = slash32s ;
    address->free -= slash32s ;
    lirptr->ablock = address ;
    return(rtnvalue) ;
    }

  if (expansion) {
    tmp = address ;
    while (tmp) {
      if (tmp->block_owner == lirptr) {
        if (tmp->free >= slash32s) {
          tmp->free -= slash32s ;
          tmp->allocated += slash32s ;
          return(rtnvalue) ;
	  }
        }
      tmp = tmp->nxt ;
      }
    ++rtnvalue ;
    factor = 1 ;
    }

  /* find the first open allocation window of c_alloc_size
     if none available halve c_alloc_size and try again */
  
  if (!c_alloc_size) c_alloc_size = (1 << 31) ;

  splitpoint = 0 ;
  split_lt = 0 ;

  while ((!splitpoint) && c_alloc_size) {
    tmp = address ;
    while (tmp) {
      if (tmp->free >= c_alloc_size) {
        if (slash32s > c_alloc_size) return(0) ;

        tmp1 = (struct address *) malloc(sizeof *tmp1) ;
        tmp1->nxt = tmp->nxt ;
        tmp->nxt = tmp1 ;
        tmp1->block_size = c_alloc_size ;
        tmp1->start_addr = tmp->start_addr + tmp->block_size - c_alloc_size ;
        tmp->block_size -= c_alloc_size ;
        tmp->free -= c_alloc_size ;
        tmp1->allocated = slash32s ;
        tmp1->free = tmp1->block_size - tmp1->allocated ;
        tmp1->block_owner = lirptr ;
        lirptr->ablock = tmp1 ;
        ++lirptr->frag_count ;
        return(rtnvalue) ;
        }
      tmp = tmp->nxt ;
      }
    c_alloc_size = c_alloc_size / 2 ;
    }
  return(0) ;
}


int
linear_allocate(int expansion, struct lir *lirptr,unsigned long long slash32s,double ddate)
{
  struct address *tmp, *tmp1 ;
  int i = 0 ;
  struct address *splitpoint = 0 ;
  float lir_lifetime, new_lifetime, lt, split_lt ;
  int rtnvalue = 1 ;
  int factor = 2 ;
  unsigned long long alloc ;
  static int not_initial = 0 ;
  float shut_date  = 0.0;

  if (expansion && not_initial) {
    tmp = address ;
    while (tmp) {
      if (tmp->block_owner == lirptr) {
        if (tmp->free >= slash32s) {
          tmp->free -= slash32s ;
          tmp->allocated += slash32s ;
          return(rtnvalue) ;
	  }
        }
      tmp = tmp->nxt ;
      }
    ++rtnvalue ;
    factor = 1 ;
    }

  /* need to split up the last block and create a new window */
  ++not_initial ;

  alloc = slash32s + max(slash32s,4) ;
  while (alloc) {
    tmp = address ;
    while (tmp) {
      if ((shut_date > 1.0) && (tmp->block_owner) && (tmp->block_owner->next_date < shut_date) && (tmp->free >= alloc)) {
        tmp1 = (struct address *) malloc(sizeof *tmp1) ;
        tmp1->start_addr = tmp->start_addr + tmp->block_size - alloc ;
        tmp->free -= alloc ;
        tmp->block_size -= alloc ;
        tmp1->block_size = alloc ;
        tmp1->allocated = slash32s ;
        tmp1->free = alloc - slash32s ;
        tmp1->block_owner = lirptr ;
        lirptr->ablock = tmp1 ;
        tmp1->nxt = tmp->nxt ;
        tmp->nxt = tmp1 ;
        return(rtnvalue) ;
        }
      if ((!tmp->block_owner) && (tmp->free >= alloc)) {
        tmp->block_owner = lirptr ;
        tmp->allocated = slash32s ;
        tmp->free = alloc - slash32s ;
        lirptr->ablock = tmp ;

        tmp1 = (struct address *) malloc(sizeof *tmp1) ;
        tmp1->nxt = tmp->nxt ;
        tmp->nxt = tmp1 ;
        tmp1->block_size = tmp1->free = tmp->block_size - alloc;
        tmp->block_size  = alloc ;
        tmp1->block_owner = 0 ;  
        tmp1->start_addr = tmp->start_addr + tmp->block_size ;
        tmp1->allocated = 0;
        return(rtnvalue) ;
        }
      tmp = tmp->nxt ;
      }
    if (shut_date < 1.0) 
      shut_date = ddate - 0.5 ; 
    else if (alloc > slash32s) {
      alloc = slash32s ;
      shut_date = 0.0 ;
      }
    else if (shut_date < 3000.0) {
      shut_date = 3001.0 ;
      }
    else 
      alloc = 0 ;
    }
  return(0) ;
}


int
allocate(int expansion, struct lir *lirptr,unsigned long long slash32s, double ddate)
{
  if (sparse == 2) return(rate_sparse_allocate(expansion,lirptr,slash32s,ddate));
  if (sparse == 1) return(sparse_allocate(expansion,lirptr,slash32s,ddate));
  return(linear_allocate(expansion,lirptr,slash32s,ddate)) ;
}