ibf_sim.c File Reference

implementation of simulation for invertible bloom filter More...

#include "platform.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

Include dependency graph for ibf_sim.c:

Go to the source code of this file.

Macros
#define	MAX_IBF_DECODE   16
#define	ROUNDS   100000
#define	FIX1   0
#define	FIX2   1
#define	STRATA   0
#define	VERBOSE   0
#define	SLOW   0

Functions
int	main (int argc, char **argv)

Detailed Description

implementation of simulation for invertible bloom filter

Author

Florian Dold

This code was used for some internal experiments, it is not build or shipped as part of the GNUnet system.

Definition in file ibf_sim.c.

Macro Definition Documentation

MAX_IBF_DECODE

#define MAX_IBF_DECODE   16

Definition at line 34 of file ibf_sim.c.

ROUNDS

#define ROUNDS   100000

Definition at line 37 of file ibf_sim.c.

FIX1

#define FIX1   0

Definition at line 41 of file ibf_sim.c.

FIX2

#define FIX2   1

Definition at line 43 of file ibf_sim.c.

STRATA

#define STRATA   0

Definition at line 46 of file ibf_sim.c.

VERBOSE

#define VERBOSE   0

Definition at line 49 of file ibf_sim.c.

SLOW

#define SLOW   0

Definition at line 51 of file ibf_sim.c.

Function Documentation

main()

int main	(	int	argc,
		char **	argv
	)

Definition at line 54 of file ibf_sim.c.

{
  unsigned int round;
  unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31
  unsigned int i;
  int j;
  unsigned int r;
  unsigned int ret;
  unsigned long long total;
  unsigned int want;
  double predict;
 
  srandom (time (NULL));
  total = 0;
  want = atoi (argv[1]);
  for (round = 0; round < ROUNDS; round++)
  {
    memset (buckets, 0, sizeof(buckets));
    for (i = 0; i < want; i++)
    {
      /* FIXME: might want to use 'better' PRNG to avoid
         PRNG-induced biases */
      r = random ();
      if (0 == r)
        continue;
#if SLOW
      for (j = 0; (j < 31) && (0 == (r & (1 << j))); j++)
        ;
#else
      /* use assembly / gcc */
      j = __builtin_ffs (r) - 1;
#endif
      buckets[j]++;
    }
    ret = 0;
    predict = 0.0;
    for (j = 31; j >= 0; j--)
    {
#if FIX1
      /* improved algorithm, for 1000 elements with IBF-DECODE 8, I
         get 990/1000 elements on average over 1 million runs; key
         idea being to stop short of the 'last' possible IBF as
         otherwise a "lowball" per-chance would unduely influence the
         result */if ((j > 0) &&
          (buckets[j - 1] > MAX_IBF_DECODE))
      {
        ret *= (1 << (j + 1));
        break;
      }
#endif
#if FIX2
      /* another improvement: don't just always cut off the last one,
         but rather try to predict based on all previous values where
         that "last" one is; additional prediction can only really
         work if MAX_IBF_DECODE is sufficiently high */
      if ((j > 0) &&
          ((buckets[j - 1] > MAX_IBF_DECODE) ||
           (predict > MAX_IBF_DECODE)))
      {
        ret *= (1 << (j + 1));
        break;
      }
#endif
#if STRATA
      /* original algorithm, for 1000 elements with IBF-DECODE 8,
         I get 920/1000 elements on average over 1 million runs */
      if (buckets[j] > MAX_IBF_DECODE)
      {
        ret *= (1 << (j + 1));
        break;
      }
#endif
      ret += buckets[j];
      predict = (buckets[j] + 2.0 * predict) / 2.0;
    }
#if VERBOSE
    fprintf (stderr, "%u ", ret);
#endif
    total += ret;
  }
  fprintf (stderr, "\n");
  fprintf (stdout, "average %llu\n", total / ROUNDS);
  return 0;
}

References MAX_IBF_DECODE, ret, and ROUNDS.