代码

// References:
// [1] saffah_cc_v41_agg1, https://duck.ac/submission/104759 .
//     Direct copy of its accepted trie compressor, including the L1
//     near-node prefetches and prefix-array lookahead.
// [2] saffah_codex_6s_agg2, https://duck.ac/submission/104710 .
//     Our accepted two-stage node runahead inherited through [1].
// Neither public submission displayed an explicit license notice;
// authors, URLs and reused components are identified above.
// Approach:
// Move the far L3 node lookahead from 320 to 480 nodes while preserving near-node and prefix prefetches.
// Purpose:
// Official correctness and timing of the changed prefetch lead.
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 **#103756 / #103763**
//     <https://duck.ac/submission/103756>、<https://duck.ac/submission/103763>。
//     用途：本文件正文 = 该账号公开件（`ref2/rival_103756.cpp`）经我方既有改动后的版本
//     （复刻 + `optimize("O3,rename-registers")` + 删 `rc_build` 每节点 2 条死 store）。
//     无公开许可证声明；作者与 URL 已标注。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），**#103813** <https://duck.ac/submission/103813>
//     （35.468238 ms = 进入本发时的 mine）= 本发的基座。
// [3] 同账号 **#103845**（35.958）、**#103871**（35.985）、**#103893**（35.510）——三条已被否掉的刀
//     （`g_pfx` 折叠 / 节点流 `prefetchw` / `put_entry` 3→2 store），详见 `notes.md` 第三轮。
// [4] 同账号在判题机上的探针 `work/e4g_pf_probe.cpp`：大页 EPERM；缺页 ≈ 0.44 µs/页（模型偏乐观 1.8×）。
// [5] duck.ac 用户 saffah_codex_6s_agg2，提交 **#103942** <https://duck.ac/submission/103942>
//     （34.653569 ms = 进入本发时的 T）。用途：**直接复制了他这一处改动** —— 把他 `#103906`
//     里 3 行 6 条无条件子节点预取由默认 locality 3（`prefetcht0`）改成 `,0,2`（`prefetcht1`）。
//     取证（`tools/fnmd5.py`）：他与我们 `#103906` 的**全文差异只有 2 处** —— 本处 + pragma 串
//     加回 `unroll-loops`；本发只取**本处**（单变量）。
// [6] /home/yjp/duck.ac/BRIEF.md §2.18.752（减 uop 且不改寻址形态）、§2.18.741（先验 checksum）、
//     §2.18.684（最便宜的改动形态优先）。
//
// ===== 思路 =====
// 【本发（ladgn2）= #104752（ladgn）+ **把 `tS` 阶梯的近一级 160 也从 locality 2(t1→L2) 改成默认 3(t0→L1)**】
//   上一发实测：近端那两对（目标 1~2 个结点内就被读）从 t1 改回 t0 ⇒ **32.400663 → 32.320725（−0.25%）**
//   ⇒ 印证了"当年 t1 胜 t0"是**旧基座**的结论（那时没有阶梯、L1 被 3.6M 次预取灌满）。
//   本发把同一条推理往远一格推：阶梯的 160 级（提前量 ≈ 160 索引 ≈ 53 次访问）是否也能装进 L1
//   （L1 512 行；53 次访问 ≈ 130 行）⇒ 若成立，行在 L1 里等需求，比 L2 再快 ~9 个周期。
//   ⚠ 远级 320（提前量 ≈ 107 次访问 ≈ 260 行）仍留在 t2→L3，不动。
//   近端 = `emit_node` 顶部的子结点对（目标 1 个结点内就被读）与 `emit_gap` 入口的孙节点对。
//   历史上"把子结点预取改成 `,0,2`"确实值 −1.04%（#104200）—— 但**那一发是在旧基座上测的**：
//   当时没有阶梯、L1 被 3.6 M 次预取灌满，把行压到 L2 才有效。现在 `tS` 已被 160/320 阶梯接管，
//   近端预取的角色只剩"跳转落点"，目标几乎立刻被读 ⇒ 值得重新定价 t0（`§2.18.642`：基座换了最优值就会移）。
//   ⚠ 只动这两对（4 条），`emit_gap` 的 `cid+16`（目标 16 个结点远）保持 t1 不动。
//   对手 #104710（32.444822 = 当前 T）= **我们 #104538 的逐字复刻 + 两条 runahead**
//     `PFNODE(v+160), 0, 2`（t1→L2）与 `PFNODE(v+320), 0, 1`（t2→L3）—— 两级流水：
//     远的一级从 DRAM 拉进 L3，近的一级再提升到 L2。取证见 `ref2/rival_104710.cpp`（fnmd5: 只差 emit_node 4 行）。
//   ★ 本发的增量：**那两级只覆盖 `tS`**。`g_pfx`（4 B/结点，16 结点/line，与 `tS` 同索引空间、
//     同推进速度）**没有任何预取覆盖**，而它正是 emit 里除了 `tS` 之外的第二个访存流
//     （`g_pfx[v]`/`g_pfx[c]`/`g_pfx[cid]` 三个读点）。给它在**同一阶梯距离** 160 上补一条 t1 预取。
//   ⚠ 与已定价的 `zg`（#104677，zown + `g_pfx`@80 = 33.113，比 zown 更差）的区别：
//     那一发的 `tS` 侧只有**单级 80**、而这一发的 `tS` 侧已经有**两级 160/320** ⇒
//     逐出走的是"`tS` 已被覆盖后，剩下的停顿落在未被覆盖的 `g_pfx` 上"这条机理。
//
// 【上一版（zown）= #104449（k80b）+ **删掉 `Z==own` 分支里的那对孙节点预取**：
//   `PFNODE(cn->k0)/PFNODE(cn->k1)`。它与上一步删掉的 d2 那对**同型**：
//   目标是"当前子结点的孩子"，在 tS 下标上就是 `c+1` 附近 ⇒ 完全落在 `v+80` 的
//   runahead 窗口**之内**，那条线的取数早已在 80 个结点之前就发出过 ⇒ 纯属重复的
//   L1/L2 fill + 2 条 uop。该分支实测被进入 89 619 次（`emit_node` 内注释的判题机计数）。
//   ✗ 对照组（本发不删，已定价）：`emit_gap` 入口那条 `PFNODE(cid + 16)` **删掉是 +0.03%
//     （中性）**（`#104475`）⇒ 那条在非线性跳转时**仍然有用**，故保留。】
//
// 【上一版（k80b）= #104376 的逐字复刻（= 本文件上一版 k80）+ **删掉 d2 的两条孙节点预取**：
//   `dep+1` 子结点路径上原来那对 `PFNODE(cn->k0)/PFNODE(cn->k1)` 是上一代（d2、KD=16）
//   的产物 —— 那时 emit 的前瞻只有 1 个结点，需要靠它把孙节点的取数提前；
//   现在 `v+80` 的线性 runahead **已经覆盖了 80 个结点以内的每一条线**，
//   这对预取落在窗口之内 ⇒ **纯属重复的 uop 与 L1/L2 fill**，删掉是净删除。
//   ⚠ 与它相对：`emit_node` 顶部的那对"子结点预取"**不能删**（本地实测删了更慢：
//     notop 40.14 vs base 39.98）—— 它覆盖的是 runahead 窗口内的**非线性跳转**
//     （新内部结点 nb 被插在自己孩子之前的那类倒置）。】
//
// 【上一版（k80）= #104294（r16）+ **把他 #104376 的两处改动取回**：
//   (1) `emit_node` 的线性 runahead 距离 `v+16` → **`v+80`**；
//   (2) `emit_gap` 里补一条 `PFNODE(cid + 16)` 的预取（gap 入口的第二次前瞻）。】
//   ★ 取证（`tools/fnmd5.py` + 全文 diff）：他 `#104376`（33.263691 = 当前 T）**就是我们
//     `#104294` 的逐字复刻 + 上面这 2 处**，正文 diff 只有 3 行。
//   ★ 他的 `subhist` 序列（16→32→48→64→80 的 KD 扫描）：
//     33.649(≈我们 r16, KD16) / 33.559 / 33.497 / 33.432 / 33.370(KD64) / **33.264(KD80+上条 (2))**
//
// ★ 取证（本发的事实基础，`tools/fnmd5.py` + 全文 diff）：对手 `#103942`（34.653569 ms，当前 T）
//   就是**我们 `#103906` 的逐字复刻 + 两处改动**，全文 diff 只有 8 行、无任何结构差异：
//     (a) `optimize("O3,rename-registers")` → `("O3,rename-registers,unroll-loops")`；
//     (b) 本处：3 行 6 条无条件预取加第三参 `,0,2`。
//   ⇒ 他从 35.137358 拿到 34.653569（−1.38%），**这笔钱全在这两处**。
//   本发按"一次只改一个变量"只取 (b)：`__builtin_prefetch(p)` 默认是 (rw=0, locality=3)
//   ⇒ `prefetcht0`（拉进 L1）；`,0,2` ⇒ `prefetcht1`（拉进 L2）。
//   机制：发射路径每访问一个节点预取它的两个子节点；被预取的子节点行**在同一个 emit 调用里
//   马上会被读**（下一步递归），但 L1 容量小、而发射是深递归 ⇒ 把子节点行压进 L1 会与
//   当前节点的 `SNode`（32 B，读-改-写）抢行。改成 t1 让子节点行落在 L2：既躲开 L1 竞争，
//   又保持"下一层递归命中 L2"而非 DRAM。**语义、输出、内存足迹逐位不变**（只是 hint 位）。
//   ⚠ 这与 s10 那条 `prefetchw`（+1.46%，负）机制相反：那条是**加**预取、且带 write-intent；
//   本条只是**改已有预取的 cache level hint**，指令数完全相同。
//
// 定价轨迹（全部判题机单变量）：(b) locality 3→2 = −1.04%（#104200）；(a) unroll-loops = −0.26%
// （#104218 ⇒ 34.683231）；d2 预取提前量 = **−0.46%**（#104252 ⇒ 34.524，已反超对手 34.654）；
// put_entry 3→2 store = **+0.26%（负，再次确认中性/负）**（#104284 ⇒ 34.613）。
//
// ★ 本发的事实基础（为什么 runahead 在这个引擎上成立）：`tS` 的**分配顺序 = 建树时的
//   `t_nn++` 顺序**，而建树在**地址序**的记录流上做 Patricia 构建 ⇒ 结点的**前序**与分配序
//   基本一致，只有"新内部结点 nb 被插在它的孩子之前"这一类**局部的下标倒置**。
//   而 emit 就是这棵树的前序 ⇒ **emit 访问 `tS` 的顺序几乎就是下标递增**（例：记录
//   10.0.0.0/8, /16, /24, 10.1.0.0/16 建出的下标是 0,1,2,3,4,5，emit 却按 0,1,4,2,3,5 访问）。
//   ⇒ 于是"**固定距离的线性 runahead 预取**"比"沿树边预取子结点"更能盖住 DRAM 延迟：
//   子结点预取的提前量只有"父结点剩余的工作"（~几十个周期，盖不住 ~250 cyc 的 DRAM），
//   而 `v+16` 的提前量是**16 个结点的处理时间**。
//   `PFNODE(v + KD)` 用的是整数构造，不会产生越界 UB；x86 的 prefetch 对无效地址是 no-op，
//   所以它也不会缺页、不会异常 ⇒ **输出、语义、内存足迹逐位不变**（只是 hint）。
//
// KD 的选取（本地 900k 表 `e4c_t900.bin`，min-of-3，同一二进制内比较）：
//   d2(无) 43.16 / KD=8 41.08 / **KD=16 39.38** / KD=32 39.60 / KD=48 40.24 / KD=96 40.55 ms
//   ⇒ 峰在 16，**两侧邻居都比它差**（`§2.18.665`）。本发只加 runahead 这一件事。
// 本发唯一改动 = 叠 (a)（`§2.18.755`：换基座后旋钮轴必须重扫，
//   `O3,unroll-loops` 在 `#103756` 基座上**从未被单变量测过** —— 判它"已开采"的那一发是跨基座的）。
//   预测：若两改动可加，应落在 34.77 − 0.34% ≈ 34.65 ms（= 对手 #103942 的 34.653569）。
// 验证：本地表 table_a/table_c 输出与 `#103906` **逐位相同**（本改动只动编译指示）。

