ip-range.js

const fetch = require('node-fetch');
const { deepStrictEqual } = require('assert');

function ipv4ToInt(ip) {
  return ip.split('.').reduce((acc, cur) => acc << 8 | +cur, 0);
}

function intToIpv4(i) {
  return `${i >>> 24}.${i >>> 16 & 0xff}.${i >>> 8 & 0xff}.${i & 0xff}`;
}

function compress(t) {
  if (!t) return false;
  const left = compress(t[0]);
  const right = compress(t[1]);
  if (left && right) {
    delete t[0];
    delete t[1];
    t.mark = true;
  }
  return t.mark;
}

function merge(cidrs) {
  const root = {};
  for (let i = 0; i < cidrs.length; i++) {
    const [ipV4String, lengthString] = cidrs[i].split('/');
    const ipInt = ipv4ToInt(ipV4String);
    const length = +lengthString;

    const shiftEnd = 31 - length;
    let t = root;
    for (let shift = 31; shift > shiftEnd; shift--) {
      const mask = 1 << shift;
      const value = ipInt & mask ? 1 : 0;
      let next = t[value];
      if (next && next.mark) {
        t = undefined;
        break;
      }
      if (!next) {
        next = t[value] = {};
      }
      t = next;
    }
    if (t) { // found
      t.mark = true;
      if (t[0]) {
        delete t[0];
      }
      if (t[1]) {
        delete t[1];
      }
    } else {
      // duplicate
    }
  }

  // console.log(JSON.stringify(root, undefined, 2))
  compress(root);
  // console.log(JSON.stringify(root, undefined, 2))

  const result = [];
  const inverse = [];

  function dfs(t, v, l) {
    if (!t) {
      inverse.push(`${intToIpv4(v)}/${l}`);
      return;
    }
    if (t.mark) {
      result.push(`${intToIpv4(v)}/${l}`);
      return;
    }
    dfs(t[0], v, l + 1);
    dfs(t[1], v | 1 << (31 - l), l + 1);
  }
  dfs(root, 0, 0);

  return { result, inverse };
}

function test(input, expected) {
  const { result } = merge(input);
  deepStrictEqual(result, expected);
}

test(['1.0.0.0/8', '0.0.0.0/8'], ['0.0.0.0/7'])
test(['127.1.0.0/16', '127.0.0.0/16'], ['127.0.0.0/15']);
test(['127.0.0.0/24', '127.0.1.0/24'], ['127.0.0.0/23']);
test(['128.0.0.0/1', '0.0.0.0/1'], ['0.0.0.0/0']);
test([
  '127.0.0.0/23',
  '0.0.0.0/2',
  '64.0.0.0/3',
  '96.0.0.0/4',
  '112.0.0.0/5',
  '120.0.0.0/6',
  '124.0.0.0/7',
  '126.0.0.0/8',
  '127.0.2.0/23',
  '127.0.4.0/22',
  '127.0.8.0/21',
  '127.0.16.0/20',
  '127.0.32.0/19',
  '127.0.64.0/18',
  '127.0.128.0/17',
  '127.1.0.0/16',
  '127.2.0.0/15',
  '127.4.0.0/14',
  '127.8.0.0/13',
  '127.16.0.0/12',
  '127.32.0.0/11',
  '127.64.0.0/10',
  '127.128.0.0/9',
  '128.0.0.0/1'], ['0.0.0.0/0']);


const ipListUrl = 'https://raw.githubusercontent.com/misakaio/chnroutes2/master/chnroutes.txt';

// https://zh.wikipedia.org/wiki/%E4%BF%9D%E7%95%99IP%E5%9C%B0%E5%9D%80
const reserved = [
  '0.0.0.0/8',
  '10.0.0.0/8',
  '100.64.0.0/10',
  '127.0.0.0/8',
  '169.254.0.0/16',
  '172.16.0.0/12',
  '192.0.0.0/24',
  '192.0.2.0/24',
  '192.88.99.0/24',
  '192.168.0.0/16',
  '198.18.0.0/15',
  '198.51.100.0/24',
  '203.0.113.0/24',
  '224.0.0.0/4',
  '240.0.0.0/4',
  '255.255.255.255/32',
]

async function main() {
  const res = await fetch(ipListUrl);
  const body = await res.text();
  const cidrs = body.split('\n')
    .map(l => l.trim())
    .filter(l => l && !l.startsWith('#'))
    .map(l => {
      return l;
      // if we want roughly
      const [ip, length] = l.split('/');
      if (+length < 16) {
        return l;
      }
      return ip.split('.').slice(0, 2).join('.') + '.0.0/16'
    })
    .concat(reserved);
  const { result, inverse } = merge(cidrs);
  // console.log(cidrs.length, result.length, inverse.length)
  // console.log(inverse.join(','))
  console.log(
    ['#!/bin/sh']
      .concat(
        result.map(r => `/sbin/route add ${r} -interface $6`)
      )
      .join('\n')
  );
}

main();