世界のIPアドレス割り当てリストからCIDR表記のデータを生成する

#やりたいこと
ファイアウォールで特定の国を許可or拒否させたいが、RIRが公開しているデータはそのままでは扱えないため、ファイアウォールで扱えるようにCIDR表記にしたい。

#世界のIPアドレスの割り当てリストとは
どの国・地域にどのIPアドレスを割り当てているかという情報が、RIR（[ARIN](http://ftp.arin.net/pub/stats/arin/delegated-arin-extended-latest), [RIPE NCC](http://ftp.ripe.net/pub/stats/ripencc/delegated-ripencc-extended-latest ), [APNIC](http://ftp.apnic.net/pub/stats/apnic/delegated-apnic-extended-latest ), [LACNIC](http://ftp.lacnic.net/pub/stats/lacnic/delegated-lacnic-extended-latest), [AfriNIC](http://ftp.afrinic.net/pub/stats/afrinic/delegated-afrinic-extended-latest)）で公開されています。このデータを使えば、ファイアウォールで特定の国を許可or拒否させることができそうですが、実はそううまくはいきません。なぜかというと、RIRが公開しているデータは「先頭IPアドレスから何個」というフォーマットで記述されいるからです。しかも1行が1つの **ネットワークアドレス/CIDR** という範囲に収まらず、適切に分割する必要があります。

####RIRが公開しているデータ
>hogenic|JP|ipv4|192.168.0.0|192|20110412|allocated|XXXXXX
>hogenic|JP|ipv4|192.168.0.192|512|20110412|allocated|XXXXXX
>hogenic|JP|ipv4|192.168.2.192|64|20110412|allocated|XXXXXX

たとえば2行目の 192.168.0.192|512 の場合、512個なので /23 に変換できそうですが、そうするとネットワークアドレスは 192.168.0.0 でなければなりません。192.168.0.192をネットワークアドレスにするためには 192.168.0.192/26, 192.168.1.0/24, 192.168.2.0/25, 192.168.2.128/26 の4つに分ける必要があります。
また、1行目〜3行目はよく見ると連続しているので、これは連結させた方がデータ量が少なくて済みます。

####ほしいデータ
>JP 192.168.0.0/23
>JP 192.168.2.0/24

実は自分で変換しなくても、[こちらのサイト](http://nami.jp/ipv4bycc/)で変換済みのデータを公開してくれています。このデータを使うのが手っ取り早いです。しかし、いつまで公開を続けてくれるのかわかりません。自動で変換するようにしていたら、公開が終わって突然サイトにアクセスできなくなった…、ということがないように、やはり自分の手が届くところで処理をさせたいと思って作りました。

#変換プログラム
標準入力からRIRのリストを読み込んで、標準出力にCIDR形式で出力するプログラムです。

**使い方**
```$ cat delegated-*-extended-latest | ./makecidr.php > cidrlist.txt
```

```php:makecidr.php
#!/usr/bin/php
<?php
//
// RIRのIPアドレス割り当てリストから、連続したIPアドレスを最大のCIDR表記に変換する	
//
$SPLIT_CLASS_A = true;	// class A(/8)より大きいブロックに分けない

// 標準入力からRIRの生データを読み込んで、CIDR単位に分割したデータに変換する
$data = [];
$fpr = fopen("php://stdin", "r");
while(! feof($fpr)) {
	$buff = rtrim(fgets($fpr,9999));
	$dd = explode("|", $buff);
	if ($dd[2] == "ipv4" && preg_match("/\A[A-Z]{2}\z/", $dd[1])) {
		$bkdata = split_cidr_block(ip2long($dd[3]), $dd[4], $dd[1]);
		foreach ($bkdata as $dd) {
			$data[] = $dd;	// $dataのフォーマット [ 先頭IP, bit数, 国 ]
		}
	}
}
fclose($fpr);

// IPアドレス順にソート
usort($data, function($a,$b) {
	return ($a[0] == $b[0]) ? 0 : (($a[0] < $b[0]) ? -1 : 1);
});

// 連結可能なCIDRを1つにまとめる
$last_cc = "";
$rewind_i = 0;
$datacnt = count($data);
for ($i=0; $i<$datacnt-1; $i++) {
	// 次に来るCIDRを見つける
	$j = $i + 1;
	if (! array_key_exists($i, $data)) continue;
	for ($j=$i+1; $j<$datacnt; $j++) {
		if (array_key_exists($j, $data)) break;
		if ($j == $datacnt-1) break 2;
	}
	list($ipsta1_n, $bit1, $cc1) = $data[$i];
	list($ipsta2_n, $bit2, $cc2) = $data[$j];
	if ($last_cc != $cc1) $rewind_i = $i;
	$last_cc = $cc1;
	// 連続する次のデータが存在するなら連結する
	if ($cc1 != $cc2) continue;	// 国が同じで無ければskip	
	if ($ipsta1_n + pow(2,$bit1) != $ipsta2_n) continue;	// IPが連続しれなければskip
	if (($ipsta1_n & pow(2,$bit1+1)-1) != 0) continue;	// IPがCIDR拡張後の先頭でなければskip	
	if ($SPLIT_CLASS_A && $bit1 >= 24) continue;	// class A以上は連結しない
	$expect_ipend_n = $ipsta1_n + pow(2, $bit1+1) - 1;
	$ipend2_n = $ipsta2_n + pow(2, $bit2) - 1;
	if ($ipend2_n == $expect_ipend_n) {	// 見つかったら連結して再スキャンする
		$data[$i] = [$ipsta1_n, $bit1+1, $cc1];
		unset($data[$j]);
		$i = $rewind_i - 1;
	}
}

// 結果出力
foreach ($data as $j => $dd) {
	$ip = long2ip($dd[0]);
	$cidr = 32 - $dd[1];
	$cc = $dd[2];
	echo "$cc $ip/$cidr\n";
}
exit;

// CIDRごとに分割する　再帰処理
function split_cidr_block($ipsta_n, $cnt, $cc, $data=[]) {
	global $SPLIT_CLASS_A;
	if ($cnt <= 0) {
		return $data;
	}
	$stabit = ceil(log($cnt,2));
	if ($SPLIT_CLASS_A && $stabit > 24) $stabit = 24;	// class Aを上限とする
	for ($bit=$stabit; $bit>=2; $bit--) {	// 分割可能な最大のCIDRを探す
		$bcnt = pow(2, $bit);
		if (($ipsta_n & $bcnt-1) == 0 && $cnt >= $bcnt) break;	// 見つかった場合
	}
	$data[] = [ $ipsta_n, $bit, $cc ];
	return split_cidr_block($ipsta_n+$bcnt, $cnt-$bcnt, $cc, $data);	// 残りを再帰的に処理する
}
?>
```

#プログラムの説明
最初にRIRの生データを読み込んで、全てを変数に格納します。**かなりメモリを食います**。IPアドレスを ip2long() 関数で数値に変換しています。これは便利な関数ですね。逆に long2ip() で数値からIPアドレスに変換できます。

split_cidr_block() では入力したデータの分割が必要な場合、CIDRごとに分割する関数です。

CIDRごとに分割したら、今度は連結可能なCIDRを見つけて連結していきます。/23 /23 があったら /24 にまとめます。連結できなくなるまで繰り返します。

たとえば /22 /24 /24 /23 というデータがあった場合、はじめに /24 /24 を連結して /23 を作り、作成した /23 と /23 を連結して /22 を作り、最後に /22 と /22 で /21 を作るといった感じです。プログラムの方はちょっと改善の余地がありそうですが。（とりあえず動いてるからヨシ！）

もし日本だけのデータでよければ、grepでJPだけ入力させてもよいでしょう。
```$ cat delegated-*-extended-latest | grep JP | ./makecidr.php > cidrlist-jp.txt
```
単純なテキストデータなので、awkやsedなどを使って、シェルスクリプトで必要なデータ形式に変換するのも簡単にできますね。