source: nikanabo/current/xdelta/diy/xdelta3-test.h @ 185

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