vendor/wikimedia/ip-set/src/IPSet.php

   1 <?php
   2 /**
   3  * Copyright 2014, 2015 Brandon Black <blblack@gmail.com>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  * http://www.gnu.org/copyleft/gpl.html
  19  *
  20  * @file
  21  * @author Brandon Black <blblack@gmail.com>
  22  */
  23 namespace IPSet;
  24
  25 /**
  26  * Matches IP addresses against a set of CIDR specifications
  27  *
  28  * Usage:
  29  *
  30  *     // At startup, calculate the optimized data structure for the set:
  31  *     $ipset = new IPSet( array(
  32  *         '208.80.154.0/26',
  33  *         '2620:0:861:1::/64',
  34  *         '10.64.0.0/22',
  35  *     ) );
  36  *
  37  *     // Runtime check against cached set (returns bool):
  38  *     $allowme = $ipset->match( $ip );
  39  *
  40  * In rough benchmarking, this takes about 80% more time than
  41  * in_array() checks on a short (a couple hundred at most) array
  42  * of addresses.  It's fast either way at those levels, though,
  43  * and IPSet would scale better than in_array if the array were
  44  * much larger.
  45  *
  46  * For mixed-family CIDR sets, however, this code gives well over
  47  * 100x speedup vs iterating IP::isInRange() over an array
  48  * of CIDR specs.
  49  *
  50  * The basic implementation is two separate binary trees
  51  * (IPv4 and IPv6) as nested php arrays with keys named 0 and 1.
  52  * The values false and true are terminal match-fail and match-success,
  53  * otherwise the value is a deeper node in the tree.
  54  *
  55  * A simple depth-compression scheme is also implemented: whole-byte
  56  * tree compression at whole-byte boundaries only, where no branching
  57  * occurs during that whole byte of depth.  A compressed node has
  58  * keys 'comp' (the byte to compare) and 'next' (the next node to
  59  * recurse into if 'comp' matched successfully).
  60  *
  61  * For example, given these inputs:
  62  *
  63  *     25.0.0.0/9
  64  *     25.192.0.0/10
  65  *
  66  * The v4 tree would look like:
  67  *
  68  *     root4 => array(
  69  *         'comp' => 25,
  70  *         'next' => array(
  71  *             0 => true,
  72  *             1 => array(
  73  *                 0 => false,
  74  *                 1 => true,
  75  *             ),
  76  *         ),
  77  *     );
  78  *
  79  * (multi-byte compression nodes were attempted as well, but were
  80  * a net loss in my test scenarios due to additional match complexity)
  81  */
  82 class IPSet {
  83         /** @var array|bool $root4 The root of the IPv4 matching tree */
  84         private $root4 = false;
  85
  86         /** @var array|bool $root6 The root of the IPv6 matching tree */
  87         private $root6 = false;
  88
  89         /**
  90          * Instantiate the object from an array of CIDR specs
  91          *
  92          * Invalid input network/mask values in $cfg will result in issuing
  93          * E_WARNING and/or E_USER_WARNING and the bad values being ignored.
  94          *
  95          * @param array $cfg Array of IPv[46] CIDR specs as strings
  96          */
  97         public function __construct( array $cfg ) {
  98                 foreach ( $cfg as $cidr ) {
  99                         $this->addCidr( $cidr );
 100                 }
 101         }
 102
 103         /**
 104          * Add a single CIDR spec to the internal matching trees
 105          *
 106          * @param string $cidr String CIDR spec, IPv[46], optional /mask (def all-1's)
 107          */
 108         private function addCidr( $cidr ) {
 109                 // v4 or v6 check
 110                 if ( strpos( $cidr, ':' ) === false ) {
 111                         $node =& $this->root4;
 112                         $defMask = '32';
 113                 } else {
 114                         $node =& $this->root6;
 115                         $defMask = '128';
 116                 }
 117
 118                 // Default to all-1's mask if no netmask in the input
 119                 if ( strpos( $cidr, '/' ) === false ) {
 120                         $net = $cidr;
 121                         $mask = $defMask;
 122                 } else {
 123                         list( $net, $mask ) = explode( '/', $cidr, 2 );
 124                         if ( !ctype_digit( $mask ) || intval( $mask ) > $defMask ) {
 125                                 trigger_error( "IPSet: Bad mask '$mask' from '$cidr', ignored", E_USER_WARNING );
 126                                 return;
 127                         }
 128                 }
 129                 $mask = intval( $mask ); // explicit integer convert, checked above
 130
 131                 // convert $net to an array of integer bytes, length 4 or 16:
 132                 $raw = inet_pton( $net );
 133                 if ( $raw === false ) {
 134                         return; // inet_pton() sends an E_WARNING for us
 135                 }
 136                 $rawOrd = array_map( 'ord', str_split( $raw ) );
 137
 138                 // iterate the bits of the address while walking the tree structure for inserts
 139                 // at the end, $snode will point to the highest node that could only lead to a
 140                 // successful match (and thus can be set to true)
 141                 $snode =& $node;
 142                 $curBit = 0;
 143                 while ( 1 ) {
 144                         if ( $node === true ) {
 145                                 // already added a larger supernet, no need to go deeper
 146                                 return;
 147                         } elseif ( $curBit == $mask ) {
 148                                 // this may wipe out deeper subnets from earlier
 149                                 $snode = true;
 150                                 return;
 151                         } elseif ( $node === false ) {
 152                                 // create new subarray to go deeper
 153                                 if ( !( $curBit & 7 ) && $curBit <= $mask - 8 ) {
 154                                         $node = array( 'comp' => $rawOrd[$curBit >> 3], 'next' => false );
 155                                 } else {
 156                                         $node = array( false, false );
 157                                 }
 158                         }
 159
 160                         if ( isset( $node['comp'] ) ) {
 161                                 $comp = $node['comp'];
 162                                 if ( $rawOrd[$curBit >> 3] == $comp && $curBit <= $mask - 8 ) {
 163                                         // whole byte matches, skip over the compressed node
 164                                         $node =& $node['next'];
 165                                         $snode =& $node;
 166                                         $curBit += 8;
 167                                         continue;
 168                                 } else {
 169                                         // have to decompress the node and check individual bits
 170                                         $unode = $node['next'];
 171                                         for ( $i = 0; $i < 8; ++$i ) {
 172                                                 $unode = ( $comp & ( 1 << $i ) )
 173                                                         ? array( false, $unode )
 174                                                         : array( $unode, false );
 175                                         }
 176                                         $node = $unode;
 177                                 }
 178                         }
 179
 180                         $maskShift = 7 - ( $curBit & 7 );
 181                         $index = ( $rawOrd[$curBit >> 3] & ( 1 << $maskShift ) ) >> $maskShift;
 182                         if ( $node[$index ^ 1] !== true ) {
 183                                 // no adjacent subnet, can't form a supernet at this level
 184                                 $snode =& $node[$index];
 185                         }
 186                         $node =& $node[$index];
 187                         ++$curBit;
 188                 }
 189         }
 190
 191         /**
 192          * Match an IP address against the set
 193          *
 194          * If $ip is unparseable, inet_pton may issue an E_WARNING to that effect
 195          *
 196          * @param string $ip string IPv[46] address
 197          * @return bool True is match success, false is match failure
 198          */
 199         public function match( $ip ) {
 200                 $raw = inet_pton( $ip );
 201                 if ( $raw === false ) {
 202                         return false; // inet_pton() sends an E_WARNING for us
 203                 }
 204
 205                 $rawOrd = array_map( 'ord', str_split( $raw ) );
 206                 if ( count( $rawOrd ) == 4 ) {
 207                         $node =& $this->root4;
 208                 } else {
 209                         $node =& $this->root6;
 210                 }
 211
 212                 $curBit = 0;
 213                 while ( $node !== true && $node !== false ) {
 214                         if ( isset( $node['comp'] ) ) {
 215                                 // compressed node, matches 1 whole byte on a byte boundary
 216                                 if ( $rawOrd[$curBit >> 3] != $node['comp'] ) {
 217                                         return false;
 218                                 }
 219                                 $curBit += 8;
 220                                 $node =& $node['next'];
 221                         } else {
 222                                 // uncompressed node, walk in the correct direction for the current bit-value
 223                                 $maskShift = 7 - ( $curBit & 7 );
 224                                 $node =& $node[( $rawOrd[$curBit >> 3] & ( 1 << $maskShift ) ) >> $maskShift];
 225                                 ++$curBit;
 226                         }
 227                 }
 228
 229                 return $node;
 230         }
 231 }