sketch_hll4_test.nx source
↩ module page · 111 lines · 3980 B
1// sketch_hll4_test.nx -- HLL_4 + Heule exception table verification.
2//
3// Tests:
4// 1. Memory: HLL_4-10 register array < HLL_8-10 by ~50%
5// 2. Cardinality estimate within +-15% of N=5000 (no exceptions
6// fire at this cardinality since max rho ~= log2(5000/1024) = 2.3)
7// 3. Exception path: directly write rho=20 to a slot; verify read-back
8// returns 20, slot's packed nibble holds sentinel 15, exception
9// count incremented
10// 4. Multiple exceptions: add three different (idx, value) entries,
11// verify each reads back correctly without interference
12// 5. Exception update: overwrite existing exception slot, count
13// should NOT increment
14// 6. Typed envelope: NX_ENV_REL_STDDEV / ReferenceImpl / Honest
15
16import "syscalls.nx"
17import "sketch_hll4.nx"
18import "sketch_types.nx"
19
20func write_i64_le(buf: *u8, value: i64) -> i64 {
21 var i: i64 = 0
22 var v: i64 = value
23 while i < 8 { buf[i] = v & 0xFF; v = v >> 8; i = i + 1 }
24 return 0
25}
26
27func main() -> i64 {
28 let h: *Hll4 = nx_hll4_alloc(10, 0)
29 if h == (0 as *Hll4) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
30
31 // ---- Memory ----
32 // HLL_4-10: m=1024, register array = 512 bytes (4 bits × 1024).
33 if h.bytes != 512 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
34 // < 60% of HLL_8-10 (1024) -- 50% reduction with slack.
35 if h.bytes >= (1024 * 60) / 100 {
36 return __syscall(93, 7, 0, 0, 0, 0, 0)
37 }
38
39 // ---- Accuracy ----
40 let N: i64 = 5000
41 let key: *u8 = sys_mmap(8)
42 var i: i64 = 0
43 while i < N {
44 write_i64_le(key, i)
45 nx_hll4_add(h, key, 8)
46 i = i + 1
47 }
48 let est: i64 = nx_hll4_estimate(h)
49 let lo: i64 = (N * 85) / 100
50 let hi: i64 = (N * 115) / 100
51 if est < lo { return __syscall(93, 10, 0, 0, 0, 0, 0) }
52 if est > hi { return __syscall(93, 11, 0, 0, 0, 0, 0) }
53
54 // ---- Exception path ----
55 let h2: *Hll4 = nx_hll4_alloc(10, 0)
56 if nx_hll4_exception_count(h2) != 0 {
57 return __syscall(93, 20, 0, 0, 0, 0, 0)
58 }
59 // Write rho=20 to slot 7 (must use sentinel + exception).
60 nx_hll4_write(h2, 7, 20)
61 if nx_hll4_read(h2, 7) != 20 {
62 return __syscall(93, 21, 0, 0, 0, 0, 0)
63 }
64 if nx_hll4_get_packed(h2.regs, 7) != NX_HLL4_SENTINEL {
65 return __syscall(93, 22, 0, 0, 0, 0, 0)
66 }
67 if nx_hll4_exception_count(h2) != 1 {
68 return __syscall(93, 23, 0, 0, 0, 0, 0)
69 }
70
71 // Multiple exceptions.
72 nx_hll4_write(h2, 42, 17)
73 nx_hll4_write(h2, 123, 25)
74 if nx_hll4_read(h2, 7) != 20 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
75 if nx_hll4_read(h2, 42) != 17 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
76 if nx_hll4_read(h2, 123) != 25 { return __syscall(93, 32, 0, 0, 0, 0, 0) }
77 if nx_hll4_exception_count(h2) != 3 {
78 return __syscall(93, 33, 0, 0, 0, 0, 0)
79 }
80
81 // Update existing exception -- count must NOT increment.
82 nx_hll4_write(h2, 42, 30)
83 if nx_hll4_read(h2, 42) != 30 { return __syscall(93, 40, 0, 0, 0, 0, 0) }
84 if nx_hll4_exception_count(h2) != 3 {
85 return __syscall(93, 41, 0, 0, 0, 0, 0)
86 }
87
88 // Normal-range write (value < 15) goes to slot, not exceptions.
89 nx_hll4_write(h2, 500, 10)
90 if nx_hll4_read(h2, 500) != 10 { return __syscall(93, 50, 0, 0, 0, 0, 0) }
91 if nx_hll4_get_packed(h2.regs, 500) != 10 {
92 return __syscall(93, 51, 0, 0, 0, 0, 0)
93 }
94 if nx_hll4_exception_count(h2) != 3 {
95 return __syscall(93, 52, 0, 0, 0, 0, 0)
96 }
97
98 // ---- Typed envelope ----
99 let q: *ApproxI64 = nx_hll4_query(h)
100 if q.envelope_kind != NX_ENV_REL_STDDEV {
101 return __syscall(93, 60, 0, 0, 0, 0, 0)
102 }
103 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
104 return __syscall(93, 61, 0, 0, 0, 0, 0)
105 }
106 if q.adv_safety != NX_ADV_HONEST {
107 return __syscall(93, 62, 0, 0, 0, 0, 0)
108 }
109
110 return 0
111}