[Server Scripting] Searching a large array/IPs acting inconsistently

Discussion in 'Server and Client Scripting' started by Homura, Jan 4, 2014.

  1. Homura

    Homura Member

    Joined:
    May 22, 2012
    Messages:
    43
    Likes Received:
    0
    I'm trying to implement a proxy ban list (obv a big list then) and it's behaving inconsistently. So, I isolated the actual list part to test separately in a web browser:

    Code (text):
    1.     function ProxyList()
    2.     {
    3.         this.works = true;
    4.         this.list;
    5.     }
    6.     ProxyList.prototype.isBanned = function(ip)
    7.     {
    8.         if (!this.works) return false;
    9.  
    10.         //binary search
    11.         var high = this.list.length - 1,
    12.             low = 0, mid, val;
    13.         while (low <= high)
    14.         {
    15.             mid = (low + high) / 2 | 0;
    16.             val = this.list[mid];
    17.             if (val < ip)
    18.             {
    19.                 low = mid + 1;
    20.             }
    21.             else if (val > ip)
    22.             {
    23.                 high = mid - 1;
    24.             }
    25.             else
    26.             {
    27.                 return true;
    28.             }
    29.         }
    30.         return false;
    31.     }
    32.     ipbans = new ProxyList();
    33.     ipbans.list = ["0.2.2.37", "0.2.2.38", "0.2.2.39", "0.2.3.12", "0.2.3.13", "0.2.3.14", "0.2.3.18", "0.2.3.19", "0.2.3.20"];
    34.    
    35.     document.write("" + ipbans.isBanned("1.0.0.1") + ipbans.isBanned("0.2.3.20") + ipbans.isBanned("0.2.3.18"));
    This works exactly as intended and changing the values of the IPs works flawlessly. So I put that function back in to the script to use on the actual list, where everything stops working.

    Code (text):
    1.     function ProxyList()
    2.     {
    3.         this.works = true;
    4.         try
    5.         {
    6.             this.list = sys.getFileContent(proxyfile).split(/\n/); // a txt file with one IP Address per line
    7.         }
    8.         catch (e)
    9.         {
    10.             print("Failed to load proxies.");
    11.             sys.sendAll("Failed to load proxies.", watch);
    12.             this.works = false;
    13.         }
    14.     }
    The function isBanned is exactly the same. The proxyFile was tested with a list of only 20 IPs instead of the full 709k, at which time it functioned flawlessly, proof that grabbing it into the list from the file is functioning fine. The following input is with the full list:

    Show there was no catch:
    /eval sys.sendMessage(source, ipbans.works, chan)
    (17:50:58) true

    Grab one off the list:
    /eval sys.sendMessage(source, ipbans.list[0], chan);
    (18:37:15) 0.2.2.35

    Neither indexOf nor my search function think it's in there:
    /eval sys.sendMessage(source, ipbans.isBanned("0.2.2.35"), chan);
    (18:40:20) false
    /eval sys.sendMessage(source, ipbans.list.indexOf("0.2.2.35"), chan);
    (18:40:59) -1


    So it has this one-way deal, right? So when I pull off this trick
    /eval sys.sendMessage(source, ipbans.list.indexOf(ipbans.list[0]), chan);
    (18:42:50) 0
    it suddenly knows where to find it? So why can't I find it?

    Now then there's this:
    /eval sys.sendMessage(source, ipbans.isBanned(ipbans.list[0]));
    (18:55:05) true

    and here's where I pull the hair out of my head in frustration. It behaves the exact same for any index, not just 0. I don't understand why it can't find it like this:

    ipbans.list[0] -> 0.2.2.35
    ipbans.list.indexOf(0.2.2.35) -> -1
    ipbans.isBanned(0.2.2.35) -> false

    but doing it all in one step:
    ipbans.list.indexOf(ipbans.list[0]) -> 0
    ipbans.isBanned(ipbans.list[0]) -> true

    The effect of this not working like it should is that the test always fails, so proxy ips are not blocked.
     
  2. TheUnknownOne

    TheUnknownOne Member

    Joined:
    Mar 28, 2011
    Messages:
    988
    Likes Received:
    3
    /eval "0.2.2.35" === ipbans.list[0]
    will probably return false for you.

    Check if there's any gibberish after the IPs in your list (like a space), and remove that from the file. Also, your list might use Windows-style line terminators (\r\n), either split using \r\n or remove all carriage returns from your file.
     
  3. Homura

    Homura Member

    Joined:
    May 22, 2012
    Messages:
    43
    Likes Received:
    0
    You were right, thank you. Carriage Returns were the problem. It works now.
     
  4. ArchZombie

    ArchZombie Member

    Joined:
    Aug 1, 2012
    Messages:
    65
    Likes Received:
    0
    PO Trainer Name:
    ArchZombie0x
    This is why computer science classes are evil....


    JavaScript has a built in hashmap, use that instead of a binary search, it's faster and simpler...

    (18:03:59) [#Watch] server: /eval for (var i = 0; i < 10000; i++) script.f("127.0.0.9") // script.f contains your function
    Exec Time: 35 miliseconds
    Serializer Time: <1 milisecond
    Result:
    <Bool> false
    (18:04:12) [#Watch] server: /eval for (var i = 0; i < 10000; i++) "127.0.0.9" in script.modules.antiproxy.PROXYBANS
    Exec Time: 6 miliseconds
    Serializer Time: <1 milisecond
    Result:
    <Bool> false

    Make an object with keys of the values of the array.
     
    Last edited: Jan 7, 2014