Commit | Line | Data |
---|---|---|
28363d2c MW |
1 | /* -*-c-*- |
2 | * | |
3 | * Reservoir and buffer handling | |
4 | * | |
5 | * (c) 2017 Straylight/Edgeware | |
6 | */ | |
7 | ||
8 | /*----- Licensing notice --------------------------------------------------* | |
9 | * | |
10 | * This file is part of Catacomb. | |
11 | * | |
12 | * Catacomb is free software: you can redistribute it and/or modify it | |
13 | * under the terms of the GNU Library General Public License as published | |
14 | * by the Free Software Foundation; either version 2 of the License, or | |
15 | * (at your option) any later version. | |
16 | * | |
17 | * Catacomb is distributed in the hope that it will be useful, but | |
18 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
20 | * Library General Public License for more details. | |
21 | * | |
22 | * You should have received a copy of the GNU Library General Public | |
23 | * License along with Catacomb. If not, write to the Free Software | |
24 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
25 | * USA. | |
26 | */ | |
27 | ||
28 | /*----- Header files ------------------------------------------------------*/ | |
29 | ||
30 | #include <assert.h> | |
31 | #include <stdlib.h> | |
32 | #include <string.h> | |
33 | ||
34 | #include "rsvr.h" | |
35 | ||
36 | /*----- Main code ---------------------------------------------------------*/ | |
37 | ||
38 | /* --- @rsvr_mkplan@ --- * | |
39 | * | |
40 | * Arguments: @rsvr_plan *plan@ = pointer to plan to fill in | |
41 | * @const rsvr_policy *pol@ = reservoir policy to follow | |
42 | * @size_t used@ = amount of data in the reservoir | |
43 | * @size_t insz@ = amount of fresh input data arriving | |
44 | * | |
45 | * Returns: --- | |
46 | * | |
47 | * Use: Prepares a plan for feeding input data into a block-oriented | |
48 | * operation. | |
49 | * | |
50 | * The caller's code for following the plan proceeds in four | |
51 | * parts. | |
52 | * | |
53 | * 1. Insert the first @plan->head@ input items into the | |
54 | * reservoir; there will be sufficient space, and | |
55 | * @plan->head@ will be at most @pol->blksz@. | |
56 | * | |
57 | * 2. Process the first @plan->from_rsvr@ items from the | |
58 | * reservoir, shifting the remaining items forward; | |
59 | * @plan->from_rsvr@ will be a multiple of @pol->blksz@. | |
60 | * | |
61 | * 3. Process the next @plan->from_input@ items directly from | |
62 | * the input; @plan->from_input@ will be a multiple of | |
63 | * @pol->blksz@. | |
64 | * | |
65 | * 4. Insert the remaining @plan->tail@ input items into the | |
66 | * reservoir for next time. | |
67 | */ | |
68 | ||
69 | void rsvr_mkplan(rsvr_plan *plan, const rsvr_policy *pol, | |
70 | size_t used, size_t insz) | |
71 | { | |
72 | unsigned extra = !!(pol->f&RSVRF_FULL); | |
73 | unsigned n, final; | |
74 | ||
75 | if (insz < pol->rsvrsz - used + extra) { | |
76 | /* Easy case: there's enough space in the reservoir for the whole input, | |
77 | * so just accumulate it and we're done. | |
78 | */ | |
79 | ||
80 | plan->head = insz; | |
81 | plan->from_rsvr = plan->from_input = plan->tail = 0; | |
82 | } else { | |
83 | /* The hard case. We're going to have to actually process something. */ | |
84 | ||
85 | /* Firstly, we top the reservoir up to the next block boundary. */ | |
86 | n = (pol->rsvrsz - used)%pol->blksz; | |
87 | plan->head = n; used += n; insz -= n; | |
88 | ||
89 | /* Next, figure out the final amount we'll leave in the reservoir. This | |
90 | * will be congruent to USED, modulo the block size, and within the last | |
91 | * BLKSZ-wide interval permitted. We must have enough material to get | |
92 | * here, or we'd be in the other branch above. | |
93 | */ | |
94 | final = pol->rsvrsz - pol->blksz + extra + | |
95 | (insz + pol->blksz - extra)%pol->blksz; | |
96 | ||
97 | /* If we don't have enough input to drain the reservoir completely, and | |
98 | * then top it up to the necessary level, then take as much as we can | |
99 | * from the reservoir; otherwise, drain completely and then use up the | |
100 | * remaining input directly. | |
101 | */ | |
102 | if (insz < final) { | |
103 | /* We don't have enough input to drain the reservoir completely and | |
104 | * then top it up to the necessary final level. Take what we can. | |
105 | */ | |
106 | ||
107 | plan->from_rsvr = used + insz - final; | |
108 | plan->from_input = 0; | |
109 | plan->tail = insz; | |
110 | } else { | |
111 | /* We have lots of input. Drain the reservoir fully, process the bulk | |
112 | * of the input buffer, and load the rest into the reservoir at the | |
113 | * end. | |
114 | */ | |
115 | ||
116 | plan->from_rsvr = used; | |
117 | plan->from_input = insz - final; | |
118 | plan->tail = final; | |
119 | } | |
120 | } | |
121 | } | |
122 | ||
123 | /* --- @rsvr_setup@ --- * | |
124 | * | |
125 | * Arguments: @rsvr_state *st@ = pointer to state structure to fill in | |
126 | * @const rsvr_policy *pol@ = reservoir policy to follow | |
127 | * @void *rsvr@ = pointer to the actual reservoir | |
128 | * @unsigned *used@ = pointer to the reservoir level | |
129 | * @const void *in@ = pointer to the input data | |
130 | * @size_t insz@ = size of the input | |
131 | * | |
132 | * Returns: --- | |
133 | * | |
134 | * Use: Prepares for a simple operation. This performs the initial | |
135 | * copy of input data into the reservoir, and prepares for the | |
136 | * next step. | |
137 | * | |
138 | * After this, the calling code should usually proceed as | |
139 | * follows. | |
140 | * | |
141 | * 1. Call @RSVR_NEXT@ in a sequence of loops, with | |
142 | * successively smaller values of @n@, to process waiting | |
143 | * data from the reservoir. Usually, each @n@ will be some | |
144 | * multiple of the block size @pol->blksz@, and the final | |
145 | * loop will have @n = pol->blksz@. | |
146 | * | |
147 | * 2. Call @rsvr_done@ to indicate that this has been done. | |
148 | * | |
149 | * 3. Call @RSVR_NEXT@ in a sequence of loops, as in step 1, | |
150 | * to process the remaining data from the input buffer. | |
151 | * | |
152 | * 4. Call @rsvr_done@ to indicate that the job is complete. | |
153 | */ | |
154 | ||
155 | void rsvr_setup(rsvr_state *st, const rsvr_policy *pol, | |
156 | void *rsvr, unsigned *used, const void *in, size_t insz) | |
157 | { | |
158 | rsvr_mkplan(&st->plan, pol, *used, insz); | |
159 | st->rsvr = rsvr; st->in = in; st->used = used; | |
160 | ||
161 | if (st->plan.head) { | |
162 | memcpy(rsvr + *st->used, st->in, st->plan.head); | |
163 | *st->used += st->plan.head; st->in += st->plan.head; | |
164 | } | |
165 | st->src = RSVRSRC_RSVR; st->p = st->rsvr; st->sz = st->plan.from_rsvr; | |
166 | } | |
167 | ||
168 | /* --- @RSVR_NEXT@, @rsvr_next@ --- * | |
169 | * | |
170 | * Arguments: @rsvr_state *st@ = pointer to the state structure | |
171 | * @size_t n@ = amount of input data required, in bytes; should | |
172 | * usually be a multiple of @pol->blksz@ | |
173 | * | |
174 | * Returns: A pointer to the next @n@ bytes of input, or null if there is | |
175 | * insufficient data remaining. | |
176 | */ | |
177 | ||
178 | const void *rsvr_next(rsvr_state *st, size_t n) { return RSVR_NEXT(st, n); } | |
179 | ||
180 | /* --- @rsvr_done@ --- * | |
181 | * | |
182 | * Arguments: @rsvr_state *st@ = pointer to the state structure | |
183 | * | |
184 | * Returns: Zero after the first pass, nonzero after the second. | |
185 | * | |
186 | * Use: Reports that the first or second stage (see @rsvr_setup@ | |
187 | * above) of an operation has been completed. | |
188 | * | |
189 | * If the first stage is complete, then this shifts stuff about | |
190 | * in the reservoir and prepares for the second stage; if the | |
191 | * second stage is complete, then it copies the remaining input | |
192 | * into the reservoir and marks the state as complete. | |
193 | */ | |
194 | ||
195 | int rsvr_done(rsvr_state *st) | |
196 | { | |
197 | assert(!st->sz); | |
198 | switch (st->src) { | |
199 | case RSVRSRC_RSVR: | |
200 | if (st->plan.from_rsvr) { | |
201 | if (st->plan.from_rsvr < *st->used) { | |
202 | memmove(st->rsvr, st->rsvr + st->plan.from_rsvr, | |
203 | *st->used - st->plan.from_rsvr); | |
204 | } | |
205 | *st->used -= st->plan.from_rsvr; | |
206 | } | |
207 | st->src = RSVRSRC_INPUT; | |
208 | st->p = st->in; st->sz = st->plan.from_input; | |
209 | return (0); | |
210 | case RSVRSRC_INPUT: | |
211 | if (st->plan.tail) { | |
212 | memcpy(st->rsvr + *st->used, st->p, st->plan.tail); | |
213 | *st->used += st->plan.tail; | |
214 | } | |
215 | st->src = RSVRSRC_DONE; | |
216 | st->p = 0; st->sz = 0; | |
217 | return (1); | |
218 | default: | |
219 | abort(); | |
220 | } | |
221 | } | |
222 | ||
223 | /*----- Testing -----------------------------------------------------------*/ | |
224 | ||
225 | #ifdef TEST_RIG | |
226 | ||
227 | #include <ctype.h> | |
228 | #include <errno.h> | |
229 | #include <stdio.h> | |
230 | ||
231 | #include <mLib/alloc.h> | |
232 | #include <mLib/bits.h> | |
233 | #include <mLib/darray.h> | |
141c1284 | 234 | #include <mLib/macros.h> |
28363d2c MW |
235 | #include <mLib/report.h> |
236 | #include <mLib/testrig.h> | |
237 | ||
238 | struct rng { | |
239 | uint32 x; | |
240 | }; | |
241 | ||
242 | static void init_rng(struct rng *r) | |
243 | { r->x = 0; } | |
244 | ||
245 | static void step_rng(struct rng *r) | |
246 | { r->x = U32(0x0d83c207*r->x + 0x380fcfea); } | |
247 | ||
248 | DA_DECL(uint_v, unsigned); | |
249 | ||
250 | struct testinfo { | |
251 | rsvr_policy pol; | |
252 | uint_v chunksz; | |
253 | uint_v blksz; | |
254 | unsigned used; | |
255 | size_t off; | |
256 | int ok; | |
257 | }; | |
258 | ||
259 | static void show_uint_v(const char *what, const uint_v *v) | |
260 | { | |
261 | size_t i; | |
262 | ||
263 | printf("\t%s:", what); | |
264 | for (i = 0; i < DA_LEN(v); i++) printf("%s%u", i ? ", " : " ", DA(v)[i]); | |
265 | printf("\n"); | |
266 | } | |
267 | ||
268 | static void report_policy(const struct rsvr_policy *pol) | |
269 | { | |
270 | printf("\tpolicy: flags = 0x%08x%s; blksz = %u; rsvrsz = %u\n", | |
271 | pol->f, pol->f&RSVRF_FULL ? " full" : pol->f ? "" : " nil", | |
272 | pol->blksz, pol->rsvrsz); | |
273 | } | |
274 | ||
275 | static void report_testinfo(const struct testinfo *info) | |
276 | { | |
277 | report_policy(&info->pol); | |
278 | show_uint_v("chunksz", &info->chunksz); | |
279 | show_uint_v("blksz", &info->blksz); | |
280 | printf("\treservoir level = %u\n", info->used); | |
281 | printf("\toffset = %lu\n", (unsigned long)info->off); | |
282 | } | |
283 | ||
284 | static void check(struct rng *r, struct testinfo *info, | |
285 | const void *p, size_t sz) | |
286 | { | |
287 | const octet *q = p; | |
288 | unsigned x; | |
289 | ||
290 | while (sz) { | |
291 | x = U8(r->x); | |
292 | if (info->ok && *q != x) { | |
293 | printf("\n*** FAIL data mismatch (0x%02x /= 0x%02x)\n", *q, x); | |
294 | report_testinfo(info); | |
295 | info->ok = 0; | |
296 | } | |
297 | q++; sz--; info->off++; | |
298 | step_rng(r); | |
299 | } | |
300 | } | |
301 | ||
302 | static void parse_intlist(uint_v *v, const char *p) | |
303 | { | |
304 | char *q; | |
305 | unsigned long n; | |
306 | int e = errno; | |
307 | ||
308 | for (;;) { | |
141c1284 | 309 | while (ISSPACE(*p)) p++; |
28363d2c MW |
310 | if (!*p) break; |
311 | if (*p == ',') p++; | |
141c1284 | 312 | while (ISSPACE(*p)) p++; |
28363d2c | 313 | errno = 0; n = strtoul(p, &q, 0); |
141c1284 | 314 | if (errno || (*q && *q != ',' && !ISSPACE(*q))) |
28363d2c MW |
315 | die(1, "invalid int list"); |
316 | p = q; DA_PUSH(v, n); | |
317 | } | |
318 | errno = e; | |
319 | } | |
320 | ||
321 | int vrfy_plan(dstr *dv) | |
322 | { | |
323 | rsvr_policy pol; | |
324 | rsvr_plan want, calc; | |
325 | unsigned used; | |
326 | size_t insz; | |
327 | int ok = 1; | |
328 | ||
329 | pol.f = *(unsigned long *)dv[0].buf; | |
330 | pol.blksz = *(unsigned long *)dv[1].buf; | |
331 | pol.rsvrsz = *(unsigned long *)dv[2].buf; | |
332 | used = *(unsigned long *)dv[3].buf; | |
333 | insz = *(unsigned long *)dv[4].buf; | |
334 | want.head = *(unsigned long *)dv[5].buf; | |
335 | want.from_rsvr = *(unsigned long *)dv[6].buf; | |
336 | want.from_input = *(unsigned long *)dv[7].buf; | |
337 | want.tail = *(unsigned long *)dv[8].buf; | |
338 | ||
339 | rsvr_mkplan(&calc, &pol, used, insz); | |
340 | ||
341 | if (want.head != calc.head || | |
342 | want.from_rsvr != calc.from_rsvr || | |
343 | want.from_input != calc.from_input || | |
344 | want.tail != calc.tail) { | |
345 | printf("\n*** FAIL plan doesn't match\n"); | |
346 | report_policy(&pol); | |
347 | printf("\treservoir level = %u\n", used); | |
348 | printf("\tinput size = %lu\n", (unsigned long)insz); | |
349 | #define SHOW(what, slot) do { \ | |
350 | printf("\t" what " (calc) %lu %s %lu (want)\n", \ | |
351 | (unsigned long)calc.slot, \ | |
352 | calc.slot == want.slot ? "=" : "/=", \ | |
353 | (unsigned long)want.slot); \ | |
354 | } while(0) | |
355 | SHOW("head", head); | |
356 | SHOW("from reservoir", from_rsvr); | |
357 | SHOW("from input", from_input); | |
358 | SHOW("tail", tail); | |
359 | #undef SHOW | |
360 | ok = 0; | |
361 | } | |
362 | ||
363 | return (ok); | |
364 | } | |
365 | ||
366 | static int vrfy_copy(dstr *dv) | |
367 | { | |
368 | struct testinfo info; | |
369 | rsvr_state st; | |
370 | struct rng ra, rb; | |
371 | octet *buf = 0, *rsvr; | |
372 | const void *p; | |
373 | size_t i, j, bsz = 0; | |
374 | unsigned n, used0, lb, ub, fin; | |
375 | ||
376 | init_rng(&ra); init_rng(&rb); | |
377 | info.pol.f = *(unsigned long *)dv[0].buf; | |
378 | info.pol.blksz = *(unsigned long *)dv[1].buf; | |
379 | info.pol.rsvrsz = *(unsigned long *)dv[2].buf; | |
380 | info.ok = 1; info.used = 0; info.off = 0; | |
381 | rsvr = xmalloc(info.pol.rsvrsz); | |
382 | DA_CREATE(&info.chunksz); parse_intlist(&info.chunksz, dv[3].buf); | |
383 | DA_CREATE(&info.blksz); parse_intlist(&info.blksz, dv[4].buf); | |
384 | for (i = 0; i < DA_LEN(&info.chunksz); i++) | |
385 | if (bsz < DA(&info.chunksz)[i]) bsz = DA(&info.chunksz)[i]; | |
386 | buf = xmalloc(bsz); | |
387 | for (i = 0; i < DA_LEN(&info.chunksz); i++) { | |
388 | n = DA(&info.chunksz)[i]; | |
389 | for (j = 0; j < n; j++) { buf[j] = U8(ra.x); step_rng(&ra); } | |
390 | used0 = info.used; | |
391 | rsvr_setup(&st, &info.pol, rsvr, &info.used, buf, n); | |
392 | if (n != st.plan.head + st.plan.from_input + st.plan.tail) { | |
393 | printf("\n*** FAIL input size crosscheck " | |
394 | "(%u /= %u + %lu + %u = %lu)\n", | |
395 | n, | |
396 | st.plan.head, (unsigned long)st.plan.from_input, st.plan.tail, | |
397 | (unsigned long)(st.plan.head + | |
398 | st.plan.from_input + | |
399 | st.plan.tail)); | |
400 | report_testinfo(&info); | |
401 | info.ok = 0; | |
402 | } | |
403 | if (st.plan.from_rsvr%info.pol.blksz) { | |
404 | printf("\n*** FAIL reservoir chunk %u misaligned\n", | |
405 | st.plan.from_rsvr); | |
406 | report_testinfo(&info); | |
407 | info.ok = 0; | |
408 | } | |
409 | if (st.plan.from_input%info.pol.blksz) { | |
410 | printf("\n*** FAIL direct chunk %lu misaligned\n", | |
411 | (unsigned long)st.plan.from_input); | |
412 | report_testinfo(&info); | |
413 | info.ok = 0; | |
414 | } | |
415 | if (st.plan.head > info.pol.rsvrsz - used0) { | |
416 | printf("\n*** FAIL top-up out of range (%u + %u = %u > %u)\n", | |
417 | used0, st.plan.head, used0 + st.plan.head, info.pol.rsvrsz); | |
418 | report_testinfo(&info); | |
419 | info.ok = 0; | |
420 | } | |
421 | if (st.plan.from_rsvr > used0 + st.plan.head) { | |
422 | printf("\n*** FAIL shift out of range (%u > %u + %u = %u)\n", | |
423 | st.plan.from_rsvr, | |
424 | used0, st.plan.head, used0 + st.plan.head); | |
425 | report_testinfo(&info); | |
426 | info.ok = 0; | |
427 | } | |
428 | if (st.plan.head != n) { | |
429 | ub = info.pol.rsvrsz + !!(info.pol.f&RSVRF_FULL); | |
430 | lb = ub - info.pol.blksz; | |
431 | fin = used0 + st.plan.head - st.plan.from_rsvr + st.plan.tail; | |
432 | if (lb > fin) { | |
433 | printf("\n*** FAIL final level out of bounds " | |
434 | "(%u > %u = %u + %u - %u + %u)\n", | |
435 | lb, fin, | |
436 | used0, st.plan.head, st.plan.from_rsvr, st.plan.tail); | |
437 | report_testinfo(&info); | |
438 | info.ok = 0; | |
439 | } | |
440 | if (fin >= ub) { | |
441 | printf("\n*** FAIL final level out of bounds " | |
442 | "(%u + %u - %u + %u = %u >= %u)\n", | |
443 | used0, st.plan.head, st.plan.from_rsvr, st.plan.tail, | |
444 | fin, ub); | |
445 | report_testinfo(&info); | |
446 | info.ok = 0; | |
447 | } | |
448 | } | |
449 | ||
450 | if (!info.ok) break; | |
451 | RSVR_DO(&st) { | |
452 | for (j = 0; j < DA_LEN(&info.blksz); j++) { | |
453 | n = DA(&info.blksz)[j]; | |
454 | while ((p = RSVR_NEXT(&st, n)) != 0) check(&rb, &info, p, n); | |
455 | } | |
456 | } | |
457 | } | |
458 | ||
459 | DA_DESTROY(&info.chunksz); | |
460 | DA_DESTROY(&info.blksz); | |
461 | xfree(rsvr); xfree(buf); | |
462 | return (info.ok); | |
463 | } | |
464 | ||
465 | static const struct test_chunk tests[] = { | |
466 | { "plan", vrfy_plan, | |
467 | { &type_ulong, &type_ulong, &type_ulong, &type_ulong, &type_ulong, | |
468 | &type_ulong, &type_ulong, &type_ulong, &type_ulong } }, | |
469 | { "copy", vrfy_copy, | |
470 | { &type_ulong, &type_ulong, &type_ulong, &type_string, &type_string } }, | |
471 | { 0, 0, { 0 } } | |
472 | }; | |
473 | ||
474 | int main(int argc, char *argv[]) | |
475 | { | |
476 | test_run(argc, argv, tests, SRCDIR "/t/rsvr"); | |
477 | return (0); | |
478 | } | |
479 | ||
480 | #endif | |
481 | ||
482 | /*----- That's all, folks -------------------------------------------------*/ |