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 
27 #include "ibf.h"
28 
33 #define IBF_KEY_HASH_VAL(k) (GNUNET_CRYPTO_crc32_n (&(k), sizeof(struct \
34  IBF_KeyHash)))
35 
42 struct IBF_Key
44 {
45  return *(struct IBF_Key *) hash;
46 }
47 
48 
56 void
58  struct GNUNET_HashCode *dst)
59 {
60  struct IBF_Key *p;
61  const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode)
62  / sizeof(struct IBF_Key);
63 
64  p = (struct IBF_Key *) dst;
65  for (unsigned int i = 0; i < keys_per_hashcode; i++)
66  *p++ = key;
67 }
68 
69 
77 struct InvertibleBloomFilter *
78 ibf_create (uint32_t size,
79  uint8_t hash_num)
80 {
81  struct InvertibleBloomFilter *ibf;
82 
83  GNUNET_assert (0 != size);
84  ibf = GNUNET_new (struct InvertibleBloomFilter);
85  ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t));
86  if (NULL == ibf->count)
87  {
88  GNUNET_free (ibf);
89  return NULL;
90  }
91  ibf->key_sum = GNUNET_malloc_large (size * sizeof(struct IBF_Key));
92  if (NULL == ibf->key_sum)
93  {
94  GNUNET_free (ibf->count);
95  GNUNET_free (ibf);
96  return NULL;
97  }
98  ibf->key_hash_sum = GNUNET_malloc_large (size * sizeof(struct IBF_KeyHash));
99  if (NULL == ibf->key_hash_sum)
100  {
101  GNUNET_free (ibf->key_sum);
102  GNUNET_free (ibf->count);
103  GNUNET_free (ibf);
104  return NULL;
105  }
106  ibf->size = size;
107  ibf->hash_num = hash_num;
108  return ibf;
109 }
110 
111 
115 static void
117  struct IBF_Key key,
118  int *dst)
119 {
120  uint32_t filled;
121  uint32_t i;
122  uint32_t bucket;
123 
124  bucket = GNUNET_CRYPTO_crc32_n (&key,
125  sizeof (key));
126  for (i = 0, filled = 0; filled < ibf->hash_num; i++)
127  {
128  uint64_t x;
129 
130  for (unsigned int j = 0; j < filled; j++)
131  if (dst[j] == bucket % ibf->size)
132  goto try_next;
133  dst[filled++] = bucket % ibf->size;
134 try_next:
135  x = ((uint64_t) bucket << 32) | i;
136  bucket = GNUNET_CRYPTO_crc32_n (&x,
137  sizeof (x));
138  }
139 }
140 
141 
142 static void
144  struct IBF_Key key,
145  const int *buckets,
146  int side)
147 {
148  for (unsigned int i = 0; i < ibf->hash_num; i++)
149  {
150  const int bucket = buckets[i];
151 
152  ibf->count[bucket].count_val += side;
153  ibf->key_sum[bucket].key_val ^= key.key_val;
154  ibf->key_hash_sum[bucket].key_hash_val
155  ^= IBF_KEY_HASH_VAL (key);
156  }
157 }
158 
159 
166 void
168  struct IBF_Key key)
169 {
170  int buckets[ibf->hash_num];
171 
172  GNUNET_assert (ibf->hash_num <= ibf->size);
173  ibf_get_indices (ibf,
174  key,
175  buckets);
176  ibf_insert_into (ibf,
177  key,
178  buckets,
179  1);
180 }
181 
182 
189 void
191  struct IBF_Key key)
192 {
193  int buckets[ibf->hash_num];
194 
195  GNUNET_assert (ibf->hash_num <= ibf->size);
196  ibf_get_indices (ibf,
197  key,
198  buckets);
199  ibf_insert_into (ibf,
200  key,
201  buckets,
202  -1);
203 }
204 
205 
209 static int
211 {
212  for (uint32_t i = 0; i < ibf->size; i++)
213  {
214  if (0 != ibf->count[i].count_val)
215  return GNUNET_NO;
216  if (0 != ibf->key_hash_sum[i].key_hash_val)
217  return GNUNET_NO;
218  if (0 != ibf->key_sum[i].key_val)
219  return GNUNET_NO;
220  }
221  return GNUNET_YES;
222 }
223 
224 
237 int
239  int *ret_side,
240  struct IBF_Key *ret_id)
241 {
242  struct IBF_KeyHash hash;
243  int buckets[ibf->hash_num];
244 
245  for (uint32_t i = 0; i < ibf->size; i++)
246  {
247  /* we can only decode from pure buckets */
248  if ( (1 != ibf->count[i].count_val) &&
249  (-1 != ibf->count[i].count_val) )
250  continue;
251 
252  hash.key_hash_val = IBF_KEY_HASH_VAL (ibf->key_sum[i]);
253 
254  /* test if the hash matches the key */
255  if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
256  continue;
257 
258  /* test if key in bucket hits its own location,
259  * if not, the key hash was subject to collision */
260  {
261  bool hit = false;
262 
263  ibf_get_indices (ibf,
264  ibf->key_sum[i],
265  buckets);
266  for (int j = 0; j < ibf->hash_num; j++)
267  if (buckets[j] == i)
268  {
269  hit = true;
270  break;
271  }
272  if (! hit)
273  continue;
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,
282  ibf->key_sum[i], buckets,
283  -ibf->count[i].count_val);
284  return GNUNET_YES;
285  }
286 
287  if (GNUNET_YES == ibf_is_empty (ibf))
288  return GNUNET_NO;
289  return GNUNET_SYSERR;
290 }
291 
292 
302 void
304  uint32_t start,
305  uint32_t count,
306  void *buf)
307 {
308  struct IBF_Key *key_dst;
309  struct IBF_KeyHash *key_hash_dst;
310  struct IBF_Count *count_dst;
311 
312  GNUNET_assert (start + count <= ibf->size);
313 
314  /* copy keys */
315  key_dst = (struct IBF_Key *) buf;
316  GNUNET_memcpy (key_dst,
317  ibf->key_sum + start,
318  count * sizeof *key_dst);
319  key_dst += count;
320  /* copy key hashes */
321  key_hash_dst = (struct IBF_KeyHash *) key_dst;
322  GNUNET_memcpy (key_hash_dst,
323  ibf->key_hash_sum + start,
324  count * sizeof *key_hash_dst);
325  key_hash_dst += count;
326  /* copy counts */
327  count_dst = (struct IBF_Count *) key_hash_dst;
328  GNUNET_memcpy (count_dst,
329  ibf->count + start,
330  count * sizeof *count_dst);
331 }
332 
333 
342 void
343 ibf_read_slice (const void *buf,
344  uint32_t start,
345  uint32_t count,
346  struct InvertibleBloomFilter *ibf)
347 {
348  struct IBF_Key *key_src;
349  struct IBF_KeyHash *key_hash_src;
350  struct IBF_Count *count_src;
351 
352  GNUNET_assert (count > 0);
353  GNUNET_assert (start + count <= ibf->size);
354 
355  /* copy keys */
356  key_src = (struct IBF_Key *) buf;
357  GNUNET_memcpy (ibf->key_sum + start,
358  key_src,
359  count * sizeof *key_src);
360  key_src += count;
361  /* copy key hashes */
362  key_hash_src = (struct IBF_KeyHash *) key_src;
363  GNUNET_memcpy (ibf->key_hash_sum + start,
364  key_hash_src,
365  count * sizeof *key_hash_src);
366  key_hash_src += count;
367  /* copy counts */
368  count_src = (struct IBF_Count *) key_hash_src;
369  GNUNET_memcpy (ibf->count + start,
370  count_src,
371  count * sizeof *count_src);
372 }
373 
374 
382 void
384  const struct InvertibleBloomFilter *ibf2)
385 {
386  GNUNET_assert (ibf1->size == ibf2->size);
387  GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
388 
389  for (uint32_t i = 0; i < ibf1->size; i++)
390  {
391  ibf1->count[i].count_val -= ibf2->count[i].count_val;
392  ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
393  ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
394  }
395 }
396 
397 
403 struct InvertibleBloomFilter *
404 ibf_dup (const struct InvertibleBloomFilter *ibf)
405 {
406  struct InvertibleBloomFilter *copy;
407 
408  copy = GNUNET_malloc (sizeof *copy);
409  copy->hash_num = ibf->hash_num;
410  copy->size = ibf->size;
412  ibf->size * sizeof(struct IBF_KeyHash));
413  copy->key_sum = GNUNET_memdup (ibf->key_sum,
414  ibf->size * sizeof(struct IBF_Key));
415  copy->count = GNUNET_memdup (ibf->count,
416  ibf->size * sizeof(struct IBF_Count));
417  return copy;
418 }
419 
420 
427 void
429 {
430  GNUNET_free (ibf->key_sum);
431  GNUNET_free (ibf->key_hash_sum);
432  GNUNET_free (ibf->count);
433  GNUNET_free (ibf);
434 }
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:184
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
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.
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:143
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
static int ibf_is_empty(struct InvertibleBloomFilter *ibf)
Test is the IBF is empty, i.e.
Definition: ibf.c:210
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:33
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:116
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
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.