2

I have a list of ip blocks like this that I obtained by stitching together different sources.

160.11.0.0/16
160.11.14.0/20
160.12.0.0/14
160.16.5.0/15
160.16.1.0/14
160.18.0.0/16
160.20.0.0/14
160.24.0.0/16
160.26.0.0/15
160.28.0.0/15
160.74.0.0/16
...

I would like to have a php function that could take in input this list and optimize it's size by removing unnecessary redundancies because the very final output of all this will be given to a software able to compare IPs and it's performances will depend of how much lines of input it will get (the shorter the list, better will be software performances).

My code would be something like:

$input_array = file("list.txt");
$output_array = optimize_ipblocks($input_array);
file_put_contents(implode("\n", $output));

This optimize_ipblocks function should be able to:

  • Isolate all blocks and see if there are smaller blocks already contained inside bigger blocks, remove the smaller ones.
  • If there are duplicates of the same kind, remove them.
  • If there are blocks that can be joined together because they share partially the content or if they touch themselves merge them into a bigger block.
  • If some aggregation of blocks can be achieved, aggregate them into and so on.

My knowledge of ip blocks unpacking and comparing is kinda limited so for now the only part i can get rid of is a duplicate check modelling the function like:

function optimize_ipblocks($input_array) {

   $blocks = array();

   foreach($input_array as $key => $val) {

      if(!in_array($val, $blocks)) $blocks[] = $val;

   }

   return $blocks;

}

I have no idea how to carry out comparisons of blocks and aggregation.

Helpful links for resolution:

Cœur
  • 37,241
  • 25
  • 195
  • 267