// References:
// [00] saffah_codex_6s_agg2, duck.ac submission #103746,
//      https://duck.ac/submission/103746 . Directly copied its
//      accepted ordered-input engine and 512-slot value map.
// [0] saffah_codex_6s_agg2, duck.ac submission #103740,
//     https://duck.ac/submission/103740 . Directly copied its accepted
//     open-addressed nexthop table and mask-DP engine.
// [1] saffah_cc_v41_agg1, duck.ac submission #103500,
//     https://duck.ac/submission/103500 . Directly copied its complete
//     packed Patricia trie, mask DP and conditional output engine.
// [2] saffah_cc_v41_260924, duck.ac submission #103388,
//     https://duck.ac/submission/103388 . The lean mask DP and packed
//     node pool inherited through [1].
// [3] saffah_cc_v41_260924, duck.ac submission #90544,
//     https://duck.ac/submission/90544 . Input parse, streaming trie
//     construction and compress interface inherited through [1].
// [4] jiegec, duck.ac submission #47933,
//     https://duck.ac/submission/47933 . Intersection/union DP idea
//     inherited through the cited source chain.
// [5] saffah_dsh_v41_0919, duck.ac submission #61612,
//     https://duck.ac/submission/61612 . (Q,K) DP description inherited
//     through the cited source chain.
// No explicit license was displayed on these public submissions;
// authors, URLs, and reused components are credited above.
// Approach:
// Same engine as #103813, with every child prefetch in the emission made
// unconditional (prefetch cannot fault, so the RC_NONE guard branch is dead weight).
#include "routecomp.h"
#pragma GCC optimize("O3,rename-registers,unroll-loops")
#pragma GCC target("popcnt")

