3be9ed1589de876e225a990f9b5ee7ada76b9609
3 * Reservoir and buffer handling
5 * (c) 2017 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
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.
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.
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,
28 /*----- Header files ------------------------------------------------------*/
36 /*----- Main code ---------------------------------------------------------*/
38 /* --- @rsvr_mkplan@ --- *
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
47 * Use: Prepares a plan for feeding input data into a block-oriented
50 * The caller's code for following the plan proceeds in four
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@.
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@.
61 * 3. Process the next @plan->from_input@ items directly from
62 * the input; @plan->from_input@ will be a multiple of
65 * 4. Insert the remaining @plan->tail@ input items into the
66 * reservoir for next time.
69 void rsvr_mkplan(rsvr_plan
*plan
, const rsvr_policy
*pol
,
70 size_t used
, size_t insz
)
72 unsigned extra
= !!(pol
->f
&RSVRF_FULL
);
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.
81 plan
->from_rsvr
= plan
->from_input
= plan
->tail
= 0;
83 /* The hard case. We're going to have to actually process something. */
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
;
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.
94 final
= pol
->rsvrsz
- pol
->blksz
+ extra
+
95 (insz
+ pol
->blksz
- extra
)%pol
->blksz
;
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.
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.
107 plan
->from_rsvr
= used
+ insz
- final
;
108 plan
->from_input
= 0;
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
116 plan
->from_rsvr
= used
;
117 plan
->from_input
= insz
- final
;
123 /* --- @rsvr_setup@ --- *
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
134 * Use: Prepares for a simple operation. This performs the initial
135 * copy of input data into the reservoir, and prepares for the
138 * After this, the calling code should usually proceed as
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@.
147 * 2. Call @rsvr_done@ to indicate that this has been done.
149 * 3. Call @RSVR_NEXT@ in a sequence of loops, as in step 1,
150 * to process the remaining data from the input buffer.
152 * 4. Call @rsvr_done@ to indicate that the job is complete.
155 void rsvr_setup(rsvr_state
*st
, const rsvr_policy
*pol
,
156 void *rsvr
, unsigned *used
, const void *in
, size_t insz
)
158 rsvr_mkplan(&st
->plan
, pol
, *used
, insz
);
159 st
->rsvr
= rsvr
; st
->in
= in
; st
->used
= used
;
162 memcpy(rsvr
+ *st
->used
, st
->in
, st
->plan
.head
);
163 *st
->used
+= st
->plan
.head
; st
->in
+= st
->plan
.head
;
165 st
->src
= RSVRSRC_RSVR
; st
->p
= st
->rsvr
; st
->sz
= st
->plan
.from_rsvr
;
168 /* --- @RSVR_NEXT@, @rsvr_next@ --- *
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@
174 * Returns: A pointer to the next @n@ bytes of input, or null if there is
175 * insufficient data remaining.
178 const void *rsvr_next(rsvr_state
*st
, size_t n
) { return RSVR_NEXT(st
, n
); }
180 /* --- @rsvr_done@ --- *
182 * Arguments: @rsvr_state *st@ = pointer to the state structure
184 * Returns: Zero after the first pass, nonzero after the second.
186 * Use: Reports that the first or second stage (see @rsvr_setup@
187 * above) of an operation has been completed.
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.
195 int rsvr_done(rsvr_state
*st
)
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
);
205 *st
->used
-= st
->plan
.from_rsvr
;
207 st
->src
= RSVRSRC_INPUT
;
208 st
->p
= st
->in
; st
->sz
= st
->plan
.from_input
;
212 memcpy(st
->rsvr
+ *st
->used
, st
->p
, st
->plan
.tail
);
213 *st
->used
+= st
->plan
.tail
;
215 st
->src
= RSVRSRC_DONE
;
216 st
->p
= 0; st
->sz
= 0;
223 /*----- Testing -----------------------------------------------------------*/
231 #include <mLib/alloc.h>
232 #include <mLib/bits.h>
233 #include <mLib/darray.h>
234 #include <mLib/macros.h>
235 #include <mLib/report.h>
236 #include <mLib/testrig.h>
242 static void init_rng(struct rng
*r
)
245 static void step_rng(struct rng
*r
)
246 { r
->x
= U32(0x0d83c207*r
->x
+ 0x380fcfea); }
248 DA_DECL(uint_v
, unsigned);
259 static void show_uint_v(const char *what
, const uint_v
*v
)
263 printf("\t%s:", what
);
264 for (i
= 0; i
< DA_LEN(v
); i
++) printf("%s%u", i ?
", " : " ", DA(v
)[i
]);
268 static void report_policy(const struct rsvr_policy
*pol
)
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
);
275 static void report_testinfo(const struct testinfo
*info
)
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
);
284 static void check(struct rng
*r
, struct testinfo
*info
,
285 const void *p
, size_t sz
)
292 if (info
->ok
&& *q
!= x
) {
293 printf("\n*** FAIL data mismatch (0x%02x /= 0x%02x)\n", *q
, x
);
294 report_testinfo(info
);
297 q
++; sz
--; info
->off
++;
302 static void parse_intlist(uint_v
*v
, const char *p
)
309 while (ISSPACE(*p
)) p
++;
312 while (ISSPACE(*p
)) p
++;
313 errno
= 0; n
= strtoul(p
, &q
, 0);
314 if (errno
|| (*q
&& *q
!= ',' && !ISSPACE(*q
)))
315 die(1, "invalid int list");
316 p
= q
; DA_PUSH(v
, n
);
321 int vrfy_plan(dstr
*dv
)
324 rsvr_plan want
, calc
;
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
;
339 rsvr_mkplan(&calc
, &pol
, used
, insz
);
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");
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); \
356 SHOW("from reservoir", from_rsvr
);
357 SHOW("from input", from_input
);
366 static int vrfy_copy(dstr
*dv
)
368 struct testinfo info
;
371 octet
*buf
= 0, *rsvr
;
373 size_t i
, j
, bsz
= 0;
374 unsigned n
, used0
, lb
, ub
, fin
;
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
];
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
); }
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",
396 st
.plan
.head
, (unsigned long)st
.plan
.from_input
, st
.plan
.tail
,
397 (unsigned long)(st
.plan
.head
+
400 report_testinfo(&info
);
403 if (st
.plan
.from_rsvr
%info
.pol
.blksz
) {
404 printf("\n*** FAIL reservoir chunk %u misaligned\n",
406 report_testinfo(&info
);
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
);
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
);
421 if (st
.plan
.from_rsvr
> used0
+ st
.plan
.head
) {
422 printf("\n*** FAIL shift out of range (%u > %u + %u = %u)\n",
424 used0
, st
.plan
.head
, used0
+ st
.plan
.head
);
425 report_testinfo(&info
);
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
;
433 printf("\n*** FAIL final level out of bounds "
434 "(%u > %u = %u + %u - %u + %u)\n",
436 used0
, st
.plan
.head
, st
.plan
.from_rsvr
, st
.plan
.tail
);
437 report_testinfo(&info
);
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
,
445 report_testinfo(&info
);
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
);
459 DA_DESTROY(&info
.chunksz
);
460 DA_DESTROY(&info
.blksz
);
461 xfree(rsvr
); xfree(buf
);
465 static const struct test_chunk tests
[] = {
467 { &type_ulong
, &type_ulong
, &type_ulong
, &type_ulong
, &type_ulong
,
468 &type_ulong
, &type_ulong
, &type_ulong
, &type_ulong
} },
470 { &type_ulong
, &type_ulong
, &type_ulong
, &type_string
, &type_string
} },
474 int main(int argc
, char *argv
[])
476 test_run(argc
, argv
, tests
, SRCDIR
"/t/rsvr");
482 /*----- That's all, folks -------------------------------------------------*/