/* mergenetblocks.c  by mjd 20011012 */

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>

#ifndef BIG_ENDIAN
#ifndef LITTLE_ENDIAN
#error "You must define BIG_ENDIAN or LITTLE_ENDIAN"
#endif 
#endif 

typedef unsigned long U32;      /* Should be precisely 32 bits */

#define unless(c) if(!(c))

typedef struct st_node {
  struct st_node *next;
  struct st_node *peer;
  U32 addr;
#ifdef DEBUG
  char * a; 
#endif
  unsigned short netmask;
} node;

node *acquire_data(FILE *, U32 *);
node *new_node(U32);
node *string_to_node(char *);
void  print_node(node *);
node *coalesce(node *, unsigned short);

int
main(int argc, char **argv) 
{
  FILE * in;
  node *addrs, *root;           /* list of addresses */
  U32 n_addrs;                  /* number of addreses in list */
  unsigned short bit;

  if (argc == 2) {
    unless (in = fopen(argv[1], "r")) {
      perror("open");
      exit(1);                  /* die */
    }
  } else if (argc == 1) {
    in = stdin;
  } else {
    fprintf(stderr, "Usage: %s [inputfile]\n", argv[0]);
    exit(1);
  }
  
  root = addrs = acquire_data(in, &n_addrs);

  for (bit = 0; bit < 32 && addrs; bit++) {
    addrs = coalesce(addrs, bit);
  }

  for ( ; root; root = root->next ) {
    print_node(root);
  }
  
  return 0;
}

void 
print_node(node * n)
{
  
  unsigned char *c = (unsigned char *)&(n->addr);
  printf("%u.%u.%u.%u/%u\n", c[0], c[1], c[2], c[3], n->netmask);
}

node *
coalesce(node *addrs, unsigned short level)
{
  node *cur, *prev = NULL, *topstart = NULL, *next;

  /* 1111...11100000...00 */
  U32 mask = ~((1 << (level+1))-1);
#ifdef LITTLE_ENDIAN
    unsigned char c, *p = (unsigned char *) &mask;
    c = p[0]; p[0] = p[3]; p[3] = c;
    c = p[1]; p[1] = p[2]; p[2] = c;
#endif

  /* goal: traverse addrs->peer list
   * create list of coalesced nodes in top->peer list
   * coalesced and leftover uncoalesced nodes all linked in addrs->next list
   */
  for (cur = addrs; cur; cur = next) {
    next = cur->peer;
    if (next &&
        (cur->addr & mask) == (next->addr & mask)) {
      /* coalesce */
      cur->next = cur->peer->next;
      cur->peer = NULL;
      if (cur->netmask == next->netmask) cur->netmask--;
      if (prev) prev->peer = cur;

      prev = cur;
      unless (topstart) topstart = cur;
      next = next->peer;
    } else if (cur->netmask < 32 - level) {
      if (prev) prev->peer = cur;
      prev = cur;
      unless (topstart) topstart = cur;
    }
  }
  return topstart;
}

node *
acquire_data(FILE *in, U32 *n)
{
  char buf[20];                /* "ddd.ddd.ddd.ddd/mm\n\0" */
  node *head = NULL, *cur = NULL;
  
  while (fgets(buf, 20, in)) {
#ifdef DEBUG
    char *save = strdup(buf);   /* debugging */
#endif
    node *new = string_to_node(buf);
#ifdef DEBUG
    new->a = save;
#endif
    ++*n;
    if (cur) {
      cur->next = cur->peer = new;
      cur = cur->next;
    } else {
      head = cur = new;
    }
  }

  return head;
} 

node *
new_node(U32 a)
{
  node *new = (node *) malloc(sizeof(node));
  unless (new) exit(1);         /* die */
  new->addr = a;
  new->netmask = 32;
  return new;
} 

/*  Caution: Destroys its argument */
node *
string_to_node(char *addr)
{
  U32 a;
  unsigned char *p = (char *) &a;
  unsigned i;
  node *n;

  addr = strtok(addr, ".\n");
  
  for (i=0; i<4; i++) {
    unless (addr) break;
    *p++ = (unsigned char) atoi(addr);
    addr = strtok(NULL, ".\n/");
  }
  n = new_node(a);
  if (n == NULL) return n;      /* XXX: move this up */

  n->netmask = atoi(addr);
  return n;
}