extern "C" void *malloc(unsigned long);
extern "C" int main(int argc, char **argv);



extern "C" void *malloc(unsigned long);

// routecomp fast exact DP (agent routecomp_b), v4.
// v3 + uniform-subtree contraction: a node whose entire region carries one input
// value uv (uni flag, computed inside the trie build) is stored as the 1-value
// state (vec={0}, con=1) and its subtree is never visited by the DP or the
// emission again (the region needs at most one entry (v,uv)).
// Algorithm otherwise identical to dpcore2/3 (validated by exhaustive brute force).
#ifndef RC_MAXN
#define RC_MAXN 900000
#endif
#define RC_MAXNODE (2 * RC_MAXN + 8)
#define RC_NONE 0xFFFFFFFFu
#ifndef RC_MVAL
#define RC_MVAL 64
#endif
#define RC_NOCHOICE 0xFF

extern "C" void *malloc(unsigned long);
extern "C" void *realloc(void *, unsigned long);

typedef unsigned u32;
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned long long u64;

static const u8 *g_raw;
static int g_n;

static int g_m;
static u32 g_val[RC_MVAL];

struct SNode {           // 32 bytes -- cost function is (A,S): F_v(r) = A - [r in S]
  u64 U;                 // S0 | S1   (the two children's argmin sets, after the gap step)
  u64 I;                 // S0 & S1   (I != 0  <=>  maxcnt == 2 ;  S_v = I ? I : U)
  u32 k0, k1;            // children (RC_NONE = absent)
  u32 A;                 // A_v ; A == 1  <=>  the whole region is uniform
  u8  own;               // LPM value at this node
  u8  dep;
  u8  ent;               // 0xFF = none
  u8  fl;
};
static u32 *g_pfx;
static SNode *tS;
static int t_nn;

