xdelta3-test.h

   1 /* xdelta 3 - delta compression tools and library Copyright (C) 2001,
   2  * 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012.
   3  * Joshua P. MacDonald
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18  */
  19
  20 /* This is public-domain Mersenne Twister code,
  21  * attributed to Michael Brundage.  Thanks!
  22  * http://www.qbrundage.com/michaelb/pubs/essays/random_number_generation.html
  23  */
  24 static const uint32_t TEST_SEED1 = 5489UL;
  25 #define MT_LEN 624
  26 #define MT_IA 397
  27 static const uint32_t UPPER_MASK = 0x80000000;
  28 static const uint32_t LOWER_MASK = 0x7FFFFFFF;
  29 static const uint32_t MATRIX_A = 0x9908B0DF;
  30
  31 #ifndef SHELL_TESTS
  32 #define SHELL_TESTS 1
  33 #endif
  34
  35 typedef struct mtrand mtrand;
  36
  37 struct mtrand {
  38   int mt_index_;
  39   uint32_t mt_buffer_[MT_LEN];
  40 };
  41
  42 int test_compare_files (const char* tgt, const char *rec);
  43 void mt_init(mtrand *mt, uint32_t seed);
  44 uint32_t mt_random (mtrand *mt);
  45 int test_setup (void);
  46
  47 void mt_init(mtrand *mt, uint32_t seed) {
  48   int i;
  49   mt->mt_buffer_[0] = seed;
  50   mt->mt_index_ = MT_LEN;
  51   for (i = 1; i < MT_LEN; i++) {
  52     /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
  53     /* In the previous versions, MSBs of the seed affect   */
  54     /* only MSBs of the array mt[].                        */
  55     /* 2002/01/09 modified by Makoto Matsumoto             */
  56     mt->mt_buffer_[i] =
  57         (1812433253UL * (mt->mt_buffer_[i-1] ^
  58                          (mt->mt_buffer_[i-1] >> 30)) + i);
  59   }
  60 }
  61
  62 uint32_t mt_random (mtrand *mt) {
  63   uint32_t y;
  64   unsigned long mag01[2];
  65   mag01[0] = 0;
  66   mag01[1] = MATRIX_A;
  67
  68   if (mt->mt_index_ >= MT_LEN) {
  69     int kk;
  70
  71     for (kk = 0; kk < MT_LEN - MT_IA; kk++) {
  72       y = (mt->mt_buffer_[kk] & UPPER_MASK) |
  73         (mt->mt_buffer_[kk + 1] & LOWER_MASK);
  74       mt->mt_buffer_[kk] = mt->mt_buffer_[kk + MT_IA] ^
  75         (y >> 1) ^ mag01[y & 0x1UL];
  76     }
  77     for (;kk < MT_LEN - 1; kk++) {
  78       y = (mt->mt_buffer_[kk] & UPPER_MASK) |
  79         (mt->mt_buffer_[kk + 1] & LOWER_MASK);
  80       mt->mt_buffer_[kk] = mt->mt_buffer_[kk + (MT_IA - MT_LEN)] ^
  81         (y >> 1) ^ mag01[y & 0x1UL];
  82     }
  83     y = (mt->mt_buffer_[MT_LEN - 1] & UPPER_MASK) |
  84       (mt->mt_buffer_[0] & LOWER_MASK);
  85     mt->mt_buffer_[MT_LEN - 1] = mt->mt_buffer_[MT_IA - 1] ^
  86       (y >> 1) ^ mag01[y & 0x1UL];
  87     mt->mt_index_ = 0;
  88   }
  89
  90   y = mt->mt_buffer_[mt->mt_index_++];
  91
  92   y ^= (y >> 11);
  93   y ^= (y << 7) & 0x9d2c5680UL;
  94   y ^= (y << 15) & 0xefc60000UL;
  95   y ^= (y >> 18);
  96
  97   return y;
  98 }
  99
 100 static mtrand static_mtrand;
 101
 102 #include <math.h>
 103
 104 static uint32_t
 105 mt_exp_rand (uint32_t mean, uint32_t max_value)
 106 {
 107   double mean_d = mean;
 108   double erand  = log (1.0 / (mt_random (&static_mtrand) /
 109                               (double)UINT32_MAX));
 110   uint32_t x = (uint32_t) (mean_d * erand + 0.5);
 111
 112   return min (x, max_value);
 113 }
 114
 115 #if SHELL_TESTS
 116 #include <sys/wait.h>
 117 #endif
 118
 119 #define MSG_IS(x) (stream->msg != NULL && strcmp ((x), stream->msg) == 0)
 120
 121 static const usize_t TWO_MEGS_AND_DELTA = (3 << 20);
 122 static const usize_t ADDR_CACHE_ROUNDS = 10000;
 123
 124 static const usize_t TEST_FILE_MEAN   = 16384;
 125 static const double TEST_ADD_MEAN     = 128;
 126 static const double TEST_ADD_MAX      = 512;
 127 static const double TEST_ADD_RATIO    = 0.1;
 128 static const double TEST_EPSILON      = 0.25;
 129
 130 #define TESTBUFSIZE (1024 * 16)
 131
 132 #define TESTFILESIZE (1024)
 133
 134 static char   TEST_TARGET_FILE[TESTFILESIZE];
 135 static char   TEST_SOURCE_FILE[TESTFILESIZE];
 136 static char   TEST_DELTA_FILE[TESTFILESIZE];
 137 static char   TEST_RECON_FILE[TESTFILESIZE];
 138 static char   TEST_RECON2_FILE[TESTFILESIZE];
 139 static char   TEST_COPY_FILE[TESTFILESIZE];
 140 static char   TEST_NOPERM_FILE[TESTFILESIZE];
 141
 142 #define CHECK(cond) if (!(cond)) { XPR(NT "check failure: " #cond); abort(); }
 143
 144 #if SHELL_TESTS
 145 /* Use a fixed soft config so that test values are fixed.  See also
 146  * test_compress_text(). */
 147 static const char* test_softcfg_str = "-C9,3,4,8,2,36,70";
 148 #endif
 149
 150 /***********************************************************************
 151  TEST HELPERS
 152  ***********************************************************************/
 153
 154 static void DOT (void) { XPR(NTR "."); }
 155 static int do_cmd (xd3_stream *stream, const char *buf)
 156 {
 157   int ret;
 158   if ((ret = system (buf)) != 0)
 159     {
 160       if (WIFEXITED (ret))
 161         {
 162           stream->msg = "command exited non-zero";
 163           IF_DEBUG1 (XPR(NT "command was: %s\n", buf));
 164         }
 165       else
 166         {
 167           stream->msg = "abnormal command termination";
 168         }
 169       return ret;
 170     }
 171   return 0;
 172 }
 173
 174 static int do_fail (xd3_stream *stream, const char *buf)
 175 {
 176   int ret;
 177   ret = system (buf);
 178   if (! WIFEXITED (ret) || WEXITSTATUS (ret) != 1)
 179     {
 180       stream->msg = "command should have not succeeded";
 181       XPR(NT "command was %s\n", buf);
 182       return XD3_INTERNAL;
 183     }
 184   return 0;
 185 }
 186
 187 /* Test that the exponential distribution actually produces its mean. */
 188 static int
 189 test_random_numbers (xd3_stream *stream, int ignore)
 190 {
 191   usize_t i;
 192   usize_t sum = 0;
 193   usize_t mean = 50;
 194   usize_t n_rounds = 1000000;
 195   double average, error;
 196   double allowed_error = 0.1;
 197
 198   mt_init (& static_mtrand, 0x9f73f7fe);
 199
 200   for (i = 0; i < n_rounds; i += 1)
 201     {
 202       sum += mt_exp_rand (mean, USIZE_T_MAX);
 203     }
 204
 205   average = (double) sum / (double) n_rounds;
 206   error   = average - (double) mean;
 207
 208   if (error < allowed_error && error > -allowed_error)
 209     {
 210       return 0;
 211     }
 212
 213   /*XPR(NT "error is %f\n", error);*/
 214   stream->msg = "random distribution looks broken";
 215   return XD3_INTERNAL;
 216 }
 217
 218 static void
 219 test_unlink (char* file)
 220 {
 221   int ret;
 222   if ((ret = unlink (file)) != 0 && errno != ENOENT)
 223     {
 224       XPR(NT "unlink %s failed: %s\n", file, strerror(ret));
 225     }
 226 }
 227
 228 static void
 229 test_cleanup (void)
 230 {
 231 #if 1
 232   test_unlink (TEST_TARGET_FILE);
 233   test_unlink (TEST_SOURCE_FILE);
 234   test_unlink (TEST_DELTA_FILE);
 235   test_unlink (TEST_RECON_FILE);
 236   test_unlink (TEST_RECON2_FILE);
 237   test_unlink (TEST_COPY_FILE);
 238   test_unlink (TEST_NOPERM_FILE);
 239 #endif
 240 }
 241
 242 int test_setup (void)
 243 {
 244   static int x = 0;
 245   x++;
 246   snprintf_func (TEST_TARGET_FILE, TESTFILESIZE, "/tmp/xdtest.target.%d", x);
 247   snprintf_func (TEST_SOURCE_FILE, TESTFILESIZE, "/tmp/xdtest.source.%d", x);
 248   snprintf_func (TEST_DELTA_FILE, TESTFILESIZE, "/tmp/xdtest.delta.%d", x);
 249   snprintf_func (TEST_RECON_FILE, TESTFILESIZE, "/tmp/xdtest.recon.%d", x);
 250   snprintf_func (TEST_RECON2_FILE, TESTFILESIZE, "/tmp/xdtest.recon2.%d", x);
 251   snprintf_func (TEST_COPY_FILE, TESTFILESIZE, "/tmp/xdtest.copy.%d", x);
 252   snprintf_func (TEST_NOPERM_FILE, TESTFILESIZE, "/tmp/xdtest.noperm.%d", x);
 253   test_cleanup();
 254   return 0;
 255 }
 256
 257 static int
 258 test_make_inputs (xd3_stream *stream, xoff_t *ss_out, xoff_t *ts_out)
 259 {
 260   usize_t ts = (mt_random (&static_mtrand) % TEST_FILE_MEAN) +
 261     TEST_FILE_MEAN / 2;
 262   usize_t ss = (mt_random (&static_mtrand) % TEST_FILE_MEAN) +
 263     TEST_FILE_MEAN / 2;
 264   uint8_t *buf = (uint8_t*) malloc (ts + ss), *sbuf = buf, *tbuf = buf + ss;
 265   usize_t sadd = 0, sadd_max = (usize_t)(ss * TEST_ADD_RATIO);
 266   FILE  *tf = NULL, *sf = NULL;
 267   usize_t i, j;
 268   int ret;
 269
 270   if (buf == NULL) { return ENOMEM; }
 271
 272   if ((tf = fopen (TEST_TARGET_FILE, "w")) == NULL ||
 273       (ss_out != NULL && (sf = fopen (TEST_SOURCE_FILE, "w")) == NULL))
 274     {
 275       stream->msg = "write failed";
 276       ret = get_errno ();
 277       goto failure;
 278     }
 279
 280   if (ss_out != NULL)
 281     {
 282       for (i = 0; i < ss; )
 283         {
 284           sbuf[i++] = (uint8_t) mt_random (&static_mtrand);
 285         }
 286     }
 287
 288   /* Then modify the data to produce copies, everything not copied is
 289    * an add.  The following logic produces the TEST_ADD_RATIO.  The
 290    * variable SADD contains the number of adds so far, which should
 291    * not exceed SADD_MAX. */
 292
 293   /* XPR(NT "ss = %u ts = %u\n", ss, ts); */
 294   for (i = 0; i < ts; )
 295     {
 296       usize_t left = ts - i;
 297       usize_t next = mt_exp_rand ((uint32_t) TEST_ADD_MEAN,
 298                                   (uint32_t) TEST_ADD_MAX);
 299       usize_t add_left = sadd_max - sadd;
 300       double add_prob = (left == 0) ? 0 : (add_left / (double) left);
 301       int do_copy;
 302
 303       next = min (left, next);
 304       do_copy = (next > add_left ||
 305                  (mt_random (&static_mtrand) / \
 306                   (double)USIZE_T_MAX) >= add_prob);
 307
 308       if (ss_out == NULL)
 309         {
 310           do_copy &= (i > 0);
 311         }
 312       else
 313         {
 314           do_copy &= (ss - next) > 0;
 315         }
 316
 317       if (do_copy)
 318         {
 319           /* Copy */
 320           size_t offset = mt_random (&static_mtrand) % ((ss_out == NULL) ?
 321                                                         i :
 322                                                         (ss - next));
 323           /* XPR(NT "[%u] copy %u at %u ", i, next, offset); */
 324
 325           for (j = 0; j < next; j += 1)
 326             {
 327               char c = ((ss_out == NULL) ? tbuf : sbuf)[offset + j];
 328               /* XPR(NT "%x%x", (c >> 4) & 0xf, c & 0xf); */
 329               tbuf[i++] = c;
 330             }
 331           /* XPR(NT "\n"); */
 332         }
 333       else
 334         {
 335           /* Add */
 336           /* XPR(NT "[%u] add %u ", i, next); */
 337           for (j = 0; j < next; j += 1)
 338             {
 339               char c = (char) mt_random (&static_mtrand);
 340               /* XPR(NT "%x%x", (c >> 4) & 0xf, c & 0xf); */
 341               tbuf[i++] = c;
 342             }
 343           /* XPR(NT "\n"); */
 344           sadd += next;
 345         }
 346     }
 347
 348   /* XPR(NT "sadd = %u max = %u\n", sadd, sadd_max); */
 349
 350   if ((fwrite (tbuf, 1, ts, tf) != ts) ||
 351       (ss_out != NULL && (fwrite (sbuf, 1, ss, sf) != ss)))
 352     {
 353       stream->msg = "write failed";
 354       ret = get_errno ();
 355       goto failure;
 356     }
 357
 358   if ((ret = fclose (tf)) || (ss_out != NULL && (ret = fclose (sf))))
 359     {
 360       stream->msg = "close failed";
 361       ret = get_errno ();
 362       goto failure;
 363     }
 364
 365   if (ts_out) { (*ts_out) = ts; }
 366   if (ss_out) { (*ss_out) = ss; }
 367
 368  failure:
 369   free (buf);
 370   return ret;
 371 }
 372
 373 int
 374 test_compare_files (const char* tgt, const char *rec)
 375 {
 376   FILE *orig, *recons;
 377   static uint8_t obuf[TESTBUFSIZE], rbuf[TESTBUFSIZE];
 378   xoff_t offset = 0;
 379   size_t i;
 380   size_t oc, rc;
 381   xoff_t diffs = 0;
 382
 383   if ((orig = fopen (tgt, "r")) == NULL)
 384     {
 385       XPR(NT "open %s failed\n", tgt);
 386       return get_errno ();
 387     }
 388
 389   if ((recons = fopen (rec, "r")) == NULL)
 390     {
 391       XPR(NT "open %s failed\n", rec);
 392       return get_errno ();
 393     }
 394
 395   for (;;)
 396     {
 397       oc = fread (obuf, 1, TESTBUFSIZE, orig);
 398       rc = fread (rbuf, 1, TESTBUFSIZE, recons);
 399
 400       if (oc != rc)
 401         {
 402           return XD3_INTERNAL;
 403         }
 404
 405       if (oc == 0)
 406         {
 407           break;
 408         }
 409
 410       for (i = 0; i < oc; i += 1)
 411         {
 412           if (obuf[i] != rbuf[i])
 413             {
 414               XPR(NT "byte %u (read %u @ %"Q"u) %d != %d\n",
 415                   (int)i, (int)oc, offset, obuf[i], rbuf[i]);
 416               diffs++;
 417               return XD3_INTERNAL;
 418             }
 419         }
 420
 421       offset += oc;
 422     }
 423
 424     fclose (orig);
 425     fclose (recons);
 426     if (diffs != 0)
 427       {
 428         return XD3_INTERNAL;
 429       }
 430     return 0;
 431 }
 432
 433 static int
 434 test_copy_to (const char *from, const char *to)
 435 {
 436   char buf[TESTBUFSIZE];
 437   int ret;
 438
 439   snprintf_func (buf, TESTBUFSIZE, "cp -f %s %s", from, to);
 440
 441   if ((ret = system (buf)) != 0)
 442     {
 443       return XD3_INTERNAL;
 444     }
 445
 446   return 0;
 447 }
 448
 449 static int
 450 test_save_copy (const char *origname)
 451 {
 452   return test_copy_to(origname, TEST_COPY_FILE);
 453 }
 454
 455 static int
 456 test_file_size (const char* file, xoff_t *size)
 457 {
 458   struct stat sbuf;
 459   int ret;
 460   (*size) = 0;
 461
 462   if (stat (file, & sbuf) < 0)
 463     {
 464       ret = get_errno ();
 465       XPR(NT "stat failed: %s: %s\n", file, strerror (ret));
 466       return ret;
 467     }
 468
 469   if (! S_ISREG (sbuf.st_mode))
 470     {
 471       ret = XD3_INTERNAL;
 472       XPR(NT "not a regular file: %s: %s\n", file, strerror (ret));
 473       return ret;
 474     }
 475
 476   (*size) = sbuf.st_size;
 477   return 0;
 478 }
 479
 480 /***********************************************************************
 481  READ OFFSET
 482  ***********************************************************************/
 483
 484 /* Common test for read_integer errors: encodes a 64-bit value and
 485  * then attempts to read as a 32-bit value.  If TRUNC is non-zero,
 486  * attempts to get errors by shortening the input, otherwise it should
 487  * overflow.  Expects XD3_INTERNAL and MSG. */
 488 static int
 489 test_read_integer_error (xd3_stream *stream, usize_t trunto, const char *msg)
 490 {
 491   uint64_t eval = 1ULL << 34;
 492   uint32_t rval;
 493   xd3_output *buf = NULL;
 494   const uint8_t *max;
 495   const uint8_t *inp;
 496   int ret;
 497
 498   buf = xd3_alloc_output (stream, buf);
 499
 500   if ((ret = xd3_emit_uint64_t (stream, & buf, eval)))
 501     {
 502       goto fail;
 503     }
 504
 505  again:
 506
 507   inp = buf->base;
 508   max = buf->base + buf->next - trunto;
 509
 510   if ((ret = xd3_read_uint32_t (stream, & inp, max, & rval)) !=
 511       XD3_INVALID_INPUT ||
 512       !MSG_IS (msg))
 513     {
 514       ret = XD3_INTERNAL;
 515     }
 516   else if (trunto && trunto < buf->next)
 517     {
 518       trunto += 1;
 519       goto again;
 520     }
 521   else
 522     {
 523       ret = 0;
 524     }
 525
 526  fail:
 527   xd3_free_output (stream, buf);
 528   return ret;
 529 }
 530
 531 /* Test integer overflow using the above routine. */
 532 static int
 533 test_decode_integer_overflow (xd3_stream *stream, int unused)
 534 {
 535   return test_read_integer_error (stream, 0, "overflow in read_intger");
 536 }
 537
 538 /* Test integer EOI using the above routine. */
 539 static int
 540 test_decode_integer_end_of_input (xd3_stream *stream, int unused)
 541 {
 542   return test_read_integer_error (stream, 1, "end-of-input in read_integer");
 543 }
 544
 545 /* Test that emit_integer/decode_integer/sizeof_integer/read_integer
 546  * work on correct inputs.  Tests powers of (2^7), plus or minus, up
 547  * to the maximum value. */
 548 #define TEST_ENCODE_DECODE_INTEGER(TYPE,ONE,MAX) \
 549   xd3_output *rbuf = NULL; \
 550   xd3_output *dbuf = NULL; \
 551   TYPE values[64]; \
 552   usize_t nvalues = 0; \
 553   usize_t i; \
 554   int ret = 0; \
 555  \
 556   for (i = 0; i < (sizeof (TYPE) * 8); i += 7) \
 557     { \
 558       values[nvalues++] = (ONE << i) - ONE; \
 559       values[nvalues++] = (ONE << i); \
 560       values[nvalues++] = (ONE << i) + ONE; \
 561     } \
 562  \
 563   values[nvalues++] = MAX-ONE; \
 564   values[nvalues++] = MAX; \
 565  \
 566   rbuf = xd3_alloc_output (stream, rbuf); \
 567   dbuf = xd3_alloc_output (stream, dbuf); \
 568  \
 569   for (i = 0; i < nvalues; i += 1) \
 570     { \
 571       const uint8_t *max; \
 572       const uint8_t *inp; \
 573       TYPE val;                 \
 574  \
 575       DOT (); \
 576       rbuf->next = 0; \
 577  \
 578       if ((ret = xd3_emit_ ## TYPE (stream, & rbuf, values[i])) || \
 579           (ret = xd3_emit_ ## TYPE (stream, & dbuf, values[i]))) \
 580         { \
 581           goto fail; \
 582         } \
 583  \
 584       inp = rbuf->base; \
 585       max = rbuf->base + rbuf->next; \
 586  \
 587       if (rbuf->next != xd3_sizeof_ ## TYPE (values[i])) \
 588         { \
 589           ret = XD3_INTERNAL; \
 590           goto fail; \
 591         } \
 592  \
 593       if ((ret = xd3_read_ ## TYPE (stream, & inp, max, & val))) \
 594         { \
 595           goto fail; \
 596         } \
 597  \
 598       if (val != values[i]) \
 599         { \
 600           ret = XD3_INTERNAL; \
 601           goto fail; \
 602         } \
 603  \
 604       DOT (); \
 605     } \
 606  \
 607   stream->next_in  = dbuf->base; \
 608   stream->avail_in = dbuf->next; \
 609  \
 610   for (i = 0; i < nvalues; i += 1) \
 611     { \
 612       TYPE val; \
 613  \
 614       if ((ret = xd3_decode_ ## TYPE (stream, & val))) \
 615         { \
 616           goto fail; \
 617         } \
 618  \
 619       if (val != values[i]) \
 620         { \
 621           ret = XD3_INTERNAL; \
 622           goto fail; \
 623         } \
 624     } \
 625  \
 626   if (stream->avail_in != 0) \
 627     { \
 628       ret = XD3_INTERNAL; \
 629       goto fail; \
 630     } \
 631  \
 632  fail: \
 633   xd3_free_output (stream, rbuf); \
 634   xd3_free_output (stream, dbuf); \
 635  \
 636   return ret
 637
 638 static int
 639 test_encode_decode_uint32_t (xd3_stream *stream, int unused)
 640 {
 641   TEST_ENCODE_DECODE_INTEGER(uint32_t,1U,UINT32_MAX);
 642 }
 643
 644 static int
 645 test_encode_decode_uint64_t (xd3_stream *stream, int unused)
 646 {
 647   TEST_ENCODE_DECODE_INTEGER(uint64_t,1ULL,UINT64_MAX);
 648 }
 649
 650 static int
 651 test_usize_t_overflow (xd3_stream *stream, int unused)
 652 {
 653   if (USIZE_T_OVERFLOW (USIZE_T_MAX, 0)) { goto fail; }
 654   if (USIZE_T_OVERFLOW (0, USIZE_T_MAX)) { goto fail; }
 655   if (USIZE_T_OVERFLOW (USIZE_T_MAX / 2, USIZE_T_MAX / 2)) { goto fail; }
 656   if (USIZE_T_OVERFLOW (USIZE_T_MAX / 2, USIZE_T_MAX / 2 + 1)) { goto fail; }
 657
 658   if (! USIZE_T_OVERFLOW (USIZE_T_MAX, 1)) { goto fail; }
 659   if (! USIZE_T_OVERFLOW (1, USIZE_T_MAX)) { goto fail; }
 660   if (! USIZE_T_OVERFLOW (USIZE_T_MAX / 2 + 1, USIZE_T_MAX / 2 + 1)) { goto fail; }
 661
 662   return 0;
 663
 664  fail:
 665   stream->msg = "incorrect overflow computation";
 666   return XD3_INTERNAL;
 667 }
 668
 669 static int
 670 test_forward_match (xd3_stream *stream, int unused)
 671 {
 672   usize_t i;
 673   uint8_t buf1[256], buf2[256];
 674
 675   memset(buf1, 0, 256);
 676   memset(buf2, 0, 256);
 677
 678   for (i = 0; i < 256; i++)
 679     {
 680       CHECK(xd3_forward_match(buf1, buf2, i) == (int)i);
 681     }
 682
 683   for (i = 0; i < 255; i++)
 684     {
 685       buf2[i] = 1;
 686       CHECK(xd3_forward_match(buf1, buf2, 256) == (int)i);
 687       buf2[i] = 0;
 688     }
 689
 690   return 0;
 691 }
 692
 693 /***********************************************************************
 694  Address cache
 695  ***********************************************************************/
 696
 697 static int
 698 test_address_cache (xd3_stream *stream, int unused)
 699 {
 700   int ret;
 701   usize_t i;
 702   usize_t offset;
 703   usize_t *addrs;
 704   uint8_t *big_buf, *buf_max;
 705   const uint8_t *buf;
 706   xd3_output *outp;
 707   uint8_t *modes;
 708   int mode_counts[16];
 709
 710   stream->acache.s_near = stream->code_table_desc->near_modes;
 711   stream->acache.s_same = stream->code_table_desc->same_modes;
 712
 713   if ((ret = xd3_encode_init_partial (stream))) { return ret; }
 714
 715   addrs = (usize_t*) xd3_alloc (stream, sizeof (usize_t), ADDR_CACHE_ROUNDS);
 716   modes = (uint8_t*) xd3_alloc (stream, sizeof (uint8_t), ADDR_CACHE_ROUNDS);
 717
 718   memset (mode_counts, 0, sizeof (mode_counts));
 719   memset (modes, 0, ADDR_CACHE_ROUNDS);
 720
 721   addrs[0] = 0;
 722
 723   mt_init (& static_mtrand, 0x9f73f7fc);
 724
 725   /* First pass: encode addresses */
 726   xd3_init_cache (& stream->acache);
 727
 728   for (offset = 1; offset < ADDR_CACHE_ROUNDS; offset += 1)
 729     {
 730       double p;
 731       usize_t addr;
 732       usize_t prev_i;
 733       usize_t nearby;
 734
 735       p         = (mt_random (&static_mtrand) / (double)USIZE_T_MAX);
 736       prev_i    = mt_random (&static_mtrand) % offset;
 737       nearby    = (mt_random (&static_mtrand) % 256) % offset;
 738       nearby    = max (1U, nearby);
 739
 740       if (p < 0.1)      { addr = addrs[offset-nearby]; }
 741       else if (p < 0.4) { addr = min (addrs[prev_i] + nearby, offset-1); }
 742       else              { addr = prev_i; }
 743
 744       if ((ret = xd3_encode_address (stream, addr, offset, & modes[offset]))) { return ret; }
 745
 746       addrs[offset] = addr;
 747       mode_counts[modes[offset]] += 1;
 748     }
 749
 750   /* Copy addresses into a contiguous buffer. */
 751   big_buf = (uint8_t*) xd3_alloc (stream, xd3_sizeof_output (ADDR_HEAD (stream)), 1);
 752
 753   for (offset = 0, outp = ADDR_HEAD (stream); outp != NULL; offset += outp->next, outp = outp->next_page)
 754     {
 755       memcpy (big_buf + offset, outp->base, outp->next);
 756     }
 757
 758   buf_max = big_buf + offset;
 759   buf     = big_buf;
 760
 761   /* Second pass: decode addresses */
 762   xd3_init_cache (& stream->acache);
 763
 764   for (offset = 1; offset < ADDR_CACHE_ROUNDS; offset += 1)
 765     {
 766       uint32_t addr;
 767
 768       if ((ret = xd3_decode_address (stream, offset, modes[offset], & buf, buf_max, & addr))) { return ret; }
 769
 770       if (addr != addrs[offset])
 771         {
 772           stream->msg = "incorrect decoded address";
 773           return XD3_INTERNAL;
 774         }
 775     }
 776
 777   /* Check that every byte, mode was used. */
 778   if (buf != buf_max)
 779     {
 780       stream->msg = "address bytes not used";
 781       return XD3_INTERNAL;
 782     }
 783
 784   for (i = 0; i < (2 + stream->acache.s_same + stream->acache.s_near); i += 1)
 785     {
 786       if (mode_counts[i] == 0)
 787         {
 788           stream->msg = "address mode not used";
 789           return XD3_INTERNAL;
 790         }
 791     }
 792
 793   xd3_free (stream, modes);
 794   xd3_free (stream, addrs);
 795   xd3_free (stream, big_buf);
 796
 797   return 0;
 798 }
 799
 800 /***********************************************************************
 801  Encode and decode with single bit error
 802  ***********************************************************************/
 803
 804 /* It compresses from 256 to around 185 bytes.
 805  * Avoids matching addresses that are a single-bit difference.
 806  * Avoids matching address 0. */
 807 static const uint8_t test_text[] =
 808 "this is a story\n"
 809 "abouttttttttttt\n"
 810 "- his is a stor\n"
 811 "- about nothing "
 812 " all. boutique -"
 813 "his story is a -"
 814 "about           "
 815 "what happens all"
 816 " the time what -"
 817 "am I ttttttt the"
 818 " person said, so"
 819 " what, per son -"
 820 " gory story is -"
 821 " about nothing -"
 822 "tttttt to test -"
 823 "his sto nothing";
 824
 825 static const uint8_t test_apphead[] = "header test";
 826
 827 static int
 828 test_compress_text (xd3_stream  *stream,
 829                     uint8_t     *encoded,
 830                     usize_t     *encoded_size)
 831 {
 832   int ret;
 833   xd3_config cfg;
 834   int oflags = stream->flags;
 835   int flags = stream->flags | XD3_FLUSH;
 836
 837   xd3_free_stream (stream);
 838   xd3_init_config (& cfg, flags);
 839
 840   /* This configuration is fixed so that the "expected non-error" the counts in
 841    * decompress_single_bit_errors are too.  See test_coftcfg_str. */
 842   cfg.smatch_cfg = XD3_SMATCH_SOFT;
 843   cfg.smatcher_soft.name = "test";
 844   cfg.smatcher_soft.large_look = 64; /* no source, not used */
 845   cfg.smatcher_soft.large_step = 64; /* no source, not used */
 846   cfg.smatcher_soft.small_look = 4;
 847   cfg.smatcher_soft.small_chain = 128;
 848   cfg.smatcher_soft.small_lchain = 16;
 849   cfg.smatcher_soft.max_lazy = 8;
 850   cfg.smatcher_soft.long_enough = 128;
 851
 852   xd3_config_stream (stream, & cfg);
 853
 854   (*encoded_size) = 0;
 855
 856   xd3_set_appheader (stream, test_apphead,
 857                      (usize_t) strlen ((char*) test_apphead));
 858
 859   if ((ret = xd3_encode_stream (stream, test_text, sizeof (test_text),
 860                                 encoded, encoded_size, 4*sizeof (test_text)))) { goto fail; }
 861
 862   if ((ret = xd3_close_stream (stream))) { goto fail; }
 863
 864  fail:
 865   xd3_free_stream (stream);
 866   xd3_init_config (& cfg, oflags);
 867   xd3_config_stream (stream, & cfg);
 868   return ret;
 869 }
 870
 871 static int
 872 test_decompress_text (xd3_stream *stream, uint8_t *enc, usize_t enc_size, usize_t test_desize)
 873 {
 874   xd3_config cfg;
 875   char decoded[sizeof (test_text)];
 876   uint8_t *apphead;
 877   usize_t apphead_size;
 878   usize_t decoded_size;
 879   const char *msg;
 880   int  ret;
 881   usize_t pos = 0;
 882   int flags = stream->flags;
 883   usize_t take;
 884
 885  input:
 886   /* Test decoding test_desize input bytes at a time */
 887   take = min (enc_size - pos, test_desize);
 888   CHECK(take > 0);
 889
 890   xd3_avail_input (stream, enc + pos, take);
 891  again:
 892   ret = xd3_decode_input (stream);
 893
 894   pos += take;
 895   take = 0;
 896
 897   switch (ret)
 898     {
 899     case XD3_OUTPUT:
 900       break;
 901     case XD3_WINSTART:
 902     case XD3_GOTHEADER:
 903       goto again;
 904     case XD3_INPUT:
 905       if (pos < enc_size) { goto input; }
 906       /* else fallthrough */
 907     case XD3_WINFINISH:
 908     default:
 909       goto fail;
 910     }
 911
 912   CHECK(ret == XD3_OUTPUT);
 913   CHECK(pos == enc_size);
 914
 915   if (stream->avail_out != sizeof (test_text))
 916     {
 917       stream->msg = "incorrect output size";
 918       ret = XD3_INTERNAL;
 919       goto fail;
 920     }
 921
 922   decoded_size = stream->avail_out;
 923   memcpy (decoded, stream->next_out, stream->avail_out);
 924
 925   xd3_consume_output (stream);
 926
 927   if ((ret = xd3_get_appheader (stream, & apphead, & apphead_size))) { goto fail; }
 928
 929   if (apphead_size != strlen ((char*) test_apphead) ||
 930       memcmp (apphead, test_apphead, strlen ((char*) test_apphead)) != 0)
 931     {
 932       stream->msg = "incorrect appheader";
 933       ret = XD3_INTERNAL;
 934       goto fail;
 935     }
 936
 937   if ((ret = xd3_decode_input (stream)) != XD3_WINFINISH ||
 938       (ret = xd3_close_stream (stream)) != 0)
 939     {
 940       goto fail;
 941     }
 942
 943   if (decoded_size != sizeof (test_text) ||
 944       memcmp (decoded, test_text, sizeof (test_text)) != 0)
 945     {
 946       stream->msg = "incorrect output text";
 947       ret = EIO;
 948     }
 949
 950  fail:
 951   msg = stream->msg;
 952   xd3_free_stream (stream);
 953   xd3_init_config (& cfg, flags);
 954   xd3_config_stream (stream, & cfg);
 955   stream->msg = msg;
 956
 957   return ret;
 958 }
 959
 960 static int
 961 test_decompress_single_bit_error (xd3_stream *stream, int expected_non_failures)
 962 {
 963   int ret;
 964   usize_t i;
 965   uint8_t encoded[4*sizeof (test_text)]; /* make room for alt code table */
 966   usize_t  encoded_size;
 967   int non_failures = 0;
 968   int cksum = (stream->flags & XD3_ADLER32) != 0;
 969
 970 //#define DEBUG_TEST_FAILURES
 971 #ifndef DEBUG_TEST_FAILURES
 972 #define TEST_FAILURES()
 973 #else
 974   /* For checking non-failure cases by hand, enable this macro and run
 975    * xdelta printdelta with print_cpymode disabled.  Every non-failure
 976    * should change a copy address mode, which doesn't cause a failure
 977    * because the address cache starts out with all zeros.
 978
 979     ./xdelta3 test
 980     for i in test_text.xz.*; do ./xdelta3 printdelta $i > $i.out;
 981     diff $i.out test_text.xz.0.out; done
 982
 983    */
 984   system ("rm -rf test_text.*");
 985   {
 986     char buf[TESTBUFSIZE];
 987     FILE *f;
 988     snprintf_func (buf, TESTBUFSIZE, "test_text");
 989     f = fopen (buf, "w");
 990     fwrite (test_text,1,sizeof (test_text),f);
 991     fclose (f);
 992   }
 993 #define TEST_FAILURES()                                         \
 994   do {                                                          \
 995     char buf[TESTBUFSIZE];                                      \
 996     FILE *f;                                                    \
 997     snprintf_func (buf, TESTBUFSIZE, "test_text.xz.%d", non_failures);  \
 998     f = fopen (buf, "w");                                       \
 999     fwrite (encoded,1,encoded_size,f);                          \
1000     fclose (f);                                                 \
1001   } while (0)
1002 #endif
1003
1004   stream->sec_data.inefficient = 1;
1005   stream->sec_inst.inefficient = 1;
1006   stream->sec_addr.inefficient = 1;
1007
1008   /* Encode text, test correct input */
1009   if ((ret = test_compress_text (stream, encoded, & encoded_size)))
1010     {
1011       /*stream->msg = "without error: encode failure";*/
1012       return ret;
1013     }
1014
1015   if ((ret = test_decompress_text (stream, encoded, encoded_size,
1016                                    sizeof (test_text) / 4)))
1017     {
1018       /*stream->msg = "without error: decode failure";*/
1019       return ret;
1020     }
1021
1022   TEST_FAILURES();
1023
1024   for (i = 0; i < encoded_size*8; i += 1)
1025     {
1026       /* Single bit error. */
1027       encoded[i/8] ^= 1 << (i%8);
1028
1029       if ((ret = test_decompress_text (stream, encoded,
1030                                        encoded_size, sizeof (test_text))) == 0)
1031         {
1032           non_failures += 1;
1033 #ifdef DEBUG_TEST_FAILURES
1034           XPR(NT "%u[%u] non-failure %u\n", i/8, i%8, non_failures);
1035 #endif
1036           TEST_FAILURES();
1037         }
1038       else
1039         {
1040           /*XPR(NT "%u[%u] failure: %s\n", i/8, i%8, stream->msg);*/
1041         }
1042
1043       /* decompress_text returns EIO when the final memcmp() fails, but that
1044        * should never happen with checksumming on. */
1045       if (cksum && ret == EIO)
1046         {
1047           /*XPR(NT "%u[%u] cksum mismatch\n", i/8, i%8);*/
1048           stream->msg = "checksum mismatch";
1049           return XD3_INTERNAL;
1050         }
1051
1052       /* Undo single bit error. */
1053       encoded[i/8] ^= 1 << (i%8);
1054     }
1055
1056   /* Test correct input again */
1057   if ((ret = test_decompress_text (stream, encoded, encoded_size, 1)))
1058     {
1059       /*stream->msg = "without error: decode failure";*/
1060       return ret;
1061     }
1062
1063   /* Check expected non-failures */
1064   if (non_failures != expected_non_failures)
1065     {
1066       XPR(NT "non-failures %u; expected %u",
1067          non_failures, expected_non_failures);
1068       stream->msg = "incorrect";
1069       return XD3_INTERNAL;
1070     }
1071
1072   DOT ();
1073
1074   return 0;
1075 }
1076
1077 /***********************************************************************
1078  Secondary compression tests
1079  ***********************************************************************/
1080
1081 #if SECONDARY_ANY
1082 typedef int (*sec_dist_func) (xd3_stream *stream, xd3_output *data);
1083
1084 static int sec_dist_func1 (xd3_stream *stream, xd3_output *data);
1085 static int sec_dist_func2 (xd3_stream *stream, xd3_output *data);
1086 static int sec_dist_func3 (xd3_stream *stream, xd3_output *data);
1087 static int sec_dist_func4 (xd3_stream *stream, xd3_output *data);
1088 static int sec_dist_func5 (xd3_stream *stream, xd3_output *data);
1089 static int sec_dist_func6 (xd3_stream *stream, xd3_output *data);
1090 static int sec_dist_func7 (xd3_stream *stream, xd3_output *data);
1091 static int sec_dist_func8 (xd3_stream *stream, xd3_output *data);
1092 static int sec_dist_func9 (xd3_stream *stream, xd3_output *data);
1093 static int sec_dist_func10 (xd3_stream *stream, xd3_output *data);
1094 static int sec_dist_func11 (xd3_stream *stream, xd3_output *data);
1095
1096 static sec_dist_func sec_dists[] =
1097 {
1098   sec_dist_func1,
1099   sec_dist_func2,
1100   sec_dist_func3,
1101   sec_dist_func4,
1102   sec_dist_func5,
1103   sec_dist_func6,
1104   sec_dist_func7,
1105   sec_dist_func8,
1106   sec_dist_func9,
1107   sec_dist_func10,
1108   sec_dist_func11,
1109 };
1110
1111 /* Test ditsribution: 100 bytes of the same character (13). */
1112 static int
1113 sec_dist_func1 (xd3_stream *stream, xd3_output *data)
1114 {
1115   int i, ret;
1116   for (i = 0; i < 100; i += 1)
1117     {
1118       if ((ret = xd3_emit_byte (stream, & data, 13))) { return ret; }
1119     }
1120   return 0;
1121 }
1122
1123 /* Test ditsribution: uniform covering half the alphabet. */
1124 static int
1125 sec_dist_func2 (xd3_stream *stream, xd3_output *data)
1126 {
1127   int i, ret;
1128   for (i = 0; i < ALPHABET_SIZE; i += 1)
1129     {
1130       if ((ret = xd3_emit_byte (stream, & data, i%(ALPHABET_SIZE/2)))) { return ret; }
1131     }
1132   return 0;
1133 }
1134
1135 /* Test ditsribution: uniform covering the entire alphabet. */
1136 static int
1137 sec_dist_func3 (xd3_stream *stream, xd3_output *data)
1138 {
1139   int i, ret;
1140   for (i = 0; i < ALPHABET_SIZE; i += 1)
1141     {
1142       if ((ret = xd3_emit_byte (stream, & data, i%ALPHABET_SIZE))) { return ret; }
1143     }
1144   return 0;
1145 }
1146
1147 /* Test distribution: An exponential distribution covering half the alphabet */
1148 static int
1149 sec_dist_func4 (xd3_stream *stream, xd3_output *data)
1150 {
1151   int i, ret, x;
1152   for (i = 0; i < ALPHABET_SIZE*20; i += 1)
1153     {
1154       x = mt_exp_rand (10, ALPHABET_SIZE/2);
1155       if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
1156     }
1157   return 0;
1158 }
1159
1160 /* Test distribution: An exponential distribution covering the entire alphabet */
1161 static int
1162 sec_dist_func5 (xd3_stream *stream, xd3_output *data)
1163 {
1164   int i, ret, x;
1165   for (i = 0; i < ALPHABET_SIZE*20; i += 1)
1166     {
1167       x = mt_exp_rand (10, ALPHABET_SIZE-1);
1168       if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
1169     }
1170   return 0;
1171 }
1172
1173 /* Test distribution: An uniform random distribution covering half the alphabet */
1174 static int
1175 sec_dist_func6 (xd3_stream *stream, xd3_output *data)
1176 {
1177   int i, ret, x;
1178   for (i = 0; i < ALPHABET_SIZE*20; i += 1)
1179     {
1180       x = mt_random (&static_mtrand) % (ALPHABET_SIZE/2);
1181       if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
1182     }
1183   return 0;
1184 }
1185
1186 /* Test distribution: An uniform random distribution covering the entire alphabet */
1187 static int
1188 sec_dist_func7 (xd3_stream *stream, xd3_output *data)
1189 {
1190   int i, ret, x;
1191   for (i = 0; i < ALPHABET_SIZE*200; i += 1)
1192     {
1193       x = mt_random (&static_mtrand) % ALPHABET_SIZE;
1194       if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
1195     }
1196   return 0;
1197 }
1198
1199 /* Test distribution: A small number of frequent characters, difficult
1200  * to divide into many groups */
1201 static int
1202 sec_dist_func8 (xd3_stream *stream, xd3_output *data)
1203 {
1204   int i, ret;
1205   for (i = 0; i < ALPHABET_SIZE*5; i += 1)
1206     {
1207       if ((ret = xd3_emit_byte (stream, & data, 0))) { return ret; }
1208       if ((ret = xd3_emit_byte (stream, & data, 64))) { return ret; }
1209       if ((ret = xd3_emit_byte (stream, & data, 128))) { return ret; }
1210       if ((ret = xd3_emit_byte (stream, & data, 255))) { return ret; }
1211     }
1212   return 0;
1213 }
1214
1215 /* Test distribution: One that causes many FGK block promotions (found a bug) */
1216 static int
1217 sec_dist_func9 (xd3_stream *stream, xd3_output *data)
1218 {
1219   int i, ret;
1220
1221   int ramp   = 0;
1222   int rcount = 0;
1223   int prom   = 0;
1224   int pcount = 0;
1225
1226   /* 200 was long enough to trigger it--only when stricter checking
1227    * that counted all blocks was turned on, but it seems I deleted
1228    * this code. (missing fgk_free_block on line 398). */
1229   for (i = 0; i < ALPHABET_SIZE*200; i += 1)
1230     {
1231     repeat:
1232       if (ramp < ALPHABET_SIZE)
1233         {
1234           /* Initially Nth symbol has (N+1) frequency */
1235           if (rcount <= ramp)
1236             {
1237               rcount += 1;
1238               if ((ret = xd3_emit_byte (stream, & data, ramp))) { return ret; }
1239               continue;
1240             }
1241
1242           ramp   += 1;
1243           rcount  = 0;
1244           goto repeat;
1245         }
1246
1247       /* Thereafter, promote least freq to max freq */
1248       if (pcount == ALPHABET_SIZE)
1249         {
1250           pcount = 0;
1251           prom   = (prom + 1) % ALPHABET_SIZE;
1252         }
1253
1254       pcount += 1;
1255       if ((ret = xd3_emit_byte (stream, & data, prom))) { return ret; }
1256     }
1257
1258   return 0;
1259 }
1260
1261 /* Test distribution: freq[i] == i*i, creates a 21-bit code length, fixed in 3.0r. */
1262 static int
1263 sec_dist_func10 (xd3_stream *stream, xd3_output *data)
1264 {
1265   int i, j, ret;
1266   for (i = 0; i < ALPHABET_SIZE; i += 1)
1267     {
1268       for (j = 0; j <= (i*i); j += 1)
1269         {
1270           if ((ret = xd3_emit_byte (stream, & data, i))) { return ret; }
1271         }
1272     }
1273   return 0;
1274 }
1275
1276 /* Test distribution: fibonacci */
1277 static int
1278 sec_dist_func11 (xd3_stream *stream, xd3_output *data)
1279 {
1280   int sum0 = 0;
1281   int sum1 = 1;
1282   int i, j, ret;
1283   for (i = 0; i < 33; ++i)
1284     {
1285       for (j = 0; j < (sum0 + sum1); ++j)
1286         {
1287           if ((ret = xd3_emit_byte (stream, & data, i))) { return ret; }
1288         }
1289       sum0 = sum1;
1290       sum1 = j;
1291     }
1292   return 0;
1293 }
1294
1295 static int
1296 test_secondary_decode (xd3_stream         *stream,
1297                        const xd3_sec_type *sec,
1298                        usize_t              input_size,
1299                        usize_t              compress_size,
1300                        const uint8_t      *dec_input,
1301                        const uint8_t      *dec_correct,
1302                        uint8_t            *dec_output)
1303 {
1304   int ret;
1305   xd3_sec_stream *dec_stream;
1306   const uint8_t *dec_input_used, *dec_input_end;
1307   uint8_t *dec_output_used, *dec_output_end;
1308
1309   if ((dec_stream = sec->alloc (stream)) == NULL) { return ENOMEM; }
1310
1311   if ((ret = sec->init (stream, dec_stream, 0)) != 0) { goto fail; }
1312
1313   dec_input_used = dec_input;
1314   dec_input_end  = dec_input + compress_size;
1315
1316   dec_output_used = dec_output;
1317   dec_output_end  = dec_output + input_size;
1318
1319   if ((ret = sec->decode (stream, dec_stream,
1320                           & dec_input_used, dec_input_end,
1321                           & dec_output_used, dec_output_end)))
1322     {
1323       goto fail;
1324     }
1325
1326   if (dec_input_used != dec_input_end)
1327     {
1328       stream->msg = "unused input";
1329       ret = XD3_INTERNAL;
1330       goto fail;
1331     }
1332
1333   if (dec_output_used != dec_output_end)
1334     {
1335       stream->msg = "unfinished output";
1336       ret = XD3_INTERNAL;
1337       goto fail;
1338     }
1339
1340   if (memcmp (dec_output, dec_correct, input_size) != 0)
1341     {
1342       stream->msg = "incorrect output";
1343       ret = XD3_INTERNAL;
1344       goto fail;
1345     }
1346
1347  fail:
1348   sec->destroy (stream, dec_stream);
1349   return ret;
1350 }
1351
1352 static int
1353 test_secondary (xd3_stream *stream, const xd3_sec_type *sec, usize_t groups)
1354 {
1355   usize_t test_i;
1356   int ret;
1357   xd3_output *in_head, *out_head, *p;
1358   usize_t p_off, input_size, compress_size;
1359   uint8_t *dec_input = NULL, *dec_output = NULL, *dec_correct = NULL;
1360   xd3_sec_stream *enc_stream;
1361   xd3_sec_cfg cfg;
1362
1363   memset (& cfg, 0, sizeof (cfg));
1364
1365   cfg.inefficient = 1;
1366
1367   for (cfg.ngroups = 1; cfg.ngroups <= groups; cfg.ngroups += 1)
1368     {
1369       XPR(NTR "\n...");
1370       for (test_i = 0; test_i < SIZEOF_ARRAY (sec_dists); test_i += 1)
1371         {
1372           mt_init (& static_mtrand, 0x9f73f7fc);
1373
1374           in_head  = xd3_alloc_output (stream, NULL);
1375           out_head = xd3_alloc_output (stream, NULL);
1376           enc_stream = sec->alloc (stream);
1377           dec_input = NULL;
1378           dec_output = NULL;
1379           dec_correct = NULL;
1380
1381           if (in_head == NULL || out_head == NULL || enc_stream == NULL)
1382             {
1383               goto nomem;
1384             }
1385
1386           if ((ret = sec_dists[test_i] (stream, in_head))) { goto fail; }
1387
1388           if ((ret = sec->init (stream, enc_stream, 1)) != 0) { goto fail; }
1389
1390           /* Encode data */
1391           if ((ret = sec->encode (stream, enc_stream,
1392                                   in_head, out_head, & cfg)))
1393             {
1394               XPR(NT "test %u: encode: %s", test_i, stream->msg);
1395               goto fail;
1396             }
1397
1398           /* Calculate sizes, allocate contiguous arrays for decoding */
1399           input_size    = xd3_sizeof_output (in_head);
1400           compress_size = xd3_sizeof_output (out_head);
1401
1402           XPR(NTR "%.3f", 8.0 * (double) compress_size / (double) input_size);
1403
1404           if ((dec_input   = (uint8_t*) xd3_alloc (stream, compress_size, 1)) == NULL ||
1405               (dec_output  = (uint8_t*) xd3_alloc (stream, input_size, 1)) == NULL ||
1406               (dec_correct = (uint8_t*) xd3_alloc (stream, input_size, 1)) == NULL)
1407             {
1408               goto nomem;
1409             }
1410
1411           /* Fill the compressed data array */
1412           for (p_off = 0, p = out_head; p != NULL;
1413                p_off += p->next, p = p->next_page)
1414             {
1415               memcpy (dec_input + p_off, p->base, p->next);
1416             }
1417
1418           CHECK(p_off == compress_size);
1419
1420           /* Fill the input data array */
1421           for (p_off = 0, p = in_head; p != NULL;
1422                p_off += p->next, p = p->next_page)
1423             {
1424               memcpy (dec_correct + p_off, p->base, p->next);
1425             }
1426
1427           CHECK(p_off == input_size);
1428
1429           if ((ret = test_secondary_decode (stream, sec, input_size,
1430                                             compress_size, dec_input,
1431                                             dec_correct, dec_output)))
1432             {
1433               XPR(NT "test %u: decode: %s", test_i, stream->msg);
1434               goto fail;
1435             }
1436
1437           /* Single-bit error test, only cover the first 10 bytes.
1438            * Some non-failures are expected in the Huffman case:
1439            * Changing the clclen array, for example, may not harm the
1440            * decoding.  Really looking for faults here. */
1441           {
1442             int i;
1443             int bytes = min (compress_size, 10U);
1444             for (i = 0; i < bytes * 8; i += 1)
1445               {
1446                 dec_input[i/8] ^= 1 << (i%8);
1447
1448                 if ((ret = test_secondary_decode (stream, sec, input_size,
1449                                                   compress_size, dec_input,
1450                                                   dec_correct, dec_output))
1451                     == 0)
1452                   {
1453                     /*XPR(NT "test %u: decode single-bit [%u/%u]
1454                       error non-failure", test_i, i/8, i%8);*/
1455                   }
1456
1457                 dec_input[i/8] ^= 1 << (i%8);
1458
1459                 if ((i % (2*bytes)) == (2*bytes)-1)
1460                   {
1461                     DOT ();
1462                   }
1463               }
1464             ret = 0;
1465           }
1466
1467           if (0) { nomem: ret = ENOMEM; }
1468
1469         fail:
1470           sec->destroy (stream, enc_stream);
1471           xd3_free_output (stream, in_head);
1472           xd3_free_output (stream, out_head);
1473           xd3_free (stream, dec_input);
1474           xd3_free (stream, dec_output);
1475           xd3_free (stream, dec_correct);
1476
1477           if (ret != 0) { return ret; }
1478         }
1479     }
1480
1481   return 0;
1482 }
1483
1484 IF_FGK (static int test_secondary_fgk  (xd3_stream *stream, usize_t gp)
1485         { return test_secondary (stream, & fgk_sec_type, gp); })
1486 IF_DJW (static int test_secondary_huff (xd3_stream *stream, usize_t gp)
1487         { return test_secondary (stream, & djw_sec_type, gp); })
1488 IF_LZMA (static int test_secondary_lzma (xd3_stream *stream, usize_t gp)
1489         { return test_secondary (stream, & lzma_sec_type, gp); })
1490 #endif
1491
1492 /***********************************************************************
1493  TEST INSTRUCTION TABLE
1494  ***********************************************************************/
1495
1496 /* Test that xd3_choose_instruction() does the right thing for its code
1497  * table. */
1498 static int
1499 test_choose_instruction (xd3_stream *stream, int ignore)
1500 {
1501   int i;
1502
1503   stream->code_table = (*stream->code_table_func) ();
1504
1505   for (i = 0; i < 256; i += 1)
1506     {
1507       const xd3_dinst *d = stream->code_table + i;
1508       xd3_rinst prev, inst;
1509
1510       CHECK(d->type1 > 0);
1511
1512       memset (& prev, 0, sizeof (prev));
1513       memset (& inst, 0, sizeof (inst));
1514
1515       if (d->type2 == 0)
1516         {
1517           inst.type = d->type1;
1518
1519           if ((inst.size = d->size1) == 0)
1520             {
1521               inst.size = TESTBUFSIZE;
1522             }
1523
1524           XD3_CHOOSE_INSTRUCTION (stream, NULL, & inst);
1525
1526           if (inst.code2 != 0 || inst.code1 != i)
1527             {
1528               stream->msg = "wrong single instruction";
1529               return XD3_INTERNAL;
1530             }
1531         }
1532       else
1533         {
1534           prev.type = d->type1;
1535           prev.size = d->size1;
1536           inst.type = d->type2;
1537           inst.size = d->size2;
1538
1539           XD3_CHOOSE_INSTRUCTION (stream, & prev, & inst);
1540
1541           if (prev.code2 != i)
1542             {
1543               stream->msg = "wrong double instruction";
1544               return XD3_INTERNAL;
1545             }
1546         }
1547     }
1548
1549   return 0;
1550 }
1551
1552 /***********************************************************************
1553  64BIT STREAMING
1554  ***********************************************************************/
1555
1556 /* This test encodes and decodes a series of 1 megabyte windows, each
1557  * containing a long run of zeros along with a single xoff_t size
1558  * record to indicate the sequence. */
1559 static int
1560 test_streaming (xd3_stream *in_stream, uint8_t *encbuf, uint8_t *decbuf, uint8_t *delbuf, usize_t megs)
1561 {
1562   xd3_stream estream, dstream;
1563   int ret;
1564   usize_t i, delsize, decsize;
1565   xd3_config cfg;
1566   xd3_init_config (& cfg, in_stream->flags);
1567   cfg.flags |= XD3_COMPLEVEL_6;
1568
1569   if ((ret = xd3_config_stream (& estream, & cfg)) ||
1570       (ret = xd3_config_stream (& dstream, & cfg)))
1571     {
1572       goto fail;
1573     }
1574
1575   for (i = 0; i < megs; i += 1)
1576     {
1577       ((usize_t*) encbuf)[0] = i;
1578
1579       if ((i % 200) == 199) { DOT (); }
1580
1581       if ((ret = xd3_process_stream (1, & estream, xd3_encode_input, 0,
1582                                      encbuf, 1 << 20,
1583                                      delbuf, & delsize, 1 << 20)))
1584         {
1585           in_stream->msg = estream.msg;
1586           goto fail;
1587         }
1588
1589       if ((ret = xd3_process_stream (0, & dstream, xd3_decode_input, 0,
1590                                      delbuf, delsize,
1591                                      decbuf, & decsize, 1 << 20)))
1592         {
1593           in_stream->msg = dstream.msg;
1594           goto fail;
1595         }
1596
1597       if (decsize != 1 << 20 ||
1598           memcmp (encbuf, decbuf, 1 << 20) != 0)
1599         {
1600           in_stream->msg = "wrong result";
1601           ret = XD3_INTERNAL;
1602           goto fail;
1603         }
1604     }
1605
1606   if ((ret = xd3_close_stream (& estream)) ||
1607       (ret = xd3_close_stream (& dstream)))
1608     {
1609       goto fail;
1610     }
1611
1612  fail:
1613   xd3_free_stream (& estream);
1614   xd3_free_stream (& dstream);
1615   return ret;
1616 }
1617
1618 /* Run tests of data streaming of over and around 4GB of data. */
1619 static int
1620 test_compressed_stream_overflow (xd3_stream *stream, int ignore)
1621 {
1622   int ret;
1623   int i;
1624   uint8_t *buf;
1625
1626   if ((buf = (uint8_t*) malloc (TWO_MEGS_AND_DELTA)) == NULL) { return ENOMEM; }
1627
1628   memset (buf, 0, TWO_MEGS_AND_DELTA);
1629   for (i = 0; i < (2 << 20); i += 256)
1630     {
1631       int j;
1632       int off = mt_random(& static_mtrand) % 10;
1633       for (j = 0; j < 256; j++)
1634         {
1635           buf[i + j] = j + off;
1636         }
1637     }
1638
1639   /* Test overflow of a 32-bit file offset. */
1640   if (SIZEOF_XOFF_T == 4)
1641     {
1642       ret = test_streaming (stream, buf, buf + (1 << 20), buf + (2 << 20), (1 << 12) + 1);
1643
1644       if (ret == XD3_INVALID_INPUT && MSG_IS ("decoder file offset overflow"))
1645         {
1646           ret = 0;
1647         }
1648       else
1649         {
1650           XPR(NT XD3_LIB_ERRMSG (stream, ret));
1651           stream->msg = "expected overflow condition";
1652           ret = XD3_INTERNAL;
1653           goto fail;
1654         }
1655     }
1656
1657   /* Test transfer of exactly 32bits worth of data. */
1658   if ((ret = test_streaming (stream,
1659                              buf,
1660                              buf + (1 << 20),
1661                              buf + (2 << 20),
1662                              1 << 12)))
1663     {
1664       goto fail;
1665     }
1666  fail:
1667   free (buf);
1668   return ret;
1669 }
1670
1671 /***********************************************************************
1672  COMMAND LINE
1673  ***********************************************************************/
1674
1675 #if SHELL_TESTS
1676
1677 /* For each pair of command templates in the array below, test that
1678  * encoding and decoding commands work.  Also check for the expected
1679  * size delta, which should be approximately TEST_ADD_RATIO times the
1680  * file size created by test_make_inputs.  Due to differences in the
1681  * application header, it is suppressed (-A) so that all delta files
1682  * are the same. */
1683 static int
1684 test_command_line_arguments (xd3_stream *stream, int ignore)
1685 {
1686   int i, ret;
1687
1688   static const char* cmdpairs[] =
1689   {
1690     /* standard input, output */
1691     "%s %s -A < %s > %s", "%s -d < %s > %s",
1692     "%s %s -A -e < %s > %s", "%s -d < %s > %s",
1693     "%s %s -A= encode < %s > %s", "%s decode < %s > %s",
1694     "%s %s -A -q encode < %s > %s", "%s -qdq < %s > %s",
1695
1696     /* file input, standard output */
1697     "%s %s -A= %s > %s", "%s -d %s > %s",
1698     "%s %s -A -e %s > %s", "%s -d %s > %s",
1699     "%s %s encode -A= %s > %s", "%s decode %s > %s",
1700
1701     /* file input, output */
1702     "%s %s -A= %s %s", "%s -d %s %s",
1703     "%s %s -A -e %s %s", "%s -d %s %s",
1704     "%s %s -A= encode %s %s", "%s decode %s %s",
1705
1706     /* option placement */
1707     "%s %s -A -f %s %s", "%s -f -d %s %s",
1708     "%s %s -e -A= %s %s", "%s -d -f %s %s",
1709     "%s %s -f encode -A= %s %s", "%s -f decode -f %s %s",
1710   };
1711
1712   char ecmd[TESTBUFSIZE], dcmd[TESTBUFSIZE];
1713   int pairs = SIZEOF_ARRAY (cmdpairs) / 2;
1714   xoff_t tsize;
1715   xoff_t dsize;
1716   double ratio;
1717
1718   mt_init (& static_mtrand, 0x9f73f7fc);
1719
1720   for (i = 0; i < pairs; i += 1)
1721     {
1722       test_setup ();
1723       if ((ret = test_make_inputs (stream, NULL, & tsize))) { return ret; }
1724
1725       snprintf_func (ecmd, TESTBUFSIZE, cmdpairs[2*i], program_name,
1726                test_softcfg_str, TEST_TARGET_FILE, TEST_DELTA_FILE);
1727       snprintf_func (dcmd, TESTBUFSIZE, cmdpairs[2*i+1], program_name,
1728                TEST_DELTA_FILE, TEST_RECON_FILE);
1729
1730       /* Encode and decode. */
1731       if ((ret = system (ecmd)) != 0)
1732         {
1733           XPR(NT "encode command: %s\n", ecmd);
1734           stream->msg = "encode cmd failed";
1735           return XD3_INTERNAL;
1736         }
1737
1738       if ((ret = system (dcmd)) != 0)
1739         {
1740           XPR(NT "decode command: %s\n", dcmd);
1741           stream->msg = "decode cmd failed";
1742           return XD3_INTERNAL;
1743         }
1744
1745       /* Compare the target file. */
1746       if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_RECON_FILE)))
1747         {
1748           return ret;
1749         }
1750
1751       if ((ret = test_file_size (TEST_DELTA_FILE, & dsize)))
1752         {
1753           return ret;
1754         }
1755
1756       ratio = (double) dsize / (double) tsize;
1757
1758       /* Check that it is not too small, not too large. */
1759       if (ratio >= TEST_ADD_RATIO + TEST_EPSILON)
1760         {
1761           XPR(NT "test encode with size ratio %.4f, "
1762              "expected < %.4f (%"Q"u, %"Q"u)\n",
1763             ratio, TEST_ADD_RATIO + TEST_EPSILON, dsize, tsize);
1764           stream->msg = "strange encoding";
1765           return XD3_INTERNAL;
1766         }
1767
1768       if (ratio <= TEST_ADD_RATIO * (1.0 - 2 * TEST_EPSILON))
1769         {
1770           XPR(NT "test encode with size ratio %.4f, "
1771              "expected > %.4f\n",
1772             ratio, TEST_ADD_RATIO - TEST_EPSILON);
1773           stream->msg = "strange encoding";
1774           return XD3_INTERNAL;
1775         }
1776
1777       /* Also check that test_compare_files works.  The delta and original should
1778        * not be identical. */
1779       if ((ret = test_compare_files (TEST_DELTA_FILE,
1780                                 TEST_TARGET_FILE)) == 0)
1781         {
1782           stream->msg = "broken test_compare_files";
1783           return XD3_INTERNAL;
1784         }
1785
1786       test_cleanup ();
1787       DOT ();
1788     }
1789
1790   return 0;
1791 }
1792
1793 static int
1794 check_vcdiff_header (xd3_stream *stream,
1795                      const char *input,
1796                      const char *line_start,
1797                      const char *matches,
1798                      int yes_or_no)
1799 {
1800   int ret;
1801   char vcmd[TESTBUFSIZE], gcmd[TESTBUFSIZE];
1802
1803   snprintf_func (vcmd, TESTBUFSIZE, "%s printhdr -f %s %s",
1804             program_name, input, TEST_RECON2_FILE);
1805
1806   if ((ret = system (vcmd)) != 0)
1807     {
1808       XPR(NT "printhdr command: %s\n", vcmd);
1809       stream->msg = "printhdr cmd failed";
1810       return XD3_INTERNAL;
1811     }
1812
1813   snprintf_func (gcmd, TESTBUFSIZE, "grep \"%s.*%s.*\" %s > /dev/null",
1814             line_start, matches, TEST_RECON2_FILE);
1815
1816   if (yes_or_no)
1817     {
1818       if ((ret = do_cmd (stream, gcmd)))
1819         {
1820           XPR(NT "%s\n", gcmd);
1821           return ret;
1822         }
1823     }
1824   else
1825     {
1826       if ((ret = do_fail (stream, gcmd)))
1827         {
1828           XPR(NT "%s\n", gcmd);
1829           return ret;
1830         }
1831     }
1832
1833   return 0;
1834 }
1835
1836 static int
1837 test_recode_command2 (xd3_stream *stream, int has_source,
1838                       int variant, int change)
1839 {
1840   int has_adler32 = (variant & 0x1) != 0;
1841   int has_apphead = (variant & 0x2) != 0;
1842   int has_secondary = (variant & 0x4) != 0;
1843
1844   int change_adler32 = (change & 0x1) != 0;
1845   int change_apphead = (change & 0x2) != 0;
1846   int change_secondary = (change & 0x4) != 0;
1847
1848   int recoded_adler32 = change_adler32 ? !has_adler32 : has_adler32;
1849   int recoded_apphead = change_apphead ? !has_apphead : has_apphead;
1850   int recoded_secondary = change_secondary ? !has_secondary : has_secondary;
1851
1852   char ecmd[TESTBUFSIZE], recmd[TESTBUFSIZE], dcmd[TESTBUFSIZE];
1853   xoff_t tsize, ssize;
1854   int ret;
1855
1856   test_setup ();
1857
1858   if ((ret = test_make_inputs (stream, has_source ? & ssize : NULL, & tsize)))
1859     {
1860       return ret;
1861     }
1862
1863   /* First encode */
1864   snprintf_func (ecmd, TESTBUFSIZE, "%s %s -f %s %s %s %s %s %s %s",
1865             program_name, test_softcfg_str,
1866             has_adler32 ? "" : "-n ",
1867             has_apphead ? "-A=encode_apphead " : "-A= ",
1868             has_secondary ? "-S djw " : "-S none ",
1869             has_source ? "-s " : "",
1870             has_source ? TEST_SOURCE_FILE : "",
1871             TEST_TARGET_FILE,
1872             TEST_DELTA_FILE);
1873
1874   if ((ret = system (ecmd)) != 0)
1875     {
1876       XPR(NT "encode command: %s\n", ecmd);
1877       stream->msg = "encode cmd failed";
1878       return XD3_INTERNAL;
1879     }
1880
1881   /* Now recode */
1882   snprintf_func (recmd, TESTBUFSIZE,
1883             "%s recode %s -f %s %s %s %s %s", program_name, test_softcfg_str,
1884             recoded_adler32 ? "" : "-n ",
1885             !change_apphead ? "" :
1886                 (recoded_apphead ? "-A=recode_apphead " : "-A= "),
1887             recoded_secondary ? "-S djw " : "-S none ",
1888             TEST_DELTA_FILE,
1889             TEST_COPY_FILE);
1890
1891   if ((ret = system (recmd)) != 0)
1892     {
1893       XPR(NT "recode command: %s\n", recmd);
1894       stream->msg = "recode cmd failed";
1895       return XD3_INTERNAL;
1896     }
1897
1898   /* Check recode changes. */
1899
1900   if ((ret = check_vcdiff_header (stream,
1901                                   TEST_COPY_FILE,
1902                                   "VCDIFF window indicator",
1903                                   "VCD_SOURCE",
1904                                   has_source))) { return ret; }
1905
1906   if ((ret = check_vcdiff_header (stream,
1907                                   TEST_COPY_FILE,
1908                                   "VCDIFF header indicator",
1909                                   "VCD_SECONDARY",
1910                                   recoded_secondary))) { return ret; }
1911
1912   if ((ret = check_vcdiff_header (stream,
1913                                   TEST_COPY_FILE,
1914                                   "VCDIFF window indicator",
1915                                   "VCD_ADLER32",
1916                                   /* Recode can't generate an adler32
1917                                    * checksum, it can only preserve it or
1918                                    * remove it. */
1919                                   has_adler32 && recoded_adler32)))
1920     {
1921       return ret;
1922     }
1923
1924   if (!change_apphead)
1925     {
1926       if ((ret = check_vcdiff_header (stream,
1927                                       TEST_COPY_FILE,
1928                                       "VCDIFF header indicator",
1929                                       "VCD_APPHEADER",
1930                                       has_apphead)))
1931         {
1932           return ret;
1933         }
1934       if ((ret = check_vcdiff_header (stream,
1935                                       TEST_COPY_FILE,
1936                                       "VCDIFF application header",
1937                                       "encode_apphead",
1938                                       has_apphead)))
1939         {
1940           return ret;
1941         }
1942     }
1943   else
1944     {
1945       if ((ret = check_vcdiff_header (stream,
1946                                       TEST_COPY_FILE,
1947                                       "VCDIFF header indicator",
1948                                       "VCD_APPHEADER",
1949                                       recoded_apphead)))
1950         {
1951           return ret;
1952         }
1953       if (recoded_apphead &&
1954           (ret = check_vcdiff_header (stream,
1955                                       TEST_COPY_FILE,
1956                                       "VCDIFF application header",
1957                                       "recode_apphead",
1958                                       1)))
1959         {
1960           return ret;
1961         }
1962     }
1963
1964   /* Now decode */
1965   snprintf_func (dcmd, TESTBUFSIZE, "%s -fd %s %s %s %s ", program_name,
1966             has_source ? "-s " : "",
1967             has_source ? TEST_SOURCE_FILE : "",
1968             TEST_COPY_FILE,
1969             TEST_RECON_FILE);
1970
1971   if ((ret = system (dcmd)) != 0)
1972     {
1973       XPR(NT "decode command: %s\n", dcmd);
1974       stream->msg = "decode cmd failed";
1975       return XD3_INTERNAL;
1976     }
1977
1978   /* Now compare. */
1979   if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_RECON_FILE)))
1980     {
1981       return ret;
1982     }
1983
1984   return 0;
1985 }
1986
1987 static int
1988 test_recode_command (xd3_stream *stream, int ignore)
1989 {
1990   /* Things to test:
1991    * - with and without a source file (recode does not change)
1992    *
1993    * (recode may or may not change -- 8 variations)
1994    * - with and without adler32
1995    * - with and without app header
1996    * - with and without secondary
1997    */
1998   int has_source;
1999   int variant;
2000   int change;
2001   int ret;
2002
2003   for (has_source = 0; has_source < 2; has_source++)
2004     {
2005       for (variant = 0; variant < 8; variant++)
2006         {
2007           for (change = 0; change < 8; change++)
2008             {
2009               if ((ret = test_recode_command2 (stream, has_source,
2010                                                variant, change)))
2011                 {
2012                   return ret;
2013                 }
2014             }
2015           DOT ();
2016         }
2017     }
2018
2019   return 0;
2020 }
2021 #endif
2022
2023 /***********************************************************************
2024  EXTERNAL I/O DECOMPRESSION/RECOMPRESSION
2025  ***********************************************************************/
2026
2027 #if EXTERNAL_COMPRESSION
2028 /* This performs one step of the test_externally_compressed_io
2029  * function described below.  It builds a pipe containing both Xdelta
2030  * and external compression/decompression that should not modify the
2031  * data passing through. */
2032 static int
2033 test_compressed_pipe (xd3_stream *stream, main_extcomp *ext, char* buf,
2034                       const char* comp_options, const char* decomp_options,
2035                       int do_ext_recomp, const char* msg)
2036 {
2037   int ret;
2038   char decomp_buf[TESTBUFSIZE];
2039
2040   if (do_ext_recomp)
2041     {
2042       snprintf_func (decomp_buf, TESTBUFSIZE,
2043                 " | %s %s", ext->decomp_cmdname, ext->decomp_options);
2044     }
2045   else
2046     {
2047       decomp_buf[0] = 0;
2048     }
2049
2050   snprintf_func (buf, TESTBUFSIZE, "%s %s < %s | %s %s | %s %s%s > %s",
2051            ext->recomp_cmdname, ext->recomp_options,
2052            TEST_TARGET_FILE,
2053            program_name, comp_options,
2054            program_name, decomp_options,
2055            decomp_buf,
2056            TEST_RECON_FILE);
2057
2058   if ((ret = system (buf)) != 0)
2059     {
2060       stream->msg = msg;
2061       return XD3_INTERNAL;
2062     }
2063
2064   if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_RECON_FILE)))
2065     {
2066       return XD3_INTERNAL;
2067     }
2068
2069   DOT ();
2070   return 0;
2071 }
2072
2073 /* We want to test that a pipe such as:
2074  *
2075  * --> | gzip -cf | xdelta3 -cf | xdelta3 -dcf | gzip -dcf | -->
2076  *
2077  * is transparent, i.e., does not modify the stream of data.  However,
2078  * we also want to verify that at the center the data is properly
2079  * compressed, i.e., that we do not just have a re-compressed gzip
2080  * format, that we have an VCDIFF format.  We do this in two steps.
2081  * First test the above pipe, then test with suppressed output
2082  * recompression (-D).  The result should be the original input:
2083  *
2084  * --> | gzip -cf | xdelta3 -cf | xdelta3 -Ddcf | -->
2085  *
2086  * Finally we want to test that -D also disables input decompression:
2087  *
2088  * --> | gzip -cf | xdelta3 -Dcf | xdelta3 -Ddcf | gzip -dcf | -->
2089  */
2090 static int
2091 test_externally_compressed_io (xd3_stream *stream, int ignore)
2092 {
2093   usize_t i;
2094   int ret;
2095   char buf[TESTBUFSIZE];
2096
2097   mt_init (& static_mtrand, 0x9f73f7fc);
2098
2099   if ((ret = test_make_inputs (stream, NULL, NULL))) { return ret; }
2100
2101   for (i = 0; i < SIZEOF_ARRAY (extcomp_types); i += 1)
2102     {
2103       main_extcomp *ext = & extcomp_types[i];
2104
2105       /* Test for the existence of the external command first, if not skip. */
2106       snprintf_func (buf, TESTBUFSIZE, "%s %s < /dev/null > /dev/null", ext->recomp_cmdname, ext->recomp_options);
2107
2108       if ((ret = system (buf)) != 0)
2109         {
2110           XPR(NT "%s=0", ext->recomp_cmdname);
2111           continue;
2112         }
2113
2114       if ((ret = test_compressed_pipe (stream, ext, buf, "-cfq", "-dcfq", 1,
2115                                        "compression failed: identity pipe")) ||
2116           (ret = test_compressed_pipe (stream, ext, buf, "-cfq", "-Rdcfq", 0,
2117                                        "compression failed: without recompression")) ||
2118           (ret = test_compressed_pipe (stream, ext, buf, "-Dcfq", "-Rdcfq", 1,
2119                                        "compression failed: without decompression")))
2120         {
2121           return ret;
2122         }
2123     }
2124
2125   return 0;
2126 }
2127
2128 /* This tests the proper functioning of external decompression for
2129  * source files.  The source and target files are identical and
2130  * compressed by gzip.  Decoding such a delta with recompression
2131  * disbaled (-R) should produce the original, uncompressed
2132  * source/target file.  Then it checks with output recompression
2133  * enabled--in this case the output should be a compressed copy of the
2134  * original source/target file.  Then it checks that encoding with
2135  * decompression disabled works--the compressed files are identical
2136  * and decoding them should always produce a compressed output,
2137  * regardless of -R since the encoded delta file had decompression
2138  * disabled..
2139  */
2140 static int
2141 test_source_decompression (xd3_stream *stream, int ignore)
2142 {
2143   int ret;
2144   char buf[TESTBUFSIZE];
2145   const main_extcomp *ext;
2146   xoff_t dsize;
2147
2148   mt_init (& static_mtrand, 0x9f73f7fc);
2149
2150   test_setup ();
2151   if ((ret = test_make_inputs (stream, NULL, NULL))) { return ret; }
2152
2153   /* Use gzip. */
2154   if ((ext = main_get_compressor ("G")) == NULL)
2155     {
2156       XPR(NT "skipped");
2157       return 0;
2158     }
2159
2160   /* Save an uncompressed copy. */
2161   if ((ret = test_save_copy (TEST_TARGET_FILE))) { return ret; }
2162
2163   /* Compress the source. */
2164   snprintf_func (buf, TESTBUFSIZE, "%s -1 %s < %s > %s", ext->recomp_cmdname,
2165            ext->recomp_options, TEST_COPY_FILE, TEST_SOURCE_FILE);
2166   if ((ret = do_cmd (stream, buf))) { return ret; }
2167   /* Compress the target. */
2168   snprintf_func (buf, TESTBUFSIZE, "%s -9 %s < %s > %s", ext->recomp_cmdname,
2169            ext->recomp_options, TEST_COPY_FILE, TEST_TARGET_FILE);
2170   if ((ret = do_cmd (stream, buf))) { return ret; }
2171
2172   /* Now the two identical files are compressed.  Delta-encode the target,
2173    * with decompression. */
2174   snprintf_func (buf, TESTBUFSIZE, "%s -e -vfq -s%s %s %s", program_name, TEST_SOURCE_FILE,
2175            TEST_TARGET_FILE, TEST_DELTA_FILE);
2176   if ((ret = do_cmd (stream, buf))) { return ret; }
2177
2178   /* Check that the compressed file is small (b/c inputs are
2179    * identical). */
2180   if ((ret = test_file_size (TEST_DELTA_FILE, & dsize))) { return ret; }
2181   /* Deltas for identical files should be very small. */
2182   if (dsize > 200)
2183     {
2184       XPR(NT "external compression did not happen\n");
2185       stream->msg = "external compression did not happen";
2186       return XD3_INTERNAL;
2187     }
2188
2189   /* Decode the delta file with recompression disabled, should get an
2190    * uncompressed file out. */
2191   snprintf_func (buf, TESTBUFSIZE, "%s -v -dq -R -s%s %s %s", program_name,
2192            TEST_SOURCE_FILE, TEST_DELTA_FILE, TEST_RECON_FILE);
2193   if ((ret = do_cmd (stream, buf))) { return ret; }
2194   if ((ret = test_compare_files (TEST_COPY_FILE,
2195                             TEST_RECON_FILE))) { return ret; }
2196
2197   /* Decode the delta file with recompression, should get a compressed file
2198    * out.  But we can't compare compressed files directly. */
2199   snprintf_func (buf, TESTBUFSIZE, "%s -v -dqf -s%s %s %s", program_name,
2200            TEST_SOURCE_FILE, TEST_DELTA_FILE, TEST_RECON_FILE);
2201   if ((ret = do_cmd (stream, buf))) { return ret; }
2202   snprintf_func (buf, TESTBUFSIZE, "%s %s < %s > %s", ext->decomp_cmdname, ext->decomp_options,
2203            TEST_RECON_FILE, TEST_RECON2_FILE);
2204   if ((ret = do_cmd (stream, buf))) { return ret; }
2205   if ((ret = test_compare_files (TEST_COPY_FILE,
2206                             TEST_RECON2_FILE))) { return ret; }
2207
2208   /* Encode with decompression disabled */
2209   snprintf_func (buf, TESTBUFSIZE, "%s -e -D -vfq -s%s %s %s", program_name,
2210            TEST_SOURCE_FILE, TEST_TARGET_FILE, TEST_DELTA_FILE);
2211   if ((ret = do_cmd (stream, buf))) { return ret; }
2212
2213   /* Decode the delta file with decompression disabled, should get the
2214    * identical compressed file out. */
2215   snprintf_func (buf, TESTBUFSIZE, "%s -d -D -vfq -s%s %s %s", program_name,
2216            TEST_SOURCE_FILE, TEST_DELTA_FILE, TEST_RECON_FILE);
2217   if ((ret = do_cmd (stream, buf))) { return ret; }
2218   if ((ret = test_compare_files (TEST_TARGET_FILE,
2219                             TEST_RECON_FILE))) { return ret; }
2220
2221   test_cleanup();
2222   return 0;
2223 }
2224 #endif
2225
2226 /***********************************************************************
2227  FORCE, STDOUT
2228  ***********************************************************************/
2229
2230 /* This tests that output will not overwrite an existing file unless
2231  * -f was specified.  The test is for encoding (the same code handles
2232  * it for decoding). */
2233 static int
2234 test_force_behavior (xd3_stream *stream, int ignore)
2235 {
2236   int ret;
2237   char buf[TESTBUFSIZE];
2238
2239   /* Create empty target file */
2240   test_setup ();
2241   snprintf_func (buf, TESTBUFSIZE, "cp /dev/null %s", TEST_TARGET_FILE);
2242   if ((ret = do_cmd (stream, buf))) { return ret; }
2243
2244   /* Encode to delta file */
2245   snprintf_func (buf, TESTBUFSIZE, "%s -e %s %s", program_name,
2246            TEST_TARGET_FILE, TEST_DELTA_FILE);
2247   if ((ret = do_cmd (stream, buf))) { return ret; }
2248
2249   /* Encode again, should fail. */
2250   snprintf_func (buf, TESTBUFSIZE, "%s -q -e %s %s ", program_name,
2251            TEST_TARGET_FILE, TEST_DELTA_FILE);
2252   if ((ret = do_fail (stream, buf))) { return ret; }
2253
2254   /* Force it, should succeed. */
2255   snprintf_func (buf, TESTBUFSIZE, "%s -f -e %s %s", program_name,
2256            TEST_TARGET_FILE, TEST_DELTA_FILE);
2257   if ((ret = do_cmd (stream, buf))) { return ret; }
2258   test_cleanup();
2259   return 0;
2260 }
2261
2262 /* This checks the proper operation of the -c flag.  When specified
2263  * the default output becomes stdout, otherwise the input must be
2264  * provided (encode) or it may be defaulted (decode w/ app header). */
2265 static int
2266 test_stdout_behavior (xd3_stream *stream, int ignore)
2267 {
2268   int ret;
2269   char buf[TESTBUFSIZE];
2270
2271   test_setup();
2272   snprintf_func (buf, TESTBUFSIZE, "cp /dev/null %s", TEST_TARGET_FILE);
2273   if ((ret = do_cmd (stream, buf))) { return ret; }
2274
2275   /* Without -c, encode writes to delta file */
2276   snprintf_func (buf, TESTBUFSIZE, "%s -e %s %s", program_name,
2277            TEST_TARGET_FILE, TEST_DELTA_FILE);
2278   if ((ret = do_cmd (stream, buf))) { return ret; }
2279
2280   /* With -c, encode writes to stdout */
2281   snprintf_func (buf, TESTBUFSIZE, "%s -e -c %s > %s", program_name,
2282            TEST_TARGET_FILE, TEST_DELTA_FILE);
2283   if ((ret = do_cmd (stream, buf))) { return ret; }
2284
2285   /* Without -c, decode writes to target file name, but it fails because the
2286    * file exists. */
2287   snprintf_func (buf, TESTBUFSIZE, "%s -q -d %s ", program_name, TEST_DELTA_FILE);
2288   if ((ret = do_fail (stream, buf))) { return ret; }
2289
2290   /* With -c, decode writes to stdout */
2291   snprintf_func (buf, TESTBUFSIZE, "%s -d -c %s > /dev/null", program_name, TEST_DELTA_FILE);
2292   if ((ret = do_cmd (stream, buf))) { return ret; }
2293   test_cleanup();
2294
2295   return 0;
2296 }
2297
2298 /* This tests that the no-output flag (-J) works. */
2299 static int
2300 test_no_output (xd3_stream *stream, int ignore)
2301 {
2302   int ret;
2303   char buf[TESTBUFSIZE];
2304
2305   test_setup ();
2306
2307   snprintf_func (buf, TESTBUFSIZE, "touch %s && chmod 0000 %s",
2308            TEST_NOPERM_FILE, TEST_NOPERM_FILE);
2309   if ((ret = do_cmd (stream, buf))) { return ret; }
2310
2311   if ((ret = test_make_inputs (stream, NULL, NULL))) { return ret; }
2312
2313   /* Try no_output encode w/out unwritable output file */
2314   snprintf_func (buf, TESTBUFSIZE, "%s -q -f -e %s %s", program_name,
2315            TEST_TARGET_FILE, TEST_NOPERM_FILE);
2316   if ((ret = do_fail (stream, buf))) { return ret; }
2317   snprintf_func (buf, TESTBUFSIZE, "%s -J -e %s %s", program_name,
2318            TEST_TARGET_FILE, TEST_NOPERM_FILE);
2319   if ((ret = do_cmd (stream, buf))) { return ret; }
2320
2321   /* Now really write the delta to test decode no-output */
2322   snprintf_func (buf, TESTBUFSIZE, "%s -e %s %s", program_name,
2323            TEST_TARGET_FILE, TEST_DELTA_FILE);
2324   if ((ret = do_cmd (stream, buf))) { return ret; }
2325
2326   snprintf_func (buf, TESTBUFSIZE, "%s -q -f -d %s %s", program_name,
2327            TEST_DELTA_FILE, TEST_NOPERM_FILE);
2328   if ((ret = do_fail (stream, buf))) { return ret; }
2329   snprintf_func (buf, TESTBUFSIZE, "%s -J -d %s %s", program_name,
2330            TEST_DELTA_FILE, TEST_NOPERM_FILE);
2331   if ((ret = do_cmd (stream, buf))) { return ret; }
2332   test_cleanup ();
2333   return 0;
2334 }
2335
2336 /* This tests that the default appheader works */
2337 static int
2338 test_appheader (xd3_stream *stream, int ignore)
2339 {
2340   int i;
2341   int ret;
2342   char buf[TESTBUFSIZE];
2343   char bogus[TESTBUFSIZE];
2344   xoff_t ssize, tsize;
2345   test_setup ();
2346
2347   if ((ret = test_make_inputs (stream, &ssize, &tsize))) { return ret; }
2348
2349   snprintf_func (buf, TESTBUFSIZE, "%s -q -f -e -s %s %s %s", program_name,
2350                  TEST_SOURCE_FILE, TEST_TARGET_FILE, TEST_DELTA_FILE);
2351   if ((ret = do_cmd (stream, buf))) { return ret; }
2352
2353   if ((ret = test_copy_to (program_name, TEST_RECON2_FILE))) { return ret; }
2354
2355   snprintf_func (buf, TESTBUFSIZE, "chmod 0700 %s", TEST_RECON2_FILE);
2356   if ((ret = do_cmd (stream, buf))) { return ret; }
2357
2358   if ((ret = test_save_copy (TEST_TARGET_FILE))) { return ret; }
2359   if ((ret = test_copy_to (TEST_SOURCE_FILE, TEST_TARGET_FILE))) { return ret; }
2360
2361   if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_COPY_FILE)) == 0)
2362     {
2363       return XD3_INVALID;  // I.e., files are different!
2364     }
2365
2366   // Test that the target file is restored.
2367   snprintf_func (buf, TESTBUFSIZE, "(cd /tmp && %s -q -f -d %s)",
2368                  TEST_RECON2_FILE,
2369                  TEST_DELTA_FILE);
2370   if ((ret = do_cmd (stream, buf))) { return ret; }
2371
2372   if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_COPY_FILE)) != 0)
2373     {
2374       return ret;
2375     }
2376
2377   // Test a malicious string w/ entries > 4 in the appheader by having
2378   // the encoder write it:
2379   for (i = 0; i < TESTBUFSIZE / 4; ++i)
2380     {
2381       bogus[2*i] = 'G';
2382       bogus[2*i+1] = '/';
2383     }
2384   bogus[TESTBUFSIZE/2-1] = 0;
2385
2386   snprintf_func (buf, TESTBUFSIZE,
2387                  "%s -q -f -A=%s -e -s %s %s %s", program_name, bogus,
2388                  TEST_SOURCE_FILE, TEST_TARGET_FILE, TEST_DELTA_FILE);
2389   if ((ret = do_cmd (stream, buf))) { return ret; }
2390   // Then read it:
2391   snprintf_func (buf, TESTBUFSIZE, "(cd /tmp && %s -q -f -d %s)",
2392                  TEST_RECON2_FILE,
2393                  TEST_DELTA_FILE);
2394   if ((ret = do_cmd (stream, buf)) == 0)
2395     {
2396       return XD3_INVALID;  // Impossible
2397     }
2398   if (!WIFEXITED(ret))
2399     {
2400       return XD3_INVALID;  // Must have crashed!
2401     }
2402
2403   return 0;
2404 }
2405
2406 /***********************************************************************
2407  Source identical optimization
2408  ***********************************************************************/
2409
2410 /* Computing a delta should be fastest when the two inputs are
2411  * identical, this checks it.  The library is called to compute a
2412  * delta between a 10000 byte file, 1000 byte winsize, 500 byte source
2413  * blocksize.  The same buffer is used for both source and target. */
2414 static int
2415 test_identical_behavior (xd3_stream *stream, int ignore)
2416 {
2417 #define IDB_TGTSZ 10000  /* Not a power of two b/c of hard-coded expectations below. */
2418 #define IDB_BLKSZ 512
2419 #define IDB_WINSZ 1000
2420 #define IDB_DELSZ 1000
2421 #define IDB_WINCNT (IDB_TGTSZ / IDB_WINSZ)
2422
2423   int ret, i;
2424   uint8_t buf[IDB_TGTSZ];
2425   uint8_t del[IDB_DELSZ];
2426   uint8_t rec[IDB_TGTSZ];
2427   xd3_source source;
2428   int nextencwin = 0;
2429   int winstarts = 0, winfinishes = 0;
2430   usize_t delpos = 0, recsize;
2431   xd3_config config;
2432   memset(&source, 0, sizeof(source));
2433
2434   for (i = 0; i < IDB_TGTSZ; i += 1)
2435     {
2436       buf[i] = (uint8_t) mt_random (&static_mtrand);
2437     }
2438
2439   stream->winsize = IDB_WINSZ;
2440
2441   source.blksize  = IDB_BLKSZ;
2442   source.name     = "";
2443   source.curblk   = NULL;
2444   source.curblkno = 0;
2445
2446   if ((ret = xd3_set_source (stream, & source))) { goto fail; }
2447
2448   /* Compute an delta between identical source and targets. */
2449   for (;;)
2450     {
2451       ret = xd3_encode_input (stream);
2452
2453       if (ret == XD3_INPUT)
2454         {
2455           xd3_avail_input (stream, buf + (IDB_WINSZ * nextencwin), IDB_WINSZ);
2456           nextencwin += 1;
2457           continue;
2458         }
2459
2460       if (ret == XD3_GETSRCBLK)
2461         {
2462           source.curblkno = source.getblkno;
2463           source.onblk    = IDB_BLKSZ;
2464           source.curblk   = buf + source.getblkno * IDB_BLKSZ;
2465           continue;
2466         }
2467
2468       if (ret == XD3_WINSTART)
2469         {
2470           winstarts++;
2471           continue;
2472         }
2473       if (ret == XD3_WINFINISH)
2474         {
2475           winfinishes++;
2476           if (winfinishes == IDB_WINCNT)
2477             {
2478               break;
2479             }
2480           continue;
2481         }
2482
2483       if (ret != XD3_OUTPUT) { goto fail; }
2484
2485       CHECK(delpos + stream->avail_out <= IDB_DELSZ);
2486
2487       memcpy (del + delpos, stream->next_out, stream->avail_out);
2488
2489       delpos += stream->avail_out;
2490
2491       xd3_consume_output (stream);
2492     }
2493
2494   CHECK(winfinishes == IDB_WINCNT);
2495   CHECK(winstarts == IDB_WINCNT);
2496   CHECK(nextencwin == IDB_WINCNT);
2497
2498   /* Reset. */
2499   memset(&source, 0, sizeof(source));
2500   source.blksize  = IDB_TGTSZ;
2501   source.onblk    = IDB_TGTSZ;
2502   source.curblk   = buf;
2503   source.curblkno = 0;
2504
2505   if ((ret = xd3_close_stream (stream))) { goto fail; }
2506   xd3_free_stream (stream);
2507   xd3_init_config (& config, 0);
2508   if ((ret = xd3_config_stream (stream, & config))) { goto fail; }
2509   if ((ret = xd3_set_source_and_size (stream, & source, IDB_TGTSZ))) { goto fail; }
2510
2511   /* Decode. */
2512   if ((ret = xd3_decode_stream (stream, del, delpos, rec, & recsize, IDB_TGTSZ))) { goto fail; }
2513
2514   /* Check result size and data. */
2515   if (recsize != IDB_TGTSZ) { stream->msg = "wrong size reconstruction"; goto fail; }
2516   if (memcmp (rec, buf, IDB_TGTSZ) != 0) { stream->msg = "wrong data reconstruction"; goto fail; }
2517
2518   /* Check that there was one copy per window. */
2519   IF_DEBUG (if (stream->n_scpy != IDB_WINCNT ||
2520                 stream->n_add != 0 ||
2521                 stream->n_run != 0) { stream->msg = "wrong copy count"; goto fail; });
2522
2523   /* Check that no checksums were computed because the initial match
2524      was presumed. */
2525   IF_DEBUG (if (stream->large_ckcnt != 0) { stream->msg = "wrong checksum behavior"; goto fail; });
2526
2527   ret = 0;
2528  fail:
2529   return ret;
2530 }
2531
2532 /***********************************************************************
2533  String matching test
2534  ***********************************************************************/
2535
2536 /* Check particular matching behaviors by calling
2537  * xd3_string_match_soft directly with specific arguments. */
2538 typedef struct _string_match_test string_match_test;
2539
2540 typedef enum
2541 {
2542   SM_NONE    = 0,
2543   SM_LAZY    = (1 << 1),
2544 } string_match_flags;
2545
2546 struct _string_match_test
2547 {
2548   const char *input;
2549   int         flags;
2550   const char *result;
2551 };
2552
2553 static const string_match_test match_tests[] =
2554 {
2555   /* nothing */
2556   { "1234567890", SM_NONE, "" },
2557
2558   /* basic run, copy */
2559   { "11111111112323232323", SM_NONE, "R0/10 C12/8@10" },
2560
2561   /* no run smaller than MIN_RUN=8 */
2562   { "1111111",  SM_NONE, "C1/6@0" },
2563   { "11111111", SM_NONE, "R0/8" },
2564
2565   /* simple promotion: the third copy address depends on promotion */
2566   { "ABCDEF_ABCDEF^ABCDEF", SM_NONE,    "C7/6@0 C14/6@7" },
2567   /* { "ABCDEF_ABCDEF^ABCDEF", SM_PROMOTE, "C7/6@0 C14/6@0" }, forgotten */
2568
2569   /* simple lazy: there is a better copy starting with "23 X" than "123 " */
2570   { "123 23 XYZ 123 XYZ", SM_NONE, "C11/4@0" },
2571   { "123 23 XYZ 123 XYZ", SM_LAZY, "C11/4@0 C12/6@4" },
2572
2573   /* trylazy: no lazy matches unless there are at least two characters beyond
2574    * the first match */
2575   { "2123_121212",   SM_LAZY, "C7/4@5" },
2576   { "2123_1212123",  SM_LAZY, "C7/4@5" },
2577   { "2123_1212123_", SM_LAZY, "C7/4@5 C8/5@0" },
2578
2579   /* trylazy: no lazy matches if the copy is >= MAXLAZY=10 */
2580   { "2123_121212123_",   SM_LAZY, "C7/6@5 C10/5@0" },
2581   { "2123_12121212123_", SM_LAZY, "C7/8@5 C12/5@0" },
2582   { "2123_1212121212123_", SM_LAZY, "C7/10@5" },
2583
2584   /* lazy run: check a run overlapped by a longer copy */
2585   { "11111112 111111112 1", SM_LAZY, "C1/6@0 R9/8 C10/10@0" },
2586
2587   /* lazy match: match_length,run_l >= min_match tests, shouldn't get any
2588    * copies within the run, no run within the copy */
2589   { "^________^________  ", SM_LAZY, "R1/8 C9/9@0" },
2590
2591   /* chain depth: it only goes back 10. this checks that the 10th match hits
2592    * and the 11th misses. */
2593   { "1234 1234_1234-1234=1234+1234[1234]1234{1234}1234<1234 ", SM_NONE,
2594     "C5/4@0 C10/4@5 C15/4@10 C20/4@15 C25/4@20 C30/4@25 C35/4@30 C40/4@35 C45/4@40 C50/5@0" },
2595   { "1234 1234_1234-1234=1234+1234[1234]1234{1234}1234<1234>1234 ", SM_NONE,
2596     "C5/4@0 C10/4@5 C15/4@10 C20/4@15 C25/4@20 C30/4@25 C35/4@30 C40/4@35 C45/4@40 C50/4@45 C55/4@50" },
2597
2598   /* ssmatch test */
2599   { "ABCDE___ABCDE*** BCDE***", SM_NONE, "C8/5@0 C17/4@1" },
2600   /*{ "ABCDE___ABCDE*** BCDE***", SM_SSMATCH, "C8/5@0 C17/7@9" }, forgotten */
2601 };
2602
2603 static int
2604 test_string_matching (xd3_stream *stream, int ignore)
2605 {
2606   usize_t i;
2607   int ret;
2608   xd3_config config;
2609   char rbuf[TESTBUFSIZE];
2610
2611   for (i = 0; i < SIZEOF_ARRAY (match_tests); i += 1)
2612     {
2613       const string_match_test *test = & match_tests[i];
2614       char *rptr = rbuf;
2615       usize_t len = (usize_t) strlen (test->input);
2616
2617       xd3_free_stream (stream);
2618       xd3_init_config (& config, 0);
2619
2620       config.smatch_cfg   = XD3_SMATCH_SOFT;
2621       config.smatcher_soft.large_look   = 4;
2622       config.smatcher_soft.large_step   = 4;
2623       config.smatcher_soft.small_look   = 4;
2624       config.smatcher_soft.small_chain  = 10;
2625       config.smatcher_soft.small_lchain = 10;
2626       config.smatcher_soft.max_lazy     = (test->flags & SM_LAZY) ? 10 : 0;
2627       config.smatcher_soft.long_enough  = 10;
2628
2629       if ((ret = xd3_config_stream (stream, & config))) { return ret; }
2630       if ((ret = xd3_encode_init_full (stream))) { return ret; }
2631
2632       xd3_avail_input (stream, (uint8_t*)test->input, len);
2633
2634       if ((ret = stream->smatcher.string_match (stream))) { return ret; }
2635
2636       *rptr = 0;
2637       while (! xd3_rlist_empty (& stream->iopt_used))
2638         {
2639           xd3_rinst *inst = xd3_rlist_pop_front (& stream->iopt_used);
2640
2641           switch (inst->type)
2642             {
2643             case XD3_RUN: *rptr++ = 'R'; break;
2644             case XD3_CPY: *rptr++ = 'C'; break;
2645             default: CHECK(0);
2646             }
2647
2648           snprintf_func (rptr, rbuf+TESTBUFSIZE-rptr, "%d/%d",
2649                          inst->pos, inst->size);
2650           rptr += strlen (rptr);
2651
2652           if (inst->type == XD3_CPY)
2653             {
2654               *rptr++ = '@';
2655               snprintf_func (rptr, rbuf+TESTBUFSIZE-rptr, "%"Q"d", inst->addr);
2656               rptr += strlen (rptr);
2657             }
2658
2659           *rptr++ = ' ';
2660
2661           xd3_rlist_push_back (& stream->iopt_free, inst);
2662         }
2663
2664       if (rptr != rbuf)
2665         {
2666           rptr -= 1; *rptr = 0;
2667         }
2668
2669       if (strcmp (rbuf, test->result) != 0)
2670         {
2671           XPR(NT "test %u: expected %s: got %s", i, test->result, rbuf);
2672           stream->msg = "wrong result";
2673           return XD3_INTERNAL;
2674         }
2675     }
2676
2677   return 0;
2678 }
2679
2680 /*
2681  * This is a test for many overlapping instructions. It must be a lazy
2682  * matcher.
2683  */
2684 static int
2685 test_iopt_flush_instructions (xd3_stream *stream, int ignore)
2686 {
2687   int ret, i;
2688   usize_t tpos = 0;
2689   usize_t delta_size, recon_size;
2690   xd3_config config;
2691   uint8_t target[TESTBUFSIZE];
2692   uint8_t delta[TESTBUFSIZE];
2693   uint8_t recon[TESTBUFSIZE];
2694
2695   xd3_free_stream (stream);
2696   xd3_init_config (& config, 0);
2697
2698   config.smatch_cfg    = XD3_SMATCH_SOFT;
2699   config.smatcher_soft.large_look    = 16;
2700   config.smatcher_soft.large_step    = 16;
2701   config.smatcher_soft.small_look    = 4;
2702   config.smatcher_soft.small_chain   = 128;
2703   config.smatcher_soft.small_lchain  = 16;
2704   config.smatcher_soft.max_lazy      = 8;
2705   config.smatcher_soft.long_enough   = 128;
2706
2707   if ((ret = xd3_config_stream (stream, & config))) { return ret; }
2708
2709   for (i = 1; i < 250; i++)
2710     {
2711       target[tpos++] = i;
2712       target[tpos++] = i+1;
2713       target[tpos++] = i+2;
2714       target[tpos++] = i+3;
2715       target[tpos++] = 0;
2716     }
2717   for (i = 1; i < 253; i++)
2718     {
2719       target[tpos++] = i;
2720     }
2721
2722   if ((ret = xd3_encode_stream (stream, target, tpos,
2723                                     delta, & delta_size, sizeof (delta))))
2724     {
2725       return ret;
2726     }
2727
2728   xd3_free_stream(stream);
2729   if ((ret = xd3_config_stream (stream, & config))) { return ret; }
2730
2731   if ((ret = xd3_decode_stream (stream, delta, delta_size,
2732                                 recon, & recon_size, sizeof (recon))))
2733     {
2734       return ret;
2735     }
2736
2737   CHECK(tpos == recon_size);
2738   CHECK(memcmp(target, recon, recon_size) == 0);
2739
2740   return 0;
2741 }
2742
2743 /*
2744  * This tests the 32/64bit ambiguity for source-window matching.
2745  */
2746 static int
2747 test_source_cksum_offset (xd3_stream *stream, int ignore)
2748 {
2749   xd3_source source;
2750
2751   // Inputs are:
2752   struct {
2753     xoff_t   cpos;   // stream->srcwin_cksum_pos;
2754     xoff_t   ipos;   // stream->total_in;
2755     xoff_t   size;   // stream->src->size;
2756
2757     usize_t  input;  // input  32-bit offset
2758     xoff_t   output; // output 64-bit offset
2759
2760   } cksum_test[] = {
2761     // If cpos is <= 2^32
2762     { 1, 1, 1, 1, 1 },
2763
2764 #if XD3_USE_LARGEFILE64
2765 //    cpos            ipos            size            input         output
2766 //    0x____xxxxxULL, 0x____xxxxxULL, 0x____xxxxxULL, 0x___xxxxxUL, 0x____xxxxxULL
2767     { 0x100100000ULL, 0x100000000ULL, 0x100200000ULL, 0x00000000UL, 0x100000000ULL },
2768     { 0x100100000ULL, 0x100000000ULL, 0x100200000ULL, 0xF0000000UL, 0x0F0000000ULL },
2769
2770     { 0x100200000ULL, 0x100100000ULL, 0x100200000ULL, 0x00300000UL, 0x000300000ULL },
2771
2772     { 25771983104ULL, 25770000000ULL, 26414808769ULL, 2139216707UL, 23614053187ULL },
2773
2774 #endif
2775
2776     { 0, 0, 0, 0, 0 },
2777   }, *test_ptr;
2778
2779   stream->src = &source;
2780
2781   for (test_ptr = cksum_test; test_ptr->cpos; test_ptr++) {
2782         xoff_t r;
2783     stream->srcwin_cksum_pos = test_ptr->cpos;
2784     stream->total_in = test_ptr->ipos;
2785
2786     r = xd3_source_cksum_offset(stream, test_ptr->input);
2787     CHECK(r == test_ptr->output);
2788   }
2789   return 0;
2790 }
2791
2792 static int
2793 test_in_memory (xd3_stream *stream, int ignore)
2794 {
2795   // test_text is 256 bytes
2796   uint8_t ibuf[sizeof(test_text)];
2797   uint8_t dbuf[sizeof(test_text)];
2798   uint8_t obuf[sizeof(test_text)];
2799   usize_t size = sizeof(test_text);
2800   usize_t dsize, osize;
2801   int r1, r2;
2802   int eflags = SECONDARY_DJW ? XD3_SEC_DJW : 0;
2803
2804   memcpy(ibuf, test_text, size);
2805   memset(ibuf + 128, 0, 16);
2806
2807   r1 = xd3_encode_memory(ibuf, size,
2808                          test_text, size,
2809                          dbuf, &dsize, size, eflags);
2810
2811   r2 = xd3_decode_memory(dbuf, dsize,
2812                          test_text, size,
2813                          obuf, &osize, size, 0);
2814
2815   if (r1 != 0 || r2 != 0 || dsize >= (size/2) || dsize < 1 ||
2816       osize != size) {
2817     stream->msg = "encode/decode size error";
2818     return XD3_INTERNAL;
2819   }
2820
2821   if (memcmp(obuf, ibuf, size) != 0) {
2822     stream->msg = "encode/decode data error";
2823     return XD3_INTERNAL;
2824   }
2825
2826   return 0;
2827 }
2828
2829 /***********************************************************************
2830  TEST MAIN
2831  ***********************************************************************/
2832
2833 static int
2834 xd3_selftest (void)
2835 {
2836 #define DO_TEST(fn,flags,arg)                                         \
2837   do {                                                                \
2838     xd3_stream stream;                                                \
2839     xd3_config config;                                                \
2840     xd3_init_config (& config, flags);                                \
2841     XPR(NT "testing " #fn "%s...",                          \
2842              flags ? (" (" #flags ")") : "");                         \
2843     if ((ret = xd3_config_stream (& stream, & config) == 0) &&        \
2844         (ret = test_ ## fn (& stream, arg)) == 0) {                   \
2845       XPR(NTR " success\n");                                          \
2846     } else {                                                          \
2847       XPR(NTR " failed: %s: %s\n", xd3_errstring (& stream),          \
2848                xd3_mainerror (ret)); }                                \
2849     xd3_free_stream (& stream);                                       \
2850     if (ret != 0) { goto failure; }                                   \
2851   } while (0)
2852
2853   int ret;
2854   DO_TEST (random_numbers, 0, 0);
2855
2856   DO_TEST (decode_integer_end_of_input, 0, 0);
2857   DO_TEST (decode_integer_overflow, 0, 0);
2858   DO_TEST (encode_decode_uint32_t, 0, 0);
2859   DO_TEST (encode_decode_uint64_t, 0, 0);
2860   DO_TEST (usize_t_overflow, 0, 0);
2861   DO_TEST (forward_match, 0, 0);
2862
2863   DO_TEST (address_cache, 0, 0);
2864
2865   DO_TEST (string_matching, 0, 0);
2866   DO_TEST (choose_instruction, 0, 0);
2867   DO_TEST (identical_behavior, 0, 0);
2868   DO_TEST (in_memory, 0, 0);
2869
2870   DO_TEST (iopt_flush_instructions, 0, 0);
2871   DO_TEST (source_cksum_offset, 0, 0);
2872
2873   DO_TEST (decompress_single_bit_error, 0, 3);
2874   DO_TEST (decompress_single_bit_error, XD3_ADLER32, 3);
2875
2876   IF_LZMA (DO_TEST (decompress_single_bit_error, XD3_SEC_LZMA, 54));
2877   IF_FGK (DO_TEST (decompress_single_bit_error, XD3_SEC_FGK, 3));
2878   IF_DJW (DO_TEST (decompress_single_bit_error, XD3_SEC_DJW, 8));
2879
2880 #if SHELL_TESTS
2881   DO_TEST (force_behavior, 0, 0);
2882   DO_TEST (stdout_behavior, 0, 0);
2883   DO_TEST (no_output, 0, 0);
2884   DO_TEST (appheader, 0, 0);
2885   DO_TEST (command_line_arguments, 0, 0);
2886
2887 #if EXTERNAL_COMPRESSION
2888   DO_TEST (source_decompression, 0, 0);
2889   DO_TEST (externally_compressed_io, 0, 0);
2890 #endif
2891
2892   DO_TEST (recode_command, 0, 0);
2893 #endif
2894
2895   IF_LZMA (DO_TEST (secondary_lzma, 0, 1));
2896   IF_DJW (DO_TEST (secondary_huff, 0, DJW_MAX_GROUPS));
2897   IF_FGK (DO_TEST (secondary_fgk, 0, 1));
2898
2899   DO_TEST (compressed_stream_overflow, 0, 0);
2900   IF_LZMA (DO_TEST (compressed_stream_overflow, XD3_SEC_LZMA, 0));
2901
2902 failure:
2903   test_cleanup ();
2904   return ret == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
2905 #undef DO_TEST
2906 }