我正在寻找一种php算法，该算法可以有效地测试一个cidr标记的网络是否与另一个网络重叠。
基本上我有以下情况：
cidr地址阵列：
$cidrNetworks = array(
'192.168.10.0/24',
'10.10.0.30/20',
etc.
);
我有一个方法可以将网络添加到阵列中，但当添加的网络与阵列中的网络allready重叠时，此方法应该引发异常。
因此，如果添加了192.168.10.0/25，则应该引发异常。
有人有/知道/"能想到"有效测试这一点的方法吗？
这是之前在聊天中讨论的类的更新版本。它可以做你需要的事情，以及许多其他有用的事情。
<?php
class IPv4Subnet implements ArrayAccess, Iterator {
/*
* Address format constants
*/
const ADDRESS_BINARY = 0x01;
const ADDRESS_INT = 0x02;
const ADDRESS_DOTDEC = 0x04;
const ADDRESS_SUBNET = 0x08;
/*
* Constants to control whether getHosts() returns the network/broadcast addresses
*/
const HOSTS_WITH_NETWORK = 0x10;
const HOSTS_WITH_BROADCAST = 0x20;
const HOSTS_ALL = 0x30;
/*
* Properties to store base address and subnet mask as binary strings
*/
protected $address;
protected $mask;
/*
* Counter to track the current iteration offset
*/
private $iteratorOffset = 0;
/*
* Array to hold values retrieved via ArrayAccess
*/
private $arrayAccessObjects = array();
/*
* Helper methods
*/
private function longToBinary ($long) {
return pack('N', $long);
}
private function longToDottedDecimal ($long) {
return ($long >> 24 & 0xFF).'.'.($long >> 16 & 0xFF).'.'.($long >> 8 & 0xFF).'.'.($long & 0xFF);
}
private function longToByteArray ($long) {
return array(
$long >> 24 & 0xFF,
$long >> 16 & 0xFF,
$long >> 8 & 0xFF,
$long & 0xFF
);
}
private function longToSubnet ($long) {
if (!isset($this->arrayAccessObjects[$long])) {
$this->arrayAccessObjects[$long] = new self($long);
}
return $this->arrayAccessObjects[$long];
}
private function binaryToLong ($binary) {
return current(unpack('N', $binary));
}
private function binaryToDottedDecimal ($binary) {
return implode('.', unpack('C*', $binary));
}
private function binaryToX ($binary, $mode) {
if ($mode & self::ADDRESS_BINARY) {
$result = $binary;
} else if ($mode & self::ADDRESS_INT) {
$result = $this->binaryToLong($binary);
} else if ($mode & self::ADDRESS_DOTDEC) {
$result = $this->binaryToDottedDecimal($binary);
} else {
$result = $this->longToSubnet($this->binaryToLong($binary));
}
return $result;
}
private function byteArrayToLong($bytes) {
return ($bytes[0] << 24) | ($bytes[1] << 16) | ($bytes[2] << 8) | $bytes[3];
}
private function byteArrayToBinary($bytes) {
return pack('C*', $bytes[0], $bytes[1], $bytes[2], $bytes[3]);
}
private function normaliseComparisonSubject (&$subject) {
if (!is_object($subject)) {
$subject = new self($subject);
}
if (!($subject instanceof self)) {
throw new InvalidArgumentException('Subject must be an instance of IPv4Subnet');
}
}
private function validateOctetArray (&$octets) {
foreach ($octets as &$octet) {
$octet = (int) $octet;
if ($octet < 0 || $octet > 255) {
return FALSE;
}
}
return TRUE;
}
/*
* Constructor
*/
public function __construct ($address = NULL, $mask = NULL) {
if ($address === NULL || (is_string($address) && trim($address) === '')) {
$address = array(0, 0, 0, 0);
} else if (is_int($address)) {
$address = $this->longToByteArray($address);
} else if (is_string($address)) {
$parts = preg_split('#s*/s*#', trim($address), -1, PREG_SPLIT_NO_EMPTY);
if (count($parts) > 2) {
throw new InvalidArgumentException('No usable IP address supplied: Syntax error');
} else if ($parts[0] === '') {
throw new InvalidArgumentException('No usable IP address supplied: IP address empty');
}
if (!empty($parts[1]) && !isset($mask)) {
$mask = $parts[1];
}
$address = preg_split('#s*.s*#', $parts[0], -1, PREG_SPLIT_NO_EMPTY);
} else if (is_array($address)) {
$address = array_values($address);
} else {
throw new InvalidArgumentException('No usable IP address supplied: Value must be a string or an integer');
}
$suppliedAddressOctets = count($address);
$address += array(0, 0, 0, 0);
if ($suppliedAddressOctets > 4) {
throw new InvalidArgumentException('No usable IP address supplied: IP address has more than 4 octets');
} else if (!$this->validateOctetArray($address)) {
throw new InvalidArgumentException('No usable IP address supplied: At least one octet value outside acceptable range 0 - 255');
}
if ($mask === NULL) {
$mask = array_pad(array(), $suppliedAddressOctets, 255) + array(0, 0, 0, 0);
} else if (is_int($mask)) {
$mask = $this->longToByteArray($mask);
} else if (is_string($mask)) {
$mask = preg_split('#s*.s*#', trim($mask), -1, PREG_SPLIT_NO_EMPTY);
switch (count($mask)) {
case 1: // CIDR
$cidr = (int) $mask[0];
if ($cidr === 0) {
// Shifting 32 bits on a 32 bit system doesn't work, so treat this as a special case
$mask = array(0, 0, 0, 0);
} else if ($cidr <= 32) {
// This looks odd, but it's the nicest way I have found to get the 32 least significant bits set in a
// way that works on both 32 and 64 bit platforms
$base = ~((~0 << 16) << 16);
$mask = $this->longToByteArray($base << (32 - $cidr));
} else {
throw new InvalidArgumentException('Supplied mask invalid: CIDR outside acceptable range 0 - 32');
}
break;
case 4: break; // Dotted decimal
default: throw new InvalidArgumentException('Supplied mask invalid: Must be either a full dotted-decimal or a CIDR');
}
} else if (is_array($mask)) {
$mask = array_values($mask);
} else {
throw new InvalidArgumentException('Supplied mask invalid: Type invalid');
}
if (!$this->validateOctetArray($mask)) {
throw new InvalidArgumentException('Supplied mask invalid: At least one octet value outside acceptable range 0 - 255');
}
// Check bits are contiguous from left
// TODO: Improve this mechanism
$asciiBits = sprintf('%032b', $this->byteArrayToLong($mask));
if (strpos(rtrim($asciiBits, '0'), '0') !== FALSE) {
throw new InvalidArgumentException('Supplied mask invalid: Set bits are not contiguous from the most significant bit');
}
$this->mask = $this->byteArrayToBinary($mask);
$this->address = $this->byteArrayToBinary($address) & $this->mask;
}
/*
* ArrayAccess interface methods (read only)
*/
public function offsetExists ($offset) {
if ($offset === 'network' || $offset === 'broadcast') {
return TRUE;
}
$offset = filter_var($offset, FILTER_VALIDATE_INT);
if ($offset === FALSE || $offset < 0) {
return FALSE;
}
return $offset < $this->getHostsCount();
}
public function offsetGet ($offset) {
if (!$this->offsetExists($offset)) {
return NULL;
}
if ($offset === 'network') {
$address = $this->getNetworkAddress(self::ADDRESS_INT);
} else if ($offset === 'broadcast') {
$address = $this->getBroadcastAddress(self::ADDRESS_INT);
} else {
// How much the address needs to be adjusted by to account for network address
$adjustment = (int) ($this->getHostsCount() > 2);
$address = $this->binaryToLong($this->address) + $offset + $adjustment;
}
return $this->longToSubnet($address);
}
public function offsetSet ($offset, $value) {}
public function offsetUnset ($offset) {}
/*
* Iterator interface methods
*/
public function current () {
return $this->offsetGet($this->iteratorOffset);
}
public function key () {
return $this->iteratorOffset;
}
public function next () {
$this->iteratorOffset++;
}
public function rewind () {
$this->iteratorOffset = 0;
}
public function valid () {
return $this->iteratorOffset < $this->getHostsCount();
}
/*
* Data access methods
*/
public function getHosts ($mode = self::ADDRESS_SUBNET) {
// Parse flags and initialise vars
$bin = (bool) ($mode & self::ADDRESS_BINARY);
$int = (bool) ($mode & self::ADDRESS_INT);
$dd = (bool) ($mode & self::ADDRESS_DOTDEC);
$base = $this->binaryToLong($this->address);
$mask = $this->binaryToLong($this->mask);
$hasNwBc = !($mask & 0x03);
$result = array();
// Get network address if requested
if (($mode & self::HOSTS_WITH_NETWORK) && $hasNwBc) {
$result[] = $base;
}
// Get hosts
for ($current = $hasNwBc ? $base + 1 : $base; ($current & $mask) === $base; $current++) {
$result[] = $current;
}
// Remove broadcast address if present and not requested
if ($hasNwBc && !($mode & self::HOSTS_WITH_BROADCAST)) {
array_pop($result);
}
// Convert to the correct type
if ($bin) {
$result = array_map(array($this, 'longToBinary'), $result);
} else if ($dd) {
$result = array_map(array($this, 'longToDottedDecimal'), $result);
} else if (!$int) {
$result = array_map(array($this, 'longToSubnet'), $result);
}
return $result;
}
public function getHostsCount () {
$count = $this->getBroadcastAddress(self::ADDRESS_INT) - $this->getNetworkAddress(self::ADDRESS_INT);
return $count > 2 ? $count - 1 : $count + 1; // Adjust return value to exclude network/broadcast addresses
}
public function getNetworkAddress ($mode = self::ADDRESS_SUBNET) {
return $this->binaryToX($this->address, $mode);
}
public function getBroadcastAddress ($mode = self::ADDRESS_SUBNET) {
return $this->binaryToX($this->address | ~$this->mask, $mode);
}
public function getMask ($mode = self::ADDRESS_DOTDEC) {
return $this->binaryToX($this->mask, $mode);
}
/*
* Stringify methods
*/
public function __toString () {
if ($this->getHostsCount() === 1) {
$result = $this->toDottedDecimal();
} else {
$result = $this->toCIDR();
}
return $result;
}
public function toDottedDecimal () {
$result = $this->getNetworkAddress(self::ADDRESS_DOTDEC);
if ($this->mask !== "xFFxFFxFFxFF") {
$result .= '/'.$this->getMask(self::ADDRESS_DOTDEC);
}
return $result;
}
public function toCIDR () {
$address = $this->getNetworkAddress(self::ADDRESS_DOTDEC);
$cidr = strlen(trim(sprintf('%b', $this->getMask(self::ADDRESS_INT)), '0')); // TODO: Improve this mechanism
return $address.'/'.$cidr;
}
/*
* Comparison methods
*/
public function contains ($subject) {
$this->normaliseComparisonSubject($subject);
$subjectAddress = $subject->getNetworkAddress(self::ADDRESS_BINARY);
$subjectMask = $subject->getMask(self::ADDRESS_BINARY);
return $this->mask !== $subjectMask && ($this->mask | ($this->mask ^ $subjectMask)) !== $this->mask && ($subjectAddress & $this->mask) === $this->address;
}
public function within ($subject) {
$this->normaliseComparisonSubject($subject);
$subjectAddress = $subject->getNetworkAddress(self::ADDRESS_BINARY);
$subjectMask = $subject->getMask(self::ADDRESS_BINARY);
return $this->mask !== $subjectMask && ($this->mask | ($this->mask ^ $subjectMask)) === $this->mask && ($this->address & $subjectMask) === $subjectAddress;
}
public function equalTo ($subject) {
$this->normaliseComparisonSubject($subject);
return $this->address === $subject->getNetworkAddress(self::ADDRESS_BINARY) && $this->mask === $subject->getMask(self::ADDRESS_BINARY);
}
public function intersect ($subject) {
$this->normaliseComparisonSubject($subject);
return $this->equalTo($subject) || $this->contains($subject) || $this->within($subject);
}
}
为了做你想做的事，该类提供了4种方法：
contains()
within()
equalTo()
intersect()
示例用法：
// Also accepts dotted decimal mask. The mask may also be passed to the second
// argument. Any valid combination of dotted decimal, CIDR and integers will be
// accepted
$subnet = new IPv4Subnet('192.168.0.0/24');
// These methods will accept a string or another instance
var_dump($subnet->contains('192.168.0.1')); //TRUE
var_dump($subnet->contains('192.168.1.1')); //FALSE
var_dump($subnet->contains('192.168.0.0/16')); //FALSE
var_dump($subnet->within('192.168.0.0/16')); //TRUE
// ...hopefully you get the picture. intersect() returns TRUE if any of the
// other three match.
该类还实现了Iterator接口，允许您迭代子网中的所有地址。迭代器排除了可以单独检索的网络地址和广播地址。
示例：
$subnet = new IPv4Subnet('192.168.0.0/28');
echo "Network: ", $subnet->getNetworkAddress(),
"; Broadcast: ", $subnet->getBroadcastAddress(),
"nHosts:n";
foreach ($subnet as $host) {
echo $host, "n";
}
该类还实现了ArrayAccess，允许您将其视为数组：
$subnet = new IPv4Subnet('192.168.0.0/28');
echo $subnet['network'], "n"; // 192.168.0.0
echo $subnet[0], "n"; // 192.168.0.1
// ...
echo $subnet[13], "n"; // 192.168.0.14
echo $subnet['broadcast'], "n"; // 192.168.0.15
注意：访问子网主机地址的迭代器/数组方法将返回另一个IPv4Subnet对象。该类实现__toString()，如果IP地址表示单个地址，则它将以点小数形式返回IP地址；如果CIDR表示多个地址，则返回CIDR。通过调用相关的get*()方法并传递所需的标志(请参阅类顶部定义的常量)，可以直接以字符串或整数的形式访问数据。
所有操作都是32位和64位安全的。兼容性应为(尽管未彻底测试)5.2+
看到它工作
为了完整性，我想您的用例将按照以下方式实现：
public function addSubnet ($newSubnet) {
$newSubnet = new IPv4Subnet($newSubnet);
foreach ($this->subnets as &$existingSubnet) {
if ($existingSubnet->contains($newSubnet)) {
throw new Exception('Subnet already added');
} else if ($existingSubnet->within($newSubnet)) {
$existingSubnet = $newSubnet;
return;
}
}
$this->subnets[] = $newSubnet;
}
看到它工作
正如在PHP聊天中简要讨论的那样，以下是我将如何实现它，以比较任意两个地址。
- 将IP地址转换为二进制形式
- 从CIDR格式提取掩码
- 取两者中最小的掩码(最不具体=包含更多地址)
- 在两种二进制表示形式上都使用掩码
- 将两者进行比较
如果存在匹配，则其中一个包含在另一个中。
这里有一些示例代码，它不是很漂亮，您需要对其进行调整以满足您的数组。
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);
我很难使它兼容32位，这就是为什么我最终选择将IP地址的每个八位字节单独转换为二进制，然后使用substr。
我一开始使用pack('C4', $ip[1] .. $ip[4])，但当使用完整的32位掩码时，我遇到了将其转换为二进制的问题(因为PHP整数是有符号的)。考虑未来的实施！
直觉上，我建议您应该做一些类似的事情：
- 设新条目为
X - 将
X转换为单个整数形式，使该整数为Y - 设任意条目
A的掩码长度为mask(A) - 比较
mask(entry) = mask(Y)所在的任何现有条目 - 屏蔽
mask(entry) > mask(Y)中的现有条目并与Y进行比较 - 为每个现有条目屏蔽
Y，其中mask(entry) < mask(X)，使得mask(Y) = mask(entry)和比较
如果你没有遇到碰撞，一切都很好。
当然，这不会检查提议的子网是否有效。
我在这里的正确性主张是，我想不出反例，但很可能有反例，所以我把它作为进一步思考的基础——希望这有帮助。
<?php
function checkOverlap ($net1, $net2) {
$mask1 = explode("/", $net1)[1];
$net1 = explode("/", $net1)[0];
$netArr1 = explode(".",$net1);
$mask2 = explode("/", $net2)[1];
$net2 = explode("/", $net2)[0];
$netArr2 = explode(".",$net2);
$newnet1 = $newnet2 = "";
foreach($netArr1 as $num) {
$binnum = decbin($num);
$length = strlen($binnum);
for ($i = 0; $i < 8-$length; $i++) {
$binnum = '0'.$binnum;
}
$newnet1 .= $binnum;
}
foreach($netArr2 as $num) {
$binnum = decbin($num);
$length = strlen($binnum);
for ($i = 0; $i < 8-$length; $i++) {
$binnum = '0'.$binnum;
}
$newnet2 .= $binnum;
}
$length = min($mask1, $mask2);
$newnet1 = substr($newnet1,0,$length);
$newnet2 = substr($newnet2,0,$length);
$overlap = 0;
if ($newnet1 == $newnet2) $overlap = 1;
return $overlap;
}
function networksOverlap ($networks, $newnet) {
$overlap = false;
foreach ($networks as $network) {
$overlap = checkOverlap($network, $newnet);
if ($overlap) return 1;
}
return $overlap;
}
$cidrNetworks = array(
'192.168.10.0/24',
'10.10.0.30/20'
);
$newnet = "192.168.10.0/25";
$overlap = networksOverlap($cidrNetworks, $newnet);
?>
不确定这是否100%正确，但试试看是否有效。