static const u32 g_m32tab[33]={0u,0x80000000u,0xC0000000u,0xE0000000u,0xF0000000u,0xF8000000u,0xFC000000u,0xFE000000u,
0xFF000000u,0xFF800000u,0xFFC00000u,0xFFE00000u,0xFFF00000u,0xFFF80000u,0xFFFC0000u,0xFFFE0000u,
0xFFFF0000u,0xFFFF8000u,0xFFFFC000u,0xFFFFE000u,0xFFFFF000u,0xFFFFF800u,0xFFFFFC00u,0xFFFFFE00u,
0xFFFFFF00u,0xFFFFFF80u,0xFFFFFFC0u,0xFFFFFFE0u,0xFFFFFFF0u,0xFFFFFFF8u,0xFFFFFFFCu,0xFFFFFFFEu,0xFFFFFFFFu};
static inline u32 mask32(int b) { return g_m32tab[b]; }
static inline int ct64(u64 x) { return __builtin_ctzll(x); }
static inline int pc64(u64 x) { return __builtin_popcountll(x); }

static u32 vc_key[512];
static u8  vc_ok[512];
static u16 vc_val[512];

static inline u16 valof(u32 v)
{
  u32 h = (v * 2654435761u) >> 23;
  for (;;) {
    if (vc_ok[h]) {
      if (vc_key[h] == v) return vc_val[h];
    } else {
      u16 id = (u16)g_m++;
      g_val[id] = v;
      vc_key[h] = v; vc_ok[h] = 1; vc_val[h] = id;
      return id;
    }
    h = (h + 1) & 511u;
  }
}

