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.