# c_sources.py -- the C programs and run scripts used for the computations, stored as text.
# Run this file (plain Python, no arguments) to write them into a subfolder "c_sources" next to it.
# In the stored text the C exclusive-or operator is written as the marker XOR_OP and restored on writing.
#
# Ancillary files for "The Mesirov-Sweet property over F_2 up to degree 33,
# with two quotients of degree two up to degree 28" (D. Niedbala Giraudin, 2026-11-07).
# 
# The C programs and scripts below are stored as text in c_sources.py; running it writes them
# into a subfolder c_sources.  Polynomials over F_2 are stored as unsigned 64-bit integers (bit i = coefficient of T to the power i).
# A bitmap over the monic polynomials g of degree D is indexed by the D low coefficients of g.
# The C programs need D >= 6.  Compile with:  gcc -O3 -march=native -pthread -o NAME NAME.c
# 
# Program A (enumeration of cells, quotients appended on the right):
#   mark.c           mark D KMAX NTHREADS out.bin   all cells with at most KMAX entries equal to 2
#   markcells_thp.c  markcells_thp D NTHREADS cells.txt out.bin   cells listed in a file
# Program B (written separately: other traversal order, continuants by the other recurrence):
#   markB2.c         markB2 D part nparts L1.bin certs.bin   set L1(D) and two-insertion certificates
#   markBc2.c        markBc2 D cells.txt part nparts out.bin  coverage of listed cells
# Certificates:
#   mitm2.c          mitm2 D CUT NPREFIX NTHREADS targets.bin certs.bin   search for f (g outside the cells)
#   chk.c            chk D certs.bin [KQ]   independent check by the Euclidean algorithm
#                    (all quotients of degree 1 or 2, gcd 1, and at most KQ quotients of degree 2 if given)
# Small degrees:
#   kmin.c           kmin D KMAX   least number k(g) of quotients of degree 2, by direct enumeration (degrees 1-5)
# Utilities:
#   uncov.c          uncov D cover.bin out.bin   list of g not covered
#   orbm.c           orbm D out.bin in1.bin in2.bin ...   union of bitmaps
# Cells:
#   cells_d29.csv ... cells_d33.csv   ten random cells (four entries 2) for each degree; the scripts read
#                    them as cells29_A.txt ... cells33_A.txt (same lines without the header line)
# Scripts (as run):
#   run33.sh, run29_32.sh, runk2.sh
# Logs:
#   logs/            outputs of the runs (degree28.log, runk2.log, kmin_d1_5.log, run33.log,
#                    degree33_control.log, run29_32_D29.log ... run29_32_D32.log)
# Independent check in Python (numpy only):
#   verif_ms_f2.py   arithmetic self-test; exhaustive recomputation of the counts of k = 0, 1, 2 at the
#                    largest degree among 22, 20, 18, 16 fitting the memory and time budgets set at the top;
#                    check of the certificate samples below, with a control on corrupted certificates
#   certs_d28_two_insertions.csv   100000 certificates (g, f) for g in L1(28), at most two quotients of degree 2
#   certs_d33_sample.csv           100000 certificates (g, f) for g outside the ten cells in degree 33
# 

import os

