#!/usr/bin/perl
'di ';
'ds 00 \"';
'ig 00 ';
;#
;# addrcomp: ip address compiler
;#
;# Translate address list into aggregated form.
;#
;# EXAMPLE
;#
;#	INPUT			OUTPUT
;#
;#	192.168.4.1		192.168.4.1
;#	192.168.4.2		192.168.4.2:255.255.255.254
;#	192.168.4.3
;#
;#	10.* !10.10.*		10.0.0.0:255.248.0.0
;#				10.8.0.0:255.254.0.0
;#				10.11.0.0:255.255.0.0
;#				10.12.0.0:255.252.0.0
;#				10.16.0.0:255.240.0.0
;#				10.32.0.0:255.224.0.0
;#				10.64.0.0:255.192.0.0
;#				10.128.0.0:255.128.0.0
;#				10.0.0.0:255.0.0.0
;#
;# Copyright (c) 1997,1998 Kazumasa Utashiro <utashiro@iij.ad.jp>
;# Internet Initiative Japan Inc.
;# 3-13 Kanda Nishiki-cho, Chiyoda-ku, Tokyo 101, Japan
;#
;# Redistribution for non-commercial purpose, with or without
;# modification, is granted as long as all copyright notices are
;# retained.  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND
;# ANY EXPRESS OR IMPLIED WARRANTIES ARE DISCLAIMED.
;#
;#
;; ($myname = $0) =~ s,.*/,,;
;;								$_=<<";#.";
Usage: $myname [-d] [-v] [-o] [files]
Options:
	-h	show this message
	-H	show manual pages
	-f #	specify format (mask, slash)
	-o	keep original data as comment line
	-d	debug option
	-v	print bitmap output for debug purpose
;#.
;; ($usage = $_) =~ s/(^|\n);# ?/\1/g;
;; $rcsid = '$Id: addrcomp,v 1.4 1998/01/26 08:32:00 utashiro Exp $'
;######################################################################
;#
;# &usage2opts: Generate getopts string from usage
;#
sub usage2opts {
    local($_, $opts) = shift;
    while (/(^|\n)\t-(\w)(\t|\s\s)?/g) {
	$opts .= $2 . ($3 ? '' : ':');
    }
    $opts;
}
require 'getopts.pl';
sub usage { print $usage, "\n$rcsid\n"; exit 1; }
&Getopts(&usage2opts($usage)) || &usage;
&usage if $opt_h;
$opt_H && do { exec "nroff -man $0|".($ENV{'PAGER'}||'more')." -s"; };
;######################################################################

