aboutsummaryrefslogtreecommitdiff
path: root/src/setu/ibf.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/setu/ibf.c')
-rw-r--r--src/setu/ibf.c294
1 files changed, 239 insertions, 55 deletions
diff --git a/src/setu/ibf.c b/src/setu/ibf.c
index 1beba9065..8f29adb62 100644
--- a/src/setu/ibf.c
+++ b/src/setu/ibf.c
@@ -20,11 +20,15 @@
20 20
21/** 21/**
22 * @file set/ibf.c 22 * @file set/ibf.c
23 * @brief implementation of the invertible Bloom filter 23 * @brief implementation of the invertible bloom filter
24 * @author Florian Dold 24 * @author Florian Dold
25 * @author Elias Summermatter
25 */ 26 */
26 27
27#include "ibf.h" 28#include "ibf.h"
29#include "gnunet_util_lib.h"
30#define LOG(kind, ...) GNUNET_log_from (kind, "setu", __VA_ARGS__)
31
28 32
29/** 33/**
30 * Compute the key's hash from the key. 34 * Compute the key's hash from the key.
@@ -58,11 +62,12 @@ ibf_hashcode_from_key (struct IBF_Key key,
58 struct GNUNET_HashCode *dst) 62 struct GNUNET_HashCode *dst)
59{ 63{
60 struct IBF_Key *p; 64 struct IBF_Key *p;
65 unsigned int i;
61 const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode) 66 const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode)
62 / sizeof(struct IBF_Key); 67 / sizeof(struct IBF_Key);
63 68
64 p = (struct IBF_Key *) dst; 69 p = (struct IBF_Key *) dst;
65 for (unsigned int i = 0; i < keys_per_hashcode; i++) 70 for (i = 0; i < keys_per_hashcode; i++)
66 *p++ = key; 71 *p++ = key;
67} 72}
68 73
@@ -75,14 +80,14 @@ ibf_hashcode_from_key (struct IBF_Key key,
75 * @return the newly created invertible bloom filter, NULL on error 80 * @return the newly created invertible bloom filter, NULL on error
76 */ 81 */
77struct InvertibleBloomFilter * 82struct InvertibleBloomFilter *
78ibf_create (uint32_t size, 83ibf_create (uint32_t size, uint8_t hash_num)
79 uint8_t hash_num)
80{ 84{
81 struct InvertibleBloomFilter *ibf; 85 struct InvertibleBloomFilter *ibf;
82 86
83 GNUNET_assert (0 != size); 87 GNUNET_assert (0 != size);
88
84 ibf = GNUNET_new (struct InvertibleBloomFilter); 89 ibf = GNUNET_new (struct InvertibleBloomFilter);
85 ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t)); 90 ibf->count = GNUNET_malloc_large (size * sizeof(uint64_t));
86 if (NULL == ibf->count) 91 if (NULL == ibf->count)
87 { 92 {
88 GNUNET_free (ibf); 93 GNUNET_free (ibf);
@@ -105,6 +110,7 @@ ibf_create (uint32_t size,
105 } 110 }
106 ibf->size = size; 111 ibf->size = size;
107 ibf->hash_num = hash_num; 112 ibf->hash_num = hash_num;
113
108 return ibf; 114 return ibf;
109} 115}
110 116
@@ -121,8 +127,7 @@ ibf_get_indices (const struct InvertibleBloomFilter *ibf,
121 uint32_t i; 127 uint32_t i;
122 uint32_t bucket; 128 uint32_t bucket;
123 129
124 bucket = GNUNET_CRYPTO_crc32_n (&key, 130 bucket = GNUNET_CRYPTO_crc32_n (&key, sizeof key);
125 sizeof (key));
126 for (i = 0, filled = 0; filled < ibf->hash_num; i++) 131 for (i = 0, filled = 0; filled < ibf->hash_num; i++)
127 { 132 {
128 uint64_t x; 133 uint64_t x;
@@ -133,8 +138,7 @@ ibf_get_indices (const struct InvertibleBloomFilter *ibf,
133 dst[filled++] = bucket % ibf->size; 138 dst[filled++] = bucket % ibf->size;
134try_next: 139try_next:
135 x = ((uint64_t) bucket << 32) | i; 140 x = ((uint64_t) bucket << 32) | i;
136 bucket = GNUNET_CRYPTO_crc32_n (&x, 141 bucket = GNUNET_CRYPTO_crc32_n (&x, sizeof x);
137 sizeof (x));
138 } 142 }
139} 143}
140 144
@@ -170,13 +174,8 @@ ibf_insert (struct InvertibleBloomFilter *ibf,
170 int buckets[ibf->hash_num]; 174 int buckets[ibf->hash_num];
171 175
172 GNUNET_assert (ibf->hash_num <= ibf->size); 176 GNUNET_assert (ibf->hash_num <= ibf->size);
173 ibf_get_indices (ibf, 177 ibf_get_indices (ibf, key, buckets);
174 key, 178 ibf_insert_into (ibf, key, buckets, 1);
175 buckets);
176 ibf_insert_into (ibf,
177 key,
178 buckets,
179 1);
180} 179}
181 180
182 181
@@ -193,13 +192,8 @@ ibf_remove (struct InvertibleBloomFilter *ibf,
193 int buckets[ibf->hash_num]; 192 int buckets[ibf->hash_num];
194 193
195 GNUNET_assert (ibf->hash_num <= ibf->size); 194 GNUNET_assert (ibf->hash_num <= ibf->size);
196 ibf_get_indices (ibf, 195 ibf_get_indices (ibf, key, buckets);
197 key, 196 ibf_insert_into (ibf, key, buckets, -1);
198 buckets);
199 ibf_insert_into (ibf,
200 key,
201 buckets,
202 -1);
203} 197}
204 198
205 199
@@ -244,6 +238,8 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
244 238
245 for (uint32_t i = 0; i < ibf->size; i++) 239 for (uint32_t i = 0; i < ibf->size; i++)
246 { 240 {
241 int hit;
242
247 /* we can only decode from pure buckets */ 243 /* we can only decode from pure buckets */
248 if ( (1 != ibf->count[i].count_val) && 244 if ( (1 != ibf->count[i].count_val) &&
249 (-1 != ibf->count[i].count_val) ) 245 (-1 != ibf->count[i].count_val) )
@@ -257,30 +253,33 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
257 253
258 /* test if key in bucket hits its own location, 254 /* test if key in bucket hits its own location,
259 * if not, the key hash was subject to collision */ 255 * if not, the key hash was subject to collision */
260 { 256 hit = GNUNET_NO;
261 bool hit = false; 257 ibf_get_indices (ibf, ibf->key_sum[i], buckets);
258 for (int j = 0; j < ibf->hash_num; j++)
259 if (buckets[j] == i)
260 hit = GNUNET_YES;
262 261
263 ibf_get_indices (ibf, 262 if (GNUNET_NO == hit)
264 ibf->key_sum[i], 263 continue;
265 buckets); 264
266 for (int j = 0; j < ibf->hash_num; j++) 265 if (1 == ibf->count[i].count_val)
267 if (buckets[j] == i) 266 {
268 { 267 ibf->remote_decoded_count++;
269 hit = true;
270 break;
271 }
272 if (! hit)
273 continue;
274 } 268 }
269 else
270 {
271 ibf->local_decoded_count++;
272 }
273
274
275 if (NULL != ret_side) 275 if (NULL != ret_side)
276 *ret_side = ibf->count[i].count_val; 276 *ret_side = ibf->count[i].count_val;
277 if (NULL != ret_id) 277 if (NULL != ret_id)
278 *ret_id = ibf->key_sum[i]; 278 *ret_id = ibf->key_sum[i];
279 279
280 /* insert on the opposite side, effectively removing the element */ 280 /* insert on the opposite side, effectively removing the element */
281 ibf_insert_into (ibf, 281 ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
282 ibf->key_sum[i], buckets, 282
283 -ibf->count[i].count_val);
284 return GNUNET_YES; 283 return GNUNET_YES;
285 } 284 }
286 285
@@ -291,6 +290,26 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
291 290
292 291
293/** 292/**
293 * Returns the minimal bytes needed to store the counter of the IBF
294 *
295 * @param ibf the IBF
296 */
297uint8_t
298ibf_get_max_counter (struct InvertibleBloomFilter *ibf)
299{
300 long long max_counter = 0;
301 for (uint64_t i = 0; i < ibf->size; i++)
302 {
303 if (ibf->count[i].count_val > max_counter)
304 {
305 max_counter = ibf->count[i].count_val;
306 }
307 }
308 return 64 - __builtin_clzll (max_counter);
309}
310
311
312/**
294 * Write buckets from an ibf to a buffer. 313 * Write buckets from an ibf to a buffer.
295 * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf. 314 * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
296 * 315 *
@@ -298,16 +317,17 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
298 * @param start with which bucket to start 317 * @param start with which bucket to start
299 * @param count how many buckets to write 318 * @param count how many buckets to write
300 * @param buf buffer to write the data to 319 * @param buf buffer to write the data to
320 * @param max bit length of a counter for unpacking
301 */ 321 */
302void 322void
303ibf_write_slice (const struct InvertibleBloomFilter *ibf, 323ibf_write_slice (const struct InvertibleBloomFilter *ibf,
304 uint32_t start, 324 uint32_t start,
305 uint32_t count, 325 uint64_t count,
306 void *buf) 326 void *buf,
327 uint8_t counter_max_length)
307{ 328{
308 struct IBF_Key *key_dst; 329 struct IBF_Key *key_dst;
309 struct IBF_KeyHash *key_hash_dst; 330 struct IBF_KeyHash *key_hash_dst;
310 struct IBF_Count *count_dst;
311 331
312 GNUNET_assert (start + count <= ibf->size); 332 GNUNET_assert (start + count <= ibf->size);
313 333
@@ -315,19 +335,182 @@ ibf_write_slice (const struct InvertibleBloomFilter *ibf,
315 key_dst = (struct IBF_Key *) buf; 335 key_dst = (struct IBF_Key *) buf;
316 GNUNET_memcpy (key_dst, 336 GNUNET_memcpy (key_dst,
317 ibf->key_sum + start, 337 ibf->key_sum + start,
318 count * sizeof *key_dst); 338 count * sizeof(*key_dst));
319 key_dst += count; 339 key_dst += count;
320 /* copy key hashes */ 340 /* copy key hashes */
321 key_hash_dst = (struct IBF_KeyHash *) key_dst; 341 key_hash_dst = (struct IBF_KeyHash *) key_dst;
322 GNUNET_memcpy (key_hash_dst, 342 GNUNET_memcpy (key_hash_dst,
323 ibf->key_hash_sum + start, 343 ibf->key_hash_sum + start,
324 count * sizeof *key_hash_dst); 344 count * sizeof(*key_hash_dst));
325 key_hash_dst += count; 345 key_hash_dst += count;
326 /* copy counts */ 346
327 count_dst = (struct IBF_Count *) key_hash_dst; 347 /* pack and copy counter */
328 GNUNET_memcpy (count_dst, 348 pack_counter (ibf,
329 ibf->count + start, 349 start,
330 count * sizeof *count_dst); 350 count,
351 (uint8_t *) key_hash_dst,
352 counter_max_length);
353
354
355}
356
357
358/**
359 * Packs the counter to transmit only the smallest possible amount of bytes and
360 * preventing overflow of the counter
361 * @param ibf the ibf to write
362 * @param start with which bucket to start
363 * @param count how many buckets to write
364 * @param buf buffer to write the data to
365 * @param max bit length of a counter for unpacking
366 */
367
368void
369pack_counter (const struct InvertibleBloomFilter *ibf,
370 uint32_t start,
371 uint64_t count,
372 uint8_t *buf,
373 uint8_t counter_max_length)
374{
375 uint8_t store_size = 0;
376 uint8_t store = 0;
377 uint16_t byte_ctr = 0;
378
379 /**
380 * Iterate over IBF bucket
381 */
382 for (uint64_t i = start; i< (count + start);)
383 {
384 uint64_t count_val_to_write = ibf->count[i].count_val;
385 uint8_t count_len_to_write = counter_max_length;
386
387 /**
388 * Pack and compose counters to byte values
389 */
390 while ((count_len_to_write + store_size) >= 8)
391 {
392 uint8_t bit_shift = 0;
393
394 /**
395 * Shift bits if more than a byte has to be written
396 * or the store size is not empty
397 */
398 if ((store_size > 0) || (count_len_to_write > 8))
399 {
400 uint8_t bit_unused = 8 - store_size;
401 bit_shift = count_len_to_write - bit_unused;
402 store = store << bit_unused;
403 }
404
405 buf[byte_ctr] = ((count_val_to_write >> bit_shift) | store) & 0xFF;
406 byte_ctr++;
407 count_len_to_write -= (8 - store_size);
408 count_val_to_write = count_val_to_write & ((1ULL <<
409 count_len_to_write) - 1);
410 store = 0;
411 store_size = 0;
412 }
413 store = (store << count_len_to_write) | count_val_to_write;
414 store_size = store_size + count_len_to_write;
415 count_len_to_write = 0;
416 i++;
417 }
418
419 /**
420 * Pack data left in story before finishing
421 */
422 if (store_size > 0)
423 {
424 buf[byte_ctr] = store << (8 - store_size);
425 byte_ctr++;
426 }
427
428}
429
430
431/**
432 * Unpacks the counter to transmit only the smallest possible amount of bytes and
433 * preventing overflow of the counter
434 * @param ibf the ibf to write
435 * @param start with which bucket to start
436 * @param count how many buckets to write
437 * @param buf buffer to write the data to
438 * @param max bit length of a counter for unpacking
439 */
440
441void
442unpack_counter (const struct InvertibleBloomFilter *ibf,
443 uint32_t start,
444 uint64_t count,
445 uint8_t *buf,
446 uint8_t counter_max_length)
447{
448 uint64_t ibf_counter_ctr = 0;
449 uint64_t store = 0;
450 uint64_t store_bit_ctr = 0;
451 uint64_t byte_ctr = 0;
452
453 /**
454 * Iterate over received bytes
455 */
456 while (true)
457 {
458 uint8_t byte_read = buf[byte_ctr];
459 uint8_t bit_to_read_left = 8;
460 byte_ctr++;
461
462 /**
463 * Pack data left in story before finishing
464 */
465 while (bit_to_read_left >= 0)
466 {
467 /**
468 * Stop decoding when end is reached
469 */
470 if (ibf_counter_ctr > (count - 1))
471 return;
472
473 /*
474 * Unpack the counter
475 */
476 if ((store_bit_ctr + bit_to_read_left) >= counter_max_length)
477 {
478 uint8_t bytes_used = counter_max_length - store_bit_ctr;
479 if (store_bit_ctr > 0)
480 {
481 store = store << bytes_used;
482 }
483
484 uint8_t bytes_to_shift = bit_to_read_left - bytes_used;
485 uint64_t counter_part = byte_read >> bytes_to_shift;
486 store = store | counter_part;
487 ibf->count[ibf_counter_ctr + start].count_val = store;
488 byte_read = byte_read & ((1 << bytes_to_shift) - 1);
489 bit_to_read_left -= bytes_used;
490 ibf_counter_ctr++;
491 store = 0;
492 store_bit_ctr = 0;
493 }
494 else
495 {
496 store_bit_ctr += bit_to_read_left;
497 if (0 == store)
498 {
499 store = byte_read;
500 }
501 else
502 {
503 store = store << bit_to_read_left;
504 store = store | byte_read;
505 }
506 break;
507
508 }
509
510 }
511
512 }
513
331} 514}
332 515
333 516
@@ -338,12 +521,14 @@ ibf_write_slice (const struct InvertibleBloomFilter *ibf,
338 * @param start which bucket to start at 521 * @param start which bucket to start at
339 * @param count how many buckets to read 522 * @param count how many buckets to read
340 * @param ibf the ibf to read from 523 * @param ibf the ibf to read from
524 * @param max bit length of a counter for unpacking
341 */ 525 */
342void 526void
343ibf_read_slice (const void *buf, 527ibf_read_slice (const void *buf,
344 uint32_t start, 528 uint32_t start,
345 uint32_t count, 529 uint64_t count,
346 struct InvertibleBloomFilter *ibf) 530 struct InvertibleBloomFilter *ibf,
531 uint8_t counter_max_length)
347{ 532{
348 struct IBF_Key *key_src; 533 struct IBF_Key *key_src;
349 struct IBF_KeyHash *key_hash_src; 534 struct IBF_KeyHash *key_hash_src;
@@ -364,11 +549,10 @@ ibf_read_slice (const void *buf,
364 key_hash_src, 549 key_hash_src,
365 count * sizeof *key_hash_src); 550 count * sizeof *key_hash_src);
366 key_hash_src += count; 551 key_hash_src += count;
367 /* copy counts */ 552
553 /* copy and unpack counts */
368 count_src = (struct IBF_Count *) key_hash_src; 554 count_src = (struct IBF_Count *) key_hash_src;
369 GNUNET_memcpy (ibf->count + start, 555 unpack_counter (ibf,start,count,(uint8_t *) count_src,counter_max_length);
370 count_src,
371 count * sizeof *count_src);
372} 556}
373 557
374 558