代码

/* routecomp: exact optimal routing-table compression.
 *
 * Theory (verified independently by lab/rc/oracle.py: a full-profile DP and an
 * exhaustive brute force over all prefixes and all values agree with it):
 *
 *   cost(u,I) = min entries needed inside subtree(u) when the value inherited
 *   from above is I.  With children c0,c1:
 *        cost(u,I) = min( push(u), cost(c0,I) + cost(c1,I) )
 *        push(u)   = 1 + min_w ( cost(c0,w) + cost(c1,w) )
 *   The profile I -> cost(u,I) is always two valued:
 *        cost(u,I) = Q[u] + (I in K[u] ? 0 : 1)
 *   and merging two children yields
 *        K0 & K1 nonempty : Q = Q0+Q1,   K = K0 & K1
 *        otherwise        : Q = Q0+Q1+1, K = K0 | K1
 *   A uniform region is Q=0, K={its value};  answer = Q[root] + (0 in K[root]?0:1).
 *
 * Emission points are trie nodes (any prefixes); values are the input table's
 * nexthops plus 0.  Runs of unmarked nodes above a subtree whose side subtrees
 * are uniform with the inherited value A collapse into one virtual node with
 * K={A}, so the DP runs on the Patricia trie of the marked nodes (O(n) nodes).
 *
 * Reconstruction: descend from the root with inherited value I; if I in K[u]
 * emit nothing and recurse with I, else emit (u.prefix, w*) and recurse with w*.
 */
#include "routecomp.h"

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
#ifdef RCTIME
static double rct0;
static double rcnow(void){struct timespec t;clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&t);return t.tv_sec*1e3+t.tv_nsec/1e6;}
#define RCMARK(tag) fprintf(stderr,"  [%s] %.2f ms\n", tag, rcnow()-rct0)
#else
#define RCMARK(tag) do{}while(0)
#endif

typedef unsigned int u32;
typedef unsigned long long u64;

struct Ent { u32 key; u32 val; u32 len; };

struct PNode {
    int par, ch0, ch1;
    u32 key, val, sa;
    unsigned char depth, marked, uniform;
};

struct DNode {
    int ch0, ch1, Q;
    u32 key, val;                 /* colour (leaf/chain) or push value */
    union { struct { int koff, klen; }; u64 kmask; };
    unsigned char depth, kind;    /* kind: 0 leaf, 1 merge, 2 chain */
};

static Ent   *ent;
static PNode *pn;    static int ptop;
static DNode *dp;    static int dtop;
static int   *dn;                                     /* Patricia node -> d-node */
static u32   *karena; static long ktop, kcap;
static u32   *valof; static int nval;                 /* colour id -> nexthop field */
static int    useMask;                                /* colours fit in one u64 */
static int   *stk;   static int sp;
static RoutingTableEntry *OUT; static int OUTC;

/* ------------------------------------------------------------------ helpers */
static int kgrow(long need) {
    if (ktop + need <= kcap) return 0;
    while (ktop + need > kcap) kcap = kcap ? kcap * 2 : (1 << 16);
    u32 *nw = (u32 *)realloc(karena, (size_t)kcap * sizeof(u32));
    if (!nw) return -1;
    karena = nw;
    return 0;
}
static int kmember(int off, int len, u32 c) {
    int lo = off, hi = off + len;
    while (lo < hi) { int m = (lo + hi) >> 1; if (karena[m] < c) lo = m + 1; else hi = m; }
    return lo < off + len && karena[lo] == c;
}
/* merge two sorted K sets: intersection if they meet, else union.
   returns 1 if they meet; *pcommon receives a common element or (union) the first. */
