IPV4 subnet list cleaner (in CIDR notation)

Question

We have a lot of IPV4 address, to group into subnets, so we need a tool for doing this:

Our list is very ugly, not ordered and sometime in subnet notation, sometime in simple address.

Sample:

192.168.5.16/30
192.168.5.18
192.168.2.231/27
192.173.17.0/24
192.168.1.5/32
192.168.5.18/32
192.168.3.0/24
192.168.2.231/27
192.168.2.245/29
192.168.4.0/29
192.173.16.0/24
192.173.18.0/24
192.173.19.0/24
10.100.12.24

some explanation about the input (our old list):

• each line hold only 1 IPV4 subnet
• if a line don't contain any subnet info like on line 2, it's a single ip, so the 32 bit mask is to be considered.
• subnet info is in the CIDR form: IPV4/integer where integer is mask length
• IPV4 is not necessarely the base (first in range) of subnet
• list is not sorted
• list is not short... could make more the 60k entries...
• there is repetition, overlap of subnets... lot of useless lines

( The last is the main reason we need to build this tool! ;-)

From this sample list we want to obtain shortened, sorted and cleaned list like:

10.100.12.24/32
192.168.1.5/32
192.168.2.224/27
192.168.3.0/24
192.168.4.0/29
192.168.5.16/30
192.173.16.0/22

Where all lines is subnet and all IPV4 part is base IP (begin of range), sorted, and without overlap or repetitions.

And where all IP present somewhere in input is present and no one more!

CIDR

For informations about:

• Subnetting http://en.wikipedia.org/wiki/IPv4_subnetting_reference
• CIDR notation http://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing#CIDR_notation

Code golf

