contrib/libarchive/libarchive/archive_read_support_format_cab.c

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