#! /usr/bin/perl
#
# IPv4アドレスブロックを可能な限り連結して出力する。
# Copyright (C) 2020 HIRAMOTO Kouji
#
# 入力: x.x.x.x/x 形式のIPアドレスブロックの一覧をprefixでソートしたもの
#  ソート例: sort -t / -k 2 -n
# 出力: x.x.x.x/x 形式のIPアドレスブロックの一覧を昇順で
# オプション: -d デバッグモード
#
#------------------------------------------------------------------------------
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# ライセンス全文: https://www.gnu.org/licenses/old-licenses/gpl-2.0.ja.html
# 日本語訳: https://licenses.opensource.jp/GPL-2.0/gpl/gpl.ja.html
#------------------------------------------------------------------------------

use strict;
use Getopt::Long;

my $Option_Debug = 0;
GetOptions("d" => \$Option_Debug);

my @A = ( [-1, -1], [2**32, 2**32] ); # 番兵を入れておく(出力の対象外)

#netmaskテーブル作成
my @PREFIX2INT = ();
my %INT2PREFIX = ();
for my $i (0 .. 32) {
    my $int = 2 ** (32 - $i);
    $PREFIX2INT[$i] = $int;
    $INT2PREFIX{$int} = $i;
}
$INT2PREFIX{0} = "sentinel";

while (<>) {
    s/^\s+//;
    s/[\s\r\n]+$//;
    if (m|^(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})(?:/(\d{1,2}))|) {
	my $ip_n = $1 * 256*256*256 + $2 * 256*256 + $3 * 256 + $4;
	my $prefix = $5;
	if (! defined $prefix || $prefix eq "") {
	    $prefix = 32;
	}
	&debug_print("#DEBUG input: %s\n", $_);
	&Process($ip_n, $prefix);
	&output_all if ($Option_Debug);
    }
    else {
	printf("# Bad input: %s\n", $_);
    }
}

&debug_print("#FINISH!\n");
&output_all;
exit 0;

sub Process
{
    my($start, $prefix) = @_;

    my $end = $start + &prefix2int($prefix) - 1;

    # 隣接も包含もしない(最小)
    if ($end + 1 < $A[1][0]) {
	splice(@A, 1, 0, [$start, $end]);
	&debug_print("#DEBUG 隣接も包含もしない(最小): %s\n", $start);
	return;
    }
    # 隣接も包含もしない(最大)
    if ($A[-2][1] + 1 < $start) {
	splice(@A, -1, 0, [$start, $end]);
	&debug_print("#DEBUG 隣接も包含もしない(最大): %s\n", $start);
	return;
    }

    # アドレスの位置を検索
    my $index_start = &binary_search(\&compare_number, $start, \@A, 0);
    my $index_end = &binary_search(\&compare_number, $end, \@A, 1);
    &debug_print("#DEBUG index_start %s index_end %s\n", $index_start, $index_end);

    # 同じ
    if ($index_start == $index_end
	&& $A[$index_start][0] == $start
	&& $A[$index_start][1] == $end) {
	&debug_print("#DEBUG 同じ: index_start %s\n", $index_start);
	return;
    }

    #始点が隣接する
    if ($index_start == $index_end
	&& $A[$index_start][1] + 1 == $start
	&& $end + 1 < $A[$index_start + 1][0]) {
	&debug_print("#DEBUG 始点が隣接する\n");
	$A[$index_start][1] = $end;
	return;
    }

    #終点が隣接する
    if ($index_start == $index_end
	&& $A[$index_start][1] + 1 < $start
	&& $end + 1 == $A[$index_start + 1][0]) {
	&debug_print("#DEBUG 終点が隣接する\n");
	$A[$index_start + 1][0] = $start;
	return;
    }

    #始点と終点が隣接する
    if ($index_start == $index_end
	&& $A[$index_start][1] + 1 == $start
	&& $end + 1 == $A[$index_start + 1][0]) {
	&debug_print("#DEBUG 始点と終点が隣接する\n");
	$A[$index_start][1] = $A[$index_start + 1][1];
	splice(@A, $index_start + 1, 1);
	return;
    }

    #隣接も包含もしない
    if ($index_start == $index_end
	&& $A[$index_start][1] < $start
	&& $end < $A[$index_start + 1][0]) {
	&debug_print("#DEBUG 隣接も包含もしない: index_start %s\n", $index_start);
	splice(@A, $index_start + 1, 0, [$start, $end]);
	return;
    }

    #包含される
    if ($index_start == $index_end + 1
	&& $A[$index_start][0] <= $start
	&& $end <= $A[$index_start][1]) {
	&debug_print("#DEBUG 包含される: %s into %s\n",
	       &start_prefix2block($start, $prefix),
	       &index2block($index_start));
	return;
    }

    print "#ASSERT\n";
    &output_all;
    exit 1;
}

