CODEWITHSUNDEEP
javaalgorithm
Rock
Rock

Reputation: 2977

Interval Partitioning on IP address range

I'm dealing with a problem to partition specific IP address ranges (in Java). Suppose I have:

startIP    endIP
1.2.3.4    1.2.5.6

and I need cut this range into every [0, 255] interval so we have:

startIP    endIP
1.2.3.4    1.2.3.255
1.2.4.0    1.2.4.255
1.2.5.0    1.2.5.6

I'm looking at this problem more or less like partitioning a decimal range for instance from 7 to 26 and we have [7, 9], [10, 19], [20, 26]. The only difference is we are dealing with 256-simal numbers. Any ideas, folks? Thank you!

Upvotes: 2

Views: 600

Answers (4)

user267885
user267885

Reputation:

I wouldn't know the specific solution for Java, but there is an algorithm in C. It will partition the IP range to largest possible subnets and print them. The resulting ranges will be aligned on subnet boundaries.

#define NETWORK_ZEROS(ip, prefix) ((ip) & (0xffffffff << (32 - (prefix))))
#define NETWORK_ONES(ip, prefix) ((ip) | (~ (0xffffffff << (32 - (prefix)))))

void print_ip(unsigned long ip)
{
    unsigned char bytes[4];
    bytes[0] = ip & 0xFF;
    bytes[1] = (ip >> 8) & 0xFF;
    bytes[2] = (ip >> 16) & 0xFF;
    bytes[3] = (ip >> 24) & 0xFF;       
    printf("%d.%d.%d.%d", bytes[3], bytes[2], bytes[1], bytes[0]);        
}

void partition_ip(unsigned long start, unsigned long stop)
{   
    int i;

    while (start < stop)
    {
        // Change the start of the loop to 24 if you 
        // need to align on /24 boundaries
        for (i=0; i <= 32; i++)
        {
            if (NETWORK_ZEROS(start, i) == start && 
                    NETWORK_ONES(start, i) <= stop)
            {
                print_ip(NETWORK_ZEROS(start, i));
                printf(" - ");
                print_ip(NETWORK_ONES(start, i));
                printf("\n");

                start = NETWORK_ONES(start, i) + 1;
                break;
            }
        }

    }
}

To convert IP to binary number just do something like this

a.b.c.d => ((((a*256)+b)*256)+c)*256+d

or

ip = (a << 24) | (b << 16) | (c << 8) | d

if you want it to be more efficient by utilizing bit shifting.

Upvotes: 1

Mihai Toader
Mihai Toader

Reputation: 12243

Some sample code (assumes the initial translation to a int[] is done outside) and which doesn't really return useful data (just prints). But the idea is there. 

public class Convertor {
    public static void convert(int []a, int []b) {
        int left = (a[0] << 24) | (a[1] << 16) | (a[2] << 8) | a[3];
        int right = left | 0xff;
        int end = (b[0] << 24) | (b[1] << 16) | (b[2] << 8) | b[3];
        while ( right < end ) {
            System.out.printf("%s -> %s\n", toIp(left), toIp(right));
            left = right + 1; right += 256;
        }
        System.out.printf("%s -> %s\n", toIp(left), toIp(end));
    }

    private static String toIp(int value) {
        return String.format("%d.%d.%d.%d",
                             value >> 24 & 0xFF,
                             value >> 16 & 0xFF,
                             value >> 8 & 0xFF,
                             value & 0xFF);
    }
}

call site:

Convertor.convert(new int[]{1, 2, 3, 4}, new int[]{1, 2, 5, 6});

output:

1.2.3.4 -> 1.2.3.255
1.2.4.0 -> 1.2.4.255
1.2.5.0 -> 1.2.5.6

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726599

You can use InetAddress for this, and run a straightforward loop to do the increments:

InetAddress from = InetAddress.getByName("1.2.3.4");
InetAddress to = InetAddress.getByName("1.2.5.6");
byte[] partsTo = to.getAddress();
for (;;) {
    System.out.print(from+" - ");
    byte[] parts = from.getAddress();
    boolean sameUpperPart = true;
    for (int i = 0 ; sameUpperPart && i < parts.length-1 ; i++) {
        sameUpperPart &= (partsTo[i] == parts[i]);
    }
    if (sameUpperPart) {
         System.out.println(to);
         break;
    }
    int last = parts.length-1;
    parts[last] = (byte)0xFF;
    System.out.println(InetAddress.getByAddress(parts));
    parts[last] = 0x00;
    for (int i = last-1 ; i >= 0 ; i--) {
        if (++parts[i] != 0) {
            break;
        }
    }
    from = InetAddress.getByAddress(parts);
}

This code produces the following output on ideone:

/1.2.3.4 - /1.2.3.255
/1.2.4.0 - /1.2.4.255
/1.2.5.0 - /1.2.5.6

Upvotes: 2

Joe K
Joe K

Reputation: 18424

First convert the IP address into a single integer, then partition by just adding 256 repeatedly, and converting back to an IP address.

public class IPPartition {
    public static void main(String[] args) {
        String startIP = "1.2.3.4";
        String endIP = "1.2.5.6";
        long start = toLong(startIP);
        long end = toLong(endIP);
        long last = start;
        long part = (start / 256 + 1) * 256;
        for (; part < end; last = part, part += 256) {
            System.out.println(toIP(last) + " " + toIP(part));
        }
        System.out.println(toIP(last) + " " + toIP(end));
    }

    private static long toLong(String ip) {
        String[] tokens = ip.split("\\.");
        long sum = 0;
        for (int i = 0; i < 4; i++) {
            sum *= 256;
            sum += Integer.parseInt(tokens[i]);
        }
        return sum;
    }


    private static String toIP(long num) {
        String result = "";
        for (int i = 0; i < 4; i++) {
            long section = num % 256;
            result = section + result;
            if (i < 3) result = "." + result;
            num /= 256;
        }
        return result;
    }
}

I used longs here just to be safe, but you might be able to use integers, I haven't tried it. There could also be some off-by-one errors or something, I haven't tested it thoroughly.

Upvotes: 1

Related Questions