src/consensus/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  * @param salt salt for mingling hashes, different salt may
  67  *        result in less (or more) collisions
  68  * @return the newly created invertible bloom filter
  69  */
  70 struct InvertibleBloomFilter *
  71 ibf_create (uint32_t size, uint8_t hash_num, uint32_t salt)
  72 {
  73   struct InvertibleBloomFilter *ibf;
  74
  75   /* TODO: use malloc_large */
  76
  77   ibf = GNUNET_malloc (sizeof (struct InvertibleBloomFilter));
  78   ibf->count = GNUNET_malloc (size * sizeof (uint8_t));
  79   ibf->key_sum = GNUNET_malloc (size * sizeof (struct GNUNET_HashCode));
  80   ibf->key_hash_sum = GNUNET_malloc (size * sizeof (struct GNUNET_HashCode));
  81   ibf->size = size;
  82   ibf->hash_num = hash_num;
  83
  84   return ibf;
  85 }
  86
  87 /**
  88  * Store unique bucket indices for the specified key in dst.
  89  */
  90 static inline void
  91 ibf_get_indices (const struct InvertibleBloomFilter *ibf,
  92                  struct IBF_Key key, int *dst)
  93 {
  94   struct GNUNET_HashCode bucket_indices;
  95   unsigned int filled;
  96   int i;
  97   GNUNET_CRYPTO_hash (&key, sizeof key, &bucket_indices);
  98   filled = 0;
  99   for (i = 0; filled < ibf->hash_num; i++)
 100   {
 101     unsigned int bucket;
 102     unsigned int j;
 103     if ( (0 != i) && (0 == (i % 16)) )
 104       GNUNET_CRYPTO_hash (&bucket_indices, sizeof (struct GNUNET_HashCode), &bucket_indices);
 105     bucket = bucket_indices.bits[i % 16] % ibf->size;
 106     for (j = 0; j < filled; j++)
 107       if (dst[j] == bucket)
 108         goto try_next;
 109     dst[filled++] = bucket;
 110     try_next: ;
 111   }
 112 }
 113
 114
 115 static void
 116 ibf_insert_into  (struct InvertibleBloomFilter *ibf,
 117                   struct IBF_Key key,
 118                   const int *buckets, int side)
 119 {
 120   int i;
 121   struct GNUNET_HashCode key_hash_sha;
 122   struct IBF_KeyHash key_hash;
 123   GNUNET_CRYPTO_hash (&key, sizeof key, &key_hash_sha);
 124   key_hash.key_hash_val = key_hash_sha.bits[0];
 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 ^= key_hash.key_hash_val;
 131   }
 132 }
 133
 134
 135 /**
 136  * Insert an element into an IBF.
 137  *
 138  * @param ibf the IBF
 139  * @param key the element's hash code
 140  */
 141 void
 142 ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
 143 {
 144   int buckets[ibf->hash_num];
 145   GNUNET_assert (ibf->hash_num <= ibf->size);
 146   ibf_get_indices (ibf, key, buckets);
 147   ibf_insert_into (ibf, key, buckets, 1);
 148 }
 149
 150 /**
 151  * Test is the IBF is empty, i.e. all counts, keys and key hashes are zero.
 152  */
 153 static int
 154 ibf_is_empty (struct InvertibleBloomFilter *ibf)
 155 {
 156   int i;
 157   for (i = 0; i < ibf->size; i++)
 158   {
 159     if (0 != ibf->count[i].count_val)
 160       return GNUNET_NO;
 161     if (0 != ibf->key_hash_sum[i].key_hash_val)
 162       return GNUNET_NO;
 163     if (0 != ibf->key_sum[i].key_val)
 164       return GNUNET_NO;
 165   }
 166   return GNUNET_YES;
 167 }
 168
 169
 170 /**
 171  * Decode and remove an element from the IBF, if possible.
 172  *
 173  * @param ibf the invertible bloom filter to decode
 174  * @param ret_side sign of the cell's count where the decoded element came from.
 175  *                 A negative sign indicates that the element was recovered
 176  *                 resides in an IBF that was previously subtracted from.
 177  * @param ret_id receives the hash code of the decoded element, if successful
 178  * @return GNUNET_YES if decoding an element was successful,
 179  *         GNUNET_NO if the IBF is empty,
 180  *         GNUNET_SYSERR if the decoding has failed
 181  */
 182 int
 183 ibf_decode (struct InvertibleBloomFilter *ibf,
 184             int *ret_side, struct IBF_Key *ret_id)
 185 {
 186   struct IBF_KeyHash hash;
 187   int i;
 188   struct GNUNET_HashCode key_hash_sha;
 189   int buckets[ibf->hash_num];
 190
 191   GNUNET_assert (NULL != ibf);
 192
 193   for (i = 0; i < ibf->size; i++)
 194   {
 195     int j;
 196     int hit;
 197
 198     /* we can only decode from pure buckets */
 199     if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
 200       continue;
 201
 202     GNUNET_CRYPTO_hash (&ibf->key_sum[i], sizeof (struct IBF_Key), &key_hash_sha);
 203     hash.key_hash_val = key_hash_sha.bits[0];
 204
 205     /* test if the hash matches the key */
 206     if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
 207       continue;
 208
 209     /* test if key in bucket hits its own location,
 210      * if not, the key hash was subject to collision */
 211     hit = GNUNET_NO;
 212     ibf_get_indices (ibf, ibf->key_sum[i], buckets);
 213     for (j = 0; j < ibf->hash_num; j++)
 214       if (buckets[j] == i)
 215         hit = GNUNET_YES;
 216
 217     if (GNUNET_NO == hit)
 218       continue;
 219
 220     if (NULL != ret_side)
 221       *ret_side = ibf->count[i].count_val;
 222     if (NULL != ret_id)
 223       *ret_id = ibf->key_sum[i];
 224
 225     /* insert on the opposite side, effectively removing the element */
 226     ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
 227
 228     return GNUNET_YES;
 229   }
 230
 231   if (GNUNET_YES == ibf_is_empty (ibf))
 232     return GNUNET_NO;
 233   return GNUNET_SYSERR;
 234 }
 235
 236
 237 /**
 238  * Write an ibf.
 239  *
 240  * @param ibf the ibf to write
 241  * @param start with which bucket to start
 242  * @param count how many buckets to write
 243  * @param buf buffer to write the data to, will be updated to point to the
 244  *            first byte after the written data
 245  * @param size pointer to the size of the buffer, will be updated, can be NULL
 246  */
 247 void
 248 ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void **buf, size_t *size)
 249 {
 250   struct IBF_Key *key_dst;
 251   struct IBF_KeyHash *key_hash_dst;
 252   struct IBF_Count *count_dst;
 253
 254   /* update size and check for overflow */
 255   if (NULL != size)
 256   {
 257     size_t old_size;
 258     old_size = *size;
 259     *size = *size - count * IBF_BUCKET_SIZE;
 260     GNUNET_assert (*size < old_size);
 261   }
 262   /* copy keys */
 263   key_dst = (struct IBF_Key *) *buf;
 264   memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst);
 265   key_dst += count;
 266   /* copy key hashes */
 267   key_hash_dst = (struct IBF_KeyHash *) key_dst;
 268   memcpy (key_hash_dst, ibf->key_hash_sum + start, count * sizeof *key_hash_dst);
 269   key_hash_dst += count;
 270   /* copy counts */
 271   count_dst = (struct IBF_Count *) key_hash_dst;
 272   memcpy (count_dst, ibf->count + start, count * sizeof *count_dst);
 273   count_dst += count;
 274   /* returned buffer is at the end of written data*/
 275   *buf = (void *) count_dst;
 276 }
 277
 278
 279 /**
 280  * Read an ibf.
 281  *
 282  * @param buf pointer to the buffer to write to, will point to first
 283  *            byte after the written data // FIXME: take 'const void *buf' for input, return number of bytes READ
 284  * @param size size of the buffer, will be updated
 285  * @param start which bucket to start at
 286  * @param count how many buckets to read
 287  * @param ibf the ibf to read from
 288  * @return GNUNET_OK on success // FIXME: return 0 on error (or -1/ssize_t), number of bytes read otherwise
 289  */
 290 int
 291 ibf_read_slice (void **buf, size_t *size, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
 292 {
 293   struct IBF_Key *key_src;
 294   struct IBF_KeyHash *key_hash_src;
 295   struct IBF_Count *count_src;
 296
 297   /* update size and check for overflow */
 298   if (NULL != size)
 299   {
 300     size_t old_size;
 301     old_size = *size;
 302     *size = *size - count * IBF_BUCKET_SIZE;
 303     if (*size > old_size)
 304       return GNUNET_SYSERR;
 305   }
 306   /* copy keys */
 307   key_src = (struct IBF_Key *) *buf;
 308   memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src);
 309   key_src += count;
 310   /* copy key hashes */
 311   key_hash_src = (struct IBF_KeyHash *) key_src;
 312   memcpy (ibf->key_hash_sum + start, key_hash_src, count * sizeof *key_hash_src);
 313   key_hash_src += count;
 314   /* copy counts */
 315   count_src = (struct IBF_Count *) key_hash_src;
 316   memcpy (ibf->count + start, count_src, count * sizeof *count_src);
 317   count_src += count;
 318   /* returned buffer is at the end of written data*/
 319   *buf = (void *) count_src;
 320   return GNUNET_OK;
 321 }
 322
 323
 324 /**
 325  * Write an ibf.
 326  *
 327  * @param ibf the ibf to write
 328  * @param buf buffer to write the data to, will be updated to point to the
 329  *            first byte after the written data
 330  * @param size pointer to the size of the buffer, will be updated, can be NULL
 331  */
 332 void
 333 ibf_write (const struct InvertibleBloomFilter *ibf, void **buf, size_t *size)
 334 {
 335   ibf_write_slice (ibf, 0, ibf->size, buf, size);
 336 }
 337
 338
 339 /**
 340  * Read an ibf.
 341  *
 342  * @param buf pointer to the buffer to write to, will point to first
 343  *            byte after the written data
 344  * @param size size of the buffer, will be updated
 345  * @param dst ibf to write buckets to
 346  * @return GNUNET_OK on success
 347  */
 348 int
 349 ibf_read (void **buf, size_t *size, struct InvertibleBloomFilter *dst)
 350 {
 351   return ibf_read_slice (buf, size, 0, dst->size, dst);
 352 }
 353
 354
 355 /**
 356  * Subtract ibf2 from ibf1, storing the result in ibf1.
 357  * The two IBF's must have the same parameters size and hash_num.
 358  *
 359  * @param ibf1 IBF that is subtracted from
 360  * @param ibf2 IBF that will be subtracted from ibf1
 361  */
 362 void
 363 ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
 364 {
 365   int i;
 366
 367   GNUNET_assert (ibf1->size == ibf2->size);
 368   GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
 369   GNUNET_assert (ibf1->salt == ibf2->salt);
 370
 371   for (i = 0; i < ibf1->size; i++)
 372   {
 373     ibf1->count[i].count_val -= ibf2->count[i].count_val;
 374     ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
 375     ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
 376   }
 377 }
 378
 379
 380 /**
 381  * Create a copy of an IBF, the copy has to be destroyed properly.
 382  *
 383  * @param ibf the IBF to copy
 384  */
 385 struct InvertibleBloomFilter *
 386 ibf_dup (const struct InvertibleBloomFilter *ibf)
 387 {
 388   struct InvertibleBloomFilter *copy;
 389   copy = GNUNET_malloc (sizeof *copy);
 390   copy->hash_num = ibf->hash_num;
 391   copy->salt = ibf->salt;
 392   copy->size = ibf->size;
 393   copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size * sizeof (struct IBF_KeyHash));
 394   copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof (struct IBF_Key));
 395   copy->count = GNUNET_memdup (ibf->count, ibf->size * sizeof (struct IBF_Count));
 396   return copy;
 397 }
 398
 399
 400 /**
 401  * Destroy all resources associated with the invertible bloom filter.
 402  * No more ibf_*-functions may be called on ibf after calling destroy.
 403  *
 404  * @param ibf the intertible bloom filter to destroy
 405  */
 406 void
 407 ibf_destroy (struct InvertibleBloomFilter *ibf)
 408 {
 409   GNUNET_free (ibf->key_sum);
 410   GNUNET_free (ibf->key_hash_sum);
 411   GNUNET_free (ibf->count);
 412   GNUNET_free (ibf);
 413 }
 414