From 994648dc54861cf65520654bc6020b51859155bb Mon Sep 17 00:00:00 2001
From: "Matteo Nastasi (mop)" <nastasi@alternativeoutput.it>
Date: Sun, 1 Feb 2015 15:05:18 +0100
Subject: [PATCH] ipclass refactored with class sorting and more efficient
 check method

---
 web/Obj/ipclass.phh | 51 +++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 47 insertions(+), 4 deletions(-)

diff --git a/web/Obj/ipclass.phh b/web/Obj/ipclass.phh
index 6bcc336..3a3d588 100644
--- a/web/Obj/ipclass.phh
+++ b/web/Obj/ipclass.phh
@@ -31,6 +31,9 @@ class IPClassItem {
         //split
         $elem = split("/", $ipset, 2);
         $addr = $elem[0];
+        if (!isset($elem[1])) {
+            fprintf(STDERR, "ORIG: %s\n", $ipset);
+        }
         $mask = (int)$elem[1];
 
         //convert mask
@@ -47,6 +50,13 @@ class IPClassItem {
         //       $ip, $this->addr, $this->mask, ((ip2long($ip) & $this->mask) == $this->addr));
         return (($ip & $this->mask) == $this->addr);
     }
+
+    static function compare($a, $b)
+    {
+        if ($a->addr == $b->addr)
+            return (0);
+        return (($a->addr < $b->addr) ? -1 : 1);
+    }
 }
 
 class IPClass {
@@ -76,6 +86,7 @@ class IPClass {
         for ($i = 0 ; $i < count($ip_in) ; $i++) {
             $this->ipcl[$i] = new IPClassItem($ip_in[$i]);
         }
+        usort($this->ipcl, array("IPClassItem", "compare"));
     }
 
     function clean()
@@ -93,10 +104,42 @@ class IPClass {
     {
         $ip = ip2long($ip_str);
 
-        for ($i = 0 ; $i < count($this->ipcl) ; $i++) {
-            if ($this->ipcl[$i]->match($ip)) {
-                fprintf(STDERR, "ban_list[%d] = %x (%x) MATCH\n", $i,
-                        $this->ipcl[$i]->addr, $this->ipcl[$i]->mask);
+        if (count($this->ipcl) == 0) {
+            return (FALSE);
+        }
+
+        if ($ip < $this->ipcl[0]->addr)
+            return (FALSE);
+
+        $imin = 0;
+        $imax = count($this->ipcl) - 1;
+
+        while ($imax >= $imin) {
+            $imid = intval($imin + (($imax - $imin) / 2));
+            // printf("X: %d M: %d N: %d | ", $arr[$imin], $arr[$imid], $arr[$imax]);
+            if ($this->ipcl[$imid]->addr == $ip) {
+                break;
+            }
+            else if ($this->ipcl[$imid]->addr > $ip) {
+                $imax = $imid - 1;
+            }
+            else {
+                $imin = $imid + 1;
+            }
+        }
+        if ($this->ipcl[$imid]->addr > $ip) {
+            if ($imid > 0) {
+                $imid--;
+            }
+            else {
+                $imid = -1;
+            }
+        }
+
+        if ($imid > -1) {
+            if ($this->ipcl[$imid]->match($ip)) {
+                fprintf(STDERR, "ban_list[%d] = %x (%x) MATCH\n", $imid,
+                        $this->ipcl[$imid]->addr, $this->ipcl[$imid]->mask);
                 return(TRUE);
             }
         }
-- 
2.17.1