Search code examples
javascriptserializationcomparisonip-address

compare list of IP ranges and short it to uniq ranges

I have a list of IP ranges (taken from CIDR with script giving start address and end address) and I'm trying to get unique ranges (currently doing it by hand)

118.184.192.0-118.184.223.255
118.187.0.0-118.187.255.255
118.187.0.0-118.187.63.255
118.187.64.0-118.187.127.255
118.191.4.0-118.191.5.255
118.191.6.0-118.191.7.255
118.191.8.0-118.191.11.255
118.191.12.0-118.191.12.255

Line 3 118.187.0.0-118.187.63.255 and line 4 118.187.64.0-118.187.127.255 could be shortened to 118.187.0.0-118.187.127.255 because 63.255 (+1) is 64.0

Could anyone give me a hint how can this be done by a script?

Current approach would be comparing Line3 2nd ip with Line4 1st ip by 'adding one' to first compared ip and checking if it is the same as second compared ip

// 118.187.63.255 (+1) = 118.187.64.0
var x = "118.187.63.255".split('.')
var y = "118.187.64.0".split('.')
var compare=0;
var thesamerange=0;
for(var i=0;i<4;i++){
  if(x[i] === y[i]){
    compare=0;
  }else{
    if((parseInt(x[i])+1)===parseInt(y[i])){
      compare=1 }
  }
  if(compare === 1){
    if( (x[i+1])==255 && (y[i+1])==0 ){
      thesamerange=1 }
  }
}

Is there an easier way to 'shorten the list' with unique ranges?

Solution

  • Here are some hints that should help you to solve the problem yourself:

    1. IP-addresses can be fully converted to numbers, and vice versa. (Explanation for Java).
    2. Check whether ranges overlap (should be joined) by whether one's endpoint is included in the other range.

    If you want a complete guide to how you may solve your issue, read on.

    Joining ranges

    What can be joined?

    First we need to decide what ranges may be joined, which includes:

    • Ranges that overlap:
      • Partly overlapping ranges.
      • Ranges where one is a subrange of the other.
    • Ranges whose endpoints are immediate neighbours. (Ranges that are "touching".)

    Sidenote: These two statements are equivalent:

    1. Range [a1, a2] and [b1, b2] are neighbours.
    2. Range [a1, a2] (partly) overlaps [b1 - 1, b2 + 1]. (Or vice versa.)

    Overlapping ranges will still overlap after "extension" (statement 2). We will make use of this later on.

    Convert to simpler type

    Now that we know the conditions for joining, we need to be able to check them.

    For easier checking, we can convert the IP-addresses to integers:

    • From dot-notation:
      Interpret IP-address as a base-256 4-"digit" number, where a digit is a dot-separated integer.
    • To dot-notation:
      1. Parse number to a 8-digit hexadecimal number (with leading zeros, if necessary).
      2. Interpret every two base-16 digits as one base-256 digit.
      3. Parse the four base-256 digits to numbers.
      4. Join the numbers with dots.

    const ip = "192.168.0.1";

console.log("IP:", ip);
console.log("IP as number:", fromIp(ip));
console.log("IP after roundtrip:", toIp(fromIp(ip)));

function fromIp(ip) {
  const numbers = ip.split(".").map(split => Number(split));
  
  const ipAsNumber = numbers.reverse().reduce((total, number, i) => {
    return total + number * (256 ** i);
  }, 0);
  
  return ipAsNumber;
}
function toIp(number) {
  const numberInHex = number.toString(16).padStart(8, "0");
  
  const hexSplits = Array.from({length:4}, (v, i) => numberInHex.slice(i * 2, i * 2 + 2));
  const ipSplits = hexSplits.map(hex => parseInt(hex, 16));
  
  return ipSplits.join(".");
}

    How to check joinability

    Realizing the checking may become easier to understand if we visualize the conditions:

    Four lines representing ranges (math.: intervals). Three lines fulfill the join conditions with a fourth line: 1. One is fully enclosed in the fourth. 2. One is partly overlapping the fourth. 3. One is immediately next to (touching) the fourth.

    Notice how the lines A, C, D may be joined with line B. Their commonality is (abstractly):

    • The joinable line's left end is to the left of B's right end.
    • The joinable line's right end is to the right of B's left end.

    Or, in code:

    // Similar to the visualization
const rangeA = { from: 0, to: 3 };
const rangeB = { from: 2, to: 6 };
const rangeC = { from: 3, to: 4 };
const rangeD = { from: 5, to: 7 };

// Not "touching" rangeB
const unjoinableRange = { from: rangeB.to + 2, to: 10 };

console.log("Can join A & B?", isJoinable(rangeA, rangeB));
console.log("Can join C & B?", isJoinable(rangeC, rangeB));
console.log("Can join D & B?", isJoinable(rangeD, rangeB));

console.log("Joinable with unjoinable?", isJoinable(rangeB, unjoinableRange));

