Reduce a list of IPv4 to lowest common CIDR

Question

I have a long list of IP addresses that show some pattern of closeness

Example:

XX.249.91.16  
XX.249.91.21  
XX.249.91.32  
XX.249.91.160  
XX.249.91.165  
XX.249.92.15  
XX.249.92.25  
XX.249.92.51  
XX.249.92.234

and sometimes a whois reveals a range like this

XX.163.224.0 - XX.163.239.255

I would like to create a list of CIDR that gives me the lowest common number

It seems Python already has such a thing - iprange_to_cidrs - but I need it in JavaScript

XX.249.90.0/16

if that is what would handle

XX.249.91.0 - XX.249.92.255

ditto XX.163.200.0/nn to handle

XX.163.224.0 - XX.163.239.255

A calculator that can do it one range at a time when I fiddle with the mask is here http://www.subnet-calculator.com/cidr.php

My preferred language is JavaScript and I have the following start but need the algorithm that does the match and transform

var list = [
    "10.249.91.16",
    "10.249.91.21",
    "10.249.91.32",
    "10.249.91.160",
    "10.249.91.165",
    "10.249.92.15",
    "10.249.92.25",
    "10.249.92.51",
    "10.249.92.234"
]
function dec2bin(ip) { 
    return ip.map(function(num) { 
      return ("00000000"+parseInt(num,10).toString(2)).slice(-8); 
    }).join(".");
}
const result = list.map(ip => dec2bin(ip));

UPDATE after reviewing an answer

FIDDLE

const getDec = ip => {
  let octet = ip.split(".");
  return (octet[0] << 24) | (octet[1] << 16) | (octet[2] << 8) | octet[3];
};

var adr1 = "111.163.224.0";
var adr2 = "111.163.239.255"
var XOR = getDec(adr1)^getDec(adr2);

// now what?

Update 2:

could the result of the range 111.163.224.0 - 111.163.239.255 be 111.163.224.0/20 ? since we have

01101111.10100011.11100000.00000000 - 0,111.163.224.0
01101111.10100011.11101111.11111111 - 0,111.163.239.255

score 9 · Answer 1 · edited Jul 03 '14 at 15:04

What you're looking for is a the set of contiguous high-order bits in the address that don't change across the entire set of addresses. IPv4 addresses are, at their core, 32-bit unsigned integers. The dotted-quad notation is a convenience for humans. It's best to deal with them in that form. Conversion is easy:

integer_ip = (octet1 << 24) | (octet2 << 16) | (octet3 << 8) | octet4

Once you have integers, the right tool for determining which ones change is bitwise exclusive or (^ in many C-derived languages). This is because it detects change, returning a 1 bit if the corresponding bit in the two values differ, and a 0 otherwise.

I'm going to use 8-bit quantities in the examples to keep it readable, but this applies just the same to the 32-bit numbers you'd get from an IP address.

We have to begin with an integer whose bits indicate which bits changed, which is none of them:

changed_bits = 0x00

For each address after the first one, XOR items n and n-1, resulting in the set of bits that changed between the two. Those can the be ORed with our running set of changed bits to add to the set:

a[0] = 0x10
a[1] = 0x11    0x10 ^ 0x11 = 0x01    changed_bits = 0x00 | 0x01 = 0x01
a[2] = 0x1f    0x11 ^ 0x1f = 0x0e    changed bits = 0x01 | 0x0e = 0x0f

The end value of changed_bits, 0x0f, indicates that during all comparisons, the upper four bits didn't change (they're all zeros) and the lower four bits did (all ones). Then all you have to do is count the number of unchanged (zero) bits, starting from the most-significant:

cidr_size = 0;
for ( bit=0 ; bits < 8 ; ++bits ) {   // Use 32 for IPs
    if ( changed_bits & 0x80 ) {      // Use 0x800000 for IPs
        break;  // Stop when we hit the first bit that changed.
    }
    ++cidr_size;
    changed_bits = changed_bits << 1;  // Rotate the next bit into the high spot
}

At this point, cidr_size will hold the number of bits your addresses had in common. Then you can use that to construct a mask with the proper number of bits

mask = 0xff << (8 - cidr_size)  // Use 0xffffffff and 32 for IPs

With that in hand, you can use it against any of the integers in your list to come up with the CIDR block:

cidr_block = a[0] & mask

Convert cidr_block back to octets, add a slash, spit out cidr_size and you're in business.

Addendum:

What's in this answer will get you the lowest common CIDR for an entire list of addresses.

