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