1#include <math/fixed.h>
2#include <math/fixed_extended.h>
3#include <math/hash.h>
4#include <mem/alloc.h>
5#include <stdbool.h>
6#include <stdint.h>
7#include <string.h>
8#include <structures/bloom.h>
9
10static uint64_t murmur_mix64(uint64_t k) {
11 k ^= k >> 33;
12 k *= UINT64_C(0xff51afd7ed558ccd);
13 k ^= k >> 33;
14 k *= UINT64_C(0xc4ceb9fe1a85ec53);
15 k ^= k >> 33;
16 return k;
17}
18
19static uint64_t djb2_64(const char *data, size_t len) {
20 uint64_t hash = 5381;
21 for (size_t i = 0; i < len; i++)
22 hash = hash * 33 ^ (uint8_t) data[i];
23 return murmur_mix64(k: hash);
24}
25
26static uint32_t counter_get(const uint8_t *counters, size_t idx) {
27 uint8_t byte = counters[idx / 2];
28 return (idx % 2 == 0) ? (byte & 0x0Fu) : (byte >> 4);
29}
30
31static void counter_set(uint8_t *counters, size_t idx, uint32_t val) {
32 if (val > COUNTER_MAX)
33 val = COUNTER_MAX;
34 if (idx % 2 == 0)
35 counters[idx / 2] =
36 (counters[idx / 2] & 0xF0u) | (uint8_t) (val & 0x0Fu);
37 else
38 counters[idx / 2] =
39 (counters[idx / 2] & 0x0Fu) | (uint8_t) ((val & 0x0Fu) << 4);
40}
41
42static void counter_increment(uint8_t *counters, size_t idx) {
43 uint32_t v = counter_get(counters, idx);
44 if (v < COUNTER_MAX) /* saturating */
45 counter_set(counters, idx, val: v + 1);
46}
47
48static void counter_decrement(uint8_t *counters, size_t idx) {
49 uint32_t v = counter_get(counters, idx);
50 if (v > 0)
51 counter_set(counters, idx, val: v - 1);
52}
53
54static void compute_positions(const struct counting_bloom_filter *cbf,
55 const char *element, size_t *positions) {
56 size_t len = strlen(str: element);
57 uint64_t h1 = hash_fnv1a_64(key: element, len);
58 uint64_t h2 = djb2_64(data: element, len);
59
60 for (size_t i = 0; i < cbf->num_hashes; i++) {
61 uint64_t combined = h1 + (uint64_t) i * h2;
62 positions[i] = (size_t) (combined % (uint64_t) cbf->num_counters);
63 }
64}
65
66/*
67 * cbf_create -- allocate a counting bloom filter sized for `capacity`
68 * simultaneous live elements at the desired `false_positive_rate`.
69 *
70 * Uses the standard optimal formulas:
71 * m = -n * ln(p) / ln(2)^2 (counter slots)
72 * k = (m/n) * ln(2) (hash functions)
73 */
74struct counting_bloom_filter *cbf_create(size_t capacity,
75 fx32_32_t false_positive_rate) {
76 if (capacity == 0 || false_positive_rate <= FX(0.0) ||
77 false_positive_rate >= FX_ONE)
78 return NULL;
79
80 fx32_32_t ln2 = FX(0.69314718056);
81 fx32_32_t ln2sq = FX(0.48045301391);
82
83 size_t num_counters = fx_to_int(x: fx_ceil(x: fx_div(
84 a: fx_mul(a: -fx_from_int(x: capacity), b: fx_ln(x: false_positive_rate)), b: ln2sq)));
85
86 size_t num_hashes = fx_to_int(x: fx_ceil(
87 x: fx_mul(a: fx_div(a: fx_from_int(x: num_counters), b: fx_from_int(x: capacity)), b: ln2)));
88
89 if (num_counters < 8)
90 num_counters = 8;
91
92 if (num_hashes < 1)
93 num_hashes = 1;
94
95 if (num_hashes > 20)
96 num_hashes = 20;
97
98 if (num_counters % 2 != 0)
99 num_counters++;
100
101 struct counting_bloom_filter *cbf =
102 kmalloc(sizeof(struct counting_bloom_filter));
103 if (!cbf)
104 return NULL;
105
106 size_t byte_count = num_counters / COUNTERS_PER_BYTE;
107 cbf->counters = kmalloc(byte_count, ALLOC_FLAGS_ZERO);
108 if (!cbf->counters) {
109 kfree(cbf);
110 return NULL;
111 }
112
113 cbf->num_counters = num_counters;
114 cbf->num_hashes = num_hashes;
115 cbf->live_elements = 0;
116
117 return cbf;
118}
119
120void cbf_destroy(struct counting_bloom_filter *cbf) {
121 if (cbf) {
122 kfree(cbf->counters);
123 kfree(cbf);
124 }
125}
126
127void cbf_add(struct counting_bloom_filter *cbf, const char *element) {
128 if (!cbf || !element)
129 return;
130
131 size_t positions[20];
132 compute_positions(cbf, element, positions);
133
134 for (size_t i = 0; i < cbf->num_hashes; i++)
135 counter_increment(counters: cbf->counters, idx: positions[i]);
136
137 cbf->live_elements++;
138}
139
140bool cbf_contains(const struct counting_bloom_filter *cbf,
141 const char *element) {
142 if (!cbf || !element)
143 return false;
144
145 size_t positions[20];
146 compute_positions(cbf, element, positions);
147
148 for (size_t i = 0; i < cbf->num_hashes; i++)
149 if (counter_get(counters: cbf->counters, idx: positions[i]) == 0)
150 return false;
151
152 return true;
153}
154
155enum bloom_remove_result cbf_remove(struct counting_bloom_filter *cbf,
156 const char *element) {
157 if (!cbf || !element)
158 return BLOOM_REMOVE_NOT_FOUND;
159
160 size_t positions[20];
161 compute_positions(cbf, element, positions);
162
163 /* all k counters must be in range (0, COUNTER_MAX) */
164 for (size_t i = 0; i < cbf->num_hashes; i++) {
165 uint32_t v = counter_get(counters: cbf->counters, idx: positions[i]);
166
167 if (v == 0)
168 return BLOOM_REMOVE_NOT_FOUND;
169
170 if (v == COUNTER_MAX)
171 return BLOOM_REMOVE_SATURATED;
172 }
173
174 for (size_t i = 0; i < cbf->num_hashes; i++)
175 counter_decrement(counters: cbf->counters, idx: positions[i]);
176
177 if (cbf->live_elements > 0)
178 cbf->live_elements--;
179
180 return BLOOM_REMOVE_OK;
181}
182
183fx32_32_t cbf_estimated_fpr(const struct counting_bloom_filter *cbf) {
184 if (!cbf || cbf->num_counters == 0)
185 return FX_ONE;
186
187 fx32_32_t exp =
188 fx_from_int(x: -(int64_t) cbf->num_hashes * (int64_t) cbf->live_elements /
189 (int64_t) cbf->num_counters);
190 return fx_pow_i32(FX_ONE - fx_exp(x: exp), exp: fx_from_int(x: cbf->num_hashes));
191}
192