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