代码

#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));
// full 20-4-8 trie (from solution_nosort), but with a PURE-READ query benchmark
static uint16_t *L1; static uint16_t *L2; static uint8_t *L3;
static uint32_t nh_tab[48]; 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)); ncode_count=0; nh_tab[0]=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=(uint16_t*)calloc(1u<<20,2); 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]=(uint16_t)code; }
        else { int idx1=(int)(v>>12); if(L1[idx1]!=0xFFFF){ uint16_t defc=L1[idx1]; L1[idx1]=0xFFFF; 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);
}
// PURE READ benchmark: just read L1[ip>>12] and accumulate
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;
    for(int i=0;i<q;i++){ unsigned ip=__builtin_bswap32(queries[i]); checksum ^= L1[ip>>12]; }
    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();
}

评测结果