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
   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 /**
  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   GNUNET_assert (ibf->hash_num <= ibf->size);
 168   ibf_get_indices (ibf, key, buckets);
 169   ibf_insert_into (ibf, key, buckets, 1);
 170 }
 171
 172
 173 /**
 174  * Remove a key from an IBF.
 175  *
 176  * @param ibf the IBF
 177  * @param key the element's hash code
 178  */
 179 void
 180 ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
 181 {
 182   int buckets[ibf->hash_num];
 183   GNUNET_assert (ibf->hash_num <= ibf->size);
 184   ibf_get_indices (ibf, key, buckets);
 185   ibf_insert_into (ibf, key, buckets, -1);
 186 }
 187
 188
 189 /**
 190  * Test is the IBF is empty, i.e. all counts, keys and key hashes are zero.
 191  */
 192 static int
 193 ibf_is_empty (struct InvertibleBloomFilter *ibf)
 194 {
 195   int i;
 196   for (i = 0; i < ibf->size; i++)
 197   {
 198     if (0 != ibf->count[i].count_val)
 199       return GNUNET_NO;
 200     if (0 != ibf->key_hash_sum[i].key_hash_val)
 201       return GNUNET_NO;
 202     if (0 != ibf->key_sum[i].key_val)
 203       return GNUNET_NO;
 204   }
 205   return GNUNET_YES;
 206 }
 207
 208
 209 /**
 210  * Decode and remove an element from the IBF, if possible.
 211  *
 212  * @param ibf the invertible bloom filter to decode
 213  * @param ret_side sign of the cell's count where the decoded element came from.
 214  *                 A negative sign indicates that the element was recovered
 215  *                 resides in an IBF that was previously subtracted from.
 216  * @param ret_id receives the hash code of the decoded element, if successful
 217  * @return GNUNET_YES if decoding an element was successful,
 218  *         GNUNET_NO if the IBF is empty,
 219  *         GNUNET_SYSERR if the decoding has failed
 220  */
 221 int
 222 ibf_decode (struct InvertibleBloomFilter *ibf,
 223             int *ret_side, struct IBF_Key *ret_id)
 224 {
 225   struct IBF_KeyHash hash;
 226   int i;
 227   int buckets[ibf->hash_num];
 228
 229   GNUNET_assert (NULL != ibf);
 230
 231   for (i = 0; i < ibf->size; i++)
 232   {
 233     int j;
 234     int hit;
 235
 236     /* we can only decode from pure buckets */
 237     if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
 238       continue;
 239
 240     hash.key_hash_val = IBF_KEY_HASH_VAL (ibf->key_sum[i]);
 241
 242     /* test if the hash matches the key */
 243     if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
 244       continue;
 245
 246     /* test if key in bucket hits its own location,
 247      * if not, the key hash was subject to collision */
 248     hit = GNUNET_NO;
 249     ibf_get_indices (ibf, ibf->key_sum[i], buckets);
 250     for (j = 0; j < ibf->hash_num; j++)
 251       if (buckets[j] == i)
 252         hit = GNUNET_YES;
 253
 254     if (GNUNET_NO == hit)
 255       continue;
 256
 257     if (NULL != ret_side)
 258       *ret_side = ibf->count[i].count_val;
 259     if (NULL != ret_id)
 260       *ret_id = ibf->key_sum[i];
 261
 262     /* insert on the opposite side, effectively removing the element */
 263     ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
 264
 265     return GNUNET_YES;
 266   }
 267
 268   if (GNUNET_YES == ibf_is_empty (ibf))
 269     return GNUNET_NO;
 270   return GNUNET_SYSERR;
 271 }
 272
 273
 274 /**
 275  * Write buckets from an ibf to a buffer.
 276  * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
 277  *
 278  * @param ibf the ibf to write
 279  * @param start with which bucket to start
 280  * @param count how many buckets to write
 281  * @param buf buffer to write the data to
 282  */
 283 void
 284 ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
 285 {
 286   struct IBF_Key *key_dst;
 287   struct IBF_KeyHash *key_hash_dst;
 288   struct IBF_Count *count_dst;
 289
 290   GNUNET_assert (start + count <= ibf->size);
 291
 292   /* copy keys */
 293   key_dst = (struct IBF_Key *) buf;
 294   GNUNET_memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst);
 295   key_dst += count;
 296   /* copy key hashes */
 297   key_hash_dst = (struct IBF_KeyHash *) key_dst;
 298   GNUNET_memcpy (key_hash_dst, ibf->key_hash_sum + start, count * sizeof *key_hash_dst);
 299   key_hash_dst += count;
 300   /* copy counts */
 301   count_dst = (struct IBF_Count *) key_hash_dst;
 302   GNUNET_memcpy (count_dst, ibf->count + start, count * sizeof *count_dst);
 303 }
 304
 305
 306 /**
 307  * Read buckets from a buffer into an ibf.
 308  *
 309  * @param buf pointer to the buffer to read from
 310  * @param start which bucket to start at
 311  * @param count how many buckets to read
 312  * @param ibf the ibf to read from
 313  */
 314 void
 315 ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
 316 {
 317   struct IBF_Key *key_src;
 318   struct IBF_KeyHash *key_hash_src;
 319   struct IBF_Count *count_src;
 320
 321   GNUNET_assert (count > 0);
 322   GNUNET_assert (start + count <= ibf->size);
 323
 324   /* copy keys */
 325   key_src = (struct IBF_Key *) buf;
 326   GNUNET_memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src);
 327   key_src += count;
 328   /* copy key hashes */
 329   key_hash_src = (struct IBF_KeyHash *) key_src;
 330   GNUNET_memcpy (ibf->key_hash_sum + start, key_hash_src, count * sizeof *key_hash_src);
 331   key_hash_src += count;
 332   /* copy counts */
 333   count_src = (struct IBF_Count *) key_hash_src;
 334   GNUNET_memcpy (ibf->count + start, count_src, count * sizeof *count_src);
 335 }
 336
 337
 338 /**
 339  * Subtract ibf2 from ibf1, storing the result in ibf1.
 340  * The two IBF's must have the same parameters size and hash_num.
 341  *
 342  * @param ibf1 IBF that is subtracted from
 343  * @param ibf2 IBF that will be subtracted from ibf1
 344  */
 345 void
 346 ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
 347 {
 348   int i;
 349
 350   GNUNET_assert (ibf1->size == ibf2->size);
 351   GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
 352
 353   for (i = 0; i < ibf1->size; i++)
 354   {
 355     ibf1->count[i].count_val -= ibf2->count[i].count_val;
 356     ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
 357     ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
 358   }
 359 }
 360
 361
 362 /**
 363  * Create a copy of an IBF, the copy has to be destroyed properly.
 364  *
 365  * @param ibf the IBF to copy
 366  */
 367 struct InvertibleBloomFilter *
 368 ibf_dup (const struct InvertibleBloomFilter *ibf)
 369 {
 370   struct InvertibleBloomFilter *copy;
 371   copy = GNUNET_malloc (sizeof *copy);
 372   copy->hash_num = ibf->hash_num;
 373   copy->size = ibf->size;
 374   copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size * sizeof (struct IBF_KeyHash));
 375   copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof (struct IBF_Key));
 376   copy->count = GNUNET_memdup (ibf->count, ibf->size * sizeof (struct IBF_Count));
 377   return copy;
 378 }
 379
 380
 381 /**
 382  * Destroy all resources associated with the invertible bloom filter.
 383  * No more ibf_*-functions may be called on ibf after calling destroy.
 384  *
 385  * @param ibf the intertible bloom filter to destroy
 386  */
 387 void
 388 ibf_destroy (struct InvertibleBloomFilter *ibf)
 389 {
 390   GNUNET_free (ibf->key_sum);
 391   GNUNET_free (ibf->key_hash_sum);
 392   GNUNET_free (ibf->count);
 393   GNUNET_free (ibf);
 394 }