GNUnet  0.10.x
Macros | Functions
ibf_sim.c File Reference

implementation of simulation for invertible bloom filter More...

#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 33 of file ibf_sim.c.

Referenced by main().

◆ ROUNDS

#define ROUNDS   100000

Definition at line 36 of file ibf_sim.c.

Referenced by main().

◆ FIX1

#define FIX1   0

Definition at line 40 of file ibf_sim.c.

◆ FIX2

#define FIX2   1

Definition at line 42 of file ibf_sim.c.

◆ STRATA

#define STRATA   0

Definition at line 45 of file ibf_sim.c.

◆ VERBOSE

#define VERBOSE   0

Definition at line 48 of file ibf_sim.c.

◆ SLOW

#define SLOW   0

Definition at line 50 of file ibf_sim.c.

Function Documentation

◆ main()

int main ( int  argc,
char **  argv 
)

Definition at line 53 of file ibf_sim.c.

References MAX_IBF_DECODE, ret, and ROUNDS.

54 {
55  unsigned int round;
56  unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31
57  unsigned int i;
58  int j;
59  unsigned int r;
60  unsigned int ret;
61  unsigned long long total;
62  unsigned int want;
63  double predict;
64 
65  srandom (time (NULL));
66  total = 0;
67  want = atoi (argv[1]);
68  for (round=0;round<ROUNDS;round++)
69  {
70  memset (buckets, 0, sizeof (buckets));
71  for (i=0;i<want;i++)
72  {
73  /* FIXME: might want to use 'better' PRNG to avoid
74  PRNG-induced biases */
75  r = random ();
76  if (0 == r)
77  continue;
78 #if SLOW
79  for (j=0;(j < 31) && (0 == (r & (1 << j)));j++) ;
80 #else
81  /* use assembly / gcc */
82  j = __builtin_ffs (r) - 1;
83 #endif
84  buckets[j]++;
85  }
86  ret = 0;
87  predict = 0.0;
88  for (j=31;j >= 0; j--)
89  {
90 #if FIX1
91  /* improved algorithm, for 1000 elements with IBF-DECODE 8, I
92  get 990/1000 elements on average over 1 million runs; key
93  idea being to stop short of the 'last' possible IBF as
94  otherwise a "lowball" per-chance would unduely influence the
95  result */
96  if ( (j > 0) &&
97  (buckets[j - 1] > MAX_IBF_DECODE) )
98  {
99  ret *= (1 << (j + 1));
100  break;
101  }
102 #endif
103 #if FIX2
104  /* another improvement: don't just always cut off the last one,
105  but rather try to predict based on all previous values where
106  that "last" one is; additional prediction can only really
107  work if MAX_IBF_DECODE is sufficiently high */
108  if ( (j > 0) &&
109  ( (buckets[j - 1] > MAX_IBF_DECODE) ||
110  (predict > MAX_IBF_DECODE) ) )
111  {
112  ret *= (1 << (j + 1));
113  break;
114  }
115 #endif
116 #if STRATA
117  /* original algorithm, for 1000 elements with IBF-DECODE 8,
118  I get 920/1000 elements on average over 1 million runs */
119  if (buckets[j] > MAX_IBF_DECODE)
120  {
121  ret *= (1 << (j+1));
122  break;
123  }
124 #endif
125  ret += buckets[j];
126  predict = (buckets[j] + 2.0 * predict) / 2.0;
127  }
128 #if VERBOSE
129  fprintf (stderr, "%u ", ret);
130 #endif
131  total += ret;
132  }
133  fprintf (stderr, "\n");
134  fprintf (stdout, "average %llu\n", total / ROUNDS);
135  return 0;
136 }
#define ROUNDS
Definition: ibf_sim.c:36
static int ret
Final status code.
Definition: gnunet-arm.c:89
#define MAX_IBF_DECODE
Definition: ibf_sim.c:33