sketch_bloom_test.nx source
↩ module page · 109 lines · 3386 B
1// sketch_bloom_test.nx -- Bloom v2 verification.
2
3import "syscalls.nx"
4import "sketch_bloom.nx"
5import "sketch_types.nx"
6
7func main() -> i64 {
8 // ---- alloc ----
9 let bf: *BloomS = nx_bloom_alloc(8192, 5)
10 if bf == (0 as *BloomS) { return __syscall(93, 5, 0, 0, 0, 0, 0) }
11 if bf.n_inserted != 0 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
12 // Reject non-power-of-2.
13 let bad: *BloomS = nx_bloom_alloc(100, 4)
14 if bad != (0 as *BloomS) { return __syscall(93, 7, 0, 0, 0, 0, 0) }
15
16 // ---- empty -> contains 0 ----
17 if nx_bloom_contains(bf, "alice", 5) != 0 {
18 return __syscall(93, 10, 0, 0, 0, 0, 0)
19 }
20 // Empty FPR == 0.
21 if nx_bloom_fpr_ppb(bf) != 0 {
22 return __syscall(93, 11, 0, 0, 0, 0, 0)
23 }
24
25 // ---- insert + contains: no false negatives ----
26 nx_bloom_insert(bf, "alice", 5)
27 nx_bloom_insert(bf, "bob", 3)
28 nx_bloom_insert(bf, "carol", 5)
29 if nx_bloom_contains(bf, "alice", 5) != 1 {
30 return __syscall(93, 20, 0, 0, 0, 0, 0)
31 }
32 if nx_bloom_contains(bf, "bob", 3) != 1 {
33 return __syscall(93, 21, 0, 0, 0, 0, 0)
34 }
35 if nx_bloom_contains(bf, "carol", 5) != 1 {
36 return __syscall(93, 22, 0, 0, 0, 0, 0)
37 }
38 if bf.n_inserted != 3 {
39 return __syscall(93, 23, 0, 0, 0, 0, 0)
40 }
41
42 // ---- envelope for queries ----
43 // m/n = 8192/3 ≈ 2730; FPR very low.
44 let q_alice: *ApproxI64 = nx_bloom_query(bf, "alice", 5)
45 if q_alice.envelope_kind != NX_ENV_ABS {
46 return __syscall(93, 30, 0, 0, 0, 0, 0)
47 }
48 if q_alice.value != 1 { // alice IS present
49 return __syscall(93, 31, 0, 0, 0, 0, 0)
50 }
51 if q_alice.maturity != NX_MATURITY_REFERENCE_IMPL {
52 return __syscall(93, 32, 0, 0, 0, 0, 0)
53 }
54 // m/n > 32 -> fpr_ppb = 0 -> conf_ppb = 1e9.
55 if q_alice.conf_ppb != 1000000000 {
56 return __syscall(93, 33, 0, 0, 0, 0, 0)
57 }
58
59 // ---- bulk insert and load FPR step-up ----
60 // Insert 1024 items into m=8192 filter -> m/n = 8 -> FPR ~ 2.14%.
61 let bf2: *BloomS = nx_bloom_alloc(8192, 5)
62 let buf: *u8 = sys_mmap(8)
63 var i: i64 = 0
64 while i < 1024 {
65 buf[0] = (i ) & 0xFF
66 buf[1] = (i >> 8 ) & 0xFF
67 buf[2] = (i >> 16) & 0xFF
68 buf[3] = 0xA1
69 buf[4] = 0
70 buf[5] = 0
71 buf[6] = 0
72 buf[7] = 0
73 nx_bloom_insert(bf2, buf, 8)
74 i = i + 1
75 }
76 if bf2.n_inserted != 1024 {
77 return __syscall(93, 40, 0, 0, 0, 0, 0)
78 }
79 // m/n = 8 -> tabulated FPR 21_420_000 ppb.
80 if nx_bloom_fpr_ppb(bf2) != 21420000 {
81 return __syscall(93, 41, 0, 0, 0, 0, 0)
82 }
83
84 // All inserted items still detected (BL1: zero false negatives).
85 i = 0
86 while i < 1024 {
87 buf[0] = (i ) & 0xFF
88 buf[1] = (i >> 8 ) & 0xFF
89 buf[2] = (i >> 16) & 0xFF
90 buf[3] = 0xA1
91 buf[4] = 0
92 buf[5] = 0
93 buf[6] = 0
94 buf[7] = 0
95 if nx_bloom_contains(bf2, buf, 8) != 1 {
96 return __syscall(93, 42, 0, 0, 0, 0, 0)
97 }
98 i = i + 1
99 }
100
101 // ---- load_ppt sanity ----
102 let load: i64 = nx_bloom_load_ppt(bf2)
103 // 1024/8192 = 0.125 = 125 ppt.
104 if load != 125 {
105 return __syscall(93, 50, 0, 0, 0, 0, 0)
106 }
107
108 return 0
109}