converting complex netrange to cidr notation

[dino]

Hello,
basically I want to convert a netrange say:
192.168.0.0 - 192.168.1.15
to the equiv:
192.168.0.0/24
192.168.1.0/28
There are cpan modules that afaik will convert a simple range but not multiple ranges as given above
any pointers please

Regards
dino

[tye]

Interesting problem.

#!/usr/bin/perl -w
use strict;

sub output {
    my( $nLow, $cBits )= @_;
    my $ipLow= join ".", unpack "C*", pack "N", $nLow;
    print "    $ipLow/$cBits\n";
}

while(  <DATA>  ) {
    my( $ipMin, $ipMax )= split " ", $_;
    print "$ipMin - $ipMax:\n";
    my $nMin= unpack "N", pack "C*", split /\./, $ipMin;
    my $nMax= unpack "N", pack "C*", split /\./, $ipMax;
    my $bitsMin= 1;
    my $maskMin= 1;
    my $bitsMax= 1;
    my $maskMax= 1;
    while( 1 ) {
        while(  0 == ( $nMin & $maskMin )  ) {
            ( $maskMin <<= 1 ) |= 1;
            $bitsMin++;
        }
        last   if  $nMax < ( $nMin | $maskMin );
        output( $nMin, $bitsMin-1 );
        ( $nMin |= $maskMin ) += 1;
    }
    while( 1 ) {
        while(  $maskMax == ( $nMax & $maskMax )  ) {
            ( $maskMax <<= 1 ) |= 1;
            $bitsMax++;
        }
        $nMax &= ~$maskMax;
        last   if  $nMax < $nMin;
        output( $nMax--, $bitsMax-1 );
    }
}
__END__
192.168.0.0 192.168.255.255
192.168.1.17 192.168.112.26

produces:

192.168.0.0 - 192.168.255.255:
    192.168.0.0/16
192.168.1.17 - 192.168.112.26:
    192.168.1.17/0
    192.168.1.18/1
    192.168.1.20/2
    192.168.1.24/3
    192.168.1.32/5
    192.168.1.64/6
    192.168.1.128/7
    192.168.2.0/9
    192.168.4.0/10
    192.168.8.0/11
    192.168.16.0/12
    192.168.32.0/13
    192.168.112.26/0
    192.168.112.24/1
    192.168.112.16/3
    192.168.112.0/4
    192.168.96.0/12
    192.168.64.0/13

Sorry about the last half being output in the reverse order.

I haven't tested it extensively, but it feels right and works for the cases I did test.

        - tye (but my friends call me "Tye")

[dino]

Thanks,
Very useful. I made $cBits = 32 - $cbits for normal cidr.
Now the question is, does this produce the minimal set?
Regards
Dino

[tye]

Thanks for catching that I was counting the bits backward.

Yes, it produces the minimal set.

        - tye (but my friends call me "Tye")

[MeowChow]

Another interesting variant of this problem would be to find the minimal set of IP's + netmasks that cover a given range... hmm, I think a Golf outing is coming on :)

update: Actually, I think these are equivalent problems, so never mind, probably.

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print

[tye]

For a single range, the above solution is the minimal one even if you allow arbitrary masks (though I haven't rigorously proved that -- just supporting your suspicion). If you allow multiple ranges, then the problem gets much harder and it becomes possible for arbitrary masks to provide smaller solutions.

        - tye (but my friends call me "Tye")

[runrig]

Net::CIDR::Lite should be able to do this:

use Net::CIDR::Lite;

my $cidr = Net::CIDR::Lite->new(
  '192.168.0.0-192.168.1.15'
);

print "$_\n" for $cidr->list();