static int kmerge(int ao, int alen, int bo, int blen, int *roff, int *rlen, u32 *pcommon) {
    int i = 0, j = 0, meet = 0;
    while (i < alen && j < blen) {
        u32 a = karena[ao + i], b = karena[bo + j];
        if (a == b) { meet = 1; break; }
        if (a < b) i++; else j++;
    }
    long need = meet ? (alen < blen ? alen : blen) : (long)alen + blen;
    if (kgrow(need) < 0) { *roff = ao; *rlen = alen; *pcommon = karena[ao]; return meet; }
    int off = (int)ktop;
    i = j = 0;
    if (meet) {
        while (i < alen && j < blen) {
            u32 a = karena[ao + i], b = karena[bo + j];
            if (a == b) { karena[ktop++] = a; *pcommon = a; i++; j++; }
            else if (a < b) i++; else j++;
        }
    } else {
        while (i < alen && j < blen) {
            u32 a = karena[ao + i], b = karena[bo + j];
            if (a < b) karena[ktop++] = a, i++;
            else if (b < a) karena[ktop++] = b, j++;
            else { karena[ktop++] = a; i++; j++; }
        }
        while (i < alen) karena[ktop++] = karena[ao + i++];
        while (j < blen) karena[ktop++] = karena[bo + j++];
        *pcommon = karena[off];
    }
    *roff = off; *rlen = (int)ktop - off;
    return meet;
}
static int newP(u32 key, int depth, int marked, u32 val) {
    PNode *p = &pn[ptop];
    p->par = -1; p->ch0 = -1; p->ch1 = -1;
    p->key = key; p->val = val; p->sa = 0;
    p->depth = (unsigned char)depth; p->marked = (unsigned char)marked; p->uniform = 0;
    return ptop++;
}
static void setChild(int par, int child) {
    int b = (int)((pn[child].key >> (31 - pn[par].depth)) & 1u);
    if (b) pn[par].ch1 = child; else pn[par].ch0 = child;
    pn[child].par = par;
}
static int newD(int kind, u32 key, int depth, int Q, int koff, int klen, u32 val) {
    DNode *d = &dp[dtop];
    d->ch0 = -1; d->ch1 = -1; d->Q = Q; d->koff = koff; d->klen = klen;
    d->key = key; d->val = val; d->depth = (unsigned char)depth; d->kind = (unsigned char)kind;
    return dtop++;
}
static int newK1(u32 c) {
    if (useMask) return 0;
    if (kgrow(1) < 0) return -1;
    int off = (int)ktop;
    karena[ktop++] = c;
    return off;
}
static void setK1(int node, u32 c) {                   /* K = {c} */
    if (useMask) dp[node].kmask = 1ull << c;
    else { dp[node].koff = newK1(c); dp[node].klen = 1; }
}
static int kmem(int node, u32 c) {
    if (useMask) return (int)((dp[node].kmask >> c) & 1ull);
    return kmember(dp[node].koff, dp[node].klen, c);
}
static void emitEntry(u32 key, int depth, u32 color) {
    RoutingTableEntry *o = &OUT[OUTC++];
    o->addr = __builtin_bswap32(key);
    o->len = (unsigned char)depth;
    o->pad[0] = o->pad[1] = o->pad[2] = 0;
    o->nexthop = valof[color];
}
static void emitD(int u, u32 amb) {
    DNode *d = &dp[u];
    if (d->kind == 0) {                                   /* uniform region */
        if (d->val != amb) emitEntry(d->key, d->depth, d->val);
        return;
    }
    if (d->kind == 2) {                                   /* collapsed chain */
        u32 a = d->val;
        if (a != amb) { emitEntry(d->key, d->depth, a); amb = a; }
        emitD(d->ch0, amb);
        return;
    }
    if (kmem(u, amb)) { emitD(d->ch0, amb); emitD(d->ch1, amb); }
    else {
        u32 w = d->val;
        emitEntry(d->key, d->depth, w);
        emitD(d->ch0, w); emitD(d->ch1, w);
    }
}

/* ---------------------------------------------------------------------- DP */
static int lcpLen(u32 a, u32 la, u32 b, u32 lb) {
    u32 l = la < lb ? la : lb;
    u32 m = (l == 0) ? 0xffffffffu : (l >= 32 ? 0u : ((1u << (32 - l)) - 1u));
    u32 d = (a ^ b) & ~m;
    if (!d) return (int)l;
    return __builtin_clz(d);
}
/* merge two D-nodes (standard (Q,K) rule) */
static int mergeD(int n0, int n1, u32 key, int depth) {
    u32 common;
    int me, Q;
    if (useMask) {
        u64 a = dp[n0].kmask, b = dp[n1].kmask, inter = a & b;
        if (inter) {
            Q = dp[n0].Q + dp[n1].Q;
            common = (u32)__builtin_ctzll(inter);
            me = newD(1, key, depth, Q, 0, 0, common);
            dp[me].kmask = inter;
        } else {
            u64 uni = a | b;
            Q = dp[n0].Q + dp[n1].Q + 1;
            common = (u32)__builtin_ctzll(uni);
            me = newD(1, key, depth, Q, 0, 0, common);
            dp[me].kmask = uni;
        }
    } else {
        int off, len;
        int meet = kmerge(dp[n0].koff, dp[n0].klen, dp[n1].koff, dp[n1].klen, &off, &len, &common);
        Q = dp[n0].Q + dp[n1].Q + (meet ? 0 : 1);
        me = newD(1, key, depth, Q, off, len, common);
    }
    dp[me].ch0 = n0;
    dp[me].ch1 = n1;
    return me;
}

