Boston, MA 02111-1307, USA.
*/
-
/**
* @file consensus/ibf.c
* @brief implementation of the invertible bloom filter
#include "ibf.h"
-
/**
- * Opaque handle to an invertible bloom filter (IBF).
+ * Create a key from a hashcode.
*
- * An IBF is a counting bloom filter that has the ability to restore
- * the hashes of its stored elements with high probability.
+ * @param hash the hashcode
+ * @return a key
*/
-struct InvertibleBloomFilter
+struct IBF_Key
+ibf_key_from_hashcode (const struct GNUNET_HashCode *hash)
{
- /**
- * How many cells does this IBF have?
- */
- unsigned int size;
-
- /**
- * In how many cells do we hash one element?
- * Usually 4 or 3.
- */
- unsigned int hash_num;
-
- /**
- * Salt for mingling hashes
- */
- uint32_t salt;
-
- /**
- * How many times has a bucket been hit?
- * Can be negative, as a result of IBF subtraction.
- */
- int8_t *count;
-
- /**
- * xor sums of the elements' hash codes, used to identify the elements.
- */
- struct GNUNET_HashCode *id_sum;
-
- /**
- * xor sums of the "hash of the hash".
- */
- struct GNUNET_HashCode *hash_sum;
+ /* FIXME: endianess */
+ return *(struct IBF_Key *) hash;
+}
-};
+/**
+ * Create a hashcode from a key, by replicating the key
+ * until the hascode is filled
+ *
+ * @param key the key
+ * @param dst hashcode to store the result in
+ */
+void
+ibf_hashcode_from_key (struct IBF_Key key, struct GNUNET_HashCode *dst)
+{
+ struct IBF_Key *p;
+ unsigned int i;
+ const unsigned int keys_per_hashcode = sizeof (struct GNUNET_HashCode) / sizeof (struct IBF_Key);
+ p = (struct IBF_Key *) dst;
+ for (i = 0; i < keys_per_hashcode; i++)
+ *p++ = key;
+}
/**
* @return the newly created invertible bloom filter
*/
struct InvertibleBloomFilter *
-ibf_create (unsigned int size, unsigned int hash_num, uint32_t salt)
+ibf_create (uint32_t size, uint8_t hash_num, uint32_t salt)
{
struct InvertibleBloomFilter *ibf;
+ /* TODO: use malloc_large */
+
ibf = GNUNET_malloc (sizeof (struct InvertibleBloomFilter));
ibf->count = GNUNET_malloc (size * sizeof (uint8_t));
- ibf->id_sum = GNUNET_malloc (size * sizeof (struct GNUNET_HashCode));
- ibf->hash_sum = GNUNET_malloc (size * sizeof (struct GNUNET_HashCode));
+ ibf->key_sum = GNUNET_malloc (size * sizeof (struct GNUNET_HashCode));
+ ibf->key_hash_sum = GNUNET_malloc (size * sizeof (struct GNUNET_HashCode));
ibf->size = size;
ibf->hash_num = hash_num;
return ibf;
}
-
-
/**
- * Insert an element into an IBF, with either positive or negative sign.
- *
- * @param ibf the IBF
- * @param id the element's hash code
- * @param side the sign of side determines the sign of the
- * inserted element.
+ * Store unique bucket indices for the specified key in dst.
*/
-void
-ibf_insert_on_side (struct InvertibleBloomFilter *ibf,
- const struct GNUNET_HashCode *key,
- int side)
+static inline void
+ibf_get_indices (const struct InvertibleBloomFilter *ibf,
+ struct IBF_Key key, int *dst)
{
struct GNUNET_HashCode bucket_indices;
- struct GNUNET_HashCode key_copy;
- struct GNUNET_HashCode key_hash;
- int *used_buckets;
- unsigned int i;
-
-
- GNUNET_assert ((1 == side) || (-1 == side));
- GNUNET_assert (NULL != ibf);
-
- used_buckets = alloca (ibf->hash_num * sizeof (int));
-
- /* copy the key, if key and an entry in the IBF alias */
- key_copy = *key;
+ unsigned int filled = 0;
+ int i;
+ GNUNET_CRYPTO_hash (&key, sizeof key, &bucket_indices);
+ for (i = 0; filled < ibf->hash_num; i++)
+ {
+ unsigned int bucket;
+ unsigned int j;
+ if ( (0 != i) && (0 == (i % 16)) )
+ GNUNET_CRYPTO_hash (&bucket_indices, sizeof (struct GNUNET_HashCode), &bucket_indices);
+ bucket = bucket_indices.bits[i] % ibf->size;
+ for (j = 0; j < filled; j++)
+ if (dst[j] == bucket)
+ goto try_next;;
+ dst[filled++] = bucket;
+ try_next: ;
+ }
+}
- bucket_indices = key_copy;
- GNUNET_CRYPTO_hash (key, sizeof (struct GNUNET_HashCode), &key_hash);
+static void
+ibf_insert_into (struct InvertibleBloomFilter *ibf,
+ struct IBF_Key key,
+ const int *buckets, int side)
+{
+ int i;
+ struct GNUNET_HashCode key_hash_sha;
+ struct IBF_KeyHash key_hash;
+ GNUNET_CRYPTO_hash (&key, sizeof key, &key_hash_sha);
+ key_hash.key_hash_val = key_hash_sha.bits[0];
for (i = 0; i < ibf->hash_num; i++)
{
- unsigned int bucket;
- unsigned int j;
- int collided;
-
- if ((i % 16) == 0)
- GNUNET_CRYPTO_hash (&bucket_indices, sizeof (struct GNUNET_HashCode),
- &bucket_indices);
-
- bucket = bucket_indices.bits[i%16] % ibf->size;
- collided = GNUNET_NO;
- for (j = 0; j < i; j++)
- if (used_buckets[j] == bucket)
- collided = GNUNET_YES;
- if (GNUNET_YES == collided)
- {
- used_buckets[i] = -1;
- continue;
- }
- used_buckets[i] = bucket;
-
- ibf->count[bucket] += side;
-
- GNUNET_CRYPTO_hash_xor (&key_copy, &ibf->id_sum[bucket],
- &ibf->id_sum[bucket]);
- GNUNET_CRYPTO_hash_xor (&key_hash, &ibf->hash_sum[bucket],
- &ibf->hash_sum[bucket]);
+ const int bucket = buckets[i];
+ ibf->count[bucket].count_val += side;
+ ibf->key_sum[bucket].key_val ^= key.key_val;
+ ibf->key_hash_sum[bucket].key_hash_val ^= key_hash.key_hash_val;
}
}
+
/**
* Insert an element into an IBF.
*
* @param id the element's hash code
*/
void
-ibf_insert (struct InvertibleBloomFilter *ibf, const struct GNUNET_HashCode *key)
+ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
{
- ibf_insert_on_side (ibf, key, 1);
+ int buckets[ibf->hash_num];
+ ibf_get_indices (ibf, key, buckets);
+ ibf_insert_into (ibf, key, buckets, 1);
}
+/**
+ * Test is the IBF is empty, i.e. all counts, keys and key hashes are zero.
+ */
static int
ibf_is_empty (struct InvertibleBloomFilter *ibf)
{
int i;
for (i = 0; i < ibf->size; i++)
{
- int j;
- if (0 != ibf->count[i])
+ if (0 != ibf->count[i].count_val)
+ return GNUNET_NO;
+ if (0 != ibf->key_hash_sum[i].key_hash_val)
+ return GNUNET_NO;
+ if (0 != ibf->key_sum[i].key_val)
return GNUNET_NO;
- for (j = 0; j < 16; ++j)
- {
- if (0 != ibf->hash_sum[i].bits[j])
- return GNUNET_NO;
- if (0 != ibf->id_sum[i].bits[j])
- return GNUNET_NO;
- }
}
return GNUNET_YES;
}
*/
int
ibf_decode (struct InvertibleBloomFilter *ibf,
- int *ret_side, struct GNUNET_HashCode *ret_id)
+ int *ret_side, struct IBF_Key *ret_id)
{
- struct GNUNET_HashCode hash;
+ struct IBF_KeyHash hash;
int i;
+ struct GNUNET_HashCode key_hash_sha;
+ int buckets[ibf->hash_num];
GNUNET_assert (NULL != ibf);
- GNUNET_assert (NULL != ret_id);
- GNUNET_assert (NULL != ret_side);
for (i = 0; i < ibf->size; i++)
{
- if ((1 != ibf->count[i]) && (-1 != ibf->count[i]))
+ int j;
+ int hit;
+
+ /* we can only decode from pure buckets */
+ if ((1 != ibf->count[i].count_val) && (-1 != ibf->count[i].count_val))
+ continue;
+
+ GNUNET_CRYPTO_hash (&ibf->key_sum[i], sizeof (struct IBF_Key), &key_hash_sha);
+ hash.key_hash_val = key_hash_sha.bits[0];
+
+ /* test if the hash matches the key */
+ if (hash.key_hash_val != ibf->key_hash_sum[i].key_hash_val)
continue;
- GNUNET_CRYPTO_hash (&ibf->id_sum[i], sizeof (struct GNUNET_HashCode), &hash);
+ /* test if key in bucket hits its own location,
+ * if not, the key hash was subject to collision */
+ hit = GNUNET_NO;
+ ibf_get_indices (ibf, ibf->key_sum[i], buckets);
+ for (j = 0; j < ibf->hash_num; j++)
+ if (buckets[j] == i)
+ hit = GNUNET_YES;
- if (0 != memcmp (&hash, &ibf->hash_sum[i], sizeof (struct GNUNET_HashCode)))
+ if (GNUNET_NO == hit)
continue;
- *ret_side = ibf->count[i];
- *ret_id = ibf->id_sum[i];
+ if (NULL != ret_side)
+ *ret_side = ibf->count[i].count_val;
+ if (NULL != ret_id)
+ *ret_id = ibf->key_sum[i];
/* insert on the opposite side, effectively removing the element */
- ibf_insert_on_side (ibf, &ibf->id_sum[i], -ibf->count[i]);
+ ibf_insert_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
return GNUNET_YES;
}
}
+/**
+ * Write an ibf.
+ *
+ * @param ibf the ibf to write
+ * @param start with which bucket to start
+ * @param count how many buckets to write
+ * @param buf buffer to write the data to, will be updated to point to the
+ * first byte after the written data
+ * @param size pointer to the size of the buffer, will be updated, can be NULL
+ */
+void
+ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void **buf, size_t *size)
+{
+ struct IBF_Key *key_dst;
+ struct IBF_KeyHash *key_hash_dst;
+ struct IBF_Count *count_dst;
+
+ /* update size and check for overflow */
+ if (NULL != size)
+ {
+ size_t old_size;
+ old_size = *size;
+ *size = *size - count * IBF_BUCKET_SIZE;
+ GNUNET_assert (*size < old_size);
+ }
+ /* copy keys */
+ key_dst = (struct IBF_Key *) *buf;
+ memcpy (key_dst, ibf->key_sum + start, count * sizeof *key_dst);
+ key_dst += count;
+ /* copy key hashes */
+ key_hash_dst = (struct IBF_KeyHash *) key_dst;
+ memcpy (key_hash_dst, ibf->key_hash_sum + start, count * sizeof *key_hash_dst);
+ key_hash_dst += count;
+ /* copy counts */
+ count_dst = (struct IBF_Count *) key_hash_dst;
+ memcpy (count_dst, ibf->count + start, count * sizeof *count_dst);
+ count_dst += count;
+ /* returned buffer is at the end of written data*/
+ *buf = (void *) count_dst;
+}
+
+
+/**
+ * Read an ibf.
+ *
+ * @param buf pointer to the buffer to write to, will point to first
+ * byte after the written data
+ * @param size size of the buffer, will be updated
+ * @param start which bucket to start at
+ * @param count how many buckets to read
+ * @param dst ibf to write buckets to
+ * @return GNUNET_OK on success
+ */
+int
+ibf_read_slice (void **buf, size_t *size, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
+{
+ struct IBF_Key *key_src;
+ struct IBF_KeyHash *key_hash_src;
+ struct IBF_Count *count_src;
+
+ /* update size and check for overflow */
+ if (NULL != size)
+ {
+ size_t old_size;
+ old_size = *size;
+ *size = *size - count * IBF_BUCKET_SIZE;
+ if (*size > old_size)
+ return GNUNET_SYSERR;
+ }
+ /* copy keys */
+ key_src = (struct IBF_Key *) *buf;
+ memcpy (ibf->key_sum + start, key_src, count * sizeof *key_src);
+ key_src += count;
+ /* copy key hashes */
+ key_hash_src = (struct IBF_KeyHash *) key_src;
+ memcpy (ibf->key_hash_sum + start, key_hash_src, count * sizeof *key_hash_src);
+ key_hash_src += count;
+ /* copy counts */
+ count_src = (struct IBF_Count *) key_hash_src;
+ memcpy (ibf->count + start, count_src, count * sizeof *count_src);
+ count_src += count;
+ /* returned buffer is at the end of written data*/
+ *buf = (void *) count_src;
+ return GNUNET_OK;
+}
+
+
+/**
+ * Write an ibf.
+ *
+ * @param ibf the ibf to write
+ * @param start with which bucket to start
+ * @param count how many buckets to write
+ * @param buf buffer to write the data to, will be updated to point to the
+ * first byte after the written data
+ * @param size pointer to the size of the buffer, will be updated, can be NULL
+ */
+void
+ibf_write (const struct InvertibleBloomFilter *ibf, void **buf, size_t *size)
+{
+ ibf_write_slice (ibf, 0, ibf->size, buf, size);
+}
+
+
+/**
+ * Read an ibf.
+ *
+ * @param buf pointer to the buffer to write to, will point to first
+ * byte after the written data
+ * @param size size of the buffer, will be updated
+ * @param start which bucket to start at
+ * @param count how many buckets to read
+ * @param dst ibf to write buckets to
+ * @return GNUNET_OK on success
+ */
+int
+ibf_read (void **buf, size_t *size, struct InvertibleBloomFilter *dst)
+{
+ return ibf_read_slice (buf, size, 0, dst->size, dst);
+}
+
/**
* Subtract ibf2 from ibf1, storing the result in ibf1.
* @param ibf2 IBF that will be subtracted from ibf1
*/
void
-ibf_subtract (struct InvertibleBloomFilter *ibf1, struct InvertibleBloomFilter *ibf2)
+ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
{
int i;
for (i = 0; i < ibf1->size; i++)
{
- ibf1->count[i] -= ibf2->count[i];
- GNUNET_CRYPTO_hash_xor (&ibf1->id_sum[i], &ibf2->id_sum[i],
- &ibf1->id_sum[i]);
- GNUNET_CRYPTO_hash_xor (&ibf1->hash_sum[i], &ibf2->hash_sum[i],
- &ibf1->hash_sum[i]);
+ ibf1->count[i].count_val -= ibf2->count[i].count_val;
+ ibf1->key_hash_sum[i].key_hash_val ^= ibf2->key_hash_sum[i].key_hash_val;
+ ibf1->key_sum[i].key_val ^= ibf2->key_sum[i].key_val;
}
}
+
+/**
+ * Create a copy of an IBF, the copy has to be destroyed properly.
+ *
+ * @param ibf the IBF to copy
+ */
+struct InvertibleBloomFilter *
+ibf_dup (const struct InvertibleBloomFilter *ibf)
+{
+ struct InvertibleBloomFilter *copy;
+ copy = GNUNET_malloc (sizeof *copy);
+ copy->hash_num = ibf->hash_num;
+ copy->salt = ibf->salt;
+ copy->size = ibf->size;
+ copy->key_hash_sum = GNUNET_memdup (ibf->key_hash_sum, ibf->size * sizeof (struct IBF_KeyHash));
+ copy->key_sum = GNUNET_memdup (ibf->key_sum, ibf->size * sizeof (struct IBF_Key));
+ copy->count = GNUNET_memdup (ibf->count, ibf->size * sizeof (struct IBF_Count));
+ return copy;
+}
+
+
+/**
+ * Destroy all resources associated with the invertible bloom filter.
+ * No more ibf_*-functions may be called on ibf after calling destroy.
+ *
+ * @param ibf the intertible bloom filter to destroy
+ */
+void
+ibf_destroy (struct InvertibleBloomFilter *ibf)
+{
+ GNUNET_free (ibf->key_sum);
+ GNUNET_free (ibf->key_hash_sum);
+ GNUNET_free (ibf->count);
+ GNUNET_free (ibf);
+}
+
projects / oweals / gnunet.git / blobdiff