#!/usr/bin/perl

#
# The name of the file containing the data is specified as an argument.
# Alternatively, the data may passed via STDIN.
# The data consist of mulitple records, one per line.
# Each record has two columns: a network address and its mask.
# The columns are seperated by whitespace.
# Lines containing only whitespace are ignored.
# Comments (anything after a "#") are ignored.
#
# 
# Example
# -------
# # This is a sample data file.
#
# 10.0.0.0   255.255.255.0     # Overlaps with 4, 5 & 6
# 10.0.0.0   255.255.255.128   # Overlaps with 5 & 6
# 10.0.0.0   255.255.255.192
# 10.0.0.64  255.255.255.192
#
# 11.0.0.0   255.255.255.0
# 11.0.1.0   255.255.255.0
# 11.0.2.0   255.255.254.0     # Overlaps with 11
# 11.0.3.0   255.255.255.0
# 11.0.4.0   255.255.255.0
#
# 12.0.0.0   255.255.255.0     # Overlaps with 15
# 12.0.0.1   255.255.255.0
#

use strict;
use warnings;


sub packip4   { return unpack('N', (pack 'C4', split(/\./, shift))); }
sub unpackip4 { return join('.', unpack('C4', pack('N', shift))); }


sub format_rec {
   my $rec = @_ ? $_[0] : $_;
   return sprintf('%s/%s (line %d)',
      unpackip4($rec->[0]),
      unpackip4($rec->[1]),
      $rec->[2],
   );
}


sub overlap {
   my ($overlaps, $r1, $r2) = @_;
   if ($r1->[2] > $r2->[2]) {
      ($r1, $r2) = ($r2, $r1)
   }
   push @$overlaps, [ $r1, $r2 ];
}


{
   my @recs;

   {
      while (<>) {
         s/#.*//;
         s/\s+\z//;
         next if !length;

         my ($net, $mask) = split /\s+/;
         $net  = packip4($net);
         $mask = packip4($mask);

         my $first = $net & $mask;
         my $last  = $net | ~$mask;

         push @recs, [ $first, $last, $. ];
      }
   }


   my @overlaps;

   if (@recs) {
      @recs = sort { $a->[0] cmp $b->[0] || $a->[1] cmp $b->[1] } @recs;

      my $crushed = shift @recs;
      my @components = ( $crushed );

      while (@recs) {
         my $rec = shift @recs;

         if ($rec->[0] gt $crushed->[1]) {
            $crushed = $rec;
            @components = ( $rec );
            next;
         }

         foreach my $component (@components) {
            next if $component->[0] gt $rec->[1]
                 || $component->[1] lt $rec->[0];
            overlap(\@overlaps, $rec, $component);
         }

         $crushed = [
            $crushed->[0],
            ( $crushed->[1] gt $rec->[1] ? $crushed->[1] : $rec->[1] )
         ];
         push @components, $rec;
      }
   }


   print map { sprintf("%s overlaps %s\n", map format_rec, @$_) }
         sort { $a->[0][2] <=> $b->[0][2] || $a->[1][2] <=> $b->[1][2] }
         @overlaps;
}