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 #include "ibf.h"
  29
  30 struct InvertibleBloomFilter
  31 {
  32   /**
  33    * How many cells does this IBF have?
  34    */
  35   unsigned int size;
  36
  37   /**
  38    * In how many cells do we hash one element?
  39    * Usually 4 or 3.
  40    */
  41   unsigned int hash_num;
  42
  43   /**
  44    * Salt for mingling hashes
  45    */
  46   uint32_t salt;
  47
  48   /**
  49    * How many times has a bucket been hit?
  50    * Can be negative, as a result of IBF subtraction.
  51    */
  52   int8_t *count;
  53
  54   /**
  55    * xor sums of the elements' hash codes, used to identify the elements.
  56    */
  57   struct GNUNET_HashCode *id_sum;
  58
  59   /**
  60    * xor sums of the "hash of the hash".
  61    */
  62   struct GNUNET_HashCode *hash_sum;
  63
  64 };
  65
  66
  67 /**
  68  * Create an invertible bloom filter.
  69  */
  70 struct InvertibleBloomFilter *
  71 ibf_create (unsigned int size, unsigned int hash_num, uint32_t salt)
  72 {
  73   struct InvertibleBloomFilter *ibf;
  74
  75   ibf = GNUNET_malloc (sizeof (struct InvertibleBloomFilter));
  76   ibf->count = GNUNET_malloc (size * sizeof (uint8_t));
  77   ibf->id_sum = GNUNET_malloc (size * sizeof (struct GNUNET_HashCode));
  78   ibf->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
  87 /**
  88  * Insert an element into an IBF.
  89  */
  90 void
  91 ibf_insert_on_side (struct InvertibleBloomFilter *ibf,
  92                     const struct GNUNET_HashCode *key,
  93                     int side)
  94 {
  95   struct GNUNET_HashCode bucket_indices;
  96   struct GNUNET_HashCode remove_key;
  97   struct GNUNET_HashCode key_hash;
  98   int i;
  99
 100   /* copy the key, if key and an entry in the IBF alias */
 101   remove_key = *key;
 102
 103   GNUNET_assert ((1 == side) || (-1 == side));
 104
 105   bucket_indices = remove_key;
 106   GNUNET_CRYPTO_hash (key, sizeof (struct GNUNET_HashCode), &key_hash);
 107
 108   for (i = 0; i < ibf->hash_num; i++)
 109   {
 110     unsigned int bucket;
 111     if ((i % 16) == 0)
 112       GNUNET_CRYPTO_hash (&bucket_indices, sizeof (struct GNUNET_HashCode),
 113                           &bucket_indices);
 114
 115     bucket = bucket_indices.bits[i%16] % ibf->size;
 116
 117     printf ("inserting %s in bucket %u side %d\n",
 118             GNUNET_h2s (&remove_key), bucket, side);
 119
 120     ibf->count[bucket] += side;
 121
 122     GNUNET_CRYPTO_hash_xor (&remove_key, &ibf->id_sum[bucket],
 123                             &ibf->id_sum[bucket]);
 124     GNUNET_CRYPTO_hash_xor (&key_hash, &ibf->hash_sum[bucket],
 125                             &ibf->hash_sum[bucket]);
 126   }
 127 }
 128
 129 /**
 130  * Insert an element into an IBF.
 131  */
 132 void
 133 ibf_insert (struct InvertibleBloomFilter *ibf, const struct GNUNET_HashCode *key)
 134 {
 135   ibf_insert_on_side (ibf, key, 1);
 136 }
 137
 138 static int
 139 ibf_is_empty (struct InvertibleBloomFilter *ibf)
 140 {
 141   int i;
 142   for (i = 0; i < ibf->size; i++)
 143   {
 144     int j;
 145     if (0 != ibf->count[i])
 146       return GNUNET_NO;
 147     for (j = 0; j < 16; ++j)
 148     {
 149       if (0 != ibf->hash_sum[i].bits[j])
 150         return GNUNET_NO;
 151       if (0 != ibf->id_sum[i].bits[j])
 152         return GNUNET_NO;
 153     }
 154   }
 155   return GNUNET_YES;
 156 }
 157
 158
 159 /**
 160  * Decode and remove an element from the IBF, if possible.
 161  *
 162  * @param ibf the invertible bloom filter to decode
 163  * @param ret_id the hash code of the decoded element, if successful
 164  * @param side sign of the cell's count where the decoded element came from.
 165  *             A negative sign indicates that the element was recovered
 166  *             resides in an IBF that was previously subtracted from.
 167  * @return GNUNET_YES if decoding an element was successful,
 168  *         GNUNET_NO if the IBF is empty,
 169  *         GNUNET_SYSERR if the decoding has failed
 170  */
 171 int
 172 ibf_decode (struct InvertibleBloomFilter *ibf,
 173             int *ret_side, struct GNUNET_HashCode *ret_id)
 174 {
 175   struct GNUNET_HashCode hash;
 176   int i;
 177
 178   GNUNET_assert (NULL != ibf);
 179   GNUNET_assert (NULL != ret_id);
 180   GNUNET_assert (NULL != ret_side);
 181
 182   for (i = 0; i < ibf->size; i++)
 183   {
 184     if ((1 != ibf->count[i]) && (-1 != ibf->count[i]))
 185       continue;
 186
 187     GNUNET_CRYPTO_hash (&ibf->id_sum[i], sizeof (struct GNUNET_HashCode), &hash);
 188
 189     if (0 != memcmp (&hash, &ibf->hash_sum[i], sizeof (struct GNUNET_HashCode)))
 190       continue;
 191
 192     printf ("%d pure\n", i);
 193     printf ("%d count\n", ibf->count[i]);
 194
 195     *ret_side = ibf->count[i];
 196     *ret_id = ibf->id_sum[i];
 197
 198     /* insert on the opposite side, effectively removing the element */
 199     ibf_insert_on_side (ibf, &ibf->id_sum[i], -ibf->count[i]);
 200
 201     return GNUNET_YES;
 202   }
 203
 204   if (GNUNET_YES == ibf_is_empty (ibf))
 205     return GNUNET_NO;
 206   return GNUNET_SYSERR;
 207 }
 208
 209
 210
 211 /**
 212  * Subtract ibf2 from ibf1, storing the result in ibf1.
 213  * The two IBF's must have the same parameters size and hash_num.
 214  *
 215  * @return a newly allocated invertible bloom filter
 216  */
 217 void
 218 ibf_subtract (struct InvertibleBloomFilter *ibf1, struct InvertibleBloomFilter *ibf2)
 219 {
 220   int i;
 221
 222   GNUNET_assert (ibf1->size == ibf2->size);
 223   GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
 224   GNUNET_assert (ibf1->salt == ibf2->salt);
 225
 226   for (i = 0; i < ibf1->size; i++)
 227   {
 228     printf ("ibf1->count[%d]=%d, ibf2->count[%d]=%d\n", i, ibf1->count[i], i,
 229         ibf2->count[i]);
 230     ibf1->count[i] -= ibf2->count[i];
 231     printf("diff: %d\n", ibf1->count[i]);
 232     GNUNET_CRYPTO_hash_xor (&ibf1->id_sum[i], &ibf2->id_sum[i],
 233                             &ibf1->id_sum[i]);
 234     GNUNET_CRYPTO_hash_xor (&ibf1->hash_sum[i], &ibf2->hash_sum[i],
 235                             &ibf1->hash_sum[i]);
 236   }
 237 }
 238