In Java, given the range of IP addresses, return the minimum list of CIDR blocks that span the range

Question

I'm having problems with some logic for converting a range of IP addresses to a list of CIDR blocks. I believe this site is doing it right: http://ip2cidr.com/

I would like to pass the start IP address and the end IP address and deduce Java from the minimum list of CIDR blocks needed to cover only the passed range and nothing more.

For example, if I pass the start address 1.1.1.111 and the end address 1.1.1.120, I would expect to receive in return: 1.1.1.111/32 1.1.1.112/29 1.1.1.120/32

(with a / 32 symbol indicating one address.)

Answer 1

In my last answer there were some errors that occurred when the first octet of the IP address was too large. It works better. Raised almost completely 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.

A CIDR block is nothing more than a series of binary numbers with a common prefix and all possible suffixes. Assume for example below, there were 8-bit IP addresses, with classes /1 , ... to /8 .

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

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

You will see that all numbers have a common prefix of 11 , but our list does not contain all of these numbers. Therefore, we must break it into two lists: one with 110 and one with 111 . The first contains only one number, so we make from it /8 block ( 111/8 ).

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

So, now we only expand to 32 bits instead of 8 and implement it in Java, and you are ready.

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

Answer 3

I ended up trying some PHP code that I found and customized for my needs. Below is the class I hit.

 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 have a few helper methods that clutter things up for the purpose of this question. But you can get a general idea.

Answer 4

The following CIDR blocks include, but are not limited to, the address range 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 

and etc.