vendor/wikimedia/ip-set/README.md

   1 IPSet
   2 =====
   3
   4 IPSet is a PHP library for matching IP addresses against a set of CIDR
   5 specifications.
   6
   7 Here is how you use it:
   8
   9 <pre lang="php">
  10 // At startup, calculate the optimized data structure for the set:
  11 $ipset = new IPSet( array(
  12     '208.80.154.0/26',
  13     '2620:0:861:1::/64',
  14     '10.64.0.0/22',
  15 ) );
  16
  17 // Runtime check against cached set (returns bool):
  18 if ( $ipset->match( $ip ) ) {
  19     // ...
  20 }
  21 </pre>
  22
  23 In rough benchmarking, this takes about 80% more time than `in_array()` checks
  24 on a short (a couple hundred at most) array of addresses.  It's fast either way
  25 at those levels, though, and IPSet would scale better than in_array if the
  26 array were much larger.
  27
  28 For mixed-family CIDR sets, however, this code gives well over 100x speedup vs
  29 iterating `IP::isInRange()` over an array of CIDR specs.
  30
  31 The basic implementation is two separate binary trees (IPv4 and IPv6) as nested
  32 php arrays with keys named 0 and 1.  The values false and true are terminal
  33 match-fail and match-success, otherwise the value is a deeper node in the tree.
  34
  35 A simple depth-compression scheme is also implemented: whole-byte tree
  36 compression at whole-byte boundaries only, where no branching occurs during
  37 that whole byte of depth.  A compressed node has keys 'comp' (the byte to
  38 compare) and 'next' (the next node to recurse into if 'comp' matched successfully).
  39
  40 For example, given these inputs:
  41
  42 <pre>
  43 25.0.0.0/9
  44 25.192.0.0/10
  45 </pre>
  46
  47 The v4 tree would look like:
  48
  49 <pre lang="php">
  50 root4 => array(
  51     'comp' => 25,
  52     'next' => array(
  53         0 => true,
  54         1 => array(
  55             0 => false,
  56             1 => true,
  57         ),
  58     ),
  59 );
  60 </pre>
  61
  62 (multi-byte compression nodes were attempted as well, but were
  63 a net loss in my test scenarios due to additional match complexity)
  64
  65
  66 License
  67 -------
  68 Copyright 2014, 2015 Brandon Black <blblack@gmail.com>
  69
  70 This program is free software; you can redistribute it and/or modify
  71 it under the terms of the GNU General Public License as published by
  72 the Free Software Foundation; either version 2 of the License, or
  73 (at your option) any later version.
  74
  75 This program is distributed in the hope that it will be useful,
  76 but WITHOUT ANY WARRANTY; without even the implied warranty of
  77 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  78 GNU General Public License for more details.
  79
  80 You should have received a copy of the GNU General Public License along
  81 with this program; if not, write to the Free Software Foundation, Inc.,
  82 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  83 <http://www.gnu.org/copyleft/gpl.html>