function isJoinable(range1, range2) {
  const maxDiff = 1; // Extend by this much; aforementioned stmt. 2 in "What can be joined?"
  return (range1.from - range2.to) <= maxDiff && (range2.from - range1.to) <= maxDiff;
}
    .as-console-wrapper {max-height:100%!important}

    Joining

    With the above sections we can easily find what ranges may be joined. But we still have to actually join them together.

    For that, we can use Array.reduce() to collect the (joined) ranges as follows:

    // Ranges A,B,C,D from before
const joinableRanges = [
  { from: 2, to: 6 },
  { from: 0, to: 3 },
  { from: 3, to: 4 },
  { from: 5, to: 7 }
];

const unjoinableRanges = [
  { from: 9, to: 10 },
  { from: -6, to: -2 }
];

const ranges = [...joinableRanges, ...unjoinableRanges];
const joinedRanges = reduceRanges(ranges);

console.log("Original:", ranges);
console.log("Reduced:", joinedRanges);

function reduceRanges(rangesToReduce) {
  const reducedRanges = rangesToReduce.reduce((ranges, range) => {
    let joinWith = range; // Start checking for current range
    const nextJoinableRange = () => ranges.find(r =>
      r !== joinWith // Avoid joining with self
      && isJoinable(r, joinWith)
    );
    
    let joinableRange = nextJoinableRange();
    
    if (!joinableRange) {
      // No joinable range was found; add current range
      ranges.push(range);
      return ranges;
    }
    
    // A joinable range was found
    
    do {
      // Remove joinable range; will be replaced with joined range
      const index = ranges.indexOf(joinableRange);
      ranges.splice(index, 1);
      
      // Add joined range
      const joinedRange = {
        from: Math.min(joinableRange.from, joinWith.from),
        to: Math.max(joinableRange.to, joinWith.to)
      };
      ranges.push(joinedRange);
      
      // Continue with (checking for) joining
      joinWith = joinedRange;
    } while (joinableRange = nextJoinableRange());
    
    return ranges;
  }, []);
  
  return reducedRanges;
}

function isJoinable(range1, range2) {
  return (range1.from - range2.to) <= 1 && (range2.from - range1.to) <= 1;
}
    .as-console-wrapper {max-height:100%!important}

    Finally

    Putting everything together:

    1. Convert from IP-address ranges to number ranges.
    2. Join ranges:
      1. If current range is unjoinable, collect.
      2. Otherwise, join with joinable range.
      3. Replace joinable range with joined range.
      4. Repeat for joined range from 2.
    3. Convert from number ranges

    const ipRanges = [
  { from: "118.184.192.0", to: "118.184.223.255" },
  { from: "118.187.0.0", to: "118.187.255.255" },
  { from: "118.187.0.0", to: "118.187.63.255" },
  { from: "118.187.64.0", to: "118.187.127.255" },
  { from: "118.191.4.0", to: "118.191.5.255" },
  { from: "118.191.6.0", to: "118.191.7.255" },
  { from: "118.191.8.0", to: "118.191.11.255" },
  { from: "118.191.12.0", to: "118.191.12.255" }
];

const numberRanges = ipRanges.map(({ from, to }) =>
  ({ from: fromIp(from), to: fromIp(to) })
);

const joinedRanges = reduceRanges(numberRanges);

const joinedIpRanges = joinedRanges.map(({ from, to }) =>
  ({ from: toIp(from), to: toIp(to) })
);

console.log("IP-ranges:", ipRanges );
console.log("Reduced IP-ranges:", joinedIpRanges);

function reduceRanges(rangesToReduce) {
  const reducedRanges = rangesToReduce.reduce((ranges, range) => {
    let joinWith = range;
    const nextJoinableRange = () => ranges.find(r =>
      r !== joinWith && isJoinable(r, joinWith)
    );
    
    let joinableRange = nextJoinableRange();
    
    if (!joinableRange) {
      ranges.push(range);
      return ranges;
    }
    
    do {
      const index = ranges.indexOf(joinableRange);
      ranges.splice(index, 1);
      
      const joinedRange = {
        from: Math.min(joinableRange.from, joinWith.from),
        to: Math.max(joinableRange.to, joinWith.to)
      };
      ranges.push(joinedRange);
      
      joinWith = joinedRange;
    } while (joinableRange = nextJoinableRange());
    
    return ranges;
  }, []);
  
  return reducedRanges;
}

function isJoinable(range1, range2) {
  return (range1.from - range2.to) <= 1 && (range2.from - range1.to) <= 1;
}

function fromIp(ip) {
  const numbers = ip.split(".").map(split => Number(split));

  const ipAsNumber = numbers.reverse().reduce((total, number, i) => {
    return total + number * (256 ** i);
  }, 0);

  return ipAsNumber;
}
function toIp(number) {
  const numberInHex = number.toString(16).padStart(8, "0");

  const hexSplits = Array.from({length:4}, (v, i) => numberInHex.slice(i * 2, i * 2 + 2));
  const ipSplits = hexSplits.map(hex => parseInt(hex, 16));

  return ipSplits.join(".");
}
    .as-console-wrapper {max-height:100%!important}

    This answer includes only how to join IP-address ranges.

    As apparent in your answer, you receive the ranges in a specific format (ranges as start-end, one per line). You may still want to convert from that format to some easier-to-work-with object. See this as an exercise!