static int buildD(int u) {
    PNode *p = &pn[u];
    int side[2];
    if (p->marked && p->uniform) {
        int lf = newD(0, p->key, p->depth, 0, 0, 0, p->val);
        setK1(lf, p->val);
        return lf;
    }
    u32 A = p->marked ? p->val : p->sa;
    int kids[2];
    kids[0] = p->ch0; kids[1] = p->ch1;
    for (int b = 0; b < 2; b++) {
        int c = kids[b];
        u32 ck = p->depth >= 32 ? p->key : (p->key | ((u32)b << (31 - p->depth)));
        int cd = p->depth + 1;
        if (c < 0) {
            int lf = newD(0, ck, cd, 0, 0, 0, A);
            setK1(lf, A);
            side[b] = lf;
        } else {
            int d = dn[c];
            if (pn[c].depth > cd) {
                int k = (int)pn[c].depth - cd;             /* chain length above c */
                if (k == 1) {
                    /* one unmarked node with a uniform (=A) sibling: exact merge */
                    int db = (int)((pn[c].key >> (31 - cd)) & 1u);   /* deep child's bit at depth cd */
                    u32 gapkey = ck | ((u32)(1 - db) << (31 - cd));
                    int gap = newD(0, gapkey, cd + 1, 0, 0, 0, A);
                    setK1(gap, A);
                    side[b] = mergeD(gap, d, ck, cd);
                } else {
                    /* >=2 chain nodes: result is (Q_D+[A not in K_D], {A}) */
                    int Q = dp[d].Q + (kmem(d, A) ? 0 : 1);
                    int ch = newD(2, ck, cd, Q, 0, 0, A);
                    setK1(ch, A);
                    dp[ch].ch0 = d;
                    side[b] = ch;
                }
            } else side[b] = d;
        }
    }
    int me = mergeD(side[0], side[1], p->key, p->depth);
    return me;
}
static void postorder(int u) {
    if (pn[u].ch0 >= 0) postorder(pn[u].ch0);
    if (pn[u].ch1 >= 0) postorder(pn[u].ch1);
    dn[u] = buildD(u);
}