XOR_CHAR = chr(94)
FILES = {}
FILES['mark.c'] = r'''/* mark.c : union coverage of cells (degree patterns in {1,2}) over F2.
   usage: mark D KMAX NTHREADS out.bin  -> covers all cells with <= KMAX twos.
   Each thread processes whole cells into its own bitmap; OR at end. */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <pthread.h>
#include <time.h>
typedef uint64_t u64;
static int D, KM, NT; static int npat=0; static int (*pats)[64]; static int *plens;
static int cur[64];
static void comp(int s,int len,int k){
  if(s==D){ memcpy(pats[npat],cur,sizeof(int)*len); plens[npat]=len; npat++; return; }
  cur[len]=1; comp(s+1,len+1,k);
  if(s+2<=D && k<KM){ cur[len]=2; comp(s+2,len+1,k+1); }
}
typedef struct { u64 *bm; int *pat; int plen; u64 mask; } ctx_t;
static void dfs(ctx_t *c,int i,u64 K1,u64 K0){
  if(i==c->plen-1){ /* last PQ: emit leaves directly */
    u64 m=c->mask, *bm=c->bm;
    if(c->pat[i]==1){ u64 g=((K1<<1)XOR_OPK0)&m; bm[g>>6]|=1ULL<<(g&63); gXOR_OP=K1&m; bm[g>>6]|=1ULL<<(g&63); }
    else { u64 base=((K1<<2)XOR_OPK0)&m; u64 t1=(K1<<1)&m, t0=K1&m;
      u64 g=base; bm[g>>6]|=1ULL<<(g&63); g=baseXOR_OPt0; bm[g>>6]|=1ULL<<(g&63);
      g=baseXOR_OPt1; bm[g>>6]|=1ULL<<(g&63); g=baseXOR_OPt1XOR_OPt0; bm[g>>6]|=1ULL<<(g&63); }
    return; }
  if(c->pat[i]==1){ dfs(c,i+1,(K1<<1)XOR_OPK0,K1); dfs(c,i+1,(K1<<1)XOR_OPK1XOR_OPK0,K1); }
  else { dfs(c,i+1,(K1<<2)XOR_OPK0,K1); dfs(c,i+1,(K1<<2)XOR_OPK1XOR_OPK0,K1); dfs(c,i+1,(K1<<2)XOR_OP(K1<<1)XOR_OPK0,K1); dfs(c,i+1,(K1<<2)XOR_OP(K1<<1)XOR_OPK1XOR_OPK0,K1); }
}
static size_t W; static u64 **bms; static int nextcell=0; static pthread_mutex_t mu=PTHREAD_MUTEX_INITIALIZER;
static void *worker(void *arg){ long t=(long)arg; ctx_t c; c.bm=bms[t]; c.mask=(1ULL<<D)-1;
  for(;;){ pthread_mutex_lock(&mu); int k=nextcell++; pthread_mutex_unlock(&mu); if(k>=npat) break;
    c.pat=pats[k]; c.plen=plens[k]; dfs(&c,0,1,0); }
  return NULL; }
int main(int argc,char**argv){
  D=atoi(argv[1]); KM=atoi(argv[2]); NT=atoi(argv[3]);
  pats=malloc(sizeof(int[64])*200000); plens=malloc(sizeof(int)*200000); comp(0,0,0);
  W=(1ULL<<D)/64; bms=malloc(sizeof(u64*)*NT); for(int t=0;t<NT;t++) bms[t]=calloc(W,8);
  struct timespec a,b; clock_gettime(CLOCK_MONOTONIC,&a);
  pthread_t th[8]; for(long t=0;t<NT;t++) pthread_create(&th[t],0,worker,(void*)t); for(int t=0;t<NT;t++) pthread_join(th[t],0);
  for(int t=1;t<NT;t++) for(size_t w=0;w<W;w++) bms[0][w]|=bms[t][w];
  clock_gettime(CLOCK_MONOTONIC,&b);
  long cov=0; for(size_t w=0;w<W;w++) cov+=__builtin_popcountll(bms[0][w]);
  double sec=(b.tv_sec-a.tv_sec)+1e-9*(b.tv_nsec-a.tv_nsec);
  printf("D=%d KMAX=%d cells=%d covered=%ld uncovered=%ld time=%.1fs ns/leaf=%.2f\n",D,KM,npat,cov,(1L<<D)-cov,sec,1e9*sec*NT/((double)npat*(1ULL<<D)));
  if(argc>4){ FILE*f=fopen(argv[4],"wb"); fwrite(bms[0],8,W,f); fclose(f); }
  return 0; }
'''
FILES['markcells_thp.c'] = r'''/* markcells D NTHREADS cells.txt out.bin : union coverage of the listed cells.
   cells.txt: one cell per line, string of '1'/'2' (PQ degrees), summing to D. */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <pthread.h>
#include <time.h>
#include <sys/mman.h>
typedef uint64_t u64;
static int D, NT, npat=0; static int pats[256][64], plens[256];
typedef struct { u64 *bm; int *pat; int plen; u64 mask; } ctx_t;
static void dfs(ctx_t *c,int i,u64 K1,u64 K0){
  if(i==c->plen-1){ u64 m=c->mask, *bm=c->bm;
    if(c->pat[i]==1){ u64 g=((K1<<1)XOR_OPK0)&m; bm[g>>6]|=1ULL<<(g&63); gXOR_OP=K1&m; bm[g>>6]|=1ULL<<(g&63); }
    else { u64 base=((K1<<2)XOR_OPK0)&m, t1=(K1<<1)&m, t0=K1&m; u64 g=base; bm[g>>6]|=1ULL<<(g&63); g=baseXOR_OPt0; bm[g>>6]|=1ULL<<(g&63); g=baseXOR_OPt1; bm[g>>6]|=1ULL<<(g&63); g=baseXOR_OPt1XOR_OPt0; bm[g>>6]|=1ULL<<(g&63); }
    return; }
  if(c->pat[i]==1){ dfs(c,i+1,(K1<<1)XOR_OPK0,K1); dfs(c,i+1,(K1<<1)XOR_OPK1XOR_OPK0,K1); }
  else { dfs(c,i+1,(K1<<2)XOR_OPK0,K1); dfs(c,i+1,(K1<<2)XOR_OPK1XOR_OPK0,K1); dfs(c,i+1,(K1<<2)XOR_OP(K1<<1)XOR_OPK0,K1); dfs(c,i+1,(K1<<2)XOR_OP(K1<<1)XOR_OPK1XOR_OPK0,K1); }
}
static size_t W; static u64 **bms; static int nextcell=0; static pthread_mutex_t mu=PTHREAD_MUTEX_INITIALIZER;
static void *worker(void *arg){ long t=(long)arg; ctx_t c; c.bm=bms[t]; c.mask=(1ULL<<D)-1;
  for(;;){ pthread_mutex_lock(&mu); int k=nextcell++; pthread_mutex_unlock(&mu); if(k>=npat) break;
    c.pat=pats[k]; c.plen=plens[k]; dfs(&c,0,1,0); fprintf(stderr,"cell %d done\n",k); }
  return NULL; }
int main(int argc,char**argv){
  D=atoi(argv[1]); NT=atoi(argv[2]); FILE*f=fopen(argv[3],"r"); char line[256];
  while(fgets(line,256,f)){ int s=0,l=0; for(char*p=line;*p=='1'||*p=='2';p++){ pats[npat][l++]=*p-'0'; s+=*p-'0'; } if(l==0) continue; if(s!=D){ fprintf(stderr,"bad cell sum %d\n",s); return 1;} plens[npat]=l; npat++; }
  fclose(f);
  W=(1ULL<<D)/64; bms=malloc(sizeof(u64*)*NT); for(int t=0;t<NT;t++){ size_t by=W*8; size_t al=(by+(2u<<20)-1)&~(size_t)((2u<<20)-1); bms[t]=aligned_alloc(2u<<20,al); if(!bms[t]){fprintf(stderr,"oom\n");return 1;} madvise(bms[t],al,MADV_HUGEPAGE); memset(bms[t],0,by); }
  struct timespec a,b; clock_gettime(CLOCK_MONOTONIC,&a);
  pthread_t th[8]; for(long t=0;t<NT;t++) pthread_create(&th[t],0,worker,(void*)t); for(int t=0;t<NT;t++) pthread_join(th[t],0);
  for(int t=1;t<NT;t++) for(size_t w=0;w<W;w++) bms[0][w]|=bms[t][w];
  clock_gettime(CLOCK_MONOTONIC,&b);
  long cov=0; for(size_t w=0;w<W;w++) cov+=__builtin_popcountll(bms[0][w]);
  double sec=(b.tv_sec-a.tv_sec)+1e-9*(b.tv_nsec-a.tv_nsec);
  printf("D=%d cells=%d covered=%ld uncovered=%ld time=%.1fs ns/leaf=%.2f\n",D,npat,cov,(1L<<D)-cov,sec,1e9*sec*NT/((double)npat*(1ULL<<D)));
  FILE*o=fopen(argv[4],"wb"); fwrite(bms[0],8,W,o); fclose(o); return 0; }
'''
FILES['markB2.c'] = r'''/* markB2 D part nparts out_L1.bin out_certs.bin
   INDEPENDENT verifier for "at most two quotients of degree 2" (backward recurrence,
   odometer with a_1 fastest, inner loop over a_1 unrolled).
   Phase 1: cells with <= 1 degree-2 quotient -> bitmap C1, L1 = sorted complement.
   Phase 2: cells with exactly two degree-2 quotients at cumulative degrees p<q (q>=p+2),
   restricted to p % nparts == part; for g in L1 store f = K(a_2..a_r) (first found). */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <sys/mman.h>
typedef unsigned long long U;
static int D; static U *C1; static U *L1; static long nL1; static U *F; static unsigned char *got;
static inline U mulq(int deg,int c,U x){ U r=x<<deg; if(c&1) rXOR_OP=x; if(deg==2 && (c&2)) rXOR_OP=x<<1; return r; }
static inline long findL1(U g){ long lo=0,hi=nL1-1; while(lo<=hi){ long m=(lo+hi)>>1; if(L1[m]==g) return m; if(L1[m]<g) lo=m+1; else hi=m-1; } return -1; }
static void run_cell(const int *deg,int r,int phase){
  int c[64]; U X[66],Y[66]; for(int i=0;i<r;i++) c[i]=0; X[r]=1; Y[r]=0;
  for(int i=r-1;i>=1;i--){ X[i]=mulq(deg[i],0,X[i+1])XOR_OPY[i+1]; Y[i]=X[i+1]; }
  U mask=(1ULL<<D)-1; int d0=deg[0]; int n0=1<<d0;
  for(;;){ U x1=X[1], y1=Y[1];
    if(phase==1){ for(int c0=0;c0<n0;c0++){ U g=(mulq(d0,c0,x1)XOR_OPy1)&mask; C1[g>>6]|=1ULL<<(g&63); } }
    else { for(int c0=0;c0<n0;c0++){ U g=(mulq(d0,c0,x1)XOR_OPy1)&mask; if(!((C1[g>>6]>>(g&63))&1ULL)){ long k=findL1(g); if(k>=0 && !got[k]){ got[k]=1; F[k]=x1; } } } }
    int i=1; while(i<r){ c[i]++; if(c[i]<(1<<deg[i])) break; c[i]=0; i++; }
    if(i==r) break;
    for(int j=i;j>=1;j--){ X[j]=mulq(deg[j],c[j],X[j+1])XOR_OPY[j+1]; Y[j]=X[j+1]; } }
}
static int mk(int *deg,int p,int q){ int r=0,s=0; while(s<D){ if(s==p||s==q){ deg[r++]=2; s+=2; } else { deg[r++]=1; s+=1; } } return r; }
int main(int argc,char**argv){ D=atoi(argv[1]); int part=atoi(argv[2]), np=atoi(argv[3]);
  size_t W=((1ULL<<D)+63)/64, by=W*8, al=(by+(2u<<20)-1)&~(size_t)((2u<<20)-1);
  C1=aligned_alloc(2u<<20,al); madvise(C1,al,MADV_HUGEPAGE); memset(C1,0,by);
  int deg[64]; int r;
  r=mk(deg,-5,-5); run_cell(deg,r,1);
  for(int p=0;p<=D-2;p++){ r=mk(deg,p,-5); run_cell(deg,r,1); }
  nL1=0; for(size_t w=0;w<W;w++) nL1+=__builtin_popcountll(~C1[w]);
  L1=malloc(8*nL1); F=malloc(8*nL1); got=calloc(nL1,1); long k=0;
  for(size_t w=0;w<W;w++){ U x=~C1[w]; while(x){ int b=__builtin_ctzll(x); L1[k++]=(w<<6)|b; x&=x-1; } }
  printf("phase1: uncovered by <=1 insertion: %ld\n",nL1); fflush(stdout);
  for(int p=0;p<=D-4;p++) if(p%np==part) for(int q=p+2;q<=D-2;q++){ r=mk(deg,p,q); run_cell(deg,r,2); }
  FILE*fl=fopen(argv[4],"wb"); fwrite(L1,8,nL1,fl); fclose(fl);
  FILE*fc=fopen(argv[5],"wb"); long nc=0; for(long i=0;i<nL1;i++) if(got[i]){ U g=L1[i]|(1ULL<<D); fwrite(&g,8,1,fc); fwrite(&F[i],8,1,fc); nc++; } fclose(fc);
  printf("phase2: certified %ld of %ld\n",nc,nL1); return 0; }
'''
FILES['markBc2.c'] = r'''/* markBc2 D cells.txt part nparts out.bin : INDEPENDENT coverage, backward recurrence,
   odometer with a_1 fastest; inner loop over a_1 unrolled; huge-page bitmap. */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <sys/mman.h>
typedef unsigned long long U;
static int D; static U *C;
static inline U mulq(int deg,int c,U x){ U r=x<<deg; if(c&1) rXOR_OP=x; if(deg==2 && (c&2)) rXOR_OP=x<<1; return r; }
static void run_cell(const int *deg,int r){
  int c[64]; U X[66],Y[66]; for(int i=0;i<r;i++) c[i]=0; X[r]=1; Y[r]=0;
  for(int i=r-1;i>=1;i--){ X[i]=mulq(deg[i],0,X[i+1])XOR_OPY[i+1]; Y[i]=X[i+1]; }
  U mask=(1ULL<<D)-1; int d0=deg[0]; int n0=1<<d0;
  for(;;){
    /* all choices of a_1 at once: g = a_1*X[1] + Y[1] */
    U x1=X[1], y1=Y[1];
    for(int c0=0;c0<n0;c0++){ U g=(mulq(d0,c0,x1)XOR_OPy1)&mask; C[g>>6]|=1ULL<<(g&63); }
    int i=1; while(i<r){ c[i]++; if(c[i]<(1<<deg[i])) break; c[i]=0; i++; }
    if(i==r) break;
    for(int j=i;j>=1;j--){ X[j]=mulq(deg[j],c[j],X[j+1])XOR_OPY[j+1]; Y[j]=X[j+1]; }
  }
}
int main(int argc,char**argv){ D=atoi(argv[1]); int part=atoi(argv[3]), np=atoi(argv[4]);
  size_t W=(1ULL<<D)/64; size_t by=W*8; size_t al=(by+(2u<<20)-1)&~(size_t)((2u<<20)-1);
  C=aligned_alloc(2u<<20,al); if(!C) return 2; madvise(C,al,MADV_HUGEPAGE); memset(C,0,by);
  FILE*f=fopen(argv[2],"r"); char line[256]; int idx=0;
  while(fgets(line,256,f)){ int deg[64],r=0,s=0; for(char*p=line;*p=='1'||*p=='2';p++){ deg[r++]=*p-'0'; s+=*p-'0'; } if(!r) continue;
    if(s!=D){ fprintf(stderr,"bad cell\n"); return 1; }
    if(idx%np==part){ run_cell(deg,r); fprintf(stderr,"B cell %d done\n",idx); } idx++; }
  FILE*o=fopen(argv[5],"wb"); fwrite(C,8,W,o); fclose(o); return 0; }
'''
FILES['mitm2.c'] = r'''/* mitm.c : for each target g (degree D, monic, given by low D bits), find f with
   f/g = [0;a1..ar], all deg a_i in {1,2}.  Randomised meet-in-the-middle:
   prefix table of NP random prefixes of total degree K (uniform over sequences),
   then V = g*K(a2..aj) mod q, U = (g+q'V)/q, suffix (U,V) checked by Euclid.
   Certificate f = r*U + r'*V.  Exhaustive fallback over all prefixes at cuts K, K+1.
   usage: mitm D K NP NTHREADS targets.bin certs.bin   (targets: uint64 low-bit codes) */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <pthread.h>
typedef uint64_t u64;
static int D,KC; static long NP; static int NT;
static inline int dg(u64 a){ return 63-__builtin_clzll(a); }   /* a != 0 */
static inline u64 pmul(u64 a,u64 b){ u64 r=0; while(b){ int i=__builtin_ctzll(b); rXOR_OP=a<<i; b&=b-1; } return r; }
static inline u64 pmod(u64 a,u64 m){ int dm=dg(m); while(a && dg(a)>=dm) aXOR_OP=m<<(dg(a)-dm); return a; }
static inline u64 pdiv(u64 a,u64 m,u64 *rem){ int dm=dg(m); u64 q=0; while(a && dg(a)>=dm){ int s=dg(a)-dm; q|=1ULL<<s; aXOR_OP=m<<s; } *rem=a; return q; }
typedef struct { u64 q,q1,r,r1; } pref_t;
static pref_t *P;
static double cnt[80];
static u64 rng=88172645463325252ULL; static inline u64 xr(void){ rngXOR_OP=rng<<13; rngXOR_OP=rng>>7; rngXOR_OP=rng<<17; return rng; }
static void build_prefixes(void){
  cnt[0]=1; cnt[1]=2; for(int s=2;s<80;s++) cnt[s]=2*cnt[s-1]+4*cnt[s-2];
  P=malloc(sizeof(pref_t)*NP);
  for(long i=0;i<NP;i++){
    /* matrix [[q,q1],[r,r1]] = prod [[a,1],[1,0]] ; start identity */
    u64 q=1,q1=0,r=0,r1=1; int s=KC;
    while(s>0){ int e; double u=(double)(xr()>>11)/9007199254740992.0;
      if(s==1) e=1; else e = (u < 2*cnt[s-1]/cnt[s]) ? 1 : 2;
      u64 a = (e==1) ? (2|(xr()&1)) : (4|(xr()&3));
      u64 nq=pmul(a,q)XOR_OPq1, nr=pmul(a,r)XOR_OPr1; q1=q; q=nq; r1=r; r=nr; s-=e; }
    P[i].q=q; P[i].q1=q1; P[i].r=r; P[i].r1=r1; }
}
/* suffix check: U/V = [b1;...;bt], all deg in {1,2}, gcd 1 */
static inline int okpair(u64 U,u64 V){
  if(!V) return 0;
  while(V){ int du=dg(U),dv=dg(V); int e=du-dv; if(e<1||e>2) return 0; u64 R; (void)pdiv(U,V,&R); U=V; V=R; }
  return U==1;
}
static inline int trial(u64 g,u64 q,u64 q1,u64 r,u64 r1,int m,u64 *f){
  u64 V=pmod(pmul(pmod(g,q),r),q);
  if(V==0 || dg(V)>=m) return 0;
  u64 rem; u64 U=pdiv(gXOR_OPpmul(q1,V),q,&rem); if(rem) return 0; /* cannot happen */
  if(dg(U)!=m) return 0;
  if(!okpair(U,V)) return 0;
  *f = pmul(r,U)XOR_OPpmul(r1,V); return 1;
}
/* exhaustive fallback: DFS over all prefixes of total degree exactly kk */
static int ex_found; static u64 ex_f;
static void exdfs(u64 g,int kk,int s,u64 q,u64 q1,u64 r,u64 r1){
  if(ex_found) return;
  if(s==kk){ u64 f; if(trial(g,q,q1,r,r1,D-kk,&f)){ ex_found=1; ex_f=f; } return; }
  for(int e=1;e<=2;e++){ if(s+e>kk) break; u64 lo=(e==1)?2:4, hi=(e==1)?4:8;
    for(u64 a=lo;a<hi;a++){ exdfs(g,kk,s+e,pmul(a,q)XOR_OPq1,q,pmul(a,r)XOR_OPr1,r); if(ex_found) return; } }
}
static u64 *tg; static long ntg; static u64 *cf; static long next=0; static pthread_mutex_t mu=PTHREAD_MUTEX_INITIALIZER;
static long nfall=0, nfail=0; static long ntrials=0;
static void *worker(void *arg){
  (void)arg; int m=D-KC;
  for(;;){ pthread_mutex_lock(&mu); long i0=next; next+=1024; pthread_mutex_unlock(&mu); if(i0>=ntg) break;
    long i1=i0+1024; if(i1>ntg) i1=ntg;
    for(long i=i0;i<i1;i++){ u64 g=tg[i]|(1ULL<<D); u64 f=0; int ok=0;
      long p; for(p=0;p<NP;p++){ if(trial(g,P[p].q,P[p].q1,P[p].r,P[p].r1,m,&f)){ ok=1; break; } } __sync_fetch_and_add(&ntrials,p+1);
      if(!ok){ __sync_fetch_and_add(&nfall,1);
        for(int kk=KC;kk<=KC+1 && !ok;kk++){ ex_found=0; /* not thread safe: guard */ 
          pthread_mutex_lock(&mu); ex_found=0; exdfs(g,kk,0,1,0,0,1); if(ex_found){ ok=1; f=ex_f; } pthread_mutex_unlock(&mu); } }
      if(!ok){ __sync_fetch_and_add(&nfail,1); f=0; }
      cf[i]=f; } }
  return NULL; }
int main(int argc,char**argv){
  D=atoi(argv[1]); KC=atoi(argv[2]); NP=atol(argv[3]); NT=atoi(argv[4]);
  FILE*fi=fopen(argv[5],"rb"); fseek(fi,0,SEEK_END); ntg=ftell(fi)/8; fseek(fi,0,SEEK_SET); tg=malloc(8*ntg); if(fread(tg,8,ntg,fi)!=(size_t)ntg) return 1; fclose(fi);
  cf=malloc(8*ntg); build_prefixes();
  pthread_t th[8]; for(int t=0;t<NT;t++) pthread_create(&th[t],0,worker,0); for(int t=0;t<NT;t++) pthread_join(th[t],0);
  FILE*fo=fopen(argv[6],"wb"); for(long i=0;i<ntg;i++){ u64 g=tg[i]|(1ULL<<D); fwrite(&g,8,1,fo); fwrite(&cf[i],8,1,fo);} fclose(fo);
  printf("D=%d targets=%ld fallback=%ld FAIL=%ld avg_trials=%.1f\n",D,ntg,nfall,nfail,(double)ntrials/ntg); return 0; }
'''
FILES['chk.c'] = r'''/* chk D certs.bin [KQ] : independent check of (g,f) pairs:
   deg g = D, 0 <= deg f < D, Euclid quotients all of degree 1 or 2, gcd = 1,
   and (if KQ given) at most KQ quotients of degree 2.
   Written independently of mitm.c (bit-by-bit long division). */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef unsigned long long U;
static int degree(U a){ int d=-1; for(int i=0;i<64;i++) if((a>>i)&1ULL) d=i; return d; }
int main(int c,char**v){ int D=atoi(v[1]); int KQ=(c>3)?atoi(v[3]):1000; FILE*f=fopen(v[2],"rb"); U g,h; long n=0,bad=0, maxq=0; long hist[4]={0};
 while(fread(&g,8,1,f)==1 && fread(&h,8,1,f)==1){ n++;
   int ok = (degree(g)==D) && h!=0 && degree(h)<D;
   U A=g,B=h; int nq2=0;
   while(ok && B){ int da=degree(A), db=degree(B); int e=da-db; if(e<1||e>2){ ok=0; break; } if(e==2) nq2++;
     /* remainder by repeated subtraction of shifted B */
     U R=A; for(int s=e;s>=0;s--){ if((R>>(db+s))&1ULL) RXOR_OP=B<<s; }
     if(R && degree(R)>=db){ ok=0; break; }
     A=B; B=R; }
   if(ok && A!=1ULL) ok=0;
   if(ok && nq2>KQ) ok=0;
   if(!ok){ bad++; if(bad<5) printf("BAD g=%llx f=%llx\n",g,h); }
   else { if(nq2>maxq) maxq=nq2; }
 }
 printf("D=%d checked=%ld bad=%ld max#deg2=%ld\n",D,n,bad,maxq); return bad?1:0; }
'''
FILES['uncov.c'] = r'''/* uncov D cover.bin out.bin : list low-bit codes of g NOT covered */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int main(int c,char**v){ int D=atoi(v[1]); size_t W=(1ULL<<D)/64; uint64_t *b=malloc(W*8);
 FILE*f=fopen(v[2],"rb"); if(fread(b,8,W,f)!=W) return 1; fclose(f); FILE*o=fopen(v[3],"wb"); long n=0;
 for(size_t w=0;w<W;w++){ uint64_t x=~b[w]; while(x){ int i=__builtin_ctzll(x); uint64_t g=(w<<6)|i; fwrite(&g,8,1,o); n++; x&=x-1; } }
 fclose(o); printf("uncovered %ld\n",n); return 0; }
'''
FILES['orbm.c'] = r'''/* orbm D out.bin in1.bin in2.bin ... : OR of bitmaps, prints uncovered count */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int main(int c,char**v){ int D=atoi(v[1]); size_t W=(1ULL<<D)/64; uint64_t *a=calloc(W,8), *b=malloc(W*8);
 for(int k=3;k<c;k++){ FILE*f=fopen(v[k],"rb"); if(fread(b,8,W,f)!=W) return 1; fclose(f); for(size_t w=0;w<W;w++) a[w]|=b[w]; }
 long n=0; for(size_t w=0;w<W;w++) n+=__builtin_popcountll(~a[w]); FILE*o=fopen(v[2],"wb"); fwrite(a,8,W,o); fclose(o);
 printf("uncovered %ld\n",n); return 0; }
'''
FILES['kmin.c'] = r'''/* For each monic g of degree d over F2, compute kmin(g) = minimal number of
   degree-2 partial quotients among f/g with all PQ degrees in {1,2}
   (255 if none with <= KMAX insertions). DFS over CF sequences. */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef uint64_t u64;
static int D, KMAX; static unsigned char *best;
static inline u64 mulsmall(u64 a, u64 x){ /* a = small poly (deg<=2), x poly */
  u64 r=0; for(int i=0;i<3;i++) if((a>>i)&1) r XOR_OP= x<<i; return r; }
static void dfs(int deg, int k, u64 K1, u64 K0){
  if(deg==D){ u64 idx = K1 & ((1ULL<<D)-1); if(best[idx]>k) best[idx]=k; return; }
  /* linear PQs T, T+1 */
  if(deg+1<=D){ dfs(deg+1,k, mulsmall(2,K1)XOR_OPK0, K1); dfs(deg+1,k, mulsmall(3,K1)XOR_OPK0, K1); }
  if(deg+2<=D && k<KMAX){ for(u64 a=4;a<8;a++) dfs(deg+2,k+1, mulsmall(a,K1)XOR_OPK0, K1); }
}
int main(int argc,char**argv){
  D=atoi(argv[1]); KMAX=atoi(argv[2]);
  best=malloc(1ULL<<D); for(u64 i=0;i<(1ULL<<D);i++) best[i]=255;
  dfs(0,0,1,0);
  long cnt[256]={0}; for(u64 i=0;i<(1ULL<<D);i++) cnt[best[i]]++;
  printf("d=%d:",D); for(int k=0;k<=KMAX;k++) printf(" k%d=%ld",k,cnt[k]); printf(" none=%ld\n",cnt[255]);
  if(argc>3){ FILE*f=fopen(argv[3],"wb"); fwrite(best,1,1ULL<<D,f); fclose(f);} 
  return 0; }
'''
FILES['run33.sh'] = r'''#!/bin/bash
# pipeline for degree 33 (pre-registered cells33_A.txt)
set -e
cd "$(dirname "$0")"
echo "start $(date)"
./markcells_thp 33 2 cells33_A.txt cov33A.bin 2> run33A.err
echo "A done $(date)"
./markBc2 33 cells33_A.txt 0 2 cov33B0.bin 2> run33B0.err &
./markBc2 33 cells33_A.txt 1 2 cov33B1.bin 2> run33B1.err &
wait
echo "B done $(date)"
./orbm 33 cov33B.bin cov33B0.bin cov33B1.bin
if cmp -s cov33A.bin cov33B.bin; then echo "A == B bitmaps identical"; else echo "A != B MISMATCH"; fi
./uncov 33 cov33A.bin unc33.bin
./mitm2 33 17 1048576 2 unc33.bin cert33.bin
echo "MITM done $(date)"
./chk 33 cert33.bin
echo "end $(date)"
'''
FILES['run29_32.sh'] = r'''#!/bin/bash
cd "$(dirname "$0")"
for D in 29 30 31 32; do
  K=$((D/2))
  {
  echo "=== D=$D start $(date)"
  ./markcells_thp $D 2 cells${D}_A.txt cov${D}A.bin 2> /dev/null
  ./markBc2 $D cells${D}_A.txt 0 2 cov${D}B0.bin 2> /dev/null &
  ./markBc2 $D cells${D}_A.txt 1 2 cov${D}B1.bin 2> /dev/null &
  wait
  ./orbm $D cov${D}B.bin cov${D}B0.bin cov${D}B1.bin
  if cmp -s cov${D}A.bin cov${D}B.bin; then echo "D=$D A == B bitmaps identical"; else echo "D=$D A != B MISMATCH"; fi
  ./uncov $D cov${D}A.bin unc${D}.bin
  ./mitm2 $D $K 1048576 2 unc${D}.bin cert${D}.bin
  ./chk $D cert${D}.bin
  rm -f cov${D}B0.bin cov${D}B1.bin cov${D}B.bin
  echo "=== D=$D end $(date)"
  } > run29_32_D${D}.log 2>&1
done
'''
FILES['runk2.sh'] = r'''#!/bin/bash
cd "$(dirname "$0")"
for D in $(seq 6 27); do
  A2=$(./mark $D 2 2 | grep -o "uncovered=[0-9]*")
  ./mark $D 1 2 covk1_$D.bin > /dev/null; ./uncov $D covk1_$D.bin LA_$D.bin > /dev/null
  ./markB2 $D 0 2 LB0_$D.bin cB0_$D.bin > /dev/null &
  ./markB2 $D 1 2 LB1_$D.bin cB1_$D.bin > /dev/null &
  wait
  if cmp -s LA_$D.bin LB0_$D.bin && cmp -s LA_$D.bin LB1_$D.bin; then same=yes; else same=NO; fi
  cat cB0_$D.bin cB1_$D.bin > cB_$D.bin
  CHK=$(./chk $D cB_$D.bin 2)
  N1=$(( $(stat -c %s LA_$D.bin) / 8 ))
  COV=$(python3 -c "
import numpy as np
L=np.fromfile('LA_$D.bin',dtype=np.uint64); c=np.fromfile('cB_$D.bin',dtype=np.uint64).reshape(-1,2)
s=np.unique(c[:,0]&np.uint64((1<<$D)-1)); print('L1_certified_all=%s' % bool(np.isin(L,s).all()))")
  echo "D=$D A_k<=2:$A2 |L1|=$N1 L1(A)==L1(B):$same $COV | $CHK"
  rm -f covk1_$D.bin
done
'''

def main():
    here = os.path.dirname(os.path.abspath(__file__))
    od = os.path.join(here, "c_sources")
    os.makedirs(od, exist_ok=True)
    for name, text in FILES.items():
        with open(os.path.join(od, name), "w") as f:
            f.write(text.replace("XOR_OP", XOR_CHAR))
        print("written", name, flush=True)

main()