From be0475f2a583d203465d3091ff933806a5ace613 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Sun, 16 Aug 2020 20:46:39 +0200 Subject: split of set union from set service (preliminary) --- src/setu/gnunet-service-setu_strata_estimator.c | 303 ++++++++++++++++++++++++ 1 file changed, 303 insertions(+) create mode 100644 src/setu/gnunet-service-setu_strata_estimator.c (limited to 'src/setu/gnunet-service-setu_strata_estimator.c') diff --git a/src/setu/gnunet-service-setu_strata_estimator.c b/src/setu/gnunet-service-setu_strata_estimator.c new file mode 100644 index 000000000..0fa6a6f17 --- /dev/null +++ b/src/setu/gnunet-service-setu_strata_estimator.c @@ -0,0 +1,303 @@ +/* + This file is part of GNUnet + Copyright (C) 2012 GNUnet e.V. + + GNUnet is free software: you can redistribute it and/or modify it + under the terms of the GNU Affero General Public License as published + by the Free Software Foundation, either version 3 of the License, + or (at your option) any later version. + + GNUnet is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see . + + SPDX-License-Identifier: AGPL3.0-or-later + */ +/** + * @file set/gnunet-service-setu_strata_estimator.c + * @brief invertible bloom filter + * @author Florian Dold + * @author Christian Grothoff + */ +#include "platform.h" +#include "gnunet_util_lib.h" +#include "ibf.h" +#include "gnunet-service-setu_strata_estimator.h" + + +/** + * Should we try compressing the strata estimator? This will + * break compatibility with the 0.10.1-network. + */ +#define FAIL_10_1_COMPATIBILTIY 1 + + +/** + * Write the given strata estimator to the buffer. + * + * @param se strata estimator to serialize + * @param[out] buf buffer to write to, must be of appropriate size + * @return number of bytes written to @a buf + */ +size_t +strata_estimator_write (const struct StrataEstimator *se, + void *buf) +{ + char *sbuf = buf; + unsigned int i; + size_t osize; + + GNUNET_assert (NULL != se); + for (i = 0; i < se->strata_count; i++) + { + ibf_write_slice (se->strata[i], + 0, + se->ibf_size, + &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]); + } + osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; +#if FAIL_10_1_COMPATIBILTIY + { + char *cbuf; + size_t nsize; + + if (GNUNET_YES == + GNUNET_try_compression (buf, + osize, + &cbuf, + &nsize)) + { + GNUNET_memcpy (buf, cbuf, nsize); + osize = nsize; + GNUNET_free (cbuf); + } + } +#endif + return osize; +} + + +/** + * Read strata from the buffer into the given strata + * estimator. The strata estimator must already be allocated. + * + * @param buf buffer to read from + * @param buf_len number of bytes in @a buf + * @param is_compressed is the data compressed? + * @param[out] se strata estimator to write to + * @return #GNUNET_OK on success + */ +int +strata_estimator_read (const void *buf, + size_t buf_len, + int is_compressed, + struct StrataEstimator *se) +{ + unsigned int i; + size_t osize; + char *dbuf; + + dbuf = NULL; + if (GNUNET_YES == is_compressed) + { + osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; + dbuf = GNUNET_decompress (buf, + buf_len, + osize); + if (NULL == dbuf) + { + GNUNET_break_op (0); /* bad compressed input data */ + return GNUNET_SYSERR; + } + buf = dbuf; + buf_len = osize; + } + + if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE) + { + GNUNET_break (0); /* very odd error */ + GNUNET_free (dbuf); + return GNUNET_SYSERR; + } + + for (i = 0; i < se->strata_count; i++) + { + ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]); + buf += se->ibf_size * IBF_BUCKET_SIZE; + } + GNUNET_free (dbuf); + return GNUNET_OK; +} + + +/** + * Add a key to the strata estimator. + * + * @param se strata estimator to add the key to + * @param key key to add + */ +void +strata_estimator_insert (struct StrataEstimator *se, + struct IBF_Key key) +{ + uint64_t v; + unsigned int i; + + v = key.key_val; + /* count trailing '1'-bits of v */ + for (i = 0; v & 1; v >>= 1, i++) + /* empty */; + ibf_insert (se->strata[i], key); +} + + +/** + * Remove a key from the strata estimator. + * + * @param se strata estimator to remove the key from + * @param key key to remove + */ +void +strata_estimator_remove (struct StrataEstimator *se, + struct IBF_Key key) +{ + uint64_t v; + unsigned int i; + + v = key.key_val; + /* count trailing '1'-bits of v */ + for (i = 0; v & 1; v >>= 1, i++) + /* empty */; + ibf_remove (se->strata[i], key); +} + + +/** + * Create a new strata estimator with the given parameters. + * + * @param strata_count number of stratas, that is, number of ibfs in the estimator + * @param ibf_size size of each ibf stratum + * @param ibf_hashnum hashnum parameter of each ibf + * @return a freshly allocated, empty strata estimator, NULL on error + */ +struct StrataEstimator * +strata_estimator_create (unsigned int strata_count, + uint32_t ibf_size, + uint8_t ibf_hashnum) +{ + struct StrataEstimator *se; + unsigned int i; + unsigned int j; + + se = GNUNET_new (struct StrataEstimator); + se->strata_count = strata_count; + se->ibf_size = ibf_size; + se->strata = GNUNET_new_array (strata_count, + struct InvertibleBloomFilter *); + for (i = 0; i < strata_count; i++) + { + se->strata[i] = ibf_create (ibf_size, ibf_hashnum); + if (NULL == se->strata[i]) + { + GNUNET_log (GNUNET_ERROR_TYPE_ERROR, + "Failed to allocate memory for strata estimator\n"); + for (j = 0; j < i; j++) + ibf_destroy (se->strata[i]); + GNUNET_free (se); + return NULL; + } + } + return se; +} + + +/** + * Estimate set difference with two strata estimators, + * i.e. arrays of IBFs. + * Does not not modify its arguments. + * + * @param se1 first strata estimator + * @param se2 second strata estimator + * @return the estimated difference + */ +unsigned int +strata_estimator_difference (const struct StrataEstimator *se1, + const struct StrataEstimator *se2) +{ + unsigned int count; + + GNUNET_assert (se1->strata_count == se2->strata_count); + count = 0; + for (int i = se1->strata_count - 1; i >= 0; i--) + { + struct InvertibleBloomFilter *diff; + /* number of keys decoded from the ibf */ + + /* FIXME: implement this without always allocating new IBFs */ + diff = ibf_dup (se1->strata[i]); + ibf_subtract (diff, se2->strata[i]); + for (int ibf_count = 0; GNUNET_YES; ibf_count++) + { + int more; + + more = ibf_decode (diff, NULL, NULL); + if (GNUNET_NO == more) + { + count += ibf_count; + break; + } + /* Estimate if decoding fails or would not terminate */ + if ((GNUNET_SYSERR == more) || (ibf_count > diff->size)) + { + ibf_destroy (diff); + return count * (1 << (i + 1)); + } + } + ibf_destroy (diff); + } + return count; +} + + +/** + * Make a copy of a strata estimator. + * + * @param se the strata estimator to copy + * @return the copy + */ +struct StrataEstimator * +strata_estimator_dup (struct StrataEstimator *se) +{ + struct StrataEstimator *c; + unsigned int i; + + c = GNUNET_new (struct StrataEstimator); + c->strata_count = se->strata_count; + c->ibf_size = se->ibf_size; + c->strata = GNUNET_new_array (se->strata_count, + struct InvertibleBloomFilter *); + for (i = 0; i < se->strata_count; i++) + c->strata[i] = ibf_dup (se->strata[i]); + return c; +} + + +/** + * Destroy a strata estimator, free all of its resources. + * + * @param se strata estimator to destroy. + */ +void +strata_estimator_destroy (struct StrataEstimator *se) +{ + unsigned int i; + + for (i = 0; i < se->strata_count; i++) + ibf_destroy (se->strata[i]); + GNUNET_free (se->strata); + GNUNET_free (se); +} -- cgit v1.2.3