added skeleton for gnunet set

13 files changed, 1060 insertions, 10 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index d895b6095..ab51ee178 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -3,7 +3,7 @@
 #endif
 
 if HAVE_EXPERIMENTAL
- EXP_DIR = gns chat consensus dv 
+ EXP_DIR = gns chat consensus dv set 
 endif
 
 if LINUX
diff --git a/src/consensus/gnunet-service-consensus.c b/src/consensus/gnunet-service-consensus.c
index 179df0fb0..a7640c51f 100644
--- a/src/consensus/gnunet-service-consensus.c
+++ b/src/consensus/gnunet-service-consensus.c
@@ -2279,7 +2279,7 @@ add_incoming_peers (struct ConsensusSession *session)
 static void
 initialize_session (struct ConsensusSession *session)
 {
-  const struct ConsensusSession *other_session;
+  struct ConsensusSession *other_session;
 
   GNUNET_assert (NULL != session->join_msg);
   initialize_session_peer_list (session);
@@ -2295,17 +2295,13 @@ initialize_session (struct ConsensusSession *session)
     {
       if (GNUNET_NO == other_session->conclude)
       {
-        /* session already owned by another client */
         GNUNET_break (0);
-        disconnect_client (session->scss.client);
+        destroy_session (session);
         return;
       }
-      else
-      {
-        GNUNET_SERVER_client_drop (session->scss.client);
-        session->scss.client = NULL;
-        break;
-      }
+      GNUNET_SERVER_client_drop (other_session->scss.client);
+      other_session->scss.client = NULL;
+      break;
     }
     other_session = other_session->next;
   }
