In Java, given an IP Address range, return the minimum list of CIDR blocks that covers the range

Question

I am having trouble with some of the logic in converting an IP Address range into a list of CIDR blocks. I do believe that this website is doing it right: http://ip2cidr.com/

I would like to pass in a starting IP address and an ending IP address and have the java spit out the minimum list of CIDR blocks required to cover only the range passed in and nothing more.

For instance, if I pass in a start address of 1.1.1.111 and an end address of 1.1.1.120, I would expect to get in return: 1.1.1.111/32 1.1.1.112/29 1.1.1.120/32

(with the /32 indicating a single address.)

Answer 1

My last answer had some bugs in it that came about when the first octet of the IP address was too big. This one works better. Lifted almost entirely from here: http://facedroid.blogspot.com/2010/06/ip-range-to-cidr.html

import java.util.ArrayList;
import java.util.List;

public class RangeToCidr {
    public static List<String> range2cidrlist( String startIp, String endIp ) {         
        long start = ipToLong(startIp);         
        long end = ipToLong(endIp);           

        ArrayList<String> pairs = new ArrayList<String>();         
        while ( end >= start ) {             
            byte maxsize = 32;             
            while ( maxsize > 0) {                 
                long mask = CIDR2MASK[ maxsize -1 ];                 
                long maskedBase = start & mask;                 

                if ( maskedBase != start ) {                     
                    break;                 
                }                 

                maxsize--;             
            }               
            double x = Math.log( end - start + 1) / Math.log( 2 );             
            byte maxdiff = (byte)( 32 - Math.floor( x ) );             
            if ( maxsize < maxdiff) {                 
                maxsize = maxdiff;             
            }             
            String ip = longToIP(start);             
            pairs.add( ip + "/" + maxsize);             
            start += Math.pow( 2, (32 - maxsize) );         
        }         
        return pairs;     
    }       

    public static final int[] CIDR2MASK = new int[] { 0x00000000, 0x80000000,             
        0xC0000000, 0xE0000000, 0xF0000000, 0xF8000000, 0xFC000000,             
        0xFE000000, 0xFF000000, 0xFF800000, 0xFFC00000, 0xFFE00000,             
        0xFFF00000, 0xFFF80000, 0xFFFC0000, 0xFFFE0000, 0xFFFF0000,             
        0xFFFF8000, 0xFFFFC000, 0xFFFFE000, 0xFFFFF000, 0xFFFFF800,             
        0xFFFFFC00, 0xFFFFFE00, 0xFFFFFF00, 0xFFFFFF80, 0xFFFFFFC0,             
        0xFFFFFFE0, 0xFFFFFFF0, 0xFFFFFFF8, 0xFFFFFFFC, 0xFFFFFFFE,             
        0xFFFFFFFF };       

    private static long ipToLong(String strIP) {         
        long[] ip = new long[4];         
        String[] ipSec = strIP.split("\\.");         
        for (int k = 0; k < 4; k++) {             
            ip[k] = Long.valueOf(ipSec[k]);         
        }         

        return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + ip[3];     
    }       

    private static String longToIP(long longIP) {         
        StringBuffer sb = new StringBuffer("");         
        sb.append(String.valueOf(longIP >>> 24));         
        sb.append(".");         
        sb.append(String.valueOf((longIP & 0x00FFFFFF) >>> 16));         
        sb.append(".");         
        sb.append(String.valueOf((longIP & 0x0000FFFF) >>> 8));         
        sb.append(".");         
        sb.append(String.valueOf(longIP & 0x000000FF));   

        return sb.toString();     
    } 
}

Answer 2

You need to understand binary numbers, nothing more.

An CIDR block is nothing else than a series of binary numbers with common prefix and all possible suffixes. Assume for the example below we had 8-bit IP-addresses, with classes /1, ... to /8.

In your case (ignoring the 1.1.1 for now), we write your numbers as binary numbers:

 1101111   - 111
 1110000   - 112
 1110001   - 113
   ...
 1110110   - 118
 1110111   - 119
 1111000   - 120

You'll see that all numbers have a common 11 prefix, but our list does not contain all these numbers. So we have to split it in two lists - one with 110 and one with 111. The first contains only one number, so we make a /8 block out of it (111/8).

The other list (from 112 to 120) contains not all numbers with 111 (since then it would go up to 127), so we split again - one list with 1110, the other with 1111. The first one is now the complete block 1110???? (or 112/4), the second one is only one single address, namely 11111000 (or 120/8).

