Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
77 / 77
100.00% covered (success)
100.00%
5 / 5
CRAP
100.00% covered (success)
100.00%
1 / 1
IPSet
100.00% covered (success)
100.00%
77 / 77
100.00% covered (success)
100.00%
5 / 5
29
100.00% covered (success)
100.00%
1 / 1
 __construct
100.00% covered (success)
100.00%
2 / 2
100.00% covered (success)
100.00%
1 / 1
2
 addCidr
100.00% covered (success)
100.00%
48 / 48
100.00% covered (success)
100.00%
1 / 1
18
 match
100.00% covered (success)
100.00%
18 / 18
100.00% covered (success)
100.00%
1 / 1
7
 newFromJson
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
1
 jsonSerialize
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
1
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 */
23namespace Wikimedia;
24
25use JsonSerializable;
26
27/**
28 * Matches IP addresses against a set of CIDR specifications
29 *
30 * Usage:
31 *
32 *     use Wikimedia\IPSet;
33 *     // At startup, calculate the optimized data structure for the set:
34 *     $ipset = new IPSet( [
35 *         '208.80.154.0/26',
36 *         '2620:0:861:1::/64',
37 *         '10.64.0.0/22',
38 *     ] );
39 *
40 *     // Runtime check against cached set (returns bool):
41 *     $allowme = $ipset->match( $ip );
42 *
43 * In rough benchmarking, this takes about 80% more time than
44 * in_array() checks on a short (a couple hundred at most) array
45 * of addresses.  It's fast either way at those levels, though,
46 * and IPSet would scale better than in_array if the array were
47 * much larger.
48 *
49 * For mixed-family CIDR sets, however, this code gives well over
50 * 100x speedup vs iterating Wikimedia\IPUtils::isInRange() over an array
51 * of CIDR specs.
52 *
53 * The basic implementation is two separate binary trees
54 * (IPv4 and IPv6) as nested php arrays with keys named 0 and 1.
55 * The values false and true are terminal match-fail and match-success,
56 * otherwise the value is a deeper node in the tree.
57 *
58 * A simple depth-compression scheme is also implemented: whole-byte
59 * tree compression at whole-byte boundaries only, where no branching
60 * occurs during that whole byte of depth.  A compressed node has
61 * keys 'comp' (the byte to compare) and 'next' (the next node to
62 * recurse into if 'comp' matched successfully).
63 *
64 * For example, given these inputs:
65 *
66 *     25.0.0.0/9
67 *     25.192.0.0/10
68 *
69 * The v4 tree would look like:
70 *
71 *     root4 => [
72 *         'comp' => 25,
73 *         'next' => [
74 *             0 => true,
75 *             1 => [
76 *                 0 => false,
77 *                 1 => true,
78 *             ],
79 *         ],
80 *     ];
81 *
82 * (multi-byte compression nodes were attempted as well, but were
83 * a net loss in my test scenarios due to additional match complexity)
84 */
85class IPSet implements JsonSerializable {
86    /** @var array|bool The root of the IPv4 matching tree */
87    private $root4 = false;
88
89    /** @var array|bool The root of the IPv6 matching tree */
90    private $root6 = false;
91
92    /**
93     * Instantiate the object from an array of CIDR specs
94     *
95     * Invalid input network/mask values in $cfg will result in issuing
96     * E_WARNING and/or E_USER_WARNING and the bad values being ignored.
97     *
98     * @param array $cfg Array of IPv[46] CIDR specs as strings
99     */
100    public function __construct( array $cfg ) {
101        foreach ( $cfg as $cidr ) {
102            $this->addCidr( $cidr );
103        }
104    }
105
106    /**
107     * Add a single CIDR spec to the internal matching trees
108     *
109     * @param string $cidr String CIDR spec, IPv[46], optional /mask (def all-1's)
110     * @return bool Returns true on success, false on failure
111     */
112    private function addCidr( $cidr ): bool {
113        // v4 or v6 check
114        if ( strpos( $cidr, ':' ) === false ) {
115            $node =& $this->root4;
116            $defMask = '32';
117        } else {
118            $node =& $this->root6;
119            $defMask = '128';
120        }
121
122        // Default to all-1's mask if no netmask in the input
123        if ( strpos( $cidr, '/' ) === false ) {
124            $net = $cidr;
125            $mask = $defMask;
126        } else {
127            [ $net, $mask ] = explode( '/', $cidr, 2 );
128            if ( (int)$mask > $defMask || !ctype_digit( $mask ) ) {
129                trigger_error( "IPSet: Bad mask '$mask' from '$cidr', ignored", E_USER_WARNING );
130                return false;
131            }
132        }
133        // explicit integer convert, checked above
134        $mask = (int)$mask;
135
136        // convert $net to an array of integer bytes, length 4 or 16
137        // phpcs:ignore Generic.PHP.NoSilencedErrors.Discouraged
138        $raw = @inet_pton( $net );
139        if ( $raw === false ) {
140            return false;
141        }
142        $rawOrd = array_map( 'ord', str_split( $raw ) );
143
144        // iterate the bits of the address while walking the tree structure for inserts
145        // at the end, $snode will point to the highest node that could only lead to a
146        // successful match (and thus can be set to true)
147        $snode =& $node;
148        $curBit = 0;
149        while ( 1 ) {
150            if ( $node === true ) {
151                // already added a larger supernet, no need to go deeper
152                return true;
153            }
154
155            if ( $curBit === $mask ) {
156                // this may wipe out deeper subnets from earlier
157                $snode = true;
158                return true;
159            }
160
161            if ( $node === false ) {
162                // create new subarray to go deeper
163                if ( !( $curBit & 7 ) && $curBit <= $mask - 8 ) {
164                    $node = [ 'comp' => $rawOrd[$curBit >> 3], 'next' => false ];
165                } else {
166                    $node = [ false, false ];
167                }
168            }
169
170            if ( isset( $node['comp'] ) ) {
171                $comp = $node['comp'];
172                if ( $rawOrd[$curBit >> 3] === $comp && $curBit <= $mask - 8 ) {
173                    // whole byte matches, skip over the compressed node
174                    $node =& $node['next'];
175                    $snode =& $node;
176                    $curBit += 8;
177                    continue;
178                }
179
180                // have to decompress the node and check individual bits
181                $unode = $node['next'];
182                for ( $i = 0; $i < 8; ++$i ) {
183                    $unode = ( $comp & ( 1 << $i ) )
184                        ? [ false, $unode ]
185                        : [ $unode, false ];
186                }
187                $node = $unode;
188            }
189
190            $maskShift = 7 - ( $curBit & 7 );
191            $index = ( $rawOrd[$curBit >> 3] & ( 1 << $maskShift ) ) >> $maskShift;
192            if ( $node[$index ^ 1] !== true ) {
193                // no adjacent subnet, can't form a supernet at this level
194                $snode =& $node[$index];
195            }
196            $node =& $node[$index];
197            ++$curBit;
198        }
199    }
200
201    /**
202     * Match an IP address against the set
203     *
204     * If $ip is unparseable, inet_pton may issue an E_WARNING to that effect
205     *
206     * @param string $ip string IPv[46] address
207     * @return bool True is match success, false is match failure
208     */
209    public function match( $ip ): bool {
210        // phpcs:ignore Generic.PHP.NoSilencedErrors.Discouraged
211        $raw = @inet_pton( $ip );
212        if ( $raw === false ) {
213            return false;
214        }
215
216        $rawOrd = array_map( 'ord', str_split( $raw ) );
217        if ( count( $rawOrd ) === 4 ) {
218            $node =& $this->root4;
219        } else {
220            $node =& $this->root6;
221        }
222
223        $curBit = 0;
224        while ( $node !== true && $node !== false ) {
225            if ( isset( $node['comp'] ) ) {
226                // compressed node, matches 1 whole byte on a byte boundary
227                if ( $rawOrd[$curBit >> 3] !== $node['comp'] ) {
228                    return false;
229                }
230                $curBit += 8;
231                $node =& $node['next'];
232            } else {
233                // uncompressed node, walk in the correct direction for the current bit-value
234                $maskShift = 7 - ( $curBit & 7 );
235                $node =& $node[( $rawOrd[$curBit >> 3] & ( 1 << $maskShift ) ) >> $maskShift];
236                ++$curBit;
237            }
238        }
239
240        return $node;
241    }
242
243    /**
244     * @param string $json
245     *
246     * @return IPSet
247     */
248    public static function newFromJson( string $json ): IPSet {
249        $ipset = new IPSet( [] );
250        $decoded = json_decode( $json, true );
251        $ipset->root4 = $decoded['ipv4'] ?? false;
252        $ipset->root6 = $decoded['ipv6'] ?? false;
253
254        return $ipset;
255    }
256
257    public function jsonSerialize(): array {
258        return [
259            'ipv4' => $this->root4,
260            'ipv6' => $this->root6,
261        ];
262    }
263}