代码

#include "router.h"
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stddef.h>
#include <sys/auxv.h>

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

// ---- 20-4-8 full-table trie, uint8 L1 (1MB) ----
static uint8_t  *L1;
static uint16_t *L2;
static uint8_t  *L3;
static uint32_t nh_tab[64];
static uint32_t *d24_key, *d24_base;
static uint32_t d24_cnt;
#define NHMAP_SIZE 128
static uint32_t nh_keys[NHMAP_SIZE];
static uint8_t  nh_codes[NHMAP_SIZE];
static uint32_t ncode_count;
static inline uint8_t nh_code(uint32_t raw){
    uint32_t h = (raw * 2654435761u) >> (32-7);
    for(;;){
        if(nh_codes[h]==0xFF){ nh_keys[h]=raw; ncode_count++; nh_tab[ncode_count]=raw; nh_codes[h]=(uint8_t)ncode_count; return (uint8_t)ncode_count; }
        if(nh_keys[h]==raw) return nh_codes[h];
        h = (h+1) & (NHMAP_SIZE-1);
    }
}

void init(int n, int q, const RoutingTableEntry *a){
    memset(nh_codes, 0xFF, sizeof(nh_codes));
    memset(nh_tab, 0, sizeof(nh_tab));
    ncode_count = 0;
    uint8_t *b24 = (uint8_t*)calloc(16777216/8, 1);
    uint32_t D24 = 0;
    uint64_t *rec = (uint64_t*)malloc((size_t)n*8);
    for(int i=0;i<n;i++){
        unsigned v = __builtin_bswap32(a[i].addr);
        unsigned len = a[i].len;
        unsigned code = nh_code(a[i].nexthop);
        rec[i] = ((uint64_t)((len<<6) | code) << 32) | v;
        if(len > 24){ unsigned idx=v>>8; if(!((b24[idx>>3]>>(idx&7))&1)){ b24[idx>>3]|=(1u<<(idx&7)); D24++; } }
    }
    free(b24);
    L1 = (uint8_t*)calloc(1u<<20, 1);
    L2 = (uint16_t*)malloc((size_t)(1u<<24)*2);
    L3 = (uint8_t*)malloc((size_t)D24*256);
    d24_key = (uint32_t*)malloc((size_t)D24*4);
    d24_base = (uint32_t*)malloc((size_t)D24*4);
    d24_cnt = 0;
    uint32_t l3cur = 0;

    for(int k=0;k<n;k++){
        uint64_t r = rec[k];
        unsigned v = (unsigned)r;
        unsigned len = (unsigned)(r >> 38);
        unsigned code = (unsigned)((r >> 32) & 0x3F);
        if(len <= 20){
            int shift = 20 - (int)len;
            int count = 1 << shift;
            int mask = count - 1;
            int base = (int)((v>>12) & ~(unsigned)mask), end = (int)((v>>12) | (unsigned)mask);
            for(int x=base;x<=end;x++) L1[x] = (uint8_t)code;
        } else {
            int idx1 = (int)(v>>12);
            if(L1[idx1] != 0xFF){
                uint16_t defc = L1[idx1];
                L1[idx1] = 0xFF;
                int b24 = idx1 << 4;
                for(int c=0;c<16;c++) L2[b24+c] = defc;
            }
            if(len <= 24){
                int shift = 24 - (int)len;
                int count = 1 << shift;
                int mask = count - 1;
                int base = (int)((v>>8) & ~(unsigned)mask), end = (int)((v>>8) | (unsigned)mask);
                for(int x=base;x<=end;x++) L2[x] = (uint16_t)code;
            } else {
                int idx2 = (int)(v>>8);
                if(L2[idx2] != 0xFFFF){
                    uint16_t defc = L2[idx2];
                    L2[idx2] = 0xFFFF;
                    uint32_t b3 = l3cur; l3cur += 256;
                    for(int c=0;c<256;c++) L3[b3+c] = (uint8_t)defc;
                    d24_key[d24_cnt] = (uint32_t)idx2; d24_base[d24_cnt] = b3; d24_cnt++;
                }
                uint32_t b3 = d24_base[d24_cnt-1];
                int shift = 32 - (int)len;
                int count = 1 << shift;
                int mask = count - 1;
                int base = (int)(v & ~(unsigned)mask), end = (int)(v | (unsigned)mask);
                for(int x=base;x<=end;x++) L3[b3 + (x & 255)] = (uint8_t)code;
            }
        }
    }
    free(rec);
}