Given just IPs, there's no magic algorithm to determine the CIDR from which they came. Based on what they have in common, the IPs used in the question could be included in any of 13 CIDR blocks as large as 10.0.0.0/8 or as small as 10.249.88.0/20. (Blocks larger than /8 are also possible, but the practical reality is that no block larger than that has ever been issued.)

To properly group the IPs, you would need a database of the CIDRs that have been issued which could be joined with the IPs you have, grouped by CIDR and aggregated to get a count. The only other thing you could get away with is knowing the netmask that goes with each IP, which isn't going to happen because the receiving end doesn't see it.

Thanks for the detailed example - a bit (pun intended) confused as to whether the actual code will change other than where indicated for 32 bits since I am actually only interested in IPs. Also how do I detect that I have a new range? The idea is to come up with 123.456.0.0/x, 234.123.123.123/32, 245.768.111.0/y — mplungjan, Jul 01 '14 at 04:18
@mplungjan: The code shouldn't change other than where indicated. I made a couple of minor edits to the answer and added an addendum that addresses ranges. — Blrfl, Jul 01 '14 at 12:11
The list is 40,000 IPs and I want to create sets of CIDRs based on the list as it looks now. Tomorrow the list will be different. I cannot create a DB of CIDRs but want to group them on the fly — mplungjan, Jul 01 '14 at 12:42
@mplungjan: What you want can't be done with the information you have. A list of IPs contains nothing that would help divine their CIDRs, which leaves you with no way to group them. The best you could do is calculate once CIDR that covers the entire list, but that isn't what you're after. If the IPs you're looking at are from the public Internet, the supplemental information you'd need to get a meaningful result is a database of all issued CIDR blocks globally. — Blrfl, Jul 01 '14 at 13:00

mplungjan · Accepted Answer · 2023-05-12T14:40:32.603

I have updated the solution which gave negative ints when using addresses with 255

fiddle

const dot2dec = ip => {
  const octet = ip.split(".");
  return (octet[0] * 16777216) + (octet[1] * 65536) + (octet[2] * 256) + (octet[3] * 1);
};

const num2dot = num => {
  let d = num % 256;
  num = Math.floor(num / 256);
  let c = num % 256;
  num = Math.floor(num / 256);
  let b = num % 256;
  num = Math.floor(num / 256);
  let a = num % 256;
  return a + "." + b + "." + c + "." + d;
};

const dec2bin = ip =>
  ip
  .split(".")
  .map(num => ("00000000" + parseInt(num, 10).toString(2)).slice(-8))
  .join(".");

const fixNegativeResult = result => result < 0 ? result >>> 0 : result;


$(function() {
  const res1 = $("#res1");
  const adr1 = "255.255.255.0";
  const adr2 = "255.255.255.123";
  //const adr1 = "111.163.224.0";
  //const adr2 = "111.163.239.255"
  res1.append("<hr>" + dot2dec(adr1) + " - " + adr1);
  res1.append("<hr>" + dot2dec(adr2) + " - " + adr2);

  const dec1 = dot2dec(adr1);
  const dec2 = dot2dec(adr2);
  const XOR = num2dot(dec1 ^ dec2);

  const andResult = fixNegativeResult(dec1 & dec2);
  const AND = num2dot(andResult);

  const MASK = dec2bin(XOR).replace(/\./g, "").indexOf("1");

  res1.append("<hr>XOR:" + XOR);
  res1.append("<hr>AND:" + AND);
  res1.append("<hr>MASK:" + MASK + "<hr>");
});

Old solition

Solution was simpler than expected. I appreciate Blrfl's time and explanation but the whole thing boiled down to the number to use is the two addresses ANDed masked by the number of leading 0s in the binary representation of the two addresses XORed

Fiddle

var adr1 = "111.163.224.0",
    adr2 = "111.163.239.255",
    AND  = dot2dec(adr1)&dot2dec(adr2), 
    XOR  = num2dot(dot2dec(adr1)^dot2dec(adr2)),
    mask = dec2bin(XOR).replace(/\./g,"").indexOf("1");

in this case 111.163.224.0/20

I see you wrote a Fiddle with these functions defined. I swapped in my IPs in question and it worked like a charm. https://jsfiddle.net/mplungjan/Lztdnnfy/ — JCotton, Feb 12 '19 at 19:53
I put different IP addresses in `adr1` & `adr2`. Can't share those. I got what I needed using [`cidr-generator`](https://www.npmjs.com/package/cidr-generator) though. — KaKi87, May 12 '23 at 13:41
Here is an update that seems to work better https://jsfiddle.net/mplungjan/rv9p17h3/ — mplungjan, May 12 '23 at 14:35

Reduce a list of IPv4 to lowest common CIDR

2 Answers2