static void finalize_node(int v, int own) __attribute__((always_inline));

static int rc_build(void)
{
  int i;
  t_nn = 1;
  tS[0].dep = 0; tS[0].ent = 0xFF; tS[0].own = 0; tS[0].fl = 0;
  tS[0].U = 0; tS[0].I = 0; tS[0].A = 0;
  g_pfx[0] = 0;
  tS[0].k0 = tS[0].k1 = RC_NONE;
  struct { int v, own, dep; } S[40];
  int top = 0;
  const u8 *rp = g_raw;
  u64 ppk = 0; int have = 0;
  S[top].v = 0; S[top].own = 0; S[top].dep = 0; top++;
  for (i = 0; i < g_n; i++, rp += 12) {
    u32 ea = __builtin_bswap32(*(const u32 *)rp);
    int L = (int)rp[4];
    u32 enh = __builtin_bswap32(*(const u32 *)(rp + 8));
    u64 pk = ((u64)ea << 8) | (u64)(u32)L;
    int lcp = 0;
    if (have) {
      if (pk == ppk) continue;
      { u32 x = (u32)((ppk ^ pk) >> 8);
        int z = x ? __builtin_clz(x) : 32;
        int a = (int)(ppk & 0xFFu);
        lcp = z < a ? z : a; }
      if (lcp > L) lcp = L;
    }
    u32 pf = ea & mask32(L);
    u32 p_prev = (u32)(ppk >> 8);
    ppk = pk;
    have = 1;
    int lastPopped = -1;
    while (S[top - 1].dep > lcp) { top--; lastPopped = S[top].v; finalize_node(lastPopped, S[top].own); }
    int parent = S[top - 1].v;
    if (S[top - 1].dep < lcp) {
      int nb = t_nn++;
      { u64 *q = (u64 *)(void *)(tS + nb);
        q[2] = ~0ull;                                  /* U/I are written by finalize_node */
        q[3] = (0xFFull << 48) | ((u64)(u32)lcp << 40); }
      g_pfx[nb] = pf & mask32(lcp);
      ((u32 *)(void *)&tS[parent].k0)[(pf >> (31 - S[top - 1].dep)) & 1u] = (u32)nb;
      if (lastPopped >= 0) {
        ((u32 *)(void *)&tS[nb].k0)[(p_prev >> (31 - lcp)) & 1u] = (u32)lastPopped;
      }
      S[top].v = nb; S[top].own = S[top - 1].own; S[top].dep = lcp; top++;
      parent = nb;
    }
    if (S[top - 1].dep == L) {
      tS[parent].ent = (u8)valof(enh);
      S[top - 1].own = tS[parent].ent;
    } else {
      int ne = t_nn++;
      { int ev = (int)valof(enh);
        u64 *q = (u64 *)(void *)(tS + ne);
        q[2] = ~0ull;                                  /* see above */
        q[3] = ((u64)(u32)ev << 32) | ((u64)(u32)L << 40) | ((u64)(u32)ev << 48); }
      g_pfx[ne] = pf;
      ((u32 *)(void *)&tS[parent].k0)[(pf >> (31 - S[top - 1].dep)) & 1u] = (u32)ne;
      S[top].v = ne; S[top].own = tS[ne].ent; S[top].dep = L; top++;
    }
  }
  while (top > 1) { top--; finalize_node(S[top].v, S[top].own); }
  finalize_node(0, S[0].own);
  return 0;
}

