diff options
Diffstat (limited to 'src/setu/ibf.c')
-rw-r--r-- | src/setu/ibf.c | 290 |
1 files changed, 235 insertions, 55 deletions
diff --git a/src/setu/ibf.c b/src/setu/ibf.c index 1beba9065..dbd23c320 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 | */ |
77 | struct InvertibleBloomFilter * | 82 | struct InvertibleBloomFilter * |
78 | ibf_create (uint32_t size, | 83 | ibf_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; |
134 | try_next: | 139 | try_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 | */ | ||
297 | uint8_t | ||
298 | ibf_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 | */ |
302 | void | 322 | void |
303 | ibf_write_slice (const struct InvertibleBloomFilter *ibf, | 323 | ibf_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,178 @@ 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 | |||
368 | void | ||
369 | pack_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 | |||
441 | void | ||
442 | unpack_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 (true) | ||
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 | } | ||
331 | } | 510 | } |
332 | 511 | ||
333 | 512 | ||
@@ -338,12 +517,14 @@ ibf_write_slice (const struct InvertibleBloomFilter *ibf, | |||
338 | * @param start which bucket to start at | 517 | * @param start which bucket to start at |
339 | * @param count how many buckets to read | 518 | * @param count how many buckets to read |
340 | * @param ibf the ibf to read from | 519 | * @param ibf the ibf to read from |
520 | * @param max bit length of a counter for unpacking | ||
341 | */ | 521 | */ |
342 | void | 522 | void |
343 | ibf_read_slice (const void *buf, | 523 | ibf_read_slice (const void *buf, |
344 | uint32_t start, | 524 | uint32_t start, |
345 | uint32_t count, | 525 | uint64_t count, |
346 | struct InvertibleBloomFilter *ibf) | 526 | struct InvertibleBloomFilter *ibf, |
527 | uint8_t counter_max_length) | ||
347 | { | 528 | { |
348 | struct IBF_Key *key_src; | 529 | struct IBF_Key *key_src; |
349 | struct IBF_KeyHash *key_hash_src; | 530 | struct IBF_KeyHash *key_hash_src; |
@@ -364,11 +545,10 @@ ibf_read_slice (const void *buf, | |||
364 | key_hash_src, | 545 | key_hash_src, |
365 | count * sizeof *key_hash_src); | 546 | count * sizeof *key_hash_src); |
366 | key_hash_src += count; | 547 | key_hash_src += count; |
367 | /* copy counts */ | 548 | |
549 | /* copy and unpack counts */ | ||
368 | count_src = (struct IBF_Count *) key_hash_src; | 550 | count_src = (struct IBF_Count *) key_hash_src; |
369 | GNUNET_memcpy (ibf->count + start, | 551 | unpack_counter (ibf,start,count,(uint8_t *) count_src,counter_max_length); |
370 | count_src, | ||
371 | count * sizeof *count_src); | ||
372 | } | 552 | } |
373 | 553 | ||
374 | 554 | ||