• Input values could be given as you will, (arguments, read from file or STDIN)
• Output to STDOUT, one subnet per line.
• Output has to be sorted by the unsigned integer value of IPV4 (big-endian)
• Output has to contain as few lines as possible
• Of course, sum of output subnet must match sum of input subnet! no more, nor less! So 0.0.0.0/0 which override everything is not accepted! (unless it's the only valid answer, see last test)
• Use of libraries forbiden! Standard loophole applies
• Shortest code wins!

Test cases

For testing this, (under bash) I use something like:

for i in {167772416..167774464};do
     echo $[i>>24].$[i>>16&255].$[i>>8&255].$[i&255]
  done

as input, this must render:

10.0.1.0/24
10.0.2.0/23
10.0.4.0/22
10.0.8.0/24
10.0.9.0/32

or

for i in {167772416..167774464};do
     [ $i -gt 167773316 ] && [ $i -lt 167773556 ] ||
         echo $[i>>24].$[i>>16&255].$[i>>8&255].$[i&255]/30
  done

Note, I've added /30 after each ip. this will do a lot of overlap!

10.0.1.0/24
10.0.2.0/23
10.0.4.0/25
10.0.4.128/29
10.0.5.116/30
10.0.5.120/29
10.0.5.128/25
10.0.6.0/23
10.0.8.0/24
10.0.9.0/30

Extreme test rule

63.168.3.85/2
64.168.3.85/2
192.168.3.85/2
191.168.3.85/2

This special case must render:

0.0.0.0/0

Accepted answers

As this question seem not so easy, I will add time from question to the list

1. CJam, 101 - user23013 - 38 hours
2. Perl, 223 - nutki - 1 week
3. Pure bash, 1040 - F.Hauri - 4 days

Answer 1

CJam, 101 95 94

qN/{'//('./1\+256b2b\{i)<}/}%_|{{):T;_aM+:M(a&}gT+}%${_2$#!{;}*}*]{_(!a32*+32<8/2fb'.*'/@,(N}%

The {~}2j construct didn't make it shorter...

Try it here. (And link for Firefox.)

Explanation

qN/               " Read each line. ";
{                 " For each line: ";
    '//           " Split by / ";
    ('./          " Split first item by . ";
    1\+256b2b     " The address + 2^32 in base 2, which always has length 33 ";
    \{i)<}/       " For each other items N (if any), get the first N+1 bits. ";
}%
_|                " Remove duplicates. ";
{                 " For each item (each array of bits): ";
    {             " Do: ";
        ):T;      " Remove last bit and save it in T. ";
        _aM+:M    " Add the array to M. ";
        (a#)      " Find the array in the original M. ";
    }g            " while it is found. ";
    T+            " Append the last T back. ";
}%
$                 " Sort. ";
{                 " Reduce and wrap in array: ";
    _2$#!         " Test if the previous string is a prefix of the current. ";
     {;}*         " If so, discard it. ";
}*]
{                 " For each item (each array of bits): ";
    _(!a32*+32<   " Remove first bit and pad to 32 bits to the right. ";
    8/2fb'.*      " Convert to IP address. ";
    '/@,(         " Append / and original length - 1. ";
    N             " Append a newline. ";
}%

Answer 2

Perl, 172 223 245

Using hashes was not necessary. The removal allowed for a significantly shorter code, though the idea is the same.

#!perl -lp0a
$_=join$\,sort map{1x(s/\d*./unpack B8,chr$&/ge>4?$&:32)&$_}@F;1while s/^(.*)
\1.*/$1/m||s/^(.*)0
\1.$/$1/m;s!^.*!(join'.',map{ord}split'',pack B32,$&).'/'.length$&!gme

Test me.

Older version with explanation:

#!perl -lp0a
s/(^|\.)(\d+)/sprintf"%08b",$2/ge,/\D/&&($_=$`|2x$',y/0-3/##01/)for@F;$_=join$\,sort@F;1while s/^((\d*)#*)
\2.*/$1/mg||s/^(\d*)0(#*)
\1[1]\b#*/$1#$2/mg;s!.+!$&.'/'.$&=~y/01//!ge;y/#/0/;s!\d{8}\B!$&.!g;s!\d{8}!"0b$&"!gee

Test me.

First convert input to textual format (s/(^|\.)(\d+)/sprintf"%08b",$2/ge,/\D/&&($_=$p|2x$',y/0-3/##01/)):

00##############################
01##############################
11##############################
10##############################

Sort it ($_=join$\,sort@F):

00##############################
01##############################
10##############################
11##############################

Clean using two regexps: one to remove duplicates and more specific addresses and the second to join two adjacent networks into one with a longer mask (s/^((\d*)#*)\n\2.*/$1/mg and s/^(\d*)0(#*)\n\1[1]\b#*/$1#$2/mg).

################################

And convert back to the original form (s!.+!$&.'/'.$&=~y/01//!ge;y/#/0/;s!\d{8}\B!$&.!g;s!\d{8}!"0b$&"!gee):

0.0.0.0/0

Answer 3

Ruby - 425

(broken - see comment below)

a=(0..32).map{[]}
l=->m{2**m-1<<32-m}
$<.map{|i|/\//=~i=i[?/]?i:i.chop+'/32'
s=$'.to_i
n=$`.split(?.).inject(0){|v,d|v*256+d.to_i}
next if s.times.any?{|t|a[t].any?{|e|n&l[t]==e[1]}}
s.upto(32){|t|a[t].reject!{|e|e[1]&l[s]==n}}
a[s]<<[i,n]
(b=k=n&l[s]
break if(y=a[s+1].select{|e|e[1]&l[s]==b}).size<2
a[s+1]-=y
a[s]<<[(0..3).map{k,i=k.divmod(256);i}.reverse*?.+?/+s.to_s,b])until(s-=1)<0}
puts a.flatten(1).sort_by{|v|v.pop}

Answer 4

Pure bash 1100 1079 1040

Edited: A little better more golfed!

#!/bin/bash -i
alias d=done e=unset f=printf\ -v g=local h=else i=then j=for k=while C=do E=fi
n(){ g s e i;j i in ${!u[@]};C [ $1 -ge $[i+1] ]&&[ $1 -le $[u[i]+1] ]&&s=$i
[ $2 -ge $[i-1] ]&&[ $2 -le $[u[i]-1] ]&&e=$i;d;if [ "$s" ];i if [ "$e" ];i \
[ $s -ne $e ]&&{ u[s]=${u[e]};e u[e];};h [ $1 -lt $s ]&&{ u[$1]=${u[s]};e u[s
];s=$1;};[ $2 -gt ${u[s]} ]&&u[s]=$2;E;h if [ "$e" ];i [ $1 -lt $e ]&&{ u[$1
]=${u[e]};e u[e];e=$1;};[ $2 -gt ${u[e]} ]&&u[e]=$2;h u[$1]=$2;E;E;};q(){ 
g s=${1#*/} m=${1%/*} z;[ -z "${s//*.*}" ]&&s=32;y $s z;set -- ${m//./ }
m=$[$1<<24|$2<<16|$3<<8|$4];n $[m&z] $[m|((2**32-1)^z)];};y(){ f $2 "%u" $[ (
2**32-1)^(~0^~0<<(32-$1))];};r(){ f $2 "%s" $[$1>>24].$[$1>>16&255].$[$1>>8&
255].$[$1&255];};t(){ g s z;k [ "$1" ];C s=32;k y $[s-1] z&&[ $1 = $[($1>>(33
-s))<<(33-s)] ]&&[ $2 -ge $[$1|((2**32-1)^z)] ];C ((s--));d;r $1 x;echo $x/$s
y $s z;if [ $2 -gt $[$1|((2**32-1)^z)] ];i set -- $[1+($1|((2**32-1)^z))] $2
h shift 2;E;d;};k read w;C q $w;d;p=-1;j o in ${!u[@]};C [ $o -gt $p ]&&p=${u[
o]}&&t $o ${u[o]};d

which work quickly, even on wide ranges!

./myscript.sh <<<"63.168.3.85/2\n64.168.3.85/2\n192.168.3.85/2\n191.168.3.85/2"
0.0.0.0/0

./myscript.sh < <(for i in {167772416..167774464};do
     [ $i -gt 167773316 ] && [ $i -lt 167773556 ] ||
         echo $[i>>24].$[i>>16&255].$[i>>8&255].$[i&255]/30
   done)
10.0.1.0/24
10.0.2.0/23
10.0.4.0/25
10.0.4.128/29
10.0.5.116/30
10.0.5.120/29
10.0.5.128/25
10.0.6.0/23
10.0.8.0/24
10.0.9.0/30

Answer 5

Javascript ~1335

While total js is 2009, the essential part is contained in two function and main routine. html, css and ~674 chars of javascript in only cosmetic.

var g={};function B(){document.getElementById('z').addEventListener('click',go);
window.addEventListener('resize',C);C();}function C(){document.getElementById('y'
).setAttribute('style','height:'+(window.innerHeight-46-document.getElementById(
'y').offsetTop).toFixed(0)+"px");document.getElementById('x').setAttribute(
'style','height:'+(window.innerHeight-46-document.getElementById('x').offsetTop
).toFixed(0)+"px");}function go(){document.getElementById('y').innerHTML='';
document.getElementById('A').innerHTML='...running...';w()
}function u(q,j){var o=Object.keys(g).sort(function(a,b){return a-b}),s,e;for(var
i=0;i<o.length;i++){if((q*1>=o[i]*1+1)&(q<=g[o[i]]*1+1))s=1*o[i];if((j*1>=o[i]-1
)&(j<=g[o[i]]-1))e=1*o[i]};if(typeof(s)!=='undefined'){if(typeof(e)!=='undefined'
){if(1*s<1*e){g[s]=g[e];delete g[e]}}else{if(1*q<1*s){g[q]=g[s];delete g[s];s=q};
if(1*j>1*g[s])g[s]=j}}else{if(typeof(e)!=='undefined'){if(1*q<1*e){g[q]=g[e];
delete g[e];e=q};if(1*j>1*g[e])g[e]=j}else{g[q]=j}}}function v(f,p){var e,ie,c=''
;while(typeof(f)!=='undefined'){e=32;while((ie=(~0<<(33-e))>>>0)&&(f==((f>>(33-e)
)<<(33-e))>>>0)&&(p>=(((~0<<32)^ie)|f)>>>0)&&(e>0))e--;c+=(f>>24&255)+"."+(f>>16&
255)+"."+(f>>8&255)+"."+(f&255);c+='/'+e+'<br/>';ie=e>0?(~0<<(32-e))>>>0:0;if(p>(
(f|(~0<<32)^ie))>>>0){var d=f;f=1*1+((f|((~0<<32)^ie))>>>0)}else{f=undefined}}
return c}function w(){var l=[];g={};document.getElementById('A').innerHTML+=
'<br/>reading...';var n=document.getElementById('x').value.split("\n");for(var
i=0;i<n.length;i++){if(!n[i].match("/"))n[i]+="/32";var s=n[i].match(
/(\d+)\.(\d+)\.(\d+)\.(\d+)\/(\d+)/);if((s)&&(s.length==6)){var k=(s[1]<<24|s[2]
<<16|s[3]<<8|s[4])>>>0;var e=(~0<<(32-s[5]))>>>0;var t=(~0&k&e)>>>0;var r=(((~0
<<32)^e)|t)>>>0;u(t,r);}};var o=Object.keys(g).sort(function(a,b){return a-b});
var h=-1;for(i=0;i<o.length;i++){if(1*o[i]>1*h){h=g[o[i]];document.getElementById
('y').innerHTML+=v(o[i],g[o[i]]);}}document.getElementById('A').innerHTML+=
'<br/>printing...'};window.onload=B;

body{font-family:Sans;background:#9ac;}#z{position:absolute;top:3em;right:2%;}
span button, span input{font-size:.63em;}#A{width:50%;min-height:3.4em;background:
#679;border:1px solid black;border-color:white black black white;border-radius:
.5em;padding:.2em 1em .2em 1em;margin:1em 0px .1em 0px;margin-left:24%;color:
#cdf;box-shadow: 2px 2px 4px black;}#y{width:72%;overflow:auto;margin-left:24%;
background:#bce;padding:1em;border-radius:.8em;border:1px solid black;box-shadow:
2px 2px 4px;border-color:white black black white;}#x{position:fixed;top:1.5em;
left:1%;padding:1em;width:18%;anchor:left;height:33em;border-radius:.3em;border:
1px solid black;border-color:white black black white;box-shadow:2px 2px 4px;}

<button id="z"> GO </button><textarea id="x"></textarea><div id="A">---</div><pre id="y"></pre>