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