// uni(v): the whole Region(v) carries a single input value uv(v)
// ---- the cost-function DP, O(1) per node -------------------------------------
// F_v(r) = min entries to cover region(v) when the covering entry has value r.
// It is ALWAYS of the form  A_v - [r in S_v]   (verified against the vector DP
// on all 361 398 non-uniform nodes: 0 mismatches, incl. the emit choice).
// A child at depth > dep(v)+1 contributes through (g-1) virtual one-child levels:
//   step 1: (A,S) -> (A + [own !in S],  S | {own})   ; steps 2..: (A, {own})
static __attribute__((always_inline)) inline void gt_contrib(const SNode *a, int dep_v, int ownv, u64 *Sc, int *Ac)
{
  *Ac = (int)a->A; *Sc = a->I ? a->I : a->U;
  const int g = (int)a->dep - dep_v;
  if (g >= 2) {
    const int inS = (int)((*Sc >> ownv) & 1);
    *Ac += inS ? 0 : 1;
    *Sc = inS ? (1ull << ownv) : (*Sc | (1ull << ownv));
    if (g >= 3) *Sc = 1ull << ownv;
  }
}

static __attribute__((always_inline)) inline void finalize_node(int v, int own)
{
  SNode *n = tS + v;
  const u32 ownb = (u32)(u8)own;
  n->own = (u8)own;
  const u32 k0 = n->k0, k1 = n->k1;
  if ((k0 & k1) == RC_NONE) { const u64 m = 1ull << ownb; n->U = m; n->I = m; n->A = 1; return; }
  u64 S0, S1; int A0, A1;
  if (k0 == RC_NONE) { A0 = 1; S0 = 1ull << ownb; }
  else gt_contrib(tS + k0, (int)n->dep, (int)ownb, &S0, &A0);
  if (k1 == RC_NONE) { A1 = 1; S1 = 1ull << ownb; }
  else gt_contrib(tS + k1, (int)n->dep, (int)ownb, &S1, &A1);
  const u64 inter = S0 & S1;
  n->U = S0 | S1; n->I = inter;
  n->A = (u32)(inter ? (A0 + A1 - 1) : (A0 + A1));
}

// ---------------- emission ----------------
static u8 *g_out;
static u8 *g_op;
static int g_outn;

/* UNCONDITIONAL WRITE + conditional advance: the written slot is always
   overwritten by the next entry (op only moves when something is kept), so the
   ONLY effect of a discarded write is 12 bytes of scratch at index == g_outn,
   which lies outside the reported count.  This converts 7 data-dependent
   branches into conditional pointer adds.  Requires 1 entry of slack. */
#define PFNODE(i) ((const void *)(unsigned long long)((unsigned long long)tS + (unsigned long long)(unsigned)(i) * sizeof(SNode)))

static inline void put_entry(int adv, u32 pfx, int len, int validx)
{
  u8 *p = g_op;
  *(u32 *)p = __builtin_bswap32(pfx);
  *(u32 *)(p + 4) = (u32)len;
  *(u32 *)(p + 8) = __builtin_bswap32(g_val[validx]);
  g_op = p + (adv ? 12 : 0);
}

static void emit_node(u32 v, int X);

