xdelta3-3.0.11.tar.gz: xdelta3-3.0.11/xdelta3-test.h

"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.0.11/xdelta3-test.h" (11 Nov 2015, 79629 Bytes) of package /linux/misc/xdelta3-3.0.11.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "xdelta3-test.h" see the Fossies "Dox" file reference documentation.

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