sketch_cpc_test.nx source
↩ module page · 140 lines · 4152 B
1// sketch_cpc_test.nx -- CPC (sparse + HIP estimator) verification.
2
3import "syscalls.nx"
4import "sketch_cpc.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 ----
14 let c: *Cpc = nx_cpc_alloc(7, 4096, 42) // m=128, big_M=4096
15 if c == (0 as *Cpc) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
16 // Reject lg_k out of range.
17 if nx_cpc_alloc(3, 1024, 1) != (0 as *Cpc) {
18 return __syscall(93, 6, 0, 0, 0, 0, 0)
19 }
20 if nx_cpc_alloc(15, 1024, 1) != (0 as *Cpc) {
21 return __syscall(93, 7, 0, 0, 0, 0, 0)
22 }
23 if nx_cpc_n_coupons(c) != 0 {
24 return __syscall(93, 8, 0, 0, 0, 0, 0)
25 }
26 // big_M = m * window = 128 * 32 = 4096.
27 if nx_cpc_big_m(c) != 4096 {
28 return __syscall(93, 9, 0, 0, 0, 0, 0)
29 }
30
31 // ---- empty: estimate = 0 ----
32 if nx_cpc_estimate(c) != 0 {
33 return __syscall(93, 10, 0, 0, 0, 0, 0)
34 }
35
36 // ---- single insertion: estimate ~ 1 ----
37 nx_cpc_add(c, "alice", 5)
38 let e1: i64 = nx_cpc_estimate(c)
39 // HIP at n=0: kappa += big_M / big_M = 1.0 -> estimate = 1.
40 if iabs(e1 - 1) > 0 {
41 return __syscall(93, 20, 0, 0, 0, 0, 0)
42 }
43
44 // ---- 100 distinct insertions: estimate ~ 100 ----
45 let c2: *Cpc = nx_cpc_alloc(7, 4096, 7)
46 let buf: *u8 = sys_mmap(8)
47 var i: i64 = 0
48 while i < 100 {
49 buf[0] = (i ) & 0xFF
50 buf[1] = (i >> 8 ) & 0xFF
51 buf[2] = 0x30
52 buf[3] = 0
53 buf[4] = 0
54 buf[5] = 0
55 buf[6] = 0
56 buf[7] = 0
57 nx_cpc_add(c2, buf, 8)
58 i = i + 1
59 }
60 let e100: i64 = nx_cpc_estimate(c2)
61 // True = 100. CPC rel-stddev ~ 1/sqrt(4096) = 1.56%. Allow +/-10 (10%).
62 if iabs(e100 - 100) > 10 {
63 return __syscall(93, 30, 0, 0, 0, 0, 0)
64 }
65
66 // ---- 1000 distinct insertions: estimate ~ 1000 ----
67 let c3: *Cpc = nx_cpc_alloc(7, 8192, 11)
68 i = 0
69 while i < 1000 {
70 buf[0] = (i ) & 0xFF
71 buf[1] = (i >> 8 ) & 0xFF
72 buf[2] = 0x40
73 buf[3] = 0
74 buf[4] = 0
75 buf[5] = 0
76 buf[6] = 0
77 buf[7] = 0
78 nx_cpc_add(c3, buf, 8)
79 i = i + 1
80 }
81 let e1000: i64 = nx_cpc_estimate(c3)
82 // 1.56% of 1000 = ~16. Allow +/-150 (15%).
83 if iabs(e1000 - 1000) > 150 {
84 return __syscall(93, 40, 0, 0, 0, 0, 0)
85 }
86
87 // ---- idempotent inserts: same key twice -> no double count ----
88 let c4: *Cpc = nx_cpc_alloc(7, 1024, 1)
89 nx_cpc_add(c4, "x", 1)
90 nx_cpc_add(c4, "x", 1)
91 nx_cpc_add(c4, "x", 1)
92 if nx_cpc_n_coupons(c4) != 1 {
93 return __syscall(93, 50, 0, 0, 0, 0, 0)
94 }
95 if nx_cpc_estimate(c4) != 1 {
96 return __syscall(93, 51, 0, 0, 0, 0, 0)
97 }
98
99 // ---- typed envelope ----
100 let q: *ApproxI64 = nx_cpc_query(c3)
101 if q.envelope_kind != NX_ENV_REL_STDDEV {
102 return __syscall(93, 60, 0, 0, 0, 0, 0)
103 }
104 // big_M = 4096 -> sqrt = 64 -> stddev_ppb = 1e9 / 64 = 15_625_000.
105 if iabs(q.param_a - 15625000) > 100000 {
106 return __syscall(93, 61, 0, 0, 0, 0, 0)
107 }
108 if q.conf_ppb != 682700000 {
109 return __syscall(93, 62, 0, 0, 0, 0, 0)
110 }
111 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
112 return __syscall(93, 63, 0, 0, 0, 0, 0)
113 }
114
115 // ---- determinism: same seed + sequence -> same estimate ----
116 let c5a: *Cpc = nx_cpc_alloc(7, 2048, 99)
117 let c5b: *Cpc = nx_cpc_alloc(7, 2048, 99)
118 i = 0
119 while i < 500 {
120 buf[0] = (i ) & 0xFF
121 buf[1] = (i >> 8 ) & 0xFF
122 buf[2] = 0x50
123 buf[3] = 0
124 buf[4] = 0
125 buf[5] = 0
126 buf[6] = 0
127 buf[7] = 0
128 nx_cpc_add(c5a, buf, 8)
129 nx_cpc_add(c5b, buf, 8)
130 i = i + 1
131 }
132 if nx_cpc_estimate(c5a) != nx_cpc_estimate(c5b) {
133 return __syscall(93, 70, 0, 0, 0, 0, 0)
134 }
135 if nx_cpc_n_coupons(c5a) != nx_cpc_n_coupons(c5b) {
136 return __syscall(93, 71, 0, 0, 0, 0, 0)
137 }
138
139 return 0
140}