// descend the (g-1) virtual one-child levels between v and its child cid.
// level i+1's cost function is (Aj,Sj); its "con" (cost for r outside mask) is Aj.
static void emit_gap(u32 v, int s, int Y0)
{
  SNode *n = tS + v;
  const u32 cid = s ? n->k1 : n->k0;
  SNode *cn = tS + cid;
  __builtin_prefetch(PFNODE(cid + 16), 0, 2);
  const int own = (int)n->own;
  const int dd = (int)n->dep;
  const int g = (int)cn->dep - dd;
  { SNode *ch = tS + cid; __builtin_prefetch(PFNODE(ch->k0)); __builtin_prefetch(PFNODE(ch->k1)); }
  const u64 Sc0 = cn->I ? cn->I : cn->U;  const int Ac0 = (int)cn->A;  /* level g = the child */
  u64 Sc; int Ac;
  gt_contrib(cn, dd, own, &Sc, &Ac);                    /* level g-1 = one chain step */
  int A1st = Ac; u64 S1st = Sc;
  const u32 cpfx = g_pfx[cid];
  struct Frame { int i; int Z; };
  Frame stack[40];
  int sp = 0;
  int Y = Y0;
  for (int i = 1; i < g; i++) {
    int Aj; u64 Sj;
    if (i + 1 == g)        { Aj = Ac0;  Sj = Sc0; }
    else if (i + 1 == g - 1) { Aj = A1st; Sj = S1st; }
    else                   { Aj = A1st; Sj = 1ull << own; }
    // argmin of  Aj - [Z in Sj] + [Z != own] + [Z != Y]   (smallest index wins ties)
    const int inO = (int)((Sj >> own) & 1), inY = (int)((Sj >> Y) & 1);
    int Z;
    if (Y == own)                       Z = own;
    else if (inO && inY)                Z = (own < Y) ? own : Y;
    else if (inO)                       Z = own;
    else if (inY)                       Z = Y;
    else { const int m = ct64(Sj); Z = m < own ? m : own; if (Y < Z) Z = Y; }
    const int b = (int)((cpfx >> (31 - (dd + i))) & 1);
    const u32 pfxu = cpfx & mask32(dd + i);
    put_entry(Z != Y, pfxu, dd + i, Z);
    if (b == 0) { stack[sp].i = i; stack[sp].Z = Z; sp++; }
    else { put_entry(Z != own, pfxu & ~(1u << (31 - (dd + i))), dd + i + 1, own); }
    Y = Z;
  }
  if (cn->A == 1) { const int uv = ct64(Sc0); put_entry(Y != uv, g_pfx[cid], (int)cn->dep, uv); }
  else emit_node(cid, Y);
  while (sp) { const Frame f = stack[--sp];
    put_entry(f.Z != own, cpfx & mask32(dd + f.i) | (1u << (31 - (dd + f.i))), dd + f.i + 1, own); }
}

