Convert ip array to smallest cidr subnet list in java

Question

I have an ip array like below and I want to convert it to smallest cidr subnet list. Is there a library for that in Java?

For example:

1.1.3.0
1.1.3.1
1.1.3.2
1.1.3.3
..
1.1.3.254
1.1.3.255
1.2.3.0
1.2.3.1
1.2.3.2
1.2.3.3
..
1.2.3.254
1.2.3.255
1.3.3.0
1.3.3.1
1.3.3.2
1.3.3.3
..
1.3.3.128
1.3.3.129

converted to

1.1.3.0/24
1.2.3.0/24
1.3.3.0/25
1.3.3.128/31

Thanks in advance.

Answer 1

I don't know whether there is a library available in Java. Indeed, I know little about Java :) But I can give you an algorithm for solving the problem, if that is any help.

1) Convert the ip addresses into pairs of integers, where the first integer is the binary representation of the ip address (a.b.c.d -> a << 24 + b << 16 + c << 8 + d) and the second integer is 32 (that is, initially each address is it's own subnet [1]).

2) Sort the list of pairs.

3) Now scan the sorted list, starting at the second pair. For each pair, if you can combine it with the previous one, do so and continue to try until combining as long as possible. Two pairs [base1, bits1] and [base2, bits2] can be combined if bits1 == bits2 and base2 ^ base1 == 1 << (32 - bits1). In that case, the combination is [base1, bits1 - 1].

4) Finally, convert the pairs back into CIDR notation: the first integer is the base of the subnet (when converted back to dotted decimal) and the second integer is the bitwidth.

Both steps 2 and 3 are O(n log n)

Footnote 1: In your example, you don't include the addresses with last byte 0, which means my algorithm will fail in your test case. You'd have to add them to the list. This point reveals a subtle but important detail in the definition of what a CIDR subnet is: technically, the smallest possible subnet is /30, because both the first and last ip of the range are reserved. Consequently /31 would have no valid IP addresses. However, people often use the term CIDR subnet to mean "a bitmask which recognizes a set of IP addresses", as in their use as filter expressions.

Answer 2

There is a library available in Java for this. The open-source IPAddress Java library has methods for merging addresses into prefix block subnets. Disclaimer: I am the project manager of the IPAddress library.

The following method "merge" shows the code, relying on the method mergeToPrefixBlocks from the library:

static String[] merge(List<String> strs) {
    // convert first to address
    IPAddress first = new IPAddressString(strs.get(0)).getAddress();
    // convert remaining to address
    IPAddress others[] = strs.subList(1, strs.size()).stream().map(str -> new IPAddressString(str).getAddress()).toArray(IPAddress[]::new);
    // merge them all
    IPAddress[] blocks = first.mergeToPrefixBlocks(others);
    // convert back to strings
    return Arrays.stream(blocks).map(block -> block.toString()).toArray(String[]::new);
}

The method can be demonstrated with your set of example addresses as shown with the following code:

ArrayList<String> strs = new ArrayList<>();
String firstPref = "1.1.3.";
String secondPref = "1.2.3.";
String thirdPref = "1.3.3.";
for(int i = 0; i <= 255; i++) {
    strs.add(firstPref + i);
    strs.add(secondPref + i);
}           
for(int i = 0; i <= 129; i++) {
    strs.add(thirdPref + i);
}
String result[] = merge(strs);
System.out.println("blocks are " + Arrays.asList(result));

The output is:

blocks are [1.3.3.128/31, 1.3.3.0/25, 1.1.3.0/24, 1.2.3.0/24]

Answer 3

Try as :

public class Test {
    public static void main(String[] args) {
        String[] ipArray1 = new String[]{"1.1.3.1", "1.1.3.3", "1.1.3.2", "1.3.3.254"};
        String[] ipArray2 = new String[ipArray1.length];
        for(int i=0; i < ipArray1.length; i++) {
            String temp = ipArray1[i];
            ipArray2[i] = temp.substring(0,6) + "0/24";
        }
        for(String  ip : ipArray2) {
            System.out.println(ip);
        }
    }
}

Output :

    1.1.3.0/24
    1.1.3.0/24
    1.1.3.0/24
    1.3.3.0/24