while (<>) {

    @deny = ();

    unless (/^\d{0,32}$/) {
	print "#\t", $_ if $opt_o;
	s/\s+$//;
	$line = $_;
	s/^\s+//;
	while (s/\s*!([\d.\*:\/{}\-,]+)$//) {
	    $deny = $1;
	    unshift(@deny, &translate_addr($deny));
	}
	unless (defined($_ = &translate_addr($_))) {
	    die "Illegal input at line $.: $line\n";
	}
    }

    &debug("INPUT : %s (%s)\n", $_, $line);

    if (@deny) {
	for $x (&complement_list($_, @deny)) {
	    &output($x);
	}
	next;
    }

    if (defined($top = $stack[$#stack])) {
	if (substr($_, 0, length($top)) eq $top) {
	    warn "Possibly duplication at line $.: $line\n";
	    next;
	}
	($top =~ /0$/) ? $prefix = $` : die 'panic';
    }
    if (/1$/) {
	if (defined($top) && ($` eq $prefix)) {
	    &debug("AGRGT : %s-%s\n", $stack[$#stack], $_);
	    chop($_);
	    pop(@stack);
	    redo;
	}
	&clearstack;
	&output($_);
    } else {
	if (defined($top) && ((substr($_, 0, length($prefix)) ne $prefix)
		     || (substr($_, length($top)) =~ /1/))) {
	    &clearstack;
	}
	&debug("PUSH  : %s\n", $_);
	push(@stack, $_);
    }
}

&clearstack;

;######################################################################

sub clearstack {

    &debug("CLEAR :\n");
    while (defined($stack = shift(@stack))) {
	&output($stack);
    }
}

sub translate_addr {
    local(@addr_list) = @_;
    local($_);
    local(@addr);
    local($masklen);

    while ($_ = shift(@addr_list)) {

	$masklen = 32;

	if (/{((\d+|\d+-\d+|,)+)}/) {
	    local($pre, $xxx, $post) = ($`, $1, $');
	    while ($xxx =~ s/[,]*(\d+)(-(\d+))?[,]*//) {
		if ($3) {
		    for ($x = $3; $1 <= $x; $x--) {
			unshift(@addr_list, $pre . $x . $post);
		    }
		} else {
		    unshift(@addr_list, $pre . $1 . $post);
		}
	    }
	    next;
	}

	# Handle asterisk (e.g. 192.168.*)
	if (/^((\d+\.){0,3})\*$/) {
	    $c = tr/\./\./;
	    $_ = sprintf("%s%s:%d.%d.%d.%d",
			 $1, join('.', ('0') x (4 - $c)), (255) x $c, (0) x 3);
	}
	# Handle slash (192.168/24)
	if (s!/(\d+)$!!) {
	    $masklen = $1;
	}
	# Handle mask (192.168.0.0:255.255.0.0)
	elsif (s/:(\d+\.\d+\.\d+\.\d+)$//) {
	    $maskbits = &bitstr($1);
	    unless ($maskbits =~ /^(1+)(0*)$/) {
		return undef;
	    }
	    $masklen = length($1);
	}

	$_ .= '.0.0.0'   if /^\d+$/;
	$_ .=   '.0.0'   if /^\d+\.\d+$/;
	$_ .=     '.0'   if /^\d+\.\d+\.\d+$/;
	return undef unless /^\d+\.\d+\.\d+\.\d+$/;

	$_ = &bitstr($_);

	if ($masklen != 32) {
	    $_ = substr($_, 0, $masklen);
	}
	push(@addr, $_);
    }

    return wantarray ? @addr : $addr[$[];
}

sub complement_list {
    local($_, @deny) = @_;

    for $deny (@deny) {
	return undef if length($_) > length($deny);
	$deny = substr($deny, length($_));
    }
    &_c($_, sort {length($a) <=> length($b)} @deny);
}

sub _c {
    local($m, @e) = @_;
    local(@x);

    return $m if @e == 0;
    return () if $e[$[] eq '';
    (&_c($m.'0', grep(s/^0//, @x=@e)), &_c($m.'1', grep(s/^1//, @x=@e)));
}

sub output {
    local($_) = @_;
    local($maskbits, $masklen);

    if ($opt_v) {
	printf "#\t%s%s\n", $_, '.' x (32 - (length($_)));
    }
    if (length($_) < 32) {
	$maskbits = ('1' x length($_)) . ('0' x (32 - length($_)));
    }
    $_ .= '0' x (32 - length($_)) if length($_) < 32;
    print &strbit($_);

    if ($maskbits) {
	if ($opt_f eq 'slash') {
	    $masklen = ($maskbits =~ tr/1/1/);
	    print "/$masklen";
	} else {
	    print ':', &strbit($maskbits);
	}
    }

    print "\n";
}

sub bitstr {
    local(@a) = split(/\./, $_[0]);
    unpack('B32', pack('N', ($a[0]<<24) + ($a[1]<<16) + ($a[2]<<8) + $a[3]));
}

sub strbit {
    local($_) = @_;

    /(\d{8})(\d{8})(\d{8})(\d{8})/ || die $_;
    sprintf("%d.%d.%d.%d",
	    unpack('C', pack('B8', $1)),
	    unpack('C', pack('B8', $2)),
	    unpack('C', pack('B8', $3)),
	    unpack('C', pack('B8', $4)));
}

sub debug {
    printf @_ if $opt_d;
}

######################################################################
.00 ;			# finish .ig

'di			\" finish diversion--previous line must be blank
.nr nl 0-1		\" fake up transition to first page again
.nr % 0			\" start at page 1
'; __END__ ############# From here on it's a standard manual page ####
.de XX
.ds XX \\$4\ (v\\$3)
..
.XX $Id: addrcomp,v 1.4 1998/01/26 08:32:00 utashiro Exp $
.TH ADDRCOMP 1 \*(XX
.SH NAME
addrcomp \- address compiler
.SH SYNOPSIS
addrcomp
[\-[hHodv]] [\-f \fIformat\fP]
[\fIfilename\fP]
.SH DESCRIPTION
.I Addrcomp
is a filter to translate the list of ip addresses to aggregated form.
Input address list:
.nf

	192.168.4.1
	192.168.4.2
	192.168.4.3

.fi
will be translated to following form.
.nf

	192.168.4.1
	192.168.4.2:255.255.255.254

.fi
.PP
Addresses can described in several syntaxes.
.nf

	192.168.1.1
	192.168.4.0:255.255.254.0
	192.168.4.0/23
	192.168.*

.fi
.PP
Also it understands the negative notation start with ! following
address range.  So if you want to exclude 10.10.10.* subnet from
overall 10.* network, it can be described as
.nf

	10.* !10.10.*

.fi
and the output will be complex affirmative address list like follwing:
.nf

	10.0.0.0:255.248.0.0
	10.8.0.0:255.254.0.0
	10.11.0.0:255.255.0.0
	10.12.0.0:255.252.0.0
	10.16.0.0:255.240.0.0
	10.32.0.0:255.224.0.0
	10.64.0.0:255.192.0.0
	10.128.0.0:255.128.0.0

.fi
Exclude address is supporting scattered address like this.
.nf

	192.168.4/24 !192.168.4.{95,96,99-158,201-255}
	192.168/16 !192.168.{0-7}.*

.fi
.SH OPTIONS
.IP "\-f \fIformat\fP"
Specify the format of address description.  If \fIformat\fP is "mask"
or this option is omitted, aggregated address range is described in
\fBaddress:mask\fP notation.  If \fIformat\fP is "slash", the output
will be like \fBaddress/masklen\fP;
.IP \-d
Debug option.
.IP \-o
Print original input line along with converted line.  Original line is 
start with # character.
.IP \-v
Print address bitmap for debugging.
.SH BUGS
Input address list should be sorted.
.SH AUTHOR
.nf
Kazumasa Utashiro <utashiro@iij.ad.jp>
Internet Initiative Japan Inc.
3-13 Kanda Nishiki-cho, Chiyoda-ku, Tokyo 101, Japan
.fi
.ex