GNUnet  0.11.x
Macros | Functions
ibf.c File Reference
#include "ibf.h"
#include "gnunet_util_lib.h"
Include dependency graph for ibf.c:

Go to the source code of this file.

Macros

#define LOG(kind, ...)   GNUNET_log_from (kind, "setu", __VA_ARGS__)
 
#define IBF_KEY_HASH_VAL(k)
 Compute the key's hash from the key. More...
 

Functions

struct IBF_Key ibf_key_from_hashcode (const struct GNUNET_HashCode *hash)
 Create a key from a hashcode. More...
 
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. More...
 
struct InvertibleBloomFilteribf_create (uint32_t size, uint8_t hash_num)
 Create an invertible bloom filter. More...
 
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. More...
 
static void ibf_insert_into (struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
 
void ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
 Insert a key into an IBF. More...
 
void ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
 Remove a key from an IBF. More...
 
static int ibf_is_empty (struct InvertibleBloomFilter *ibf)
 Test is the IBF is empty, i.e. More...
 
int ibf_decode (struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
 Decode and remove an element from the IBF, if possible. More...
 
uint8_t ibf_get_max_counter (struct InvertibleBloomFilter *ibf)
 Returns the minimal bytes needed to store the counter of the IBF. More...
 
void ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint64_t count, void *buf, uint8_t counter_max_length)
 Write buckets from an ibf to a buffer. More...
 
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 the counter. More...
 
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 the counter. More...
 
void ibf_read_slice (const void *buf, uint32_t start, uint64_t count, struct InvertibleBloomFilter *ibf, uint8_t counter_max_length)
 Read buckets from a buffer into an ibf. More...
 
void ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
 Subtract ibf2 from ibf1, storing the result in ibf1. More...
 
struct InvertibleBloomFilteribf_dup (const struct InvertibleBloomFilter *ibf)
 Create a copy of an IBF, the copy has to be destroyed properly. More...
 
void ibf_destroy (struct InvertibleBloomFilter *ibf)
 Destroy all resources associated with the invertible bloom filter. More...
 

Macro Definition Documentation

◆ LOG

#define LOG (   kind,
  ... 
)    GNUNET_log_from (kind, "setu", __VA_ARGS__)

Definition at line 30 of file ibf.c.

◆ IBF_KEY_HASH_VAL

#define IBF_KEY_HASH_VAL (   k)
Value:
(GNUNET_CRYPTO_crc32_n (&(k), sizeof(struct \
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
Hash of an IBF key.
Definition: ibf.h:54

Compute the key's hash from the key.

Redefine to use a different hash function.

Definition at line 37 of file ibf.c.

Referenced by ibf_decode(), and ibf_insert_into().

Function Documentation

◆ ibf_key_from_hashcode()

struct IBF_Key ibf_key_from_hashcode ( const struct GNUNET_HashCode hash)

Create a key from a hashcode.

Parameters
hashthe hashcode
Returns
a key

Definition at line 47 of file ibf.c.

48 {
49  return *(struct IBF_Key *) hash;
50 }
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45

◆ ibf_hashcode_from_key()

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.

Parameters
keythe key
dsthashcode to store the result in

Definition at line 61 of file ibf.c.

References p.

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 }
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
A 512-bit hashcode.
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45

◆ ibf_create()

struct InvertibleBloomFilter* ibf_create ( uint32_t  size,
uint8_t  hash_num 
)

Create an invertible bloom filter.

Parameters
sizenumber of IBF buckets
hash_numnumber of buckets one element is hashed in
Returns
the newly created invertible bloom filter, NULL on error

Definition at line 83 of file ibf.c.

References InvertibleBloomFilter::count, GNUNET_assert, GNUNET_free, GNUNET_malloc_large, GNUNET_new, hash_num, InvertibleBloomFilter::hash_num, InvertibleBloomFilter::key_hash_sum, InvertibleBloomFilter::key_sum, size, and InvertibleBloomFilter::size.

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 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Invertible bloom filter (IBF).
Definition: ibf.h:82
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_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
static unsigned int size
Size of the "table".
Definition: peer.c:67
static unsigned int hash_num
Hash of an IBF key.
Definition: ibf.h:54
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
#define GNUNET_free(ptr)
Wrapper around free.

◆ ibf_get_indices()

static void ibf_get_indices ( const struct InvertibleBloomFilter ibf,
struct IBF_Key  key,
int *  dst 
)
static

Store unique bucket indices for the specified key in dst.

Definition at line 122 of file ibf.c.

References GNUNET_CRYPTO_crc32_n(), InvertibleBloomFilter::hash_num, and InvertibleBloomFilter::size.

Referenced by ibf_decode(), ibf_insert(), and ibf_remove().

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 }
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
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
Here is the call graph for this function:
Here is the caller graph for this function:

◆ ibf_insert_into()

static void ibf_insert_into ( struct InvertibleBloomFilter ibf,
struct IBF_Key  key,
const int *  buckets,
int  side 
)
static

Definition at line 147 of file ibf.c.

References InvertibleBloomFilter::count, IBF_Count::count_val, InvertibleBloomFilter::hash_num, IBF_KEY_HASH_VAL, InvertibleBloomFilter::key_hash_sum, IBF_KeyHash::key_hash_val, InvertibleBloomFilter::key_sum, and IBF_Key::key_val.

Referenced by ibf_decode(), ibf_insert(), and ibf_remove().

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 }
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
uint64_t key_val
Definition: ibf.h:47
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
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
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
Here is the caller graph for this function:

