.gitignore

/ipv4_inv

get.sh

#!/bin/bash

make ipv4_inv 1>& 2
tail -n +3 /usr/share/chnroutes2/chnroutes.txt | ./ipv4_inv

ipv4_inv.cc

#include <cstdio>
#include <stdint.h>
#include <set>

union IPv4Addr {
    struct {
        uint32_t x;
        uint8_t prefix;
    };

    struct {
        // FIXME Little Endian only
        uint8_t d;
        uint8_t c;
        uint8_t b;
        uint8_t a;

        uint8_t p;
    };

    bool read() {
        prefix = 32;
        return scanf("%hhu.%hhu.%hhu.%hhu/%hhu", &a, &b, &c, &d, &prefix) >= 4 && valid();
    }

    bool read(const char * s) {
        prefix = 32;
        return sscanf(s, "%hhu.%hhu.%hhu.%hhu/%hhu", &a, &b, &c, &d, &prefix) >= 4 && valid();
    }

    bool read(const char * s, const char * mask) {
        if (sscanf(s, "%hhu.%hhu.%hhu.%hhu", &a, &b, &c, &d) == 4) {
            IPv4Addr netmask;
            if (netmask.read(mask)) {
                prefix = __builtin_popcount(netmask.x);
                return valid();
            }
        }
        return false;
    }

    bool valid() const {
        return ((x >> (32 - prefix)) << (32 - prefix)) == x;
    }

    const char * c_str() const {
        // FIXME not thread safe
        static char buf[128];
        snprintf(buf, sizeof(buf), "%hhu.%hhu.%hhu.%hhu/%hhu", a, b, c, d, prefix);
        return buf;
    }

    const char * ipfilter() const {
        // FIXME not thread safe
        static char buf[128];
        int suffix = 32 - prefix;
#define BITS(a) (uint8_t)((1 << std::min(8, std::max(0, a))) - 1)
        snprintf(buf, sizeof(buf), "%hhu.%hhu.%hhu.%hhu-%hhu.%hhu.%hhu.%hhu", a, b, c, d,
                a | BITS(suffix - 24), b | BITS(suffix - 16),
                c | BITS(suffix - 8), d | BITS(suffix - 0));
        return buf;
    }

    IPv4Addr() : x(0), prefix(0) { };
    IPv4Addr(uint32_t x, uint8_t prefix = 32) : x(x), prefix(prefix) { };
    IPv4Addr(const char * s) { read(s); }

    uint32_t last() const {
        return (uint32_t)((uint64_t)x + (((uint64_t)1) << (32 - prefix)) - 1);
    }

    uint32_t first() const {
        return x;
    }

    int overlap_with(const IPv4Addr& addr) const {
        return first() <= addr.last() && last() >= addr.first();
    }

    int contain(const IPv4Addr& addr) const {
        return first() <= addr.first() && addr.last() <= last();
    }

    bool operator < (const IPv4Addr& rhs) const {
        return (x < rhs.x) || (x == rhs.x && prefix < rhs.prefix);
    }
};

struct IPv4AddrSet : public std::set<IPv4Addr> {
    bool contain(IPv4Addr addr) const {
        iterator it = lower_bound(addr);
        return it->contain(addr) || (it != begin() && (--it)->contain(addr));
    }

    bool overlap(IPv4Addr addr) const {
        iterator it_begin = lower_bound(addr.first());
        iterator it_end   = upper_bound(addr.last());

        if (it_begin != begin()) --it_begin;
        if (it_end   != end())   ++it_end;

        for (iterator it = it_begin; it != it_end; ++it) if (it->overlap_with(addr)) return true;
        return false;
    }

    void insert(IPv4Addr addr) {
        if (!addr.valid()) throw "Invalid IPv4Addr";
        if (overlap(addr)) throw "IPv4AddrSet does not allow overlapping IPv4Addr";
        std::set<IPv4Addr>::insert(addr);
    }

    void print() const {
        for (iterator i = begin(); i != end(); ++i) printf("%s\n", i->c_str());
    }

    void print_ipfilter() const {
        for (iterator i = begin(); i != end(); ++i) printf("prefix:%s\n", i->ipfilter());
    }

    IPv4AddrSet invert() const {
        IPv4AddrSet ret;

        uint8_t prefix = 0;
        uint64_t     x = 0;

        for(;;) {
            // choose a prefix that does not overlap
            ++prefix;

            IPv4Addr addr(x, prefix);
            if (!addr.valid()) continue;

            if (!overlap(addr)) {
                // that is ok, add to return set
                ret.insert(addr);
            } else if (!count(addr)) {
                // overlapped but not encounter exact entry, try next prefix
                continue;
            }

            // next addr
            x = ((x >> (32 - prefix)) + 1) << (32 - prefix);
            if (x >> 32) break;
            prefix = 0;
        }
        return ret;
    }
};

IPv4AddrSet used;

int main(int argc, char const *argv[]) {

    // Add non-Internet addresses
    used.insert(IPv4Addr("0.0.0.0/8"));
    used.insert(IPv4Addr("10.0.0.0/8"));
    used.insert(IPv4Addr("127.0.0.0/8"));
    used.insert(IPv4Addr("169.254.0.0/16"));
    used.insert(IPv4Addr("172.16.0.0/12"));
    used.insert(IPv4Addr("224.0.0.0/4"));
    used.insert(IPv4Addr("240.0.0.0/4"));
    used.insert(IPv4Addr("192.168.0.0/16"));

    char ip[128];
    while (scanf("%s", ip) == 1) {
        used.insert(IPv4Addr(ip));
    }
    used.invert().print();

    return 0;
}