/* Range2subnet. Author: Warren Toomey wkt@csadfa.cs.adfa.oz.au */

#include <stdio.h>
#include <string.h>
#define min(a,b) ((a) <= (b) ? (a) : (b))
#define max(a,b) ((a) >= (b) ? (a) : (b))

typedef unsigned int uint32_t;

/* A subnet can be described by a range of IP addresses,
 * or more properly as a base IP address plus a subnet size.
 */
struct subnet {
  uint32_t low;
  uint32_t high;

  uint32_t base;
  uint32_t size;

  uint32_t gateway;
  struct subnet *next;
};

struct subnet *slist;

int subbit[33] = {
  0x00000000, 0x80000000, 0xc0000000, 0xe0000000,
  0xf0000000, 0xf8000000, 0xfc000000, 0xfe000000,
  0xff000000, 0xff800000, 0xffc00000, 0xffe00000,
  0xfff00000, 0xfff80000, 0xfffc0000, 0xfffe0000,
  0xffff0000, 0xffff8000, 0xffffc000, 0xffffe000,
  0xfffff000, 0xfffff800, 0xfffffc00, 0xfffffe00,
  0xffffff00, 0xffffff80, 0xffffffc0, 0xffffffe0,
  0xfffffff0, 0xfffffff8, 0xfffffffc, 0xfffffffe,
  0xffffffff
};

/* Insert the subnet entry in order into the list */
void prepend(struct subnet *s)
{
  struct subnet *last, *this;

  s->next = NULL;
  if (slist == NULL) slist = s;
  else {
    for (this = last = slist;
	 this && (s->low > this->high); last = this, this = this->next) ;

    if (last == this) slist = s;
    else last->next = s;
    s->next = this;
  }
}

/* Convert an uint32_t address into
 * a dotted decimal string
 */
char *addrtoa(addr)
  uint32_t addr;
{
  static char buf[80];
  char *a;

  a = (char *) &addr;
  /* Pretend it's a char array, print each char as an int */
#ifdef BIG_ENDIAN
  sprintf(buf, "%d.%d.%d.%d",
 		 a[0] & 0xff, a[1] & 0xff, a[2] & 0xff, a[3] & 0xff);
#else
  sprintf(buf, "%d.%d.%d.%d",
 		 a[3] & 0xff, a[2] & 0xff, a[1] & 0xff, a[0] & 0xff);
#endif
  return (buf);
}

/* Parse a dotted decimal string into a uint32_t.
 * Return 0 on error.
 */
uint32_t parse_dotaddr(char *str)
{
  char *a, *b, *c;
  uint32_t d[4], i;

  if (str == NULL) return (0); c = a = strdup(str); if (a == NULL) return (0);

  for (i = 0; i < 3; i++) {
    if ((b = strpbrk(a, ".")) == NULL) return (0);
    *b = '\0'; d[i] = atoi(a); if (d[i] > 255) return (0);
    a = ++b;
  }
  d[i] = atoi(a); if (d[i] > 255) return (0);

  free(c);
  return (d[0] * 16777216 + d[1] * 65536 + d[2] * 256 + d[3]);
}

/* Take a structure with low and high, and find
 * one or more subnets that will cover that
 * range. Return 1 if a single subnet fits the
 * range, or 0 otherwise. Build up a linked list
 * of subnets in slist. This function is recursive.
 */
int resubnet(s)
  struct subnet *s;
{
  struct subnet E, *N;
  uint32_t b, t, oldb, oldt, oldsize;
  int i, exact = 0;

  N = (struct subnet *) malloc(sizeof(struct subnet));
  /* Try subnet sizes from 32 downwards */
  for (i = 32; i >= 0; i--) {
    oldb = b; oldt = t; oldsize = i + 1;
    b = s->low & subbit[i]; t = b | (~subbit[i]);

    /* If an exact match, setup base/size in our subnet argument */
    if ((t == s->high) && (b == s->low)) {
      exact = 1; s->base = oldb = b; oldt = t; s->size = oldsize = i; break;
    }
    if ((t > s->high) || (b < s->low)) break;
  }

  /* Find a subnet which fits inside the range */
  N->base = N->low = max(s->low, oldb);
  N->high = min(s->high, oldt);
  N->size = oldsize;

  /* Insert N into the list of subnets */
  prepend(N);

  /* If a gap at the bottom, subnet the gap */
  if (N->low > s->low) { E.low = s->low; E.high = N->low - 1; resubnet(&E); }

  /* If a gap at the top, subnet the gap */
  if (N->high< s->high) { E.high = s->high; E.low = N->high + 1; resubnet(&E); }
  return (exact);
}

/* Take a structure with low and high, and find
 * one subnet that will cover that range. This
 * subnet may exceed the given range.
 */
void bigsubnet(s)
  struct subnet *s;
{
  uint32_t b, t;
  int i;

  /* Try subnet sizes from 32 downwards */
  for (i = 32; i >= 0; i--) {
    b = s->low & subbit[i]; t = b | (~subbit[i]);

    /* If an exact match, setup base/size in our subnet argument */
    if ((t >= s->high) && (b <= s->low)) { break; }
  }
  s->base= b; s->size= i; s->low= b; s->high=t; return;
}

void usage()
{ printf("Usage: range2subnet low_address high_address\n"); exit(1); }

void print_subnet(struct subnet *s)
{
  uint32_t d[4];
  char buf[80];
  int i;

  d[0] = (s->base >> 24) & 0xff; d[1] = (s->base >> 16) & 0xff;
  d[2] = (s->base >> 8) & 0xff;  d[3] = s->base & 0xff;

  switch ((s->size + 7) / 8) {
    case 0:
    case 1:
      sprintf(buf,"%d/%d", d[0], s->size); break;
    case 2:
      sprintf(buf, "%d.%d/%d", d[0], d[1], s->size); break;
    case 3:
      sprintf(buf, "%d.%d.%d/%d", d[0], d[1], d[2], s->size); break;
    case 4:
    case 5:
      sprintf(buf, "%d.%d.%d.%d/%d", d[0], d[1], d[2], d[3], s->size); break;
  }
  printf(buf); for (i=18-strlen(buf); i; i--) putchar(' ');
  printf("\t%s to ", addrtoa(s->low)); printf("%s\n", addrtoa(s->high));
}

int main(int argc, char *argv[])
{
  struct subnet S, *ptr;
  uint32_t swap;
  int exact;

  if (argc != 3) usage();

  S.low = parse_dotaddr(argv[1]);
  if (S.low == 0) { printf("Bad low address %s\n", argv[1]); exit(1); }

  S.high = parse_dotaddr(argv[2]);
  if (S.high==0) { printf("Bad high address %s\n", argv[2]); exit(1); }

  if (S.low > S.high) { swap = S.low; S.low = S.high; S.high = swap; }
  exact= resubnet(&S);
  if (exact == 1) printf("Your range can be expressed by a single subnet:\n\n");
  else printf("Your range can only be expressed by several subnets:\n\n");

  for (ptr = slist; ptr; ptr = ptr->next) {
  	printf("\t"); print_subnet(ptr);
  }

  if (exact == 0) {
    printf("\nAlternatively you can cover the ");
    printf("range with the single subnet:\n\n");

    bigsubnet(&S); printf("\t"); print_subnet(&S);
  }
}