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