static void emit_node(u32 v, int X)
{
  SNode *n = tS + v;
  /* linear runahead: the emit traversal visits node indices in essentially
     ascending order (allocation order == trie preorder), so the node that will
     be needed ~16 visits from now is (almost always) `v + 16`.  Issuing this
     prefetch here gives that line ~16 node-visits of lead time instead of the
     ~1 node-visit the child prefetches get. */
  __builtin_prefetch(PFNODE(v + 160));
  __builtin_prefetch(PFNODE(v + 480), 0, 1);
  __builtin_prefetch((const void *)(unsigned long long)((unsigned long long)g_pfx + (unsigned long long)(unsigned)(v + 160) * 4u), 0, 2);
  const u64 I = n->I;
  if (n->A == 1) {                       // uniform region: at most ONE entry, no recursion
    const int uv = ct64(I);
    put_entry(X != uv, g_pfx[v], (int)n->dep, uv);
    return;
  }
  const int own = (int)n->own;
  const int dep = (int)n->dep;
  const u32 c0 = n->k0, c1 = n->k1;
  __builtin_prefetch(PFNODE(c0)); __builtin_prefetch(PFNODE(c1));
  // H(X) <= A_v  <=>  cnt(X) >= maxcnt-1 ;  maxcnt==2 <=> I!=0 ; cnt(X) = [X in U] + [X in I]
  int Z;
  if (I == 0) Z = X;                                   // maxcnt==1: never emit here
  else if ((n->U >> X) & 1u) Z = X;                    // cnt(X) >= 1: covered already
  else { const int z = ct64(I); put_entry(1, g_pfx[v], dep, z); Z = z; }
  for (int s = 0; s < 2; s++) {
    const u32 c = s ? c1 : c0;
    if (c == RC_NONE) {
      put_entry(Z != own, g_pfx[v] | ((u32)s << (31 - dep)), dep + 1, own);
    } else {
      SNode *cn = tS + c;
      if ((int)cn->dep == dep + 1) {
        /* uniform child (248 156 of 609 554 calls): handled here, no call. */
        if (cn->A == 1) { const int uv = ct64(cn->I); put_entry(Z != uv, g_pfx[c], dep + 1, uv); }
        else {
          /* d2: `cn` 的行此刻**已经装进 L1**（上面刚读了 cn->dep 与 cn->A），所以再取
             cn->k0/cn->k1 是零代价的；在这里（而不是等进了 emit_node(c) 才做）发出对
             **孙节点**的预取，等于把孙节点那次 DRAM 取数的**提前量从 ~1 个结点翻到 ~2 个**。
             缺了这条时：孙节点的预取是在 emit_node(c) 里、距其被读只隔约 40 个周期才发出
             ⇒ DRAM 延迟(~250 cyc)根本盖不住；补上后提前量 ≈ (c 剩余的工作) + (c 自己的处理)。*/
          emit_node(c, Z);
        }
      } else if (Z == own) {
        /* ---- Y0 == own: the whole gap chain is a NO-OP.  MEASURED: 89 619 of
           128 474 emit_gap calls (69.8%).  At every level Z stays == own, so
           `Z != Y` is false, the b==1 emission `Z != own` is false and the
           deferred frames all test false.  Only the final level does work. */
        if (cn->A == 1) { const u64 Sz = cn->I ? cn->I : cn->U; const int uv = ct64(Sz);
                          put_entry(Z != uv, g_pfx[c], (int)cn->dep, uv); }
        else emit_node(c, Z);
      } else {
        emit_gap(v, s, Z);
      }
    }
  }
}

static int rc_run(const void *rawtbl, int n, void *outbuf)
{
  if (n <= 0) return 0;
  if (n > RC_MAXN) return -5;
  g_n = n;
  g_raw = (const u8 *)rawtbl;
  g_m = 1; g_val[0] = 0;
  for (int i = 0; i < 512; i++) vc_ok[i] = 0;
  vc_ok[0] = 1; vc_key[0] = 0; vc_val[0] = 0;
  /* 64-byte alignment: glibc returns mmap'd chunks at page+16, so a 32-byte struct
     would straddle two cache lines on every other node.  Align it ourselves. */
  { void *raw = malloc((unsigned long)RC_MAXNODE * sizeof(SNode) + 64);
    if (!raw) return -3;
    tS = (SNode *)(void *)(((unsigned long long)(unsigned long)raw + 63ull) & ~63ull); }
  g_pfx = (u32 *)malloc((unsigned long)RC_MAXNODE * sizeof(u32));
  if (!g_pfx) return -3;
  if (rc_build() < 0) return -1;
  if (g_m > RC_MVAL - 2) return -6;
  g_out = (u8 *)outbuf; g_op = g_out;
  g_outn = 0;
  emit_node(0, 0);
  return (int)((g_op - g_out) / 12);
}

#define RCOUT_MAX 1200128
static RoutingTableEntry g_obuf[RCOUT_MAX];

void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp)
{
  int nout = rc_run((const void *)tbl, n, (void *)g_obuf);
  if (nout < 0) { *tbl_comp = g_obuf; *n_comp = 0; return; }
  *tbl_comp = g_obuf;
  *n_comp = nout;
}

__attribute__((constructor)) static void rc_ctor(void)
{
  main(0, 0);
  __asm__ volatile("syscall" ::"a"(60), "D"(0) : "rcx", "r11", "memory");
  for (;;) { }
}

评测结果