src/set/gnunet-service-set_union_strata_estimator.c

   1 /*
   2       This file is part of GNUnet
   3       Copyright (C) 2012 GNUnet e.V.
   4
   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.
   9
  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.
  14
  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/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  19  */
  20 /**
  21  * @file set/gnunet-service-set_union_strata_estimator.c
  22  * @brief invertible bloom filter
  23  * @author Florian Dold
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_util_lib.h"
  28 #include "ibf.h"
  29 #include "gnunet-service-set_union_strata_estimator.h"
  30
  31
  32 /**
  33  * Should we try compressing the strata estimator? This will
  34  * break compatibility with the 0.10.1-network.
  35  */
  36 #define FAIL_10_1_COMPATIBILTIY 1
  37
  38
  39 /**
  40  * Write the given strata estimator to the buffer.
  41  *
  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
  45  */
  46 size_t
  47 strata_estimator_write(const struct StrataEstimator *se,
  48                        void *buf)
  49 {
  50   char *sbuf = buf;
  51   unsigned int i;
  52   size_t osize;
  53
  54   GNUNET_assert(NULL != se);
  55   for (i = 0; i < se->strata_count; i++)
  56     {
  57       ibf_write_slice(se->strata[i],
  58                       0,
  59                       se->ibf_size,
  60                       &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]);
  61     }
  62   osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
  63 #if FAIL_10_1_COMPATIBILTIY
  64   {
  65     char *cbuf;
  66     size_t nsize;
  67
  68     if (GNUNET_YES ==
  69         GNUNET_try_compression(buf,
  70                                osize,
  71                                &cbuf,
  72                                &nsize))
  73       {
  74         GNUNET_memcpy(buf, cbuf, nsize);
  75         osize = nsize;
  76         GNUNET_free(cbuf);
  77       }
  78   }
  79 #endif
  80   return osize;
  81 }
  82
  83
  84 /**
  85  * Read strata from the buffer into the given strata
  86  * estimator.  The strata estimator must already be allocated.
  87  *
  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
  93  */
  94 int
  95 strata_estimator_read(const void *buf,
  96                       size_t buf_len,
  97                       int is_compressed,
  98                       struct StrataEstimator *se)
  99 {
 100   unsigned int i;
 101   size_t osize;
 102   char *dbuf;
 103
 104   dbuf = NULL;
 105   if (GNUNET_YES == is_compressed)
 106     {
 107       osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
 108       dbuf = GNUNET_decompress(buf,
 109                                buf_len,
 110                                osize);
 111       if (NULL == dbuf)
 112         {
 113           GNUNET_break_op(0); /* bad compressed input data */
 114           return GNUNET_SYSERR;
 115         }
 116       buf = dbuf;
 117       buf_len = osize;
 118     }
 119
 120   if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE)
 121     {
 122       GNUNET_break(0); /* very odd error */
 123       GNUNET_free_non_null(dbuf);
 124       return GNUNET_SYSERR;
 125     }
 126
 127   for (i = 0; i < se->strata_count; i++)
 128     {
 129       ibf_read_slice(buf, 0, se->ibf_size, se->strata[i]);
 130       buf += se->ibf_size * IBF_BUCKET_SIZE;
 131     }
 132   GNUNET_free_non_null(dbuf);
 133   return GNUNET_OK;
 134 }
 135
 136
 137 /**
 138  * Add a key to the strata estimator.
 139  *
 140  * @param se strata estimator to add the key to
 141  * @param key key to add
 142  */
 143 void
 144 strata_estimator_insert(struct StrataEstimator *se,
 145                         struct IBF_Key key)
 146 {
 147   uint64_t v;
 148   unsigned int i;
 149
 150   v = key.key_val;
 151   /* count trailing '1'-bits of v */
 152   for (i = 0; v & 1; v >>= 1, i++)
 153     /* empty */;
 154   ibf_insert(se->strata[i], key);
 155 }
 156
 157
 158 /**
 159  * Remove a key from the strata estimator.
 160  *
 161  * @param se strata estimator to remove the key from
 162  * @param key key to remove
 163  */
 164 void
 165 strata_estimator_remove(struct StrataEstimator *se,
 166                         struct IBF_Key key)
 167 {
 168   uint64_t v;
 169   unsigned int i;
 170
 171   v = key.key_val;
 172   /* count trailing '1'-bits of v */
 173   for (i = 0; v & 1; v >>= 1, i++)
 174     /* empty */;
 175   ibf_remove(se->strata[i], key);
 176 }
 177
 178
 179 /**
 180  * Create a new strata estimator with the given parameters.
 181  *
 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
 186  */
 187 struct StrataEstimator *
 188 strata_estimator_create(unsigned int strata_count,
 189                         uint32_t ibf_size,
 190                         uint8_t ibf_hashnum)
 191 {
 192   struct StrataEstimator *se;
 193   unsigned int i;
 194   unsigned int j;
 195
 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++)
 202     {
 203       se->strata[i] = ibf_create(ibf_size, ibf_hashnum);
 204       if (NULL == se->strata[i])
 205         {
 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]);
 210           GNUNET_free(se);
 211           return NULL;
 212         }
 213     }
 214   return se;
 215 }
 216
 217
 218 /**
 219  * Estimate set difference with two strata estimators,
 220  * i.e. arrays of IBFs.
 221  * Does not not modify its arguments.
 222  *
 223  * @param se1 first strata estimator
 224  * @param se2 second strata estimator
 225  * @return the estimated difference
 226  */
 227 unsigned int
 228 strata_estimator_difference(const struct StrataEstimator *se1,
 229                             const struct StrataEstimator *se2)
 230 {
 231   unsigned int count;
 232
 233   GNUNET_assert(se1->strata_count == se2->strata_count);
 234   count = 0;
 235   for (int i = se1->strata_count - 1; i >= 0; i--)
 236     {
 237       struct InvertibleBloomFilter *diff;
 238       /* number of keys decoded from the ibf */
 239
 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++)
 244         {
 245           int more;
 246
 247           more = ibf_decode(diff, NULL, NULL);
 248           if (GNUNET_NO == more)
 249             {
 250               count += ibf_count;
 251               break;
 252             }
 253           /* Estimate if decoding fails or would not terminate */
 254           if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
 255             {
 256               ibf_destroy(diff);
 257               return count * (1 << (i + 1));
 258             }
 259         }
 260       ibf_destroy(diff);
 261     }
 262   return count;
 263 }
 264
 265
 266 /**
 267  * Make a copy of a strata estimator.
 268  *
 269  * @param se the strata estimator to copy
 270  * @return the copy
 271  */
 272 struct StrataEstimator *
 273 strata_estimator_dup(struct StrataEstimator *se)
 274 {
 275   struct StrataEstimator *c;
 276   unsigned int i;
 277
 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]);
 285   return c;
 286 }
 287
 288
 289 /**
 290  * Destroy a strata estimator, free all of its resources.
 291  *
 292  * @param se strata estimator to destroy.
 293  */
 294 void
 295 strata_estimator_destroy(struct StrataEstimator *se)
 296 {
 297   unsigned int i;
 298
 299   for (i = 0; i < se->strata_count; i++)
 300     ibf_destroy(se->strata[i]);
 301   GNUNET_free(se->strata);
 302   GNUNET_free(se);
 303 }