◆ ibf_insert()

void ibf_insert ( struct InvertibleBloomFilter ibf,
struct IBF_Key  key 
)

Insert a key into an IBF.

Parameters
ibfthe IBF
keythe element's hash code

Definition at line 171 of file ibf.c.

References GNUNET_assert, InvertibleBloomFilter::hash_num, ibf_get_indices(), ibf_insert_into(), and InvertibleBloomFilter::size.

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 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
Definition: ibf.c:147
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
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
Here is the call graph for this function:

◆ ibf_remove()

void ibf_remove ( struct InvertibleBloomFilter ibf,
struct IBF_Key  key 
)

Remove a key from an IBF.

Parameters
ibfthe IBF
keythe element's hash code

Definition at line 189 of file ibf.c.

References GNUNET_assert, InvertibleBloomFilter::hash_num, ibf_get_indices(), ibf_insert_into(), and InvertibleBloomFilter::size.

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 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
Definition: ibf.c:147
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
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
Here is the call graph for this function:

◆ ibf_is_empty()

static int ibf_is_empty ( struct InvertibleBloomFilter ibf)
static

Test is the IBF is empty, i.e.

all counts, keys and key hashes are zero.

Definition at line 204 of file ibf.c.

References InvertibleBloomFilter::count, IBF_Count::count_val, GNUNET_NO, GNUNET_YES, InvertibleBloomFilter::key_hash_sum, IBF_KeyHash::key_hash_val, InvertibleBloomFilter::key_sum, IBF_Key::key_val, and InvertibleBloomFilter::size.

Referenced by ibf_decode().

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 }
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
uint64_t key_val
Definition: ibf.h:47
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint32_t key_hash_val
Definition: ibf.h:56
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
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
Here is the caller graph for this function:

◆ ibf_decode()

int ibf_decode ( struct InvertibleBloomFilter ibf,
int *  ret_side,
struct IBF_Key ret_id 
)

Decode and remove an element from the IBF, if possible.

Parameters
ibfthe invertible bloom filter to decode
ret_sidesign of the cell's count where the decoded element came from. A negative sign indicates that the element was recovered resides in an IBF that was previously subtracted from.
ret_idreceives the hash code of the decoded element, if successful
Returns
GNUNET_YES if decoding an element was successful, GNUNET_NO if the IBF is empty, GNUNET_SYSERR if the decoding has failed

Definition at line 232 of file ibf.c.

References InvertibleBloomFilter::count, IBF_Count::count_val, GNUNET_assert, GNUNET_NO, GNUNET_SYSERR, GNUNET_YES, InvertibleBloomFilter::hash_num, ibf_get_indices(), ibf_insert_into(), ibf_is_empty(), IBF_KEY_HASH_VAL, InvertibleBloomFilter::key_hash_sum, IBF_KeyHash::key_hash_val, InvertibleBloomFilter::key_sum, InvertibleBloomFilter::local_decoded_count, InvertibleBloomFilter::remote_decoded_count, and InvertibleBloomFilter::size.

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 }
int remote_decoded_count
If an IBF is decoded this count stores how many elements are on the remote site.
Definition: ibf.h:108
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
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
Definition: ibf.c:147
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
static int ibf_is_empty(struct InvertibleBloomFilter *ibf)
Test is the IBF is empty, i.e.
Definition: ibf.c:204
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
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
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
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
Hash of an IBF key.
Definition: ibf.h:54
int local_decoded_count
If an IBF is decoded this count stores how many elements are on the local site.
Definition: ibf.h:101
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
Here is the call graph for this function:

◆ ibf_get_max_counter()

uint8_t ibf_get_max_counter ( struct InvertibleBloomFilter ibf)

Returns the minimal bytes needed to store the counter of the IBF.

Parameters
ibfthe IBF

Definition at line 298 of file ibf.c.

References InvertibleBloomFilter::count, IBF_Count::count_val, and InvertibleBloomFilter::size.

Referenced by send_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 }
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
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
int8_t count_val
Definition: ibf.h:65
Here is the caller graph for this function:

◆ ibf_write_slice()

void ibf_write_slice ( const struct InvertibleBloomFilter ibf,
uint32_t  start,
uint64_t  count,
void *  buf,
uint8_t  counter_max_length 
)

Write buckets from an ibf to a buffer.

Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.

Parameters
ibfthe ibf to write
startwith which bucket to start
counthow many buckets to write
bufbuffer to write the data to
maxbit length of a counter for unpacking

