nx_phash_index_gate.nx source
↩ module page · 154 lines · 8741 B
1// nx_phash_index_gate.nx -- referee for the sublinear Hamming index (nx_phash_index, BK-tree).
2// PROVES, in-process (no external elf, no shell orchestration), what a TinEye-scale index must
3// guarantee:
4// row1 EXACTNESS (clustered): over K clustered near-dup queries the BK-tree match SET equals the
5// linear O(N) brute-force set -- no false positives, no recall loss.
6// row2 MEASURED-EXCEED: average candidates examined by the BK-tree << N (sublinear pruning),
7// printed as an honest ratio on a realistic clustered corpus.
8// row3 EXACTNESS (adversarial uniform-random): correctness HOLDS even where pruning is weak --
9// the answer is exact regardless of speed (the liar-kill that separates "fast" from "right").
10// row4 DETERMINISM: identical query -> identical candidates-examined AND identical match count,
11// twice (bit-exact; the sovereign moat over float ANN indexes).
12// row5 BUILD INTEGRITY: every one of the N fingerprints is present in the tree.
13// GREEN iff 5/5. Deterministic corpus (MMIX LCG, fixed seed) so the verdict is reproducible.
14// Durable verdict -> knowledge/status/phash_index_gate.log. license_tier: ORIGINAL
15import "nx_phash_index.nx"
16
17func g_puts(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
18func g_num(v: i64) -> i64 { let bb: *u8=sys_mmap(28); var m: i64=v; if m<0{m=0-m;sys_write(1,"-" as *u8,1)}; let t: *u8=sys_mmap(28); var k: i64=0; if m==0{t[0]=(48 as u8);k=1}; while m>0{t[k]=((48+(m%10)) as u8);m=m/10;k=k+1}; var i: i64=0; while i<k{bb[i]=t[k-1-i];i=i+1}; sys_write(1,bb,k); return 0 }
19func g_w(fd: i64, s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(fd,s,n); return 0 }
20func g_wn(fd: i64, v: i64) -> i64 { let bb: *u8=sys_mmap(28); var m: i64=v; if m<0{m=0-m}; let t: *u8=sys_mmap(28); var k: i64=0; if m==0{t[0]=(48 as u8);k=1}; while m>0{t[k]=((48+(m%10)) as u8);m=m/10;k=k+1}; var i: i64=0; while i<k{bb[i]=t[k-1-i];i=i+1}; sys_write(fd,bb,k); return 0 }
21
22// MMIX LCG (Knuth): deterministic 64-bit stream from a fixed seed. s[0] holds the state.
23func g_rng(s: *i64) -> i64 { let x: i64 = s[0] * 0x5851F42D4C957F2D + 0x14057B7EF767814F; s[0]=x; return x }
24// a bit position 0..63 from the mid bits of a fresh LCG word
25func g_bitpos(s: *i64) -> i64 { return (g_rng(s) >> 20) & 63 }
26// fingerprint = center XOR a mask of up to k random bits (<=k, positions may collide)
27func g_jitter(s: *i64, center: i64, k: i64) -> i64 { var v: i64=center; var i: i64=0; while i<k { v = v ^ (1 << g_bitpos(s)); i=i+1 } return v }
28
29// brute-force linear reference: payloads of all fps within Hamming r of q.
30func g_brute(fp: *i64, pay: *i64, n: i64, q: i64, r: i64, out: *i64, out_cap: i64) -> i64 {
31 var nout: i64=0; var i: i64=0
32 while i<n { if nx_simhash_hamming(q, fp[i]) <= r { if nout<out_cap { out[nout]=pay[i]; nout=nout+1 } } i=i+1 }
33 return nout
34}
35func g_memzero(memb: *u8, n: i64) -> i64 { var i: i64=0; while i<n { memb[i]=0 as u8; i=i+1 } return 0 }
36func g_memmark(memb: *u8, out: *i64, cnt: i64) -> i64 { var i: i64=0; while i<cnt { memb[out[i]]=1 as u8; i=i+1 } return 0 }
37func g_memeq(a: *u8, b: *u8, n: i64) -> i64 { var i: i64=0; while i<n { if a[i]!=b[i] { return 0 } i=i+1 } return 1 }
38
39func main() -> i64 {
40 g_puts("=== PHASH INDEX GATE (BK-tree sublinear Hamming index: exact == linear, sublinear, deterministic) ===\n" as *u8)
41 let C: i64 = 256 // cluster centers (power of two)
42 let M: i64 = 16 // members per cluster
43 let N: i64 = C * M // 4096 fingerprints
44 let R: i64 = 8 // near-duplicate Hamming radius
45
46 let seedbox: *i64 = sys_mmap(8) as *i64
47 seedbox[0] = 0x123456789ABCDEF // fixed seed -> reproducible corpus
48
49 // cluster centers
50 let centers: *i64 = sys_mmap(8*C) as *i64
51 var c: i64 = 0
52 while c < C { centers[c] = g_rng(seedbox); c = c + 1 }
53
54 // corpus: member (c,m) = center[c] jittered by <=4 bits; payload = running global index
55 let fp: *i64 = sys_mmap(8*N) as *i64
56 let pay: *i64 = sys_mmap(8*N) as *i64
57 var idx: i64 = 0
58 c = 0
59 while c < C {
60 var m: i64 = 0
61 while m < M { fp[idx] = g_jitter(seedbox, centers[c], 4); pay[idx] = idx; idx = idx + 1; m = m + 1 }
62 c = c + 1
63 }
64
65 // build the BK-tree (tree arrays separate from corpus arrays so brute-force has an untouched copy)
66 let ch: *i64 = sys_mmap(8*N*65) as *i64
67 pi_init_children(ch, N)
68 let tfp: *i64 = sys_mmap(8*N) as *i64
69 let tpay: *i64 = sys_mmap(8*N) as *i64
70 var nodes: i64 = 0
71 var i: i64 = 0
72 while i < N { nodes = pi_insert(tfp, tpay, ch, nodes, fp[i], pay[i]); i = i + 1 }
73
74 let outbk: *i64 = sys_mmap(8*N) as *i64
75 let outbr: *i64 = sys_mmap(8*N) as *i64
76 let mema: *u8 = sys_mmap(N)
77 let memb: *u8 = sys_mmap(N)
78 let visbox: *i64 = sys_mmap(8) as *i64
79
80 var pass: i64 = 0
81 let rows: i64 = 5
82
83 // ---- row1: clustered exactness + accumulate the exceed metric ----
84 let K: i64 = 32
85 var exact1: i64 = 1
86 var sum_vis: i64 = 0
87 var q: i64 = 0
88 while q < K {
89 let cc: i64 = (g_rng(seedbox) >> 24) & (C - 1)
90 let query: i64 = g_jitter(seedbox, centers[cc], 2)
91 let nbk: i64 = pi_query(tfp, tpay, ch, nodes, query, R, outbk, N, visbox)
92 let nbr: i64 = g_brute(fp, pay, N, query, R, outbr, N)
93 g_memzero(mema, N); g_memzero(memb, N)
94 g_memmark(mema, outbk, nbk); g_memmark(memb, outbr, nbr)
95 if nbk != nbr { exact1 = 0 }
96 if g_memeq(mema, memb, N) == 0 { exact1 = 0 }
97 sum_vis = sum_vis + visbox[0]
98 q = q + 1
99 }
100 var avg_vis: i64 = 0
101 if K > 0 { avg_vis = sum_vis / K }
102 g_puts(" row1 clustered exactness (BK set == linear set, K=32) -> " as *u8)
103 if exact1==1 { pass=pass+1; g_puts("PASS\n" as *u8) } else { g_puts("FAIL\n" as *u8) }
104
105 // ---- row2: measured-exceed (avg candidates << N) ----
106 g_puts(" row2 sublinear: avg candidates=" as *u8); g_num(avg_vis); g_puts(" vs linear N=" as *u8); g_num(N)
107 g_puts(" (~" as *u8)
108 if avg_vis>0 { g_num(N / avg_vis) } else { g_num(0) }
109 g_puts("x fewer comparisons) -> " as *u8)
110 if avg_vis < N { pass=pass+1; g_puts("PASS\n" as *u8) } else { g_puts("FAIL\n" as *u8) }
111
112 // ---- row3: adversarial uniform-random exactness (correctness regardless of pruning) ----
113 let K2: i64 = 8
114 let R2: i64 = 12
115 var exact3: i64 = 1
116 q = 0
117 while q < K2 {
118 let query: i64 = g_rng(seedbox)
119 let nbk: i64 = pi_query(tfp, tpay, ch, nodes, query, R2, outbk, N, visbox)
120 let nbr: i64 = g_brute(fp, pay, N, query, R2, outbr, N)
121 g_memzero(mema, N); g_memzero(memb, N)
122 g_memmark(mema, outbk, nbk); g_memmark(memb, outbr, nbr)
123 if nbk != nbr { exact3 = 0 }
124 if g_memeq(mema, memb, N) == 0 { exact3 = 0 }
125 q = q + 1
126 }
127 g_puts(" row3 adversarial exactness (uniform-random, K=8, r=12) -> " as *u8)
128 if exact3==1 { pass=pass+1; g_puts("PASS (exact even where pruning is weak)\n" as *u8) } else { g_puts("FAIL\n" as *u8) }
129
130 // ---- row4: determinism (same query twice -> identical visited + count) ----
131 let dq: i64 = g_jitter(seedbox, centers[7], 3)
132 let n_a: i64 = pi_query(tfp, tpay, ch, nodes, dq, R, outbk, N, visbox)
133 let vis_a: i64 = visbox[0]
134 let n_b: i64 = pi_query(tfp, tpay, ch, nodes, dq, R, outbr, N, visbox)
135 let vis_b: i64 = visbox[0]
136 g_puts(" row4 determinism -> visited " as *u8); g_num(vis_a); g_puts("==" as *u8); g_num(vis_b)
137 g_puts(", count " as *u8); g_num(n_a); g_puts("==" as *u8); g_num(n_b); g_puts(" -> " as *u8)
138 if vis_a==vis_b { if n_a==n_b { pass=pass+1; g_puts("PASS\n" as *u8) } else { g_puts("FAIL\n" as *u8) } } else { g_puts("FAIL\n" as *u8) }
139
140 // ---- row5: build integrity (all N inserted) ----
141 g_puts(" row5 build integrity -> nodes=" as *u8); g_num(nodes); g_puts(" of " as *u8); g_num(N); g_puts(" -> " as *u8)
142 if nodes==N { pass=pass+1; g_puts("PASS\n" as *u8) } else { g_puts("FAIL\n" as *u8) }
143
144 g_puts("----\nPHASH-INDEX-GATE rows=" as *u8); g_num(rows); g_puts(" pass=" as *u8); g_num(pass); g_puts("\n" as *u8)
145 let lg: i64=sys_openat_append("knowledge/status/phash_index_gate.log" as *u8, 0x1a4)
146 if lg>=0 {
147 g_w(lg, "PHASH-INDEX-GATE rows=" as *u8); g_wn(lg, rows); g_w(lg, " pass=" as *u8); g_wn(lg, pass)
148 g_w(lg, " avg_candidates=" as *u8); g_wn(lg, avg_vis); g_w(lg, " N=" as *u8); g_wn(lg, N)
149 if pass==rows { g_w(lg, " verdict=GREEN\n" as *u8) } else { g_w(lg, " verdict=RED\n" as *u8) }
150 sys_close(lg)
151 }
152 if pass==rows { g_puts("PHASH-INDEX-GATE GREEN\n" as *u8); sys_exit(0); return 0 }
153 g_puts("PHASH-INDEX-GATE RED\n" as *u8); sys_exit(1); return 1
154}