我正在寻找一种有效测试一个cidr标记网络是否与另一个重叠的PHP算法.
基本上我有以下情况:
一系列cidr地址:
$cidrNetworks = array( '192.168.10.0/24','10.10.0.30/20',etc. );
我有一个方法可以将网络添加到数组中,但是当添加的网络与数组中的网络重叠时,此方法应该抛出异常.
所以即.如果添加了192.168.10.0/25,则应抛出异常.
有没有人/知道/“可以想到”一种方法来有效地测试这个?
这是之前在聊天中讨论的类的更新版本.它可以做你需要的,以及许多其他有用的东西.
原文链接:https://www.f2er.com/php/135205.html<?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); } 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],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); 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); } else if (is_int($mask)) { $mask = $this->longToByteArray($mask); } else if (is_string($mask)) { $mask = preg_split('#\s*\.\s*#',trim($mask),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); } 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 !== "\xFF\xFF\xFF\xFF") { $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地址作为点分十进制返回,如果它代表多个地址,则返回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; }