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/report.h>
 235 #include <mLib/testrig.h>
 236
 237 struct rng {
 238   uint32 x;
 239 };
 240
 241 static void init_rng(struct rng *r)
 242   { r->x = 0; }
 243
 244 static void step_rng(struct rng *r)
 245   { r->x = U32(0x0d83c207*r->x + 0x380fcfea); }
 246
 247 DA_DECL(uint_v, unsigned);
 248
 249 struct testinfo {
 250   rsvr_policy pol;
 251   uint_v chunksz;
 252   uint_v blksz;
 253   unsigned used;
 254   size_t off;
 255   int ok;
 256 };
 257
 258 static void show_uint_v(const char *what, const uint_v *v)
 259 {
 260   size_t i;
 261
 262   printf("\t%s:", what);
 263   for (i = 0; i < DA_LEN(v); i++) printf("%s%u", i ? ", " : " ", DA(v)[i]);
 264   printf("\n");
 265 }
 266
 267 static void report_policy(const struct rsvr_policy *pol)
 268 {
 269   printf("\tpolicy: flags = 0x%08x%s; blksz = %u; rsvrsz = %u\n",
 270          pol->f, pol->f&RSVRF_FULL ? " full" : pol->f ? "" : " nil",
 271          pol->blksz, pol->rsvrsz);
 272 }
 273
 274 static void report_testinfo(const struct testinfo *info)
 275 {
 276   report_policy(&info->pol);
 277   show_uint_v("chunksz", &info->chunksz);
 278   show_uint_v("blksz", &info->blksz);
 279   printf("\treservoir level = %u\n", info->used);
 280   printf("\toffset = %lu\n", (unsigned long)info->off);
 281 }
 282
 283 static void check(struct rng *r, struct testinfo *info,
 284                   const void *p, size_t sz)
 285 {
 286   const octet *q = p;
 287   unsigned x;
 288
 289   while (sz) {
 290     x = U8(r->x);
 291     if (info->ok && *q != x) {
 292       printf("\n*** FAIL data mismatch (0x%02x /= 0x%02x)\n", *q, x);
 293       report_testinfo(info);
 294       info->ok = 0;
 295     }
 296     q++; sz--; info->off++;
 297     step_rng(r);
 298   }
 299 }
 300
 301 static void parse_intlist(uint_v *v, const char *p)
 302 {
 303   char *q;
 304   unsigned long n;
 305   int e = errno;
 306
 307   for (;;) {
 308     while (isspace((unsigned char)*p)) p++;
 309     if (!*p) break;
 310     if (*p == ',') p++;
 311     while (isspace((unsigned char)*p)) p++;
 312     errno = 0; n = strtoul(p, &q, 0);
 313     if (errno || (*q && *q != ',' && !isspace((unsigned char)*q)))
 314       die(1, "invalid int list");
 315     p = q; DA_PUSH(v, n);
 316   }
 317   errno = e;
 318 }
 319
 320 int vrfy_plan(dstr *dv)
 321 {
 322   rsvr_policy pol;
 323   rsvr_plan want, calc;
 324   unsigned used;
 325   size_t insz;
 326   int ok = 1;
 327
 328   pol.f = *(unsigned long *)dv[0].buf;
 329   pol.blksz = *(unsigned long *)dv[1].buf;
 330   pol.rsvrsz = *(unsigned long *)dv[2].buf;
 331   used = *(unsigned long *)dv[3].buf;
 332   insz = *(unsigned long *)dv[4].buf;
 333   want.head = *(unsigned long *)dv[5].buf;
 334   want.from_rsvr = *(unsigned long *)dv[6].buf;
 335   want.from_input = *(unsigned long *)dv[7].buf;
 336   want.tail = *(unsigned long *)dv[8].buf;
 337
 338   rsvr_mkplan(&calc, &pol, used, insz);
 339
 340   if (want.head != calc.head ||
 341       want.from_rsvr != calc.from_rsvr ||
 342       want.from_input != calc.from_input ||
 343       want.tail != calc.tail) {
 344     printf("\n*** FAIL plan doesn't match\n");
 345     report_policy(&pol);
 346     printf("\treservoir level = %u\n", used);
 347     printf("\tinput size = %lu\n", (unsigned long)insz);
 348 #define SHOW(what, slot) do {                                           \
 349   printf("\t" what " (calc) %lu %s %lu (want)\n",                       \
 350          (unsigned long)calc.slot,                                      \
 351          calc.slot == want.slot ? "=" : "/=",                           \
 352          (unsigned long)want.slot);                                     \
 353 } while(0)
 354     SHOW("head", head);
 355     SHOW("from reservoir", from_rsvr);
 356     SHOW("from input", from_input);
 357     SHOW("tail", tail);
 358 #undef SHOW
 359     ok = 0;
 360   }
 361
 362   return (ok);
 363 }
 364
 365 static int vrfy_copy(dstr *dv)
 366 {
 367   struct testinfo info;
 368   rsvr_state st;
 369   struct rng ra, rb;
 370   octet *buf = 0, *rsvr;
 371   const void *p;
 372   size_t i, j, bsz = 0;
 373   unsigned n, used0, lb, ub, fin;
 374
 375   init_rng(&ra); init_rng(&rb);
 376   info.pol.f = *(unsigned long *)dv[0].buf;
 377   info.pol.blksz = *(unsigned long *)dv[1].buf;
 378   info.pol.rsvrsz = *(unsigned long *)dv[2].buf;
 379   info.ok = 1; info.used = 0; info.off = 0;
 380   rsvr = xmalloc(info.pol.rsvrsz);
 381   DA_CREATE(&info.chunksz); parse_intlist(&info.chunksz, dv[3].buf);
 382   DA_CREATE(&info.blksz); parse_intlist(&info.blksz, dv[4].buf);
 383   for (i = 0; i < DA_LEN(&info.chunksz); i++)
 384     if (bsz < DA(&info.chunksz)[i]) bsz = DA(&info.chunksz)[i];
 385   buf = xmalloc(bsz);
 386   for (i = 0; i < DA_LEN(&info.chunksz); i++) {
 387     n = DA(&info.chunksz)[i];
 388     for (j = 0; j < n; j++) { buf[j] = U8(ra.x); step_rng(&ra); }
 389     used0 = info.used;
 390     rsvr_setup(&st, &info.pol, rsvr, &info.used, buf, n);
 391     if (n != st.plan.head + st.plan.from_input + st.plan.tail) {
 392       printf("\n*** FAIL input size crosscheck "
 393              "(%u /= %u + %lu + %u = %lu)\n",
 394              n,
 395              st.plan.head, (unsigned long)st.plan.from_input, st.plan.tail,
 396              (unsigned long)(st.plan.head +
 397                              st.plan.from_input +
 398                              st.plan.tail));
 399       report_testinfo(&info);
 400       info.ok = 0;
 401     }
 402     if (st.plan.from_rsvr%info.pol.blksz) {
 403       printf("\n*** FAIL reservoir chunk %u misaligned\n",
 404              st.plan.from_rsvr);
 405       report_testinfo(&info);
 406       info.ok = 0;
 407     }
 408     if (st.plan.from_input%info.pol.blksz) {
 409       printf("\n*** FAIL direct chunk %lu misaligned\n",
 410              (unsigned long)st.plan.from_input);
 411       report_testinfo(&info);
 412       info.ok = 0;
 413     }
 414     if (st.plan.head > info.pol.rsvrsz - used0) {
 415       printf("\n*** FAIL top-up out of range (%u + %u = %u > %u)\n",
 416              used0, st.plan.head, used0 + st.plan.head, info.pol.rsvrsz);
 417       report_testinfo(&info);
 418       info.ok = 0;
 419     }
 420     if (st.plan.from_rsvr > used0 + st.plan.head) {
 421       printf("\n*** FAIL shift out of range (%u > %u + %u = %u)\n",
 422              st.plan.from_rsvr,
 423              used0, st.plan.head, used0 + st.plan.head);
 424       report_testinfo(&info);
 425       info.ok = 0;
 426     }
 427     if (st.plan.head != n) {
 428       ub = info.pol.rsvrsz + !!(info.pol.f&RSVRF_FULL);
 429       lb = ub - info.pol.blksz;
 430       fin = used0 + st.plan.head - st.plan.from_rsvr + st.plan.tail;
 431       if (lb > fin) {
 432         printf("\n*** FAIL final level out of bounds "
 433                "(%u > %u = %u + %u - %u + %u)\n",
 434                lb, fin,
 435                used0, st.plan.head, st.plan.from_rsvr, st.plan.tail);
 436         report_testinfo(&info);
 437         info.ok = 0;
 438       }
 439       if (fin >= ub) {
 440         printf("\n*** FAIL final level out of bounds "
 441                "(%u + %u - %u + %u = %u >= %u)\n",
 442                used0, st.plan.head, st.plan.from_rsvr, st.plan.tail,
 443                fin, ub);
 444         report_testinfo(&info);
 445         info.ok = 0;
 446       }
 447     }
 448
 449     if (!info.ok) break;
 450     RSVR_DO(&st) {
 451       for (j = 0; j < DA_LEN(&info.blksz); j++) {
 452         n = DA(&info.blksz)[j];
 453         while ((p = RSVR_NEXT(&st, n)) != 0) check(&rb, &info, p, n);
 454       }
 455     }
 456   }
 457
 458   DA_DESTROY(&info.chunksz);
 459   DA_DESTROY(&info.blksz);
 460   xfree(rsvr); xfree(buf);
 461   return (info.ok);
 462 }
 463
 464 static const struct test_chunk tests[] = {
 465   { "plan", vrfy_plan,
 466     { &type_ulong, &type_ulong, &type_ulong, &type_ulong, &type_ulong,
 467       &type_ulong, &type_ulong, &type_ulong, &type_ulong } },
 468   { "copy", vrfy_copy,
 469     { &type_ulong, &type_ulong, &type_ulong, &type_string, &type_string } },
 470   { 0, 0, { 0 } }
 471 };
 472
 473 int main(int argc, char *argv[])
 474 {
 475   test_run(argc, argv, tests, SRCDIR "/t/rsvr");
 476   return (0);
 477 }
 478
 479 #endif
 480
 481 /*----- That's all, folks -------------------------------------------------*/