Тестирование, если сеть в записи cidr перекрывает другую сеть

Вот обновленная версия класса, ранее обсуждавшегося в чате. Он может делать то, что вам нужно, а также много других полезных вещей.

 <?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 !== "\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 

NB: методы итератора / массива доступа к адресам узлов подсети возвращают другой объект 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; } 

Посмотрите, как работает

Как было кратко обсуждено в чате PHP, вот как я его реализую, чтобы сравнить любые два адреса.

1. Преобразование IP-адресов в их двоичную форму
2. Извлечь маски из формата CIDR
3. Возьмите минимальную маску двух (наименьшая конкретная = содержит больше адресов)
4. Используйте маску для обоих двоичных представлений.
5. Сравните эти два.

Если есть совпадение, то один содержится внутри другого.

Вот пример кода, это не очень красиво, и вы захотите адаптировать его для обслуживания вашего массива.

 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-целые числа подписаны). Мысль о будущей реализации!

Интуитивно я бы предложил вам сделать что-то вроде:

1. Пусть новая запись будет X
2. Преобразуйте X в единую целочисленную форму, пусть это целое число Y
3. Пусть длина маски любой записи A является mask(A)
4. Сравните любые существующие записи, где mask(entry) = mask(Y)
5. Отметьте существующие записи, в которых mask(entry) > mask(Y) и сравните с Y
6. Mask off Y для каждой существующей записи, где mask(entry) < mask(X) , так что mask(Y) = mask(entry) и compare

Если вы не столкнетесь с столкновениями, все будет хорошо.

Конечно, это не проверяет правильность предлагаемой подсети.

Мое предложение о правильности здесь заключается в том, что я не могу придумать контр-пример, но может быть и одно, поэтому я предлагаю это в качестве основы для дальнейшей мысли – надеюсь, что это поможет.

 <?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% правильно, но попробуйте, посмотрите, работает ли он.