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