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