/* -------------------------------------------------------------------- main */
void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp) {
    if (n <= 0) { *tbl_comp = (RoutingTableEntry *)malloc(8); *n_comp = 0; return; }

#ifdef RCTIME
    rct0 = rcnow();
#endif
    ent = (Ent *)malloc((size_t)n * sizeof(Ent));
    Ent *tmp = (Ent *)malloc((size_t)n * sizeof(Ent));
    if (!ent || !tmp) { *tbl_comp = (RoutingTableEntry *)malloc(8); *n_comp = 0; return; }
    for (int i = 0; i < n; i++) {
        ent[i].key = __builtin_bswap32(tbl[i].addr);
        ent[i].val = tbl[i].nexthop;
        ent[i].len = tbl[i].len > 32 ? 32 : tbl[i].len;
    }
    {   /* stable sort by len, then 4 LSD radix passes by key -> (key,len) asc */
        int cnt[33];
        for (int i = 0; i <= 32; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[ent[i].len]++;
        int s = 0;
        for (int i = 0; i <= 32; i++) { int c = cnt[i]; cnt[i] = s; s += c; }
        for (int i = 0; i < n; i++) tmp[cnt[ent[i].len]++] = ent[i];
        Ent *t = ent; ent = tmp; tmp = t;
    }
    for (int pass = 0; pass < 4; pass++) {
        int sh = pass * 8, cnt[256];
        for (int i = 0; i < 256; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[(ent[i].key >> sh) & 255u]++;
        int s = 0;
        for (int i = 0; i < 256; i++) { int c = cnt[i]; cnt[i] = s; s += c; }
        for (int i = 0; i < n; i++) tmp[cnt[(ent[i].key >> sh) & 255u]++] = ent[i];
        Ent *t = ent; ent = tmp; tmp = t;
    }
    free(tmp); tmp = 0;

    {   /* mask host bits, drop duplicate (addr,len) keeping the first */
        int m = 0;
        for (int i = 0; i < n; i++) {
            u32 len = ent[i].len;
            u32 key = len == 0 ? 0u : (len >= 32 ? ent[i].key : (ent[i].key & ~((1u << (32 - len)) - 1u)));
            if (m > 0 && ent[m - 1].key == key && ent[m - 1].len == len) continue;
            ent[m].key = key; ent[m].val = ent[i].val; ent[m].len = len;
            m++;
        }
        n = m;
    }

    {   /* colour ids: 0 = field 0, then distinct nonzero nexthops */
        u32 *vs = (u32 *)malloc((size_t)n * sizeof(u32));
        u32 *vt = (u32 *)malloc((size_t)n * sizeof(u32));
        for (int i = 0; i < n; i++) vs[i] = ent[i].val;
        for (int pass = 0; pass < 4; pass++) {
            int sh = pass * 8, cnt[256];
            for (int i = 0; i < 256; i++) cnt[i] = 0;
            for (int i = 0; i < n; i++) cnt[(vs[i] >> sh) & 255u]++;
            int s = 0;
            for (int i = 0; i < 256; i++) { int c = cnt[i]; cnt[i] = s; s += c; }
            for (int i = 0; i < n; i++) vt[cnt[(vs[i] >> sh) & 255u]++] = vs[i];
            u32 *t = vs; vs = vt; vt = t;
        }
        free(vt);
        valof = (u32 *)malloc((size_t)(n + 2) * sizeof(u32));
        nval = 0;
        valof[nval++] = 0;
        for (int i = 0; i < n; i++)
            if ((i == 0 || vs[i] != vs[i - 1]) && vs[i] != 0) valof[nval++] = vs[i];
        for (int i = 0; i < n; i++) {
            u32 v = ent[i].val;
            int lo = 0, hi = nval - 1;
            while (lo < hi) { int mid = (lo + hi) >> 1; if (valof[mid] < v) lo = mid + 1; else hi = mid; }
            ent[i].val = (u32)lo;
        }
        free(vs);
        useMask = (nval <= 64);
    }

    RCMARK("sort+colours");
    /* uniformity of each entry within the marked tree */
    unsigned char *uni = (unsigned char *)malloc((size_t)n);
    {
        int *par = (int *)malloc((size_t)n * sizeof(int));
        int *sz  = (int *)malloc((size_t)n * sizeof(int));
        u32 *cd  = (u32 *)malloc((size_t)n * sizeof(u32));
        stk = (int *)malloc((size_t)(n + 1) * sizeof(int));
        u64 *eR = (u64 *)malloc((size_t)n * sizeof(u64));
        for (int i = 0; i < n; i++) {
            u32 len = ent[i].len;
            u64 w = len >= 32 ? 1u : (1ull << (32 - len));
            eR[i] = (u64)ent[i].key + w;
        }
        sp = 0;
        for (int i = 0; i < n; i++) {
            while (sp > 0 && eR[stk[sp - 1]] <= (u64)ent[i].key) sp--;
            par[i] = sp > 0 ? stk[sp - 1] : -1;
            stk[sp++] = i;
        }
        free(eR);
        for (int i = 0; i < n; i++) { sz[i] = 1; cd[i] = 0; }
        for (int i = n - 1; i >= 1; i--) {
            int pp = par[i];
            if (pp >= 0) { cd[pp] += cd[i] + (ent[i].val != ent[pp].val ? (u32)sz[i] : 0u); sz[pp] += sz[i]; }
        }
        for (int i = 0; i < n; i++) uni[i] = (cd[i] == 0);
        free(par); free(sz); free(cd);
    }

    RCMARK("uniformity");
    /* Patricia trie over the marked nodes, root at depth 0 */
    pn = (PNode *)malloc((size_t)(2 * n + 4) * sizeof(PNode));
    dn = (int *)malloc((size_t)(2 * n + 4) * sizeof(int));
    int *pstk = (int *)malloc((size_t)(n + 4) * sizeof(int));
    int *pnodeOf = (int *)malloc((size_t)n * sizeof(int));
    ptop = 0;
    int root, start = 0;
    if (ent[0].len == 0) {
        root = newP(0, 0, 1, ent[0].val);
        pnodeOf[0] = root;
        pstk[0] = root; sp = 1;
        start = 1;
    } else {
        root = newP(0, 0, 0, 0);
        pstk[0] = root; sp = 1;
    }
    {
        u32 pkey = 0, plen = 0;
        for (int i = start; i < n; i++) {
            u32 key = ent[i].key, len = ent[i].len;
            int l = lcpLen(pkey, plen, key, len);
            int last = -1;
            while (sp > 0 && (int)pn[pstk[sp - 1]].depth > l) last = pstk[--sp];
            int parent;
            if (sp > 0 && (int)pn[pstk[sp - 1]].depth == l) parent = pstk[sp - 1];
            else {
                u32 bkey = (l == 0) ? 0u : (l >= 32 ? key : (key & ~((1u << (32 - l)) - 1u)));
                parent = newP(bkey, l, 0, 0);
                if (last >= 0) setChild(parent, last);
                if (sp > 0) {
                    int pp = pstk[sp - 1];
                    if (pn[pp].ch0 == last) pn[pp].ch0 = parent;
                    else if (pn[pp].ch1 == last) pn[pp].ch1 = parent;
                    pn[parent].par = pp;
                } else root = parent;
                pstk[sp++] = parent;
            }
            int node = newP(ent[i].key, (int)len, 1, ent[i].val);
            setChild(parent, node);
            pstk[sp++] = node;
            pnodeOf[i] = node;
            pkey = key; plen = len;
        }
    }
    free(pstk);
#ifdef RCDEBUG
    for (int i = 0; i < ptop; i++) {
        for (int s2 = 0; s2 < 2; s2++) {
            int c = s2 ? pn[i].ch1 : pn[i].ch0;
            if (c < 0) continue;
            if (c >= ptop) { fprintf(stderr, "BAD child %d of %d\n", c, i); continue; }
            if (pn[c].par != i) fprintf(stderr, "BAD par node %d -> child %d (child.par=%d)\n", i, c, pn[c].par);
            if ((int)pn[c].depth <= (int)pn[i].depth) fprintf(stderr, "BAD depth %d(%d) -> %d(%d)\n", i, pn[i].depth, c, pn[c].depth);
            int b = (int)((pn[c].key >> (31 - pn[i].depth)) & 1u);
            if (b != s2) fprintf(stderr, "BAD slot %d -> %d in slot %d but bit %d\n", i, c, s2, b);
        }
    }
    fprintf(stderr, "ptop=%d root=%d start=%d\n", ptop, root, start);
#endif
    for (int i = start; i < n; i++) pn[pnodeOf[i]].uniform = uni[i];
    if (start == 1) pn[root].uniform = uni[0];
    free(pnodeOf); free(uni);

    RCMARK("patricia");
    /* structural ambient: value of the deepest marked ancestor */
    {
        int *sstk = (int *)malloc((size_t)(2 * n + 8) * sizeof(int));
        int top = 0;
        pn[root].sa = 0;
        sstk[top++] = root;
        while (top > 0) {
            int u = sstk[--top];
            u32 A = pn[u].marked ? pn[u].val : pn[u].sa;
            if (pn[u].ch0 >= 0) { pn[pn[u].ch0].sa = A; sstk[top++] = pn[u].ch0; }
            if (pn[u].ch1 >= 0) { pn[pn[u].ch1].sa = A; sstk[top++] = pn[u].ch1; }
        }
        free(sstk);
    }

    RCMARK("sa");
    dp = (DNode *)malloc((size_t)(3 * (size_t)ptop + 16) * sizeof(DNode));
    karena = 0; ktop = 0; kcap = 0;
    dtop = 0;
    postorder(root);
    int droot = dn[root];
    OUT = (RoutingTableEntry *)malloc((size_t)(dtop + 2) * sizeof(RoutingTableEntry));
    OUTC = 0;
    RCMARK("dp");
    emitD(droot, 0);
    RCMARK("reconstruct");
    fprintf(stderr, "  ptop=%d dtop=%d n=%d nval=%d\n", ptop, dtop, n, nval);
#ifdef RCDEBUG
    fprintf(stderr, "--- patricia ---\n");
    for (int i = 0; i < ptop; i++)
        fprintf(stderr, "P%d d=%d key=%08x mk=%d val=%u uni=%d sa=%u ch=(%d,%d)\n",
                i, pn[i].depth, pn[i].key, pn[i].marked, pn[i].val, pn[i].uniform, pn[i].sa, pn[i].ch0, pn[i].ch1);
    fprintf(stderr, "--- dnodes (root=%d dtop=%d) ---\n", droot, dtop);
    for (int i = 0; i < dtop; i++) {
        fprintf(stderr, "D%d kind=%d d=%d key=%08x Q=%d val=%u ch=(%d,%d) K=", i, dp[i].kind, dp[i].depth,
                dp[i].key, dp[i].Q, dp[i].val, dp[i].ch0, dp[i].ch1);
        for (int j = 0; j < dp[i].klen && j < 8; j++) fprintf(stderr, "%u,", karena[dp[i].koff + j]);
        fprintf(stderr, "\n");
    }
#endif
    *tbl_comp = OUT;
    *n_comp = OUTC;
    free(ent); free(pn); free(dn); free(dp); free(karena); free(stk);
}

评测结果