diff --git a/src/set/Makefile.am b/src/set/Makefile.am
new file mode 100644
index 000000000..fb6aa5b21
--- /dev/null
+++ b/src/set/Makefile.am
@@ -0,0 +1,72 @@
+INCLUDES = -I$(top_srcdir)/src/include
+
+pkgcfgdir= $(pkgdatadir)/config.d/
+
+libexecdir= $(pkglibdir)/libexec/
+
+pkgcfg_DATA = \
+  set.conf
+
+if MINGW
+ WINFLAGS = -Wl,--no-undefined -Wl,--export-all-symbols 
+endif
+
+if USE_COVERAGE
+  AM_CFLAGS = -fprofile-arcs -ftest-coverage
+endif
+
+bin_PROGRAMS = \
+ gnunet-set
+
+libexec_PROGRAMS = \
+ gnunet-service-set
+
+lib_LTLIBRARIES = \
+  libgnunetset.la
+
+gnunet_set_SOURCES = \
+ gnunet-set.c
+gnunet_set_LDADD = \
+  $(top_builddir)/src/util/libgnunetutil.la \
+  $(top_builddir)/src/set/libgnunetset.la \
+  $(top_builddir)/src/testbed/libgnunettestbed.la \
+  $(GN_LIBINTL)
+gnunet_set_DEPENDENCIES = \
+  libgnunetset.la
+
+gnunet_service_set_SOURCES = \
+ gnunet-service-set.c \
+ ibf.c \
+ strata_estimator.c
+gnunet_service_set_LDADD = \
+  $(top_builddir)/src/util/libgnunetutil.la \
+  $(top_builddir)/src/core/libgnunetcore.la \
+  $(top_builddir)/src/stream/libgnunetstream.la \
+  $(top_builddir)/src/mesh/libgnunetmesh.la \
+  $(GN_LIBINTL)
+
+libgnunetset_la_SOURCES = \
+  set_api.c
+libgnunetset_la_LIBADD = \
+  $(top_builddir)/src/util/libgnunetutil.la \
+  $(LTLIBINTL)
+libgnunetset_la_LDFLAGS = \
+  $(GN_LIB_LDFLAGS)
+
+check_PROGRAMS = \
+ test_set_api
+
+if ENABLE_TEST_RUN
+TESTS = $(check_PROGRAMS)
+endif
+
+test_set_api_SOURCES = \
+ test_set_api.c
+test_set_api_LDADD = \
+  $(top_builddir)/src/util/libgnunetutil.la \
+  $(top_builddir)/src/testing/libgnunettesting.la \
+  $(top_builddir)/src/set/libgnunetset.la
+
+EXTRA_DIST = \
+  test_set.conf
+
diff --git a/src/set/gnunet-service-set.c b/src/set/gnunet-service-set.c
new file mode 100644
index 000000000..9eaca990e
--- /dev/null
+++ b/src/set/gnunet-service-set.c
@@ -0,0 +1,71 @@
+/*
+      This file is part of GNUnet
+      (C) 2013 Christian Grothoff (and other contributing authors)
+
+      GNUnet is free software; you can redistribute it and/or modify
+      it under the terms of the GNU General Public License as published
+      by the Free Software Foundation; either version 2, or (at your
+      option) any later version.
+
+      GNUnet is distributed in the hope that it will be useful, but
+      WITHOUT ANY WARRANTY; without even the implied warranty of
+      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+      General Public License for more details.
+
+      You should have received a copy of the GNU General Public License
+      along with GNUnet; see the file COPYING.  If not, write to the
+      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+      Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file set/gnunet-service-set.c
+ * @brief two-peer set operations
+ * @author Florian Dold
+ */
+
+#include "platform.h"
+#include "gnunet_common.h"
+#include "gnunet_protocols.h"
+#include "gnunet_applications.h"
+#include "gnunet_util_lib.h"
+#include "gnunet_core_service.h"
+#include "gnunet_stream_lib.h"
+
+
+/**
+ * Function called by the service's run
+ * method to run service-specific setup code.
+ *
+ * @param cls closure
+ * @param server the initialized server
+ * @param cfg configuration to use
+ */
+static void
+run (void *cls,
+     struct GNUNET_SERVER_Handle * server,
+     const struct GNUNET_CONFIGURATION_Handle *
+     cfg)
+
+{
+  /* FIXME */
+}
+
+
+/**
+ * The main function for the set service.
+ *
+ * @param argc number of arguments from the command line
+ * @param argv command line arguments
+ * @return 0 ok, 1 on error
+ */
+int
+main (int argc, char *const *argv)
+{
+  int ret;
+  ret = GNUNET_SERVICE_run (argc, argv, "set", GNUNET_SERVICE_OPTION_NONE, &run, NULL);
+  GNUNET_log (GNUNET_ERROR_TYPE_INFO, "exit\n");
+  return (GNUNET_OK == ret) ? 0 : 1;
+}
+
+
diff --git a/src/set/gnunet-set.c b/src/set/gnunet-set.c
new file mode 100644
index 000000000..bb494ffe7
--- /dev/null
+++ b/src/set/gnunet-set.c
@@ -0,0 +1,62 @@
+/*
+      This file is part of GNUnet
+      (C) 2012 Christian Grothoff (and other contributing authors)
+
+      GNUnet is free software; you can redistribute it and/or modify
+      it under the terms of the GNU General Public License as published
+      by the Free Software Foundation; either version 2, or (at your
+      option) any later version.
+
+      GNUnet is distributed in the hope that it will be useful, but
+      WITHOUT ANY WARRANTY; without even the implied warranty of
+      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+      General Public License for more details.
+
+      You should have received a copy of the GNU General Public License
+      along with GNUnet; see the file COPYING.  If not, write to the
+      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+      Boston, MA 02111-1307, USA.
+ */
+
+/**
+ * @file set/gnunet-set.c
+ * @brief profiling tool for the set service
+ * @author Florian Dold
+ */
+#include "platform.h"
+#include "gnunet_common.h"
+#include "gnunet_util_lib.h"
+#include "gnunet_testbed_service.h"
+
+
+/**
+ * Main function that will be run.
+ *
+ * @param cls closure
+ * @param args remaining command-line arguments
+ * @param cfgfile name of the configuration file used (for saving, can be NULL!)
+ * @param cfg configuration
+ */
+static void
+run (void *cls, char *const *args,
+     const char *cfgfile,
+     const struct GNUNET_CONFIGURATION_Handle *
+     cfg)
+{
+  /* FIXME */
+}
+
+
+
+int
+main (int argc, char **argv)
+{
+   static const struct GNUNET_GETOPT_CommandLineOption options[] = {
+      GNUNET_GETOPT_OPTION_END
+  };
+  GNUNET_PROGRAM_run2 (argc, argv, "gnunet-set",
+                      "help",
+                      options, &run, NULL, GNUNET_YES);
+  return 0;
+}
+
diff --git a/src/set/ibf.c b/src/set/ibf.c
new file mode 100644
index 000000000..739b97339
--- /dev/null
+++ b/src/set/ibf.c
@@ -0,0 +1,357 @@
+/*
+      This file is part of GNUnet
+      (C) 2012 Christian Grothoff (and other contributing authors)
+
+      GNUnet is free software; you can redistribute it and/or modify
+      it under the terms of the GNU General Public License as published
+      by the Free Software Foundation; either version 2, or (at your
+      option) any later version.
+
+      GNUnet is distributed in the hope that it will be useful, but
+      WITHOUT ANY WARRANTY; without even the implied warranty of
+      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+      General Public License for more details.
+
+      You should have received a copy of the GNU General Public License
+      along with GNUnet; see the file COPYING.  If not, write to the
+      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+      Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file consensus/ibf.c
+ * @brief implementation of the invertible bloom filter
+ * @author Florian Dold
+ */
+
+#include "ibf.h"
+
+/**
+ * Create a key from a hashcode.
+ *
+ * @param hash the hashcode
+ * @return a key
+ */
+struct IBF_Key
+ibf_key_from_hashcode (const struct GNUNET_HashCode *hash)
+{
+  /* 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;
+}
+
+
+/**
+ * Create an invertible bloom filter.
+ *
+ * @param size number of IBF buckets
+ * @param hash_num number of buckets one element is hashed in
+ * @return the newly created invertible bloom filter
+ */
+struct InvertibleBloomFilter *
+ibf_create (uint32_t size, uint8_t hash_num)
+{
+  struct InvertibleBloomFilter *ibf;
+
+  /* TODO: use malloc_large */
+
+  ibf = GNUNET_malloc (sizeof (struct InvertibleBloomFilter));
+  ibf->count = GNUNET_malloc (size * sizeof (uint8_t));
+  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;
+}
+
+/**
+ * Store unique bucket indices for the specified key in dst.
+ */
+static inline void
+ibf_get_indices (const struct InvertibleBloomFilter *ibf,
+                 struct IBF_Key key, int *dst)
+{
+  struct GNUNET_HashCode bucket_indices;
+  unsigned int filled;
+  int i;
+  GNUNET_CRYPTO_hash (&key, sizeof key, &bucket_indices);
+  filled = 0;
+  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 % 16] % ibf->size;
+    for (j = 0; j < filled; j++)
+      if (dst[j] == bucket)
+        goto try_next;
+    dst[filled++] = bucket;
+    try_next: ;
+  }
+}
+
+
+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++)
+  {
+    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 ibf the IBF
+ * @param key the element's hash code
+ */
+void
+ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key)
+{
+  int buckets[ibf->hash_num];
+  GNUNET_assert (ibf->hash_num <= ibf->size);
+  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++)
+  {
+    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;
+  }
+  return GNUNET_YES;
+}
+
+
+/**
+ * Decode and remove an element from the IBF, if possible.
+ *
+ * @param ibf the invertible bloom filter to decode
+ * @param ret_side sign 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.
+ * @param ret_id receives the hash code of the decoded element, if successful
+ * @return GNUNET_YES if decoding an element was successful,
+ *         GNUNET_NO if the IBF is empty,
+ *         GNUNET_SYSERR if the decoding has failed
+ */
+int
+ibf_decode (struct InvertibleBloomFilter *ibf,
+            int *ret_side, struct IBF_Key *ret_id)
+{
+  struct IBF_KeyHash hash;
+  int i;
+  struct GNUNET_HashCode key_hash_sha;
+  int buckets[ibf->hash_num];
+
+  GNUNET_assert (NULL != ibf);
+
+  for (i = 0; i < ibf->size; 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;
+
+    /* 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 (GNUNET_NO == hit)
+      continue;
+
+    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_into (ibf, ibf->key_sum[i], buckets, -ibf->count[i].count_val);
+
+    return GNUNET_YES;
+  }
+
+  if (GNUNET_YES == ibf_is_empty (ibf))
+    return GNUNET_NO;
+  return GNUNET_SYSERR;
+}
+
+
+/**
+ * Write buckets from an ibf to a buffer.
+ * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
+ * 
+ * @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
+ */
+void
+ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
+{
+  struct IBF_Key *key_dst;
+  struct IBF_KeyHash *key_hash_dst;
+  struct IBF_Count *count_dst;
+
+  GNUNET_assert (start + count <= ibf->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;
+}
+
+
+/**
+ * Read buckets from a buffer into an ibf.
+ *
+ * @param buf pointer to the buffer to read from
+ * @param start which bucket to start at
+ * @param count how many buckets to read
+ * @param ibf the ibf to read from
+ */
+void
+ibf_read_slice (const void *buf, 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;
+
+  GNUNET_assert (start + count <= ibf->size);
+
+  /* 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;
+}
+
+
+/**
+ * Subtract ibf2 from ibf1, storing the result in ibf1.
+ * The two IBF's must have the same parameters size and hash_num.
+ *
+ * @param ibf1 IBF that is subtracted from
+ * @param ibf2 IBF that will be subtracted from ibf1
+ */
+void
+ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
+{
+  int i;
+
+  GNUNET_assert (ibf1->size == ibf2->size);
+  GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
+
+  for (i = 0; i < ibf1->size; 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->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);
+}
+
diff --git a/src/set/ibf.h b/src/set/ibf.h
new file mode 100644
index 000000000..2bf3ef7c7
--- /dev/null
+++ b/src/set/ibf.h
@@ -0,0 +1,224 @@
+/*
+      This file is part of GNUnet
+      (C) 2012 Christian Grothoff (and other contributing authors)
+
+      GNUnet is free software; you can redistribute it and/or modify
+      it under the terms of the GNU General Public License as published
+      by the Free Software Foundation; either version 2, or (at your
+      option) any later version.
+
+      GNUnet is distributed in the hope that it will be useful, but
+      WITHOUT ANY WARRANTY; without even the implied warranty of
+      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+      General Public License for more details.
+
+      You should have received a copy of the GNU General Public License
+      along with GNUnet; see the file COPYING.  If not, write to the
+      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+      Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file consensus/ibf.h
+ * @brief invertible bloom filter
+ * @author Florian Dold
+ */
+
+#ifndef GNUNET_CONSENSUS_IBF_H
+#define GNUNET_CONSENSUS_IBF_H
+
+#include "platform.h"
+#include "gnunet_common.h"
+#include "gnunet_util_lib.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#if 0                           /* keep Emacsens' auto-indent happy */
+}
+#endif
+#endif
+
+
+struct IBF_Key
+{
+  uint64_t key_val;
+};
+
+struct IBF_KeyHash
+{
+  uint32_t key_hash_val;
+};
+
+struct IBF_Count
+{
+  int8_t count_val;
+};
+
+/**
+ * Size of one ibf bucket in bytes
+ */
+#define IBF_BUCKET_SIZE (sizeof (struct IBF_Count) + sizeof (struct IBF_Key) + \
+    sizeof (struct IBF_KeyHash))
+
+/**
+ * Invertible bloom filter (IBF).
+ *
+ * An IBF is a counting bloom filter that has the ability to restore
+ * the hashes of its stored elements with high probability.
+ */
+struct InvertibleBloomFilter
+{
+  /**
+   * How many cells does this IBF have?
+   */
+  uint32_t size;
+
+  /**
+   * In how many cells do we hash one element?
+   * Usually 4 or 3.
+   */
+  uint8_t hash_num;
+
+  /**
+   * Xor sums of the elements' keys, used to identify the elements.
+   * Array of 'size' elements.
+   */
+  struct IBF_Key *key_sum;
+
+  /**
+   * Xor sums of the hashes of the keys of inserted elements.
+   * Array of 'size' elements.
+   */
+  struct IBF_KeyHash *key_hash_sum;
+
+  /**
+   * How many times has a bucket been hit?
+   * Can be negative, as a result of IBF subtraction.
+   * Array of 'size' elements.
+   */
+  struct IBF_Count *count;
+};
+
+
+/**
+ * Write buckets from an ibf to a buffer.
+ * Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
+ * 
+ * @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
+ */
+void
+ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf);
+
+
+/**
+ * Read buckets from a buffer into an ibf.
+ *
+ * @param buf pointer to the buffer to read from
+ * @param start which bucket to start at
+ * @param count how many buckets to read
+ * @param ibf the ibf to read from
+ */
+void
+ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf);
+
+
+/**
+ * Create a key from a hashcode.
+ *
+ * @param hash the hashcode
+ * @return a key
+ */
+struct IBF_Key
+ibf_key_from_hashcode (const struct GNUNET_HashCode *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);
+
+
+/**
+ * Create an invertible bloom filter.
+ *
+ * @param size number of IBF buckets
+ * @param hash_num number of buckets one element is hashed in, usually 3 or 4
+ * @return the newly created invertible bloom filter
+ */
+struct InvertibleBloomFilter *
+ibf_create (uint32_t size, uint8_t hash_num);
+
+
+/**
+ * Insert an element into an IBF.
+ *
+ * @param ibf the IBF
+ * @param key the element's hash code
+ */
+void
+ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
+
+
+/**
+ * Subtract ibf2 from ibf1, storing the result in ibf1.
+ * The two IBF's must have the same parameters size and hash_num.
+ *
+ * @param ibf1 IBF that is subtracted from
+ * @param ibf2 IBF that will be subtracted from ibf1
+ */
+void
+ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2);
+
+
+/**
+ * Decode and remove an element from the IBF, if possible.
+ *
+ * @param ibf the invertible bloom filter to decode
+ * @param ret_side sign 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.
+ * @param ret_id receives the hash code of the decoded element, if successful
+ * @return GNUNET_YES if decoding an element was successful,
+ *         GNUNET_NO if the IBF is empty,
+ *         GNUNET_SYSERR if the decoding has failed
+ */
+int
+ibf_decode (struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id);
+
+
+/**
+ * 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);
+
+/**
+ * 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);
+
+
+#if 0                           /* keep Emacsens' auto-indent happy */
+{
+#endif
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
diff --git a/src/set/set.conf.in b/src/set/set.conf.in
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/src/set/set.conf.in
diff --git a/src/set/set_api.c b/src/set/set_api.c
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/src/set/set_api.c
diff --git a/src/set/strata_estimator.c b/src/set/strata_estimator.c
new file mode 100644
index 000000000..685c50f0f
--- /dev/null
+++ b/src/set/strata_estimator.c
@@ -0,0 +1,145 @@
+/*
+      This file is part of GNUnet
+      (C) 2012 Christian Grothoff (and other contributing authors)
+
+      GNUnet is free software; you can redistribute it and/or modify
+      it under the terms of the GNU General Public License as published
+      by the Free Software Foundation; either version 2, or (at your
+      option) any later version.
+
+      GNUnet is distributed in the hope that it will be useful, but
+      WITHOUT ANY WARRANTY; without even the implied warranty of
+      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+      General Public License for more details.
+
+      You should have received a copy of the GNU General Public License
+      along with GNUnet; see the file COPYING.  If not, write to the
+      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+      Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file consensus/ibf.h
+ * @brief invertible bloom filter
+ * @author Florian Dold
+ */
+
+#include "platform.h"
+#include "gnunet_common.h"
+#include "ibf.h"
+#include "strata_estimator.h"
+
+void
+strata_estimator_write (const struct StrataEstimator *se, void *buf)
+{
+  int i;
+  for (i = 0; i < se->strata_count; i++)
+  {
+    ibf_write_slice (se->strata[i], 0, se->ibf_size, buf);
+    buf += se->ibf_size * IBF_BUCKET_SIZE;
+  }
+}
+
+void
+strata_estimator_read (const void *buf, struct StrataEstimator *se)
+{
+  int i;
+  for (i = 0; i < se->strata_count; i++)
+  {
+    ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
+    buf += se->ibf_size * IBF_BUCKET_SIZE;
+  }
+}
+
+
+void
+strata_estimator_insert (struct StrataEstimator *se, struct GNUNET_HashCode *key)
+{
+  uint32_t v;
+  int i;
+  v = key->bits[0];
+  /* count trailing '1'-bits of v */
+  for (i = 0; v & 1; v>>=1, i++)
+    /* empty */;
+  ibf_insert (se->strata[i], ibf_key_from_hashcode (key));
+}
+
+
+
+struct StrataEstimator *
+strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
+{
+  struct StrataEstimator *se;
+  int i;
+
+  /* fixme: allocate everything in one chunk */
+
+  se = GNUNET_malloc (sizeof (struct StrataEstimator));
+  se->strata_count = strata_count;
+  se->ibf_size = ibf_size;
+  se->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * strata_count);
+  for (i = 0; i < strata_count; i++)
+    se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
+  return se;
+}
+
+
+/**
+ * Estimate set difference with two strata estimators,
+ * i.e. arrays of IBFs.
+ * Does not not modify its arguments.
+ *
+ * @param se1 first strata estimator
+ * @param se2 second strata estimator
+ * @return the estimated difference
+ */
+unsigned int
+strata_estimator_difference (const struct StrataEstimator *se1,
+                             const struct StrataEstimator *se2)
+{
+  int i;
+  int count;
+
+  GNUNET_assert (se1->strata_count == se2->strata_count);
+  count = 0;
+  for (i = se1->strata_count - 1; i >= 0; i--)
+  {
+    struct InvertibleBloomFilter *diff;
+    /* number of keys decoded from the ibf */
+    int ibf_count;
+    int more;
+    ibf_count = 0;
+    /* FIXME: implement this without always allocating new IBFs */
+    diff = ibf_dup (se1->strata[i]);
+    ibf_subtract (diff, se2->strata[i]);
+    for (;;)
+    {
+      more = ibf_decode (diff, NULL, NULL);
+      if (GNUNET_NO == more)
+      {
+        count += ibf_count;
+        break;
+      }
+      if (GNUNET_SYSERR == more)
+      {
+        ibf_destroy (diff);
+        return count * (1 << (i + 1));
+      }
+      ibf_count++;
+    }
+    ibf_destroy (diff);
+  }
+  return count;
+}
+
+
+void
+strata_estimator_destroy (struct StrataEstimator *se)
+{
+  int i;
+  for (i = 0; i < se->strata_count; i++)
+    ibf_destroy (se->strata[i]);
+  GNUNET_free (se->strata);
+  GNUNET_free (se);
+}
+
diff --git a/src/set/strata_estimator.h b/src/set/strata_estimator.h
new file mode 100644
index 000000000..cb5bd3d0a
--- /dev/null
+++ b/src/set/strata_estimator.h
@@ -0,0 +1,84 @@
+/*
+      This file is part of GNUnet
+      (C) 2012 Christian Grothoff (and other contributing authors)
+
+      GNUnet is free software; you can redistribute it and/or modify
+      it under the terms of the GNU General Public License as published
+      by the Free Software Foundation; either version 2, or (at your
+      option) any later version.
+
+      GNUnet is distributed in the hope that it will be useful, but
+      WITHOUT ANY WARRANTY; without even the implied warranty of
+      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+      General Public License for more details.
+
+      You should have received a copy of the GNU General Public License
+      along with GNUnet; see the file COPYING.  If not, write to the
+      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+      Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file consensus/strata_estimator.h
+ * @brief estimator of set difference
+ * @author Florian Dold
+ */
+
+#ifndef GNUNET_CONSENSUS_STRATA_ESTIMATOR_H
+#define GNUNET_CONSENSUS_STRATA_ESTIMATOR_H
+
+#include "platform.h"
+#include "gnunet_common.h"
+#include "gnunet_util_lib.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#if 0                           /* keep Emacsens' auto-indent happy */
+}
+#endif
+#endif
+
+
+struct StrataEstimator
+{
+  struct InvertibleBloomFilter **strata;
+  unsigned int strata_count;
+  unsigned int ibf_size;
+};
+
+
+void
+strata_estimator_write (const struct StrataEstimator *se, void *buf);
+
+
+void
+strata_estimator_read (const void *buf, struct StrataEstimator *se);
+
+
+struct StrataEstimator *
+strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum);
+
+
+unsigned int
+strata_estimator_difference (const struct StrataEstimator *se1,
+                             const struct StrataEstimator *se2);
+
+
+void
+strata_estimator_insert (struct StrataEstimator *se, struct GNUNET_HashCode *key);
+
+
+void
+strata_estimator_destroy (struct StrataEstimator *se);
+
+
+#if 0                           /* keep Emacsens' auto-indent happy */
+{
+#endif
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+
diff --git a/src/set/test_set.conf b/src/set/test_set.conf
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/src/set/test_set.conf
diff --git a/src/set/test_set_api.c b/src/set/test_set_api.c
new file mode 100644
index 000000000..f9e027a86
--- /dev/null
+++ b/src/set/test_set_api.c
@@ -0,0 +1,39 @@
+/*
+     This file is part of GNUnet.
+     (C) 2012 Christian Grothoff (and other contributing authors)
+
+     GNUnet is free software; you can redistribute it and/or modify
+     it under the terms of the GNU General Public License as published
+     by the Free Software Foundation; either version 3, or (at your
+     option) any later version.
+
+     GNUnet is distributed in the hope that it will be useful, but
+     WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+     General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with GNUnet; see the file COPYING.  If not, write to the
+     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+     Boston, MA 02111-1307, USA.
+*/
+
+/**
+ * @file set/test_set_api.c
+ * @brief testcase for consensus_api.c
+ */
+#include "platform.h"
+#include "gnunet_util_lib.h"
+#include "gnunet_testing_lib.h"
+
+int
+main (int argc, char **argv)
+{
+  int ret;
+
+  ret = GNUNET_TESTING_peer_run ("test_set_api",
+                                 "test_set.conf",
+                                 &run, NULL);
+  return ret;
+}
+