A script to reduce a list of CIDRs

Feed this script a list of CIDRs, and it will return a sorted list, with adjacent CIDRs reduced. For example:

1.2.2.0/24
1.2.3.0/24

=>

1.2.2.0/23

It’s also intelligent enough to do things like this:

1.2.1.0/24
1.2.2.0/24
1.2.3.0/24
1.2.4.0/24
1.2.5.0/24
1.2.6.0/24
1.2.7.0/24

=>

1.2.1.0/24
1.2.2.0/23
1.2.4.0/22

(It reduced my firewall ruleset from over 780,000 lines, to just over 9,000.)


 

#!/usr/bin/perl -w

use strict;
use Data::Dumper;

my @ips;

sub ipCmp($$) {
    my $ip1 = shift;
    my $ip2 = shift;
    my $r = ($ip1->[0] <=> $ip2->[0]);
    return $r ? $r : ($ip2->[1] <=> $ip1->[1]);
}

sub ipStr($) {
    my $i = shift;
    my @ip;
    foreach (0..3) {
        unshift @ip, $i & 0xff;
        $i >>= 8;
    }
    return join('.', @ip);
}

sub reduce($$) {
    my $start = shift;
    my $end = shift;
    my @ret;
    while ($start <= $end) {
         my $nmb = 1;
         while (1) {
            my $nm = (2 ** $nmb) - 1;
            last if (($start & ~$nm) != $start) || (($start | $nm) > $end);
            ++$nmb;
        }
        --$nmb;
        push @ret, ipStr($start) . '/' . (32 - $nmb);
        $start += 2 ** $nmb;
    }
    return @ret;        
}

print STDERR "Reading...\n";
while (<>) {
    my ($ip, $nm) = /(?:\s|^)((?:\d+\.){0,3}(?:\d+))(?:\/(\d+))(?:\s|$)/;
    next unless $ip;
    $nm = 32 unless $nm;
    my @ipa = split(/\./, $ip);
    unshift @ipa, 0, 0, 0 if @ipa == 1;
    splice @ipa, 1, 0, 0 while @ipa < 4;
    my $start = 0;
    foreach (@ipa) {
        $start = ($start << 8) | ($_ & 0xff);
    }
    my $nmb = ((2 ** $nm) - 1) << (32 - $nm);
    $start &= $nmb;
    my $end = $start | (~$nmb & 0xffffffff);
    push @ips, [ $start, $end, "$ip/$nm" ];
}

print STDERR "Sorting...\n";
@ips = sort { ipCmp($a, $b) } @ips;

print STDERR "Reducing...\n";
my $start = $ips[0]->[0];
my $end = $ips[0]->[1];
foreach my $ip (@ips) {
    if ($ip->[0] <= $end + 1) {
        $end = $ip->[1] if $ip->[1] > $end;
        next;
    }
    my @r = reduce($start, $end);
    print join("\n", @r), "\n";
    $start = $ip->[0];
    $end = $ip->[1];
}
my @r = reduce($start, $end);
print join("\n", @r), "\n";

exit 0;