chiark - git - mdw - catacomb/blob - base/rsvr.c

   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>
 234 #include <mLib/macros.h>
 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 (;;) {
 309     while (ISSPACE(*p)) p++;
 310     if (!*p) break;
 311     if (*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);
 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 -------------------------------------------------*/