#!/usr/local/bin/perl -w

use strict;
use Getopt::Std;
use Socket;

sub v4toi($);
sub v4_init($$);
sub v4_process();
sub v4_print();
sub v4_splitrange($$);
sub Usage();

use constant UINT32_MAX => 0xffffffff;

my %nets = ( '10.0.0.0/8'	=> [],
	     '172.16.0.0/12'	=> [],
	     '192.168.0.0/16'	=> [],
	   );

use vars qw/$opt_b $opt_c $opt_s $opt_q/;
Usage() unless getopts("b:c:s:q");

my $bits_limit = 32;
$bits_limit = (32 - $opt_b) if defined $opt_b;
$opt_c-- if defined $opt_c;

foreach my $n (keys %nets) { v4_init($n, \$nets{$n}); }
v4_process;
v4_print;
exit(0);

# ASCII network, reference to [$first, $count, \@array]
sub v4_init($$) {
  my ($net, $r) = @_;
  my ($first, $mask) = split /\//, $net;
  $first = v4toi($first);
  my $count = ($first | (1 << 32-$mask)-1) - $first + 1;
  my @a = (0) x $count; # array of statuses of addresses (0 - unused, 1 - used)
  $$r = [$first, $count, \@a];
}

sub v4_process() {
  my ($count, $d, $first, $found, $last, $i, $mask, $n, $net, $r, $t);

  LOOP: while(<>) {
    chomp;
    # get needed column
    $_ = (split /$opt_s/)[$opt_c] if defined($opt_c) && defined($opt_s);
    $found = 0;
    ($net, $mask) = split /\//;
    $mask = 32 unless defined $mask;

    # IP must be parseable and mask must be unsigned integer <=32
    if ($mask =~ /\D/ || $mask > 32 || !defined(inet_aton($net))) {
      warn "$net/$mask is not correct network, ignored" unless defined $opt_q;
      next LOOP;
    }
    $first = v4toi($net);
    $count = ($first | ((1 << 32-$mask)-1)) - $first + 1;

    # search for supernet
    while (($d, $n) = each %nets) {
      # threshold
      $t = $$n[0] + $$n[1];
      if ($first >= $$n[0] && $first < $t) {
	if ($first + $count > $t) {
	  warn "$net/$mask not within $d, ignored" unless defined $opt_q;
	  next LOOP;
	}
	$found = 1;
        for ($i=$first-$$n[0], $last=$i+$count-1, $r=$$n[2]; $i <= $last; $i++)
    	  { $$r[$i] = 1; }
      }
    }

    warn "$net/$mask not in valid networks, ignored"
      unless $found || defined $opt_q;
  }
}

# print out holes in each supernet
sub v4_print() {
  my ($first, $i, $n, $r, $subnet);

  foreach $n (values %nets) {
    for ($i = 0, $first = undef, $r = $$n[2]; $i < $$n[1]; $i++) {
      if ($$r[$i]) {	# used address is found
        print join ("\n", v4_splitrange($$n[0] + $first, $i - $first)), "\n"
	  if defined $first;
	$first = undef;	# there is no hole at this address
      } else { $first = $i unless defined $first; }
    }
    # the supernet is over, do we still have unfinished hole?
    print join ("\n", v4_splitrange($$n[0] + $first, $i - $first)), "\n"
      if defined $first;
  }
}

# Split plain range of IP addresses to the list of valid CIDR subnets
# Input: IPv4 as integer, range length
sub v4_splitrange($$) {
  my ($first, $len) = @_;
  my $bits;
  my @res;

  while ($len > 0) {
    for ($bits = 0; $first == ($first & UINT32_MAX << $bits+1) &&
	   $bits < $bits_limit && $len >= 1 << $bits+1; $bits++) {}
    push @res, (v4toa($first) . "/" . (32-$bits));
    $len   -= 1 << $bits;
    $first += 1 << $bits;
  }
  return @res;
}

# Convert ASCII IPv4 address to Perl integer
sub v4toi($) { return unpack "L", pack "C4", reverse split /\D/, $_[0], 4; }

# Convert Perl integer to ASCII IPv4 address
sub v4toa($) { return join '.', unpack 'C4', pack 'N', $_[0]; }

sub Usage() {
  print STDERR
    "Usage: $0 [-b bits] [-c column] [-s separator] [-q] [file ...]\n";
  exit(1);
}