So, now only extend to 32 bit instead of 8, and implement in Java, and you are ready.

In mathematical terms, one block always goes from x * 2^n to (x+1) * 2^n - 1, and we then use 32 - n as the block-size suffix. So you only need to find the next multiple of some power of two.

Answer 3

I ended up repurposing some PHP code I had found and tweaking to my needs. Below is the class I ended up with.

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class RangeToCidr {
    private static final String IP_ADDRESS = "(\\d{1,3})\\.(\\d{1,3})\\.(\\d{1,3})\\.(\\d{1,3})";
    private static final Pattern addressPattern = Pattern.compile(IP_ADDRESS);

    public static List<String> rangeToCidrList(String istart, String iend)  {       
        int start = toInteger(istart);
        int end = toInteger(iend);

        List<String> result = new ArrayList<String>();

        while (end >= start) {
            int maxsize = imaxblock( start, 32);
            double x = (Math.log(end - start + 1) / Math.log(2) ) ;
            int maxdiff = (int) (Math.floor(32 - Math.floor(x)));

            String ip = intToIP(start);
            if (maxsize < maxdiff) {
                maxsize = maxdiff;
            }
            result.add( ip + "/" + (int)maxsize );
            start += Math.pow(2, (32-maxsize));
        }
        return result;
    }

    private static int toInteger(String address) {
        Matcher matcher = addressPattern.matcher(address);
        if (matcher.matches()) {
            return matchAddress(matcher);
        }
        else
            throw new IllegalArgumentException("Could not parse [" + address + "]");
    }

    private static int matchAddress(Matcher matcher) {
        int addr = 0;
        for (int i = 1; i <= 4; ++i) { 
            int n = (rangeCheck(Integer.parseInt(matcher.group(i)), -1, 255));
            addr |= ((n & 0xff) << 8*(4-i));
        }
        return addr;
    }

    private static int rangeCheck(int value, int begin, int end) {
        if (value > begin && value <= end) // (begin,end]
            return value;

        throw new IllegalArgumentException("Value [" + value + "] not in range ("+begin+","+end+"]");
    }

    private static String intToIP(int val) {
        int octets[] = new int[4];
        for (int j = 3; j >= 0; --j)
            octets[j] |= ((val >>> 8*(3-j)) & (0xff));

        StringBuilder str = new StringBuilder();
        for (int i =0; i < octets.length; ++i){
            str.append(octets[i]);
            if (i != octets.length - 1) {
                str.append("."); 
            }
        }
        return str.toString();
    }

    private static long imask(int t)    {
        return (long)(Math.pow(2, 32) - Math.pow(2, 32-t) ) ;
    }

    private static int imaxblock(long ibase, int tbit)  {
        while (tbit > 0)    {
            long im = imask(tbit-1);
            long imand = ibase & im ;
            if (imand != ibase) {
                break;
            }
            tbit--;
        }
        return tbit;
    }
}

I've got a few helper methods in there that, for the purposes of this question, clutter things up. But you can get the general idea.

Answer 4

The following CIDR blocks contain (not limited to) the range of addresses 1.1.1.111 - 1.1.1.120

/1 - /27

address   prefix   network    DirectedBroadcast 
1.1.1.111   /27    1.1.1.96   1.1.1.127
1.1.1.111   /26    1.1.1.64   1.1.1.127
1.1.1.111   /25    1.1.1.0    1.1.1.127
1.1.1.111   /24    1.1.1.0    1.1.1.255

etc.

Answer 5

The open-source IPAddress Java library can do this for you. Disclaimer: I am the project manager of the IPAddress library.

Here is a sample method to do it:

static void toPrefixBlocks(String str1, String str2) {
    IPAddressString string1 = new IPAddressString(str1);
    IPAddressString string2 = new IPAddressString(str2);
    IPAddress one = string1.getAddress(), two = string2.getAddress();
    IPAddressSeqRange range = one.spanWithRange(two);
    System.out.println("starting with range " + range);
    IPAddress blocks[] = range.spanWithPrefixBlocks();
    System.out.println("prefix blocks are " + Arrays.asList(blocks));
}

Using your example:

toPrefixBlocks("1.1.1.111","1.1.1.120");

The output is:

starting with range 1.1.1.111 -> 1.1.1.120
prefix blocks are [1.1.1.111/32, 1.1.1.112/29, 1.1.1.120/32]