diff options
Diffstat (limited to 'src/contrib/service/set/gnunet-service-set_union_strata_estimator.c')
-rw-r--r-- | src/contrib/service/set/gnunet-service-set_union_strata_estimator.c | 297 |
1 files changed, 297 insertions, 0 deletions
diff --git a/src/contrib/service/set/gnunet-service-set_union_strata_estimator.c b/src/contrib/service/set/gnunet-service-set_union_strata_estimator.c new file mode 100644 index 000000000..6de9fb5eb --- /dev/null +++ b/src/contrib/service/set/gnunet-service-set_union_strata_estimator.c | |||
@@ -0,0 +1,297 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | Copyright (C) 2012 GNUnet e.V. | ||
4 | |||
5 | GNUnet is free software: you can redistribute it and/or modify it | ||
6 | under the terms of the GNU Affero General Public License as published | ||
7 | by the Free Software Foundation, either version 3 of the License, | ||
8 | or (at your 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 | Affero General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU Affero General Public License | ||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
17 | |||
18 | SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | */ | ||
20 | /** | ||
21 | * @file set/gnunet-service-set_union_strata_estimator.c | ||
22 | * @brief invertible bloom filter | ||
23 | * @author Florian Dold | ||
24 | * @author Christian Grothoff | ||
25 | */ | ||
26 | #include "platform.h" | ||
27 | #include "gnunet_util_lib.h" | ||
28 | #include "ibf.h" | ||
29 | #include "gnunet-service-set_union_strata_estimator.h" | ||
30 | |||
31 | |||
32 | /** | ||
33 | * Should we try compressing the strata estimator? This will | ||
34 | * break compatibility with the 0.10.1-network. | ||
35 | */ | ||
36 | #define FAIL_10_1_COMPATIBILTIY 1 | ||
37 | |||
38 | |||
39 | /** | ||
40 | * Write the given strata estimator to the buffer. | ||
41 | * | ||
42 | * @param se strata estimator to serialize | ||
43 | * @param[out] buf buffer to write to, must be of appropriate size | ||
44 | * @return number of bytes written to @a buf | ||
45 | */ | ||
46 | size_t | ||
47 | strata_estimator_write (const struct StrataEstimator *se, | ||
48 | void *buf) | ||
49 | { | ||
50 | char *sbuf = buf; | ||
51 | unsigned int i; | ||
52 | size_t osize; | ||
53 | |||
54 | GNUNET_assert (NULL != se); | ||
55 | for (i = 0; i < se->strata_count; i++) | ||
56 | { | ||
57 | ibf_write_slice (se->strata[i], | ||
58 | 0, | ||
59 | se->ibf_size, | ||
60 | &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]); | ||
61 | } | ||
62 | osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; | ||
63 | #if FAIL_10_1_COMPATIBILTIY | ||
64 | { | ||
65 | char *cbuf; | ||
66 | size_t nsize; | ||
67 | |||
68 | if (GNUNET_YES == | ||
69 | GNUNET_try_compression (buf, | ||
70 | osize, | ||
71 | &cbuf, | ||
72 | &nsize)) | ||
73 | { | ||
74 | GNUNET_memcpy (buf, cbuf, nsize); | ||
75 | osize = nsize; | ||
76 | GNUNET_free (cbuf); | ||
77 | } | ||
78 | } | ||
79 | #endif | ||
80 | return osize; | ||
81 | } | ||
82 | |||
83 | |||
84 | /** | ||
85 | * Read strata from the buffer into the given strata | ||
86 | * estimator. The strata estimator must already be allocated. | ||
87 | * | ||
88 | * @param buf buffer to read from | ||
89 | * @param buf_len number of bytes in @a buf | ||
90 | * @param is_compressed is the data compressed? | ||
91 | * @param[out] se strata estimator to write to | ||
92 | * @return #GNUNET_OK on success | ||
93 | */ | ||
94 | int | ||
95 | strata_estimator_read (const void *buf, | ||
96 | size_t buf_len, | ||
97 | int is_compressed, | ||
98 | struct StrataEstimator *se) | ||
99 | { | ||
100 | unsigned int i; | ||
101 | size_t osize; | ||
102 | char *dbuf; | ||
103 | |||
104 | dbuf = NULL; | ||
105 | if (GNUNET_YES == is_compressed) | ||
106 | { | ||
107 | osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count; | ||
108 | dbuf = GNUNET_decompress (buf, | ||
109 | buf_len, | ||
110 | osize); | ||
111 | if (NULL == dbuf) | ||
112 | { | ||
113 | GNUNET_break_op (0); /* bad compressed input data */ | ||
114 | return GNUNET_SYSERR; | ||
115 | } | ||
116 | buf = dbuf; | ||
117 | buf_len = osize; | ||
118 | } | ||
119 | |||
120 | if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE) | ||
121 | { | ||
122 | GNUNET_break (0); /* very odd error */ | ||
123 | GNUNET_free (dbuf); | ||
124 | return GNUNET_SYSERR; | ||
125 | } | ||
126 | |||
127 | for (i = 0; i < se->strata_count; i++) | ||
128 | { | ||
129 | ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]); | ||
130 | buf += se->ibf_size * IBF_BUCKET_SIZE; | ||
131 | } | ||
132 | GNUNET_free (dbuf); | ||
133 | return GNUNET_OK; | ||
134 | } | ||
135 | |||
136 | |||
137 | /** | ||
138 | * Add a key to the strata estimator. | ||
139 | * | ||
140 | * @param se strata estimator to add the key to | ||
141 | * @param key key to add | ||
142 | */ | ||
143 | void | ||
144 | strata_estimator_insert (struct StrataEstimator *se, | ||
145 | struct IBF_Key key) | ||
146 | { | ||
147 | uint64_t v; | ||
148 | unsigned int i; | ||
149 | |||
150 | v = key.key_val; | ||
151 | /* count trailing '1'-bits of v */ | ||
152 | for (i = 0; v & 1; v >>= 1, i++) | ||
153 | /* empty */; | ||
154 | ibf_insert (se->strata[i], key); | ||
155 | } | ||
156 | |||
157 | |||
158 | void | ||
159 | strata_estimator_remove (struct StrataEstimator *se, | ||
160 | struct IBF_Key key) | ||
161 | { | ||
162 | uint64_t v; | ||
163 | unsigned int i; | ||
164 | |||
165 | v = key.key_val; | ||
166 | /* count trailing '1'-bits of v */ | ||
167 | for (i = 0; v & 1; v >>= 1, i++) | ||
168 | /* empty */; | ||
169 | ibf_remove (se->strata[i], key); | ||
170 | } | ||
171 | |||
172 | |||
173 | /** | ||
174 | * Create a new strata estimator with the given parameters. | ||
175 | * | ||
176 | * @param strata_count number of stratas, that is, number of ibfs in the estimator | ||
177 | * @param ibf_size size of each ibf stratum | ||
178 | * @param ibf_hashnum hashnum parameter of each ibf | ||
179 | * @return a freshly allocated, empty strata estimator, NULL on error | ||
180 | */ | ||
181 | struct StrataEstimator * | ||
182 | strata_estimator_create (unsigned int strata_count, | ||
183 | uint32_t ibf_size, | ||
184 | uint8_t ibf_hashnum) | ||
185 | { | ||
186 | struct StrataEstimator *se; | ||
187 | unsigned int i; | ||
188 | unsigned int j; | ||
189 | |||
190 | se = GNUNET_new (struct StrataEstimator); | ||
191 | se->strata_count = strata_count; | ||
192 | se->ibf_size = ibf_size; | ||
193 | se->strata = GNUNET_new_array (strata_count, | ||
194 | struct InvertibleBloomFilter *); | ||
195 | for (i = 0; i < strata_count; i++) | ||
196 | { | ||
197 | se->strata[i] = ibf_create (ibf_size, ibf_hashnum); | ||
198 | if (NULL == se->strata[i]) | ||
199 | { | ||
200 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
201 | "Failed to allocate memory for strata estimator\n"); | ||
202 | for (j = 0; j < i; j++) | ||
203 | ibf_destroy (se->strata[i]); | ||
204 | GNUNET_free (se); | ||
205 | return NULL; | ||
206 | } | ||
207 | } | ||
208 | return se; | ||
209 | } | ||
210 | |||
211 | |||
212 | /** | ||
213 | * Estimate set difference with two strata estimators, | ||
214 | * i.e. arrays of IBFs. | ||
215 | * Does not not modify its arguments. | ||
216 | * | ||
217 | * @param se1 first strata estimator | ||
218 | * @param se2 second strata estimator | ||
219 | * @return the estimated difference | ||
220 | */ | ||
221 | unsigned int | ||
222 | strata_estimator_difference (const struct StrataEstimator *se1, | ||
223 | const struct StrataEstimator *se2) | ||
224 | { | ||
225 | unsigned int count; | ||
226 | |||
227 | GNUNET_assert (se1->strata_count == se2->strata_count); | ||
228 | count = 0; | ||
229 | for (int i = se1->strata_count - 1; i >= 0; i--) | ||
230 | { | ||
231 | struct InvertibleBloomFilter *diff; | ||
232 | /* number of keys decoded from the ibf */ | ||
233 | |||
234 | /* FIXME: implement this without always allocating new IBFs */ | ||
235 | diff = ibf_dup (se1->strata[i]); | ||
236 | ibf_subtract (diff, se2->strata[i]); | ||
237 | for (int ibf_count = 0; GNUNET_YES; ibf_count++) | ||
238 | { | ||
239 | int more; | ||
240 | |||
241 | more = ibf_decode (diff, NULL, NULL); | ||
242 | if (GNUNET_NO == more) | ||
243 | { | ||
244 | count += ibf_count; | ||
245 | break; | ||
246 | } | ||
247 | /* Estimate if decoding fails or would not terminate */ | ||
248 | if ((GNUNET_SYSERR == more) || (ibf_count > diff->size)) | ||
249 | { | ||
250 | ibf_destroy (diff); | ||
251 | return count * (1 << (i + 1)); | ||
252 | } | ||
253 | } | ||
254 | ibf_destroy (diff); | ||
255 | } | ||
256 | return count; | ||
257 | } | ||
258 | |||
259 | |||
260 | /** | ||
261 | * Make a copy of a strata estimator. | ||
262 | * | ||
263 | * @param se the strata estimator to copy | ||
264 | * @return the copy | ||
265 | */ | ||
266 | struct StrataEstimator * | ||
267 | strata_estimator_dup (struct StrataEstimator *se) | ||
268 | { | ||
269 | struct StrataEstimator *c; | ||
270 | unsigned int i; | ||
271 | |||
272 | c = GNUNET_new (struct StrataEstimator); | ||
273 | c->strata_count = se->strata_count; | ||
274 | c->ibf_size = se->ibf_size; | ||
275 | c->strata = GNUNET_new_array (se->strata_count, | ||
276 | struct InvertibleBloomFilter *); | ||
277 | for (i = 0; i < se->strata_count; i++) | ||
278 | c->strata[i] = ibf_dup (se->strata[i]); | ||
279 | return c; | ||
280 | } | ||
281 | |||
282 | |||
283 | /** | ||
284 | * Destroy a strata estimator, free all of its resources. | ||
285 | * | ||
286 | * @param se strata estimator to destroy. | ||
287 | */ | ||
288 | void | ||
289 | strata_estimator_destroy (struct StrataEstimator *se) | ||
290 | { | ||
291 | unsigned int i; | ||
292 | |||
293 | for (i = 0; i < se->strata_count; i++) | ||
294 | ibf_destroy (se->strata[i]); | ||
295 | GNUNET_free (se->strata); | ||
296 | GNUNET_free (se); | ||
297 | } | ||