Convert ip array to smallest cidr subnet list in java

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.

Solution

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.