Definition at line 323 of file ibf.c.

References GNUNET_assert, GNUNET_memcpy, InvertibleBloomFilter::key_hash_sum, InvertibleBloomFilter::key_sum, pack_counter(), and size.

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 }
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
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 char buf[2048]
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
static unsigned int size
Size of the "table".
Definition: peer.c:67
Hash of an IBF key.
Definition: ibf.h:54
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
Here is the call graph for this function:

◆ pack_counter()

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 the counter.

Parameters
ibfthe ibf to write
startwith which bucket to start
counthow many buckets to write
bufbuffer to write the data to
maxbit length of a counter for unpacking

Iterate over IBF bucket

Pack and compose counters to byte values

Shift bits if more than a byte has to be written or the store size is not empty

Pack data left in story before finishing

Definition at line 369 of file ibf.c.

References InvertibleBloomFilter::count, IBF_Count::count_val, and start.

Referenced by ibf_write_slice().

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 }
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
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
static char buf[2048]
int8_t count_val
Definition: ibf.h:65
Here is the caller graph for this function:

◆ unpack_counter()

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 the counter.

Parameters
ibfthe ibf to write
startwith which bucket to start
counthow many buckets to write
bufbuffer to write the data to
maxbit length of a counter for unpacking

Iterate over received bytes

Pack data left in story before finishing

Stop decoding when end is reached

Definition at line 442 of file ibf.c.

References InvertibleBloomFilter::count, IBF_Count::count_val, and start.

Referenced by ibf_read_slice().

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 }
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
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
static char buf[2048]
int8_t count_val
Definition: ibf.h:65
Here is the caller graph for this function:

◆ ibf_read_slice()

void ibf_read_slice ( const void *  buf,
uint32_t  start,
uint64_t  count,
struct InvertibleBloomFilter ibf,
uint8_t  counter_max_length 
)

Read buckets from a buffer into an ibf.

Parameters
bufpointer to the buffer to read from
startwhich bucket to start at
counthow many buckets to read
ibfthe ibf to read from
maxbit length of a counter for unpacking

Definition at line 527 of file ibf.c.

References GNUNET_assert, GNUNET_memcpy, InvertibleBloomFilter::key_hash_sum, InvertibleBloomFilter::key_sum, size, and unpack_counter().

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;
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 }
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
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
static char buf[2048]
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
static unsigned int size
Size of the "table".
Definition: peer.c:67
Hash of an IBF key.
Definition: ibf.h:54
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
Here is the call graph for this function:

◆ ibf_subtract()

void ibf_subtract ( struct InvertibleBloomFilter ibf1,
const struct InvertibleBloomFilter ibf2 
)

Subtract ibf2 from ibf1, storing the result in ibf1.

The two IBF's must have the same parameters size and hash_num.

Parameters
ibf1IBF that is subtracted from
ibf2IBF that will be subtracted from ibf1

Definition at line 567 of file ibf.c.

References InvertibleBloomFilter::count, IBF_Count::count_val, GNUNET_assert, InvertibleBloomFilter::hash_num, InvertibleBloomFilter::key_hash_sum, IBF_KeyHash::key_hash_val, InvertibleBloomFilter::key_sum, IBF_Key::key_val, and InvertibleBloomFilter::size.

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 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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
uint64_t key_val
Definition: ibf.h:47
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint32_t key_hash_val
Definition: ibf.h:56
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
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

◆ ibf_dup()

struct InvertibleBloomFilter* ibf_dup ( const struct InvertibleBloomFilter ibf)

Create a copy of an IBF, the copy has to be destroyed properly.

Parameters
ibfthe IBF to copy

Definition at line 588 of file ibf.c.

References InvertibleBloomFilter::count, GNUNET_malloc, GNUNET_memdup, InvertibleBloomFilter::hash_num, InvertibleBloomFilter::key_hash_sum, InvertibleBloomFilter::key_sum, and InvertibleBloomFilter::size.

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 }
Invertible bloom filter (IBF).
Definition: ibf.h:82
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.
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:93
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
Hash of an IBF key.
Definition: ibf.h:54
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
#define GNUNET_malloc(size)
Wrapper around malloc.

◆ ibf_destroy()

void ibf_destroy ( struct InvertibleBloomFilter ibf)

Destroy all resources associated with the invertible bloom filter.

No more ibf_*-functions may be called on ibf after calling destroy.

Parameters
ibfthe intertible bloom filter to destroy

Definition at line 612 of file ibf.c.

References InvertibleBloomFilter::count, GNUNET_free, InvertibleBloomFilter::key_hash_sum, and InvertibleBloomFilter::key_sum.

613 {
614  GNUNET_free (ibf->key_sum);
615  GNUNET_free (ibf->key_hash_sum);
616  GNUNET_free (ibf->count);
617  GNUNET_free (ibf);
618 }
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
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:99
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:105
#define GNUNET_free(ptr)
Wrapper around free.