/* recreate a route list from bogons list
 * Copyright 2005 Michael John Wensley http://www.wensley.org.uk/
 */
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <dirent.h>
#include <unistd.h>

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

#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>

char net[44];

void router(in_addr_t, in_addr_t);
void declare(in_addr_t, int);

int main(argc, argv, envp)
int argc;
char *argv[];
char *envp[];
{
	FILE* in;
	char* next;
	unsigned char n1, n2, n3, n4, n5;
	in_addr_t top;
	in_addr_t first;
	in_addr_t last;

	top = 0;

/*	router(0xe0000000,0xf0000000);
 *	exit(0);
 */
	/* in = fopen("/tmp/data","r"); */
	in = stdin;
	while (fgets(net, sizeof(net), in)) {
		if (*net < '0') continue;
		if (*net > '9') continue;
		n1 = strtol(net, &next, 10);
		next++;
		n2 = strtol(next, &next, 10);
		next++;
		n3 = strtol(next, &next, 10);
		next++;
		n4 = strtol(next, &next, 10);
		next++;
		n5 = strtol(next, &next, 10);
		/* printf("Fields %d.%d.%d.%d/%d\n", n1, n2, n3, n4, n5); */

		/* get first and last addresses of bogon prefix... */
		first = (n1 << 24) + (n2 << 16) + (n3 << 8) + n4;
		last = first + (0xFFFFFFFF >> n5);
		
		/* hack to support /32's */
		if (n5 == 32)
			last++;

		/* create largest route that fits at top and bottom
		 * printf("Find Route %x to %x\n", top, first); */
		router(top, first);

		top = last + 1;
	}
	/* and finish off!
	 * printf("Find Route %x to %x\n", top, 0); */
	router(top, 0);
	return EXIT_SUCCESS;
}

/* 0 0 match, dec
 *
 * 0 1 - lower bits all 0 cont
 * == 0 0 route
 * == 0 N route + recurse
 * == N 0 recurse
 * == N N recurse + recurse
 *
 * 1 0 impossible, as implies dont comes before route.
 * 1 1 match, dec
 * usually contains small routes, then big routes, then small ones again...
 */
void router(in_addr_t route, in_addr_t dont) {
	/* hunt first unequal bit. 00 01 11 */

	unsigned int prefix;
	unsigned int count;
	prefix = 32;

	/* if, route this large is acceptable
	 * and this small is required.
	if (route == dont)
		return;

	/* quick fix - not needed caused by trailing empty line
	 * if (route == 0)
	 *	return;
	 */
	/* need to overflow check (32 bit integers wraparound)
	 * also cant check a zero prefix as this is div0 (there would be no routes anyways)
	 */
	while (count = 1 << (32 - prefix),
	(((route + count) < dont) && (route < dont)) ||
	(((route + count) > dont) && (route > dont)) &&
	((route + count) > 0) &&
	(prefix > 1)) {
/*		printf("Route %x, dont %x, prefix %d\n", route, dont, prefix); */

/*		printf("Check %x\n", prefix); */
		if (route % (count << 1)) {
			declare(route, prefix);
/*			printf("Add %x\n", (1 << (32 - prefix))); */
			route += count;
		} else prefix--;	/* see if a bigger route is needed */
	}
	/* here we check if a prefix consumes <= available addresses
	 */
/*	printf("More routes... begin %x\n", route); */
	while (route != dont) {
		/* if a big prefix fits, use it. */
		count = 1 << (32 - prefix);
		if ( ((route + count) <= dont) && (route < dont) || 
			((route + count) >= dont) && (route > dont)) {
			declare(route, prefix);
			route += count;
		} else prefix++; /* try a smaller route */
	}
}

void declare(in_addr_t route, int prefix) {
	printf("%d.%d.%d.%d/%d\n",
(route >> 24) & 0xFF, 
(route >> 16) & 0xFF, 
(route >> 8) & 0xFF, 
(route >> 0) & 0xFF, prefix);

}