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