--- /dev/null
+/* -*-c-*-
+ *
+ * Reservoir and buffer handling
+ *
+ * (c) 2017 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Library General Public License as published
+ * by the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * Catacomb is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb. If not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+ * USA.
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "rsvr.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @rsvr_mkplan@ --- *
+ *
+ * Arguments: @rsvr_plan *plan@ = pointer to plan to fill in
+ * @const rsvr_policy *pol@ = reservoir policy to follow
+ * @size_t used@ = amount of data in the reservoir
+ * @size_t insz@ = amount of fresh input data arriving
+ *
+ * Returns: ---
+ *
+ * Use: Prepares a plan for feeding input data into a block-oriented
+ * operation.
+ *
+ * The caller's code for following the plan proceeds in four
+ * parts.
+ *
+ * 1. Insert the first @plan->head@ input items into the
+ * reservoir; there will be sufficient space, and
+ * @plan->head@ will be at most @pol->blksz@.
+ *
+ * 2. Process the first @plan->from_rsvr@ items from the
+ * reservoir, shifting the remaining items forward;
+ * @plan->from_rsvr@ will be a multiple of @pol->blksz@.
+ *
+ * 3. Process the next @plan->from_input@ items directly from
+ * the input; @plan->from_input@ will be a multiple of
+ * @pol->blksz@.
+ *
+ * 4. Insert the remaining @plan->tail@ input items into the
+ * reservoir for next time.
+ */
+
+void rsvr_mkplan(rsvr_plan *plan, const rsvr_policy *pol,
+ size_t used, size_t insz)
+{
+ unsigned extra = !!(pol->f&RSVRF_FULL);
+ unsigned n, final;
+
+ if (insz < pol->rsvrsz - used + extra) {
+ /* Easy case: there's enough space in the reservoir for the whole input,
+ * so just accumulate it and we're done.
+ */
+
+ plan->head = insz;
+ plan->from_rsvr = plan->from_input = plan->tail = 0;
+ } else {
+ /* The hard case. We're going to have to actually process something. */
+
+ /* Firstly, we top the reservoir up to the next block boundary. */
+ n = (pol->rsvrsz - used)%pol->blksz;
+ plan->head = n; used += n; insz -= n;
+
+ /* Next, figure out the final amount we'll leave in the reservoir. This
+ * will be congruent to USED, modulo the block size, and within the last
+ * BLKSZ-wide interval permitted. We must have enough material to get
+ * here, or we'd be in the other branch above.
+ */
+ final = pol->rsvrsz - pol->blksz + extra +
+ (insz + pol->blksz - extra)%pol->blksz;
+
+ /* If we don't have enough input to drain the reservoir completely, and
+ * then top it up to the necessary level, then take as much as we can
+ * from the reservoir; otherwise, drain completely and then use up the
+ * remaining input directly.
+ */
+ if (insz < final) {
+ /* We don't have enough input to drain the reservoir completely and
+ * then top it up to the necessary final level. Take what we can.
+ */
+
+ plan->from_rsvr = used + insz - final;
+ plan->from_input = 0;
+ plan->tail = insz;
+ } else {
+ /* We have lots of input. Drain the reservoir fully, process the bulk
+ * of the input buffer, and load the rest into the reservoir at the
+ * end.
+ */
+
+ plan->from_rsvr = used;
+ plan->from_input = insz - final;
+ plan->tail = final;
+ }
+ }
+}
+
+/* --- @rsvr_setup@ --- *
+ *
+ * Arguments: @rsvr_state *st@ = pointer to state structure to fill in
+ * @const rsvr_policy *pol@ = reservoir policy to follow
+ * @void *rsvr@ = pointer to the actual reservoir
+ * @unsigned *used@ = pointer to the reservoir level
+ * @const void *in@ = pointer to the input data
+ * @size_t insz@ = size of the input
+ *
+ * Returns: ---
+ *
+ * Use: Prepares for a simple operation. This performs the initial
+ * copy of input data into the reservoir, and prepares for the
+ * next step.
+ *
+ * After this, the calling code should usually proceed as
+ * follows.
+ *
+ * 1. Call @RSVR_NEXT@ in a sequence of loops, with
+ * successively smaller values of @n@, to process waiting
+ * data from the reservoir. Usually, each @n@ will be some
+ * multiple of the block size @pol->blksz@, and the final
+ * loop will have @n = pol->blksz@.
+ *
+ * 2. Call @rsvr_done@ to indicate that this has been done.
+ *
+ * 3. Call @RSVR_NEXT@ in a sequence of loops, as in step 1,
+ * to process the remaining data from the input buffer.
+ *
+ * 4. Call @rsvr_done@ to indicate that the job is complete.
+ */
+
+void rsvr_setup(rsvr_state *st, const rsvr_policy *pol,
+ void *rsvr, unsigned *used, const void *in, size_t insz)
+{
+ rsvr_mkplan(&st->plan, pol, *used, insz);
+ st->rsvr = rsvr; st->in = in; st->used = used;
+
+ if (st->plan.head) {
+ memcpy(rsvr + *st->used, st->in, st->plan.head);
+ *st->used += st->plan.head; st->in += st->plan.head;
+ }
+ st->src = RSVRSRC_RSVR; st->p = st->rsvr; st->sz = st->plan.from_rsvr;
+}
+
+/* --- @RSVR_NEXT@, @rsvr_next@ --- *
+ *
+ * Arguments: @rsvr_state *st@ = pointer to the state structure
+ * @size_t n@ = amount of input data required, in bytes; should
+ * usually be a multiple of @pol->blksz@
+ *
+ * Returns: A pointer to the next @n@ bytes of input, or null if there is
+ * insufficient data remaining.
+ */
+
+const void *rsvr_next(rsvr_state *st, size_t n) { return RSVR_NEXT(st, n); }
+
+/* --- @rsvr_done@ --- *
+ *
+ * Arguments: @rsvr_state *st@ = pointer to the state structure
+ *
+ * Returns: Zero after the first pass, nonzero after the second.
+ *
+ * Use: Reports that the first or second stage (see @rsvr_setup@
+ * above) of an operation has been completed.
+ *
+ * If the first stage is complete, then this shifts stuff about
+ * in the reservoir and prepares for the second stage; if the
+ * second stage is complete, then it copies the remaining input
+ * into the reservoir and marks the state as complete.
+ */
+
+int rsvr_done(rsvr_state *st)
+{
+ assert(!st->sz);
+ switch (st->src) {
+ case RSVRSRC_RSVR:
+ if (st->plan.from_rsvr) {
+ if (st->plan.from_rsvr < *st->used) {
+ memmove(st->rsvr, st->rsvr + st->plan.from_rsvr,
+ *st->used - st->plan.from_rsvr);
+ }
+ *st->used -= st->plan.from_rsvr;
+ }
+ st->src = RSVRSRC_INPUT;
+ st->p = st->in; st->sz = st->plan.from_input;
+ return (0);
+ case RSVRSRC_INPUT:
+ if (st->plan.tail) {
+ memcpy(st->rsvr + *st->used, st->p, st->plan.tail);
+ *st->used += st->plan.tail;
+ }
+ st->src = RSVRSRC_DONE;
+ st->p = 0; st->sz = 0;
+ return (1);
+ default:
+ abort();
+ }
+}
+
+/*----- Testing -----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+#include <ctype.h>
+#include <errno.h>
+#include <stdio.h>
+
+#include <mLib/alloc.h>
+#include <mLib/bits.h>
+#include <mLib/darray.h>
+#include <mLib/report.h>
+#include <mLib/testrig.h>
+
+struct rng {
+ uint32 x;
+};
+
+static void init_rng(struct rng *r)
+ { r->x = 0; }
+
+static void step_rng(struct rng *r)
+ { r->x = U32(0x0d83c207*r->x + 0x380fcfea); }
+
+DA_DECL(uint_v, unsigned);
+
+struct testinfo {
+ rsvr_policy pol;
+ uint_v chunksz;
+ uint_v blksz;
+ unsigned used;
+ size_t off;
+ int ok;
+};
+
+static void show_uint_v(const char *what, const uint_v *v)
+{
+ size_t i;
+
+ printf("\t%s:", what);
+ for (i = 0; i < DA_LEN(v); i++) printf("%s%u", i ? ", " : " ", DA(v)[i]);
+ printf("\n");
+}
+
+static void report_policy(const struct rsvr_policy *pol)
+{
+ printf("\tpolicy: flags = 0x%08x%s; blksz = %u; rsvrsz = %u\n",
+ pol->f, pol->f&RSVRF_FULL ? " full" : pol->f ? "" : " nil",
+ pol->blksz, pol->rsvrsz);
+}
+
+static void report_testinfo(const struct testinfo *info)
+{
+ report_policy(&info->pol);
+ show_uint_v("chunksz", &info->chunksz);
+ show_uint_v("blksz", &info->blksz);
+ printf("\treservoir level = %u\n", info->used);
+ printf("\toffset = %lu\n", (unsigned long)info->off);
+}
+
+static void check(struct rng *r, struct testinfo *info,
+ const void *p, size_t sz)
+{
+ const octet *q = p;
+ unsigned x;
+
+ while (sz) {
+ x = U8(r->x);
+ if (info->ok && *q != x) {
+ printf("\n*** FAIL data mismatch (0x%02x /= 0x%02x)\n", *q, x);
+ report_testinfo(info);
+ info->ok = 0;
+ }
+ q++; sz--; info->off++;
+ step_rng(r);
+ }
+}
+
+static void parse_intlist(uint_v *v, const char *p)
+{
+ char *q;
+ unsigned long n;
+ int e = errno;
+
+ for (;;) {
+ while (isspace((unsigned char)*p)) p++;
+ if (!*p) break;
+ if (*p == ',') p++;
+ while (isspace((unsigned char)*p)) p++;
+ errno = 0; n = strtoul(p, &q, 0);
+ if (errno || (*q && *q != ',' && !isspace((unsigned char)*q)))
+ die(1, "invalid int list");
+ p = q; DA_PUSH(v, n);
+ }
+ errno = e;
+}
+
+int vrfy_plan(dstr *dv)
+{
+ rsvr_policy pol;
+ rsvr_plan want, calc;
+ unsigned used;
+ size_t insz;
+ int ok = 1;
+
+ pol.f = *(unsigned long *)dv[0].buf;
+ pol.blksz = *(unsigned long *)dv[1].buf;
+ pol.rsvrsz = *(unsigned long *)dv[2].buf;
+ used = *(unsigned long *)dv[3].buf;
+ insz = *(unsigned long *)dv[4].buf;
+ want.head = *(unsigned long *)dv[5].buf;
+ want.from_rsvr = *(unsigned long *)dv[6].buf;
+ want.from_input = *(unsigned long *)dv[7].buf;
+ want.tail = *(unsigned long *)dv[8].buf;
+
+ rsvr_mkplan(&calc, &pol, used, insz);
+
+ if (want.head != calc.head ||
+ want.from_rsvr != calc.from_rsvr ||
+ want.from_input != calc.from_input ||
+ want.tail != calc.tail) {
+ printf("\n*** FAIL plan doesn't match\n");
+ report_policy(&pol);
+ printf("\treservoir level = %u\n", used);
+ printf("\tinput size = %lu\n", (unsigned long)insz);
+#define SHOW(what, slot) do { \
+ printf("\t" what " (calc) %lu %s %lu (want)\n", \
+ (unsigned long)calc.slot, \
+ calc.slot == want.slot ? "=" : "/=", \
+ (unsigned long)want.slot); \
+} while(0)
+ SHOW("head", head);
+ SHOW("from reservoir", from_rsvr);
+ SHOW("from input", from_input);
+ SHOW("tail", tail);
+#undef SHOW
+ ok = 0;
+ }
+
+ return (ok);
+}
+
+static int vrfy_copy(dstr *dv)
+{
+ struct testinfo info;
+ rsvr_state st;
+ struct rng ra, rb;
+ octet *buf = 0, *rsvr;
+ const void *p;
+ size_t i, j, bsz = 0;
+ unsigned n, used0, lb, ub, fin;
+
+ init_rng(&ra); init_rng(&rb);
+ info.pol.f = *(unsigned long *)dv[0].buf;
+ info.pol.blksz = *(unsigned long *)dv[1].buf;
+ info.pol.rsvrsz = *(unsigned long *)dv[2].buf;
+ info.ok = 1; info.used = 0; info.off = 0;
+ rsvr = xmalloc(info.pol.rsvrsz);
+ DA_CREATE(&info.chunksz); parse_intlist(&info.chunksz, dv[3].buf);
+ DA_CREATE(&info.blksz); parse_intlist(&info.blksz, dv[4].buf);
+ for (i = 0; i < DA_LEN(&info.chunksz); i++)
+ if (bsz < DA(&info.chunksz)[i]) bsz = DA(&info.chunksz)[i];
+ buf = xmalloc(bsz);
+ for (i = 0; i < DA_LEN(&info.chunksz); i++) {
+ n = DA(&info.chunksz)[i];
+ for (j = 0; j < n; j++) { buf[j] = U8(ra.x); step_rng(&ra); }
+ used0 = info.used;
+ rsvr_setup(&st, &info.pol, rsvr, &info.used, buf, n);
+ if (n != st.plan.head + st.plan.from_input + st.plan.tail) {
+ printf("\n*** FAIL input size crosscheck "
+ "(%u /= %u + %lu + %u = %lu)\n",
+ n,
+ st.plan.head, (unsigned long)st.plan.from_input, st.plan.tail,
+ (unsigned long)(st.plan.head +
+ st.plan.from_input +
+ st.plan.tail));
+ report_testinfo(&info);
+ info.ok = 0;
+ }
+ if (st.plan.from_rsvr%info.pol.blksz) {
+ printf("\n*** FAIL reservoir chunk %u misaligned\n",
+ st.plan.from_rsvr);
+ report_testinfo(&info);
+ info.ok = 0;
+ }
+ if (st.plan.from_input%info.pol.blksz) {
+ printf("\n*** FAIL direct chunk %lu misaligned\n",
+ (unsigned long)st.plan.from_input);
+ report_testinfo(&info);
+ info.ok = 0;
+ }
+ if (st.plan.head > info.pol.rsvrsz - used0) {
+ printf("\n*** FAIL top-up out of range (%u + %u = %u > %u)\n",
+ used0, st.plan.head, used0 + st.plan.head, info.pol.rsvrsz);
+ report_testinfo(&info);
+ info.ok = 0;
+ }
+ if (st.plan.from_rsvr > used0 + st.plan.head) {
+ printf("\n*** FAIL shift out of range (%u > %u + %u = %u)\n",
+ st.plan.from_rsvr,
+ used0, st.plan.head, used0 + st.plan.head);
+ report_testinfo(&info);
+ info.ok = 0;
+ }
+ if (st.plan.head != n) {
+ ub = info.pol.rsvrsz + !!(info.pol.f&RSVRF_FULL);
+ lb = ub - info.pol.blksz;
+ fin = used0 + st.plan.head - st.plan.from_rsvr + st.plan.tail;
+ if (lb > fin) {
+ printf("\n*** FAIL final level out of bounds "
+ "(%u > %u = %u + %u - %u + %u)\n",
+ lb, fin,
+ used0, st.plan.head, st.plan.from_rsvr, st.plan.tail);
+ report_testinfo(&info);
+ info.ok = 0;
+ }
+ if (fin >= ub) {
+ printf("\n*** FAIL final level out of bounds "
+ "(%u + %u - %u + %u = %u >= %u)\n",
+ used0, st.plan.head, st.plan.from_rsvr, st.plan.tail,
+ fin, ub);
+ report_testinfo(&info);
+ info.ok = 0;
+ }
+ }
+
+ if (!info.ok) break;
+ RSVR_DO(&st) {
+ for (j = 0; j < DA_LEN(&info.blksz); j++) {
+ n = DA(&info.blksz)[j];
+ while ((p = RSVR_NEXT(&st, n)) != 0) check(&rb, &info, p, n);
+ }
+ }
+ }
+
+ DA_DESTROY(&info.chunksz);
+ DA_DESTROY(&info.blksz);
+ xfree(rsvr); xfree(buf);
+ return (info.ok);
+}
+
+static const struct test_chunk tests[] = {
+ { "plan", vrfy_plan,
+ { &type_ulong, &type_ulong, &type_ulong, &type_ulong, &type_ulong,
+ &type_ulong, &type_ulong, &type_ulong, &type_ulong } },
+ { "copy", vrfy_copy,
+ { &type_ulong, &type_ulong, &type_ulong, &type_string, &type_string } },
+ { 0, 0, { 0 } }
+};
+
+int main(int argc, char *argv[])
+{
+ test_run(argc, argv, tests, SRCDIR "/t/rsvr");
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * Reservoir and buffer handling
+ *
+ * (c) 2017 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Catacomb.
+ *
+ * Catacomb is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Library General Public License as published
+ * by the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * Catacomb is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb. If not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+ * USA.
+ */
+
+#ifndef CATACOMB_RSVR_H
+#define CATACOMB_RSVR_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stddef.h>
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct rsvr_policy {
+ unsigned f; /* Flags... */
+#define RSVRF_FULL 1u /* Hold back a full reservoir */
+ unsigned blksz; /* Block size */
+ unsigned rsvrsz; /* Reservoir size; multiple of
+ * @blksz@ */
+} rsvr_policy;
+
+typedef struct rsvr_plan {
+ unsigned head; /* First, accumulate @head@ bytes
+ * into the reservoir */
+ unsigned from_rsvr; /* Next, process @from_rsvr@ bytes
+ * from the reservoir */
+ size_t from_input; /* Then, process @from_input@ bytes
+ * directly from the input */
+ unsigned tail; /* Finally, accumulate the remaining
+ * @tail@ bytes of input into the
+ * reservoir */
+} rsvr_plan;
+
+enum { RSVRSRC_RSVR, RSVRSRC_INPUT, RSVRSRC_DONE };
+
+typedef struct rsvr_state {
+ rsvr_plan plan;
+ unsigned *used;
+ unsigned char *rsvr;
+ const unsigned char *in, *p;
+ size_t sz;
+ unsigned src;
+} rsvr_state;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @rsvr_mkplan@ --- *
+ *
+ * Arguments: @rsvr_plan *plan@ = pointer to plan to fill in
+ * @const rsvr_policy *pol@ = reservoir policy to follow
+ * @size_t used@ = amount of data in the reservoir
+ * @size_t insz@ = amount of fresh input data arriving
+ *
+ * Returns: ---
+ *
+ * Use: Prepares a plan for feeding input data into a block-oriented
+ * operation.
+ *
+ * The caller's code for following the plan proceeds in four
+ * parts.
+ *
+ * 1. Insert the first @plan->head@ input items into the
+ * reservoir; there will be sufficient space, and
+ * @plan->head@ will be at most @pol->blksz@.
+ *
+ * 2. Process the first @plan->from_rsvr@ items from the
+ * reservoir, shifting the remaining items forward;
+ * @plan->from_rsvr@ will be a multiple of @pol->blksz@.
+ *
+ * 3. Process the next @plan->from_input@ items directly from
+ * the input; @plan->from_input@ will be a multiple of
+ * @pol->blksz@.
+ *
+ * 4. Insert the remaining @plan->tail@ input items into the
+ * reservoir for next time.
+ */
+
+extern void rsvr_mkplan(rsvr_plan */*plan*/, const rsvr_policy */*pol*/,
+ size_t /*used*/, size_t /*insz*/);
+
+/* --- @rsvr_setup@ --- *
+ *
+ * Arguments: @rsvr_state *st@ = pointer to state structure to fill in
+ * @const rsvr_policy *pol@ = reservoir policy to follow
+ * @void *rsvr@ = pointer to the actual reservoir
+ * @unsigned *used@ = pointer to the reservoir level
+ * @const void *in@ = pointer to the input data
+ * @size_t insz@ = size of the input
+ *
+ * Returns: ---
+ *
+ * Use: Prepares for a simple operation. This performs the initial
+ * copy of input data into the reservoir, and prepares for the
+ * next step.
+ *
+ * After this, the calling code should usually proceed as
+ * follows.
+ *
+ * 1. Call @RSVR_NEXT@ in a sequence of loops, with
+ * successively smaller values of @n@, to process waiting
+ * data from the reservoir. Usually, each @n@ will be some
+ * multiple of the block size @pol->blksz@, and the final
+ * loop will have @n = pol->blksz@.
+ *
+ * 2. Call @rsvr_done@ to indicate that this has been done.
+ *
+ * 3. Call @RSVR_NEXT@ in a sequence of loops, as in step 1,
+ * to process the remaining data from the input buffer.
+ *
+ * 4. Call @rsvr_done@ to indicate that the job is complete.
+ */
+
+extern void rsvr_setup(rsvr_state */*st*/, const rsvr_policy */*pol*/,
+ void */*rsvr*/, unsigned */*used*/,
+ const void */*in*/, size_t /*insz*/);
+
+/* --- @RSVR_NEXT@, @rsvr_next@ --- *
+ *
+ * Arguments: @rsvr_state *st@ = pointer to the state structure
+ * @size_t n@ = amount of input data required, in bytes; should
+ * usually be a multiple of @pol->blksz@
+ *
+ * Returns: A pointer to the next @n@ bytes of input, or null if there is
+ * insufficient data remaining.
+ */
+
+#define RSVR_NEXT(st, n) \
+ ((n) > (st)->sz \
+ ? 0 \
+ : ((st)->sz -= (n), \
+ (st)->p += (n), \
+ (const void *)((st)->p - (n))))
+extern const void *rsvr_next(rsvr_state */*st*/, size_t /*n*/);
+
+/* --- @rsvr_done@ --- *
+ *
+ * Arguments: @rsvr_state *st@ = pointer to the state structure
+ *
+ * Returns: Zero after the first pass, nonzero after the second.
+ *
+ * Use: Reports that the first or second stage (see @rsvr_setup@
+ * above) of an operation has been completed.
+ *
+ * If the first stage is complete, then this shifts stuff about
+ * in the reservoir and prepares for the second stage; if the
+ * second stage is complete, then it copies the remaining input
+ * into the reservoir and marks the state as complete.
+ */
+
+extern int rsvr_done(rsvr_state */*st*/);
+
+/* --- @RSVR_DO@ --- *
+ *
+ * Arguments: @st@ = pointer to state structure
+ *
+ * Use: Invoke as @RSVR_DO(st) stmt@: performs two passes of @stmt@
+ * over the reservoir and input buffers respectively.
+ */
+
+#define RSVR_DO(st) switch (0) while (!rsvr_done(st)) case 0:
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif