Question: I'm searching for a php algorithm that efficiently test if one cidr notated network overlaps another.

Basically I have the following situation:

Array of cidr adresses:

```
$cidrNetworks = array(
    '192.168.10.0/24',
    '10.10.0.30/20',
    etc.
);

```

I have a method that adds networks to the array, but this method should throw an exception when a network is added that overlaps with a network allready in the array. 

So ie. if 192.168.10.0/25 is added an exception should be thrown.

Does anyone have/know/"can think of" an method to test this efficiently?

Answer: 
As discussed briefly in PHP chat, here's how I would implement it, to compare any two addresses.

1. Convert the IP addresses to their binary form
2. Extract the masks from the CIDR format
3. Take the minimum mask of the two (least specific =
contains more addresses)
4. Use the mask on both binary representations.
5. Compare the two.

If there is a match, then one is contained within the other.

Here's some example code, it's not very pretty and you'll want to adapt it to cater for your array.

```
function bin_pad($num)
{
    return str_pad(decbin($num), 8, '0', STR_PAD_LEFT);
}

$ip1 = '192.168.0.0/23';
$ip2 = '192.168.1.0/24';

$regex = '~(\d+)\.(\d+)\.(\d+)\.(\d+)/(\d+)~';

preg_match($regex, $ip1, $ip1);
preg_match($regex, $ip2, $ip2);

$mask = min($ip1[5], $ip2[5]);

$ip1 = substr(
    bin_pad($ip1[1]) . bin_pad($ip1[2]) .
    bin_pad($ip1[3]) . bin_pad($ip1[4]),
    0, $mask
);

$ip2 = substr(
    bin_pad($ip2[1]) . bin_pad($ip2[2]) .
    bin_pad($ip2[3]) . bin_pad($ip2[4]),
    0, $mask
);

var_dump($ip1, $ip2, $ip1 === $ip2);

```

I had trouble making it 32 bit compatible, which is why I eventually opted for converting each octet of the IP address into binary individually, and then using `substr`.

I started off using `pack('C4', $ip[1] .. $ip[4])` but when it came to using a full 32 bit mask I ran into problems converting it into binary (since PHP integers are signed). Thought for a future implementation though!
Intuitively I would suggest you'd want to do something like:

1. Let the new entry be `X`
2. Convert `X` to single integer form, let that integer be `Y`
3. Let mask length of any entry `A` be `mask(A)`
4. Compare any existing entries where `mask(entry) = mask(Y)`
5. Mask off existing entries where `mask(entry) > mask(Y)` and compare with `Y`
6. Mask off `Y` for each existing entry where `mask(entry) < mask(X)`, such that `mask(Y) = mask(entry)` and compare

Provided you encounter no collisions, all is well.

Of course this does not check if the proposed subnet is valid.

My proposition of correctness here is that I can't think of a counter-example, but there may well be one so I offer this as a basis for further thought - hope this helps.