[SOLVED] Help needed to compress ip address ranges

[WoodsyDotOrg]

I've googled til my brain went boom... So the short story goes; I have lots of ip address ranges in multiple files which need to go into an iptables firewall... Sounds simple right?

Example of files:
1.0.1.0-1.0.1.255
1.0.1.0-1.1.0.255
1.0.2.0-1.0.3.255
1.0.4.0-1.0.7.255
1.0.8.0-1.0.15.255
1.0.16.0-1.0.31.255
1.0.32.0-1.0.63.255
1.0.64.0-1.0.127.255
1.0.128.0-1.0.255.255
1.1.0.0-1.1.0.255

I have stripped/parsed them, checked the syntax uniq'd and dumped into a central file which happens to be about 2 meg.

But as you can see, there are considerable overlaps.
The above can ultimately be compressed into one line alone. 1.0.1.0-1.1.0.255

Normally I would'nt care but unfortunately the limited ram/cpu resources on the firewalls have made it imperative that I optimise these lists.

So my question is: How can I evaluate/compress the above 10 lines into one on a shell?

I don't care how dirty the code is! :]

Now for sanity sake I've decided that converting all these IP's to decimal will make this task quite a lot easier.

Perl helped there...
print unpack('N', pack('C4', split(/\./, $ARGV[0])));
and reversed
print join('.', unpack('C4', pack('N', $ARGV[0])));

Above list becomes:
16777472-16777727
16777472-16843007
16777728-16778239
16778240-16779263
16779264-16781311
16781312-16785407
16785408-16793599
16793600-16809983
16809984-16842751
16842752-16843007

Now I'm stuck...

Any help would be greatly appreciated.

[Rubberman]

Please explain what you are trying to accomplish. Saying "put these into an iptables firewall" isn't particularly helpful. FWIW, 1.x.x.x IP addresses are class A addresses. Are you simply using that as an example, or are you REALLY trying to filter such an address?

[Kloschüssel]

I would propose this as a general algorithm:

* sort the list
* check / merge a line with the line below it if it overlaps

After that you should have a compressed address range. For sorting the file, you have the "sort" command. Thinking of a object oriented fashion, I would instantiate a class "AddressRange" that implements the method "bool Overlaps(AddressRange)" and "AddressRange Join(AddressRange)".

So, likewise in pseudocode:

sorted=sort < input
lastline=""
while read line < $sorted
do
   if [ -z $lastline ] then
      lastline = line
   else
      if [ check $lastline $line ]
      then
         lastline=merge $lastline $line
      else
         lastline=$line
         # no merge, put it to output
         echo $lastline
      fi
    fi
done
# output the remainder
echo $lastline

[WoodsyDotOrg]

Have found various solutions.

#!/bin/bash
cat numberlist.txt | tr "-" " " |
while read min max ; do
        seq $min $max
done | 
sort -n -u | (cat - && echo "done") |
while read ip ; do
  if [ -z "$min" ] ; then
    min=$ip
    max=$ip
  else
    if [ $ip = "done" ] ; then
      echo "$min-$max"
      break
    else
      if (($ip - 1 == $max)) ; then
        max=$ip
      else
        echo "$min-$max"
        min=$ip
        max=$ip
      fi
    fi
  fi
done

OR

#!/usr/bin/env ruby -w

if ARGV.size != 1
  puts "Usage: #{$0} [file]"
  exit
else
  inputfile=ARGV[0]
end
require 'ipaddr'
def to_range(a)
  r=[];s=a[0]
  a.each_cons(2) do |a|
    if a[1]-a[0]!=1
        r<<["#{s}-#{a[0]}"]
        s=a[1]
    end
  end
  left=a.index(s)
  r<<["#{a[left..-1][0]}-#{a[left..-1][-1]}"]
end

def dec2ip(dec) return IPAddr.new(dec, Socket::AF_INET).to_s end

def ip2dec(ip) return IPAddr.new(ip).to_i end

consolidate=[]
ips = File.open(inputfile).read.gsub(/\n/," ").split
ips.each do |x|
  one,two = x.split("-")
  consolidate<< (ip2dec(one)..ip2dec(two)).to_a
end
to_range(consolidate.flatten.sort.uniq).each do |w|
  s,e = w[0].split("-")
  print "#{dec2ip(s.to_i)} - #{dec2ip(e.to_i)}\n"
end

OR

#!/usr/bin/awk -f

BEGIN{  FS="[.|-]"
        OFS="."
}

NR==1{
    for(i=1;i<=NF;i++)
        ip[i]=$i
}

NR>1{
    for(x=1;x<=4;x++){
        if(ip[x] < $x)
            break       
        if(ip[x] > $x)
            for(;x<=4;x++)
                ip[x]=$x        
    }   

    for(y=5;y<=8;y++){
        if(ip[y] > $y)
            break       
        if(ip[y] < $y)
            for(;y<=8;y++)
                ip[y]=$y        
    }   
}

END{
    print "start ip is : "ip[1],ip[2],ip[3],ip[4]
    print "end ip is : "ip[5],ip[6],ip[7],ip[8]
}

For continued reading - linuxquestions.org/questions/programming-9/help-needed-to-compress-ip-address-ranges-833156/]Help needed to compress ip address ranges

Thanks