IPSet.php

Go to the documentation of this file.

<?php
class IPSet {
    private $root4 = array( false, false );

    private $root6 = array( false, false );

    public function __construct( array $cfg ) {
        foreach ( $cfg as $cidr ) {
            $this->addCidr( $cidr );
        }

        self::recOptimize( $this->root4 );
        self::recCompress( $this->root4, 0, 24 );
        self::recOptimize( $this->root6 );
        self::recCompress( $this->root6, 0, 120 );
    }

    private function addCidr( $cidr ) {
        // v4 or v6 check
        if ( strpos( $cidr, ':' ) === false ) {
            $node =& $this->root4;
            $defMask = '32';
        } else {
            $node =& $this->root6;
            $defMask = '128';
        }

        // Default to all-1's mask if no netmask in the input
        if ( strpos( $cidr, '/' ) === false ) {
            $net = $cidr;
            $mask = $defMask;
        } else {
            list( $net, $mask ) = explode( '/', $cidr, 2 );
            if ( !ctype_digit( $mask ) || intval( $mask ) > $defMask ) {
                trigger_error( "IPSet: Bad mask '$mask' from '$cidr', ignored", E_USER_WARNING );
                return;
            }
        }
        $mask = intval( $mask ); // explicit integer convert, checked above

        // convert $net to an array of integer bytes, length 4 or 16:
        $raw = inet_pton( $net );
        if ( $raw === false ) {
            return; // inet_pton() sends an E_WARNING for us
        }
        $rawOrd = array_map( 'ord', str_split( $raw ) );

        // special-case: zero mask overwrites the whole tree with a pair of terminal successes
        if ( $mask == 0 ) {
            $node = array( true, true );
            return;
        }

        // iterate the bits of the address while walking the tree structure for inserts
        $curBit = 0;
        while ( 1 ) {
            $maskShift = 7 - ( $curBit & 7 );
            $node =& $node[( $rawOrd[$curBit >> 3] & ( 1 << $maskShift ) ) >> $maskShift];
            ++$curBit;
            if ( $node === true ) {
                // already added a larger supernet, no need to go deeper
                return;
            } elseif ( $curBit == $mask ) {
                // this may wipe out deeper subnets from earlier
                $node = true;
                return;
            } elseif ( $node === false ) {
                // create new subarray to go deeper
                $node = array( false, false );
            }
        }
    }

    public function match( $ip ) {
        $raw = inet_pton( $ip );
        if ( $raw === false ) {
            return false; // inet_pton() sends an E_WARNING for us
        }

        $rawOrd = array_map( 'ord', str_split( $raw ) );
        if ( count( $rawOrd ) == 4 ) {
            $node =& $this->root4;
        } else {
            $node =& $this->root6;
        }

        $curBit = 0;
        while ( 1 ) {
            if ( isset( $node['comp'] ) ) {
                // compressed node, matches 1 whole byte on a byte boundary
                if ( $rawOrd[$curBit >> 3] != $node['comp'] ) {
                    return false;
                }
                $curBit += 8;
                $node =& $node['next'];
            } else {
                // uncompressed node, walk in the correct direction for the current bit-value
                $maskShift = 7 - ( $curBit & 7 );
                $node =& $node[( $rawOrd[$curBit >> 3] & ( 1 << $maskShift ) ) >> $maskShift];
                ++$curBit;
            }

            if ( $node === true || $node === false ) {
                return $node;
            }
        }
    }

    private static function recOptimize( &$node ) {
        if ( $node[0] !== false && $node[0] !== true && self::recOptimize( $node[0] ) ) {
            $node[0] = true;
        }
        if ( $node[1] !== false && $node[1] !== true && self::recOptimize( $node[1] ) ) {
            $node[1] = true;
        }
        if ( $node[0] === true && $node[1] === true ) {
            return true;
        }
        return false;
    }

    private static function recCompress( &$node, $curBit, $maxCompStart ) {
        if ( !( $curBit & 7 ) ) { // byte boundary, check for depth-8 single path(s)
            $byte = 0;
            $cnode =& $node;
            $i = 8;
            while ( $i-- ) {
                if ( $cnode[0] === false ) {
                    $byte |= 1 << $i;
                    $cnode =& $cnode[1];
                } elseif ( $cnode[1] === false ) {
                    $cnode =& $cnode[0];
                } else {
                    // partial-byte branching, give up
                    break;
                }
            }
            if ( $i == -1 ) { // means we did not exit the while() via break
                $node = array(
                    'comp' => $byte,
                    'next' => &$cnode,
                );
                $curBit += 8;
                if ( $cnode !== true ) {
                    self::recCompress( $cnode, $curBit, $maxCompStart );
                }
                return;
            }
        }

        ++$curBit;
        if ( $curBit <= $maxCompStart ) {
            if ( $node[0] !== false && $node[0] !== true ) {
                self::recCompress( $node[0], $curBit, $maxCompStart );
            }
            if ( $node[1] !== false && $node[1] !== true ) {
                self::recCompress( $node[1], $curBit, $maxCompStart );
            }
        }
    }
}