src/set/ibf.c

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