2 This file is part of GNUnet
3 Copyright (C) 2012 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
21 * @file set/gnunet-service-set_union_strata_estimator.c
22 * @brief invertible bloom filter
23 * @author Florian Dold
24 * @author Christian Grothoff
27 #include "gnunet_util_lib.h"
29 #include "gnunet-service-set_union_strata_estimator.h"
33 * Should we try compressing the strata estimator? This will
34 * break compatibility with the 0.10.1-network.
36 #define FAIL_10_1_COMPATIBILTIY 1
40 * Write the given strata estimator to the buffer.
42 * @param se strata estimator to serialize
43 * @param[out] buf buffer to write to, must be of appropriate size
44 * @return number of bytes written to @a buf
47 strata_estimator_write (const struct StrataEstimator *se,
54 GNUNET_assert (NULL != se);
55 for (i = 0; i < se->strata_count; i++)
57 ibf_write_slice (se->strata[i],
60 &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]);
62 osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
63 #if FAIL_10_1_COMPATIBILTIY
69 GNUNET_try_compression (buf,
74 GNUNET_memcpy (buf, cbuf, nsize);
85 * Read strata from the buffer into the given strata
86 * estimator. The strata estimator must already be allocated.
88 * @param buf buffer to read from
89 * @param buf_len number of bytes in @a buf
90 * @param is_compressed is the data compressed?
91 * @param[out] se strata estimator to write to
92 * @return #GNUNET_OK on success
95 strata_estimator_read (const void *buf,
98 struct StrataEstimator *se)
105 if (GNUNET_YES == is_compressed)
107 osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
108 dbuf = GNUNET_decompress (buf,
113 GNUNET_break_op (0); /* bad compressed input data */
114 return GNUNET_SYSERR;
120 if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE)
122 GNUNET_break (0); /* very odd error */
123 GNUNET_free_non_null (dbuf);
124 return GNUNET_SYSERR;
127 for (i = 0; i < se->strata_count; i++)
129 ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
130 buf += se->ibf_size * IBF_BUCKET_SIZE;
132 GNUNET_free_non_null (dbuf);
138 * Add a key to the strata estimator.
140 * @param se strata estimator to add the key to
141 * @param key key to add
144 strata_estimator_insert (struct StrataEstimator *se,
151 /* count trailing '1'-bits of v */
152 for (i = 0; v &1; v >>= 1, i++)
154 ibf_insert (se->strata[i], key);
159 * Remove a key from the strata estimator.
161 * @param se strata estimator to remove the key from
162 * @param key key to remove
165 strata_estimator_remove (struct StrataEstimator *se,
172 /* count trailing '1'-bits of v */
173 for (i = 0; v &1; v >>= 1, i++)
175 ibf_remove (se->strata[i], key);
180 * Create a new strata estimator with the given parameters.
182 * @param strata_count number of stratas, that is, number of ibfs in the estimator
183 * @param ibf_size size of each ibf stratum
184 * @param ibf_hashnum hashnum parameter of each ibf
185 * @return a freshly allocated, empty strata estimator, NULL on error
187 struct StrataEstimator *
188 strata_estimator_create (unsigned int strata_count,
192 struct StrataEstimator *se;
196 se = GNUNET_new (struct StrataEstimator);
197 se->strata_count = strata_count;
198 se->ibf_size = ibf_size;
199 se->strata = GNUNET_new_array (strata_count,
200 struct InvertibleBloomFilter *);
201 for (i = 0; i < strata_count; i++)
203 se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
204 if (NULL == se->strata[i])
206 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
207 "Failed to allocate memory for strata estimator\n");
208 for (j = 0; j < i; j++)
209 ibf_destroy (se->strata[i]);
219 * Estimate set difference with two strata estimators,
220 * i.e. arrays of IBFs.
221 * Does not not modify its arguments.
223 * @param se1 first strata estimator
224 * @param se2 second strata estimator
225 * @return the estimated difference
228 strata_estimator_difference (const struct StrataEstimator *se1,
229 const struct StrataEstimator *se2)
233 GNUNET_assert (se1->strata_count == se2->strata_count);
235 for (int i = se1->strata_count - 1; i >= 0; i--)
237 struct InvertibleBloomFilter *diff;
238 /* number of keys decoded from the ibf */
240 /* FIXME: implement this without always allocating new IBFs */
241 diff = ibf_dup (se1->strata[i]);
242 ibf_subtract (diff, se2->strata[i]);
243 for (int ibf_count = 0; GNUNET_YES; ibf_count++)
247 more = ibf_decode (diff, NULL, NULL);
248 if (GNUNET_NO == more)
253 /* Estimate if decoding fails or would not terminate */
254 if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
257 return count * (1 << (i + 1));
267 * Make a copy of a strata estimator.
269 * @param se the strata estimator to copy
272 struct StrataEstimator *
273 strata_estimator_dup (struct StrataEstimator *se)
275 struct StrataEstimator *c;
278 c = GNUNET_new (struct StrataEstimator);
279 c->strata_count = se->strata_count;
280 c->ibf_size = se->ibf_size;
281 c->strata = GNUNET_new_array (se->strata_count,
282 struct InvertibleBloomFilter *);
283 for (i = 0; i < se->strata_count; i++)
284 c->strata[i] = ibf_dup (se->strata[i]);
290 * Destroy a strata estimator, free all of its resources.
292 * @param se strata estimator to destroy.
295 strata_estimator_destroy (struct StrataEstimator *se)
299 for (i = 0; i < se->strata_count; i++)
300 ibf_destroy (se->strata[i]);
301 GNUNET_free (se->strata);