user3450548
  • 183
  • 11
  • 1
    It seems you're looking to hire a freelancer to do it for you. We *help* with code, but we don't *create* code. Asking for full solutions when you haven't tried much yourself is not how StackOverflow works. There are PHP libraries to get IP ranges from CIDR addresses. – h2ooooooo Mar 06 '16 at 14:42
  • @h2ooooooo I also accept some hint on the passage of the algorytms i have to follow, then i can code them by myself.. is just I'm getting stuck with a problem I can't slice in smaller pieces, should the question be moved on algorytms stack exchange ? – user3450548 Mar 06 '16 at 14:45
  • You can get IP ranges [with the method here](http://stackoverflow.com/a/20057242/247893). That way you can compare the IP ranges as a simple number and compare them to eachother to figure out which are unnessesary. Once you've gotten all the full ranges you can go through and discard the unnessesary ones and create new ones that fit your description. – h2ooooooo Mar 06 '16 at 14:46
  • could this be used to check the output of answers? http://www.techzoom.net/Tools/IPAddressCalculator – Ryan Vincent Feb 22 '17 at 17:12

2 Answers2

0

I wrote a class for merging Ip ranges into an optimized superset of IP ranges. For your usage, you should first convert your CIDR addresses into from-to IP ranges, as in the $ranges array in this usage example:

$ranges=[
    ["from" => '192.168.0.1',"to" => '192.168.0.9'],
    ["from" => '192.168.0.3',"to" => '192.168.0.6'],
    ["from" => '192.168.0.1',"to" => '192.168.0.5'],
    ["from" => '192.168.0.13',"to" => '192.168.0.17'],
    ["from" => '192.168.0.2',"to" => '192.168.0.4'],
    ["from" => '192.168.0.2',"to" => '192.168.0.7'],
    ["from" => '192.168.0.12',"to" => '192.168.0.14'],
];

$rm=new C_RangeMerger($ranges,'ip');
$mergedRanges=$rm->getMergedRanges();

echo("<pre>".print_r($mergedRanges,1)."</pre>");

class C_RangeMerger

Output:

Array
(
    [0] => Array
        (
            [from] => 192.168.0.1
            [to] => 192.168.0.9
        )

    [1] => Array
        (
            [from] => 192.168.0.12
            [to] => 192.168.0.17
        )

)

Hope that helps!

Maickel
  • 54
  • 2
-1

This function should do what you want..

<?php

function merge_cidr(array $cidr_or_ipv4_list)
{ // Main function
$valid_ip='0*?((?:0)|(?:2(?:(?:[0-4][0-9])|(?:5[0-5])))|(?:1?[0-9]{1,2}))'; // Build the valid ipv4 regex
$valid_ip.=str_repeat(".$valid_ip",3); // Finalize the ipv4 regex accepting leading zeros for each part
$valid_routing_prefix='(?:0*?((?:(?:0)|(?:3[0-2])|(?:[1-2]?[0-9]))))'; // Build a regex for the routing prefix (accepting leading zeros)
    foreach($cidr_or_ipv4_list as $a) // For each entry you pass to the function
    if (is_string($a) && preg_match("#^[^0-9]*$valid_ip(?:/$valid_routing_prefix)?[^0-9]*$#", $a, $m))
    { // Extracting the valid ipv4 and optionnaly the routing prefix
        $m[5] = ctype_digit($m[5]) ? ((int)$m[5]) : 32; // Initialize the valid routing prefix to the extracted value or 32 if mismatch
        $c[$m[5]][] = ip2long("$m[1].$m[2].$m[3].$m[4]") & (-1 << (32 - $m[5])); // Initialize the working array with key (prefix) and value as subnet by bitwise the decimal ip
    }

    if ($c) // If any valid ipv4 with optional routing prefix matched
    {
        foreach($c as &$unique) $unique=array_unique($unique); //Make unique as possible before processing
        $c = merge_cidr_summarize($c); // Pass the valid array to the slave function
        foreach($c as $d => & $e) // For each result as routing prefix => Decimal value
        $e = array_map(
        function ($a) use($d)
        {
            return [$a, $a + (1 << (32 - $d)) - 1];
        }

        , $e); // Change it to an array containing the range of ip
        foreach($c as $f => $g) // For each result as routing prefix => array of decimal value
        foreach($c as $h => $i) // For each result as routing prefix => array of decimal value
        if ($f > $h) // If we are not in the same line and the second line have a lower routing prefix
        foreach($g as $j => $k) // For each line as id => array of decimal values
        foreach($i as $l) // For each line as decimal value in the second foreach
        if ($k[0] >= $l[0] && $k[1] <= $l[1]) // If the block with lower routing prefix is totally including the first
        unset($c[$f][$j]); // Unset the smaller block
        foreach($c as $f => $g) //  For each result as routing prefix => array of decimal value
        {
            usort($g,
            function (array $a, array $b)
            {
                return  $b[0]>$a[0]?1:($b[0]<$a[0]?-1:0);
            }); // Order the result "naturally" inversed
            foreach($g as $h) // For each ordered result
            $z[] = long2ip($h[0]) . '/' . $f; // Convert it to human readable
        }

        return array_reverse($z); // And return the reversed result (order by routing prefix DESC and ip DESC)
    }
}

function merge_cidr_summarize(array $a)
{ // Slave function
    $b = false; // Did we make a change ?
    $c = []; // Initialize the result to an empty array
    krsort($a); // Order the input by routing prefix DESC
    foreach($a as $d => $e) { // For each entry as cidr => Array of decimal values
        sort($a[$d]); // Order the values "naturally"
        $k = count($a[$d]); // Count the values for the loop
        for ($i = 0; $i < $k; $i++) // Loop to check all values with this routing prefix
        if ($a[$d][$i] == $a[$d][$i + 1]) continue; // If the subnet is the same as the next, then directly goto the next
        elseif (($a[$d][$i] & (-1 << 33 - $d)) == ($a[$d][$i + 1] & (-1 << 33 - $d))) { // Check if subnet of this line and the next line are equals
            $c[$d - 1][] = $a[$d][$i++] & (-1 << 33 - $d); //  If yes add the new subnet in result array and skip the next line
            $b = true; // And tell the script to run again
        }
        else $c[$d][] = $a[$d][$i]; //  Else don't make anything
    }

    return $b ? merge_cidr_summarize($c) : $a; // If any change run again else return the result
}

To try it

<?php

$your_array=['160.11.0.0/16','160.11.14.0/20','160.12.0.0/14','160.16.5.0/15','160.16.1.0/14','160.18.0.0/16','160.20.0.0/14','160.24.0.0/16','160.26.0.0/15','160.28.0.0/15','160.74.0.0/16'];

print_r(merge_cidr($your_array));

Output.. Check it in https://eval.in/745895

/*
    Array
    (
        [0] => 160.16.0.0/13
        [1] => 160.12.0.0/14
        [2] => 160.28.0.0/15
        [3] => 160.26.0.0/15
        [4] => 160.74.0.0/16
        [5] => 160.24.0.0/16
        [6] => 160.11.0.0/16
    )
*/
Php'Regex
  • 213
  • 3
  • 4
  • 3
    can you at least indent it properly? its horrible to look at, and even harder to understand if you're someone needing assistance. – DevDonkey Feb 22 '17 at 12:51