sub output_all
{
    my($format, $join_str);
    if ($Option_Debug) {
	$format = "\t%s\n";
	$join_str = " , ";
    }
    else {
	$format = "%s\n";
	$join_str = "\n";
    }
    for my $i (1 .. $#A - 1) {
	printf($format, join($join_str, &index2block($i)));
    }
}

sub start_prefix2block
{
    my($start, $prefix) = @_;
    return sprintf("%s/%s", &int2ip($start), $prefix);
}

sub index2block {
    my $i = shift;
    &range2block($A[$i][0], $A[$i][1]);
}

sub int2ip
{
    my $int = shift;
    my @ip = ();
    for my $i (1..4) {
	unshift(@ip, $int & 255);
	$int >>= 8;
    }
    return join(".", @ip);
}

sub int2prefix
{
    my $int = shift;
    return $INT2PREFIX{$int};
}

sub prefix2int
{
    my $prefix = shift;
    return $PREFIX2INT[$prefix];
}

# IPアドレスレンジをprefix単位に変換する
sub range2block
{
    my($start, $end) = @_;

    if ($start > $end) {
	return ();
    }

    my $p_by_start = "sentinel";
    for my $i (0 .. 32) {
	if ($start % $PREFIX2INT[$i] == 0) {
	    $p_by_start = $PREFIX2INT[$i];
	    last;
	}
    }
    my $range = $end - $start + 1;
    my $p_by_range = "sentinel";
    for my $i (0 .. 32) {
	if ($PREFIX2INT[$i] <= $range) {
	    $p_by_range = $PREFIX2INT[$i];
	    last;
	}
    }
    my $p = "sentinel";
    if ($p_by_start < $p_by_range) {
	$p = $p_by_start;
    }
    else {
	$p = $p_by_range;
    }

    return (sprintf("%s/%s", &int2ip($start), &int2prefix($p)), &range2block($start + $p, $end));
}


#==============================================================================
# バイナリサーチを行う。
# 普通のバイナリサーチは「一致する値」のインデックスを返すが、
# この関数は IPアドレスブロックの検索用に
# $array[$i] <= $key < $array[$i+1]
# となる $i を返す。
sub binary_search
{
    my ($cmp_code, $key, $array_ref, $start_end) = @_;

    # リストのサイズを得ておく
    my $max_index = $#$array_ref;

    # 特例1: リストに値がない時
    if ($max_index < 1) {
	return -1;
    }
    # 特例2: リストの最小値より小さい時
    if ($cmp_code->( $key, $array_ref->[0][$start_end] ) == -1) {
	return -1;
    }
    # 特例3: リストの最大値より大きい時
    if ($cmp_code->( $key, $array_ref->[-1][$start_end] ) >= 0) {
	return $max_index;
    }

    # 実際にサーチする
    my $low  = 0;
    my $mid  = undef;
    my $high = $max_index;
    while ( $low <= $high ) {
        $mid = int( $low + ( ( $high - $low ) / 2 ) );
	# $key < $array[$mid] →目的のアドレスブロックはもっと小さい方
	if ($cmp_code->( $key, $array_ref->[$mid][$start_end] ) < 0) {
	    $high = $mid - 1;
	}
	# $array[$mid] <= $key < $array[$mid] →ちょうど合致
	elsif ($cmp_code->( $key, $array_ref->[$mid+1][$start_end] ) < 0) {
	    last;
	}
	# $array[$mid] <= $key →目的のアドレスブロックはもっと大きい方
	else {
	    $low = $mid + 1;
	}
    }
    return $mid;
}

# 数値を比較する
sub compare_number
{
    my($x, $y) = @_;
    return ($x <=> $y);
}

sub debug_print
{
    return if (! $Option_Debug);
    my $format = shift;
    my @args = @_;
    printf($format, @args);
}