#!/usr/bin/perl

# Filter to convert a list of IPs to a list of CIDR masked nets that
# cover the same set of IPs.  Needs a sorted list of IP addresses as
# input.  In order to sort an IP list using the standard sort utility,
# you need the following parameters:
# 	sort -t. +0n -1 +1n -2 +2n -3 +3n 
# Fun, isn't it?

#
# Binary base for different netmasks
# 
# Each entry contains either undef (we've already consumed the
# base address that was here) or a base address which has been
# matched with the corresponding netmask (as the bucket it is
# stored in)
#
# Addresses can't be promoted beyond the level where they have LSBs
# that are zero, of course.
my @nets;

sub find_cidr($) {
	my $ip = shift;
	my $i = 32;

	return 0 if $ip == 0;
	while ($ip && $i && ($ip & 1) == 0) {
		$ip >>= 1;
		$i--;
	}
	return $i;
}

sub format_ip($) {
	my $ip = shift;
	sprintf("%d.%d.%d.%d",
		$ip >> 24,
		($ip >> 16) & 255,
		($ip >> 8) & 255,
		$ip & 255);
}
# Dump the data for nets found so far, and start anew
sub dump_nets() {
	for ($i = 1; $i < 32; $i++) {
		if (defined($nets[$i])) {
			print format_ip($nets[$i]) . "/$i\n";
			$nets[$i] = undef;
		}
	}
	if (defined($nets[32])) {
		print format_ip($nets[$i]) . "\n";
		$nets[32] = undef;
	}
}

$reallastip = undef;
while (<>) {
	die "Bad input - not an IP: $_" if !/^\d+\.\d+\.\d+\.\d+$/;
	($a, $b, $c, $d) = split(/\./);
	die "Bad input - not an IP: $_"
		if $a < 0 || $b < 0 || $c < 0 || $d < 0 ||
		   $a > 255 || $b > 255 || $c > 255 || $d > 255;
	$ip = $d + 256*($c + 256*($b + 256 * $a));
	die "Unsorted input\n" if defined($reallastip) && $ip <= $reallastip;
	# Check for difference to last IP + 1 here, and if mismatch,
	# print out the last completed net
	if (defined($lastip) && $lastip+1 != $ip) {
		# We've got a non-continuity in the IP addresses - dump
		# out all the nets we've got, and re-initialize based on
		# the new recieved IP address
		dump_nets();
		$lastip = undef;
	}
	if (!defined($lastip)) {
		# Initialization case
		# If we have an IP address with an LSB of 1 and no previous
		# context, it *can't* be part of a net.  Just print it and
		# get another one.
		if ($ip & 1) {
			print;
			next;
		}
		$cidrbase = find_cidr($ip);
	} else {
		if ($cidrbase >= find_cidr($ip)) {
			dump_nets();
			$cidrbase = find_cidr($ip);
		}
	}
	$lastip = $ip;
	#
	# Store this IP as base if we have no net in the working
	#
	if (!defined($nets[32])) {
		$nets[32] = $ip;
	}

	# Iterate and look for completion of smaller and smaller netmasks
	# (larger and larger nets) being done by this IP.   Terminate when
	# a the previous half of a netmask is not available, or the IP we're
	# examining stop being the last IP in a mask.
	for ($i = 31; $i > 1; $i--) {
		$mask = (1<<(32 - $i)) - 1;
		if (($ip & $mask) != $mask || $cidrbase > $i) {
			# We're done - no more bits to match
			last;
		}
		$nets[$i] = $ip - ($ip & $mask);
		$nets[$i+1] = undef;
	}
}
dump_nets();

