1 /*- 2 * Copyright (c) 2010-2012 Michihiro NAKAJIMA 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR 15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 17 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT, 18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include "archive_platform.h" 27 28 #ifdef HAVE_ERRNO_H 29 #include <errno.h> 30 #endif 31 #ifdef HAVE_LIMITS_H 32 #include <limits.h> 33 #endif 34 #ifdef HAVE_STDLIB_H 35 #include <stdlib.h> 36 #endif 37 #ifdef HAVE_STRING_H 38 #include <string.h> 39 #endif 40 #ifdef HAVE_ZLIB_H 41 #include <zlib.h> 42 #endif 43 44 #include "archive.h" 45 #include "archive_entry.h" 46 #include "archive_entry_locale.h" 47 #include "archive_private.h" 48 #include "archive_read_private.h" 49 #include "archive_endian.h" 50 51 52 struct lzx_dec { 53 /* Decoding status. */ 54 int state; 55 56 /* 57 * Window to see last decoded data, from 32KBi to 2MBi. 58 */ 59 int w_size; 60 int w_mask; 61 /* Window buffer, which is a loop buffer. */ 62 unsigned char *w_buff; 63 /* The insert position to the window. */ 64 int w_pos; 65 /* The position where we can copy decoded code from the window. */ 66 int copy_pos; 67 /* The length how many bytes we can copy decoded code from 68 * the window. */ 69 int copy_len; 70 /* Translation reversal for x86 proccessor CALL byte sequence(E8). 71 * This is used for LZX only. */ 72 uint32_t translation_size; 73 char translation; 74 char block_type; 75 #define VERBATIM_BLOCK 1 76 #define ALIGNED_OFFSET_BLOCK 2 77 #define UNCOMPRESSED_BLOCK 3 78 size_t block_size; 79 size_t block_bytes_avail; 80 /* Repeated offset. */ 81 int r0, r1, r2; 82 unsigned char rbytes[4]; 83 int rbytes_avail; 84 int length_header; 85 int position_slot; 86 int offset_bits; 87 88 struct lzx_pos_tbl { 89 int base; 90 int footer_bits; 91 } *pos_tbl; 92 /* 93 * Bit stream reader. 94 */ 95 struct lzx_br { 96 #define CACHE_TYPE uint64_t 97 #define CACHE_BITS (8 * sizeof(CACHE_TYPE)) 98 /* Cache buffer. */ 99 CACHE_TYPE cache_buffer; 100 /* Indicates how many bits avail in cache_buffer. */ 101 int cache_avail; 102 unsigned char odd; 103 char have_odd; 104 } br; 105 106 /* 107 * Huffman coding. 108 */ 109 struct huffman { 110 int len_size; 111 int freq[17]; 112 unsigned char *bitlen; 113 114 /* 115 * Use a index table. It's faster than searching a huffman 116 * coding tree, which is a binary tree. But a use of a large 117 * index table causes L1 cache read miss many times. 118 */ 119 #define HTBL_BITS 10 120 int max_bits; 121 int shift_bits; 122 int tbl_bits; 123 int tree_used; 124 int tree_avail; 125 /* Direct access table. */ 126 uint16_t *tbl; 127 /* Binary tree table for extra bits over the direct access. */ 128 struct htree_t { 129 uint16_t left; 130 uint16_t right; 131 } *tree; 132 } at, lt, mt, pt; 133 134 int loop; 135 int error; 136 }; 137 138 static const int slots[] = { 139 30, 32, 34, 36, 38, 42, 50, 66, 98, 162, 290 140 }; 141 #define SLOT_BASE 15 142 #define SLOT_MAX 21/*->25*/ 143 144 struct lzx_stream { 145 const unsigned char *next_in; 146 int64_t avail_in; 147 int64_t total_in; 148 unsigned char *next_out; 149 int64_t avail_out; 150 int64_t total_out; 151 struct lzx_dec *ds; 152 }; 153 154 /* 155 * Cabinet file definitions. 156 */ 157 /* CFHEADER offset */ 158 #define CFHEADER_signature 0 159 #define CFHEADER_cbCabinet 8 160 #define CFHEADER_coffFiles 16 161 #define CFHEADER_versionMinor 24 162 #define CFHEADER_versionMajor 25 163 #define CFHEADER_cFolders 26 164 #define CFHEADER_cFiles 28 165 #define CFHEADER_flags 30 166 #define CFHEADER_setID 32 167 #define CFHEADER_iCabinet 34 168 #define CFHEADER_cbCFHeader 36 169 #define CFHEADER_cbCFFolder 38 170 #define CFHEADER_cbCFData 39 171 172 /* CFFOLDER offset */ 173 #define CFFOLDER_coffCabStart 0 174 #define CFFOLDER_cCFData 4 175 #define CFFOLDER_typeCompress 6 176 #define CFFOLDER_abReserve 8 177 178 /* CFFILE offset */ 179 #define CFFILE_cbFile 0 180 #define CFFILE_uoffFolderStart 4 181 #define CFFILE_iFolder 8 182 #define CFFILE_date_time 10 183 #define CFFILE_attribs 14 184 185 /* CFDATA offset */ 186 #define CFDATA_csum 0 187 #define CFDATA_cbData 4 188 #define CFDATA_cbUncomp 6 189 190 static const char *compression_name[] = { 191 "NONE", 192 "MSZIP", 193 "Quantum", 194 "LZX", 195 }; 196 197 struct cfdata { 198 /* Sum value of this CFDATA. */ 199 uint32_t sum; 200 uint16_t compressed_size; 201 uint16_t compressed_bytes_remaining; 202 uint16_t uncompressed_size; 203 uint16_t uncompressed_bytes_remaining; 204 /* To know how many bytes we have decompressed. */ 205 uint16_t uncompressed_avail; 206 /* Offset from the beginning of compressed data of this CFDATA */ 207 uint16_t read_offset; 208 int64_t unconsumed; 209 /* To keep memory image of this CFDATA to compute the sum. */ 210 size_t memimage_size; 211 unsigned char *memimage; 212 /* Result of calculation of sum. */ 213 uint32_t sum_calculated; 214 unsigned char sum_extra[4]; 215 int sum_extra_avail; 216 const void *sum_ptr; 217 }; 218 219 struct cffolder { 220 uint32_t cfdata_offset_in_cab; 221 uint16_t cfdata_count; 222 uint16_t comptype; 223 #define COMPTYPE_NONE 0x0000 224 #define COMPTYPE_MSZIP 0x0001 225 #define COMPTYPE_QUANTUM 0x0002 226 #define COMPTYPE_LZX 0x0003 227 uint16_t compdata; 228 const char *compname; 229 /* At the time reading CFDATA */ 230 struct cfdata cfdata; 231 int cfdata_index; 232 /* Flags to mark progress of decompression. */ 233 char decompress_init; 234 }; 235 236 struct cffile { 237 uint32_t uncompressed_size; 238 uint32_t offset; 239 time_t mtime; 240 uint16_t folder; 241 #define iFoldCONTINUED_FROM_PREV 0xFFFD 242 #define iFoldCONTINUED_TO_NEXT 0xFFFE 243 #define iFoldCONTINUED_PREV_AND_NEXT 0xFFFF 244 unsigned char attr; 245 #define ATTR_RDONLY 0x01 246 #define ATTR_NAME_IS_UTF 0x80 247 struct archive_string pathname; 248 }; 249 250 struct cfheader { 251 /* Total bytes of all file size in a Cabinet. */ 252 uint32_t total_bytes; 253 uint32_t files_offset; 254 uint16_t folder_count; 255 uint16_t file_count; 256 uint16_t flags; 257 #define PREV_CABINET 0x0001 258 #define NEXT_CABINET 0x0002 259 #define RESERVE_PRESENT 0x0004 260 uint16_t setid; 261 uint16_t cabinet; 262 /* Version number. */ 263 unsigned char major; 264 unsigned char minor; 265 unsigned char cffolder; 266 unsigned char cfdata; 267 /* All folders in a cabinet. */ 268 struct cffolder *folder_array; 269 /* All files in a cabinet. */ 270 struct cffile *file_array; 271 int file_index; 272 }; 273 274 struct cab { 275 /* entry_bytes_remaining is the number of bytes we expect. */ 276 int64_t entry_offset; 277 int64_t entry_bytes_remaining; 278 int64_t entry_unconsumed; 279 int64_t entry_compressed_bytes_read; 280 int64_t entry_uncompressed_bytes_read; 281 struct cffolder *entry_cffolder; 282 struct cffile *entry_cffile; 283 struct cfdata *entry_cfdata; 284 285 /* Offset from beginning of a cabinet file. */ 286 int64_t cab_offset; 287 struct cfheader cfheader; 288 struct archive_wstring ws; 289 290 /* Flag to mark progress that an archive was read their first header.*/ 291 char found_header; 292 char end_of_archive; 293 char end_of_entry; 294 char end_of_entry_cleanup; 295 char read_data_invoked; 296 int64_t bytes_skipped; 297 298 unsigned char *uncompressed_buffer; 299 size_t uncompressed_buffer_size; 300 301 int init_default_conversion; 302 struct archive_string_conv *sconv; 303 struct archive_string_conv *sconv_default; 304 struct archive_string_conv *sconv_utf8; 305 char format_name[64]; 306 307 #ifdef HAVE_ZLIB_H 308 z_stream stream; 309 char stream_valid; 310 #endif 311 struct lzx_stream xstrm; 312 }; 313 314 static int archive_read_format_cab_bid(struct archive_read *, int); 315 static int archive_read_format_cab_options(struct archive_read *, 316 const char *, const char *); 317 static int archive_read_format_cab_read_header(struct archive_read *, 318 struct archive_entry *); 319 static int archive_read_format_cab_read_data(struct archive_read *, 320 const void **, size_t *, int64_t *); 321 static int archive_read_format_cab_read_data_skip(struct archive_read *); 322 static int archive_read_format_cab_cleanup(struct archive_read *); 323 324 static int cab_skip_sfx(struct archive_read *); 325 static time_t cab_dos_time(const unsigned char *); 326 static int cab_read_data(struct archive_read *, const void **, 327 size_t *, int64_t *); 328 static int cab_read_header(struct archive_read *); 329 static uint32_t cab_checksum_cfdata_4(const void *, size_t bytes, uint32_t); 330 static uint32_t cab_checksum_cfdata(const void *, size_t bytes, uint32_t); 331 static void cab_checksum_update(struct archive_read *, size_t); 332 static int cab_checksum_finish(struct archive_read *); 333 static int cab_next_cfdata(struct archive_read *); 334 static const void *cab_read_ahead_cfdata(struct archive_read *, ssize_t *); 335 static const void *cab_read_ahead_cfdata_none(struct archive_read *, ssize_t *); 336 static const void *cab_read_ahead_cfdata_deflate(struct archive_read *, 337 ssize_t *); 338 static const void *cab_read_ahead_cfdata_lzx(struct archive_read *, 339 ssize_t *); 340 static int64_t cab_consume_cfdata(struct archive_read *, int64_t); 341 static int64_t cab_minimum_consume_cfdata(struct archive_read *, int64_t); 342 static int lzx_decode_init(struct lzx_stream *, int); 343 static int lzx_read_blocks(struct lzx_stream *, int); 344 static int lzx_decode_blocks(struct lzx_stream *, int); 345 static void lzx_decode_free(struct lzx_stream *); 346 static void lzx_translation(struct lzx_stream *, void *, size_t, uint32_t); 347 static void lzx_cleanup_bitstream(struct lzx_stream *); 348 static int lzx_decode(struct lzx_stream *, int); 349 static int lzx_read_pre_tree(struct lzx_stream *); 350 static int lzx_read_bitlen(struct lzx_stream *, struct huffman *, int); 351 static int lzx_huffman_init(struct huffman *, size_t, int); 352 static void lzx_huffman_free(struct huffman *); 353 static int lzx_make_huffman_table(struct huffman *); 354 static inline int lzx_decode_huffman(struct huffman *, unsigned); 355 static int lzx_decode_huffman_tree(struct huffman *, unsigned, int); 356 357 358 int 359 archive_read_support_format_cab(struct archive *_a) 360 { 361 struct archive_read *a = (struct archive_read *)_a; 362 struct cab *cab; 363 int r; 364 365 archive_check_magic(_a, ARCHIVE_READ_MAGIC, 366 ARCHIVE_STATE_NEW, "archive_read_support_format_cab"); 367 368 cab = (struct cab *)calloc(1, sizeof(*cab)); 369 if (cab == NULL) { 370 archive_set_error(&a->archive, ENOMEM, 371 "Can't allocate CAB data"); 372 return (ARCHIVE_FATAL); 373 } 374 archive_string_init(&cab->ws); 375 archive_wstring_ensure(&cab->ws, 256); 376 377 r = __archive_read_register_format(a, 378 cab, 379 "cab", 380 archive_read_format_cab_bid, 381 archive_read_format_cab_options, 382 archive_read_format_cab_read_header, 383 archive_read_format_cab_read_data, 384 archive_read_format_cab_read_data_skip, 385 NULL, 386 archive_read_format_cab_cleanup, 387 NULL, 388 NULL); 389 390 if (r != ARCHIVE_OK) 391 free(cab); 392 return (ARCHIVE_OK); 393 } 394 395 static int 396 find_cab_magic(const char *p) 397 { 398 switch (p[4]) { 399 case 0: 400 /* 401 * Note: Self-Extraction program has 'MSCF' string in their 402 * program. If we were finding 'MSCF' string only, we got 403 * wrong place for Cabinet header, thus, we have to check 404 * following four bytes which are reserved and must be set 405 * to zero. 406 */ 407 if (memcmp(p, "MSCF\0\0\0\0", 8) == 0) 408 return 0; 409 return 5; 410 case 'F': return 1; 411 case 'C': return 2; 412 case 'S': return 3; 413 case 'M': return 4; 414 default: return 5; 415 } 416 } 417 418 static int 419 archive_read_format_cab_bid(struct archive_read *a, int best_bid) 420 { 421 const char *p; 422 ssize_t bytes_avail, offset, window; 423 424 /* If there's already a better bid than we can ever 425 make, don't bother testing. */ 426 if (best_bid > 64) 427 return (-1); 428 429 if ((p = __archive_read_ahead(a, 8, NULL)) == NULL) 430 return (-1); 431 432 if (memcmp(p, "MSCF\0\0\0\0", 8) == 0) 433 return (64); 434 435 /* 436 * Attempt to handle self-extracting archives 437 * by noting a PE header and searching forward 438 * up to 128k for a 'MSCF' marker. 439 */ 440 if (p[0] == 'M' && p[1] == 'Z') { 441 offset = 0; 442 window = 4096; 443 while (offset < (1024 * 128)) { 444 const char *h = __archive_read_ahead(a, offset + window, 445 &bytes_avail); 446 if (h == NULL) { 447 /* Remaining bytes are less than window. */ 448 window >>= 1; 449 if (window < 128) 450 return (0); 451 continue; 452 } 453 p = h + offset; 454 while (p + 8 < h + bytes_avail) { 455 int next; 456 if ((next = find_cab_magic(p)) == 0) 457 return (64); 458 p += next; 459 } 460 offset = p - h; 461 } 462 } 463 return (0); 464 } 465 466 static int 467 archive_read_format_cab_options(struct archive_read *a, 468 const char *key, const char *val) 469 { 470 struct cab *cab; 471 int ret = ARCHIVE_FAILED; 472 473 cab = (struct cab *)(a->format->data); 474 if (strcmp(key, "hdrcharset") == 0) { 475 if (val == NULL || val[0] == 0) 476 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 477 "cab: hdrcharset option needs a character-set name"); 478 else { 479 cab->sconv = archive_string_conversion_from_charset( 480 &a->archive, val, 0); 481 if (cab->sconv != NULL) 482 ret = ARCHIVE_OK; 483 else 484 ret = ARCHIVE_FATAL; 485 } 486 return (ret); 487 } 488 489 /* Note: The "warn" return is just to inform the options 490 * supervisor that we didn't handle it. It will generate 491 * a suitable error if no one used this option. */ 492 return (ARCHIVE_WARN); 493 } 494 495 static int 496 cab_skip_sfx(struct archive_read *a) 497 { 498 const char *p, *q; 499 size_t skip; 500 ssize_t bytes, window; 501 502 window = 4096; 503 for (;;) { 504 const char *h = __archive_read_ahead(a, window, &bytes); 505 if (h == NULL) { 506 /* Remaining size are less than window. */ 507 window >>= 1; 508 if (window < 128) { 509 archive_set_error(&a->archive, 510 ARCHIVE_ERRNO_FILE_FORMAT, 511 "Couldn't find out CAB header"); 512 return (ARCHIVE_FATAL); 513 } 514 continue; 515 } 516 p = h; 517 q = p + bytes; 518 519 /* 520 * Scan ahead until we find something that looks 521 * like the cab header. 522 */ 523 while (p + 8 < q) { 524 int next; 525 if ((next = find_cab_magic(p)) == 0) { 526 skip = p - h; 527 __archive_read_consume(a, skip); 528 return (ARCHIVE_OK); 529 } 530 p += next; 531 } 532 skip = p - h; 533 __archive_read_consume(a, skip); 534 } 535 } 536 537 static int 538 truncated_error(struct archive_read *a) 539 { 540 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT, 541 "Truncated CAB header"); 542 return (ARCHIVE_FATAL); 543 } 544 545 static ssize_t 546 cab_strnlen(const unsigned char *p, size_t maxlen) 547 { 548 size_t i; 549 550 for (i = 0; i <= maxlen; i++) { 551 if (p[i] == 0) 552 break; 553 } 554 if (i > maxlen) 555 return (-1);/* invalid */ 556 return ((ssize_t)i); 557 } 558 559 /* Read bytes as much as remaining. */ 560 static const void * 561 cab_read_ahead_remaining(struct archive_read *a, size_t min, ssize_t *avail) 562 { 563 const void *p; 564 565 while (min > 0) { 566 p = __archive_read_ahead(a, min, avail); 567 if (p != NULL) 568 return (p); 569 min--; 570 } 571 return (NULL); 572 } 573 574 /* Convert a path separator '\' -> '/' */ 575 static int 576 cab_convert_path_separator_1(struct archive_string *fn, unsigned char attr) 577 { 578 size_t i; 579 int mb; 580 581 /* Easy check if we have '\' in multi-byte string. */ 582 mb = 0; 583 for (i = 0; i < archive_strlen(fn); i++) { 584 if (fn->s[i] == '\\') { 585 if (mb) { 586 /* This may be second byte of multi-byte 587 * character. */ 588 break; 589 } 590 fn->s[i] = '/'; 591 mb = 0; 592 } else if ((fn->s[i] & 0x80) && !(attr & ATTR_NAME_IS_UTF)) 593 mb = 1; 594 else 595 mb = 0; 596 } 597 if (i == archive_strlen(fn)) 598 return (0); 599 return (-1); 600 } 601 602 /* 603 * Replace a character '\' with '/' in wide character. 604 */ 605 static void 606 cab_convert_path_separator_2(struct cab *cab, struct archive_entry *entry) 607 { 608 const wchar_t *wp; 609 size_t i; 610 611 /* If a conversion to wide character failed, force the replacement. */ 612 if ((wp = archive_entry_pathname_w(entry)) != NULL) { 613 archive_wstrcpy(&(cab->ws), wp); 614 for (i = 0; i < archive_strlen(&(cab->ws)); i++) { 615 if (cab->ws.s[i] == L'\\') 616 cab->ws.s[i] = L'/'; 617 } 618 archive_entry_copy_pathname_w(entry, cab->ws.s); 619 } 620 } 621 622 /* 623 * Read CFHEADER, CFFOLDER and CFFILE. 624 */ 625 static int 626 cab_read_header(struct archive_read *a) 627 { 628 const unsigned char *p; 629 struct cab *cab; 630 struct cfheader *hd; 631 size_t bytes, used; 632 ssize_t len; 633 int64_t skip; 634 int err, i; 635 int cur_folder, prev_folder; 636 uint32_t offset32; 637 638 a->archive.archive_format = ARCHIVE_FORMAT_CAB; 639 if (a->archive.archive_format_name == NULL) 640 a->archive.archive_format_name = "CAB"; 641 642 if ((p = __archive_read_ahead(a, 42, NULL)) == NULL) 643 return (truncated_error(a)); 644 645 cab = (struct cab *)(a->format->data); 646 if (cab->found_header == 0 && 647 p[0] == 'M' && p[1] == 'Z') { 648 /* This is an executable? Must be self-extracting... */ 649 err = cab_skip_sfx(a); 650 if (err < ARCHIVE_WARN) 651 return (err); 652 653 if ((p = __archive_read_ahead(a, sizeof(*p), NULL)) == NULL) 654 return (truncated_error(a)); 655 } 656 657 cab->cab_offset = 0; 658 /* 659 * Read CFHEADER. 660 */ 661 hd = &cab->cfheader; 662 if (p[CFHEADER_signature+0] != 'M' || p[CFHEADER_signature+1] != 'S' || 663 p[CFHEADER_signature+2] != 'C' || p[CFHEADER_signature+3] != 'F') { 664 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT, 665 "Couldn't find out CAB header"); 666 return (ARCHIVE_FATAL); 667 } 668 hd->total_bytes = archive_le32dec(p + CFHEADER_cbCabinet); 669 hd->files_offset = archive_le32dec(p + CFHEADER_coffFiles); 670 hd->minor = p[CFHEADER_versionMinor]; 671 hd->major = p[CFHEADER_versionMajor]; 672 hd->folder_count = archive_le16dec(p + CFHEADER_cFolders); 673 if (hd->folder_count == 0) 674 goto invalid; 675 hd->file_count = archive_le16dec(p + CFHEADER_cFiles); 676 if (hd->file_count == 0) 677 goto invalid; 678 hd->flags = archive_le16dec(p + CFHEADER_flags); 679 hd->setid = archive_le16dec(p + CFHEADER_setID); 680 hd->cabinet = archive_le16dec(p + CFHEADER_iCabinet); 681 used = CFHEADER_iCabinet + 2; 682 if (hd->flags & RESERVE_PRESENT) { 683 uint16_t cfheader; 684 cfheader = archive_le16dec(p + CFHEADER_cbCFHeader); 685 if (cfheader > 60000U) 686 goto invalid; 687 hd->cffolder = p[CFHEADER_cbCFFolder]; 688 hd->cfdata = p[CFHEADER_cbCFData]; 689 used += 4;/* cbCFHeader, cbCFFolder and cbCFData */ 690 used += cfheader;/* abReserve */ 691 } else 692 hd->cffolder = 0;/* Avoid compiling warning. */ 693 if (hd->flags & PREV_CABINET) { 694 /* How many bytes are used for szCabinetPrev. */ 695 if ((p = __archive_read_ahead(a, used+256, NULL)) == NULL) 696 return (truncated_error(a)); 697 if ((len = cab_strnlen(p + used, 255)) <= 0) 698 goto invalid; 699 used += len + 1; 700 /* How many bytes are used for szDiskPrev. */ 701 if ((p = __archive_read_ahead(a, used+256, NULL)) == NULL) 702 return (truncated_error(a)); 703 if ((len = cab_strnlen(p + used, 255)) <= 0) 704 goto invalid; 705 used += len + 1; 706 } 707 if (hd->flags & NEXT_CABINET) { 708 /* How many bytes are used for szCabinetNext. */ 709 if ((p = __archive_read_ahead(a, used+256, NULL)) == NULL) 710 return (truncated_error(a)); 711 if ((len = cab_strnlen(p + used, 255)) <= 0) 712 goto invalid; 713 used += len + 1; 714 /* How many bytes are used for szDiskNext. */ 715 if ((p = __archive_read_ahead(a, used+256, NULL)) == NULL) 716 return (truncated_error(a)); 717 if ((len = cab_strnlen(p + used, 255)) <= 0) 718 goto invalid; 719 used += len + 1; 720 } 721 __archive_read_consume(a, used); 722 cab->cab_offset += used; 723 used = 0; 724 725 /* 726 * Read CFFOLDER. 727 */ 728 hd->folder_array = (struct cffolder *)calloc( 729 hd->folder_count, sizeof(struct cffolder)); 730 if (hd->folder_array == NULL) 731 goto nomem; 732 733 bytes = 8; 734 if (hd->flags & RESERVE_PRESENT) 735 bytes += hd->cffolder; 736 bytes *= hd->folder_count; 737 if ((p = __archive_read_ahead(a, bytes, NULL)) == NULL) 738 return (truncated_error(a)); 739 offset32 = 0; 740 for (i = 0; i < hd->folder_count; i++) { 741 struct cffolder *folder = &(hd->folder_array[i]); 742 folder->cfdata_offset_in_cab = 743 archive_le32dec(p + CFFOLDER_coffCabStart); 744 folder->cfdata_count = archive_le16dec(p+CFFOLDER_cCFData); 745 folder->comptype = 746 archive_le16dec(p+CFFOLDER_typeCompress) & 0x0F; 747 folder->compdata = 748 archive_le16dec(p+CFFOLDER_typeCompress) >> 8; 749 /* Get a compression name. */ 750 if (folder->comptype < 751 sizeof(compression_name) / sizeof(compression_name[0])) 752 folder->compname = compression_name[folder->comptype]; 753 else 754 folder->compname = "UNKNOWN"; 755 p += 8; 756 used += 8; 757 if (hd->flags & RESERVE_PRESENT) { 758 p += hd->cffolder;/* abReserve */ 759 used += hd->cffolder; 760 } 761 /* 762 * Sanity check if each data is acceptable. 763 */ 764 if (offset32 >= folder->cfdata_offset_in_cab) 765 goto invalid; 766 offset32 = folder->cfdata_offset_in_cab; 767 768 /* Set a request to initialize zlib for the CFDATA of 769 * this folder. */ 770 folder->decompress_init = 0; 771 } 772 __archive_read_consume(a, used); 773 cab->cab_offset += used; 774 775 /* 776 * Read CFFILE. 777 */ 778 /* Seek read pointer to the offset of CFFILE if needed. */ 779 skip = (int64_t)hd->files_offset - cab->cab_offset; 780 if (skip < 0) { 781 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 782 "Invalid offset of CFFILE %jd < %jd", 783 (intmax_t)hd->files_offset, (intmax_t)cab->cab_offset); 784 return (ARCHIVE_FATAL); 785 } 786 if (skip) { 787 __archive_read_consume(a, skip); 788 cab->cab_offset += skip; 789 } 790 /* Allocate memory for CFDATA */ 791 hd->file_array = (struct cffile *)calloc( 792 hd->file_count, sizeof(struct cffile)); 793 if (hd->file_array == NULL) 794 goto nomem; 795 796 prev_folder = -1; 797 for (i = 0; i < hd->file_count; i++) { 798 struct cffile *file = &(hd->file_array[i]); 799 ssize_t avail; 800 801 if ((p = __archive_read_ahead(a, 16, NULL)) == NULL) 802 return (truncated_error(a)); 803 file->uncompressed_size = archive_le32dec(p + CFFILE_cbFile); 804 file->offset = archive_le32dec(p + CFFILE_uoffFolderStart); 805 file->folder = archive_le16dec(p + CFFILE_iFolder); 806 file->mtime = cab_dos_time(p + CFFILE_date_time); 807 file->attr = (uint8_t)archive_le16dec(p + CFFILE_attribs); 808 __archive_read_consume(a, 16); 809 810 cab->cab_offset += 16; 811 if ((p = cab_read_ahead_remaining(a, 256, &avail)) == NULL) 812 return (truncated_error(a)); 813 if ((len = cab_strnlen(p, avail-1)) <= 0) 814 goto invalid; 815 816 /* Copy a pathname. */ 817 archive_string_init(&(file->pathname)); 818 archive_strncpy(&(file->pathname), p, len); 819 __archive_read_consume(a, len + 1); 820 cab->cab_offset += len + 1; 821 822 /* 823 * Sanity check if each data is acceptable. 824 */ 825 if (file->uncompressed_size > 0x7FFF8000) 826 goto invalid;/* Too large */ 827 if ((int64_t)file->offset + (int64_t)file->uncompressed_size 828 > ARCHIVE_LITERAL_LL(0x7FFF8000)) 829 goto invalid;/* Too large */ 830 switch (file->folder) { 831 case iFoldCONTINUED_TO_NEXT: 832 /* This must be last file in a folder. */ 833 if (i != hd->file_count -1) 834 goto invalid; 835 cur_folder = hd->folder_count -1; 836 break; 837 case iFoldCONTINUED_PREV_AND_NEXT: 838 /* This must be only one file in a folder. */ 839 if (hd->file_count != 1) 840 goto invalid; 841 /* FALL THROUGH */ 842 case iFoldCONTINUED_FROM_PREV: 843 /* This must be first file in a folder. */ 844 if (i != 0) 845 goto invalid; 846 prev_folder = cur_folder = 0; 847 offset32 = file->offset; 848 break; 849 default: 850 if (file->folder >= hd->folder_count) 851 goto invalid; 852 cur_folder = file->folder; 853 break; 854 } 855 /* Dot not back track. */ 856 if (cur_folder < prev_folder) 857 goto invalid; 858 if (cur_folder != prev_folder) 859 offset32 = 0; 860 prev_folder = cur_folder; 861 862 /* Make sure there are not any blanks from last file 863 * contents. */ 864 if (offset32 != file->offset) 865 goto invalid; 866 offset32 += file->uncompressed_size; 867 868 /* CFDATA is available for file contents. */ 869 if (file->uncompressed_size > 0 && 870 hd->folder_array[cur_folder].cfdata_count == 0) 871 goto invalid; 872 } 873 874 if (hd->cabinet != 0 || hd->flags & (PREV_CABINET | NEXT_CABINET)) { 875 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT, 876 "Multivolume cabinet file is unsupported"); 877 return (ARCHIVE_WARN); 878 } 879 return (ARCHIVE_OK); 880 invalid: 881 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT, 882 "Invalid CAB header"); 883 return (ARCHIVE_FATAL); 884 nomem: 885 archive_set_error(&a->archive, ENOMEM, 886 "Can't allocate memory for CAB data"); 887 return (ARCHIVE_FATAL); 888 } 889 890 static int 891 archive_read_format_cab_read_header(struct archive_read *a, 892 struct archive_entry *entry) 893 { 894 struct cab *cab; 895 struct cfheader *hd; 896 struct cffolder *prev_folder; 897 struct cffile *file; 898 struct archive_string_conv *sconv; 899 int err = ARCHIVE_OK, r; 900 901 cab = (struct cab *)(a->format->data); 902 if (cab->found_header == 0) { 903 err = cab_read_header(a); 904 if (err < ARCHIVE_WARN) 905 return (err); 906 /* We've found the header. */ 907 cab->found_header = 1; 908 } 909 hd = &cab->cfheader; 910 911 if (hd->file_index >= hd->file_count) { 912 cab->end_of_archive = 1; 913 return (ARCHIVE_EOF); 914 } 915 file = &hd->file_array[hd->file_index++]; 916 917 cab->end_of_entry = 0; 918 cab->end_of_entry_cleanup = 0; 919 cab->entry_compressed_bytes_read = 0; 920 cab->entry_uncompressed_bytes_read = 0; 921 cab->entry_unconsumed = 0; 922 cab->entry_cffile = file; 923 924 /* 925 * Choose a proper folder. 926 */ 927 prev_folder = cab->entry_cffolder; 928 switch (file->folder) { 929 case iFoldCONTINUED_FROM_PREV: 930 case iFoldCONTINUED_PREV_AND_NEXT: 931 cab->entry_cffolder = &hd->folder_array[0]; 932 break; 933 case iFoldCONTINUED_TO_NEXT: 934 cab->entry_cffolder = &hd->folder_array[hd->folder_count-1]; 935 break; 936 default: 937 cab->entry_cffolder = &hd->folder_array[file->folder]; 938 break; 939 } 940 /* If a cffolder of this file is changed, reset a cfdata to read 941 * file contents from next cfdata. */ 942 if (prev_folder != cab->entry_cffolder) 943 cab->entry_cfdata = NULL; 944 945 /* If a pathname is UTF-8, prepare a string conversion object 946 * for UTF-8 and use it. */ 947 if (file->attr & ATTR_NAME_IS_UTF) { 948 if (cab->sconv_utf8 == NULL) { 949 cab->sconv_utf8 = 950 archive_string_conversion_from_charset( 951 &(a->archive), "UTF-8", 1); 952 if (cab->sconv_utf8 == NULL) 953 return (ARCHIVE_FATAL); 954 } 955 sconv = cab->sconv_utf8; 956 } else if (cab->sconv != NULL) { 957 /* Choose the conversion specified by the option. */ 958 sconv = cab->sconv; 959 } else { 960 /* Choose the default conversion. */ 961 if (!cab->init_default_conversion) { 962 cab->sconv_default = 963 archive_string_default_conversion_for_read( 964 &(a->archive)); 965 cab->init_default_conversion = 1; 966 } 967 sconv = cab->sconv_default; 968 } 969 970 /* 971 * Set a default value and common data 972 */ 973 r = cab_convert_path_separator_1(&(file->pathname), file->attr); 974 if (archive_entry_copy_pathname_l(entry, file->pathname.s, 975 archive_strlen(&(file->pathname)), sconv) != 0) { 976 if (errno == ENOMEM) { 977 archive_set_error(&a->archive, ENOMEM, 978 "Can't allocate memory for Pathname"); 979 return (ARCHIVE_FATAL); 980 } 981 archive_set_error(&a->archive, 982 ARCHIVE_ERRNO_FILE_FORMAT, 983 "Pathname cannot be converted " 984 "from %s to current locale.", 985 archive_string_conversion_charset_name(sconv)); 986 err = ARCHIVE_WARN; 987 } 988 if (r < 0) { 989 /* Convert a path separator '\' -> '/' */ 990 cab_convert_path_separator_2(cab, entry); 991 } 992 993 archive_entry_set_size(entry, file->uncompressed_size); 994 if (file->attr & ATTR_RDONLY) 995 archive_entry_set_mode(entry, AE_IFREG | 0555); 996 else 997 archive_entry_set_mode(entry, AE_IFREG | 0666); 998 archive_entry_set_mtime(entry, file->mtime, 0); 999 1000 cab->entry_bytes_remaining = file->uncompressed_size; 1001 cab->entry_offset = 0; 1002 /* We don't need compress data. */ 1003 if (file->uncompressed_size == 0) 1004 cab->end_of_entry_cleanup = cab->end_of_entry = 1; 1005 1006 /* Set up a more descriptive format name. */ 1007 sprintf(cab->format_name, "CAB %d.%d (%s)", 1008 hd->major, hd->minor, cab->entry_cffolder->compname); 1009 a->archive.archive_format_name = cab->format_name; 1010 1011 return (err); 1012 } 1013 1014 static int 1015 archive_read_format_cab_read_data(struct archive_read *a, 1016 const void **buff, size_t *size, int64_t *offset) 1017 { 1018 struct cab *cab = (struct cab *)(a->format->data); 1019 int r; 1020 1021 switch (cab->entry_cffile->folder) { 1022 case iFoldCONTINUED_FROM_PREV: 1023 case iFoldCONTINUED_TO_NEXT: 1024 case iFoldCONTINUED_PREV_AND_NEXT: 1025 *buff = NULL; 1026 *size = 0; 1027 *offset = 0; 1028 archive_clear_error(&a->archive); 1029 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT, 1030 "Cannot restore this file split in multivolume."); 1031 return (ARCHIVE_FAILED); 1032 default: 1033 break; 1034 } 1035 if (cab->read_data_invoked == 0) { 1036 if (cab->bytes_skipped) { 1037 if (cab->entry_cfdata == NULL) { 1038 r = cab_next_cfdata(a); 1039 if (r < 0) 1040 return (r); 1041 } 1042 if (cab_consume_cfdata(a, cab->bytes_skipped) < 0) 1043 return (ARCHIVE_FATAL); 1044 cab->bytes_skipped = 0; 1045 } 1046 cab->read_data_invoked = 1; 1047 } 1048 if (cab->entry_unconsumed) { 1049 /* Consume as much as the compressor actually used. */ 1050 r = (int)cab_consume_cfdata(a, cab->entry_unconsumed); 1051 cab->entry_unconsumed = 0; 1052 if (r < 0) 1053 return (r); 1054 } 1055 if (cab->end_of_archive || cab->end_of_entry) { 1056 if (!cab->end_of_entry_cleanup) { 1057 /* End-of-entry cleanup done. */ 1058 cab->end_of_entry_cleanup = 1; 1059 } 1060 *offset = cab->entry_offset; 1061 *size = 0; 1062 *buff = NULL; 1063 return (ARCHIVE_EOF); 1064 } 1065 1066 return (cab_read_data(a, buff, size, offset)); 1067 } 1068 1069 static uint32_t 1070 cab_checksum_cfdata_4(const void *p, size_t bytes, uint32_t seed) 1071 { 1072 const unsigned char *b; 1073 unsigned u32num; 1074 uint32_t sum; 1075 1076 u32num = (unsigned)bytes / 4; 1077 sum = seed; 1078 b = p; 1079 for (;u32num > 0; --u32num) { 1080 sum ^= archive_le32dec(b); 1081 b += 4; 1082 } 1083 return (sum); 1084 } 1085 1086 static uint32_t 1087 cab_checksum_cfdata(const void *p, size_t bytes, uint32_t seed) 1088 { 1089 const unsigned char *b; 1090 uint32_t sum; 1091 uint32_t t; 1092 1093 sum = cab_checksum_cfdata_4(p, bytes, seed); 1094 b = p; 1095 b += bytes & ~3; 1096 t = 0; 1097 switch (bytes & 3) { 1098 case 3: 1099 t |= ((uint32_t)(*b++)) << 16; 1100 /* FALL THROUGH */ 1101 case 2: 1102 t |= ((uint32_t)(*b++)) << 8; 1103 /* FALL THROUGH */ 1104 case 1: 1105 t |= *b; 1106 /* FALL THROUGH */ 1107 default: 1108 break; 1109 } 1110 sum ^= t; 1111 1112 return (sum); 1113 } 1114 1115 static void 1116 cab_checksum_update(struct archive_read *a, size_t bytes) 1117 { 1118 struct cab *cab = (struct cab *)(a->format->data); 1119 struct cfdata *cfdata = cab->entry_cfdata; 1120 const unsigned char *p; 1121 size_t sumbytes; 1122 1123 if (cfdata->sum == 0 || cfdata->sum_ptr == NULL) 1124 return; 1125 /* 1126 * Calculate the sum of this CFDATA. 1127 * Make sure CFDATA must be calculated in four bytes. 1128 */ 1129 p = cfdata->sum_ptr; 1130 sumbytes = bytes; 1131 if (cfdata->sum_extra_avail) { 1132 while (cfdata->sum_extra_avail < 4 && sumbytes > 0) { 1133 cfdata->sum_extra[ 1134 cfdata->sum_extra_avail++] = *p++; 1135 sumbytes--; 1136 } 1137 if (cfdata->sum_extra_avail == 4) { 1138 cfdata->sum_calculated = cab_checksum_cfdata_4( 1139 cfdata->sum_extra, 4, cfdata->sum_calculated); 1140 cfdata->sum_extra_avail = 0; 1141 } 1142 } 1143 if (sumbytes) { 1144 int odd = sumbytes & 3; 1145 if (sumbytes - odd > 0) 1146 cfdata->sum_calculated = cab_checksum_cfdata_4( 1147 p, sumbytes - odd, cfdata->sum_calculated); 1148 if (odd) 1149 memcpy(cfdata->sum_extra, p + sumbytes - odd, odd); 1150 cfdata->sum_extra_avail = odd; 1151 } 1152 cfdata->sum_ptr = NULL; 1153 } 1154 1155 static int 1156 cab_checksum_finish(struct archive_read *a) 1157 { 1158 struct cab *cab = (struct cab *)(a->format->data); 1159 struct cfdata *cfdata = cab->entry_cfdata; 1160 int l; 1161 1162 /* Do not need to compute a sum. */ 1163 if (cfdata->sum == 0) 1164 return (ARCHIVE_OK); 1165 1166 /* 1167 * Calculate the sum of remaining CFDATA. 1168 */ 1169 if (cfdata->sum_extra_avail) { 1170 cfdata->sum_calculated = 1171 cab_checksum_cfdata(cfdata->sum_extra, 1172 cfdata->sum_extra_avail, cfdata->sum_calculated); 1173 cfdata->sum_extra_avail = 0; 1174 } 1175 1176 l = 4; 1177 if (cab->cfheader.flags & RESERVE_PRESENT) 1178 l += cab->cfheader.cfdata; 1179 cfdata->sum_calculated = cab_checksum_cfdata( 1180 cfdata->memimage + CFDATA_cbData, l, cfdata->sum_calculated); 1181 if (cfdata->sum_calculated != cfdata->sum) { 1182 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT, 1183 "Checksum error CFDATA[%d] %x:%x in %d bytes", 1184 cab->entry_cffolder->cfdata_index -1, 1185 cfdata->sum, cfdata->sum_calculated, 1186 cfdata->compressed_size); 1187 return (ARCHIVE_FAILED); 1188 } 1189 return (ARCHIVE_OK); 1190 } 1191 1192 /* 1193 * Read CFDATA if needed. 1194 */ 1195 static int 1196 cab_next_cfdata(struct archive_read *a) 1197 { 1198 struct cab *cab = (struct cab *)(a->format->data); 1199 struct cfdata *cfdata = cab->entry_cfdata; 1200 1201 /* There are remaining bytes in current CFDATA, use it first. */ 1202 if (cfdata != NULL && cfdata->uncompressed_bytes_remaining > 0) 1203 return (ARCHIVE_OK); 1204 1205 if (cfdata == NULL) { 1206 int64_t skip; 1207 1208 cab->entry_cffolder->cfdata_index = 0; 1209 1210 /* Seek read pointer to the offset of CFDATA if needed. */ 1211 skip = cab->entry_cffolder->cfdata_offset_in_cab 1212 - cab->cab_offset; 1213 if (skip < 0) { 1214 int folder_index; 1215 switch (cab->entry_cffile->folder) { 1216 case iFoldCONTINUED_FROM_PREV: 1217 case iFoldCONTINUED_PREV_AND_NEXT: 1218 folder_index = 0; 1219 break; 1220 case iFoldCONTINUED_TO_NEXT: 1221 folder_index = cab->cfheader.folder_count-1; 1222 break; 1223 default: 1224 folder_index = cab->entry_cffile->folder; 1225 break; 1226 } 1227 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 1228 "Invalid offset of CFDATA in folder(%d) %jd < %jd", 1229 folder_index, 1230 (intmax_t)cab->entry_cffolder->cfdata_offset_in_cab, 1231 (intmax_t)cab->cab_offset); 1232 return (ARCHIVE_FATAL); 1233 } 1234 if (skip > 0) { 1235 if (__archive_read_consume(a, skip) < 0) 1236 return (ARCHIVE_FATAL); 1237 cab->cab_offset = 1238 cab->entry_cffolder->cfdata_offset_in_cab; 1239 } 1240 } 1241 1242 /* 1243 * Read a CFDATA. 1244 */ 1245 if (cab->entry_cffolder->cfdata_index < 1246 cab->entry_cffolder->cfdata_count) { 1247 const unsigned char *p; 1248 int l; 1249 1250 cfdata = &(cab->entry_cffolder->cfdata); 1251 cab->entry_cffolder->cfdata_index++; 1252 cab->entry_cfdata = cfdata; 1253 cfdata->sum_calculated = 0; 1254 cfdata->sum_extra_avail = 0; 1255 cfdata->sum_ptr = NULL; 1256 l = 8; 1257 if (cab->cfheader.flags & RESERVE_PRESENT) 1258 l += cab->cfheader.cfdata; 1259 if ((p = __archive_read_ahead(a, l, NULL)) == NULL) 1260 return (truncated_error(a)); 1261 cfdata->sum = archive_le32dec(p + CFDATA_csum); 1262 cfdata->compressed_size = archive_le16dec(p + CFDATA_cbData); 1263 cfdata->compressed_bytes_remaining = cfdata->compressed_size; 1264 cfdata->uncompressed_size = 1265 archive_le16dec(p + CFDATA_cbUncomp); 1266 cfdata->uncompressed_bytes_remaining = 1267 cfdata->uncompressed_size; 1268 cfdata->uncompressed_avail = 0; 1269 cfdata->read_offset = 0; 1270 cfdata->unconsumed = 0; 1271 1272 /* 1273 * Sanity check if data size is acceptable. 1274 */ 1275 if (cfdata->compressed_size == 0 || 1276 cfdata->compressed_size > (0x8000+6144)) 1277 goto invalid; 1278 if (cfdata->uncompressed_size > 0x8000) 1279 goto invalid; 1280 if (cfdata->uncompressed_size == 0) { 1281 switch (cab->entry_cffile->folder) { 1282 case iFoldCONTINUED_PREV_AND_NEXT: 1283 case iFoldCONTINUED_TO_NEXT: 1284 break; 1285 case iFoldCONTINUED_FROM_PREV: 1286 default: 1287 goto invalid; 1288 } 1289 } 1290 /* If CFDATA is not last in a folder, an uncompressed 1291 * size must be 0x8000(32KBi) */ 1292 if ((cab->entry_cffolder->cfdata_index < 1293 cab->entry_cffolder->cfdata_count) && 1294 cfdata->uncompressed_size != 0x8000) 1295 goto invalid; 1296 1297 /* A compressed data size and an uncompressed data size must 1298 * be the same in no compression mode. */ 1299 if (cab->entry_cffolder->comptype == COMPTYPE_NONE && 1300 cfdata->compressed_size != cfdata->uncompressed_size) 1301 goto invalid; 1302 1303 /* 1304 * Save CFDATA image for sum check. 1305 */ 1306 if (cfdata->memimage_size < (size_t)l) { 1307 free(cfdata->memimage); 1308 cfdata->memimage = malloc(l); 1309 if (cfdata->memimage == NULL) { 1310 archive_set_error(&a->archive, ENOMEM, 1311 "Can't allocate memory for CAB data"); 1312 return (ARCHIVE_FATAL); 1313 } 1314 cfdata->memimage_size = l; 1315 } 1316 memcpy(cfdata->memimage, p, l); 1317 1318 /* Consume bytes as much as we used. */ 1319 __archive_read_consume(a, l); 1320 cab->cab_offset += l; 1321 } else if (cab->entry_cffolder->cfdata_count > 0) { 1322 /* Run out of all CFDATA in a folder. */ 1323 cfdata->compressed_size = 0; 1324 cfdata->uncompressed_size = 0; 1325 cfdata->compressed_bytes_remaining = 0; 1326 cfdata->uncompressed_bytes_remaining = 0; 1327 } else { 1328 /* Current folder does not have any CFDATA. */ 1329 cfdata = &(cab->entry_cffolder->cfdata); 1330 cab->entry_cfdata = cfdata; 1331 memset(cfdata, 0, sizeof(*cfdata)); 1332 } 1333 return (ARCHIVE_OK); 1334 invalid: 1335 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT, 1336 "Invalid CFDATA"); 1337 return (ARCHIVE_FATAL); 1338 } 1339 1340 /* 1341 * Read ahead CFDATA. 1342 */ 1343 static const void * 1344 cab_read_ahead_cfdata(struct archive_read *a, ssize_t *avail) 1345 { 1346 struct cab *cab = (struct cab *)(a->format->data); 1347 int err; 1348 1349 err = cab_next_cfdata(a); 1350 if (err < ARCHIVE_OK) { 1351 *avail = err; 1352 return (NULL); 1353 } 1354 1355 switch (cab->entry_cffolder->comptype) { 1356 case COMPTYPE_NONE: 1357 return (cab_read_ahead_cfdata_none(a, avail)); 1358 case COMPTYPE_MSZIP: 1359 return (cab_read_ahead_cfdata_deflate(a, avail)); 1360 case COMPTYPE_LZX: 1361 return (cab_read_ahead_cfdata_lzx(a, avail)); 1362 default: /* Unsupported compression. */ 1363 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT, 1364 "Unsupported CAB compression : %s", 1365 cab->entry_cffolder->compname); 1366 *avail = ARCHIVE_FAILED; 1367 return (NULL); 1368 } 1369 } 1370 1371 /* 1372 * Read ahead CFDATA as uncompressed data. 1373 */ 1374 static const void * 1375 cab_read_ahead_cfdata_none(struct archive_read *a, ssize_t *avail) 1376 { 1377 struct cab *cab = (struct cab *)(a->format->data); 1378 struct cfdata *cfdata; 1379 const void *d; 1380 1381 cfdata = cab->entry_cfdata; 1382 1383 /* 1384 * Note: '1' here is a performance optimization. 1385 * Recall that the decompression layer returns a count of 1386 * available bytes; asking for more than that forces the 1387 * decompressor to combine reads by copying data. 1388 */ 1389 d = __archive_read_ahead(a, 1, avail); 1390 if (*avail <= 0) { 1391 *avail = truncated_error(a); 1392 return (NULL); 1393 } 1394 if (*avail > cfdata->uncompressed_bytes_remaining) 1395 *avail = cfdata->uncompressed_bytes_remaining; 1396 cfdata->uncompressed_avail = cfdata->uncompressed_size; 1397 cfdata->unconsumed = *avail; 1398 cfdata->sum_ptr = d; 1399 return (d); 1400 } 1401 1402 /* 1403 * Read ahead CFDATA as deflate data. 1404 */ 1405 #ifdef HAVE_ZLIB_H 1406 static const void * 1407 cab_read_ahead_cfdata_deflate(struct archive_read *a, ssize_t *avail) 1408 { 1409 struct cab *cab = (struct cab *)(a->format->data); 1410 struct cfdata *cfdata; 1411 const void *d; 1412 int r, mszip; 1413 uint16_t uavail; 1414 char eod = 0; 1415 1416 cfdata = cab->entry_cfdata; 1417 /* If the buffer hasn't been allocated, allocate it now. */ 1418 if (cab->uncompressed_buffer == NULL) { 1419 cab->uncompressed_buffer_size = 0x8000; 1420 cab->uncompressed_buffer 1421 = (unsigned char *)malloc(cab->uncompressed_buffer_size); 1422 if (cab->uncompressed_buffer == NULL) { 1423 archive_set_error(&a->archive, ENOMEM, 1424 "No memory for CAB reader"); 1425 *avail = ARCHIVE_FATAL; 1426 return (NULL); 1427 } 1428 } 1429 1430 uavail = cfdata->uncompressed_avail; 1431 if (uavail == cfdata->uncompressed_size) { 1432 d = cab->uncompressed_buffer + cfdata->read_offset; 1433 *avail = uavail - cfdata->read_offset; 1434 return (d); 1435 } 1436 1437 if (!cab->entry_cffolder->decompress_init) { 1438 cab->stream.next_in = NULL; 1439 cab->stream.avail_in = 0; 1440 cab->stream.total_in = 0; 1441 cab->stream.next_out = NULL; 1442 cab->stream.avail_out = 0; 1443 cab->stream.total_out = 0; 1444 if (cab->stream_valid) 1445 r = inflateReset(&cab->stream); 1446 else 1447 r = inflateInit2(&cab->stream, 1448 -15 /* Don't check for zlib header */); 1449 if (r != Z_OK) { 1450 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 1451 "Can't initialize deflate decompression."); 1452 *avail = ARCHIVE_FATAL; 1453 return (NULL); 1454 } 1455 /* Stream structure has been set up. */ 1456 cab->stream_valid = 1; 1457 /* We've initialized decompression for this stream. */ 1458 cab->entry_cffolder->decompress_init = 1; 1459 } 1460 1461 if (cfdata->compressed_bytes_remaining == cfdata->compressed_size) 1462 mszip = 2; 1463 else 1464 mszip = 0; 1465 eod = 0; 1466 cab->stream.total_out = uavail; 1467 /* 1468 * We always uncompress all data in current CFDATA. 1469 */ 1470 while (!eod && cab->stream.total_out < cfdata->uncompressed_size) { 1471 ssize_t bytes_avail; 1472 1473 cab->stream.next_out = 1474 cab->uncompressed_buffer + cab->stream.total_out; 1475 cab->stream.avail_out = 1476 cfdata->uncompressed_size - cab->stream.total_out; 1477 1478 d = __archive_read_ahead(a, 1, &bytes_avail); 1479 if (bytes_avail <= 0) { 1480 *avail = truncated_error(a); 1481 return (NULL); 1482 } 1483 if (bytes_avail > cfdata->compressed_bytes_remaining) 1484 bytes_avail = cfdata->compressed_bytes_remaining; 1485 /* 1486 * A bug in zlib.h: stream.next_in should be marked 'const' 1487 * but isn't (the library never alters data through the 1488 * next_in pointer, only reads it). The result: this ugly 1489 * cast to remove 'const'. 1490 */ 1491 cab->stream.next_in = (Bytef *)(uintptr_t)d; 1492 cab->stream.avail_in = (uInt)bytes_avail; 1493 cab->stream.total_in = 0; 1494 1495 /* Cut out a tow-byte MSZIP signature(0x43, 0x4b). */ 1496 if (mszip > 0) { 1497 if (bytes_avail <= mszip) { 1498 if (mszip == 2) { 1499 if (cab->stream.next_in[0] != 0x43) 1500 goto nomszip; 1501 if (bytes_avail > 1 && 1502 cab->stream.next_in[1] != 0x4b) 1503 goto nomszip; 1504 } else if (cab->stream.next_in[0] != 0x4b) 1505 goto nomszip; 1506 cfdata->unconsumed = bytes_avail; 1507 cfdata->sum_ptr = d; 1508 if (cab_minimum_consume_cfdata( 1509 a, cfdata->unconsumed) < 0) { 1510 *avail = ARCHIVE_FATAL; 1511 return (NULL); 1512 } 1513 mszip -= (int)bytes_avail; 1514 continue; 1515 } 1516 if (mszip == 1 && cab->stream.next_in[0] != 0x4b) 1517 goto nomszip; 1518 else if (cab->stream.next_in[0] != 0x43 || 1519 cab->stream.next_in[1] != 0x4b) 1520 goto nomszip; 1521 cab->stream.next_in += mszip; 1522 cab->stream.avail_in -= mszip; 1523 cab->stream.total_in += mszip; 1524 mszip = 0; 1525 } 1526 1527 r = inflate(&cab->stream, 0); 1528 switch (r) { 1529 case Z_OK: 1530 break; 1531 case Z_STREAM_END: 1532 eod = 1; 1533 break; 1534 default: 1535 goto zlibfailed; 1536 } 1537 cfdata->unconsumed = cab->stream.total_in; 1538 cfdata->sum_ptr = d; 1539 if (cab_minimum_consume_cfdata(a, cfdata->unconsumed) < 0) { 1540 *avail = ARCHIVE_FATAL; 1541 return (NULL); 1542 } 1543 } 1544 uavail = (uint16_t)cab->stream.total_out; 1545 1546 if (uavail < cfdata->uncompressed_size) { 1547 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 1548 "Invalid uncompressed size (%d < %d)", 1549 uavail, cfdata->uncompressed_size); 1550 *avail = ARCHIVE_FATAL; 1551 return (NULL); 1552 } 1553 1554 /* 1555 * Note: I suspect there is a bug in makecab.exe because, in rare 1556 * case, compressed bytes are still remaining regardless we have 1557 * gotten all uncompressed bytes, which size is recoded in CFDATA, 1558 * as much as we need, and we have to use the garbage so as to 1559 * correctly compute the sum of CFDATA accordingly. 1560 */ 1561 if (cfdata->compressed_bytes_remaining > 0) { 1562 ssize_t bytes_avail; 1563 1564 d = __archive_read_ahead(a, cfdata->compressed_bytes_remaining, 1565 &bytes_avail); 1566 if (bytes_avail <= 0) { 1567 *avail = truncated_error(a); 1568 return (NULL); 1569 } 1570 cfdata->unconsumed = cfdata->compressed_bytes_remaining; 1571 cfdata->sum_ptr = d; 1572 if (cab_minimum_consume_cfdata(a, cfdata->unconsumed) < 0) { 1573 *avail = ARCHIVE_FATAL; 1574 return (NULL); 1575 } 1576 } 1577 1578 /* 1579 * Set dictionary data for decompressing of next CFDATA, which 1580 * in the same folder. This is why we always do decompress CFDATA 1581 * even if beginning CFDATA or some of CFDATA are not used in 1582 * skipping file data. 1583 */ 1584 if (cab->entry_cffolder->cfdata_index < 1585 cab->entry_cffolder->cfdata_count) { 1586 r = inflateReset(&cab->stream); 1587 if (r != Z_OK) 1588 goto zlibfailed; 1589 r = inflateSetDictionary(&cab->stream, 1590 cab->uncompressed_buffer, cfdata->uncompressed_size); 1591 if (r != Z_OK) 1592 goto zlibfailed; 1593 } 1594 1595 d = cab->uncompressed_buffer + cfdata->read_offset; 1596 *avail = uavail - cfdata->read_offset; 1597 cfdata->uncompressed_avail = uavail; 1598 1599 return (d); 1600 1601 zlibfailed: 1602 switch (r) { 1603 case Z_MEM_ERROR: 1604 archive_set_error(&a->archive, ENOMEM, 1605 "Out of memory for deflate decompression"); 1606 break; 1607 default: 1608 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 1609 "Deflate decompression failed (%d)", r); 1610 break; 1611 } 1612 *avail = ARCHIVE_FATAL; 1613 return (NULL); 1614 nomszip: 1615 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 1616 "CFDATA incorrect(no MSZIP signature)"); 1617 *avail = ARCHIVE_FATAL; 1618 return (NULL); 1619 } 1620 1621 #else /* HAVE_ZLIB_H */ 1622 1623 static const void * 1624 cab_read_ahead_cfdata_deflate(struct archive_read *a, ssize_t *avail) 1625 { 1626 *avail = ARCHIVE_FATAL; 1627 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 1628 "libarchive compiled without deflate support (no libz)"); 1629 return (NULL); 1630 } 1631 1632 #endif /* HAVE_ZLIB_H */ 1633 1634 static const void * 1635 cab_read_ahead_cfdata_lzx(struct archive_read *a, ssize_t *avail) 1636 { 1637 struct cab *cab = (struct cab *)(a->format->data); 1638 struct cfdata *cfdata; 1639 const void *d; 1640 int r; 1641 uint16_t uavail; 1642 1643 cfdata = cab->entry_cfdata; 1644 /* If the buffer hasn't been allocated, allocate it now. */ 1645 if (cab->uncompressed_buffer == NULL) { 1646 cab->uncompressed_buffer_size = 0x8000; 1647 cab->uncompressed_buffer 1648 = (unsigned char *)malloc(cab->uncompressed_buffer_size); 1649 if (cab->uncompressed_buffer == NULL) { 1650 archive_set_error(&a->archive, ENOMEM, 1651 "No memory for CAB reader"); 1652 *avail = ARCHIVE_FATAL; 1653 return (NULL); 1654 } 1655 } 1656 1657 uavail = cfdata->uncompressed_avail; 1658 if (uavail == cfdata->uncompressed_size) { 1659 d = cab->uncompressed_buffer + cfdata->read_offset; 1660 *avail = uavail - cfdata->read_offset; 1661 return (d); 1662 } 1663 1664 if (!cab->entry_cffolder->decompress_init) { 1665 r = lzx_decode_init(&cab->xstrm, 1666 cab->entry_cffolder->compdata); 1667 if (r != ARCHIVE_OK) { 1668 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 1669 "Can't initialize LZX decompression."); 1670 *avail = ARCHIVE_FATAL; 1671 return (NULL); 1672 } 1673 /* We've initialized decompression for this stream. */ 1674 cab->entry_cffolder->decompress_init = 1; 1675 } 1676 1677 /* Clean up remaining bits of previous CFDATA. */ 1678 lzx_cleanup_bitstream(&cab->xstrm); 1679 cab->xstrm.total_out = uavail; 1680 while (cab->xstrm.total_out < cfdata->uncompressed_size) { 1681 ssize_t bytes_avail; 1682 1683 cab->xstrm.next_out = 1684 cab->uncompressed_buffer + cab->xstrm.total_out; 1685 cab->xstrm.avail_out = 1686 cfdata->uncompressed_size - cab->xstrm.total_out; 1687 1688 d = __archive_read_ahead(a, 1, &bytes_avail); 1689 if (bytes_avail <= 0) { 1690 archive_set_error(&a->archive, 1691 ARCHIVE_ERRNO_FILE_FORMAT, 1692 "Truncated CAB file data"); 1693 *avail = ARCHIVE_FATAL; 1694 return (NULL); 1695 } 1696 if (bytes_avail > cfdata->compressed_bytes_remaining) 1697 bytes_avail = cfdata->compressed_bytes_remaining; 1698 1699 cab->xstrm.next_in = d; 1700 cab->xstrm.avail_in = bytes_avail; 1701 cab->xstrm.total_in = 0; 1702 r = lzx_decode(&cab->xstrm, 1703 cfdata->compressed_bytes_remaining == bytes_avail); 1704 switch (r) { 1705 case ARCHIVE_OK: 1706 case ARCHIVE_EOF: 1707 break; 1708 default: 1709 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC, 1710 "LZX decompression failed (%d)", r); 1711 *avail = ARCHIVE_FATAL; 1712 return (NULL); 1713 } 1714 cfdata->unconsumed = cab->xstrm.total_in; 1715 cfdata->sum_ptr = d; 1716 if (cab_minimum_consume_cfdata(a, cfdata->unconsumed) < 0) { 1717 *avail = ARCHIVE_FATAL; 1718 return (NULL); 1719 } 1720 } 1721 1722 uavail = (uint16_t)cab->xstrm.total_out; 1723 /* 1724 * Make sure a read pointer advances to next CFDATA. 1725 */ 1726 if (cfdata->compressed_bytes_remaining > 0) { 1727 ssize_t bytes_avail; 1728 1729 d = __archive_read_ahead(a, cfdata->compressed_bytes_remaining, 1730 &bytes_avail); 1731 if (bytes_avail <= 0) { 1732 *avail = truncated_error(a); 1733 return (NULL); 1734 } 1735 cfdata->unconsumed = cfdata->compressed_bytes_remaining; 1736 cfdata->sum_ptr = d; 1737 if (cab_minimum_consume_cfdata(a, cfdata->unconsumed) < 0) { 1738 *avail = ARCHIVE_FATAL; 1739 return (NULL); 1740 } 1741 } 1742 1743 /* 1744 * Translation reversal of x86 proccessor CALL byte sequence(E8). 1745 */ 1746 lzx_translation(&cab->xstrm, cab->uncompressed_buffer, 1747 cfdata->uncompressed_size, 1748 (cab->entry_cffolder->cfdata_index-1) * 0x8000); 1749 1750 d = cab->uncompressed_buffer + cfdata->read_offset; 1751 *avail = uavail - cfdata->read_offset; 1752 cfdata->uncompressed_avail = uavail; 1753 1754 return (d); 1755 } 1756 1757 /* 1758 * Consume CFDATA. 1759 * We always decompress CFDATA to consume CFDATA as much as we need 1760 * in uncompressed bytes because all CFDATA in a folder are related 1761 * so we do not skip any CFDATA without decompressing. 1762 * Note: If the folder of a CFFILE is iFoldCONTINUED_PREV_AND_NEXT or 1763 * iFoldCONTINUED_FROM_PREV, we won't decompress because a CFDATA for 1764 * the CFFILE is remaining bytes of previous Multivolume CAB file. 1765 */ 1766 static int64_t 1767 cab_consume_cfdata(struct archive_read *a, int64_t consumed_bytes) 1768 { 1769 struct cab *cab = (struct cab *)(a->format->data); 1770 struct cfdata *cfdata; 1771 int64_t cbytes, rbytes; 1772 int err; 1773 1774 rbytes = cab_minimum_consume_cfdata(a, consumed_bytes); 1775 if (rbytes < 0) 1776 return (ARCHIVE_FATAL); 1777 1778 cfdata = cab->entry_cfdata; 1779 while (rbytes > 0) { 1780 ssize_t avail; 1781 1782 if (cfdata->compressed_size == 0) { 1783 archive_set_error(&a->archive, 1784 ARCHIVE_ERRNO_FILE_FORMAT, 1785 "Invalid CFDATA"); 1786 return (ARCHIVE_FATAL); 1787 } 1788 cbytes = cfdata->uncompressed_bytes_remaining; 1789 if (cbytes > rbytes) 1790 cbytes = rbytes; 1791 rbytes -= cbytes; 1792 1793 if (cfdata->uncompressed_avail == 0 && 1794 (cab->entry_cffile->folder == iFoldCONTINUED_PREV_AND_NEXT || 1795 cab->entry_cffile->folder == iFoldCONTINUED_FROM_PREV)) { 1796 /* We have not read any data yet. */ 1797 if (cbytes == cfdata->uncompressed_bytes_remaining) { 1798 /* Skip whole current CFDATA. */ 1799 __archive_read_consume(a, 1800 cfdata->compressed_size); 1801 cab->cab_offset += cfdata->compressed_size; 1802 cfdata->compressed_bytes_remaining = 0; 1803 cfdata->uncompressed_bytes_remaining = 0; 1804 err = cab_next_cfdata(a); 1805 if (err < 0) 1806 return (err); 1807 cfdata = cab->entry_cfdata; 1808 if (cfdata->uncompressed_size == 0) { 1809 switch (cab->entry_cffile->folder) { 1810 case iFoldCONTINUED_PREV_AND_NEXT: 1811 case iFoldCONTINUED_TO_NEXT: 1812 case iFoldCONTINUED_FROM_PREV: 1813 rbytes = 0; 1814 break; 1815 default: 1816 break; 1817 } 1818 } 1819 continue; 1820 } 1821 cfdata->read_offset += (uint16_t)cbytes; 1822 cfdata->uncompressed_bytes_remaining -= (uint16_t)cbytes; 1823 break; 1824 } else if (cbytes == 0) { 1825 err = cab_next_cfdata(a); 1826 if (err < 0) 1827 return (err); 1828 cfdata = cab->entry_cfdata; 1829 if (cfdata->uncompressed_size == 0) { 1830 switch (cab->entry_cffile->folder) { 1831 case iFoldCONTINUED_PREV_AND_NEXT: 1832 case iFoldCONTINUED_TO_NEXT: 1833 case iFoldCONTINUED_FROM_PREV: 1834 return (ARCHIVE_FATAL); 1835 default: 1836 break; 1837 } 1838 } 1839 continue; 1840 } 1841 while (cbytes > 0) { 1842 (void)cab_read_ahead_cfdata(a, &avail); 1843 if (avail <= 0) 1844 return (ARCHIVE_FATAL); 1845 if (avail > cbytes) 1846 avail = (ssize_t)cbytes; 1847 if (cab_minimum_consume_cfdata(a, avail) < 0) 1848 return (ARCHIVE_FATAL); 1849 cbytes -= avail; 1850 } 1851 } 1852 return (consumed_bytes); 1853 } 1854 1855 /* 1856 * Consume CFDATA as much as we have already gotten and 1857 * compute the sum of CFDATA. 1858 */ 1859 static int64_t 1860 cab_minimum_consume_cfdata(struct archive_read *a, int64_t consumed_bytes) 1861 { 1862 struct cab *cab = (struct cab *)(a->format->data); 1863 struct cfdata *cfdata; 1864 int64_t cbytes, rbytes; 1865 int err; 1866 1867 cfdata = cab->entry_cfdata; 1868 rbytes = consumed_bytes; 1869 if (cab->entry_cffolder->comptype == COMPTYPE_NONE) { 1870 if (consumed_bytes < cfdata->unconsumed) 1871 cbytes = consumed_bytes; 1872 else 1873 cbytes = cfdata->unconsumed; 1874 rbytes -= cbytes; 1875 cfdata->read_offset += (uint16_t)cbytes; 1876 cfdata->uncompressed_bytes_remaining -= (uint16_t)cbytes; 1877 cfdata->unconsumed -= cbytes; 1878 } else { 1879 cbytes = cfdata->uncompressed_avail - cfdata->read_offset; 1880 if (cbytes > 0) { 1881 if (consumed_bytes < cbytes) 1882 cbytes = consumed_bytes; 1883 rbytes -= cbytes; 1884 cfdata->read_offset += (uint16_t)cbytes; 1885 cfdata->uncompressed_bytes_remaining -= (uint16_t)cbytes; 1886 } 1887 1888 if (cfdata->unconsumed) { 1889 cbytes = cfdata->unconsumed; 1890 cfdata->unconsumed = 0; 1891 } else 1892 cbytes = 0; 1893 } 1894 if (cbytes) { 1895 /* Compute the sum. */ 1896 cab_checksum_update(a, (size_t)cbytes); 1897 1898 /* Consume as much as the compressor actually used. */ 1899 __archive_read_consume(a, cbytes); 1900 cab->cab_offset += cbytes; 1901 cfdata->compressed_bytes_remaining -= (uint16_t)cbytes; 1902 if (cfdata->compressed_bytes_remaining == 0) { 1903 err = cab_checksum_finish(a); 1904 if (err < 0) 1905 return (err); 1906 } 1907 } 1908 return (rbytes); 1909 } 1910 1911 /* 1912 * Returns ARCHIVE_OK if successful, ARCHIVE_FATAL otherwise, sets 1913 * cab->end_of_entry if it consumes all of the data. 1914 */ 1915 static int 1916 cab_read_data(struct archive_read *a, const void **buff, 1917 size_t *size, int64_t *offset) 1918 { 1919 struct cab *cab = (struct cab *)(a->format->data); 1920 ssize_t bytes_avail; 1921 1922 if (cab->entry_bytes_remaining == 0) { 1923 *buff = NULL; 1924 *size = 0; 1925 *offset = cab->entry_offset; 1926 cab->end_of_entry = 1; 1927 return (ARCHIVE_OK); 1928 } 1929 1930 *buff = cab_read_ahead_cfdata(a, &bytes_avail); 1931 if (bytes_avail <= 0) { 1932 *buff = NULL; 1933 *size = 0; 1934 *offset = 0; 1935 if (bytes_avail == 0 && 1936 cab->entry_cfdata->uncompressed_size == 0) { 1937 /* All of CFDATA in a folder has been handled. */ 1938 archive_set_error(&a->archive, 1939 ARCHIVE_ERRNO_FILE_FORMAT, "Invalid CFDATA"); 1940 return (ARCHIVE_FATAL); 1941 } else 1942 return ((int)bytes_avail); 1943 } 1944 if (bytes_avail > cab->entry_bytes_remaining) 1945 bytes_avail = (ssize_t)cab->entry_bytes_remaining; 1946 1947 *size = bytes_avail; 1948 *offset = cab->entry_offset; 1949 cab->entry_offset += bytes_avail; 1950 cab->entry_bytes_remaining -= bytes_avail; 1951 if (cab->entry_bytes_remaining == 0) 1952 cab->end_of_entry = 1; 1953 cab->entry_unconsumed = bytes_avail; 1954 if (cab->entry_cffolder->comptype == COMPTYPE_NONE) { 1955 /* Don't consume more than current entry used. */ 1956 if (cab->entry_cfdata->unconsumed > cab->entry_unconsumed) 1957 cab->entry_cfdata->unconsumed = cab->entry_unconsumed; 1958 } 1959 return (ARCHIVE_OK); 1960 } 1961 1962 static int 1963 archive_read_format_cab_read_data_skip(struct archive_read *a) 1964 { 1965 struct cab *cab; 1966 int64_t bytes_skipped; 1967 int r; 1968 1969 cab = (struct cab *)(a->format->data); 1970 1971 if (cab->end_of_archive) 1972 return (ARCHIVE_EOF); 1973 1974 if (!cab->read_data_invoked) { 1975 cab->bytes_skipped += cab->entry_bytes_remaining; 1976 cab->entry_bytes_remaining = 0; 1977 /* This entry is finished and done. */ 1978 cab->end_of_entry_cleanup = cab->end_of_entry = 1; 1979 return (ARCHIVE_OK); 1980 } 1981 1982 if (cab->entry_unconsumed) { 1983 /* Consume as much as the compressor actually used. */ 1984 r = (int)cab_consume_cfdata(a, cab->entry_unconsumed); 1985 cab->entry_unconsumed = 0; 1986 if (r < 0) 1987 return (r); 1988 } else if (cab->entry_cfdata == NULL) { 1989 r = cab_next_cfdata(a); 1990 if (r < 0) 1991 return (r); 1992 } 1993 1994 /* if we've already read to end of data, we're done. */ 1995 if (cab->end_of_entry_cleanup) 1996 return (ARCHIVE_OK); 1997 1998 /* 1999 * If the length is at the beginning, we can skip the 2000 * compressed data much more quickly. 2001 */ 2002 bytes_skipped = cab_consume_cfdata(a, cab->entry_bytes_remaining); 2003 if (bytes_skipped < 0) 2004 return (ARCHIVE_FATAL); 2005 2006 /* If the compression type is none(uncompressed), we've already 2007 * consumed data as much as the current entry size. */ 2008 if (cab->entry_cffolder->comptype == COMPTYPE_NONE && 2009 cab->entry_cfdata != NULL) 2010 cab->entry_cfdata->unconsumed = 0; 2011 2012 /* This entry is finished and done. */ 2013 cab->end_of_entry_cleanup = cab->end_of_entry = 1; 2014 return (ARCHIVE_OK); 2015 } 2016 2017 static int 2018 archive_read_format_cab_cleanup(struct archive_read *a) 2019 { 2020 struct cab *cab = (struct cab *)(a->format->data); 2021 struct cfheader *hd = &cab->cfheader; 2022 int i; 2023 2024 if (hd->folder_array != NULL) { 2025 for (i = 0; i < hd->folder_count; i++) 2026 free(hd->folder_array[i].cfdata.memimage); 2027 free(hd->folder_array); 2028 } 2029 if (hd->file_array != NULL) { 2030 for (i = 0; i < cab->cfheader.file_count; i++) 2031 archive_string_free(&(hd->file_array[i].pathname)); 2032 free(hd->file_array); 2033 } 2034 #ifdef HAVE_ZLIB_H 2035 if (cab->stream_valid) 2036 inflateEnd(&cab->stream); 2037 #endif 2038 lzx_decode_free(&cab->xstrm); 2039 archive_wstring_free(&cab->ws); 2040 free(cab->uncompressed_buffer); 2041 free(cab); 2042 (a->format->data) = NULL; 2043 return (ARCHIVE_OK); 2044 } 2045 2046 /* Convert an MSDOS-style date/time into Unix-style time. */ 2047 static time_t 2048 cab_dos_time(const unsigned char *p) 2049 { 2050 int msTime, msDate; 2051 struct tm ts; 2052 2053 msDate = archive_le16dec(p); 2054 msTime = archive_le16dec(p+2); 2055 2056 memset(&ts, 0, sizeof(ts)); 2057 ts.tm_year = ((msDate >> 9) & 0x7f) + 80; /* Years since 1900. */ 2058 ts.tm_mon = ((msDate >> 5) & 0x0f) - 1; /* Month number. */ 2059 ts.tm_mday = msDate & 0x1f; /* Day of month. */ 2060 ts.tm_hour = (msTime >> 11) & 0x1f; 2061 ts.tm_min = (msTime >> 5) & 0x3f; 2062 ts.tm_sec = (msTime << 1) & 0x3e; 2063 ts.tm_isdst = -1; 2064 return (mktime(&ts)); 2065 } 2066 2067 /***************************************************************** 2068 * 2069 * LZX decompression code. 2070 * 2071 *****************************************************************/ 2072 2073 /* 2074 * Initialize LZX decoder. 2075 * 2076 * Returns ARCHIVE_OK if initialization was successful. 2077 * Returns ARCHIVE_FAILED if w_bits has unsupported value. 2078 * Returns ARCHIVE_FATAL if initialization failed; memory allocation 2079 * error occurred. 2080 */ 2081 static int 2082 lzx_decode_init(struct lzx_stream *strm, int w_bits) 2083 { 2084 struct lzx_dec *ds; 2085 int slot, w_size, w_slot; 2086 int base, footer; 2087 int base_inc[18]; 2088 2089 if (strm->ds == NULL) { 2090 strm->ds = calloc(1, sizeof(*strm->ds)); 2091 if (strm->ds == NULL) 2092 return (ARCHIVE_FATAL); 2093 } 2094 ds = strm->ds; 2095 ds->error = ARCHIVE_FAILED; 2096 2097 /* Allow bits from 15(32KBi) up to 21(2MBi) */ 2098 if (w_bits < SLOT_BASE || w_bits > SLOT_MAX) 2099 return (ARCHIVE_FAILED); 2100 2101 ds->error = ARCHIVE_FATAL; 2102 2103 /* 2104 * Alloc window 2105 */ 2106 w_size = ds->w_size; 2107 w_slot = slots[w_bits - SLOT_BASE]; 2108 ds->w_size = 1U << w_bits; 2109 ds->w_mask = ds->w_size -1; 2110 if (ds->w_buff == NULL || w_size != ds->w_size) { 2111 free(ds->w_buff); 2112 ds->w_buff = malloc(ds->w_size); 2113 if (ds->w_buff == NULL) 2114 return (ARCHIVE_FATAL); 2115 free(ds->pos_tbl); 2116 ds->pos_tbl = malloc(sizeof(ds->pos_tbl[0]) * w_slot); 2117 if (ds->pos_tbl == NULL) 2118 return (ARCHIVE_FATAL); 2119 lzx_huffman_free(&(ds->mt)); 2120 } 2121 2122 for (footer = 0; footer < 18; footer++) 2123 base_inc[footer] = 1 << footer; 2124 base = footer = 0; 2125 for (slot = 0; slot < w_slot; slot++) { 2126 int n; 2127 if (footer == 0) 2128 base = slot; 2129 else 2130 base += base_inc[footer]; 2131 if (footer < 17) { 2132 footer = -2; 2133 for (n = base; n; n >>= 1) 2134 footer++; 2135 if (footer <= 0) 2136 footer = 0; 2137 } 2138 ds->pos_tbl[slot].base = base; 2139 ds->pos_tbl[slot].footer_bits = footer; 2140 } 2141 2142 ds->w_pos = 0; 2143 ds->state = 0; 2144 ds->br.cache_buffer = 0; 2145 ds->br.cache_avail = 0; 2146 ds->r0 = ds->r1 = ds->r2 = 1; 2147 2148 /* Initialize aligned offset tree. */ 2149 if (lzx_huffman_init(&(ds->at), 8, 8) != ARCHIVE_OK) 2150 return (ARCHIVE_FATAL); 2151 2152 /* Initialize pre-tree. */ 2153 if (lzx_huffman_init(&(ds->pt), 20, 10) != ARCHIVE_OK) 2154 return (ARCHIVE_FATAL); 2155 2156 /* Initialize Main tree. */ 2157 if (lzx_huffman_init(&(ds->mt), 256+(w_slot<<3), 16) 2158 != ARCHIVE_OK) 2159 return (ARCHIVE_FATAL); 2160 2161 /* Initialize Length tree. */ 2162 if (lzx_huffman_init(&(ds->lt), 249, 16) != ARCHIVE_OK) 2163 return (ARCHIVE_FATAL); 2164 2165 ds->error = 0; 2166 2167 return (ARCHIVE_OK); 2168 } 2169 2170 /* 2171 * Release LZX decoder. 2172 */ 2173 static void 2174 lzx_decode_free(struct lzx_stream *strm) 2175 { 2176 2177 if (strm->ds == NULL) 2178 return; 2179 free(strm->ds->w_buff); 2180 free(strm->ds->pos_tbl); 2181 lzx_huffman_free(&(strm->ds->at)); 2182 lzx_huffman_free(&(strm->ds->pt)); 2183 lzx_huffman_free(&(strm->ds->mt)); 2184 lzx_huffman_free(&(strm->ds->lt)); 2185 free(strm->ds); 2186 strm->ds = NULL; 2187 } 2188 2189 /* 2190 * E8 Call Translation reversal. 2191 */ 2192 static void 2193 lzx_translation(struct lzx_stream *strm, void *p, size_t size, uint32_t offset) 2194 { 2195 struct lzx_dec *ds = strm->ds; 2196 unsigned char *b, *end; 2197 2198 if (!ds->translation || size <= 10) 2199 return; 2200 b = p; 2201 end = b + size - 10; 2202 while (b < end && (b = memchr(b, 0xE8, end - b)) != NULL) { 2203 size_t i = b - (unsigned char *)p; 2204 int32_t cp, displacement, value; 2205 2206 cp = (int32_t)(offset + (uint32_t)i); 2207 value = archive_le32dec(&b[1]); 2208 if (value >= -cp && value < (int32_t)ds->translation_size) { 2209 if (value >= 0) 2210 displacement = value - cp; 2211 else 2212 displacement = value + ds->translation_size; 2213 archive_le32enc(&b[1], (uint32_t)displacement); 2214 } 2215 b += 5; 2216 } 2217 } 2218 2219 /* 2220 * Bit stream reader. 2221 */ 2222 /* Check that the cache buffer has enough bits. */ 2223 #define lzx_br_has(br, n) ((br)->cache_avail >= n) 2224 /* Get compressed data by bit. */ 2225 #define lzx_br_bits(br, n) \ 2226 (((uint32_t)((br)->cache_buffer >> \ 2227 ((br)->cache_avail - (n)))) & cache_masks[n]) 2228 #define lzx_br_bits_forced(br, n) \ 2229 (((uint32_t)((br)->cache_buffer << \ 2230 ((n) - (br)->cache_avail))) & cache_masks[n]) 2231 /* Read ahead to make sure the cache buffer has enough compressed data we 2232 * will use. 2233 * True : completed, there is enough data in the cache buffer. 2234 * False : we met that strm->next_in is empty, we have to get following 2235 * bytes. */ 2236 #define lzx_br_read_ahead_0(strm, br, n) \ 2237 (lzx_br_has((br), (n)) || lzx_br_fillup(strm, br)) 2238 /* True : the cache buffer has some bits as much as we need. 2239 * False : there are no enough bits in the cache buffer to be used, 2240 * we have to get following bytes if we could. */ 2241 #define lzx_br_read_ahead(strm, br, n) \ 2242 (lzx_br_read_ahead_0((strm), (br), (n)) || lzx_br_has((br), (n))) 2243 2244 /* Notify how many bits we consumed. */ 2245 #define lzx_br_consume(br, n) ((br)->cache_avail -= (n)) 2246 #define lzx_br_consume_unaligned_bits(br) ((br)->cache_avail &= ~0x0f) 2247 2248 #define lzx_br_is_unaligned(br) ((br)->cache_avail & 0x0f) 2249 2250 static const uint32_t cache_masks[] = { 2251 0x00000000, 0x00000001, 0x00000003, 0x00000007, 2252 0x0000000F, 0x0000001F, 0x0000003F, 0x0000007F, 2253 0x000000FF, 0x000001FF, 0x000003FF, 0x000007FF, 2254 0x00000FFF, 0x00001FFF, 0x00003FFF, 0x00007FFF, 2255 0x0000FFFF, 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 2256 0x000FFFFF, 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 2257 0x00FFFFFF, 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 2258 0x0FFFFFFF, 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 2259 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF 2260 }; 2261 2262 /* 2263 * Shift away used bits in the cache data and fill it up with following bits. 2264 * Call this when cache buffer does not have enough bits you need. 2265 * 2266 * Returns 1 if the cache buffer is full. 2267 * Returns 0 if the cache buffer is not full; input buffer is empty. 2268 */ 2269 static int 2270 lzx_br_fillup(struct lzx_stream *strm, struct lzx_br *br) 2271 { 2272 /* 2273 * x86 proccessor family can read misaligned data without an access error. 2274 */ 2275 int n = CACHE_BITS - br->cache_avail; 2276 2277 for (;;) { 2278 switch (n >> 4) { 2279 case 4: 2280 if (strm->avail_in >= 8) { 2281 br->cache_buffer = 2282 ((uint64_t)strm->next_in[1]) << 56 | 2283 ((uint64_t)strm->next_in[0]) << 48 | 2284 ((uint64_t)strm->next_in[3]) << 40 | 2285 ((uint64_t)strm->next_in[2]) << 32 | 2286 ((uint32_t)strm->next_in[5]) << 24 | 2287 ((uint32_t)strm->next_in[4]) << 16 | 2288 ((uint32_t)strm->next_in[7]) << 8 | 2289 (uint32_t)strm->next_in[6]; 2290 strm->next_in += 8; 2291 strm->avail_in -= 8; 2292 br->cache_avail += 8 * 8; 2293 return (1); 2294 } 2295 break; 2296 case 3: 2297 if (strm->avail_in >= 6) { 2298 br->cache_buffer = 2299 (br->cache_buffer << 48) | 2300 ((uint64_t)strm->next_in[1]) << 40 | 2301 ((uint64_t)strm->next_in[0]) << 32 | 2302 ((uint32_t)strm->next_in[3]) << 24 | 2303 ((uint32_t)strm->next_in[2]) << 16 | 2304 ((uint32_t)strm->next_in[5]) << 8 | 2305 (uint32_t)strm->next_in[4]; 2306 strm->next_in += 6; 2307 strm->avail_in -= 6; 2308 br->cache_avail += 6 * 8; 2309 return (1); 2310 } 2311 break; 2312 case 0: 2313 /* We have enough compressed data in 2314 * the cache buffer.*/ 2315 return (1); 2316 default: 2317 break; 2318 } 2319 if (strm->avail_in < 2) { 2320 /* There is not enough compressed data to 2321 * fill up the cache buffer. */ 2322 if (strm->avail_in == 1) { 2323 br->odd = *strm->next_in++; 2324 strm->avail_in--; 2325 br->have_odd = 1; 2326 } 2327 return (0); 2328 } 2329 br->cache_buffer = 2330 (br->cache_buffer << 16) | 2331 archive_le16dec(strm->next_in); 2332 strm->next_in += 2; 2333 strm->avail_in -= 2; 2334 br->cache_avail += 16; 2335 n -= 16; 2336 } 2337 } 2338 2339 static void 2340 lzx_br_fixup(struct lzx_stream *strm, struct lzx_br *br) 2341 { 2342 int n = CACHE_BITS - br->cache_avail; 2343 2344 if (br->have_odd && n >= 16 && strm->avail_in > 0) { 2345 br->cache_buffer = 2346 (br->cache_buffer << 16) | 2347 ((uint16_t)(*strm->next_in)) << 8 | br->odd; 2348 strm->next_in++; 2349 strm->avail_in--; 2350 br->cache_avail += 16; 2351 br->have_odd = 0; 2352 } 2353 } 2354 2355 static void 2356 lzx_cleanup_bitstream(struct lzx_stream *strm) 2357 { 2358 strm->ds->br.cache_avail = 0; 2359 strm->ds->br.have_odd = 0; 2360 } 2361 2362 /* 2363 * Decode LZX. 2364 * 2365 * 1. Returns ARCHIVE_OK if output buffer or input buffer are empty. 2366 * Please set available buffer and call this function again. 2367 * 2. Returns ARCHIVE_EOF if decompression has been completed. 2368 * 3. Returns ARCHIVE_FAILED if an error occurred; compressed data 2369 * is broken or you do not set 'last' flag properly. 2370 */ 2371 #define ST_RD_TRANSLATION 0 2372 #define ST_RD_TRANSLATION_SIZE 1 2373 #define ST_RD_BLOCK_TYPE 2 2374 #define ST_RD_BLOCK_SIZE 3 2375 #define ST_RD_ALIGNMENT 4 2376 #define ST_RD_R0 5 2377 #define ST_RD_R1 6 2378 #define ST_RD_R2 7 2379 #define ST_COPY_UNCOMP1 8 2380 #define ST_COPY_UNCOMP2 9 2381 #define ST_RD_ALIGNED_OFFSET 10 2382 #define ST_RD_VERBATIM 11 2383 #define ST_RD_PRE_MAIN_TREE_256 12 2384 #define ST_MAIN_TREE_256 13 2385 #define ST_RD_PRE_MAIN_TREE_REM 14 2386 #define ST_MAIN_TREE_REM 15 2387 #define ST_RD_PRE_LENGTH_TREE 16 2388 #define ST_LENGTH_TREE 17 2389 #define ST_MAIN 18 2390 #define ST_LENGTH 19 2391 #define ST_OFFSET 20 2392 #define ST_REAL_POS 21 2393 #define ST_COPY 22 2394 2395 static int 2396 lzx_decode(struct lzx_stream *strm, int last) 2397 { 2398 struct lzx_dec *ds = strm->ds; 2399 int64_t avail_in; 2400 int r; 2401 2402 if (ds->error) 2403 return (ds->error); 2404 2405 avail_in = strm->avail_in; 2406 lzx_br_fixup(strm, &(ds->br)); 2407 do { 2408 if (ds->state < ST_MAIN) 2409 r = lzx_read_blocks(strm, last); 2410 else { 2411 int64_t bytes_written = strm->avail_out; 2412 r = lzx_decode_blocks(strm, last); 2413 bytes_written -= strm->avail_out; 2414 strm->next_out += bytes_written; 2415 strm->total_out += bytes_written; 2416 } 2417 } while (r == 100); 2418 strm->total_in += avail_in - strm->avail_in; 2419 return (r); 2420 } 2421 2422 static int 2423 lzx_read_blocks(struct lzx_stream *strm, int last) 2424 { 2425 struct lzx_dec *ds = strm->ds; 2426 struct lzx_br *br = &(ds->br); 2427 int i, r; 2428 2429 for (;;) { 2430 switch (ds->state) { 2431 case ST_RD_TRANSLATION: 2432 if (!lzx_br_read_ahead(strm, br, 1)) { 2433 ds->state = ST_RD_TRANSLATION; 2434 if (last) 2435 goto failed; 2436 return (ARCHIVE_OK); 2437 } 2438 ds->translation = lzx_br_bits(br, 1); 2439 lzx_br_consume(br, 1); 2440 /* FALL THROUGH */ 2441 case ST_RD_TRANSLATION_SIZE: 2442 if (ds->translation) { 2443 if (!lzx_br_read_ahead(strm, br, 32)) { 2444 ds->state = ST_RD_TRANSLATION_SIZE; 2445 if (last) 2446 goto failed; 2447 return (ARCHIVE_OK); 2448 } 2449 ds->translation_size = lzx_br_bits(br, 16); 2450 lzx_br_consume(br, 16); 2451 ds->translation_size <<= 16; 2452 ds->translation_size |= lzx_br_bits(br, 16); 2453 lzx_br_consume(br, 16); 2454 } 2455 /* FALL THROUGH */ 2456 case ST_RD_BLOCK_TYPE: 2457 if (!lzx_br_read_ahead(strm, br, 3)) { 2458 ds->state = ST_RD_BLOCK_TYPE; 2459 if (last) 2460 goto failed; 2461 return (ARCHIVE_OK); 2462 } 2463 ds->block_type = lzx_br_bits(br, 3); 2464 lzx_br_consume(br, 3); 2465 /* Check a block type. */ 2466 switch (ds->block_type) { 2467 case VERBATIM_BLOCK: 2468 case ALIGNED_OFFSET_BLOCK: 2469 case UNCOMPRESSED_BLOCK: 2470 break; 2471 default: 2472 goto failed;/* Invalid */ 2473 } 2474 /* FALL THROUGH */ 2475 case ST_RD_BLOCK_SIZE: 2476 if (!lzx_br_read_ahead(strm, br, 24)) { 2477 ds->state = ST_RD_BLOCK_SIZE; 2478 if (last) 2479 goto failed; 2480 return (ARCHIVE_OK); 2481 } 2482 ds->block_size = lzx_br_bits(br, 8); 2483 lzx_br_consume(br, 8); 2484 ds->block_size <<= 16; 2485 ds->block_size |= lzx_br_bits(br, 16); 2486 lzx_br_consume(br, 16); 2487 if (ds->block_size == 0) 2488 goto failed; 2489 ds->block_bytes_avail = ds->block_size; 2490 if (ds->block_type != UNCOMPRESSED_BLOCK) { 2491 if (ds->block_type == VERBATIM_BLOCK) 2492 ds->state = ST_RD_VERBATIM; 2493 else 2494 ds->state = ST_RD_ALIGNED_OFFSET; 2495 break; 2496 } 2497 /* FALL THROUGH */ 2498 case ST_RD_ALIGNMENT: 2499 /* 2500 * Handle an Uncompressed Block. 2501 */ 2502 /* Skip padding to align following field on 2503 * 16-bit boundary. */ 2504 if (lzx_br_is_unaligned(br)) 2505 lzx_br_consume_unaligned_bits(br); 2506 else { 2507 if (lzx_br_read_ahead(strm, br, 16)) 2508 lzx_br_consume(br, 16); 2509 else { 2510 ds->state = ST_RD_ALIGNMENT; 2511 if (last) 2512 goto failed; 2513 return (ARCHIVE_OK); 2514 } 2515 } 2516 /* Preparation to read repeated offsets R0,R1 and R2. */ 2517 ds->rbytes_avail = 0; 2518 ds->state = ST_RD_R0; 2519 /* FALL THROUGH */ 2520 case ST_RD_R0: 2521 case ST_RD_R1: 2522 case ST_RD_R2: 2523 do { 2524 uint16_t u16; 2525 /* Drain bits in the cache buffer of 2526 * bit-stream. */ 2527 if (lzx_br_has(br, 32)) { 2528 u16 = lzx_br_bits(br, 16); 2529 lzx_br_consume(br, 16); 2530 archive_le16enc(ds->rbytes, u16); 2531 u16 = lzx_br_bits(br, 16); 2532 lzx_br_consume(br, 16); 2533 archive_le16enc(ds->rbytes+2, u16); 2534 ds->rbytes_avail = 4; 2535 } else if (lzx_br_has(br, 16)) { 2536 u16 = lzx_br_bits(br, 16); 2537 lzx_br_consume(br, 16); 2538 archive_le16enc(ds->rbytes, u16); 2539 ds->rbytes_avail = 2; 2540 } 2541 if (ds->rbytes_avail < 4 && ds->br.have_odd) { 2542 ds->rbytes[ds->rbytes_avail++] = 2543 ds->br.odd; 2544 ds->br.have_odd = 0; 2545 } 2546 while (ds->rbytes_avail < 4) { 2547 if (strm->avail_in <= 0) { 2548 if (last) 2549 goto failed; 2550 return (ARCHIVE_OK); 2551 } 2552 ds->rbytes[ds->rbytes_avail++] = 2553 *strm->next_in++; 2554 strm->avail_in--; 2555 } 2556 ds->rbytes_avail = 0; 2557 if (ds->state == ST_RD_R0) { 2558 ds->r0 = archive_le32dec(ds->rbytes); 2559 if (ds->r0 < 0) 2560 goto failed; 2561 ds->state = ST_RD_R1; 2562 } else if (ds->state == ST_RD_R1) { 2563 ds->r1 = archive_le32dec(ds->rbytes); 2564 if (ds->r1 < 0) 2565 goto failed; 2566 ds->state = ST_RD_R2; 2567 } else if (ds->state == ST_RD_R2) { 2568 ds->r2 = archive_le32dec(ds->rbytes); 2569 if (ds->r2 < 0) 2570 goto failed; 2571 /* We've gotten all repeated offsets. */ 2572 ds->state = ST_COPY_UNCOMP1; 2573 } 2574 } while (ds->state != ST_COPY_UNCOMP1); 2575 /* FALL THROUGH */ 2576 case ST_COPY_UNCOMP1: 2577 /* 2578 * Copy bytes form next_in to next_out directly. 2579 */ 2580 while (ds->block_bytes_avail) { 2581 int l; 2582 2583 if (strm->avail_out <= 0) 2584 /* Output buffer is empty. */ 2585 return (ARCHIVE_OK); 2586 if (strm->avail_in <= 0) { 2587 /* Input buffer is empty. */ 2588 if (last) 2589 goto failed; 2590 return (ARCHIVE_OK); 2591 } 2592 l = (int)ds->block_bytes_avail; 2593 if (l > ds->w_size - ds->w_pos) 2594 l = ds->w_size - ds->w_pos; 2595 if (l > strm->avail_out) 2596 l = (int)strm->avail_out; 2597 if (l > strm->avail_in) 2598 l = (int)strm->avail_in; 2599 memcpy(strm->next_out, strm->next_in, l); 2600 memcpy(&(ds->w_buff[ds->w_pos]), 2601 strm->next_in, l); 2602 strm->next_in += l; 2603 strm->avail_in -= l; 2604 strm->next_out += l; 2605 strm->avail_out -= l; 2606 strm->total_out += l; 2607 ds->w_pos = (ds->w_pos + l) & ds->w_mask; 2608 ds->block_bytes_avail -= l; 2609 } 2610 /* FALL THROUGH */ 2611 case ST_COPY_UNCOMP2: 2612 /* Re-align; skip padding byte. */ 2613 if (ds->block_size & 1) { 2614 if (strm->avail_in <= 0) { 2615 /* Input buffer is empty. */ 2616 ds->state = ST_COPY_UNCOMP2; 2617 if (last) 2618 goto failed; 2619 return (ARCHIVE_OK); 2620 } 2621 strm->next_in++; 2622 strm->avail_in --; 2623 } 2624 /* This block ended. */ 2625 ds->state = ST_RD_BLOCK_TYPE; 2626 return (ARCHIVE_EOF); 2627 /********************/ 2628 case ST_RD_ALIGNED_OFFSET: 2629 /* 2630 * Read Aligned offset tree. 2631 */ 2632 if (!lzx_br_read_ahead(strm, br, 3 * ds->at.len_size)) { 2633 ds->state = ST_RD_ALIGNED_OFFSET; 2634 if (last) 2635 goto failed; 2636 return (ARCHIVE_OK); 2637 } 2638 memset(ds->at.freq, 0, sizeof(ds->at.freq)); 2639 for (i = 0; i < ds->at.len_size; i++) { 2640 ds->at.bitlen[i] = lzx_br_bits(br, 3); 2641 ds->at.freq[ds->at.bitlen[i]]++; 2642 lzx_br_consume(br, 3); 2643 } 2644 if (!lzx_make_huffman_table(&ds->at)) 2645 goto failed; 2646 /* FALL THROUGH */ 2647 case ST_RD_VERBATIM: 2648 ds->loop = 0; 2649 /* FALL THROUGH */ 2650 case ST_RD_PRE_MAIN_TREE_256: 2651 /* 2652 * Read Pre-tree for first 256 elements of main tree. 2653 */ 2654 if (!lzx_read_pre_tree(strm)) { 2655 ds->state = ST_RD_PRE_MAIN_TREE_256; 2656 if (last) 2657 goto failed; 2658 return (ARCHIVE_OK); 2659 } 2660 if (!lzx_make_huffman_table(&ds->pt)) 2661 goto failed; 2662 ds->loop = 0; 2663 /* FALL THROUGH */ 2664 case ST_MAIN_TREE_256: 2665 /* 2666 * Get path lengths of first 256 elements of main tree. 2667 */ 2668 r = lzx_read_bitlen(strm, &ds->mt, 256); 2669 if (r < 0) 2670 goto failed; 2671 else if (!r) { 2672 ds->state = ST_MAIN_TREE_256; 2673 if (last) 2674 goto failed; 2675 return (ARCHIVE_OK); 2676 } 2677 ds->loop = 0; 2678 /* FALL THROUGH */ 2679 case ST_RD_PRE_MAIN_TREE_REM: 2680 /* 2681 * Read Pre-tree for remaining elements of main tree. 2682 */ 2683 if (!lzx_read_pre_tree(strm)) { 2684 ds->state = ST_RD_PRE_MAIN_TREE_REM; 2685 if (last) 2686 goto failed; 2687 return (ARCHIVE_OK); 2688 } 2689 if (!lzx_make_huffman_table(&ds->pt)) 2690 goto failed; 2691 ds->loop = 256; 2692 /* FALL THROUGH */ 2693 case ST_MAIN_TREE_REM: 2694 /* 2695 * Get path lengths of remaining elements of main tree. 2696 */ 2697 r = lzx_read_bitlen(strm, &ds->mt, -1); 2698 if (r < 0) 2699 goto failed; 2700 else if (!r) { 2701 ds->state = ST_MAIN_TREE_REM; 2702 if (last) 2703 goto failed; 2704 return (ARCHIVE_OK); 2705 } 2706 if (!lzx_make_huffman_table(&ds->mt)) 2707 goto failed; 2708 ds->loop = 0; 2709 /* FALL THROUGH */ 2710 case ST_RD_PRE_LENGTH_TREE: 2711 /* 2712 * Read Pre-tree for remaining elements of main tree. 2713 */ 2714 if (!lzx_read_pre_tree(strm)) { 2715 ds->state = ST_RD_PRE_LENGTH_TREE; 2716 if (last) 2717 goto failed; 2718 return (ARCHIVE_OK); 2719 } 2720 if (!lzx_make_huffman_table(&ds->pt)) 2721 goto failed; 2722 ds->loop = 0; 2723 /* FALL THROUGH */ 2724 case ST_LENGTH_TREE: 2725 /* 2726 * Get path lengths of remaining elements of main tree. 2727 */ 2728 r = lzx_read_bitlen(strm, &ds->lt, -1); 2729 if (r < 0) 2730 goto failed; 2731 else if (!r) { 2732 ds->state = ST_LENGTH_TREE; 2733 if (last) 2734 goto failed; 2735 return (ARCHIVE_OK); 2736 } 2737 if (!lzx_make_huffman_table(&ds->lt)) 2738 goto failed; 2739 ds->state = ST_MAIN; 2740 return (100); 2741 } 2742 } 2743 failed: 2744 return (ds->error = ARCHIVE_FAILED); 2745 } 2746 2747 static int 2748 lzx_decode_blocks(struct lzx_stream *strm, int last) 2749 { 2750 struct lzx_dec *ds = strm->ds; 2751 struct lzx_br bre = ds->br; 2752 struct huffman *at = &(ds->at), *lt = &(ds->lt), *mt = &(ds->mt); 2753 const struct lzx_pos_tbl *pos_tbl = ds->pos_tbl; 2754 unsigned char *noutp = strm->next_out; 2755 unsigned char *endp = noutp + strm->avail_out; 2756 unsigned char *w_buff = ds->w_buff; 2757 unsigned char *at_bitlen = at->bitlen; 2758 unsigned char *lt_bitlen = lt->bitlen; 2759 unsigned char *mt_bitlen = mt->bitlen; 2760 size_t block_bytes_avail = ds->block_bytes_avail; 2761 int at_max_bits = at->max_bits; 2762 int lt_max_bits = lt->max_bits; 2763 int mt_max_bits = mt->max_bits; 2764 int c, copy_len = ds->copy_len, copy_pos = ds->copy_pos; 2765 int w_pos = ds->w_pos, w_mask = ds->w_mask, w_size = ds->w_size; 2766 int length_header = ds->length_header; 2767 int offset_bits = ds->offset_bits; 2768 int position_slot = ds->position_slot; 2769 int r0 = ds->r0, r1 = ds->r1, r2 = ds->r2; 2770 int state = ds->state; 2771 char block_type = ds->block_type; 2772 2773 for (;;) { 2774 switch (state) { 2775 case ST_MAIN: 2776 for (;;) { 2777 if (block_bytes_avail == 0) { 2778 /* This block ended. */ 2779 ds->state = ST_RD_BLOCK_TYPE; 2780 ds->br = bre; 2781 ds->block_bytes_avail = 2782 block_bytes_avail; 2783 ds->copy_len = copy_len; 2784 ds->copy_pos = copy_pos; 2785 ds->length_header = length_header; 2786 ds->position_slot = position_slot; 2787 ds->r0 = r0; ds->r1 = r1; ds->r2 = r2; 2788 ds->w_pos = w_pos; 2789 strm->avail_out = endp - noutp; 2790 return (ARCHIVE_EOF); 2791 } 2792 if (noutp >= endp) 2793 /* Output buffer is empty. */ 2794 goto next_data; 2795 2796 if (!lzx_br_read_ahead(strm, &bre, 2797 mt_max_bits)) { 2798 if (!last) 2799 goto next_data; 2800 /* Remaining bits are less than 2801 * maximum bits(mt.max_bits) but maybe 2802 * it still remains as much as we need, 2803 * so we should try to use it with 2804 * dummy bits. */ 2805 c = lzx_decode_huffman(mt, 2806 lzx_br_bits_forced( 2807 &bre, mt_max_bits)); 2808 lzx_br_consume(&bre, mt_bitlen[c]); 2809 if (!lzx_br_has(&bre, 0)) 2810 goto failed;/* Over read. */ 2811 } else { 2812 c = lzx_decode_huffman(mt, 2813 lzx_br_bits(&bre, mt_max_bits)); 2814 lzx_br_consume(&bre, mt_bitlen[c]); 2815 } 2816 if (c > UCHAR_MAX) 2817 break; 2818 /* 2819 * 'c' is exactly literal code. 2820 */ 2821 /* Save a decoded code to reference it 2822 * afterward. */ 2823 w_buff[w_pos] = c; 2824 w_pos = (w_pos + 1) & w_mask; 2825 /* Store the decoded code to output buffer. */ 2826 *noutp++ = c; 2827 block_bytes_avail--; 2828 } 2829 /* 2830 * Get a match code, its length and offset. 2831 */ 2832 c -= UCHAR_MAX + 1; 2833 length_header = c & 7; 2834 position_slot = c >> 3; 2835 /* FALL THROUGH */ 2836 case ST_LENGTH: 2837 /* 2838 * Get a length. 2839 */ 2840 if (length_header == 7) { 2841 if (!lzx_br_read_ahead(strm, &bre, 2842 lt_max_bits)) { 2843 if (!last) { 2844 state = ST_LENGTH; 2845 goto next_data; 2846 } 2847 c = lzx_decode_huffman(lt, 2848 lzx_br_bits_forced( 2849 &bre, lt_max_bits)); 2850 lzx_br_consume(&bre, lt_bitlen[c]); 2851 if (!lzx_br_has(&bre, 0)) 2852 goto failed;/* Over read. */ 2853 } else { 2854 c = lzx_decode_huffman(lt, 2855 lzx_br_bits(&bre, lt_max_bits)); 2856 lzx_br_consume(&bre, lt_bitlen[c]); 2857 } 2858 copy_len = c + 7 + 2; 2859 } else 2860 copy_len = length_header + 2; 2861 if ((size_t)copy_len > block_bytes_avail) 2862 goto failed; 2863 /* 2864 * Get an offset. 2865 */ 2866 switch (position_slot) { 2867 case 0: /* Use repeated offset 0. */ 2868 copy_pos = r0; 2869 state = ST_REAL_POS; 2870 continue; 2871 case 1: /* Use repeated offset 1. */ 2872 copy_pos = r1; 2873 /* Swap repeated offset. */ 2874 r1 = r0; 2875 r0 = copy_pos; 2876 state = ST_REAL_POS; 2877 continue; 2878 case 2: /* Use repeated offset 2. */ 2879 copy_pos = r2; 2880 /* Swap repeated offset. */ 2881 r2 = r0; 2882 r0 = copy_pos; 2883 state = ST_REAL_POS; 2884 continue; 2885 default: 2886 offset_bits = 2887 pos_tbl[position_slot].footer_bits; 2888 break; 2889 } 2890 /* FALL THROUGH */ 2891 case ST_OFFSET: 2892 /* 2893 * Get the offset, which is a distance from 2894 * current window position. 2895 */ 2896 if (block_type == ALIGNED_OFFSET_BLOCK && 2897 offset_bits >= 3) { 2898 int offbits = offset_bits - 3; 2899 2900 if (!lzx_br_read_ahead(strm, &bre, offbits)) { 2901 state = ST_OFFSET; 2902 if (last) 2903 goto failed; 2904 goto next_data; 2905 } 2906 copy_pos = lzx_br_bits(&bre, offbits) << 3; 2907 2908 /* Get an aligned number. */ 2909 if (!lzx_br_read_ahead(strm, &bre, 2910 offbits + at_max_bits)) { 2911 if (!last) { 2912 state = ST_OFFSET; 2913 goto next_data; 2914 } 2915 lzx_br_consume(&bre, offbits); 2916 c = lzx_decode_huffman(at, 2917 lzx_br_bits_forced(&bre, 2918 at_max_bits)); 2919 lzx_br_consume(&bre, at_bitlen[c]); 2920 if (!lzx_br_has(&bre, 0)) 2921 goto failed;/* Over read. */ 2922 } else { 2923 lzx_br_consume(&bre, offbits); 2924 c = lzx_decode_huffman(at, 2925 lzx_br_bits(&bre, at_max_bits)); 2926 lzx_br_consume(&bre, at_bitlen[c]); 2927 } 2928 /* Add an aligned number. */ 2929 copy_pos += c; 2930 } else { 2931 if (!lzx_br_read_ahead(strm, &bre, 2932 offset_bits)) { 2933 state = ST_OFFSET; 2934 if (last) 2935 goto failed; 2936 goto next_data; 2937 } 2938 copy_pos = lzx_br_bits(&bre, offset_bits); 2939 lzx_br_consume(&bre, offset_bits); 2940 } 2941 copy_pos += pos_tbl[position_slot].base -2; 2942 2943 /* Update repeated offset LRU queue. */ 2944 r2 = r1; 2945 r1 = r0; 2946 r0 = copy_pos; 2947 /* FALL THROUGH */ 2948 case ST_REAL_POS: 2949 /* 2950 * Compute a real position in window. 2951 */ 2952 copy_pos = (w_pos - copy_pos) & w_mask; 2953 /* FALL THROUGH */ 2954 case ST_COPY: 2955 /* 2956 * Copy several bytes as extracted data from the window 2957 * into the output buffer. 2958 */ 2959 for (;;) { 2960 const unsigned char *s; 2961 int l; 2962 2963 l = copy_len; 2964 if (copy_pos > w_pos) { 2965 if (l > w_size - copy_pos) 2966 l = w_size - copy_pos; 2967 } else { 2968 if (l > w_size - w_pos) 2969 l = w_size - w_pos; 2970 } 2971 if (noutp + l >= endp) 2972 l = (int)(endp - noutp); 2973 s = w_buff + copy_pos; 2974 if (l >= 8 && ((copy_pos + l < w_pos) 2975 || (w_pos + l < copy_pos))) { 2976 memcpy(w_buff + w_pos, s, l); 2977 memcpy(noutp, s, l); 2978 } else { 2979 unsigned char *d; 2980 int li; 2981 2982 d = w_buff + w_pos; 2983 for (li = 0; li < l; li++) 2984 noutp[li] = d[li] = s[li]; 2985 } 2986 noutp += l; 2987 copy_pos = (copy_pos + l) & w_mask; 2988 w_pos = (w_pos + l) & w_mask; 2989 block_bytes_avail -= l; 2990 if (copy_len <= l) 2991 /* A copy of current pattern ended. */ 2992 break; 2993 copy_len -= l; 2994 if (noutp >= endp) { 2995 /* Output buffer is empty. */ 2996 state = ST_COPY; 2997 goto next_data; 2998 } 2999 } 3000 state = ST_MAIN; 3001 break; 3002 } 3003 } 3004 failed: 3005 return (ds->error = ARCHIVE_FAILED); 3006 next_data: 3007 ds->br = bre; 3008 ds->block_bytes_avail = block_bytes_avail; 3009 ds->copy_len = copy_len; 3010 ds->copy_pos = copy_pos; 3011 ds->length_header = length_header; 3012 ds->offset_bits = offset_bits; 3013 ds->position_slot = position_slot; 3014 ds->r0 = r0; ds->r1 = r1; ds->r2 = r2; 3015 ds->state = state; 3016 ds->w_pos = w_pos; 3017 strm->avail_out = endp - noutp; 3018 return (ARCHIVE_OK); 3019 } 3020 3021 static int 3022 lzx_read_pre_tree(struct lzx_stream *strm) 3023 { 3024 struct lzx_dec *ds = strm->ds; 3025 struct lzx_br *br = &(ds->br); 3026 int i; 3027 3028 if (ds->loop == 0) 3029 memset(ds->pt.freq, 0, sizeof(ds->pt.freq)); 3030 for (i = ds->loop; i < ds->pt.len_size; i++) { 3031 if (!lzx_br_read_ahead(strm, br, 4)) { 3032 ds->loop = i; 3033 return (0); 3034 } 3035 ds->pt.bitlen[i] = lzx_br_bits(br, 4); 3036 ds->pt.freq[ds->pt.bitlen[i]]++; 3037 lzx_br_consume(br, 4); 3038 } 3039 ds->loop = i; 3040 return (1); 3041 } 3042 3043 /* 3044 * Read a bunch of bit-lengths from pre-tree. 3045 */ 3046 static int 3047 lzx_read_bitlen(struct lzx_stream *strm, struct huffman *d, int end) 3048 { 3049 struct lzx_dec *ds = strm->ds; 3050 struct lzx_br *br = &(ds->br); 3051 int c, i, j, ret, same; 3052 unsigned rbits; 3053 3054 i = ds->loop; 3055 if (i == 0) 3056 memset(d->freq, 0, sizeof(d->freq)); 3057 ret = 0; 3058 if (end < 0) 3059 end = d->len_size; 3060 while (i < end) { 3061 ds->loop = i; 3062 if (!lzx_br_read_ahead(strm, br, ds->pt.max_bits)) 3063 goto getdata; 3064 rbits = lzx_br_bits(br, ds->pt.max_bits); 3065 c = lzx_decode_huffman(&(ds->pt), rbits); 3066 switch (c) { 3067 case 17:/* several zero lengths, from 4 to 19. */ 3068 if (!lzx_br_read_ahead(strm, br, ds->pt.bitlen[c]+4)) 3069 goto getdata; 3070 lzx_br_consume(br, ds->pt.bitlen[c]); 3071 same = lzx_br_bits(br, 4) + 4; 3072 if (i + same > end) 3073 return (-1);/* Invalid */ 3074 lzx_br_consume(br, 4); 3075 for (j = 0; j < same; j++) 3076 d->bitlen[i++] = 0; 3077 break; 3078 case 18:/* many zero lengths, from 20 to 51. */ 3079 if (!lzx_br_read_ahead(strm, br, ds->pt.bitlen[c]+5)) 3080 goto getdata; 3081 lzx_br_consume(br, ds->pt.bitlen[c]); 3082 same = lzx_br_bits(br, 5) + 20; 3083 if (i + same > end) 3084 return (-1);/* Invalid */ 3085 lzx_br_consume(br, 5); 3086 memset(d->bitlen + i, 0, same); 3087 i += same; 3088 break; 3089 case 19:/* a few same lengths. */ 3090 if (!lzx_br_read_ahead(strm, br, 3091 ds->pt.bitlen[c]+1+ds->pt.max_bits)) 3092 goto getdata; 3093 lzx_br_consume(br, ds->pt.bitlen[c]); 3094 same = lzx_br_bits(br, 1) + 4; 3095 if (i + same > end) 3096 return (-1); 3097 lzx_br_consume(br, 1); 3098 rbits = lzx_br_bits(br, ds->pt.max_bits); 3099 c = lzx_decode_huffman(&(ds->pt), rbits); 3100 lzx_br_consume(br, ds->pt.bitlen[c]); 3101 c = (d->bitlen[i] - c + 17) % 17; 3102 if (c < 0) 3103 return (-1);/* Invalid */ 3104 for (j = 0; j < same; j++) 3105 d->bitlen[i++] = c; 3106 d->freq[c] += same; 3107 break; 3108 default: 3109 lzx_br_consume(br, ds->pt.bitlen[c]); 3110 c = (d->bitlen[i] - c + 17) % 17; 3111 if (c < 0) 3112 return (-1);/* Invalid */ 3113 d->freq[c]++; 3114 d->bitlen[i++] = c; 3115 break; 3116 } 3117 } 3118 ret = 1; 3119 getdata: 3120 ds->loop = i; 3121 return (ret); 3122 } 3123 3124 static int 3125 lzx_huffman_init(struct huffman *hf, size_t len_size, int tbl_bits) 3126 { 3127 int bits; 3128 3129 if (hf->bitlen == NULL || hf->len_size != (int)len_size) { 3130 free(hf->bitlen); 3131 hf->bitlen = calloc(len_size, sizeof(hf->bitlen[0])); 3132 if (hf->bitlen == NULL) 3133 return (ARCHIVE_FATAL); 3134 hf->len_size = (int)len_size; 3135 } else 3136 memset(hf->bitlen, 0, len_size * sizeof(hf->bitlen[0])); 3137 if (hf->tbl == NULL) { 3138 if (tbl_bits < HTBL_BITS) 3139 bits = tbl_bits; 3140 else 3141 bits = HTBL_BITS; 3142 hf->tbl = malloc(((size_t)1 << bits) * sizeof(hf->tbl[0])); 3143 if (hf->tbl == NULL) 3144 return (ARCHIVE_FATAL); 3145 hf->tbl_bits = tbl_bits; 3146 } 3147 if (hf->tree == NULL && tbl_bits > HTBL_BITS) { 3148 hf->tree_avail = 1 << (tbl_bits - HTBL_BITS + 4); 3149 hf->tree = malloc(hf->tree_avail * sizeof(hf->tree[0])); 3150 if (hf->tree == NULL) 3151 return (ARCHIVE_FATAL); 3152 } 3153 return (ARCHIVE_OK); 3154 } 3155 3156 static void 3157 lzx_huffman_free(struct huffman *hf) 3158 { 3159 free(hf->bitlen); 3160 free(hf->tbl); 3161 free(hf->tree); 3162 } 3163 3164 /* 3165 * Make a huffman coding table. 3166 */ 3167 static int 3168 lzx_make_huffman_table(struct huffman *hf) 3169 { 3170 uint16_t *tbl; 3171 const unsigned char *bitlen; 3172 int bitptn[17], weight[17]; 3173 int i, maxbits = 0, ptn, tbl_size, w; 3174 int diffbits, len_avail; 3175 3176 /* 3177 * Initialize bit patterns. 3178 */ 3179 ptn = 0; 3180 for (i = 1, w = 1 << 15; i <= 16; i++, w >>= 1) { 3181 bitptn[i] = ptn; 3182 weight[i] = w; 3183 if (hf->freq[i]) { 3184 ptn += hf->freq[i] * w; 3185 maxbits = i; 3186 } 3187 } 3188 if ((ptn & 0xffff) != 0 || maxbits > hf->tbl_bits) 3189 return (0);/* Invalid */ 3190 3191 hf->max_bits = maxbits; 3192 3193 /* 3194 * Cut out extra bits which we won't house in the table. 3195 * This preparation reduces the same calculation in the for-loop 3196 * making the table. 3197 */ 3198 if (maxbits < 16) { 3199 int ebits = 16 - maxbits; 3200 for (i = 1; i <= maxbits; i++) { 3201 bitptn[i] >>= ebits; 3202 weight[i] >>= ebits; 3203 } 3204 } 3205 if (maxbits > HTBL_BITS) { 3206 int htbl_max; 3207 uint16_t *p; 3208 3209 diffbits = maxbits - HTBL_BITS; 3210 for (i = 1; i <= HTBL_BITS; i++) { 3211 bitptn[i] >>= diffbits; 3212 weight[i] >>= diffbits; 3213 } 3214 htbl_max = bitptn[HTBL_BITS] + 3215 weight[HTBL_BITS] * hf->freq[HTBL_BITS]; 3216 p = &(hf->tbl[htbl_max]); 3217 while (p < &hf->tbl[1U<<HTBL_BITS]) 3218 *p++ = 0; 3219 } else 3220 diffbits = 0; 3221 hf->shift_bits = diffbits; 3222 3223 /* 3224 * Make the table. 3225 */ 3226 tbl_size = 1 << HTBL_BITS; 3227 tbl = hf->tbl; 3228 bitlen = hf->bitlen; 3229 len_avail = hf->len_size; 3230 hf->tree_used = 0; 3231 for (i = 0; i < len_avail; i++) { 3232 uint16_t *p; 3233 int len, cnt; 3234 uint16_t bit; 3235 int extlen; 3236 struct htree_t *ht; 3237 3238 if (bitlen[i] == 0) 3239 continue; 3240 /* Get a bit pattern */ 3241 len = bitlen[i]; 3242 ptn = bitptn[len]; 3243 cnt = weight[len]; 3244 if (len <= HTBL_BITS) { 3245 /* Calculate next bit pattern */ 3246 if ((bitptn[len] = ptn + cnt) > tbl_size) 3247 return (0);/* Invalid */ 3248 /* Update the table */ 3249 p = &(tbl[ptn]); 3250 while (--cnt >= 0) 3251 p[cnt] = (uint16_t)i; 3252 continue; 3253 } 3254 3255 /* 3256 * A bit length is too big to be housed to a direct table, 3257 * so we use a tree model for its extra bits. 3258 */ 3259 bitptn[len] = ptn + cnt; 3260 bit = 1U << (diffbits -1); 3261 extlen = len - HTBL_BITS; 3262 3263 p = &(tbl[ptn >> diffbits]); 3264 if (*p == 0) { 3265 *p = len_avail + hf->tree_used; 3266 ht = &(hf->tree[hf->tree_used++]); 3267 if (hf->tree_used > hf->tree_avail) 3268 return (0);/* Invalid */ 3269 ht->left = 0; 3270 ht->right = 0; 3271 } else { 3272 if (*p < len_avail || 3273 *p >= (len_avail + hf->tree_used)) 3274 return (0);/* Invalid */ 3275 ht = &(hf->tree[*p - len_avail]); 3276 } 3277 while (--extlen > 0) { 3278 if (ptn & bit) { 3279 if (ht->left < len_avail) { 3280 ht->left = len_avail + hf->tree_used; 3281 ht = &(hf->tree[hf->tree_used++]); 3282 if (hf->tree_used > hf->tree_avail) 3283 return (0);/* Invalid */ 3284 ht->left = 0; 3285 ht->right = 0; 3286 } else { 3287 ht = &(hf->tree[ht->left - len_avail]); 3288 } 3289 } else { 3290 if (ht->right < len_avail) { 3291 ht->right = len_avail + hf->tree_used; 3292 ht = &(hf->tree[hf->tree_used++]); 3293 if (hf->tree_used > hf->tree_avail) 3294 return (0);/* Invalid */ 3295 ht->left = 0; 3296 ht->right = 0; 3297 } else { 3298 ht = &(hf->tree[ht->right - len_avail]); 3299 } 3300 } 3301 bit >>= 1; 3302 } 3303 if (ptn & bit) { 3304 if (ht->left != 0) 3305 return (0);/* Invalid */ 3306 ht->left = (uint16_t)i; 3307 } else { 3308 if (ht->right != 0) 3309 return (0);/* Invalid */ 3310 ht->right = (uint16_t)i; 3311 } 3312 } 3313 return (1); 3314 } 3315 3316 static int 3317 lzx_decode_huffman_tree(struct huffman *hf, unsigned rbits, int c) 3318 { 3319 struct htree_t *ht; 3320 int extlen; 3321 3322 ht = hf->tree; 3323 extlen = hf->shift_bits; 3324 while (c >= hf->len_size) { 3325 c -= hf->len_size; 3326 if (extlen-- <= 0 || c >= hf->tree_used) 3327 return (0); 3328 if (rbits & (1U << extlen)) 3329 c = ht[c].left; 3330 else 3331 c = ht[c].right; 3332 } 3333 return (c); 3334 } 3335 3336 static inline int 3337 lzx_decode_huffman(struct huffman *hf, unsigned rbits) 3338 { 3339 int c; 3340 /* 3341 * At first search an index table for a bit pattern. 3342 * If it fails, search a huffman tree for. 3343 */ 3344 c = hf->tbl[rbits >> hf->shift_bits]; 3345 if (c < hf->len_size) 3346 return (c); 3347 /* This bit pattern needs to be found out at a huffman tree. */ 3348 return (lzx_decode_huffman_tree(hf, rbits, c)); 3349 } 3350 3351