1 /* xdelta 3 - delta compression tools and library Copyright (C) 2001,
2 * 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012.
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.
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.
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
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
24 static const uint32_t TEST_SEED1 = 5489UL;
27 static const uint32_t UPPER_MASK = 0x80000000;
28 static const uint32_t LOWER_MASK = 0x7FFFFFFF;
29 static const uint32_t MATRIX_A = 0x9908B0DF;
35 typedef struct mtrand mtrand;
39 uint32_t mt_buffer_[MT_LEN];
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);
47 void mt_init(mtrand *mt, uint32_t seed) {
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 */
57 (1812433253UL * (mt->mt_buffer_[i-1] ^
58 (mt->mt_buffer_[i-1] >> 30)) + i);
62 uint32_t mt_random (mtrand *mt) {
64 unsigned long mag01[2];
68 if (mt->mt_index_ >= MT_LEN) {
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];
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];
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];
90 y = mt->mt_buffer_[mt->mt_index_++];
93 y ^= (y << 7) & 0x9d2c5680UL;
94 y ^= (y << 15) & 0xefc60000UL;
100 static mtrand static_mtrand;
105 mt_exp_rand (uint32_t mean, uint32_t max_value)
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);
112 return min (x, max_value);
116 #include <sys/wait.h>
119 #define MSG_IS(x) (stream->msg != NULL && strcmp ((x), stream->msg) == 0)
121 static const usize_t TWO_MEGS_AND_DELTA = (3 << 20);
122 static const usize_t ADDR_CACHE_ROUNDS = 10000;
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;
130 #define TESTBUFSIZE (1024 * 16)
132 #define TESTFILESIZE (1024)
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];
142 #define CHECK(cond) if (!(cond)) { XPR(NT "check failure: " #cond); abort(); }
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";
150 /***********************************************************************
152 ***********************************************************************/
154 static void DOT (void) { XPR(NTR "."); }
155 static int do_cmd (xd3_stream *stream, const char *buf)
158 if ((ret = system (buf)) != 0)
162 stream->msg = "command exited non-zero";
163 IF_DEBUG1 (XPR(NT "command was: %s\n", buf));
167 stream->msg = "abnormal command termination";
174 static int do_fail (xd3_stream *stream, const char *buf)
178 if (! WIFEXITED (ret) || WEXITSTATUS (ret) != 1)
180 stream->msg = "command should have not succeeded";
181 XPR(NT "command was %s\n", buf);
187 /* Test that the exponential distribution actually produces its mean. */
189 test_random_numbers (xd3_stream *stream, int ignore)
194 usize_t n_rounds = 1000000;
195 double average, error;
196 double allowed_error = 0.1;
198 mt_init (& static_mtrand, 0x9f73f7fe);
200 for (i = 0; i < n_rounds; i += 1)
202 sum += mt_exp_rand (mean, USIZE_T_MAX);
205 average = (double) sum / (double) n_rounds;
206 error = average - (double) mean;
208 if (error < allowed_error && error > -allowed_error)
213 /*XPR(NT "error is %f\n", error);*/
214 stream->msg = "random distribution looks broken";
219 test_unlink (char* file)
222 if ((ret = unlink (file)) != 0 && errno != ENOENT)
224 XPR(NT "unlink %s failed: %s\n", file, strerror(ret));
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);
242 int test_setup (void)
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);
258 test_make_inputs (xd3_stream *stream, xoff_t *ss_out, xoff_t *ts_out)
260 usize_t ts = (mt_random (&static_mtrand) % TEST_FILE_MEAN) +
262 usize_t ss = (mt_random (&static_mtrand) % TEST_FILE_MEAN) +
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;
270 if (buf == NULL) { return ENOMEM; }
272 if ((tf = fopen (TEST_TARGET_FILE, "w")) == NULL ||
273 (ss_out != NULL && (sf = fopen (TEST_SOURCE_FILE, "w")) == NULL))
275 stream->msg = "write failed";
282 for (i = 0; i < ss; )
284 sbuf[i++] = (uint8_t) mt_random (&static_mtrand);
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. */
293 /* XPR(NT "ss = %u ts = %u\n", ss, ts); */
294 for (i = 0; i < ts; )
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);
303 next = min (left, next);
304 do_copy = (next > add_left ||
305 (mt_random (&static_mtrand) / \
306 (double)USIZE_T_MAX) >= add_prob);
314 do_copy &= (ss - next) > 0;
320 size_t offset = mt_random (&static_mtrand) % ((ss_out == NULL) ?
323 /* XPR(NT "[%u] copy %u at %u ", i, next, offset); */
325 for (j = 0; j < next; j += 1)
327 char c = ((ss_out == NULL) ? tbuf : sbuf)[offset + j];
328 /* XPR(NT "%x%x", (c >> 4) & 0xf, c & 0xf); */
336 /* XPR(NT "[%u] add %u ", i, next); */
337 for (j = 0; j < next; j += 1)
339 char c = (char) mt_random (&static_mtrand);
340 /* XPR(NT "%x%x", (c >> 4) & 0xf, c & 0xf); */
348 /* XPR(NT "sadd = %u max = %u\n", sadd, sadd_max); */
350 if ((fwrite (tbuf, 1, ts, tf) != ts) ||
351 (ss_out != NULL && (fwrite (sbuf, 1, ss, sf) != ss)))
353 stream->msg = "write failed";
358 if ((ret = fclose (tf)) || (ss_out != NULL && (ret = fclose (sf))))
360 stream->msg = "close failed";
365 if (ts_out) { (*ts_out) = ts; }
366 if (ss_out) { (*ss_out) = ss; }
374 test_compare_files (const char* tgt, const char *rec)
377 static uint8_t obuf[TESTBUFSIZE], rbuf[TESTBUFSIZE];
383 if ((orig = fopen (tgt, "r")) == NULL)
385 XPR(NT "open %s failed\n", tgt);
389 if ((recons = fopen (rec, "r")) == NULL)
391 XPR(NT "open %s failed\n", rec);
397 oc = fread (obuf, 1, TESTBUFSIZE, orig);
398 rc = fread (rbuf, 1, TESTBUFSIZE, recons);
410 for (i = 0; i < oc; i += 1)
412 if (obuf[i] != rbuf[i])
414 XPR(NT "byte %u (read %u @ %"Q"u) %d != %d\n",
415 (int)i, (int)oc, offset, obuf[i], rbuf[i]);
434 test_copy_to (const char *from, const char *to)
436 char buf[TESTBUFSIZE];
439 snprintf_func (buf, TESTBUFSIZE, "cp -f %s %s", from, to);
441 if ((ret = system (buf)) != 0)
450 test_save_copy (const char *origname)
452 return test_copy_to(origname, TEST_COPY_FILE);
456 test_file_size (const char* file, xoff_t *size)
462 if (stat (file, & sbuf) < 0)
465 XPR(NT "stat failed: %s: %s\n", file, strerror (ret));
469 if (! S_ISREG (sbuf.st_mode))
472 XPR(NT "not a regular file: %s: %s\n", file, strerror (ret));
476 (*size) = sbuf.st_size;
480 /***********************************************************************
482 ***********************************************************************/
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. */
489 test_read_integer_error (xd3_stream *stream, usize_t trunto, const char *msg)
491 uint64_t eval = 1ULL << 34;
493 xd3_output *buf = NULL;
498 buf = xd3_alloc_output (stream, buf);
500 if ((ret = xd3_emit_uint64_t (stream, & buf, eval)))
508 max = buf->base + buf->next - trunto;
510 if ((ret = xd3_read_uint32_t (stream, & inp, max, & rval)) !=
516 else if (trunto && trunto < buf->next)
527 xd3_free_output (stream, buf);
531 /* Test integer overflow using the above routine. */
533 test_decode_integer_overflow (xd3_stream *stream, int unused)
535 return test_read_integer_error (stream, 0, "overflow in read_intger");
538 /* Test integer EOI using the above routine. */
540 test_decode_integer_end_of_input (xd3_stream *stream, int unused)
542 return test_read_integer_error (stream, 1, "end-of-input in read_integer");
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; \
552 usize_t nvalues = 0; \
556 for (i = 0; i < (sizeof (TYPE) * 8); i += 7) \
558 values[nvalues++] = (ONE << i) - ONE; \
559 values[nvalues++] = (ONE << i); \
560 values[nvalues++] = (ONE << i) + ONE; \
563 values[nvalues++] = MAX-ONE; \
564 values[nvalues++] = MAX; \
566 rbuf = xd3_alloc_output (stream, rbuf); \
567 dbuf = xd3_alloc_output (stream, dbuf); \
569 for (i = 0; i < nvalues; i += 1) \
571 const uint8_t *max; \
572 const uint8_t *inp; \
578 if ((ret = xd3_emit_ ## TYPE (stream, & rbuf, values[i])) || \
579 (ret = xd3_emit_ ## TYPE (stream, & dbuf, values[i]))) \
585 max = rbuf->base + rbuf->next; \
587 if (rbuf->next != xd3_sizeof_ ## TYPE (values[i])) \
589 ret = XD3_INTERNAL; \
593 if ((ret = xd3_read_ ## TYPE (stream, & inp, max, & val))) \
598 if (val != values[i]) \
600 ret = XD3_INTERNAL; \
607 stream->next_in = dbuf->base; \
608 stream->avail_in = dbuf->next; \
610 for (i = 0; i < nvalues; i += 1) \
614 if ((ret = xd3_decode_ ## TYPE (stream, & val))) \
619 if (val != values[i]) \
621 ret = XD3_INTERNAL; \
626 if (stream->avail_in != 0) \
628 ret = XD3_INTERNAL; \
633 xd3_free_output (stream, rbuf); \
634 xd3_free_output (stream, dbuf); \
639 test_encode_decode_uint32_t (xd3_stream *stream, int unused)
641 TEST_ENCODE_DECODE_INTEGER(uint32_t,1U,UINT32_MAX);
645 test_encode_decode_uint64_t (xd3_stream *stream, int unused)
647 TEST_ENCODE_DECODE_INTEGER(uint64_t,1ULL,UINT64_MAX);
651 test_usize_t_overflow (xd3_stream *stream, int unused)
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; }
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; }
665 stream->msg = "incorrect overflow computation";
670 test_forward_match (xd3_stream *stream, int unused)
673 uint8_t buf1[256], buf2[256];
675 memset(buf1, 0, 256);
676 memset(buf2, 0, 256);
678 for (i = 0; i < 256; i++)
680 CHECK(xd3_forward_match(buf1, buf2, i) == (int)i);
683 for (i = 0; i < 255; i++)
686 CHECK(xd3_forward_match(buf1, buf2, 256) == (int)i);
693 /***********************************************************************
695 ***********************************************************************/
698 test_address_cache (xd3_stream *stream, int unused)
704 uint8_t *big_buf, *buf_max;
710 stream->acache.s_near = stream->code_table_desc->near_modes;
711 stream->acache.s_same = stream->code_table_desc->same_modes;
713 if ((ret = xd3_encode_init_partial (stream))) { return ret; }
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);
718 memset (mode_counts, 0, sizeof (mode_counts));
719 memset (modes, 0, ADDR_CACHE_ROUNDS);
723 mt_init (& static_mtrand, 0x9f73f7fc);
725 /* First pass: encode addresses */
726 xd3_init_cache (& stream->acache);
728 for (offset = 1; offset < ADDR_CACHE_ROUNDS; offset += 1)
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);
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; }
744 if ((ret = xd3_encode_address (stream, addr, offset, & modes[offset]))) { return ret; }
746 addrs[offset] = addr;
747 mode_counts[modes[offset]] += 1;
750 /* Copy addresses into a contiguous buffer. */
751 big_buf = (uint8_t*) xd3_alloc (stream, xd3_sizeof_output (ADDR_HEAD (stream)), 1);
753 for (offset = 0, outp = ADDR_HEAD (stream); outp != NULL; offset += outp->next, outp = outp->next_page)
755 memcpy (big_buf + offset, outp->base, outp->next);
758 buf_max = big_buf + offset;
761 /* Second pass: decode addresses */
762 xd3_init_cache (& stream->acache);
764 for (offset = 1; offset < ADDR_CACHE_ROUNDS; offset += 1)
768 if ((ret = xd3_decode_address (stream, offset, modes[offset], & buf, buf_max, & addr))) { return ret; }
770 if (addr != addrs[offset])
772 stream->msg = "incorrect decoded address";
777 /* Check that every byte, mode was used. */
780 stream->msg = "address bytes not used";
784 for (i = 0; i < (2 + stream->acache.s_same + stream->acache.s_near); i += 1)
786 if (mode_counts[i] == 0)
788 stream->msg = "address mode not used";
793 xd3_free (stream, modes);
794 xd3_free (stream, addrs);
795 xd3_free (stream, big_buf);
800 /***********************************************************************
801 Encode and decode with single bit error
802 ***********************************************************************/
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[] =
825 static const uint8_t test_apphead[] = "header test";
828 test_compress_text (xd3_stream *stream,
830 usize_t *encoded_size)
834 int oflags = stream->flags;
835 int flags = stream->flags | XD3_FLUSH;
837 xd3_free_stream (stream);
838 xd3_init_config (& cfg, flags);
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;
852 xd3_config_stream (stream, & cfg);
856 xd3_set_appheader (stream, test_apphead,
857 (usize_t) strlen ((char*) test_apphead));
859 if ((ret = xd3_encode_stream (stream, test_text, sizeof (test_text),
860 encoded, encoded_size, 4*sizeof (test_text)))) { goto fail; }
862 if ((ret = xd3_close_stream (stream))) { goto fail; }
865 xd3_free_stream (stream);
866 xd3_init_config (& cfg, oflags);
867 xd3_config_stream (stream, & cfg);
872 test_decompress_text (xd3_stream *stream, uint8_t *enc, usize_t enc_size, usize_t test_desize)
875 char decoded[sizeof (test_text)];
877 usize_t apphead_size;
878 usize_t decoded_size;
882 int flags = stream->flags;
886 /* Test decoding test_desize input bytes at a time */
887 take = min (enc_size - pos, test_desize);
890 xd3_avail_input (stream, enc + pos, take);
892 ret = xd3_decode_input (stream);
905 if (pos < enc_size) { goto input; }
906 /* else fallthrough */
912 CHECK(ret == XD3_OUTPUT);
913 CHECK(pos == enc_size);
915 if (stream->avail_out != sizeof (test_text))
917 stream->msg = "incorrect output size";
922 decoded_size = stream->avail_out;
923 memcpy (decoded, stream->next_out, stream->avail_out);
925 xd3_consume_output (stream);
927 if ((ret = xd3_get_appheader (stream, & apphead, & apphead_size))) { goto fail; }
929 if (apphead_size != strlen ((char*) test_apphead) ||
930 memcmp (apphead, test_apphead, strlen ((char*) test_apphead)) != 0)
932 stream->msg = "incorrect appheader";
937 if ((ret = xd3_decode_input (stream)) != XD3_WINFINISH ||
938 (ret = xd3_close_stream (stream)) != 0)
943 if (decoded_size != sizeof (test_text) ||
944 memcmp (decoded, test_text, sizeof (test_text)) != 0)
946 stream->msg = "incorrect output text";
952 xd3_free_stream (stream);
953 xd3_init_config (& cfg, flags);
954 xd3_config_stream (stream, & cfg);
961 test_decompress_single_bit_error (xd3_stream *stream, int expected_non_failures)
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;
970 //#define DEBUG_TEST_FAILURES
971 #ifndef DEBUG_TEST_FAILURES
972 #define TEST_FAILURES()
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.
980 for i in test_text.xz.*; do ./xdelta3 printdelta $i > $i.out;
981 diff $i.out test_text.xz.0.out; done
984 system ("rm -rf test_text.*");
986 char buf[TESTBUFSIZE];
988 snprintf_func (buf, TESTBUFSIZE, "test_text");
989 f = fopen (buf, "w");
990 fwrite (test_text,1,sizeof (test_text),f);
993 #define TEST_FAILURES() \
995 char buf[TESTBUFSIZE]; \
997 snprintf_func (buf, TESTBUFSIZE, "test_text.xz.%d", non_failures); \
998 f = fopen (buf, "w"); \
999 fwrite (encoded,1,encoded_size,f); \
1004 stream->sec_data.inefficient = 1;
1005 stream->sec_inst.inefficient = 1;
1006 stream->sec_addr.inefficient = 1;
1008 /* Encode text, test correct input */
1009 if ((ret = test_compress_text (stream, encoded, & encoded_size)))
1011 /*stream->msg = "without error: encode failure";*/
1015 if ((ret = test_decompress_text (stream, encoded, encoded_size,
1016 sizeof (test_text) / 4)))
1018 /*stream->msg = "without error: decode failure";*/
1024 for (i = 0; i < encoded_size*8; i += 1)
1026 /* Single bit error. */
1027 encoded[i/8] ^= 1 << (i%8);
1029 if ((ret = test_decompress_text (stream, encoded,
1030 encoded_size, sizeof (test_text))) == 0)
1033 #ifdef DEBUG_TEST_FAILURES
1034 XPR(NT "%u[%u] non-failure %u\n", i/8, i%8, non_failures);
1040 /*XPR(NT "%u[%u] failure: %s\n", i/8, i%8, stream->msg);*/
1043 /* decompress_text returns EIO when the final memcmp() fails, but that
1044 * should never happen with checksumming on. */
1045 if (cksum && ret == EIO)
1047 /*XPR(NT "%u[%u] cksum mismatch\n", i/8, i%8);*/
1048 stream->msg = "checksum mismatch";
1049 return XD3_INTERNAL;
1052 /* Undo single bit error. */
1053 encoded[i/8] ^= 1 << (i%8);
1056 /* Test correct input again */
1057 if ((ret = test_decompress_text (stream, encoded, encoded_size, 1)))
1059 /*stream->msg = "without error: decode failure";*/
1063 /* Check expected non-failures */
1064 if (non_failures != expected_non_failures)
1066 XPR(NT "non-failures %u; expected %u",
1067 non_failures, expected_non_failures);
1068 stream->msg = "incorrect";
1069 return XD3_INTERNAL;
1077 /***********************************************************************
1078 Secondary compression tests
1079 ***********************************************************************/
1082 typedef int (*sec_dist_func) (xd3_stream *stream, xd3_output *data);
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);
1096 static sec_dist_func sec_dists[] =
1111 /* Test ditsribution: 100 bytes of the same character (13). */
1113 sec_dist_func1 (xd3_stream *stream, xd3_output *data)
1116 for (i = 0; i < 100; i += 1)
1118 if ((ret = xd3_emit_byte (stream, & data, 13))) { return ret; }
1123 /* Test ditsribution: uniform covering half the alphabet. */
1125 sec_dist_func2 (xd3_stream *stream, xd3_output *data)
1128 for (i = 0; i < ALPHABET_SIZE; i += 1)
1130 if ((ret = xd3_emit_byte (stream, & data, i%(ALPHABET_SIZE/2)))) { return ret; }
1135 /* Test ditsribution: uniform covering the entire alphabet. */
1137 sec_dist_func3 (xd3_stream *stream, xd3_output *data)
1140 for (i = 0; i < ALPHABET_SIZE; i += 1)
1142 if ((ret = xd3_emit_byte (stream, & data, i%ALPHABET_SIZE))) { return ret; }
1147 /* Test distribution: An exponential distribution covering half the alphabet */
1149 sec_dist_func4 (xd3_stream *stream, xd3_output *data)
1152 for (i = 0; i < ALPHABET_SIZE*20; i += 1)
1154 x = mt_exp_rand (10, ALPHABET_SIZE/2);
1155 if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
1160 /* Test distribution: An exponential distribution covering the entire alphabet */
1162 sec_dist_func5 (xd3_stream *stream, xd3_output *data)
1165 for (i = 0; i < ALPHABET_SIZE*20; i += 1)
1167 x = mt_exp_rand (10, ALPHABET_SIZE-1);
1168 if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
1173 /* Test distribution: An uniform random distribution covering half the alphabet */
1175 sec_dist_func6 (xd3_stream *stream, xd3_output *data)
1178 for (i = 0; i < ALPHABET_SIZE*20; i += 1)
1180 x = mt_random (&static_mtrand) % (ALPHABET_SIZE/2);
1181 if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
1186 /* Test distribution: An uniform random distribution covering the entire alphabet */
1188 sec_dist_func7 (xd3_stream *stream, xd3_output *data)
1191 for (i = 0; i < ALPHABET_SIZE*200; i += 1)
1193 x = mt_random (&static_mtrand) % ALPHABET_SIZE;
1194 if ((ret = xd3_emit_byte (stream, & data, x))) { return ret; }
1199 /* Test distribution: A small number of frequent characters, difficult
1200 * to divide into many groups */
1202 sec_dist_func8 (xd3_stream *stream, xd3_output *data)
1205 for (i = 0; i < ALPHABET_SIZE*5; i += 1)
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; }
1215 /* Test distribution: One that causes many FGK block promotions (found a bug) */
1217 sec_dist_func9 (xd3_stream *stream, xd3_output *data)
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)
1232 if (ramp < ALPHABET_SIZE)
1234 /* Initially Nth symbol has (N+1) frequency */
1238 if ((ret = xd3_emit_byte (stream, & data, ramp))) { return ret; }
1247 /* Thereafter, promote least freq to max freq */
1248 if (pcount == ALPHABET_SIZE)
1251 prom = (prom + 1) % ALPHABET_SIZE;
1255 if ((ret = xd3_emit_byte (stream, & data, prom))) { return ret; }
1261 /* Test distribution: freq[i] == i*i, creates a 21-bit code length, fixed in 3.0r. */
1263 sec_dist_func10 (xd3_stream *stream, xd3_output *data)
1266 for (i = 0; i < ALPHABET_SIZE; i += 1)
1268 for (j = 0; j <= (i*i); j += 1)
1270 if ((ret = xd3_emit_byte (stream, & data, i))) { return ret; }
1276 /* Test distribution: fibonacci */
1278 sec_dist_func11 (xd3_stream *stream, xd3_output *data)
1283 for (i = 0; i < 33; ++i)
1285 for (j = 0; j < (sum0 + sum1); ++j)
1287 if ((ret = xd3_emit_byte (stream, & data, i))) { return ret; }
1296 test_secondary_decode (xd3_stream *stream,
1297 const xd3_sec_type *sec,
1299 usize_t compress_size,
1300 const uint8_t *dec_input,
1301 const uint8_t *dec_correct,
1302 uint8_t *dec_output)
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;
1309 if ((dec_stream = sec->alloc (stream)) == NULL) { return ENOMEM; }
1311 if ((ret = sec->init (stream, dec_stream, 0)) != 0) { goto fail; }
1313 dec_input_used = dec_input;
1314 dec_input_end = dec_input + compress_size;
1316 dec_output_used = dec_output;
1317 dec_output_end = dec_output + input_size;
1319 if ((ret = sec->decode (stream, dec_stream,
1320 & dec_input_used, dec_input_end,
1321 & dec_output_used, dec_output_end)))
1326 if (dec_input_used != dec_input_end)
1328 stream->msg = "unused input";
1333 if (dec_output_used != dec_output_end)
1335 stream->msg = "unfinished output";
1340 if (memcmp (dec_output, dec_correct, input_size) != 0)
1342 stream->msg = "incorrect output";
1348 sec->destroy (stream, dec_stream);
1353 test_secondary (xd3_stream *stream, const xd3_sec_type *sec, usize_t groups)
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;
1363 memset (& cfg, 0, sizeof (cfg));
1365 cfg.inefficient = 1;
1367 for (cfg.ngroups = 1; cfg.ngroups <= groups; cfg.ngroups += 1)
1370 for (test_i = 0; test_i < SIZEOF_ARRAY (sec_dists); test_i += 1)
1372 mt_init (& static_mtrand, 0x9f73f7fc);
1374 in_head = xd3_alloc_output (stream, NULL);
1375 out_head = xd3_alloc_output (stream, NULL);
1376 enc_stream = sec->alloc (stream);
1381 if (in_head == NULL || out_head == NULL || enc_stream == NULL)
1386 if ((ret = sec_dists[test_i] (stream, in_head))) { goto fail; }
1388 if ((ret = sec->init (stream, enc_stream, 1)) != 0) { goto fail; }
1391 if ((ret = sec->encode (stream, enc_stream,
1392 in_head, out_head, & cfg)))
1394 XPR(NT "test %u: encode: %s", test_i, stream->msg);
1398 /* Calculate sizes, allocate contiguous arrays for decoding */
1399 input_size = xd3_sizeof_output (in_head);
1400 compress_size = xd3_sizeof_output (out_head);
1402 XPR(NTR "%.3f", 8.0 * (double) compress_size / (double) input_size);
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)
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)
1415 memcpy (dec_input + p_off, p->base, p->next);
1418 CHECK(p_off == compress_size);
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)
1424 memcpy (dec_correct + p_off, p->base, p->next);
1427 CHECK(p_off == input_size);
1429 if ((ret = test_secondary_decode (stream, sec, input_size,
1430 compress_size, dec_input,
1431 dec_correct, dec_output)))
1433 XPR(NT "test %u: decode: %s", test_i, stream->msg);
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. */
1443 int bytes = min (compress_size, 10U);
1444 for (i = 0; i < bytes * 8; i += 1)
1446 dec_input[i/8] ^= 1 << (i%8);
1448 if ((ret = test_secondary_decode (stream, sec, input_size,
1449 compress_size, dec_input,
1450 dec_correct, dec_output))
1453 /*XPR(NT "test %u: decode single-bit [%u/%u]
1454 error non-failure", test_i, i/8, i%8);*/
1457 dec_input[i/8] ^= 1 << (i%8);
1459 if ((i % (2*bytes)) == (2*bytes)-1)
1467 if (0) { nomem: ret = ENOMEM; }
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);
1477 if (ret != 0) { return ret; }
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); })
1492 /***********************************************************************
1493 TEST INSTRUCTION TABLE
1494 ***********************************************************************/
1496 /* Test that xd3_choose_instruction() does the right thing for its code
1499 test_choose_instruction (xd3_stream *stream, int ignore)
1503 stream->code_table = (*stream->code_table_func) ();
1505 for (i = 0; i < 256; i += 1)
1507 const xd3_dinst *d = stream->code_table + i;
1508 xd3_rinst prev, inst;
1510 CHECK(d->type1 > 0);
1512 memset (& prev, 0, sizeof (prev));
1513 memset (& inst, 0, sizeof (inst));
1517 inst.type = d->type1;
1519 if ((inst.size = d->size1) == 0)
1521 inst.size = TESTBUFSIZE;
1524 XD3_CHOOSE_INSTRUCTION (stream, NULL, & inst);
1526 if (inst.code2 != 0 || inst.code1 != i)
1528 stream->msg = "wrong single instruction";
1529 return XD3_INTERNAL;
1534 prev.type = d->type1;
1535 prev.size = d->size1;
1536 inst.type = d->type2;
1537 inst.size = d->size2;
1539 XD3_CHOOSE_INSTRUCTION (stream, & prev, & inst);
1541 if (prev.code2 != i)
1543 stream->msg = "wrong double instruction";
1544 return XD3_INTERNAL;
1552 /***********************************************************************
1554 ***********************************************************************/
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. */
1560 test_streaming (xd3_stream *in_stream, uint8_t *encbuf, uint8_t *decbuf, uint8_t *delbuf, usize_t megs)
1562 xd3_stream estream, dstream;
1564 usize_t i, delsize, decsize;
1566 xd3_init_config (& cfg, in_stream->flags);
1567 cfg.flags |= XD3_COMPLEVEL_6;
1569 if ((ret = xd3_config_stream (& estream, & cfg)) ||
1570 (ret = xd3_config_stream (& dstream, & cfg)))
1575 for (i = 0; i < megs; i += 1)
1577 ((usize_t*) encbuf)[0] = i;
1579 if ((i % 200) == 199) { DOT (); }
1581 if ((ret = xd3_process_stream (1, & estream, xd3_encode_input, 0,
1583 delbuf, & delsize, 1 << 20)))
1585 in_stream->msg = estream.msg;
1589 if ((ret = xd3_process_stream (0, & dstream, xd3_decode_input, 0,
1591 decbuf, & decsize, 1 << 20)))
1593 in_stream->msg = dstream.msg;
1597 if (decsize != 1 << 20 ||
1598 memcmp (encbuf, decbuf, 1 << 20) != 0)
1600 in_stream->msg = "wrong result";
1606 if ((ret = xd3_close_stream (& estream)) ||
1607 (ret = xd3_close_stream (& dstream)))
1613 xd3_free_stream (& estream);
1614 xd3_free_stream (& dstream);
1618 /* Run tests of data streaming of over and around 4GB of data. */
1620 test_compressed_stream_overflow (xd3_stream *stream, int ignore)
1626 if ((buf = (uint8_t*) malloc (TWO_MEGS_AND_DELTA)) == NULL) { return ENOMEM; }
1628 memset (buf, 0, TWO_MEGS_AND_DELTA);
1629 for (i = 0; i < (2 << 20); i += 256)
1632 int off = mt_random(& static_mtrand) % 10;
1633 for (j = 0; j < 256; j++)
1635 buf[i + j] = j + off;
1639 /* Test overflow of a 32-bit file offset. */
1640 if (SIZEOF_XOFF_T == 4)
1642 ret = test_streaming (stream, buf, buf + (1 << 20), buf + (2 << 20), (1 << 12) + 1);
1644 if (ret == XD3_INVALID_INPUT && MSG_IS ("decoder file offset overflow"))
1650 XPR(NT XD3_LIB_ERRMSG (stream, ret));
1651 stream->msg = "expected overflow condition";
1657 /* Test transfer of exactly 32bits worth of data. */
1658 if ((ret = test_streaming (stream,
1671 /***********************************************************************
1673 ***********************************************************************/
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
1684 test_command_line_arguments (xd3_stream *stream, int ignore)
1688 static const char* cmdpairs[] =
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",
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",
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",
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",
1712 char ecmd[TESTBUFSIZE], dcmd[TESTBUFSIZE];
1713 int pairs = SIZEOF_ARRAY (cmdpairs) / 2;
1718 mt_init (& static_mtrand, 0x9f73f7fc);
1720 for (i = 0; i < pairs; i += 1)
1723 if ((ret = test_make_inputs (stream, NULL, & tsize))) { return ret; }
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);
1730 /* Encode and decode. */
1731 if ((ret = system (ecmd)) != 0)
1733 XPR(NT "encode command: %s\n", ecmd);
1734 stream->msg = "encode cmd failed";
1735 return XD3_INTERNAL;
1738 if ((ret = system (dcmd)) != 0)
1740 XPR(NT "decode command: %s\n", dcmd);
1741 stream->msg = "decode cmd failed";
1742 return XD3_INTERNAL;
1745 /* Compare the target file. */
1746 if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_RECON_FILE)))
1751 if ((ret = test_file_size (TEST_DELTA_FILE, & dsize)))
1756 ratio = (double) dsize / (double) tsize;
1758 /* Check that it is not too small, not too large. */
1759 if (ratio >= TEST_ADD_RATIO + TEST_EPSILON)
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;
1768 if (ratio <= TEST_ADD_RATIO * (1.0 - 2 * TEST_EPSILON))
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;
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)
1782 stream->msg = "broken test_compare_files";
1783 return XD3_INTERNAL;
1794 check_vcdiff_header (xd3_stream *stream,
1796 const char *line_start,
1797 const char *matches,
1801 char vcmd[TESTBUFSIZE], gcmd[TESTBUFSIZE];
1803 snprintf_func (vcmd, TESTBUFSIZE, "%s printhdr -f %s %s",
1804 program_name, input, TEST_RECON2_FILE);
1806 if ((ret = system (vcmd)) != 0)
1808 XPR(NT "printhdr command: %s\n", vcmd);
1809 stream->msg = "printhdr cmd failed";
1810 return XD3_INTERNAL;
1813 snprintf_func (gcmd, TESTBUFSIZE, "grep \"%s.*%s.*\" %s > /dev/null",
1814 line_start, matches, TEST_RECON2_FILE);
1818 if ((ret = do_cmd (stream, gcmd)))
1820 XPR(NT "%s\n", gcmd);
1826 if ((ret = do_fail (stream, gcmd)))
1828 XPR(NT "%s\n", gcmd);
1837 test_recode_command2 (xd3_stream *stream, int has_source,
1838 int variant, int change)
1840 int has_adler32 = (variant & 0x1) != 0;
1841 int has_apphead = (variant & 0x2) != 0;
1842 int has_secondary = (variant & 0x4) != 0;
1844 int change_adler32 = (change & 0x1) != 0;
1845 int change_apphead = (change & 0x2) != 0;
1846 int change_secondary = (change & 0x4) != 0;
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;
1852 char ecmd[TESTBUFSIZE], recmd[TESTBUFSIZE], dcmd[TESTBUFSIZE];
1853 xoff_t tsize, ssize;
1858 if ((ret = test_make_inputs (stream, has_source ? & ssize : NULL, & tsize)))
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 : "",
1874 if ((ret = system (ecmd)) != 0)
1876 XPR(NT "encode command: %s\n", ecmd);
1877 stream->msg = "encode cmd failed";
1878 return XD3_INTERNAL;
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 ",
1891 if ((ret = system (recmd)) != 0)
1893 XPR(NT "recode command: %s\n", recmd);
1894 stream->msg = "recode cmd failed";
1895 return XD3_INTERNAL;
1898 /* Check recode changes. */
1900 if ((ret = check_vcdiff_header (stream,
1902 "VCDIFF window indicator",
1904 has_source))) { return ret; }
1906 if ((ret = check_vcdiff_header (stream,
1908 "VCDIFF header indicator",
1910 recoded_secondary))) { return ret; }
1912 if ((ret = check_vcdiff_header (stream,
1914 "VCDIFF window indicator",
1916 /* Recode can't generate an adler32
1917 * checksum, it can only preserve it or
1919 has_adler32 && recoded_adler32)))
1924 if (!change_apphead)
1926 if ((ret = check_vcdiff_header (stream,
1928 "VCDIFF header indicator",
1934 if ((ret = check_vcdiff_header (stream,
1936 "VCDIFF application header",
1945 if ((ret = check_vcdiff_header (stream,
1947 "VCDIFF header indicator",
1953 if (recoded_apphead &&
1954 (ret = check_vcdiff_header (stream,
1956 "VCDIFF application header",
1965 snprintf_func (dcmd, TESTBUFSIZE, "%s -fd %s %s %s %s ", program_name,
1966 has_source ? "-s " : "",
1967 has_source ? TEST_SOURCE_FILE : "",
1971 if ((ret = system (dcmd)) != 0)
1973 XPR(NT "decode command: %s\n", dcmd);
1974 stream->msg = "decode cmd failed";
1975 return XD3_INTERNAL;
1979 if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_RECON_FILE)))
1988 test_recode_command (xd3_stream *stream, int ignore)
1991 * - with and without a source file (recode does not change)
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
2003 for (has_source = 0; has_source < 2; has_source++)
2005 for (variant = 0; variant < 8; variant++)
2007 for (change = 0; change < 8; change++)
2009 if ((ret = test_recode_command2 (stream, has_source,
2023 /***********************************************************************
2024 EXTERNAL I/O DECOMPRESSION/RECOMPRESSION
2025 ***********************************************************************/
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. */
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)
2038 char decomp_buf[TESTBUFSIZE];
2042 snprintf_func (decomp_buf, TESTBUFSIZE,
2043 " | %s %s", ext->decomp_cmdname, ext->decomp_options);
2050 snprintf_func (buf, TESTBUFSIZE, "%s %s < %s | %s %s | %s %s%s > %s",
2051 ext->recomp_cmdname, ext->recomp_options,
2053 program_name, comp_options,
2054 program_name, decomp_options,
2058 if ((ret = system (buf)) != 0)
2061 return XD3_INTERNAL;
2064 if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_RECON_FILE)))
2066 return XD3_INTERNAL;
2073 /* We want to test that a pipe such as:
2075 * --> | gzip -cf | xdelta3 -cf | xdelta3 -dcf | gzip -dcf | -->
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:
2084 * --> | gzip -cf | xdelta3 -cf | xdelta3 -Ddcf | -->
2086 * Finally we want to test that -D also disables input decompression:
2088 * --> | gzip -cf | xdelta3 -Dcf | xdelta3 -Ddcf | gzip -dcf | -->
2091 test_externally_compressed_io (xd3_stream *stream, int ignore)
2095 char buf[TESTBUFSIZE];
2097 mt_init (& static_mtrand, 0x9f73f7fc);
2099 if ((ret = test_make_inputs (stream, NULL, NULL))) { return ret; }
2101 for (i = 0; i < SIZEOF_ARRAY (extcomp_types); i += 1)
2103 main_extcomp *ext = & extcomp_types[i];
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);
2108 if ((ret = system (buf)) != 0)
2110 XPR(NT "%s=0", ext->recomp_cmdname);
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")))
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
2141 test_source_decompression (xd3_stream *stream, int ignore)
2144 char buf[TESTBUFSIZE];
2145 const main_extcomp *ext;
2148 mt_init (& static_mtrand, 0x9f73f7fc);
2151 if ((ret = test_make_inputs (stream, NULL, NULL))) { return ret; }
2154 if ((ext = main_get_compressor ("G")) == NULL)
2160 /* Save an uncompressed copy. */
2161 if ((ret = test_save_copy (TEST_TARGET_FILE))) { return ret; }
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; }
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; }
2178 /* Check that the compressed file is small (b/c inputs are
2180 if ((ret = test_file_size (TEST_DELTA_FILE, & dsize))) { return ret; }
2181 /* Deltas for identical files should be very small. */
2184 XPR(NT "external compression did not happen\n");
2185 stream->msg = "external compression did not happen";
2186 return XD3_INTERNAL;
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; }
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; }
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; }
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; }
2226 /***********************************************************************
2228 ***********************************************************************/
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). */
2234 test_force_behavior (xd3_stream *stream, int ignore)
2237 char buf[TESTBUFSIZE];
2239 /* Create empty target file */
2241 snprintf_func (buf, TESTBUFSIZE, "cp /dev/null %s", TEST_TARGET_FILE);
2242 if ((ret = do_cmd (stream, buf))) { return ret; }
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; }
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; }
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; }
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). */
2266 test_stdout_behavior (xd3_stream *stream, int ignore)
2269 char buf[TESTBUFSIZE];
2272 snprintf_func (buf, TESTBUFSIZE, "cp /dev/null %s", TEST_TARGET_FILE);
2273 if ((ret = do_cmd (stream, buf))) { return ret; }
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; }
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; }
2285 /* Without -c, decode writes to target file name, but it fails because the
2287 snprintf_func (buf, TESTBUFSIZE, "%s -q -d %s ", program_name, TEST_DELTA_FILE);
2288 if ((ret = do_fail (stream, buf))) { return ret; }
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; }
2298 /* This tests that the no-output flag (-J) works. */
2300 test_no_output (xd3_stream *stream, int ignore)
2303 char buf[TESTBUFSIZE];
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; }
2311 if ((ret = test_make_inputs (stream, NULL, NULL))) { return ret; }
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; }
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; }
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; }
2336 /* This tests that the default appheader works */
2338 test_appheader (xd3_stream *stream, int ignore)
2342 char buf[TESTBUFSIZE];
2343 char bogus[TESTBUFSIZE];
2344 xoff_t ssize, tsize;
2347 if ((ret = test_make_inputs (stream, &ssize, &tsize))) { return ret; }
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; }
2353 if ((ret = test_copy_to (program_name, TEST_RECON2_FILE))) { return ret; }
2355 snprintf_func (buf, TESTBUFSIZE, "chmod 0700 %s", TEST_RECON2_FILE);
2356 if ((ret = do_cmd (stream, buf))) { return ret; }
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; }
2361 if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_COPY_FILE)) == 0)
2363 return XD3_INVALID; // I.e., files are different!
2366 // Test that the target file is restored.
2367 snprintf_func (buf, TESTBUFSIZE, "(cd /tmp && %s -q -f -d %s)",
2370 if ((ret = do_cmd (stream, buf))) { return ret; }
2372 if ((ret = test_compare_files (TEST_TARGET_FILE, TEST_COPY_FILE)) != 0)
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)
2384 bogus[TESTBUFSIZE/2-1] = 0;
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; }
2391 snprintf_func (buf, TESTBUFSIZE, "(cd /tmp && %s -q -f -d %s)",
2394 if ((ret = do_cmd (stream, buf)) == 0)
2396 return XD3_INVALID; // Impossible
2398 if (!WIFEXITED(ret))
2400 return XD3_INVALID; // Must have crashed!
2406 /***********************************************************************
2407 Source identical optimization
2408 ***********************************************************************/
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. */
2415 test_identical_behavior (xd3_stream *stream, int ignore)
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)
2424 uint8_t buf[IDB_TGTSZ];
2425 uint8_t del[IDB_DELSZ];
2426 uint8_t rec[IDB_TGTSZ];
2429 int winstarts = 0, winfinishes = 0;
2430 usize_t delpos = 0, recsize;
2432 memset(&source, 0, sizeof(source));
2434 for (i = 0; i < IDB_TGTSZ; i += 1)
2436 buf[i] = (uint8_t) mt_random (&static_mtrand);
2439 stream->winsize = IDB_WINSZ;
2441 source.blksize = IDB_BLKSZ;
2443 source.curblk = NULL;
2444 source.curblkno = 0;
2446 if ((ret = xd3_set_source (stream, & source))) { goto fail; }
2448 /* Compute an delta between identical source and targets. */
2451 ret = xd3_encode_input (stream);
2453 if (ret == XD3_INPUT)
2455 xd3_avail_input (stream, buf + (IDB_WINSZ * nextencwin), IDB_WINSZ);
2460 if (ret == XD3_GETSRCBLK)
2462 source.curblkno = source.getblkno;
2463 source.onblk = IDB_BLKSZ;
2464 source.curblk = buf + source.getblkno * IDB_BLKSZ;
2468 if (ret == XD3_WINSTART)
2473 if (ret == XD3_WINFINISH)
2476 if (winfinishes == IDB_WINCNT)
2483 if (ret != XD3_OUTPUT) { goto fail; }
2485 CHECK(delpos + stream->avail_out <= IDB_DELSZ);
2487 memcpy (del + delpos, stream->next_out, stream->avail_out);
2489 delpos += stream->avail_out;
2491 xd3_consume_output (stream);
2494 CHECK(winfinishes == IDB_WINCNT);
2495 CHECK(winstarts == IDB_WINCNT);
2496 CHECK(nextencwin == IDB_WINCNT);
2499 memset(&source, 0, sizeof(source));
2500 source.blksize = IDB_TGTSZ;
2501 source.onblk = IDB_TGTSZ;
2502 source.curblk = buf;
2503 source.curblkno = 0;
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; }
2512 if ((ret = xd3_decode_stream (stream, del, delpos, rec, & recsize, IDB_TGTSZ))) { goto fail; }
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; }
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; });
2523 /* Check that no checksums were computed because the initial match
2525 IF_DEBUG (if (stream->large_ckcnt != 0) { stream->msg = "wrong checksum behavior"; goto fail; });
2532 /***********************************************************************
2533 String matching test
2534 ***********************************************************************/
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;
2544 } string_match_flags;
2546 struct _string_match_test
2553 static const string_match_test match_tests[] =
2556 { "1234567890", SM_NONE, "" },
2558 /* basic run, copy */
2559 { "11111111112323232323", SM_NONE, "R0/10 C12/8@10" },
2561 /* no run smaller than MIN_RUN=8 */
2562 { "1111111", SM_NONE, "C1/6@0" },
2563 { "11111111", SM_NONE, "R0/8" },
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 */
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" },
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" },
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" },
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" },
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" },
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" },
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 */
2604 test_string_matching (xd3_stream *stream, int ignore)
2609 char rbuf[TESTBUFSIZE];
2611 for (i = 0; i < SIZEOF_ARRAY (match_tests); i += 1)
2613 const string_match_test *test = & match_tests[i];
2615 usize_t len = (usize_t) strlen (test->input);
2617 xd3_free_stream (stream);
2618 xd3_init_config (& config, 0);
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;
2629 if ((ret = xd3_config_stream (stream, & config))) { return ret; }
2630 if ((ret = xd3_encode_init_full (stream))) { return ret; }
2632 xd3_avail_input (stream, (uint8_t*)test->input, len);
2634 if ((ret = stream->smatcher.string_match (stream))) { return ret; }
2637 while (! xd3_rlist_empty (& stream->iopt_used))
2639 xd3_rinst *inst = xd3_rlist_pop_front (& stream->iopt_used);
2643 case XD3_RUN: *rptr++ = 'R'; break;
2644 case XD3_CPY: *rptr++ = 'C'; break;
2648 snprintf_func (rptr, rbuf+TESTBUFSIZE-rptr, "%d/%d",
2649 inst->pos, inst->size);
2650 rptr += strlen (rptr);
2652 if (inst->type == XD3_CPY)
2655 snprintf_func (rptr, rbuf+TESTBUFSIZE-rptr, "%"Q"d", inst->addr);
2656 rptr += strlen (rptr);
2661 xd3_rlist_push_back (& stream->iopt_free, inst);
2666 rptr -= 1; *rptr = 0;
2669 if (strcmp (rbuf, test->result) != 0)
2671 XPR(NT "test %u: expected %s: got %s", i, test->result, rbuf);
2672 stream->msg = "wrong result";
2673 return XD3_INTERNAL;
2681 * This is a test for many overlapping instructions. It must be a lazy
2685 test_iopt_flush_instructions (xd3_stream *stream, int ignore)
2689 usize_t delta_size, recon_size;
2691 uint8_t target[TESTBUFSIZE];
2692 uint8_t delta[TESTBUFSIZE];
2693 uint8_t recon[TESTBUFSIZE];
2695 xd3_free_stream (stream);
2696 xd3_init_config (& config, 0);
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;
2707 if ((ret = xd3_config_stream (stream, & config))) { return ret; }
2709 for (i = 1; i < 250; i++)
2712 target[tpos++] = i+1;
2713 target[tpos++] = i+2;
2714 target[tpos++] = i+3;
2717 for (i = 1; i < 253; i++)
2722 if ((ret = xd3_encode_stream (stream, target, tpos,
2723 delta, & delta_size, sizeof (delta))))
2728 xd3_free_stream(stream);
2729 if ((ret = xd3_config_stream (stream, & config))) { return ret; }
2731 if ((ret = xd3_decode_stream (stream, delta, delta_size,
2732 recon, & recon_size, sizeof (recon))))
2737 CHECK(tpos == recon_size);
2738 CHECK(memcmp(target, recon, recon_size) == 0);
2744 * This tests the 32/64bit ambiguity for source-window matching.
2747 test_source_cksum_offset (xd3_stream *stream, int ignore)
2753 xoff_t cpos; // stream->srcwin_cksum_pos;
2754 xoff_t ipos; // stream->total_in;
2755 xoff_t size; // stream->src->size;
2757 usize_t input; // input 32-bit offset
2758 xoff_t output; // output 64-bit offset
2761 // If cpos is <= 2^32
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 },
2770 { 0x100200000ULL, 0x100100000ULL, 0x100200000ULL, 0x00300000UL, 0x000300000ULL },
2772 { 25771983104ULL, 25770000000ULL, 26414808769ULL, 2139216707UL, 23614053187ULL },
2779 stream->src = &source;
2781 for (test_ptr = cksum_test; test_ptr->cpos; test_ptr++) {
2783 stream->srcwin_cksum_pos = test_ptr->cpos;
2784 stream->total_in = test_ptr->ipos;
2786 r = xd3_source_cksum_offset(stream, test_ptr->input);
2787 CHECK(r == test_ptr->output);
2793 test_in_memory (xd3_stream *stream, int ignore)
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;
2802 int eflags = SECONDARY_DJW ? XD3_SEC_DJW : 0;
2804 memcpy(ibuf, test_text, size);
2805 memset(ibuf + 128, 0, 16);
2807 r1 = xd3_encode_memory(ibuf, size,
2809 dbuf, &dsize, size, eflags);
2811 r2 = xd3_decode_memory(dbuf, dsize,
2813 obuf, &osize, size, 0);
2815 if (r1 != 0 || r2 != 0 || dsize >= (size/2) || dsize < 1 ||
2817 stream->msg = "encode/decode size error";
2818 return XD3_INTERNAL;
2821 if (memcmp(obuf, ibuf, size) != 0) {
2822 stream->msg = "encode/decode data error";
2823 return XD3_INTERNAL;
2829 /***********************************************************************
2831 ***********************************************************************/
2836 #define DO_TEST(fn,flags,arg) \
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"); \
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; } \
2854 DO_TEST (random_numbers, 0, 0);
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);
2863 DO_TEST (address_cache, 0, 0);
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);
2870 DO_TEST (iopt_flush_instructions, 0, 0);
2871 DO_TEST (source_cksum_offset, 0, 0);
2873 DO_TEST (decompress_single_bit_error, 0, 3);
2874 DO_TEST (decompress_single_bit_error, XD3_ADLER32, 3);
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));
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);
2887 #if EXTERNAL_COMPRESSION
2888 DO_TEST (source_decompression, 0, 0);
2889 DO_TEST (externally_compressed_io, 0, 0);
2892 DO_TEST (recode_command, 0, 0);
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));
2899 DO_TEST (compressed_stream_overflow, 0, 0);
2900 IF_LZMA (DO_TEST (compressed_stream_overflow, XD3_SEC_LZMA, 0));
2904 return ret == 0 ? EXIT_SUCCESS : EXIT_FAILURE;