sketch_cuckoo_test.nx source
↩ module page · 136 lines · 4689 B
1// sketch_cuckoo_test.nx -- Cuckoo Filter end-to-end verification.
2//
3// Exit code mapping (matches smoke gate):
4// 0 all pass
5// 5 alloc returned NULL or rejected power-of-2
6// 10/11 empty filter false positives
7// 20 insert returned 0 (failed) under-capacity
8// 21/22 contains returns wrong value after insert
9// 30 delete returned 0 (failed) for present item
10// 31 contains still returns 1 after delete
11// 32 total counter wrong after delete
12// 40 rejected non-power-of-2
13// 50 multiple inserts collide / total wrong
14// 60 envelope_kind wrong
15// 61 conf_ppb wrong (should be 1e9 - 31e6)
16// 62 maturity wrong
17// 63 adv_safety wrong
18// 70 deterministic reproducibility broken
19
20import "syscalls.nx"
21import "sketch_cuckoo.nx"
22import "sketch_types.nx"
23
24func main() -> i64 {
25 // ---- construction ----
26 let c: *CuckooFilter = nx_cuckoo_alloc(256, 1)
27 if c == (0 as *CuckooFilter) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
28
29 // Reject non-power-of-2.
30 let bad: *CuckooFilter = nx_cuckoo_alloc(100, 1)
31 if bad != (0 as *CuckooFilter) { return __syscall(93, 40, 0, 0, 0, 0, 0) }
32
33 // ---- empty filter never reports present ----
34 if nx_cuckoo_contains(c, 12345) != 0 {
35 return __syscall(93, 10, 0, 0, 0, 0, 0)
36 }
37 if nx_cuckoo_contains(c, 67890) != 0 {
38 return __syscall(93, 11, 0, 0, 0, 0, 0)
39 }
40
41 // ---- single insert / contains / delete cycle ----
42 let h1: i64 = 0x123456789ABCDEF0
43 if nx_cuckoo_insert(c, h1) != 1 {
44 return __syscall(93, 20, 0, 0, 0, 0, 0)
45 }
46 if nx_cuckoo_contains(c, h1) != 1 {
47 return __syscall(93, 21, 0, 0, 0, 0, 0)
48 }
49 // A different hash should NOT match unless coincidentally same fp + bucket.
50 if nx_cuckoo_contains(c, 0xDEADBEEFCAFEBABE) != 0 {
51 // Probabilistic: ~3.1% chance of false positive for any single
52 // unrelated hash. Use carefully-chosen hash that we know
53 // collides nowhere -- the test value 0xDEADBEEF... has
54 // fp = 0xBE = 190, bucket1 = (0xDEADBEEFCAFEBABE >> 8) & 0xFF
55 // = different from h1's bucket. This may rarely flake; if so,
56 // we'd see exit 22 -- a single retry will pass.
57 return __syscall(93, 22, 0, 0, 0, 0, 0)
58 }
59
60 // ---- delete ----
61 if nx_cuckoo_delete(c, h1) != 1 {
62 return __syscall(93, 30, 0, 0, 0, 0, 0)
63 }
64 if nx_cuckoo_contains(c, h1) != 0 {
65 return __syscall(93, 31, 0, 0, 0, 0, 0)
66 }
67 if c.total != 0 {
68 return __syscall(93, 32, 0, 0, 0, 0, 0)
69 }
70
71 // ---- bulk insert: 200 items into a 256-bucket * 4-slot filter
72 // (1024 slot capacity, ~19% load). All should fit. ----
73 var i: i64 = 0
74 while i < 200 {
75 // Mix index to get spread fingerprints + buckets.
76 let h: i64 = i * 0x9E3779B97F4A7C15 + 0xCAFEBABE
77 if nx_cuckoo_insert(c, h) != 1 {
78 return __syscall(93, 50, 0, 0, 0, 0, 0)
79 }
80 i = i + 1
81 }
82 if c.total != 200 {
83 return __syscall(93, 50, 0, 0, 0, 0, 0)
84 }
85
86 // ---- all inserted items must be contained (no false negatives
87 // ever for items truly inserted) ----
88 i = 0
89 while i < 200 {
90 let h: i64 = i * 0x9E3779B97F4A7C15 + 0xCAFEBABE
91 if nx_cuckoo_contains(c, h) != 1 {
92 return __syscall(93, 51, 0, 0, 0, 0, 0)
93 }
94 i = i + 1
95 }
96
97 // ---- typed envelope ----
98 let q: *ApproxI64 = nx_cuckoo_query(c, h1) // not present (deleted)
99 if q.envelope_kind != NX_ENV_ABS {
100 return __syscall(93, 60, 0, 0, 0, 0, 0)
101 }
102 // conf_ppb = 1e9 - 31e6 = 969_000_000.
103 if q.conf_ppb != 969000000 {
104 return __syscall(93, 61, 0, 0, 0, 0, 0)
105 }
106 if q.maturity != NX_MATURITY_REFERENCE_IMPL {
107 return __syscall(93, 62, 0, 0, 0, 0, 0)
108 }
109 if q.adv_safety != NX_ADV_HONEST {
110 return __syscall(93, 63, 0, 0, 0, 0, 0)
111 }
112
113 // ---- deterministic reproducibility ----
114 let c2a: *CuckooFilter = nx_cuckoo_alloc(64, 42)
115 let c2b: *CuckooFilter = nx_cuckoo_alloc(64, 42)
116 i = 0
117 while i < 50 {
118 let h: i64 = i * 31337 + 0xBEEF
119 nx_cuckoo_insert(c2a, h)
120 nx_cuckoo_insert(c2b, h)
121 i = i + 1
122 }
123 // Byte-for-byte: same bucket contents.
124 let buf_a: *u8 = c2a.buckets
125 let buf_b: *u8 = c2b.buckets
126 let bytes: i64 = c2a.n_buckets * 4
127 i = 0
128 while i < bytes {
129 if buf_a[i] != buf_b[i] {
130 return __syscall(93, 70, 0, 0, 0, 0, 0)
131 }
132 i = i + 1
133 }
134
135 return 0
136}