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  ;
81 #else
82  /* use assembly / gcc */
83  j = __builtin_ffs(r) - 1;
84 #endif
85  buckets[j]++;
86  }
87  ret = 0;
88  predict = 0.0;
89  for (j = 31; j >= 0; j--)
90  {
91 #if FIX1
92  /* improved algorithm, for 1000 elements with IBF-DECODE 8, I
93  get 990/1000 elements on average over 1 million runs; key
94  idea being to stop short of the 'last' possible IBF as
95  otherwise a "lowball" per-chance would unduely influence the
96  result */
97  if ((j > 0) &&
98  (buckets[j - 1] > MAX_IBF_DECODE))
99  {
100  ret *= (1 << (j + 1));
101  break;
102  }
103 #endif
104 #if FIX2
105  /* another improvement: don't just always cut off the last one,
106  but rather try to predict based on all previous values where
107  that "last" one is; additional prediction can only really
108  work if MAX_IBF_DECODE is sufficiently high */
109  if ((j > 0) &&
110  ((buckets[j - 1] > MAX_IBF_DECODE) ||
111  (predict > MAX_IBF_DECODE)))
112  {
113  ret *= (1 << (j + 1));
114  break;
115  }
116 #endif
117 #if STRATA
118  /* original algorithm, for 1000 elements with IBF-DECODE 8,
119  I get 920/1000 elements on average over 1 million runs */
120  if (buckets[j] > MAX_IBF_DECODE)
121  {
122  ret *= (1 << (j + 1));
123  break;
124  }
125 #endif
126  ret += buckets[j];
127  predict = (buckets[j] + 2.0 * predict) / 2.0;
128  }
129 #if VERBOSE
130  fprintf(stderr, "%u ", ret);
131 #endif
132  total += ret;
133  }
134  fprintf(stderr, "\n");
135  fprintf(stdout, "average %llu\n", total / ROUNDS);
136  return 0;
137 }
#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