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.c614
1 files changed, 0 insertions, 614 deletions
diff --git a/src/setu/ibf.c b/src/setu/ibf.c
deleted file mode 100644
index dbd23c320..000000000
--- a/src/setu/ibf.c
+++ /dev/null
@@ -1,614 +0,0 @@
1/*
2 This file is part of GNUnet
3 Copyright (C) 2012 GNUnet e.V.
4
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero 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.
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 Affero General Public License for more details.
14
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 SPDX-License-Identifier: AGPL3.0-or-later
19 */
20
21/**
22 * @file set/ibf.c
23 * @brief implementation of the invertible bloom filter
24 * @author Florian Dold
25 * @author Elias Summermatter
26 */
27
28#include "ibf.h"
29#include "gnunet_util_lib.h"
30#define LOG(kind, ...) GNUNET_log_from (kind, "setu", __VA_ARGS__)
31
32
33/**
34 * Compute the key's hash from the key.
35 * Redefine to use a different hash function.
36 */
37#define IBF_KEY_HASH_VAL(k) (GNUNET_CRYPTO_crc32_n (&(k), sizeof(struct \
38 IBF_KeyHash)))
39
40/**
41 * Create a key from a hashcode.
42 *
43 * @param hash the hashcode
44 * @return a key
45 */
46struct IBF_Key
47ibf_key_from_hashcode (const struct GNUNET_HashCode *hash)
48{
49 return *(struct IBF_Key *) hash;
50}
51
52
53/**
54 * Create a hashcode from a key, by replicating the key
55 * until the hascode is filled
56 *
57 * @param key the key
58 * @param dst hashcode to store the result in
59 */
60void
61ibf_hashcode_from_key (struct IBF_Key key,
62 struct GNUNET_HashCode *dst)
63{
64 struct IBF_Key *p;
65 unsigned int i;
66 const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode)
67 / sizeof(struct IBF_Key);
68
69 p = (struct IBF_Key *) dst;
70 for (i = 0; i < keys_per_hashcode; i++)
71 *p++ = key;
72}
73
74
75/**
76 * Create an invertible bloom filter.
77 *
78 * @param size number of IBF buckets
79 * @param hash_num number of buckets one element is hashed in
80 * @return the newly created invertible bloom filter, NULL on error
81 */
82struct InvertibleBloomFilter *
83ibf_create (uint32_t size, uint8_t hash_num)
84{
85 struct InvertibleBloomFilter *ibf;
86
87 GNUNET_assert (0 != size);
88
89 ibf = GNUNET_new (struct InvertibleBloomFilter);
90 ibf->count = GNUNET_malloc_large (size * sizeof(uint64_t));
91 if (NULL == ibf->count)
92 {
93 GNUNET_free (ibf);
94 return NULL;
95 }
96 ibf->key_sum = GNUNET_malloc_large (size * sizeof(struct IBF_Key));
97 if (NULL == ibf->key_sum)
98 {
99 GNUNET_free (ibf->count);
100 GNUNET_free (ibf);
101 return NULL;
102 }
103 ibf->key_hash_sum = GNUNET_malloc_large (size * sizeof(struct IBF_KeyHash));
104 if (NULL == ibf->key_hash_sum)
105 {
106 GNUNET_free (ibf->key_sum);
107 GNUNET_free (ibf->count);
108 GNUNET_free (ibf);
109 return NULL;
110 }
111 ibf->size = size;
112 ibf->hash_num = hash_num;
113
114 return ibf;
115}
116
117
118/**
119 * Store unique bucket indices for the specified @a key in @a dst.
120 */
121static void
122ibf_get_indices (const struct InvertibleBloomFilter *ibf,
123 struct IBF_Key key,
124 int *dst)
125{
126 uint32_t filled;
127 uint32_t i;
128 uint32_t bucket;
129
130 bucket = GNUNET_CRYPTO_crc32_n (&key, sizeof key);
131 for (i = 0, filled = 0; filled < ibf->hash_num; i++)
132 {
133 uint64_t x;
134
135 for (unsigned int j = 0; j < filled; j++)
136 if (dst[j] == bucket % ibf->size)
137 goto try_next;
138 dst[filled++] = bucket % ibf->size;
139try_next:
140 x = ((uint64_t) bucket << 32) | i;
141 bucket = GNUNET_CRYPTO_crc32_n (&x, sizeof x);
142 }
143}
144
145
146static void
147ibf_insert_into (struct InvertibleBloomFilter *ibf,
148 struct IBF_Key key,
149 const int *buckets,
150 int side)
151{
152 for (unsigned int i = 0; i < ibf->hash_num; i++)
153 {
154 const int bucket = buckets[i];
155
156 ibf->count[bucket].count_val += side;
157 ibf->key_sum[bucket].key_val ^= key.key_val;
158 ibf->key_hash_sum[bucket].key_hash_val
159 ^= IBF_KEY_HASH_VAL (key);
160 }
161}
162
163
164/**
165 * Insert a key into an IBF.
166 *
167 * @param ibf the IBF
168 * @param key the element's hash code
169 */
170void
171ibf_insert (struct InvertibleBloomFilter *ibf,
172 struct IBF_Key key)
173{
174 int buckets[ibf->hash_num];
175
176 GNUNET_assert (ibf->hash_num <= ibf->size);
177 ibf_get_indices (ibf, key, buckets);
178 ibf_insert_into (ibf, key, buckets, 1);
179}
180
181
182/**
183 * Remove a key from an IBF.
184 *
185 * @param ibf the IBF
186 * @param key the element's hash code
187 */
188void
189ibf_remove (struct InvertibleBloomFilter *ibf,
190 struct IBF_Key key)
191{
192 int buckets[ibf->hash_num];
193
194 GNUNET_assert (ibf->hash_num <= ibf->size);
195 ibf_get_indices (ibf, key, buckets);
196 ibf_insert_into (ibf, key, buckets, -1);
197}
198
199
200/**
201 * Test is the IBF is empty, i.e. all counts, keys and key hashes are zero.
202 */
203static int
204ibf_is_empty (struct InvertibleBloomFilter *ibf)
205{
206 for (uint32_t i = 0; i < ibf->size; i++)
207 {
208 if (0 != ibf->count[i].count_val)
209 return GNUNET_NO;
210 if (0 != ibf->key_hash_sum[i].key_hash_val)
211 return GNUNET_NO;
212 if (0 != ibf->key_sum[i].key_val)
213 return GNUNET_NO;
214 }
215 return GNUNET_YES;
216}
217
218
219/**
220 * Decode and remove an element from the IBF, if possible.
221 *
222 * @param ibf the invertible bloom filter to decode
223 * @param ret_side sign of the cell's count where the decoded element came from.
224 * A negative sign indicates that the element was recovered
225 * resides in an IBF that was previously subtracted from.
226 * @param ret_id receives the hash code of the decoded element, if successful
227 * @return #GNUNET_YES if decoding an element was successful,
228 * #GNUNET_NO if the IBF is empty,
229 * #GNUNET_SYSERR if the decoding has failed
230 */
231int
232ibf_decode (struct InvertibleBloomFilter *ibf,
233 int *ret_side,
234 struct IBF_Key *ret_id)
235{
236 struct IBF_KeyHash hash;
237 int buckets[ibf->hash_num];
238
239 for (uint32_t i = 0; i < ibf->size; i++)
240 {
241 int hit;
242
243 /* we can only decode from pure buckets */
244 if ( (1 != ibf->count[i].count_val) &&
245 (-1 != ibf->count[i].count_val) )
246 continue;
247
248 hash.key_hash_val = IBF_KEY_HASH_VAL (ibf->key_sum[i]);
249
250 /* test if the hash matches the key */
251 if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
252 continue;
253
254 /* test if key in bucket hits its own location,
255 * if not, the key hash was subject to collision */
256 hit = GNUNET_NO;
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;
261
262 if (GNUNET_NO == hit)
263 continue;
264
265 if (1 == ibf->count[i].count_val)
266 {
267 ibf->remote_decoded_count++;
268 }
269 else
270 {
271 ibf->local_decoded_count++;
272 }
273
274
275 if (NULL != ret_side)
276 *ret_side = ibf->count[i].count_val;
277 if (NULL != ret_id)
278 *ret_id = ibf->key_sum[i];
279
280 /* insert on the opposite side, effectively removing the element */
281 ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
282
283 return GNUNET_YES;
284 }
285
286 if (GNUNET_YES == ibf_is_empty (ibf))
287 return GNUNET_NO;
288 return GNUNET_SYSERR;
289}
290
291
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/**
313 * Write buckets from an ibf to a buffer.
314 * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
315 *
316 * @param ibf the ibf to write
317 * @param start with which bucket to start
318 * @param count how many buckets to write
319 * @param buf buffer to write the data to
320 * @param max bit length of a counter for unpacking
321 */
322void
323ibf_write_slice (const struct InvertibleBloomFilter *ibf,
324 uint32_t start,
325 uint64_t count,
326 void *buf,
327 uint8_t counter_max_length)
328{
329 struct IBF_Key *key_dst;
330 struct IBF_KeyHash *key_hash_dst;
331
332 GNUNET_assert (start + count <= ibf->size);
333
334 /* copy keys */
335 key_dst = (struct IBF_Key *) buf;
336 GNUNET_memcpy (key_dst,
337 ibf->key_sum + start,
338 count * sizeof(*key_dst));
339 key_dst += count;
340 /* copy key hashes */
341 key_hash_dst = (struct IBF_KeyHash *) key_dst;
342 GNUNET_memcpy (key_hash_dst,
343 ibf->key_hash_sum + start,
344 count * sizeof(*key_hash_dst));
345 key_hash_dst += count;
346
347 /* pack and copy counter */
348 pack_counter (ibf,
349 start,
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 (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 }
510}
511
512
513/**
514 * Read buckets from a buffer into an ibf.
515 *
516 * @param buf pointer to the buffer to read from
517 * @param start which bucket to start at
518 * @param count how many buckets to read
519 * @param ibf the ibf to read from
520 * @param max bit length of a counter for unpacking
521 */
522void
523ibf_read_slice (const void *buf,
524 uint32_t start,
525 uint64_t count,
526 struct InvertibleBloomFilter *ibf,
527 uint8_t counter_max_length)
528{
529 struct IBF_Key *key_src;
530 struct IBF_KeyHash *key_hash_src;
531 struct IBF_Count *count_src;
532
533 GNUNET_assert (count > 0);
534 GNUNET_assert (start + count <= ibf->size);
535
536 /* copy keys */
537 key_src = (struct IBF_Key *) buf;
538 GNUNET_memcpy (ibf->key_sum + start,
539 key_src,
540 count * sizeof *key_src);
541 key_src += count;
542 /* copy key hashes */
543 key_hash_src = (struct IBF_KeyHash *) key_src;
544 GNUNET_memcpy (ibf->key_hash_sum + start,
545 key_hash_src,
546 count * sizeof *key_hash_src);
547 key_hash_src += count;
548
549 /* copy and unpack counts */
550 count_src = (struct IBF_Count *) key_hash_src;
551 unpack_counter (ibf,start,count,(uint8_t *) count_src,counter_max_length);
552}
553
554
555/**
556 * Subtract ibf2 from ibf1, storing the result in ibf1.
557 * The two IBF's must have the same parameters size and hash_num.
558 *
559 * @param ibf1 IBF that is subtracted from
560 * @param ibf2 IBF that will be subtracted from ibf1
561 */
562void
563ibf_subtract (struct InvertibleBloomFilter *ibf1,
564 const struct InvertibleBloomFilter *ibf2)
565{
566 GNUNET_assert (ibf1->size == ibf2->size);
567 GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
568
569 for (uint32_t i = 0; i < ibf1->size; i++)
570 {
571 ibf1->count[i].count_val -= ibf2->count[i].count_val;
572 ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
573 ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
574 }
575}
576
577
578/**
579 * Create a copy of an IBF, the copy has to be destroyed properly.
580 *
581 * @param ibf the IBF to copy
582 */
583struct InvertibleBloomFilter *
584ibf_dup (const struct InvertibleBloomFilter *ibf)
585{
586 struct InvertibleBloomFilter *copy;
587
588 copy = GNUNET_malloc (sizeof *copy);
589 copy->hash_num = ibf->hash_num;
590 copy->size = ibf->size;
591 copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum,
592 ibf->size * sizeof(struct IBF_KeyHash));
593 copy->key_sum = GNUNET_memdup (ibf->key_sum,
594 ibf->size * sizeof(struct IBF_Key));
595 copy->count = GNUNET_memdup (ibf->count,
596 ibf->size * sizeof(struct IBF_Count));
597 return copy;
598}
599
600
601/**
602 * Destroy all resources associated with the invertible bloom filter.
603 * No more ibf_*-functions may be called on ibf after calling destroy.
604 *
605 * @param ibf the intertible bloom filter to destroy
606 */
607void
608ibf_destroy (struct InvertibleBloomFilter *ibf)
609{
610 GNUNET_free (ibf->key_sum);
611 GNUNET_free (ibf->key_hash_sum);
612 GNUNET_free (ibf->count);
613 GNUNET_free (ibf);
614}
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-16 04:20:47 +0000