2 This file is part of GNUnet
3 Copyright (C) 2012 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
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 Affero General Public License for more details.
18 * @brief implementation of the invertible bloom filter
19 * @author Florian Dold
25 * Compute the key's hash from the key.
26 * Redefine to use a different hash function.
28 #define IBF_KEY_HASH_VAL(k) (GNUNET_CRYPTO_crc32_n (&(k), sizeof (struct IBF_KeyHash)))
31 * Create a key from a hashcode.
33 * @param hash the hashcode
37 ibf_key_from_hashcode (const struct GNUNET_HashCode *hash)
39 return *(struct IBF_Key *) hash;
43 * Create a hashcode from a key, by replicating the key
44 * until the hascode is filled
47 * @param dst hashcode to store the result in
50 ibf_hashcode_from_key (struct IBF_Key key,
51 struct GNUNET_HashCode *dst)
55 const unsigned int keys_per_hashcode = sizeof (struct GNUNET_HashCode) / sizeof (struct IBF_Key);
57 p = (struct IBF_Key *) dst;
58 for (i = 0; i < keys_per_hashcode; i++)
64 * Create an invertible bloom filter.
66 * @param size number of IBF buckets
67 * @param hash_num number of buckets one element is hashed in
68 * @return the newly created invertible bloom filter, NULL on error
70 struct InvertibleBloomFilter *
71 ibf_create (uint32_t size, uint8_t hash_num)
73 struct InvertibleBloomFilter *ibf;
75 GNUNET_assert (0 != size);
77 ibf = GNUNET_new (struct InvertibleBloomFilter);
78 ibf->count = GNUNET_malloc_large (size * sizeof (uint8_t));
79 if (NULL == ibf->count)
84 ibf->key_sum = GNUNET_malloc_large (size * sizeof (struct IBF_Key));
85 if (NULL == ibf->key_sum)
87 GNUNET_free (ibf->count);
91 ibf->key_hash_sum = GNUNET_malloc_large (size * sizeof (struct IBF_KeyHash));
92 if (NULL == ibf->key_hash_sum)
94 GNUNET_free (ibf->key_sum);
95 GNUNET_free (ibf->count);
100 ibf->hash_num = hash_num;
107 * Store unique bucket indices for the specified key in dst.
110 ibf_get_indices (const struct InvertibleBloomFilter *ibf,
118 bucket = GNUNET_CRYPTO_crc32_n (&key, sizeof key);
119 for (i = 0, filled=0; filled < ibf->hash_num; i++)
123 for (j = 0; j < filled; j++)
124 if (dst[j] == bucket)
126 dst[filled++] = bucket % ibf->size;
128 x = ((uint64_t) bucket << 32) | i;
129 bucket = GNUNET_CRYPTO_crc32_n (&x, sizeof x);
135 ibf_insert_into (struct InvertibleBloomFilter *ibf,
137 const int *buckets, int side)
141 for (i = 0; i < ibf->hash_num; i++)
143 const int bucket = buckets[i];
144 ibf->count[bucket].count_val += side;
145 ibf->key_sum[bucket].key_val ^= key.key_val;
146 ibf->key_hash_sum[bucket].key_hash_val
147 ^= IBF_KEY_HASH_VAL (key);
153 * Insert a key into an IBF.
156 * @param key the element's hash code
159 ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
161 int buckets[ibf->hash_num];
162 GNUNET_assert (ibf->hash_num <= ibf->size);
163 ibf_get_indices (ibf, key, buckets);
164 ibf_insert_into (ibf, key, buckets, 1);
169 * Remove a key from an IBF.
172 * @param key the element's hash code
175 ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
177 int buckets[ibf->hash_num];
178 GNUNET_assert (ibf->hash_num <= ibf->size);
179 ibf_get_indices (ibf, key, buckets);
180 ibf_insert_into (ibf, key, buckets, -1);
185 * Test is the IBF is empty, i.e. all counts, keys and key hashes are zero.
188 ibf_is_empty (struct InvertibleBloomFilter *ibf)
191 for (i = 0; i < ibf->size; i++)
193 if (0 != ibf->count[i].count_val)
195 if (0 != ibf->key_hash_sum[i].key_hash_val)
197 if (0 != ibf->key_sum[i].key_val)
205 * Decode and remove an element from the IBF, if possible.
207 * @param ibf the invertible bloom filter to decode
208 * @param ret_side sign of the cell's count where the decoded element came from.
209 * A negative sign indicates that the element was recovered
210 * resides in an IBF that was previously subtracted from.
211 * @param ret_id receives the hash code of the decoded element, if successful
212 * @return GNUNET_YES if decoding an element was successful,
213 * GNUNET_NO if the IBF is empty,
214 * GNUNET_SYSERR if the decoding has failed
217 ibf_decode (struct InvertibleBloomFilter *ibf,
218 int *ret_side, struct IBF_Key *ret_id)
220 struct IBF_KeyHash hash;
222 int buckets[ibf->hash_num];
224 GNUNET_assert (NULL != ibf);
226 for (i = 0; i < ibf->size; i++)
231 /* we can only decode from pure buckets */
232 if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
235 hash.key_hash_val = IBF_KEY_HASH_VAL (ibf->key_sum[i]);
237 /* test if the hash matches the key */
238 if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
241 /* test if key in bucket hits its own location,
242 * if not, the key hash was subject to collision */
244 ibf_get_indices (ibf, ibf->key_sum[i], buckets);
245 for (j = 0; j < ibf->hash_num; j++)
249 if (GNUNET_NO == hit)
252 if (NULL != ret_side)
253 *ret_side = ibf->count[i].count_val;
255 *ret_id = ibf->key_sum[i];
257 /* insert on the opposite side, effectively removing the element */
258 ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
263 if (GNUNET_YES == ibf_is_empty (ibf))
265 return GNUNET_SYSERR;
270 * Write buckets from an ibf to a buffer.
271 * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
273 * @param ibf the ibf to write
274 * @param start with which bucket to start
275 * @param count how many buckets to write
276 * @param buf buffer to write the data to
279 ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
281 struct IBF_Key *key_dst;
282 struct IBF_KeyHash *key_hash_dst;
283 struct IBF_Count *count_dst;
285 GNUNET_assert (start + count <= ibf->size);
288 key_dst = (struct IBF_Key *) buf;
289 GNUNET_memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst);
291 /* copy key hashes */
292 key_hash_dst = (struct IBF_KeyHash *) key_dst;
293 GNUNET_memcpy (key_hash_dst, ibf->key_hash_sum + start, count * sizeof *key_hash_dst);
294 key_hash_dst += count;
296 count_dst = (struct IBF_Count *) key_hash_dst;
297 GNUNET_memcpy (count_dst, ibf->count + start, count * sizeof *count_dst);
302 * Read buckets from a buffer into an ibf.
304 * @param buf pointer to the buffer to read from
305 * @param start which bucket to start at
306 * @param count how many buckets to read
307 * @param ibf the ibf to read from
310 ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
312 struct IBF_Key *key_src;
313 struct IBF_KeyHash *key_hash_src;
314 struct IBF_Count *count_src;
316 GNUNET_assert (count > 0);
317 GNUNET_assert (start + count <= ibf->size);
320 key_src = (struct IBF_Key *) buf;
321 GNUNET_memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src);
323 /* copy key hashes */
324 key_hash_src = (struct IBF_KeyHash *) key_src;
325 GNUNET_memcpy (ibf->key_hash_sum + start, key_hash_src, count * sizeof *key_hash_src);
326 key_hash_src += count;
328 count_src = (struct IBF_Count *) key_hash_src;
329 GNUNET_memcpy (ibf->count + start, count_src, count * sizeof *count_src);
334 * Subtract ibf2 from ibf1, storing the result in ibf1.
335 * The two IBF's must have the same parameters size and hash_num.
337 * @param ibf1 IBF that is subtracted from
338 * @param ibf2 IBF that will be subtracted from ibf1
341 ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
345 GNUNET_assert (ibf1->size == ibf2->size);
346 GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
348 for (i = 0; i < ibf1->size; i++)
350 ibf1->count[i].count_val -= ibf2->count[i].count_val;
351 ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
352 ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
358 * Create a copy of an IBF, the copy has to be destroyed properly.
360 * @param ibf the IBF to copy
362 struct InvertibleBloomFilter *
363 ibf_dup (const struct InvertibleBloomFilter *ibf)
365 struct InvertibleBloomFilter *copy;
366 copy = GNUNET_malloc (sizeof *copy);
367 copy->hash_num = ibf->hash_num;
368 copy->size = ibf->size;
369 copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size * sizeof (struct IBF_KeyHash));
370 copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof (struct IBF_Key));
371 copy->count = GNUNET_memdup (ibf->count, ibf->size * sizeof (struct IBF_Count));
377 * Destroy all resources associated with the invertible bloom filter.
378 * No more ibf_*-functions may be called on ibf after calling destroy.
380 * @param ibf the intertible bloom filter to destroy
383 ibf_destroy (struct InvertibleBloomFilter *ibf)
385 GNUNET_free (ibf->key_sum);
386 GNUNET_free (ibf->key_hash_sum);
387 GNUNET_free (ibf->count);