CODEWITHSUNDEEP
mathip
Edi Wang
Edi Wang

Reputation: 3637

Optimize a simple arithmetic which matches IP range

I want to check if an IP address is in a certain range, matching by "*" only. For example, "202.121.189.8" is in "202.121.189.*".

The scenario is that I have a list of banned IPs, some of them contains "*", so I wrote a function, it works fine so far:

static bool IsInRange(string ip, List<string> ipList)
{
    if (ipList.Contains(ip))
    {
        return true;
    }

    var ipSets = ip.Split('.');
    foreach (var item in ipList)
    {
        var itemSets = item.Split('.');
        for (int i = 0; i < 4; i++)
        {
            if (itemSets[i] == "*")
            {
                bool isMatch = true;
                for (int j = 0; j < i; j++)
                {
                    if (ipSets[i - j - 1] != itemSets[i - j - 1])
                    {
                        isMatch = false;
                    }
                }
                if (isMatch)
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Test code:

string ip = "202.121.189.8";
List<string> ipList = new List<string>() { "202.121.168.25", "202.121.189.*" };

Console.WriteLine(IsInRange(ip, ipList));

But I think what i wrote is very stupid, and I want to optimize it, does anyone have an idea how to simplify this function? not to use so many "for....if...".

Upvotes: 0

Views: 171

Answers (4)

Vlad
Vlad

Reputation: 35594

A good idea would be to represent the banned subnets in a form of a pair: mask + base address. So your check will look like that:

banned = (ip & mask == baseaddress & mask);

For 11.22.33.* the base address will be 11*0x1000000 + 22*0x10000 + 33*0x100, mask will be 0xffffff00.

For single address 55.44.33.22 the address will be 55*0x1000000 + 44*0x10000 * 33*0x100 + 22, mask will be 0xffffffff.

You'll need to convert the address to a 32-bit int as a separate procedure.

After that all, your code will look like that:

int numip = ip2int(ip);
bool isIpBanned = banList.Any(item =>
            numip & item.mask == item.baseaddress & item.mask);

By the way, this way you'll be able to represent even bans on smaller subsets.

int ip2int(string ip) // error checking omitted
{
    var parts = ip.Split('.');
    int result = 0;
    foreach (var p in parts)
        result = result * 0x100 + int.Parse(p);
}


class BanItem { public int baseaddres; public int mask; }

BanItem ip2banItem(string ip)
{
    BanItem bi = new BanItem() { baseaddres = 0, mask = 0 };
    var parts = ip.Split('.');
    foreach (var p in parts)
    {
        bi.baseaddress *= 0x100;
        bi.mask *= 0x100;
        if (p != "*")
        {
            bi.mask += 0xff;
            bi.baseaddress += int.Parse(p);
        }
    }
    return bi;
}

banList = banIps.Select(ip2banItem).ToList();

Upvotes: 1

Cybercartel
Cybercartel

Reputation: 12592

I would use a space filling curve like in the xkcd comic: http://xkcd.com/195/. It's the function H(x,y) = (H(x),H(y)) and it reduces the 2 dimension to 1 dimension. It would also show that you are a real b*** coder.

Upvotes: 0

mlishn
mlishn

Reputation: 1667

Written In Java (Untested):

static boolean IsInRange(String ip, Vector<String> ipList) {
    int indexOfStar = 0;
    for (int i=0; i<ipList.size(); i++) {
        if (ipList.contains("*")) {
            indexOfStar = ipList.indexOf("*");
            if ((ip.substring(0, indexOfStar)).equals(ipList.get(i).substring(0, indexOfStar))) {
                return true;
            }
        }
    }
    return false;
}

Upvotes: 0

Algorithmist
Algorithmist

Reputation: 6695

I think you should keep a separate list for IP with * and those without asterick.

say IpList1 contains IP's without * and

IpList2 --those contain * ..actually what we will be storing is the part before .* in this list. for e.g. 202.121.189.* would be stored as 202.121.189 only..

Thus for a given IP addrerss you just need to check for that IP address in IpList1,if it is not found over there then for each Ip in IPList 2 you need to check whether it is a substring of input IP or not.

Thus no requirement of complex for and if loops.

Upvotes: 1

Related Questions