sketch_kmv_test.nx source
↩ module page · 196 lines · 6486 B
1// sketch_kmv_test.nx -- KMV cardinality + union + Jaccard verification.
2
3import "syscalls.nx"
4import "sketch_kmv.nx"
5import "sketch_types.nx"
6
7func iabs(x: i64) -> i64 {
8 if x < 0 { return -x }
9 return x
10}
11
12func main() -> i64 {
13 // ---- alloc + empty ----
14 let kmv: *Kmv = nx_kmv_alloc(256, 42)
15 if kmv == (0 as *Kmv) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
16 if nx_kmv_estimate(kmv) != 0 {
17 return __syscall(93, 10, 0, 0, 0, 0, 0)
18 }
19 // Reject below min.
20 let bad: *Kmv = nx_kmv_alloc(8, 1)
21 if bad != (0 as *Kmv) { return __syscall(93, 11, 0, 0, 0, 0, 0) }
22
23 // ---- under-cap exact-counting ----
24 nx_kmv_add_hash(kmv, 100)
25 nx_kmv_add_hash(kmv, 200)
26 nx_kmv_add_hash(kmv, 300)
27 if kmv.n_items != 3 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
28 if nx_kmv_estimate(kmv) != 3 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
29 // Re-insert: idempotent (KMV is a SET).
30 nx_kmv_add_hash(kmv, 200)
31 if kmv.n_items != 3 { return __syscall(93, 22, 0, 0, 0, 0, 0) }
32 // values sorted ascending.
33 if kmv.values[0] != 100 { return __syscall(93, 23, 0, 0, 0, 0, 0) }
34 if kmv.values[1] != 200 { return __syscall(93, 24, 0, 0, 0, 0, 0) }
35 if kmv.values[2] != 300 { return __syscall(93, 25, 0, 0, 0, 0, 0) }
36
37 // ---- cardinality with full sketch ----
38 // Fill kmv2 with hashes spread across [0, 2^32). We'll add
39 // 5000 deterministic hashes by murmur3-of-counter. With K=256,
40 // est should be near 5000 within 26% (1/sqrt(255)).
41 let kmv2: *Kmv = nx_kmv_alloc(256, 42)
42 let buf: *u8 = sys_mmap(8)
43 var i: i64 = 0
44 while i < 5000 {
45 // Murmur3 of the counter (8-byte LE).
46 buf[0] = (i ) & 0xFF
47 buf[1] = (i >> 8 ) & 0xFF
48 buf[2] = (i >> 16) & 0xFF
49 buf[3] = (i >> 24) & 0xFF
50 buf[4] = (i >> 32) & 0xFF
51 buf[5] = (i >> 40) & 0xFF
52 buf[6] = (i >> 48) & 0xFF
53 buf[7] = (i >> 56) & 0xFF
54 nx_kmv_add(kmv2, buf, 8)
55 i = i + 1
56 }
57 if kmv2.n_items != 256 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
58 let est: i64 = nx_kmv_estimate(kmv2)
59 // Within 35% margin for K=256 (looser than 1-sigma).
60 let target: i64 = 5000
61 let margin: i64 = (target * 35) / 100 // 1750
62 if iabs(est - target) > margin {
63 return __syscall(93, 31, 0, 0, 0, 0, 0)
64 }
65 // Sorted invariant.
66 i = 1
67 while i < kmv2.n_items {
68 if kmv2.values[i] < kmv2.values[i - 1] {
69 return __syscall(93, 32, 0, 0, 0, 0, 0)
70 }
71 i = i + 1
72 }
73
74 // ---- typed envelope ----
75 let q: *ApproxI64 = nx_kmv_query(kmv2)
76 if q.envelope_kind != NX_ENV_REL_STDDEV {
77 return __syscall(93, 40, 0, 0, 0, 0, 0)
78 }
79 if q.param_a != 62700000 { // 1/sqrt(255) for k=256
80 return __syscall(93, 41, 0, 0, 0, 0, 0)
81 }
82 if q.conf_ppb != 682700000 {
83 return __syscall(93, 42, 0, 0, 0, 0, 0)
84 }
85 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
86 return __syscall(93, 43, 0, 0, 0, 0, 0)
87 }
88 if q.adv_safety != NX_ADV_HONEST {
89 return __syscall(93, 44, 0, 0, 0, 0, 0)
90 }
91
92 // ---- union: two identical sketches union to themselves ----
93 let kmv3a: *Kmv = nx_kmv_alloc(128, 7)
94 let kmv3b: *Kmv = nx_kmv_alloc(128, 7)
95 i = 0
96 while i < 1000 {
97 buf[0] = (i ) & 0xFF
98 buf[1] = (i >> 8 ) & 0xFF
99 buf[2] = (i >> 16) & 0xFF
100 buf[3] = (i >> 24) & 0xFF
101 buf[4] = 0
102 buf[5] = 0
103 buf[6] = 0
104 buf[7] = 0
105 nx_kmv_add(kmv3a, buf, 8)
106 nx_kmv_add(kmv3b, buf, 8)
107 i = i + 1
108 }
109 let unioned: *Kmv = nx_kmv_union(kmv3a, kmv3b)
110 if unioned == (0 as *Kmv) {
111 return __syscall(93, 50, 0, 0, 0, 0, 0)
112 }
113 // Identical inputs: union should match either sketch byte-for-byte.
114 if unioned.n_items != kmv3a.n_items {
115 return __syscall(93, 51, 0, 0, 0, 0, 0)
116 }
117 i = 0
118 while i < unioned.n_items {
119 if unioned.values[i] != kmv3a.values[i] {
120 return __syscall(93, 52, 0, 0, 0, 0, 0)
121 }
122 i = i + 1
123 }
124
125 // ---- Jaccard: identical sketches -> 1.0 (ppm = 1_000_000) ----
126 let j_identical: i64 = nx_kmv_jaccard_ppm(kmv3a, kmv3b)
127 if j_identical != 1000000 {
128 return __syscall(93, 60, 0, 0, 0, 0, 0)
129 }
130
131 // ---- Jaccard: disjoint sketches -> 0 ----
132 let kmv4a: *Kmv = nx_kmv_alloc(64, 99)
133 let kmv4b: *Kmv = nx_kmv_alloc(64, 99)
134 i = 0
135 while i < 100 {
136 buf[0] = i & 0xFF
137 buf[1] = 0xAA // different prefix space
138 buf[2] = 0
139 buf[3] = 0
140 buf[4] = 0
141 buf[5] = 0
142 buf[6] = 0
143 buf[7] = 0
144 nx_kmv_add(kmv4a, buf, 8)
145 buf[1] = 0xBB // different prefix -> completely different hashes
146 nx_kmv_add(kmv4b, buf, 8)
147 i = i + 1
148 }
149 let j_disjoint: i64 = nx_kmv_jaccard_ppm(kmv4a, kmv4b)
150 // Disjoint hash spaces. Some collision possible but should be near 0.
151 if j_disjoint > 50000 { // < 5%
152 return __syscall(93, 61, 0, 0, 0, 0, 0)
153 }
154
155 // ---- Jaccard: 50% overlap ----
156 // Fill 5a with 0..200, 5b with 100..300. True Jaccard:
157 // |intersect| = 100 (values 100..199)
158 // |union| = 300 (values 0..299)
159 // J = 100/300 = 0.333 = 333333 ppm
160 let kmv5a: *Kmv = nx_kmv_alloc(256, 11)
161 let kmv5b: *Kmv = nx_kmv_alloc(256, 11)
162 i = 0
163 while i < 200 {
164 buf[0] = (i ) & 0xFF
165 buf[1] = (i >> 8 ) & 0xFF
166 buf[2] = 0xC0 // shared prefix for shared hash space
167 buf[3] = 0
168 buf[4] = 0
169 buf[5] = 0
170 buf[6] = 0
171 buf[7] = 0
172 nx_kmv_add(kmv5a, buf, 8)
173 i = i + 1
174 }
175 i = 100
176 while i < 300 {
177 buf[0] = (i ) & 0xFF
178 buf[1] = (i >> 8 ) & 0xFF
179 buf[2] = 0xC0
180 buf[3] = 0
181 buf[4] = 0
182 buf[5] = 0
183 buf[6] = 0
184 buf[7] = 0
185 nx_kmv_add(kmv5b, buf, 8)
186 i = i + 1
187 }
188 let j_overlap: i64 = nx_kmv_jaccard_ppm(kmv5a, kmv5b)
189 // True J = 100/300 = 0.333; tolerate ±10% (k=256, 1/sqrt(255) = 6.3%
190 // applies to cardinalities so Jaccard tolerance scales).
191 if iabs(j_overlap - 333333) > 100000 {
192 return __syscall(93, 62, 0, 0, 0, 0, 0)
193 }
194
195 return 0
196}