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