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 /**
  23  * @file consensus/ibf.c
  24  * @brief implementation of the invertible bloom filter
  25  * @author Florian Dold
  26  */
  27
  28
  29 #include "ibf.h"
  30
  31
  32 /**
  33  * Create a key from a hashcode.
  34  *
  35  * @param hash the hashcode
  36  * @return a key
  37  */
  38 uint64_t
  39 ibf_key_from_hashcode (const struct GNUNET_HashCode *hash)
  40 {
  41   return GNUNET_ntohll (*(uint64_t *) hash);
  42 }
  43
  44
  45 /**
  46  * Create a hashcode from a key, by replicating the key
  47  * until the hascode is filled
  48  *
  49  * @param key the key
  50  * @param dst hashcode to store the result in
  51  */
  52 void
  53 ibf_hashcode_from_key (uint64_t key, struct GNUNET_HashCode *dst)
  54 {
  55   uint64_t *p;
  56   int i;
  57   p = (uint64_t *) dst;
  58   for (i = 0; i < 8; 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  * @param salt salt for mingling hashes, different salt may
  69  *        result in less (or more) collisions
  70  * @return the newly created invertible bloom filter
  71  */
  72 struct InvertibleBloomFilter *
  73 ibf_create (uint32_t size, unsigned int hash_num, uint32_t salt)
  74 {
  75   struct InvertibleBloomFilter *ibf;
  76
  77   ibf = GNUNET_malloc (sizeof (struct InvertibleBloomFilter));
  78   ibf->count = GNUNET_malloc (size * sizeof (uint8_t));
  79   ibf->id_sum = GNUNET_malloc (size * sizeof (struct GNUNET_HashCode));
  80   ibf->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                  uint64_t key, int *dst)
  93 {
  94   struct GNUNET_HashCode bucket_indices;
  95   unsigned int filled = 0;
  96   int i;
  97   GNUNET_CRYPTO_hash (&key, sizeof key, &bucket_indices);
  98   for (i = 0; filled < ibf->hash_num; i++)
  99   {
 100     unsigned int bucket;
 101     unsigned int j;
 102     if ( (0 != i) && (0 == (i % 16)) )
 103       GNUNET_CRYPTO_hash (&bucket_indices, sizeof (struct GNUNET_HashCode), &bucket_indices);
 104     bucket = bucket_indices.bits[i] % ibf->size;
 105     for (j = 0; j < filled; j++)
 106       if (dst[j] == bucket)
 107         goto try_next;;
 108     dst[filled++] = bucket;
 109     try_next: ;
 110   }
 111 }
 112
 113
 114 static void
 115 ibf_insert_into  (struct InvertibleBloomFilter *ibf,
 116                   uint64_t key,
 117                   const int *buckets, int side)
 118 {
 119   int i;
 120   struct GNUNET_HashCode key_hash_sha;
 121   uint32_t key_hash;
 122   GNUNET_CRYPTO_hash (&key, sizeof key, &key_hash_sha);
 123   key_hash = key_hash_sha.bits[0];
 124   for (i = 0; i < ibf->hash_num; i++)
 125   {
 126     const int bucket = buckets[i];
 127     ibf->count[bucket] += side;
 128     ibf->id_sum[bucket] ^= key;
 129     ibf->hash_sum[bucket] ^= key_hash;
 130   }
 131 }
 132
 133
 134 /**
 135  * Insert an element into an IBF.
 136  *
 137  * @param ibf the IBF
 138  * @param id the element's hash code
 139  */
 140 void
 141 ibf_insert (struct InvertibleBloomFilter *ibf, uint64_t key)
 142 {
 143   int buckets[ibf->hash_num];
 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])
 158       return GNUNET_NO;
 159     if (0 != ibf->hash_sum[i])
 160       return GNUNET_NO;
 161     if (0 != ibf->id_sum[i])
 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 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 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, uint64_t *ret_id)
 183 {
 184   uint32_t 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]) && (-1 != ibf->count[i]))
 198       continue;
 199
 200     GNUNET_CRYPTO_hash (&ibf->id_sum[i], sizeof (uint64_t), &key_hash_sha);
 201     hash = key_hash_sha.bits[0];
 202
 203     /* test if the hash matches the key */
 204     if (hash != ibf->hash_sum[i])
 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->id_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];
 220     if (NULL != ret_id)
 221       *ret_id = ibf->id_sum[i];
 222
 223     /* insert on the opposite side, effectively removing the element */
 224     ibf_insert_into (ibf, ibf->id_sum[i], buckets, -ibf->count[i]);
 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  * Subtract ibf2 from ibf1, storing the result in ibf1.
 237  * The two IBF's must have the same parameters size and hash_num.
 238  *
 239  * @param ibf1 IBF that is subtracted from
 240  * @param ibf2 IBF that will be subtracted from ibf1
 241  */
 242 void
 243 ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
 244 {
 245   int i;
 246
 247   GNUNET_assert (ibf1->size == ibf2->size);
 248   GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
 249   GNUNET_assert (ibf1->salt == ibf2->salt);
 250
 251   for (i = 0; i < ibf1->size; i++)
 252   {
 253     ibf1->count[i] -= ibf2->count[i];
 254     ibf1->hash_sum[i] ^= ibf2->hash_sum[i];
 255     ibf1->id_sum[i] ^= ibf2->id_sum[i];
 256   }
 257 }
 258
 259 /**
 260  * Create a copy of an IBF, the copy has to be destroyed properly.
 261  *
 262  * @param ibf the IBF to copy
 263  */
 264 struct InvertibleBloomFilter *
 265 ibf_dup (struct InvertibleBloomFilter *ibf)
 266 {
 267   struct InvertibleBloomFilter *copy;
 268   copy = GNUNET_malloc (sizeof *copy);
 269   copy->hash_num = ibf->hash_num;
 270   copy->salt = ibf->salt;
 271   copy->size = ibf->size;
 272   copy->hash_sum = GNUNET_memdup (ibf->hash_sum, ibf->size * sizeof (struct GNUNET_HashCode));
 273   copy->id_sum = GNUNET_memdup (ibf->id_sum, ibf->size * sizeof (struct GNUNET_HashCode));
 274   copy->count = GNUNET_memdup (ibf->count, ibf->size * sizeof (uint8_t));
 275   return copy;
 276 }
 277
 278 /**
 279  * Destroy all resources associated with the invertible bloom filter.
 280  * No more ibf_*-functions may be called on ibf after calling destroy.
 281  *
 282  * @param ibf the intertible bloom filter to destroy
 283  */
 284 void
 285 ibf_destroy (struct InvertibleBloomFilter *ibf)
 286 {
 287   GNUNET_free (ibf->hash_sum);
 288   GNUNET_free (ibf->id_sum);
 289   GNUNET_free (ibf->count);
 290   GNUNET_free (ibf);
 291 }