PHP Find IP Range Overlap [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

need an algorithm for collapsing netblock ranges into lists of superset ranges

In PHP, I have a file with IPs in the following format:

1. x.x.x.x (single 开发者_如何学编程ip)
2. x.x.x.x/x (CIDR)
3. x.x.x.x-x.x.x.x (ip range)

where each x is 0 to 255.

I would like to make a PHP file to optimize this into a list of IP ranges with the least number of ranges possible (join overlapping entries).

---

The first part, getting a unique set of IP ranges can be done like so (note: there is no checking for valid data)

function cidrToIps($cidr) {
    list($base, $bits) = explode('/', $cidr);
    list($a, $b, $c, $d) = explode('.', $base);
    $i = ($a << 24) + ($b << 16) + ($c << 8) + $d;
    $mask = $bits == 0 ? 0 : (~0 << (32 - $bits));
    return array_map('long2ip', range($i & $mask, $i | (~$mask & 0xFFFFFFFF)));
}

function rangeToIps($range) {
    list($ip1, $ip2) = explode("-", $range);
    $ip1int = ip2long($ip1);
    $ip2int = ip2long($ip2);
    return array_map('long2ip', range($ip1int, $ip2int));
}

$all_ips = array();

function processLine($line) {
    global $all_ips;
    $line = trim($line);
    $ipRex = "[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}\.[0-9]{1,3}"; 
    if (preg_match("#^".$ipRex."/[0-9]{1,2}$#", $line)) {
        $all_ips = array_merge($all_ips, cidrToIps($line));
    } elseif (preg_match("#^".$ipRex."-".$ipRex."$#", $line)) {
        $all_ips = array_merge($all_ips, rangeToIps($line));
    } else {
        $all_ops[] = $line;
    }
}

$lines = array('192.168.9.0/22', '192.168.8.45', '192.168.10.10-192.168.10.99');

foreach ($lines as $line) {
    processLine($line);
}

$filtered_ips = array_unique($all_ips);

I'll leave the rest of it (converting it back into ranges, cidrs and ip addresses) to you.