GNUnet  0.10.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 IBF_KeyHash)))
34 
41 struct IBF_Key
43 {
44  return *(struct IBF_Key *)hash;
45 }
46 
54 void
56  struct GNUNET_HashCode *dst)
57 {
58  struct IBF_Key *p;
59  unsigned int i;
60  const unsigned int keys_per_hashcode = sizeof(struct GNUNET_HashCode) / sizeof(struct IBF_Key);
61 
62  p = (struct IBF_Key *)dst;
63  for (i = 0; i < keys_per_hashcode; i++)
64  *p++ = key;
65 }
66 
67 
75 struct InvertibleBloomFilter *
76 ibf_create(uint32_t size, uint8_t hash_num)
77 {
78  struct InvertibleBloomFilter *ibf;
79 
80  GNUNET_assert(0 != size);
81 
82  ibf = GNUNET_new(struct InvertibleBloomFilter);
83  ibf->count = GNUNET_malloc_large(size * sizeof(uint8_t));
84  if (NULL == ibf->count)
85  {
86  GNUNET_free(ibf);
87  return NULL;
88  }
89  ibf->key_sum = GNUNET_malloc_large(size * sizeof(struct IBF_Key));
90  if (NULL == ibf->key_sum)
91  {
92  GNUNET_free(ibf->count);
93  GNUNET_free(ibf);
94  return NULL;
95  }
96  ibf->key_hash_sum = GNUNET_malloc_large(size * sizeof(struct IBF_KeyHash));
97  if (NULL == ibf->key_hash_sum)
98  {
99  GNUNET_free(ibf->key_sum);
100  GNUNET_free(ibf->count);
101  GNUNET_free(ibf);
102  return NULL;
103  }
104  ibf->size = size;
105  ibf->hash_num = hash_num;
106 
107  return ibf;
108 }
109 
110 
114 static void
116  struct IBF_Key key,
117  int *dst)
118 {
119  uint32_t filled;
120  uint32_t i;
121  uint32_t bucket;
122 
123  bucket = GNUNET_CRYPTO_crc32_n(&key, sizeof key);
124  for (i = 0, filled = 0; filled < ibf->hash_num; i++)
125  {
126  unsigned int j;
127  uint64_t x;
128  for (j = 0; j < filled; j++)
129  if (dst[j] == bucket)
130  goto try_next;
131  dst[filled++] = bucket % ibf->size;
132 try_next:;
133  x = ((uint64_t)bucket << 32) | i;
134  bucket = GNUNET_CRYPTO_crc32_n(&x, sizeof x);
135  }
136 }
137 
138 
139 static void
141  struct IBF_Key key,
142  const int *buckets, int side)
143 {
144  int i;
145 
146  for (i = 0; i < ibf->hash_num; i++)
147  {
148  const int bucket = buckets[i];
149  ibf->count[bucket].count_val += side;
150  ibf->key_sum[bucket].key_val ^= key.key_val;
151  ibf->key_hash_sum[bucket].key_hash_val
152  ^= IBF_KEY_HASH_VAL(key);
153  }
154 }
155 
156 
163 void
165 {
166  int buckets[ibf->hash_num];
167 
168  GNUNET_assert(ibf->hash_num <= ibf->size);
169  ibf_get_indices(ibf, key, buckets);
170  ibf_insert_into(ibf, key, buckets, 1);
171 }
172 
173 
180 void
182 {
183  int buckets[ibf->hash_num];
184 
185  GNUNET_assert(ibf->hash_num <= ibf->size);
186  ibf_get_indices(ibf, key, buckets);
187  ibf_insert_into(ibf, key, buckets, -1);
188 }
189 
190 
194 static int
196 {
197  int i;
198 
199  for (i = 0; i < ibf->size; i++)
200  {
201  if (0 != ibf->count[i].count_val)
202  return GNUNET_NO;
203  if (0 != ibf->key_hash_sum[i].key_hash_val)
204  return GNUNET_NO;
205  if (0 != ibf->key_sum[i].key_val)
206  return GNUNET_NO;
207  }
208  return GNUNET_YES;
209 }
210 
211 
224 int
226  int *ret_side, struct IBF_Key *ret_id)
227 {
228  struct IBF_KeyHash hash;
229  int i;
230  int buckets[ibf->hash_num];
231 
232  GNUNET_assert(NULL != ibf);
233 
234  for (i = 0; i < ibf->size; i++)
235  {
236  int j;
237  int hit;
238 
239  /* we can only decode from pure buckets */
240  if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
241  continue;
242 
243  hash.key_hash_val = IBF_KEY_HASH_VAL(ibf->key_sum[i]);
244 
245  /* test if the hash matches the key */
246  if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
247  continue;
248 
249  /* test if key in bucket hits its own location,
250  * if not, the key hash was subject to collision */
251  hit = GNUNET_NO;
252  ibf_get_indices(ibf, ibf->key_sum[i], buckets);
253  for (j = 0; j < ibf->hash_num; j++)
254  if (buckets[j] == i)
255  hit = GNUNET_YES;
256 
257  if (GNUNET_NO == hit)
258  continue;
259 
260  if (NULL != ret_side)
261  *ret_side = ibf->count[i].count_val;
262  if (NULL != ret_id)
263  *ret_id = ibf->key_sum[i];
264 
265  /* insert on the opposite side, effectively removing the element */
266  ibf_insert_into(ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
267 
268  return GNUNET_YES;
269  }
270 
271  if (GNUNET_YES == ibf_is_empty(ibf))
272  return GNUNET_NO;
273  return GNUNET_SYSERR;
274 }
275 
276 
286 void
287 ibf_write_slice(const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
288 {
289  struct IBF_Key *key_dst;
290  struct IBF_KeyHash *key_hash_dst;
291  struct IBF_Count *count_dst;
292 
293  GNUNET_assert(start + count <= ibf->size);
294 
295  /* copy keys */
296  key_dst = (struct IBF_Key *)buf;
297  GNUNET_memcpy(key_dst, ibf->key_sum + start, count * sizeof *key_dst);
298  key_dst += count;
299  /* copy key hashes */
300  key_hash_dst = (struct IBF_KeyHash *)key_dst;
301  GNUNET_memcpy(key_hash_dst, ibf->key_hash_sum + start, count * sizeof *key_hash_dst);
302  key_hash_dst += count;
303  /* copy counts */
304  count_dst = (struct IBF_Count *)key_hash_dst;
305  GNUNET_memcpy(count_dst, ibf->count + start, count * sizeof *count_dst);
306 }
307 
308 
317 void
318 ibf_read_slice(const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
319 {
320  struct IBF_Key *key_src;
321  struct IBF_KeyHash *key_hash_src;
322  struct IBF_Count *count_src;
323 
324  GNUNET_assert(count > 0);
325  GNUNET_assert(start + count <= ibf->size);
326 
327  /* copy keys */
328  key_src = (struct IBF_Key *)buf;
329  GNUNET_memcpy(ibf->key_sum + start, key_src, count * sizeof *key_src);
330  key_src += count;
331  /* copy key hashes */
332  key_hash_src = (struct IBF_KeyHash *)key_src;
333  GNUNET_memcpy(ibf->key_hash_sum + start, key_hash_src, count * sizeof *key_hash_src);
334  key_hash_src += count;
335  /* copy counts */
336  count_src = (struct IBF_Count *)key_hash_src;
337  GNUNET_memcpy(ibf->count + start, count_src, count * sizeof *count_src);
338 }
339 
340 
348 void
350 {
351  int i;
352 
353  GNUNET_assert(ibf1->size == ibf2->size);
354  GNUNET_assert(ibf1->hash_num == ibf2->hash_num);
355 
356  for (i = 0; i < ibf1->size; i++)
357  {
358  ibf1->count[i].count_val -= ibf2->count[i].count_val;
359  ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
360  ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
361  }
362 }
363 
364 
370 struct InvertibleBloomFilter *
371 ibf_dup(const struct InvertibleBloomFilter *ibf)
372 {
373  struct InvertibleBloomFilter *copy;
374 
375  copy = GNUNET_malloc(sizeof *copy);
376  copy->hash_num = ibf->hash_num;
377  copy->size = ibf->size;
378  copy->key_hash_sum = GNUNET_memdup(ibf->key_hash_sum, ibf->size * sizeof(struct IBF_KeyHash));
379  copy->key_sum = GNUNET_memdup(ibf->key_sum, ibf->size * sizeof(struct IBF_Key));
380  copy->count = GNUNET_memdup(ibf->count, ibf->size * sizeof(struct IBF_Count));
381  return copy;
382 }
383 
384 
391 void
393 {
394  GNUNET_free(ibf->key_sum);
396  GNUNET_free(ibf->count);
397  GNUNET_free(ibf);
398 }
void ibf_remove(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Remove a key from an IBF.
Definition: ibf.c:181
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:105
struct IBF_Key * key_sum
Xor sums of the elements&#39; keys, used to identify the elements.
Definition: ibf.h:95
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:79
static void ibf_insert_into(struct InvertibleBloomFilter *ibf, struct IBF_Key key, const int *buckets, int side)
Definition: ibf.c:140
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_NO
Definition: gnunet_common.h:78
#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:46
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:287
#define GNUNET_malloc_large(size)
Wrapper around malloc.
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:371
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:83
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
uint32_t key_hash_val
Definition: ibf.h:54
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:225
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:55
static char buf[2048]
uint8_t hash_num
In how many cells do we hash one element? Usually 4 or 3.
Definition: ibf.h:89
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:349
#define IBF_KEY_HASH_VAL(k)
Compute the key&#39;s hash from the key.
Definition: ibf.c:33
A 512-bit hashcode.
Type of the count field of IBF buckets.
Definition: ibf.h:61
struct IBF_KeyHash * key_hash_sum
Xor sums of the hashes of the keys of inserted elements.
Definition: ibf.h:101
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:318
struct GNUNET_HashCode key
The key used in the DHT.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
invertible bloom filter
static unsigned int size
Size of the "table".
Definition: peer.c:66
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:392
static unsigned int hash_num
Hash of an IBF key.
Definition: ibf.h:53
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:76
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:164
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:115
int8_t count_val
Definition: ibf.h:62
#define GNUNET_YES
Definition: gnunet_common.h:77
static int ibf_is_empty(struct InvertibleBloomFilter *ibf)
Test is the IBF is empty, i.e.
Definition: ibf.c:195
struct IBF_Key ibf_key_from_hashcode(const struct GNUNET_HashCode *hash)
Create a key from a hashcode.
Definition: ibf.c:42
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:45
struct IBF_Count * count
How many times has a bucket been hit? Can be negative, as a result of IBF subtraction.
Definition: ibf.h:108
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.