src/set/ibf.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 /**
  22  * @file set/ibf.c
  23  * @brief implementation of the invertible bloom filter
  24  * @author Florian Dold
  25  */
  26
  27 #include "ibf.h"
  28
  29 /**
  30  * Compute the key's hash from the key.
  31  * Redefine to use a different hash function.
  32  */
  33 #define IBF_KEY_HASH_VAL(k) (GNUNET_CRYPTO_crc32_n (&(k), sizeof(struct \
  34                                                                  IBF_KeyHash)))
  35
  36 /**
  37  * Create a key from a hashcode.
  38  *
  39  * @param hash the hashcode
  40  * @return a key
  41  */
  42 struct IBF_Key
  43 ibf_key_from_hashcode (const struct GNUNET_HashCode *hash)
  44 {
  45   return *(struct IBF_Key *) hash;
  46 }
  47
  48
  49 /**
  50  * Create a hashcode from a key, by replicating the key
  51  * until the hascode is filled
  52  *
  53  * @param key the key
  54  * @param dst hashcode to store the result in
  55  */
  56 void
  57 ibf_hashcode_from_key (struct IBF_Key key,
  58                        struct GNUNET_HashCode *dst)
  59 {
  60   struct IBF_Key *p;
  61   unsigned int i;
  62   const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode)
  63                                          / sizeof(struct IBF_Key);
  64
  65   p = (struct IBF_Key *) dst;
  66   for (i = 0; i < keys_per_hashcode; i++)
  67     *p++ = key;
  68 }
  69
  70
  71 /**
  72  * Create an invertible bloom filter.
  73  *
  74  * @param size number of IBF buckets
  75  * @param hash_num number of buckets one element is hashed in
  76  * @return the newly created invertible bloom filter, NULL on error
  77  */
  78 struct InvertibleBloomFilter *
  79 ibf_create (uint32_t size, uint8_t hash_num)
  80 {
  81   struct InvertibleBloomFilter *ibf;
  82
  83   GNUNET_assert (0 != size);
  84
  85   ibf = GNUNET_new (struct InvertibleBloomFilter);
  86   ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t));
  87   if (NULL == ibf->count)
  88   {
  89     GNUNET_free (ibf);
  90     return NULL;
  91   }
  92   ibf->key_sum = GNUNET_malloc_large (size * sizeof(struct IBF_Key));
  93   if (NULL == ibf->key_sum)
  94   {
  95     GNUNET_free (ibf->count);
  96     GNUNET_free (ibf);
  97     return NULL;
  98   }
  99   ibf->key_hash_sum = GNUNET_malloc_large (size * sizeof(struct IBF_KeyHash));
 100   if (NULL == ibf->key_hash_sum)
 101   {
 102     GNUNET_free (ibf->key_sum);
 103     GNUNET_free (ibf->count);
 104     GNUNET_free (ibf);
 105     return NULL;
 106   }
 107   ibf->size = size;
 108   ibf->hash_num = hash_num;
 109
 110   return ibf;
 111 }
 112
 113
 114 /**
 115  * Store unique bucket indices for the specified key in dst.
 116  */
 117 static void
 118 ibf_get_indices (const struct InvertibleBloomFilter *ibf,
 119                  struct IBF_Key key,
 120                  int *dst)
 121 {
 122   uint32_t filled;
 123   uint32_t i;
 124   uint32_t bucket;
 125
 126   bucket = GNUNET_CRYPTO_crc32_n (&key, sizeof key);
 127   for (i = 0, filled = 0; filled < ibf->hash_num; i++)
 128   {
 129     unsigned int j;
 130     uint64_t x;
 131     for (j = 0; j < filled; j++)
 132       if (dst[j] == bucket)
 133         goto try_next;
 134     dst[filled++] = bucket % ibf->size;
 135 try_next:;
 136     x = ((uint64_t) bucket << 32) | i;
 137     bucket = GNUNET_CRYPTO_crc32_n (&x, sizeof x);
 138   }
 139 }
 140
 141
 142 static void
 143 ibf_insert_into (struct InvertibleBloomFilter *ibf,
 144                  struct IBF_Key key,
 145                  const int *buckets, int side)
 146 {
 147   int i;
 148
 149   for (i = 0; i < ibf->hash_num; i++)
 150   {
 151     const int bucket = buckets[i];
 152     ibf->count[bucket].count_val += side;
 153     ibf->key_sum[bucket].key_val ^= key.key_val;
 154     ibf->key_hash_sum[bucket].key_hash_val
 155       ^= IBF_KEY_HASH_VAL (key);
 156   }
 157 }
 158
 159
 160 /**
 161  * Insert a key into an IBF.
 162  *
 163  * @param ibf the IBF
 164  * @param key the element's hash code
 165  */
 166 void
 167 ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
 168 {
 169   int buckets[ibf->hash_num];
 170
 171   GNUNET_assert (ibf->hash_num <= ibf->size);
 172   ibf_get_indices (ibf, key, buckets);
 173   ibf_insert_into (ibf, key, buckets, 1);
 174 }
 175
 176
 177 /**
 178  * Remove a key from an IBF.
 179  *
 180  * @param ibf the IBF
 181  * @param key the element's hash code
 182  */
 183 void
 184 ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
 185 {
 186   int buckets[ibf->hash_num];
 187
 188   GNUNET_assert (ibf->hash_num <= ibf->size);
 189   ibf_get_indices (ibf, key, buckets);
 190   ibf_insert_into (ibf, key, buckets, -1);
 191 }
 192
 193
 194 /**
 195  * Test is the IBF is empty, i.e. all counts, keys and key hashes are zero.
 196  */
 197 static int
 198 ibf_is_empty (struct InvertibleBloomFilter *ibf)
 199 {
 200   int i;
 201
 202   for (i = 0; i < ibf->size; i++)
 203   {
 204     if (0 != ibf->count[i].count_val)
 205       return GNUNET_NO;
 206     if (0 != ibf->key_hash_sum[i].key_hash_val)
 207       return GNUNET_NO;
 208     if (0 != ibf->key_sum[i].key_val)
 209       return GNUNET_NO;
 210   }
 211   return GNUNET_YES;
 212 }
 213
 214
 215 /**
 216  * Decode and remove an element from the IBF, if possible.
 217  *
 218  * @param ibf the invertible bloom filter to decode
 219  * @param ret_side sign of the cell's count where the decoded element came from.
 220  *                 A negative sign indicates that the element was recovered
 221  *                 resides in an IBF that was previously subtracted from.
 222  * @param ret_id receives the hash code of the decoded element, if successful
 223  * @return GNUNET_YES if decoding an element was successful,
 224  *         GNUNET_NO if the IBF is empty,
 225  *         GNUNET_SYSERR if the decoding has failed
 226  */
 227 int
 228 ibf_decode (struct InvertibleBloomFilter *ibf,
 229             int *ret_side, struct IBF_Key *ret_id)
 230 {
 231   struct IBF_KeyHash hash;
 232   int i;
 233   int buckets[ibf->hash_num];
 234
 235   GNUNET_assert (NULL != ibf);
 236
 237   for (i = 0; i < ibf->size; i++)
 238   {
 239     int j;
 240     int hit;
 241
 242     /* we can only decode from pure buckets */
 243     if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
 244       continue;
 245
 246     hash.key_hash_val = IBF_KEY_HASH_VAL (ibf->key_sum[i]);
 247
 248     /* test if the hash matches the key */
 249     if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
 250       continue;
 251
 252     /* test if key in bucket hits its own location,
 253      * if not, the key hash was subject to collision */
 254     hit = GNUNET_NO;
 255     ibf_get_indices (ibf, ibf->key_sum[i], buckets);
 256     for (j = 0; j < ibf->hash_num; j++)
 257       if (buckets[j] == i)
 258         hit = GNUNET_YES;
 259
 260     if (GNUNET_NO == hit)
 261       continue;
 262
 263     if (NULL != ret_side)
 264       *ret_side = ibf->count[i].count_val;
 265     if (NULL != ret_id)
 266       *ret_id = ibf->key_sum[i];
 267
 268     /* insert on the opposite side, effectively removing the element */
 269     ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
 270
 271     return GNUNET_YES;
 272   }
 273
 274   if (GNUNET_YES == ibf_is_empty (ibf))
 275     return GNUNET_NO;
 276   return GNUNET_SYSERR;
 277 }
 278
 279
 280 /**
 281  * Write buckets from an ibf to a buffer.
 282  * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
 283  *
 284  * @param ibf the ibf to write
 285  * @param start with which bucket to start
 286  * @param count how many buckets to write
 287  * @param buf buffer to write the data to
 288  */
 289 void
 290 ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start,
 291                  uint32_t count, void *buf)
 292 {
 293   struct IBF_Key *key_dst;
 294   struct IBF_KeyHash *key_hash_dst;
 295   struct IBF_Count *count_dst;
 296
 297   GNUNET_assert (start + count <= ibf->size);
 298
 299   /* copy keys */
 300   key_dst = (struct IBF_Key *) buf;
 301   GNUNET_memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst);
 302   key_dst += count;
 303   /* copy key hashes */
 304   key_hash_dst = (struct IBF_KeyHash *) key_dst;
 305   GNUNET_memcpy (key_hash_dst, ibf->key_hash_sum + start, count
 306                  * sizeof *key_hash_dst);
 307   key_hash_dst += count;
 308   /* copy counts */
 309   count_dst = (struct IBF_Count *) key_hash_dst;
 310   GNUNET_memcpy (count_dst, ibf->count + start, count * sizeof *count_dst);
 311 }
 312
 313
 314 /**
 315  * Read buckets from a buffer into an ibf.
 316  *
 317  * @param buf pointer to the buffer to read from
 318  * @param start which bucket to start at
 319  * @param count how many buckets to read
 320  * @param ibf the ibf to read from
 321  */
 322 void
 323 ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct
 324                 InvertibleBloomFilter *ibf)
 325 {
 326   struct IBF_Key *key_src;
 327   struct IBF_KeyHash *key_hash_src;
 328   struct IBF_Count *count_src;
 329
 330   GNUNET_assert (count > 0);
 331   GNUNET_assert (start + count <= ibf->size);
 332
 333   /* copy keys */
 334   key_src = (struct IBF_Key *) buf;
 335   GNUNET_memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src);
 336   key_src += count;
 337   /* copy key hashes */
 338   key_hash_src = (struct IBF_KeyHash *) key_src;
 339   GNUNET_memcpy (ibf->key_hash_sum + start, key_hash_src, count
 340                  * sizeof *key_hash_src);
 341   key_hash_src += count;
 342   /* copy counts */
 343   count_src = (struct IBF_Count *) key_hash_src;
 344   GNUNET_memcpy (ibf->count + start, count_src, count * sizeof *count_src);
 345 }
 346
 347
 348 /**
 349  * Subtract ibf2 from ibf1, storing the result in ibf1.
 350  * The two IBF's must have the same parameters size and hash_num.
 351  *
 352  * @param ibf1 IBF that is subtracted from
 353  * @param ibf2 IBF that will be subtracted from ibf1
 354  */
 355 void
 356 ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct
 357               InvertibleBloomFilter *ibf2)
 358 {
 359   int i;
 360
 361   GNUNET_assert (ibf1->size == ibf2->size);
 362   GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
 363
 364   for (i = 0; i < ibf1->size; i++)
 365   {
 366     ibf1->count[i].count_val -= ibf2->count[i].count_val;
 367     ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
 368     ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
 369   }
 370 }
 371
 372
 373 /**
 374  * Create a copy of an IBF, the copy has to be destroyed properly.
 375  *
 376  * @param ibf the IBF to copy
 377  */
 378 struct InvertibleBloomFilter *
 379 ibf_dup (const struct InvertibleBloomFilter *ibf)
 380 {
 381   struct InvertibleBloomFilter *copy;
 382
 383   copy = GNUNET_malloc (sizeof *copy);
 384   copy->hash_num = ibf->hash_num;
 385   copy->size = ibf->size;
 386   copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size
 387                                       * sizeof(struct IBF_KeyHash));
 388   copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof(struct
 389                                                                   IBF_Key));
 390   copy->count = GNUNET_memdup (ibf->count, ibf->size * sizeof(struct
 391                                                               IBF_Count));
 392   return copy;
 393 }
 394
 395
 396 /**
 397  * Destroy all resources associated with the invertible bloom filter.
 398  * No more ibf_*-functions may be called on ibf after calling destroy.
 399  *
 400  * @param ibf the intertible bloom filter to destroy
 401  */
 402 void
 403 ibf_destroy (struct InvertibleBloomFilter *ibf)
 404 {
 405   GNUNET_free (ibf->key_sum);
 406   GNUNET_free (ibf->key_hash_sum);
 407   GNUNET_free (ibf->count);
 408   GNUNET_free (ibf);
 409 }