`bloom.nx` source

↩ module page · 123 lines · 4455 B
1// bloom.nx -- Bloom filter (Burton Howard Bloom, 1970).
2//
3// Probabilistic set membership: "probably present" or
4// "definitely absent".  Uses k independent hash functions to
5// set k bits per insert; a query returns "absent" iff any of
6// k bits is unset.
7//
8// Used for: cache-miss avoidance (Bigtable, Cassandra), spell-
9// checkers, network protocol scoping (BitTorrent peer exchange),
10// password leak detection (HIBP k-anonymity prefix).
11//
12// Trade-off: memory + time efficient at the cost of allowing
13// false positives (no false negatives).  For target false-
14// positive rate p, expected items n:
15//   m = -n * ln(p) / (ln(2)^2)         bits of bitmap
16//   k = (m / n) * ln(2)                hash functions
17// Caller picks (m, k) at construction.
18//
19// Invariants:
20//   BL1  False NEGATIVE rate is exactly 0.  If a key was
21//        inserted, query returns true.
22//   BL2  False positive rate depends on (m, k, n) per the
23//        formula above.  Caller responsibility.
24//   BL3  Capacity (cap_bits) must be a power of two so we can
25//        mask instead of modulo.  Hash bits map to bit indices
26//        via & (cap_bits - 1).
27//   BL4  Two hash functions are mixed via the "Kirsch-Mitzenmacher
28//        double hashing" trick (h1 + i*h2 for i = 0..k-1) to
29//        cheaply produce k independent-enough hashes from two.
30
31import "syscalls.nx"
32import "murmur3.nx"
33
34struct Bloom {
35    bits:    *u8,
36    cap:     i64,         // bitmap size in bits (power of 2)
37    mask:    i64,         // cap - 1, for modulo-by-mask
38    k:       i64,         // number of hash functions
39}
40
41func bl_is_pow2(n: i64) -> i64 {
42    if n < 8 { return 0 }
43    if (n & (n - 1)) != 0 { return 0 }
44    return 1
45}
46
47// Allocate a Bloom filter with `cap_bits` bitmap (must be power
48// of 2, >= 8) and k hash functions per insert/query.
49func bloom_new(cap_bits: i64, k: i64) -> *Bloom {
50    if bl_is_pow2(cap_bits) != 1 { return 0 as *Bloom }
51    if k < 1 { return 0 as *Bloom }
52    let bf_raw: *u8 = sys_mmap(64)
53    let bf: *Bloom = bf_raw as *Bloom
54    bf.bits = sys_mmap(cap_bits / 8)
55    var i: i64 = 0
56    while i < cap_bits / 8 { bf.bits[i] = 0; i = i + 1 }
57    bf.cap = cap_bits
58    bf.mask = cap_bits - 1
59    bf.k = k
60    return bf
61}
62
63// Set bit at position `bit_idx`.
64func bl_set_bit(bf: *Bloom, bit_idx: i64) -> i64 {
65    let byte_idx: i64 = (bit_idx >> 3) & ((bf.cap >> 3) - 1)
66    let bit_pos: i64 = bit_idx & 7
67    bf.bits[byte_idx] = bf.bits[byte_idx] | (1 << bit_pos)
68    return 0
69}
70
71// Test bit at position.  Returns 0 or 1.
72func bl_get_bit(bf: *Bloom, bit_idx: i64) -> i64 {
73    let byte_idx: i64 = (bit_idx >> 3) & ((bf.cap >> 3) - 1)
74    let bit_pos: i64 = bit_idx & 7
75    return (bf.bits[byte_idx] >> bit_pos) & 1
76}
77
78// Insert a key.  Sets k bits derived from two-hash double-hashing.
79func bloom_insert(bf: *Bloom, key: *u8, key_len: i64) -> i64 {
80    let h1: i64 = murmur3_32(0, key, key_len)
81    let h2: i64 = murmur3_32(1, key, key_len)
82    var i: i64 = 0
83    while i < bf.k {
84        let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
85        let bit_idx: i64 = combined & bf.mask
86        bl_set_bit(bf, bit_idx)
87        i = i + 1
88    }
89    return 0
90}
91
92// Query a key.  Returns 1 if all k bits are set ("probably
93// present"); 0 if any bit is unset ("definitely absent").
94func bloom_contains(bf: *Bloom, key: *u8, key_len: i64) -> i64 {
95    let h1: i64 = murmur3_32(0, key, key_len)
96    let h2: i64 = murmur3_32(1, key, key_len)
97    var i: i64 = 0
98    while i < bf.k {
99        let combined: i64 = (h1 + (i * h2)) & 0xFFFFFFFF
100        let bit_idx: i64 = combined & bf.mask
101        if bl_get_bit(bf, bit_idx) == 0 { return 0 }
102        i = i + 1
103    }
104    return 1
105}
106
107// Compile-only smoke.
108func main() -> i64 {
109    let bf: *Bloom = bloom_new(1024, 4)
110    if bf == (0 as *Bloom) { return 1 }
111    bloom_insert(bf, "alice", 5)
112    bloom_insert(bf, "bob", 3)
113    if bloom_contains(bf, "alice", 5) != 1 { return 2 }
114    if bloom_contains(bf, "bob", 3) != 1 { return 3 }
115    // "carol" should be ABSENT (not inserted).
116    if bloom_contains(bf, "carol", 5) != 0 {
117        // could be a false positive at 1024 bits with 2 inserts
118        // -- vanishingly unlikely but technically allowed.  Only
119        // fail if it consistently returns true for many absent
120        // keys (smoke is a single check; tolerate).
121    }
122    return 0
123}
bloom.nx source

`bloom.nx` source
