GNUnet  0.11.x
ibf.c
Go to the documentation of this file.
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 
28 #include "ibf.h"
29 #include "gnunet_util_lib.h"
30 #define LOG(kind, ...) GNUNET_log_from (kind, "setu", __VA_ARGS__)
31 
32 
37 #define IBF_KEY_HASH_VAL(k) (GNUNET_CRYPTO_crc32_n (&(k), sizeof(struct \
38  IBF_KeyHash)))
39 
46 struct IBF_Key
48 {
49  return *(struct IBF_Key *) hash;
50 }
51 
52 
60 void
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 
82 struct InvertibleBloomFilter *
83 ibf_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 
121 static void
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;
139 try_next:
140  x = ((uint64_t) bucket << 32) | i;
141  bucket = GNUNET_CRYPTO_crc32_n (&x, sizeof x);
142  }
143 }
144 
145 
146 static void
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 
170 void
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 
188 void
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 
203 static int
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 
231 int
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 
297 uint8_t
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 
322 void
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 
368 void
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 
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 
390  while ((count_len_to_write + store_size) >= 8)
391  {
392  uint8_t bit_shift = 0;
393 
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 
422  if (store_size > 0)
423  {
424  buf[byte_ctr] = store << (8 - store_size);
425  byte_ctr++;
426  }
427 
428 }
429 
430 
441 void
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 
456  while (true)
457  {
458  uint8_t byte_read = buf[byte_ctr];
459  uint8_t bit_to_read_left = 8;
460  byte_ctr++;
461 
465  while (bit_to_read_left >= 0)
466  {
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 }
515 
516 
526 void
527 ibf_read_slice (const void *buf,
528  uint32_t start,
529  uint64_t count,
530  struct InvertibleBloomFilter *ibf,
531  uint8_t counter_max_length)
532 {
533  struct IBF_Key *key_src;
534  struct IBF_KeyHash *key_hash_src;
535  struct IBF_Count *count_src;
536 
537  GNUNET_assert (count > 0);
538  GNUNET_assert (start + count <= ibf->size);
539 
540  /* copy keys */
541  key_src = (struct IBF_Key *) buf;
542  GNUNET_memcpy (ibf->key_sum + start,
543  key_src,
544  count * sizeof *key_src);
545  key_src += count;
546  /* copy key hashes */
547  key_hash_src = (struct IBF_KeyHash *) key_src;
548  GNUNET_memcpy (ibf->key_hash_sum + start,
549  key_hash_src,
550  count * sizeof *key_hash_src);
551  key_hash_src += count;
552 
553  /* copy and unpack counts */
554  count_src = (struct IBF_Count *) key_hash_src;
555  unpack_counter (ibf,start,count,(uint8_t *) count_src,counter_max_length);
556 }
557 
558 
566 void
568  const struct InvertibleBloomFilter *ibf2)
569 {
570  GNUNET_assert (ibf1->size == ibf2->size);
571  GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
572 
573  for (uint32_t i = 0; i < ibf1->size; i++)
574  {
575  ibf1->count[i].count_val -= ibf2->count[i].count_val;
576  ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
577  ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
578  }
579 }
580 
581 
587 struct InvertibleBloomFilter *
588 ibf_dup (const struct InvertibleBloomFilter *ibf)
589 {
590  struct InvertibleBloomFilter *copy;
591 
592  copy = GNUNET_malloc (sizeof *copy);
593  copy->hash_num = ibf->hash_num;
594  copy->size = ibf->size;
596  ibf->size * sizeof(struct IBF_KeyHash));
597  copy->key_sum = GNUNET_memdup (ibf->key_sum,
598  ibf->size * sizeof(struct IBF_Key));
599  copy->count = GNUNET_memdup (ibf->count,
600  ibf->size * sizeof(struct IBF_Count));
601  return copy;
602 }
603 
604 
611 void
613 {
614  GNUNET_free (ibf->key_sum);
615  GNUNET_free (ibf->key_hash_sum);
616  GNUNET_free (ibf->count);
617  GNUNET_free (ibf);
618 }
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:184
void unpack_counter(const struct InvertibleBloomFilter *ibf, uint32_t start, uint64_t count, uint8_t *buf, uint8_t counter_max_length)
Unpacks the counter to transmit only the smallest possible amount of bytes and preventing overflow of...
Definition: ibf.c:442
int32_t GNUNET_CRYPTO_crc32_n(const void *buf, size_t len)
Compute the CRC32 checksum for the first len bytes of the buffer.
Definition: crypto_crc.c:106
uint8_t ibf_get_max_counter(struct InvertibleBloomFilter *ibf)
Returns the minimal bytes needed to store the counter of the IBF.
Definition: ibf.c:298
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
int remote_decoded_count
If an IBF is decoded this count stores how many elements are on the remote site.
Definition: ibf.h:108
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Invertible bloom filter (IBF).
Definition: ibf.h:82
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:112
#define GNUNET_memdup(buf, size)
Allocate and initialize a block of memory.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
uint64_t key_val
Definition: ibf.h:47
void ibf_write_slice(const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
Write buckets from an ibf to a buffer.
Definition: ibf.c:290
#define GNUNET_malloc_large(size)
Wrapper around malloc.
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
Definition: ibf.c:147
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:379
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
void pack_counter(const struct InvertibleBloomFilter *ibf, uint32_t start, uint64_t count, uint8_t *buf, uint8_t counter_max_length)
Packs the counter to transmit only the smallest possible amount of bytes and preventing overflow of t...
Definition: ibf.c:369
static int ibf_is_empty(struct InvertibleBloomFilter *ibf)
Test is the IBF is empty, i.e.
Definition: ibf.c:204
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
uint32_t key_hash_val
Definition: ibf.h:56
#define IBF_KEY_HASH_VAL(k)
Compute the key&#39;s hash from the key.
Definition: ibf.c:37
int ibf_decode(struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
Decode and remove an element from the IBF, if possible.
Definition: ibf.c:228
void ibf_hashcode_from_key(struct IBF_Key key, struct GNUNET_HashCode *dst)
Create a hashcode from a key, by replicating the key until the hascode is filled. ...
Definition: ibf.c:57
static char buf[2048]
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:356
static void ibf_get_indices(const struct InvertibleBloomFilter *ibf, struct IBF_Key key, int *dst)
Store unique bucket indices for the specified key in dst.
Definition: ibf.c:122
A 512-bit hashcode.
Type of the count field of IBF buckets.
Definition: ibf.h:63
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
void ibf_read_slice(const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
Read buckets from a buffer into an ibf.
Definition: ibf.c:323
struct GNUNET_HashCode key
The key used in the DHT.
static unsigned int size
Size of the "table".
Definition: peer.c:67
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:403
static unsigned int hash_num
Hash of an IBF key.
Definition: ibf.h:54
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:79
int local_decoded_count
If an IBF is decoded this count stores how many elements are on the local site.
Definition: ibf.h:101
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:167
int8_t count_val
Definition: ibf.h:65
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
struct IBF_Key ibf_key_from_hashcode(const struct GNUNET_HashCode *hash)
Create a key from a hashcode.
Definition: ibf.c:43
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.