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
   6       it under the terms of the GNU General Public License as published
   7       by the Free Software Foundation; either version 3, or (at your
   8       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       General Public License for more details.
  14
  15       You should have received a copy of the GNU General Public License
  16       along with GNUnet; see the file COPYING.  If not, write to the
  17       Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18       Boston, MA 02110-1301, USA.
  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   int i;
 232   unsigned int count;
 233
 234   GNUNET_assert (se1->strata_count == se2->strata_count);
 235   count = 0;
 236   for (i = se1->strata_count - 1; i >= 0; i--)
 237   {
 238     struct InvertibleBloomFilter *diff;
 239     /* number of keys decoded from the ibf */
 240     int ibf_count;
 241
 242     /* FIXME: implement this without always allocating new IBFs */
 243     diff = ibf_dup (se1->strata[i]);
 244     ibf_subtract (diff, se2->strata[i]);
 245     for (ibf_count = 0; GNUNET_YES; ibf_count++)
 246     {
 247       int more;
 248
 249       more = ibf_decode (diff, NULL, NULL);
 250       if (GNUNET_NO == more)
 251       {
 252         count += ibf_count;
 253         break;
 254       }
 255       /* Estimate if decoding fails or would not terminate */
 256       if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
 257       {
 258         ibf_destroy (diff);
 259         return count * (1 << (i + 1));
 260       }
 261     }
 262     ibf_destroy (diff);
 263   }
 264   return count;
 265 }
 266
 267
 268 /**
 269  * Make a copy of a strata estimator.
 270  *
 271  * @param se the strata estimator to copy
 272  * @return the copy
 273  */
 274 struct StrataEstimator *
 275 strata_estimator_dup (struct StrataEstimator *se)
 276 {
 277   struct StrataEstimator *c;
 278   unsigned int i;
 279
 280   c = GNUNET_new (struct StrataEstimator);
 281   c->strata_count = se->strata_count;
 282   c->ibf_size = se->ibf_size;
 283   c->strata = GNUNET_new_array (se->strata_count,
 284                                 struct InvertibleBloomFilter *);
 285   for (i = 0; i < se->strata_count; i++)
 286     c->strata[i] = ibf_dup (se->strata[i]);
 287   return c;
 288 }
 289
 290
 291 /**
 292  * Destroy a strata estimator, free all of its resources.
 293  *
 294  * @param se strata estimator to destroy.
 295  */
 296 void
 297 strata_estimator_destroy (struct StrataEstimator *se)
 298 {
 299   unsigned int i;
 300
 301   for (i = 0; i < se->strata_count; i++)
 302     ibf_destroy (se->strata[i]);
 303   GNUNET_free (se->strata);
 304   GNUNET_free (se);
 305 }