1#include <math/align.h>
2#include <math/fixed.h>
3#include <math/hash.h>
4#include <math/min_max.h>
5#include <mem/alloc.h>
6#include <stdbool.h>
7#include <stdint.h>
8#include <string.h>
9#include <structures/bloom.h>
10
11static uint64_t murmur_mix64(uint64_t k) {
12 k ^= k >> 33;
13 k *= UINT64_C(0xff51afd7ed558ccd);
14 k ^= k >> 33;
15 k *= UINT64_C(0xc4ceb9fe1a85ec53);
16 k ^= k >> 33;
17 return k;
18}
19
20static uint64_t djb2_64(const char *data, size_t len) {
21 uint64_t hash = 5381;
22 for (size_t i = 0; i < len; i++)
23 hash = hash * 33 ^ (uint8_t) data[i];
24 return murmur_mix64(k: hash);
25}
26
27static uint32_t counter_get(const uint8_t *counters, size_t idx) {
28 uint8_t byte = counters[idx / 2];
29 return (idx % 2 == 0) ? (byte & 0x0Fu) : (byte >> 4);
30}
31
32static void counter_set(uint8_t *counters, size_t idx, uint32_t val) {
33 val = MIN(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 num_counters = MAX(num_counters, CBF_COUNTERS_MIN);
90 num_hashes = CLAMP(num_hashes, CBF_HASHES_MIN, CBF_HASHES_MAX);
91 num_counters = ALIGN_UP(num_counters, 2);
92
93 struct counting_bloom_filter *cbf = vnew(cbf);
94 if (!cbf)
95 return NULL;
96
97 size_t byte_count = num_counters / COUNTERS_PER_BYTE;
98 cbf->counters = valloc(byte_count, ALLOC_ZERO);
99 if (!cbf->counters) {
100 vfree(cbf);
101 return NULL;
102 }
103
104 cbf->num_counters = num_counters;
105 cbf->num_hashes = num_hashes;
106 cbf->live_elements = 0;
107
108 return cbf;
109}
110
111void cbf_destroy(struct counting_bloom_filter *cbf) {
112 if (cbf) {
113 vfree(cbf->counters);
114 vfree(cbf);
115 }
116}
117
118void cbf_add(struct counting_bloom_filter *cbf, const char *element) {
119 if (!cbf || !element)
120 return;
121
122 size_t positions[CBF_HASHES_MAX];
123 compute_positions(cbf, element, positions);
124
125 for (size_t i = 0; i < cbf->num_hashes; i++)
126 counter_increment(counters: cbf->counters, idx: positions[i]);
127
128 cbf->live_elements++;
129}
130
131bool cbf_contains(const struct counting_bloom_filter *cbf,
132 const char *element) {
133 if (!cbf || !element)
134 return false;
135
136 size_t positions[CBF_HASHES_MAX];
137 compute_positions(cbf, element, positions);
138
139 for (size_t i = 0; i < cbf->num_hashes; i++)
140 if (counter_get(counters: cbf->counters, idx: positions[i]) == 0)
141 return false;
142
143 return true;
144}
145
146enum bloom_remove_result cbf_remove(struct counting_bloom_filter *cbf,
147 const char *element) {
148 if (!cbf || !element)
149 return BLOOM_REMOVE_NOT_FOUND;
150
151 size_t positions[CBF_HASHES_MAX];
152 compute_positions(cbf, element, positions);
153
154 /* all k counters must be in range (0, COUNTER_MAX) */
155 for (size_t i = 0; i < cbf->num_hashes; i++) {
156 uint32_t v = counter_get(counters: cbf->counters, idx: positions[i]);
157
158 if (v == 0)
159 return BLOOM_REMOVE_NOT_FOUND;
160
161 if (v == COUNTER_MAX)
162 return BLOOM_REMOVE_SATURATED;
163 }
164
165 for (size_t i = 0; i < cbf->num_hashes; i++)
166 counter_decrement(counters: cbf->counters, idx: positions[i]);
167
168 if (cbf->live_elements > 0)
169 cbf->live_elements--;
170
171 return BLOOM_REMOVE_OK;
172}
173
174fx32_32_t cbf_estimated_fpr(const struct counting_bloom_filter *cbf) {
175 if (!cbf || cbf->num_counters == 0)
176 return FX_ONE;
177
178 fx32_32_t exp =
179 fx_from_int(x: -(int64_t) cbf->num_hashes * (int64_t) cbf->live_elements /
180 (int64_t) cbf->num_counters);
181 return fx_pow_i32(FX_ONE - fx_exp(x: exp), exp: fx_from_int(x: cbf->num_hashes));
182}
183