nx_phash_index_gate.nx source
↩ module page · 166 lines · 9660 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"
16import "nx_gate_verdict.nx"
17
18func 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 }
19func 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 }
20func 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 }
21func g_wn(fd: i64, v: i64) -> i64 { let bb: *u8=sys_mmap(28); var m: i64=v; if m<0{m=0-m;sys_write(fd,"-" 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(fd,bb,k); return 0 }
22
23// MMIX LCG (Knuth): deterministic 64-bit stream from a fixed seed. s[0] holds the state.
24func g_rng(s: *i64) -> i64 { let x: i64 = s[0] * 0x5851F42D4C957F2D + 0x14057B7EF767814F; s[0]=x; return x }
25// a bit position 0..63 from the mid bits of a fresh LCG word
26func g_bitpos(s: *i64) -> i64 { return (g_rng(s) >> 20) & 63 }
27// fingerprint = center XOR a mask of up to k random bits (<=k, positions may collide)
28func 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 }
29
30// brute-force linear reference: payloads of all fps within Hamming r of q.
31func g_brute(fp: *i64, pay: *i64, n: i64, q: i64, r: i64, out: *i64, out_cap: i64) -> i64 {
32 var nout: i64=0; var i: i64=0
33 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 }
34 return nout
35}
36func g_memzero(memb: *u8, n: i64) -> i64 { var i: i64=0; while i<n { memb[i]=0 as u8; i=i+1 } return 0 }
37func 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 }
38func 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 }
39
40func main() -> i64 {
41 g_puts("=== PHASH INDEX GATE (BK-tree sublinear Hamming index: exact == linear, sublinear, deterministic) ===\n" as *u8)
42 let C: i64 = 256 // cluster centers (power of two)
43 let M: i64 = 16 // members per cluster
44 let N: i64 = C * M // 4096 fingerprints
45 let R: i64 = 8 // near-duplicate Hamming radius
46
47 let seedbox: *i64 = sys_mmap(8) as *i64
48 seedbox[0] = 0x123456789ABCDEF // fixed seed -> reproducible corpus
49
50 // cluster centers
51 let centers: *i64 = sys_mmap(8*C) as *i64
52 var c: i64 = 0
53 while c < C { centers[c] = g_rng(seedbox); c = c + 1 }
54
55 // corpus: member (c,m) = center[c] jittered by <=4 bits; payload = running global index
56 let fp: *i64 = sys_mmap(8*N) as *i64
57 let pay: *i64 = sys_mmap(8*N) as *i64
58 var idx: i64 = 0
59 c = 0
60 while c < C {
61 var m: i64 = 0
62 while m < M { fp[idx] = g_jitter(seedbox, centers[c], 4); pay[idx] = idx; idx = idx + 1; m = m + 1 }
63 c = c + 1
64 }
65
66 // build the BK-tree (tree arrays separate from corpus arrays so brute-force has an untouched copy)
67 let ch: *i64 = sys_mmap(8*N*65) as *i64
68 pi_init_children(ch, N)
69 let tfp: *i64 = sys_mmap(8*N) as *i64
70 let tpay: *i64 = sys_mmap(8*N) as *i64
71 var nodes: i64 = 0
72 var i: i64 = 0
73 while i < N { nodes = pi_insert(tfp, tpay, ch, nodes, fp[i], pay[i]); i = i + 1 }
74
75 let outbk: *i64 = sys_mmap(8*N) as *i64
76 let outbr: *i64 = sys_mmap(8*N) as *i64
77 let mema: *u8 = sys_mmap(N)
78 let memb: *u8 = sys_mmap(N)
79 let visbox: *i64 = sys_mmap(8) as *i64
80
81 // D001 MIGRATION 2026-09-01 (/compare/mediaingest): the hand-rolled pass/rows pair became a
82 // gv_ctr, so DECLARED == EXECUTED by construction and the exit code carries the verdict where
83 // nx_gate_green can read it. This gate had no elf purely because /api/promote refuses a gate that
84 // rolls its own verdict -- the teeth below were always good, and were always unprovable from outside.
85 let gc: *i64 = gv_ctr()
86
87 // ---- row1: clustered exactness + accumulate the exceed metric ----
88 let K: i64 = 32
89 var exact1: i64 = 1
90 var sum_vis: i64 = 0
91 var q: i64 = 0
92 while q < K {
93 let cc: i64 = (g_rng(seedbox) >> 24) & (C - 1)
94 let query: i64 = g_jitter(seedbox, centers[cc], 2)
95 let nbk: i64 = pi_query(tfp, tpay, ch, nodes, query, R, outbk, N, visbox)
96 let nbr: i64 = g_brute(fp, pay, N, query, R, outbr, N)
97 g_memzero(mema, N); g_memzero(memb, N)
98 g_memmark(mema, outbk, nbk); g_memmark(memb, outbr, nbr)
99 if nbk != nbr { exact1 = 0 }
100 if g_memeq(mema, memb, N) == 0 { exact1 = 0 }
101 sum_vis = sum_vis + visbox[0]
102 q = q + 1
103 }
104 var avg_vis: i64 = 0
105 if K > 0 { avg_vis = sum_vis / K }
106 g_puts(" row1 clustered exactness (BK set == linear set, K=32) -> " as *u8)
107 gv_check("row1-clustered-exactness-BK-set-equals-brute-force-set" as *u8, exact1, gc)
108
109 // ---- row2: measured-exceed (avg candidates << N) ----
110 g_puts(" row2 sublinear: avg candidates=" as *u8); g_num(avg_vis); g_puts(" vs linear N=" as *u8); g_num(N)
111 g_puts(" (~" as *u8)
112 if avg_vis>0 { g_num(N / avg_vis) } else { g_num(0) }
113 g_puts("x fewer comparisons) -> " as *u8)
114 var r2ok: i64 = 0
115 if avg_vis < N { r2ok = 1 }
116 gv_check("row2-sublinear-avg-candidates-below-linear-N" as *u8, r2ok, gc)
117
118 // ---- row3: adversarial uniform-random exactness (correctness regardless of pruning) ----
119 let K2: i64 = 8
120 let R2: i64 = 12
121 var exact3: i64 = 1
122 q = 0
123 while q < K2 {
124 let query: i64 = g_rng(seedbox)
125 let nbk: i64 = pi_query(tfp, tpay, ch, nodes, query, R2, outbk, N, visbox)
126 let nbr: i64 = g_brute(fp, pay, N, query, R2, outbr, N)
127 g_memzero(mema, N); g_memzero(memb, N)
128 g_memmark(mema, outbk, nbk); g_memmark(memb, outbr, nbr)
129 if nbk != nbr { exact3 = 0 }
130 if g_memeq(mema, memb, N) == 0 { exact3 = 0 }
131 q = q + 1
132 }
133 g_puts(" row3 adversarial exactness (uniform-random, K=8, r=12) -> " as *u8)
134 gv_check("row3-adversarial-uniform-random-exactness-holds-where-pruning-is-weak" as *u8, exact3, gc)
135
136 // ---- row4: determinism (same query twice -> identical visited + count) ----
137 let dq: i64 = g_jitter(seedbox, centers[7], 3)
138 let n_a: i64 = pi_query(tfp, tpay, ch, nodes, dq, R, outbk, N, visbox)
139 let vis_a: i64 = visbox[0]
140 let n_b: i64 = pi_query(tfp, tpay, ch, nodes, dq, R, outbr, N, visbox)
141 let vis_b: i64 = visbox[0]
142 g_puts(" row4 determinism -> visited " as *u8); g_num(vis_a); g_puts("==" as *u8); g_num(vis_b)
143 g_puts(", count " as *u8); g_num(n_a); g_puts("==" as *u8); g_num(n_b); g_puts(" -> " as *u8)
144 var r4ok: i64 = 0
145 if vis_a==vis_b { if n_a==n_b { r4ok = 1 } }
146 gv_check("row4-determinism-same-query-twice-identical-visited-and-count" as *u8, r4ok, gc)
147
148 // ---- row5: build integrity (all N inserted) ----
149 g_puts(" row5 build integrity -> nodes=" as *u8); g_num(nodes); g_puts(" of " as *u8); g_num(N); g_puts(" -> " as *u8)
150 var r5ok: i64 = 0
151 if nodes==N { r5ok = 1 }
152 gv_check("row5-build-integrity-all-N-fingerprints-in-the-tree" as *u8, r5ok, gc)
153
154 // The durable log keeps its historical format, but its numbers now come from the SAME counter
155 // that decides the verdict (gc[0] passed, gc[1] total) rather than from a second hand-rolled tally --
156 // two counters of one population is how a log and a verdict drift apart without either being wrong.
157 let lg: i64=sys_openat_append("knowledge/status/phash_index_gate.log" as *u8, 0x1a4)
158 if lg>=0 {
159 g_w(lg, "PHASH-INDEX-GATE rows=" as *u8); g_wn(lg, gc[1]); g_w(lg, " pass=" as *u8); g_wn(lg, gc[0])
160 g_w(lg, " avg_candidates=" as *u8); g_wn(lg, avg_vis); g_w(lg, " N=" as *u8); g_wn(lg, N)
161 if gc[0]==gc[1] { g_w(lg, " verdict=GREEN\n" as *u8) } else { g_w(lg, " verdict=RED\n" as *u8) }
162 sys_close(lg)
163 }
164 return gv_verdict("nx_phash_index_gate" as *u8, gc,
165 "subject: nx_phash_index BK-tree against a brute-force linear oracle on a fixed-seed 4096-fingerprint corpus -- exactness on clustered AND adversarial uniform-random queries, sublinear pruning, bit-exact determinism, build integrity. D001-migrated 2026-09-01, teeth unchanged" as *u8)
166}