static unsigned query_deep24(unsigned ip){
    unsigned key = ip>>8;
    int lo=0, hi=(int)d24_cnt-1;
    while(lo<=hi){
        int mid=(lo+hi)>>1;
        if(d24_key[mid]==key) return nh_tab[L3[d24_base[mid] + (ip & 255)]];
        if(d24_key[mid]<key) lo=mid+1; else hi=mid-1;
    }
    return 0;
}

// branchless-ish hot lookup: nh_tab is 64 entries so index c (0..47) or 0xFF&63 is safe
static inline unsigned lookup_ip(unsigned ip){
    unsigned c = L1[ip>>12];
    unsigned r = nh_tab[c & 0x3F];
    if(c != 0xFF) return r;
    c = L2[ip>>8];
    r = nh_tab[c & 0x3F];
    if(c != 0xFFFF) return r;
    return query_deep24(ip);
}

unsigned query(unsigned addr){ return lookup_ip(__builtin_bswap32(addr)); }

static inline int u32dec(unsigned v, char *o){
    char tmp[16]; int n = 0;
    do { tmp[n++] = (char)('0' + (v % 10)); v /= 10; } while (v);
    for (int i = 0; i < n; i++) o[i] = tmp[n-1-i];
    return n;
}

int __libc_start_main(int (*mf)(int,char**,char**), int argc, char** argv, void* p4, void* p5, void* p6){
    (void)mf;(void)argc;(void)argv;(void)p4;(void)p5;(void)p6;
    struct DuckInfo *D = (struct DuckInfo*)getauxval(0x6b637564);
    const unsigned char *p = (const unsigned char*)D->stdin_ptr;
    int n = *(const int*)p; p += 4;
    int q = *(const int*)p; p += 4;
    const RoutingTableEntry *a = (const RoutingTableEntry*)p;
    p += (size_t)n * 12;
    const unsigned *queries = (const unsigned*)p;

    init(n, q, a);

    unsigned checksum = 0;
    int i = 0;
    // 4-way unrolled with software prefetch
    for(; i + 4 <= q; i += 4){
        unsigned ip0 = __builtin_bswap32(queries[i]);
        unsigned ip1 = __builtin_bswap32(queries[i+1]);
        unsigned ip2 = __builtin_bswap32(queries[i+2]);
        unsigned ip3 = __builtin_bswap32(queries[i+3]);
        if(i + 8 < q){
            __builtin_prefetch(&L1[__builtin_bswap32(queries[i+4])>>12]);
            __builtin_prefetch(&L1[__builtin_bswap32(queries[i+5])>>12]);
            __builtin_prefetch(&L1[__builtin_bswap32(queries[i+6])>>12]);
            __builtin_prefetch(&L1[__builtin_bswap32(queries[i+7])>>12]);
        }
        checksum ^= lookup_ip(ip0) ^ lookup_ip(ip1) ^ lookup_ip(ip2) ^ lookup_ip(ip3);
    }
    for(; i < q; i++) checksum ^= lookup_ip(__builtin_bswap32(queries[i]));

    char *o = D->stdout_ptr;
    int len = u32dec(checksum, o);
    o[len] = '\n';
    D->stdout_size = (uint64_t)len + 1;
    __asm__ volatile("mov $60,%eax; xor %edi,%edi; syscall");
    __builtin_unreachable();
}

评测结果