Skip to content

Instantly share code, notes, and snippets.

@winguse
Created April 6, 2020 08:16
Show Gist options
  • Save winguse/0b486ca87dd2cbca6c084678820cfb59 to your computer and use it in GitHub Desktop.
Save winguse/0b486ca87dd2cbca6c084678820cfb59 to your computer and use it in GitHub Desktop.
const fs = require('fs')
const http = require('http');
// https://ftp.arin.net/pub/stats/arin/delegated-arin-extended-latest
// https://ftp.apnic.net/stats/apnic/delegated-apnic-latest
/**
* get content from URL
* @param {String} url URL
* @returns {Promise<String>} the response body of input URL
*/
async function get(url) {
return new Promise((resolve, reject) =>
http.get(url, res => {
if (res.statusCode === 200) {
let data = '';
res.on('data', chunk => data += chunk)
res.on('end', () => resolve(data))
res.on('error', e => reject(e))
} else {
reject(`Get ${url} status code: ${res.statusCode}.`)
}
})
);
}
/**
* get content from local file path
* @param {String} path local file path
* @returns {Promise<String>} the file content of input file path
*/
async function readFile(path) {
return new Promise((resolve, reject) => {
fs.readFile(path, (err, data) => {
if (err) {
reject(err)
} else {
resolve(data.toString())
}
})
})
}
/**
* The marks for {IPNode}s
*/
const Marks = {
Empty: 0,
CN: 1,
US: 2,
};
class Route {
ip = 0
range = 0
mark = Marks.CN
constructor(ip = 0, range = 0, mark = Marks.CN) {
this.ip = ip
this.range = range
this.mark = mark
}
}
class Solution {
count = 0x7fff
childrenMarks = [0, 0]
}
/**
* The IP Node
*/
class IPNode {
/**
* route mark
* @type {Number}
*/
mark = Marks.Empty;
/**
* two children of the current node
* @type {IPNode[]}
*/
children = [null, null]
/**
* the dp solutions
* @type {Solution[]}
*/
solutions = [new Solution(), new Solution(), new Solution()]
constructor() {}
}
/**
* add IP to the tree
* @param {Number} ip ip of an integer
* @param {Number} depth the tree depth
* @param {IPNode} node node of current IP
* @param {Number} range the mask range
* @param {Number} mark the mark of the current route
*/
function add(ip, depth, node, range, mark) {
if (node.mark) {
console.log('err', intToIPv4(ip), depth, range, mark, node.mark)
process.exit(1)
return
}
if (depth === range) {
node.mark = mark
return
}
const next = (ip & (1 << (31 - depth))) ? 1 : 0;
if (!node.children[next]) {
node.children[next] = new IPNode()
}
add(ip, depth + 1, node.children[next], range, mark);
}
/**
* IP addr to ip integer
* @param {String} ip ip addr string format
* @returns {Number} the integer of the IP
*/
function ipv4ToInt(ip) {
return ip.split('.')
.map(v => parseInt(v, 10))
.reduce((acc, v) => (acc << 8) | v, 0)
}
/**
*
* @param {Number} ip
* @returns {String}
*/
function intToIPv4(ip) {
const items = []
for (let i = 0; i < 4; i++) {
items.push(ip & 0xff)
ip >>>= 8
}
return items.reverse().map(v => v.toString(10)).join('.')
}
/**
* mark the tree by file content
* @param {String} file path of the file
* @param {Number} mark mark of the ip
* @param {String} countryCode the code of the country
* @param {IPNode} root
*/
async function markByFile(file, mark, countryCode, root) {
const content = await readFile(file)
content.split('\n')
.map(l => l.trim())
.filter(l => !l.startsWith('#'))
.map(l => l.split('|'))
.map(([, country, type, addr, count]) => ({
country, type, addr, count,
}))
.filter(({country, type}) => country === countryCode && type === 'ipv4')
.forEach(({addr, count}) => {
const range = Math.floor(32 - Math.log2(count))
const ip = ipv4ToInt(addr)
// console.log(countryCode, addr, ip, range)
add(ip, 0, root, range, mark)
})
}
/**
* dynamic programming to the the most optimized tree
* @param {IPNode} node
* @returns {Solution[]}
*/
function dp(node) {
if (!node) {
const emptyMarkSolution = [new Solution(), new Solution(), new Solution()]
emptyMarkSolution[0].count = 0
return emptyMarkSolution
}
if (node.mark) {
node.solutions[node.mark].count = 1
return node.solutions
}
const leftChildSolutions = dp(node.children[0])
const rightChildSolutions = dp(node.children[1])
for (let currentMark = 1; currentMark < 3; currentMark++) {
for (let leftChildMark = 0; leftChildMark < 3; leftChildMark++) {
for (let rightChildMark = 0; rightChildMark < 3; rightChildMark++) {
let count = leftChildSolutions[leftChildMark].count + rightChildSolutions[rightChildMark].count;
if (leftChildMark === rightChildMark && currentMark === leftChildMark) {
count --
} else if (currentMark !== leftChildMark && currentMark !== rightChildMark) {
count ++
}
if (count < node.solutions[currentMark].count) {
node.solutions[currentMark].count = count
node.solutions[currentMark].childrenMarks = [leftChildMark, rightChildMark]
}
}
}
}
return node.solutions;
}
/**
* get the final result form IP tree
* @param {IPNode} node
* @param {Number} ip
* @param {Number} depth
* @param {Number} mark
* @param {Number} parentMark
* @param {Route[]} result
*/
function getResult(node, ip, depth, mark, parentMark, result) {
if (!node) {
return
}
if (mark !== parentMark) {
result.push(new Route(ip, depth, mark))
}
const {childrenMarks: [leftMark, rightMark], count} = node.solutions[mark]
getResult(node.children[0], ip, depth + 1, leftMark, mark, result)
getResult(node.children[1], ip | (1 << (31 - depth)), depth + 1, rightMark, mark, result)
}
async function main() {
const root = new IPNode()
await markByFile('/Users/winguse/Downloads/delegated-apnic-latest.txt', Marks.CN, 'CN', root)
await markByFile('/Users/winguse/Downloads/delegated-arin-extended-latest.txt', Marks.US, 'US', root)
dp(root)
const mark = root.solutions[Marks.CN].count < root.solutions[Marks.US].count ? Marks.CN : Marks.US
const solution = root.solutions[mark];
const result = []
result.push(new Route(0, 0, mark))
getResult(root.children[0], 0 << 31, 1, solution.childrenMarks[0], mark, result)
getResult(root.children[1], 1 << 31, 1, solution.childrenMarks[1], mark, result)
result.sort(({range: a}, {range: b}) => b - a).forEach(({ip, mark, range}) => {
console.log(`${intToIPv4(ip)}/${range} -> ${mark === Marks.CN ? 'CN' : 'US'}`)
})
console.log(root.solutions)
console.log(result.length)
}
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment