diff options
Diffstat (limited to 'src/set/gnunet-set-ibf.c')
-rw-r--r-- | src/set/gnunet-set-ibf.c | 238 |
1 files changed, 238 insertions, 0 deletions
diff --git a/src/set/gnunet-set-ibf.c b/src/set/gnunet-set-ibf.c new file mode 100644 index 000000000..d431795f1 --- /dev/null +++ b/src/set/gnunet-set-ibf.c | |||
@@ -0,0 +1,238 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | (C) 2012 Christian Grothoff (and other contributing authors) | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 3, or (at your | ||
8 | option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @file consensus/gnunet-consensus-ibf.c | ||
23 | * @brief tool for reconciling data with invertible bloom filters | ||
24 | * @author Florian Dold | ||
25 | */ | ||
26 | |||
27 | |||
28 | #include "platform.h" | ||
29 | #include "gnunet_common.h" | ||
30 | #include "gnunet_container_lib.h" | ||
31 | #include "gnunet_util_lib.h" | ||
32 | |||
33 | #include "ibf.h" | ||
34 | |||
35 | static unsigned int asize = 10; | ||
36 | static unsigned int bsize = 10; | ||
37 | static unsigned int csize = 10; | ||
38 | static unsigned int hash_num = 3; | ||
39 | static unsigned int ibf_size = 80; | ||
40 | |||
41 | /* FIXME: add parameter for this */ | ||
42 | static enum GNUNET_CRYPTO_Quality random_quality = GNUNET_CRYPTO_QUALITY_WEAK; | ||
43 | |||
44 | static struct GNUNET_CONTAINER_MultiHashMap *set_a; | ||
45 | static struct GNUNET_CONTAINER_MultiHashMap *set_b; | ||
46 | /* common elements in a and b */ | ||
47 | static struct GNUNET_CONTAINER_MultiHashMap *set_c; | ||
48 | |||
49 | static struct GNUNET_CONTAINER_MultiHashMap *key_to_hashcode; | ||
50 | |||
51 | static struct InvertibleBloomFilter *ibf_a; | ||
52 | static struct InvertibleBloomFilter *ibf_b; | ||
53 | |||
54 | |||
55 | static void | ||
56 | register_hashcode (struct GNUNET_HashCode *hash) | ||
57 | { | ||
58 | struct GNUNET_HashCode replicated; | ||
59 | struct IBF_Key key; | ||
60 | key = ibf_key_from_hashcode (hash); | ||
61 | ibf_hashcode_from_key (key, &replicated); | ||
62 | GNUNET_CONTAINER_multihashmap_put (key_to_hashcode, &replicated, GNUNET_memdup (hash, sizeof *hash), | ||
63 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); | ||
64 | } | ||
65 | |||
66 | static void | ||
67 | iter_hashcodes (struct IBF_Key key, GNUNET_CONTAINER_HashMapIterator iter, void *cls) | ||
68 | { | ||
69 | struct GNUNET_HashCode replicated; | ||
70 | ibf_hashcode_from_key (key, &replicated); | ||
71 | GNUNET_CONTAINER_multihashmap_get_multiple (key_to_hashcode, &replicated, iter, cls); | ||
72 | } | ||
73 | |||
74 | |||
75 | static int | ||
76 | insert_iterator (void *cls, | ||
77 | const struct GNUNET_HashCode *key, | ||
78 | void *value) | ||
79 | { | ||
80 | struct InvertibleBloomFilter *ibf = (struct InvertibleBloomFilter *) cls; | ||
81 | ibf_insert (ibf, ibf_key_from_hashcode (key)); | ||
82 | return GNUNET_YES; | ||
83 | } | ||
84 | |||
85 | |||
86 | static int | ||
87 | remove_iterator (void *cls, | ||
88 | const struct GNUNET_HashCode *key, | ||
89 | void *value) | ||
90 | { | ||
91 | struct GNUNET_CONTAINER_MultiHashMap *hashmap = cls; | ||
92 | /* if remove fails, there just was a collision with another key */ | ||
93 | (void) GNUNET_CONTAINER_multihashmap_remove (hashmap, value, NULL); | ||
94 | return GNUNET_YES; | ||
95 | } | ||
96 | |||
97 | |||
98 | static void | ||
99 | run (void *cls, char *const *args, const char *cfgfile, | ||
100 | const struct GNUNET_CONFIGURATION_Handle *cfg) | ||
101 | { | ||
102 | struct GNUNET_HashCode id; | ||
103 | struct IBF_Key ibf_key; | ||
104 | int i; | ||
105 | int side; | ||
106 | int res; | ||
107 | struct GNUNET_TIME_Absolute start_time; | ||
108 | struct GNUNET_TIME_Relative delta_time; | ||
109 | |||
110 | set_a = GNUNET_CONTAINER_multihashmap_create (((asize == 0) ? 1 : (asize + csize)), | ||
111 | GNUNET_NO); | ||
112 | set_b = GNUNET_CONTAINER_multihashmap_create (((bsize == 0) ? 1 : (bsize + csize)), | ||
113 | GNUNET_NO); | ||
114 | set_c = GNUNET_CONTAINER_multihashmap_create (((csize == 0) ? 1 : csize), | ||
115 | GNUNET_NO); | ||
116 | |||
117 | key_to_hashcode = GNUNET_CONTAINER_multihashmap_create (((asize+bsize+csize == 0) ? 1 : (asize+bsize+csize)), | ||
118 | GNUNET_NO); | ||
119 | |||
120 | printf ("hash-num=%u, size=%u, #(A-B)=%u, #(B-A)=%u, #(A&B)=%u\n", | ||
121 | hash_num, ibf_size, asize, bsize, csize); | ||
122 | |||
123 | i = 0; | ||
124 | while (i < asize) | ||
125 | { | ||
126 | GNUNET_CRYPTO_hash_create_random (random_quality, &id); | ||
127 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id)) | ||
128 | continue; | ||
129 | GNUNET_CONTAINER_multihashmap_put ( | ||
130 | set_a, &id, NULL, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); | ||
131 | register_hashcode (&id); | ||
132 | i++; | ||
133 | } | ||
134 | i = 0; | ||
135 | while (i < bsize) | ||
136 | { | ||
137 | GNUNET_CRYPTO_hash_create_random (random_quality, &id); | ||
138 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id)) | ||
139 | continue; | ||
140 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id)) | ||
141 | continue; | ||
142 | GNUNET_CONTAINER_multihashmap_put ( | ||
143 | set_b, &id, NULL, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); | ||
144 | register_hashcode (&id); | ||
145 | i++; | ||
146 | } | ||
147 | i = 0; | ||
148 | while (i < csize) | ||
149 | { | ||
150 | GNUNET_CRYPTO_hash_create_random (random_quality, &id); | ||
151 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_a, &id)) | ||
152 | continue; | ||
153 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_b, &id)) | ||
154 | continue; | ||
155 | if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (set_c, &id)) | ||
156 | continue; | ||
157 | GNUNET_CONTAINER_multihashmap_put ( | ||
158 | set_c, &id, NULL, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); | ||
159 | register_hashcode (&id); | ||
160 | i++; | ||
161 | } | ||
162 | |||
163 | ibf_a = ibf_create (ibf_size, hash_num); | ||
164 | ibf_b = ibf_create (ibf_size, hash_num); | ||
165 | |||
166 | printf ("generated sets\n"); | ||
167 | |||
168 | start_time = GNUNET_TIME_absolute_get (); | ||
169 | |||
170 | GNUNET_CONTAINER_multihashmap_iterate (set_a, &insert_iterator, ibf_a); | ||
171 | GNUNET_CONTAINER_multihashmap_iterate (set_b, &insert_iterator, ibf_b); | ||
172 | GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_a); | ||
173 | GNUNET_CONTAINER_multihashmap_iterate (set_c, &insert_iterator, ibf_b); | ||
174 | |||
175 | delta_time = GNUNET_TIME_absolute_get_duration (start_time); | ||
176 | |||
177 | printf ("encoded in: %s\n", GNUNET_STRINGS_relative_time_to_string (delta_time, GNUNET_NO)); | ||
178 | |||
179 | ibf_subtract (ibf_a, ibf_b); | ||
180 | |||
181 | |||
182 | start_time = GNUNET_TIME_absolute_get (); | ||
183 | |||
184 | for (;;) | ||
185 | { | ||
186 | res = ibf_decode (ibf_a, &side, &ibf_key); | ||
187 | if (GNUNET_SYSERR == res) | ||
188 | { | ||
189 | printf ("decode failed\n"); | ||
190 | return; | ||
191 | } | ||
192 | if (GNUNET_NO == res) | ||
193 | { | ||
194 | if ((0 == GNUNET_CONTAINER_multihashmap_size (set_b)) && | ||
195 | (0 == GNUNET_CONTAINER_multihashmap_size (set_a))) | ||
196 | { | ||
197 | delta_time = GNUNET_TIME_absolute_get_duration (start_time); | ||
198 | printf ("decoded successfully in: %s\n", GNUNET_STRINGS_relative_time_to_string (delta_time, GNUNET_NO)); | ||
199 | } | ||
200 | else | ||
201 | printf ("decode missed elements\n"); | ||
202 | return; | ||
203 | } | ||
204 | |||
205 | if (side == 1) | ||
206 | iter_hashcodes (ibf_key, remove_iterator, set_a); | ||
207 | if (side == -1) | ||
208 | iter_hashcodes (ibf_key, remove_iterator, set_b); | ||
209 | } | ||
210 | } | ||
211 | |||
212 | int | ||
213 | main (int argc, char **argv) | ||
214 | { | ||
215 | static const struct GNUNET_GETOPT_CommandLineOption options[] = { | ||
216 | {'A', "asize", NULL, | ||
217 | gettext_noop ("number of element in set A-B"), 1, | ||
218 | &GNUNET_GETOPT_set_uint, &asize}, | ||
219 | {'B', "bsize", NULL, | ||
220 | gettext_noop ("number of element in set B-A"), 1, | ||
221 | &GNUNET_GETOPT_set_uint, &bsize}, | ||
222 | {'C', "csize", NULL, | ||
223 | gettext_noop ("number of common elements in A and B"), 1, | ||
224 | &GNUNET_GETOPT_set_uint, &csize}, | ||
225 | {'k', "hash-num", NULL, | ||
226 | gettext_noop ("hash num"), 1, | ||
227 | &GNUNET_GETOPT_set_uint, &hash_num}, | ||
228 | {'s', "ibf-size", NULL, | ||
229 | gettext_noop ("ibf size"), 1, | ||
230 | &GNUNET_GETOPT_set_uint, &ibf_size}, | ||
231 | GNUNET_GETOPT_OPTION_END | ||
232 | }; | ||
233 | GNUNET_PROGRAM_run2 (argc, argv, "gnunet-consensus-ibf", | ||
234 | "help", | ||
235 | options, &run, NULL, GNUNET_YES); | ||
236 | return 0; | ||
237 | } | ||
238 | |||