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         }
2114
2115         for (footer = 0; footer < 18; footer++)
2116                 base_inc[footer] = 1 << footer;
2117         base = footer = 0;
2118         for (slot = 0; slot < w_slot; slot++) {
2119                 int n;
2120                 if (footer == 0)
2121                         base = slot;
2122                 else
2123                         base += base_inc[footer];
2124                 if (footer < 17) {
2125                         footer = -2;
2126                         for (n = base; n; n >>= 1)
2127                                 footer++;
2128                         if (footer <= 0)
2129                                 footer = 0;
2130                 }
2131                 ds->pos_tbl[slot].base = base;
2132                 ds->pos_tbl[slot].footer_bits = footer;
2133         }
2134
2135         ds->w_pos = 0;
2136         ds->state = 0;
2137         ds->br.cache_buffer = 0;
2138         ds->br.cache_avail = 0;
2139         ds->r0 = ds->r1 = ds->r2 = 1;
2140
2141         /* Initialize aligned offset tree. */
2142         if (lzx_huffman_init(&(ds->at), 8, 8) != ARCHIVE_OK)
2143                 return (ARCHIVE_FATAL);
2144
2145         /* Initialize pre-tree. */
2146         if (lzx_huffman_init(&(ds->pt), 20, 10) != ARCHIVE_OK)
2147                 return (ARCHIVE_FATAL);
2148
2149         /* Initialize Main tree. */
2150         if (lzx_huffman_init(&(ds->mt), 256+(w_slot<<3), 16)
2151             != ARCHIVE_OK)
2152                 return (ARCHIVE_FATAL);
2153
2154         /* Initialize Length tree. */
2155         if (lzx_huffman_init(&(ds->lt), 249, 16) != ARCHIVE_OK)
2156                 return (ARCHIVE_FATAL);
2157
2158         ds->error = 0;
2159
2160         return (ARCHIVE_OK);
2161 }
2162
2163 /*
2164  * Release LZX decoder.
2165  */
2166 static void
2167 lzx_decode_free(struct lzx_stream *strm)
2168 {
2169
2170         if (strm->ds == NULL)
2171                 return;
2172         free(strm->ds->w_buff);
2173         free(strm->ds->pos_tbl);
2174         lzx_huffman_free(&(strm->ds->at));
2175         lzx_huffman_free(&(strm->ds->pt));
2176         lzx_huffman_free(&(strm->ds->mt));
2177         lzx_huffman_free(&(strm->ds->lt));
2178         free(strm->ds);
2179         strm->ds = NULL;
2180 }
2181
2182 /*
2183  * E8 Call Translation reversal.
2184  */
2185 static void
2186 lzx_translation(struct lzx_stream *strm, void *p, size_t size, uint32_t offset)
2187 {
2188         struct lzx_dec *ds = strm->ds;
2189         unsigned char *b, *end;
2190
2191         if (!ds->translation || size <= 10)
2192                 return;
2193         b = p;
2194         end = b + size - 10;
2195         while (b < end && (b = memchr(b, 0xE8, end - b)) != NULL) {
2196                 size_t i = b - (unsigned char *)p;
2197                 int32_t cp, displacement, value;
2198
2199                 cp = (int32_t)(offset + (uint32_t)i);
2200                 value = archive_le32dec(&b[1]);
2201                 if (value >= -cp && value < (int32_t)ds->translation_size) {
2202                         if (value >= 0)
2203                                 displacement = value - cp;
2204                         else
2205                                 displacement = value + ds->translation_size;
2206                         archive_le32enc(&b[1], (uint32_t)displacement);
2207                 }
2208                 b += 5;
2209         }
2210 }
2211
2212 /*
2213  * Bit stream reader.
2214  */
2215 /* Check that the cache buffer has enough bits. */
2216 #define lzx_br_has(br, n)       ((br)->cache_avail >= n)
2217 /* Get compressed data by bit. */
2218 #define lzx_br_bits(br, n)                              \
2219         (((uint32_t)((br)->cache_buffer >>              \
2220                 ((br)->cache_avail - (n)))) & cache_masks[n])
2221 #define lzx_br_bits_forced(br, n)                       \
2222         (((uint32_t)((br)->cache_buffer <<              \
2223                 ((n) - (br)->cache_avail))) & cache_masks[n])
2224 /* Read ahead to make sure the cache buffer has enough compressed data we
2225  * will use.
2226  *  True  : completed, there is enough data in the cache buffer.
2227  *  False : we met that strm->next_in is empty, we have to get following
2228  *          bytes. */
2229 #define lzx_br_read_ahead_0(strm, br, n)        \
2230         (lzx_br_has((br), (n)) || lzx_br_fillup(strm, br))
2231 /*  True  : the cache buffer has some bits as much as we need.
2232  *  False : there are no enough bits in the cache buffer to be used,
2233  *          we have to get following bytes if we could. */
2234 #define lzx_br_read_ahead(strm, br, n)  \
2235         (lzx_br_read_ahead_0((strm), (br), (n)) || lzx_br_has((br), (n)))
2236
2237 /* Notify how many bits we consumed. */
2238 #define lzx_br_consume(br, n)   ((br)->cache_avail -= (n))
2239 #define lzx_br_consume_unaligned_bits(br) ((br)->cache_avail &= ~0x0f)
2240
2241 #define lzx_br_is_unaligned(br) ((br)->cache_avail & 0x0f)
2242
2243 static const uint32_t cache_masks[] = {
2244         0x00000000, 0x00000001, 0x00000003, 0x00000007,
2245         0x0000000F, 0x0000001F, 0x0000003F, 0x0000007F,
2246         0x000000FF, 0x000001FF, 0x000003FF, 0x000007FF,
2247         0x00000FFF, 0x00001FFF, 0x00003FFF, 0x00007FFF,
2248         0x0000FFFF, 0x0001FFFF, 0x0003FFFF, 0x0007FFFF,
2249         0x000FFFFF, 0x001FFFFF, 0x003FFFFF, 0x007FFFFF,
2250         0x00FFFFFF, 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF,
2251         0x0FFFFFFF, 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF,
2252         0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
2253 };
2254
2255 /*
2256  * Shift away used bits in the cache data and fill it up with following bits.
2257  * Call this when cache buffer does not have enough bits you need.
2258  *
2259  * Returns 1 if the cache buffer is full.
2260  * Returns 0 if the cache buffer is not full; input buffer is empty.
2261  */
2262 static int
2263 lzx_br_fillup(struct lzx_stream *strm, struct lzx_br *br)
2264 {
2265 /*
2266  * x86 processor family can read misaligned data without an access error.
2267  */
2268         int n = CACHE_BITS - br->cache_avail;
2269
2270         for (;;) {
2271                 switch (n >> 4) {
2272                 case 4:
2273                         if (strm->avail_in >= 8) {
2274                                 br->cache_buffer =
2275                                     ((uint64_t)strm->next_in[1]) << 56 |
2276                                     ((uint64_t)strm->next_in[0]) << 48 |
2277                                     ((uint64_t)strm->next_in[3]) << 40 |
2278                                     ((uint64_t)strm->next_in[2]) << 32 |
2279                                     ((uint32_t)strm->next_in[5]) << 24 |
2280                                     ((uint32_t)strm->next_in[4]) << 16 |
2281                                     ((uint32_t)strm->next_in[7]) << 8 |
2282                                      (uint32_t)strm->next_in[6];
2283                                 strm->next_in += 8;
2284                                 strm->avail_in -= 8;
2285                                 br->cache_avail += 8 * 8;
2286                                 return (1);
2287                         }
2288                         break;
2289                 case 3:
2290                         if (strm->avail_in >= 6) {
2291                                 br->cache_buffer =
2292                                    (br->cache_buffer << 48) |
2293                                     ((uint64_t)strm->next_in[1]) << 40 |
2294                                     ((uint64_t)strm->next_in[0]) << 32 |
2295                                     ((uint32_t)strm->next_in[3]) << 24 |
2296                                     ((uint32_t)strm->next_in[2]) << 16 |
2297                                     ((uint32_t)strm->next_in[5]) << 8 |
2298                                      (uint32_t)strm->next_in[4];
2299                                 strm->next_in += 6;
2300                                 strm->avail_in -= 6;
2301                                 br->cache_avail += 6 * 8;
2302                                 return (1);
2303                         }
2304                         break;
2305                 case 0:
2306                         /* We have enough compressed data in
2307                          * the cache buffer.*/
2308                         return (1);
2309                 default:
2310                         break;
2311                 }
2312                 if (strm->avail_in < 2) {
2313                         /* There is not enough compressed data to
2314                          * fill up the cache buffer. */
2315                         if (strm->avail_in == 1) {
2316                                 br->odd = *strm->next_in++;
2317                                 strm->avail_in--;
2318                                 br->have_odd = 1;
2319                         }
2320                         return (0);
2321                 }
2322                 br->cache_buffer =
2323                    (br->cache_buffer << 16) |
2324                     archive_le16dec(strm->next_in);
2325                 strm->next_in += 2;
2326                 strm->avail_in -= 2;
2327                 br->cache_avail += 16;
2328                 n -= 16;
2329         }
2330 }
2331
2332 static void
2333 lzx_br_fixup(struct lzx_stream *strm, struct lzx_br *br)
2334 {
2335         int n = CACHE_BITS - br->cache_avail;
2336
2337         if (br->have_odd && n >= 16 && strm->avail_in > 0) {
2338                 br->cache_buffer =
2339                    (br->cache_buffer << 16) |
2340                    ((uint16_t)(*strm->next_in)) << 8 | br->odd;
2341                 strm->next_in++;
2342                 strm->avail_in--;
2343                 br->cache_avail += 16;
2344                 br->have_odd = 0;
2345         }
2346 }
2347
2348 static void
2349 lzx_cleanup_bitstream(struct lzx_stream *strm)
2350 {
2351         strm->ds->br.cache_avail = 0;
2352         strm->ds->br.have_odd = 0;
2353 }
2354
2355 /*
2356  * Decode LZX.
2357  *
2358  * 1. Returns ARCHIVE_OK if output buffer or input buffer are empty.
2359  *    Please set available buffer and call this function again.
2360  * 2. Returns ARCHIVE_EOF if decompression has been completed.
2361  * 3. Returns ARCHIVE_FAILED if an error occurred; compressed data
2362  *    is broken or you do not set 'last' flag properly.
2363  */
2364 #define ST_RD_TRANSLATION       0
2365 #define ST_RD_TRANSLATION_SIZE  1
2366 #define ST_RD_BLOCK_TYPE        2
2367 #define ST_RD_BLOCK_SIZE        3
2368 #define ST_RD_ALIGNMENT         4
2369 #define ST_RD_R0                5
2370 #define ST_RD_R1                6
2371 #define ST_RD_R2                7
2372 #define ST_COPY_UNCOMP1         8
2373 #define ST_COPY_UNCOMP2         9
2374 #define ST_RD_ALIGNED_OFFSET    10
2375 #define ST_RD_VERBATIM          11
2376 #define ST_RD_PRE_MAIN_TREE_256 12
2377 #define ST_MAIN_TREE_256        13
2378 #define ST_RD_PRE_MAIN_TREE_REM 14
2379 #define ST_MAIN_TREE_REM        15
2380 #define ST_RD_PRE_LENGTH_TREE   16
2381 #define ST_LENGTH_TREE          17
2382 #define ST_MAIN                 18
2383 #define ST_LENGTH               19
2384 #define ST_OFFSET               20
2385 #define ST_REAL_POS             21
2386 #define ST_COPY                 22
2387
2388 static int
2389 lzx_decode(struct lzx_stream *strm, int last)
2390 {
2391         struct lzx_dec *ds = strm->ds;
2392         int64_t avail_in;
2393         int r;
2394
2395         if (ds->error)
2396                 return (ds->error);
2397
2398         avail_in = strm->avail_in;
2399         lzx_br_fixup(strm, &(ds->br));
2400         do {
2401                 if (ds->state < ST_MAIN)
2402                         r = lzx_read_blocks(strm, last);
2403                 else {
2404                         int64_t bytes_written = strm->avail_out;
2405                         r = lzx_decode_blocks(strm, last);
2406                         bytes_written -= strm->avail_out;
2407                         strm->next_out += bytes_written;
2408                         strm->total_out += bytes_written;
2409                 }
2410         } while (r == 100);
2411         strm->total_in += avail_in - strm->avail_in;
2412         return (r);
2413 }
2414
2415 static int
2416 lzx_read_blocks(struct lzx_stream *strm, int last)
2417 {
2418         struct lzx_dec *ds = strm->ds;
2419         struct lzx_br *br = &(ds->br);
2420         int i, r;
2421
2422         for (;;) {
2423                 switch (ds->state) {
2424                 case ST_RD_TRANSLATION:
2425                         if (!lzx_br_read_ahead(strm, br, 1)) {
2426                                 ds->state = ST_RD_TRANSLATION;
2427                                 if (last)
2428                                         goto failed;
2429                                 return (ARCHIVE_OK);
2430                         }
2431                         ds->translation = lzx_br_bits(br, 1);
2432                         lzx_br_consume(br, 1);
2433                         /* FALL THROUGH */
2434                 case ST_RD_TRANSLATION_SIZE:
2435                         if (ds->translation) {
2436                                 if (!lzx_br_read_ahead(strm, br, 32)) {
2437                                         ds->state = ST_RD_TRANSLATION_SIZE;
2438                                         if (last)
2439                                                 goto failed;
2440                                         return (ARCHIVE_OK);
2441                                 }
2442                                 ds->translation_size = lzx_br_bits(br, 16);
2443                                 lzx_br_consume(br, 16);
2444                                 ds->translation_size <<= 16;
2445                                 ds->translation_size |= lzx_br_bits(br, 16);
2446                                 lzx_br_consume(br, 16);
2447                         }
2448                         /* FALL THROUGH */
2449                 case ST_RD_BLOCK_TYPE:
2450                         if (!lzx_br_read_ahead(strm, br, 3)) {
2451                                 ds->state = ST_RD_BLOCK_TYPE;
2452                                 if (last)
2453                                         goto failed;
2454                                 return (ARCHIVE_OK);
2455                         }
2456                         ds->block_type = lzx_br_bits(br, 3);
2457                         lzx_br_consume(br, 3);
2458                         /* Check a block type. */
2459                         switch (ds->block_type) {
2460                         case VERBATIM_BLOCK:
2461                         case ALIGNED_OFFSET_BLOCK:
2462                         case UNCOMPRESSED_BLOCK:
2463                                 break;
2464                         default:
2465                                 goto failed;/* Invalid */
2466                         }
2467                         /* FALL THROUGH */
2468                 case ST_RD_BLOCK_SIZE:
2469                         if (!lzx_br_read_ahead(strm, br, 24)) {
2470                                 ds->state = ST_RD_BLOCK_SIZE;
2471                                 if (last)
2472                                         goto failed;
2473                                 return (ARCHIVE_OK);
2474                         }
2475                         ds->block_size = lzx_br_bits(br, 8);
2476                         lzx_br_consume(br, 8);
2477                         ds->block_size <<= 16;
2478                         ds->block_size |= lzx_br_bits(br, 16);
2479                         lzx_br_consume(br, 16);
2480                         if (ds->block_size == 0)
2481                                 goto failed;
2482                         ds->block_bytes_avail = ds->block_size;
2483                         if (ds->block_type != UNCOMPRESSED_BLOCK) {
2484                                 if (ds->block_type == VERBATIM_BLOCK)
2485                                         ds->state = ST_RD_VERBATIM;
2486                                 else
2487                                         ds->state = ST_RD_ALIGNED_OFFSET;
2488                                 break;
2489                         }
2490                         /* FALL THROUGH */
2491                 case ST_RD_ALIGNMENT:
2492                         /*
2493                          * Handle an Uncompressed Block.
2494                          */
2495                         /* Skip padding to align following field on
2496                          * 16-bit boundary. */
2497                         if (lzx_br_is_unaligned(br))
2498                                 lzx_br_consume_unaligned_bits(br);
2499                         else {
2500                                 if (lzx_br_read_ahead(strm, br, 16))
2501                                         lzx_br_consume(br, 16);
2502                                 else {
2503                                         ds->state = ST_RD_ALIGNMENT;
2504                                         if (last)
2505                                                 goto failed;
2506                                         return (ARCHIVE_OK);
2507                                 }
2508                         }
2509                         /* Preparation to read repeated offsets R0,R1 and R2. */
2510                         ds->rbytes_avail = 0;
2511                         ds->state = ST_RD_R0;
2512                         /* FALL THROUGH */
2513                 case ST_RD_R0:
2514                 case ST_RD_R1:
2515                 case ST_RD_R2:
2516                         do {
2517                                 uint16_t u16;
2518                                 /* Drain bits in the cache buffer of
2519                                  * bit-stream. */
2520                                 if (lzx_br_has(br, 32)) {
2521                                         u16 = lzx_br_bits(br, 16);
2522                                         lzx_br_consume(br, 16);
2523                                         archive_le16enc(ds->rbytes, u16);
2524                                         u16 = lzx_br_bits(br, 16);
2525                                         lzx_br_consume(br, 16);
2526                                         archive_le16enc(ds->rbytes+2, u16);
2527                                         ds->rbytes_avail = 4;
2528                                 } else if (lzx_br_has(br, 16)) {
2529                                         u16 = lzx_br_bits(br, 16);
2530                                         lzx_br_consume(br, 16);
2531                                         archive_le16enc(ds->rbytes, u16);
2532                                         ds->rbytes_avail = 2;
2533                                 }
2534                                 if (ds->rbytes_avail < 4 && ds->br.have_odd) {
2535                                         ds->rbytes[ds->rbytes_avail++] =
2536                                             ds->br.odd;
2537                                         ds->br.have_odd = 0;
2538                                 }
2539                                 while (ds->rbytes_avail < 4) {
2540                                         if (strm->avail_in <= 0) {
2541                                                 if (last)
2542                                                         goto failed;
2543                                                 return (ARCHIVE_OK);
2544                                         }
2545                                         ds->rbytes[ds->rbytes_avail++] =
2546                                             *strm->next_in++;
2547                                         strm->avail_in--;
2548                                 }
2549                                 ds->rbytes_avail = 0;
2550                                 if (ds->state == ST_RD_R0) {
2551                                         ds->r0 = archive_le32dec(ds->rbytes);
2552                                         if (ds->r0 < 0)
2553                                                 goto failed;
2554                                         ds->state = ST_RD_R1;
2555                                 } else if (ds->state == ST_RD_R1) {
2556                                         ds->r1 = archive_le32dec(ds->rbytes);
2557                                         if (ds->r1 < 0)
2558                                                 goto failed;
2559                                         ds->state = ST_RD_R2;
2560                                 } else if (ds->state == ST_RD_R2) {
2561                                         ds->r2 = archive_le32dec(ds->rbytes);
2562                                         if (ds->r2 < 0)
2563                                                 goto failed;
2564                                         /* We've gotten all repeated offsets. */
2565                                         ds->state = ST_COPY_UNCOMP1;
2566                                 }
2567                         } while (ds->state != ST_COPY_UNCOMP1);
2568                         /* FALL THROUGH */
2569                 case ST_COPY_UNCOMP1:
2570                         /*
2571                          * Copy bytes form next_in to next_out directly.
2572                          */
2573                         while (ds->block_bytes_avail) {
2574                                 int l;
2575
2576                                 if (strm->avail_out <= 0)
2577                                         /* Output buffer is empty. */
2578                                         return (ARCHIVE_OK);
2579                                 if (strm->avail_in <= 0) {
2580                                         /* Input buffer is empty. */
2581                                         if (last)
2582                                                 goto failed;
2583                                         return (ARCHIVE_OK);
2584                                 }
2585                                 l = (int)ds->block_bytes_avail;
2586                                 if (l > ds->w_size - ds->w_pos)
2587                                         l = ds->w_size - ds->w_pos;
2588                                 if (l > strm->avail_out)
2589                                         l = (int)strm->avail_out;
2590                                 if (l > strm->avail_in)
2591                                         l = (int)strm->avail_in;
2592                                 memcpy(strm->next_out, strm->next_in, l);
2593                                 memcpy(&(ds->w_buff[ds->w_pos]),
2594                                     strm->next_in, l);
2595                                 strm->next_in += l;
2596                                 strm->avail_in -= l;
2597                                 strm->next_out += l;
2598                                 strm->avail_out -= l;
2599                                 strm->total_out += l;
2600                                 ds->w_pos = (ds->w_pos + l) & ds->w_mask;
2601                                 ds->block_bytes_avail -= l;
2602                         }
2603                         /* FALL THROUGH */
2604                 case ST_COPY_UNCOMP2:
2605                         /* Re-align; skip padding byte. */
2606                         if (ds->block_size & 1) {
2607                                 if (strm->avail_in <= 0) {
2608                                         /* Input buffer is empty. */
2609                                         ds->state = ST_COPY_UNCOMP2;
2610                                         if (last)
2611                                                 goto failed;
2612                                         return (ARCHIVE_OK);
2613                                 }
2614                                 strm->next_in++;
2615                                 strm->avail_in --;
2616                         }
2617                         /* This block ended. */
2618                         ds->state = ST_RD_BLOCK_TYPE;
2619                         return (ARCHIVE_EOF);
2620                         /********************/
2621                 case ST_RD_ALIGNED_OFFSET:
2622                         /*
2623                          * Read Aligned offset tree.
2624                          */
2625                         if (!lzx_br_read_ahead(strm, br, 3 * ds->at.len_size)) {
2626                                 ds->state = ST_RD_ALIGNED_OFFSET;
2627                                 if (last)
2628                                         goto failed;
2629                                 return (ARCHIVE_OK);
2630                         }
2631                         memset(ds->at.freq, 0, sizeof(ds->at.freq));
2632                         for (i = 0; i < ds->at.len_size; i++) {
2633                                 ds->at.bitlen[i] = lzx_br_bits(br, 3);
2634                                 ds->at.freq[ds->at.bitlen[i]]++;
2635                                 lzx_br_consume(br, 3);
2636                         }
2637                         if (!lzx_make_huffman_table(&ds->at))
2638                                 goto failed;
2639                         /* FALL THROUGH */
2640                 case ST_RD_VERBATIM:
2641                         ds->loop = 0;
2642                         /* FALL THROUGH */
2643                 case ST_RD_PRE_MAIN_TREE_256:
2644                         /*
2645                          * Read Pre-tree for first 256 elements of main tree.
2646                          */
2647                         if (!lzx_read_pre_tree(strm)) {
2648                                 ds->state = ST_RD_PRE_MAIN_TREE_256;
2649                                 if (last)
2650                                         goto failed;
2651                                 return (ARCHIVE_OK);
2652                         }
2653                         if (!lzx_make_huffman_table(&ds->pt))
2654                                 goto failed;
2655                         ds->loop = 0;
2656                         /* FALL THROUGH */
2657                 case ST_MAIN_TREE_256:
2658                         /*
2659                          * Get path lengths of first 256 elements of main tree.
2660                          */
2661                         r = lzx_read_bitlen(strm, &ds->mt, 256);
2662                         if (r < 0)
2663                                 goto failed;
2664                         else if (!r) {
2665                                 ds->state = ST_MAIN_TREE_256;
2666                                 if (last)
2667                                         goto failed;
2668                                 return (ARCHIVE_OK);
2669                         }
2670                         ds->loop = 0;
2671                         /* FALL THROUGH */
2672                 case ST_RD_PRE_MAIN_TREE_REM:
2673                         /*
2674                          * Read Pre-tree for remaining elements of main tree.
2675                          */
2676                         if (!lzx_read_pre_tree(strm)) {
2677                                 ds->state = ST_RD_PRE_MAIN_TREE_REM;
2678                                 if (last)
2679                                         goto failed;
2680                                 return (ARCHIVE_OK);
2681                         }
2682                         if (!lzx_make_huffman_table(&ds->pt))
2683                                 goto failed;
2684                         ds->loop = 256;
2685                         /* FALL THROUGH */
2686                 case ST_MAIN_TREE_REM:
2687                         /*
2688                          * Get path lengths of remaining elements of main tree.
2689                          */
2690                         r = lzx_read_bitlen(strm, &ds->mt, -1);
2691                         if (r < 0)
2692                                 goto failed;
2693                         else if (!r) {
2694                                 ds->state = ST_MAIN_TREE_REM;
2695                                 if (last)
2696                                         goto failed;
2697                                 return (ARCHIVE_OK);
2698                         }
2699                         if (!lzx_make_huffman_table(&ds->mt))
2700                                 goto failed;
2701                         ds->loop = 0;
2702                         /* FALL THROUGH */
2703                 case ST_RD_PRE_LENGTH_TREE:
2704                         /*
2705                          * Read Pre-tree for remaining elements of main tree.
2706                          */
2707                         if (!lzx_read_pre_tree(strm)) {
2708                                 ds->state = ST_RD_PRE_LENGTH_TREE;
2709                                 if (last)
2710                                         goto failed;
2711                                 return (ARCHIVE_OK);
2712                         }
2713                         if (!lzx_make_huffman_table(&ds->pt))
2714                                 goto failed;
2715                         ds->loop = 0;
2716                         /* FALL THROUGH */
2717                 case ST_LENGTH_TREE:
2718                         /*
2719                          * Get path lengths of remaining elements of main tree.
2720                          */
2721                         r = lzx_read_bitlen(strm, &ds->lt, -1);
2722                         if (r < 0)
2723                                 goto failed;
2724                         else if (!r) {
2725                                 ds->state = ST_LENGTH_TREE;
2726                                 if (last)
2727                                         goto failed;
2728                                 return (ARCHIVE_OK);
2729                         }
2730                         if (!lzx_make_huffman_table(&ds->lt))
2731                                 goto failed;
2732                         ds->state = ST_MAIN;
2733                         return (100);
2734                 }
2735         }
2736 failed:
2737         return (ds->error = ARCHIVE_FAILED);
2738 }
2739
2740 static int
2741 lzx_decode_blocks(struct lzx_stream *strm, int last)
2742 {
2743         struct lzx_dec *ds = strm->ds;
2744         struct lzx_br bre = ds->br;
2745         struct huffman *at = &(ds->at), *lt = &(ds->lt), *mt = &(ds->mt);
2746         const struct lzx_pos_tbl *pos_tbl = ds->pos_tbl;
2747         unsigned char *noutp = strm->next_out;
2748         unsigned char *endp = noutp + strm->avail_out;
2749         unsigned char *w_buff = ds->w_buff;
2750         unsigned char *at_bitlen = at->bitlen;
2751         unsigned char *lt_bitlen = lt->bitlen;
2752         unsigned char *mt_bitlen = mt->bitlen;
2753         size_t block_bytes_avail = ds->block_bytes_avail;
2754         int at_max_bits = at->max_bits;
2755         int lt_max_bits = lt->max_bits;
2756         int mt_max_bits = mt->max_bits;
2757         int c, copy_len = ds->copy_len, copy_pos = ds->copy_pos;
2758         int w_pos = ds->w_pos, w_mask = ds->w_mask, w_size = ds->w_size;
2759         int length_header = ds->length_header;
2760         int offset_bits = ds->offset_bits;
2761         int position_slot = ds->position_slot;
2762         int r0 = ds->r0, r1 = ds->r1, r2 = ds->r2;
2763         int state = ds->state;
2764         char block_type = ds->block_type;
2765
2766         for (;;) {
2767                 switch (state) {
2768                 case ST_MAIN:
2769                         for (;;) {
2770                                 if (block_bytes_avail == 0) {
2771                                         /* This block ended. */
2772                                         ds->state = ST_RD_BLOCK_TYPE;
2773                                         ds->br = bre;
2774                                         ds->block_bytes_avail =
2775                                             block_bytes_avail;
2776                                         ds->copy_len = copy_len;
2777                                         ds->copy_pos = copy_pos;
2778                                         ds->length_header = length_header;
2779                                         ds->position_slot = position_slot;
2780                                         ds->r0 = r0; ds->r1 = r1; ds->r2 = r2;
2781                                         ds->w_pos = w_pos;
2782                                         strm->avail_out = endp - noutp;
2783                                         return (ARCHIVE_EOF);
2784                                 }
2785                                 if (noutp >= endp)
2786                                         /* Output buffer is empty. */
2787                                         goto next_data;
2788
2789                                 if (!lzx_br_read_ahead(strm, &bre,
2790                                     mt_max_bits)) {
2791                                         if (!last)
2792                                                 goto next_data;
2793                                         /* Remaining bits are less than
2794                                          * maximum bits(mt.max_bits) but maybe
2795                                          * it still remains as much as we need,
2796                                          * so we should try to use it with
2797                                          * dummy bits. */
2798                                         c = lzx_decode_huffman(mt,
2799                                               lzx_br_bits_forced(
2800                                                 &bre, mt_max_bits));
2801                                         lzx_br_consume(&bre, mt_bitlen[c]);
2802                                         if (!lzx_br_has(&bre, 0))
2803                                                 goto failed;/* Over read. */
2804                                 } else {
2805                                         c = lzx_decode_huffman(mt,
2806                                               lzx_br_bits(&bre, mt_max_bits));
2807                                         lzx_br_consume(&bre, mt_bitlen[c]);
2808                                 }
2809                                 if (c > UCHAR_MAX)
2810                                         break;
2811                                 /*
2812                                  * 'c' is exactly literal code.
2813                                  */
2814                                 /* Save a decoded code to reference it
2815                                  * afterward. */
2816                                 w_buff[w_pos] = c;
2817                                 w_pos = (w_pos + 1) & w_mask;
2818                                 /* Store the decoded code to output buffer. */
2819                                 *noutp++ = c;
2820                                 block_bytes_avail--;
2821                         }
2822                         /*
2823                          * Get a match code, its length and offset.
2824                          */
2825                         c -= UCHAR_MAX + 1;
2826                         length_header = c & 7;
2827                         position_slot = c >> 3;
2828                         /* FALL THROUGH */
2829                 case ST_LENGTH:
2830                         /*
2831                          * Get a length.
2832                          */
2833                         if (length_header == 7) {
2834                                 if (!lzx_br_read_ahead(strm, &bre,
2835                                     lt_max_bits)) {
2836                                         if (!last) {
2837                                                 state = ST_LENGTH;
2838                                                 goto next_data;
2839                                         }
2840                                         c = lzx_decode_huffman(lt,
2841                                               lzx_br_bits_forced(
2842                                                 &bre, lt_max_bits));
2843                                         lzx_br_consume(&bre, lt_bitlen[c]);
2844                                         if (!lzx_br_has(&bre, 0))
2845                                                 goto failed;/* Over read. */
2846                                 } else {
2847                                         c = lzx_decode_huffman(lt,
2848                                             lzx_br_bits(&bre, lt_max_bits));
2849                                         lzx_br_consume(&bre, lt_bitlen[c]);
2850                                 }
2851                                 copy_len = c + 7 + 2;
2852                         } else
2853                                 copy_len = length_header + 2;
2854                         if ((size_t)copy_len > block_bytes_avail)
2855                                 goto failed;
2856                         /*
2857                          * Get an offset.
2858                          */
2859                         switch (position_slot) {
2860                         case 0: /* Use repeated offset 0. */
2861                                 copy_pos = r0;
2862                                 state = ST_REAL_POS;
2863                                 continue;
2864                         case 1: /* Use repeated offset 1. */
2865                                 copy_pos = r1;
2866                                 /* Swap repeated offset. */
2867                                 r1 = r0;
2868                                 r0 = copy_pos;
2869                                 state = ST_REAL_POS;
2870                                 continue;
2871                         case 2: /* Use repeated offset 2. */
2872                                 copy_pos = r2;
2873                                 /* Swap repeated offset. */
2874                                 r2 = r0;
2875                                 r0 = copy_pos;
2876                                 state = ST_REAL_POS;
2877                                 continue;
2878                         default:
2879                                 offset_bits =
2880                                     pos_tbl[position_slot].footer_bits;
2881                                 break;
2882                         }
2883                         /* FALL THROUGH */
2884                 case ST_OFFSET:
2885                         /*
2886                          * Get the offset, which is a distance from
2887                          * current window position.
2888                          */
2889                         if (block_type == ALIGNED_OFFSET_BLOCK &&
2890                             offset_bits >= 3) {
2891                                 int offbits = offset_bits - 3;
2892
2893                                 if (!lzx_br_read_ahead(strm, &bre, offbits)) {
2894                                         state = ST_OFFSET;
2895                                         if (last)
2896                                                 goto failed;
2897                                         goto next_data;
2898                                 }
2899                                 copy_pos = lzx_br_bits(&bre, offbits) << 3;
2900
2901                                 /* Get an aligned number. */
2902                                 if (!lzx_br_read_ahead(strm, &bre,
2903                                     offbits + at_max_bits)) {
2904                                         if (!last) {
2905                                                 state = ST_OFFSET;
2906                                                 goto next_data;
2907                                         }
2908                                         lzx_br_consume(&bre, offbits);
2909                                         c = lzx_decode_huffman(at,
2910                                               lzx_br_bits_forced(&bre,
2911                                                 at_max_bits));
2912                                         lzx_br_consume(&bre, at_bitlen[c]);
2913                                         if (!lzx_br_has(&bre, 0))
2914                                                 goto failed;/* Over read. */
2915                                 } else {
2916                                         lzx_br_consume(&bre, offbits);
2917                                         c = lzx_decode_huffman(at,
2918                                               lzx_br_bits(&bre, at_max_bits));
2919                                         lzx_br_consume(&bre, at_bitlen[c]);
2920                                 }
2921                                 /* Add an aligned number. */
2922                                 copy_pos += c;
2923                         } else {
2924                                 if (!lzx_br_read_ahead(strm, &bre,
2925                                     offset_bits)) {
2926                                         state = ST_OFFSET;
2927                                         if (last)
2928                                                 goto failed;
2929                                         goto next_data;
2930                                 }
2931                                 copy_pos = lzx_br_bits(&bre, offset_bits);
2932                                 lzx_br_consume(&bre, offset_bits);
2933                         }
2934                         copy_pos += pos_tbl[position_slot].base -2;
2935
2936                         /* Update repeated offset LRU queue. */
2937                         r2 = r1;
2938                         r1 = r0;
2939                         r0 = copy_pos;
2940                         /* FALL THROUGH */
2941                 case ST_REAL_POS:
2942                         /*
2943                          * Compute a real position in window.
2944                          */
2945                         copy_pos = (w_pos - copy_pos) & w_mask;
2946                         /* FALL THROUGH */
2947                 case ST_COPY:
2948                         /*
2949                          * Copy several bytes as extracted data from the window
2950                          * into the output buffer.
2951                          */
2952                         for (;;) {
2953                                 const unsigned char *s;
2954                                 int l;
2955
2956                                 l = copy_len;
2957                                 if (copy_pos > w_pos) {
2958                                         if (l > w_size - copy_pos)
2959                                                 l = w_size - copy_pos;
2960                                 } else {
2961                                         if (l > w_size - w_pos)
2962                                                 l = w_size - w_pos;
2963                                 }
2964                                 if (noutp + l >= endp)
2965                                         l = (int)(endp - noutp);
2966                                 s = w_buff + copy_pos;
2967                                 if (l >= 8 && ((copy_pos + l < w_pos)
2968                                   || (w_pos + l < copy_pos))) {
2969                                         memcpy(w_buff + w_pos, s, l);
2970                                         memcpy(noutp, s, l);
2971                                 } else {
2972                                         unsigned char *d;
2973                                         int li;
2974
2975                                         d = w_buff + w_pos;
2976                                         for (li = 0; li < l; li++)
2977                                                 noutp[li] = d[li] = s[li];
2978                                 }
2979                                 noutp += l;
2980                                 copy_pos = (copy_pos + l) & w_mask;
2981                                 w_pos = (w_pos + l) & w_mask;
2982                                 block_bytes_avail -= l;
2983                                 if (copy_len <= l)
2984                                         /* A copy of current pattern ended. */
2985                                         break;
2986                                 copy_len -= l;
2987                                 if (noutp >= endp) {
2988                                         /* Output buffer is empty. */
2989                                         state = ST_COPY;
2990                                         goto next_data;
2991                                 }
2992                         }
2993                         state = ST_MAIN;
2994                         break;
2995                 }
2996         }
2997 failed:
2998         return (ds->error = ARCHIVE_FAILED);
2999 next_data:
3000         ds->br = bre;
3001         ds->block_bytes_avail = block_bytes_avail;
3002         ds->copy_len = copy_len;
3003         ds->copy_pos = copy_pos;
3004         ds->length_header = length_header;
3005         ds->offset_bits = offset_bits;
3006         ds->position_slot = position_slot;
3007         ds->r0 = r0; ds->r1 = r1; ds->r2 = r2;
3008         ds->state = state;
3009         ds->w_pos = w_pos;
3010         strm->avail_out = endp - noutp;
3011         return (ARCHIVE_OK);
3012 }
3013
3014 static int
3015 lzx_read_pre_tree(struct lzx_stream *strm)
3016 {
3017         struct lzx_dec *ds = strm->ds;
3018         struct lzx_br *br = &(ds->br);
3019         int i;
3020
3021         if (ds->loop == 0)
3022                 memset(ds->pt.freq, 0, sizeof(ds->pt.freq));
3023         for (i = ds->loop; i < ds->pt.len_size; i++) {
3024                 if (!lzx_br_read_ahead(strm, br, 4)) {
3025                         ds->loop = i;
3026                         return (0);
3027                 }
3028                 ds->pt.bitlen[i] = lzx_br_bits(br, 4);
3029                 ds->pt.freq[ds->pt.bitlen[i]]++;
3030                 lzx_br_consume(br, 4);
3031         }
3032         ds->loop = i;
3033         return (1);
3034 }
3035
3036 /*
3037  * Read a bunch of bit-lengths from pre-tree.
3038  */
3039 static int
3040 lzx_read_bitlen(struct lzx_stream *strm, struct huffman *d, int end)
3041 {
3042         struct lzx_dec *ds = strm->ds;
3043         struct lzx_br *br = &(ds->br);
3044         int c, i, j, ret, same;
3045         unsigned rbits;
3046
3047         i = ds->loop;
3048         if (i == 0)
3049                 memset(d->freq, 0, sizeof(d->freq));
3050         ret = 0;
3051         if (end < 0)
3052                 end = d->len_size;
3053         while (i < end) {
3054                 ds->loop = i;
3055                 if (!lzx_br_read_ahead(strm, br, ds->pt.max_bits))
3056                         goto getdata;
3057                 rbits = lzx_br_bits(br, ds->pt.max_bits);
3058                 c = lzx_decode_huffman(&(ds->pt), rbits);
3059                 switch (c) {
3060                 case 17:/* several zero lengths, from 4 to 19. */
3061                         if (!lzx_br_read_ahead(strm, br, ds->pt.bitlen[c]+4))
3062                                 goto getdata;
3063                         lzx_br_consume(br, ds->pt.bitlen[c]);
3064                         same = lzx_br_bits(br, 4) + 4;
3065                         if (i + same > end)
3066                                 return (-1);/* Invalid */
3067                         lzx_br_consume(br, 4);
3068                         for (j = 0; j < same; j++)
3069                                 d->bitlen[i++] = 0;
3070                         break;
3071                 case 18:/* many zero lengths, from 20 to 51. */
3072                         if (!lzx_br_read_ahead(strm, br, ds->pt.bitlen[c]+5))
3073                                 goto getdata;
3074                         lzx_br_consume(br, ds->pt.bitlen[c]);
3075                         same = lzx_br_bits(br, 5) + 20;
3076                         if (i + same > end)
3077                                 return (-1);/* Invalid */
3078                         lzx_br_consume(br, 5);
3079                         memset(d->bitlen + i, 0, same);
3080                         i += same;
3081                         break;
3082                 case 19:/* a few same lengths. */
3083                         if (!lzx_br_read_ahead(strm, br,
3084                             ds->pt.bitlen[c]+1+ds->pt.max_bits))
3085                                 goto getdata;
3086                         lzx_br_consume(br, ds->pt.bitlen[c]);
3087                         same = lzx_br_bits(br, 1) + 4;
3088                         if (i + same > end)
3089                                 return (-1);
3090                         lzx_br_consume(br, 1);
3091                         rbits = lzx_br_bits(br, ds->pt.max_bits);
3092                         c = lzx_decode_huffman(&(ds->pt), rbits);
3093                         lzx_br_consume(br, ds->pt.bitlen[c]);
3094                         c = (d->bitlen[i] - c + 17) % 17;
3095                         if (c < 0)
3096                                 return (-1);/* Invalid */
3097                         for (j = 0; j < same; j++)
3098                                 d->bitlen[i++] = c;
3099                         d->freq[c] += same;
3100                         break;
3101                 default:
3102                         lzx_br_consume(br, ds->pt.bitlen[c]);
3103                         c = (d->bitlen[i] - c + 17) % 17;
3104                         if (c < 0)
3105                                 return (-1);/* Invalid */
3106                         d->freq[c]++;
3107                         d->bitlen[i++] = c;
3108                         break;
3109                 }
3110         }
3111         ret = 1;
3112 getdata:
3113         ds->loop = i;
3114         return (ret);
3115 }
3116
3117 static int
3118 lzx_huffman_init(struct huffman *hf, size_t len_size, int tbl_bits)
3119 {
3120
3121         if (hf->bitlen == NULL || hf->len_size != (int)len_size) {
3122                 free(hf->bitlen);
3123                 hf->bitlen = calloc(len_size,  sizeof(hf->bitlen[0]));
3124                 if (hf->bitlen == NULL)
3125                         return (ARCHIVE_FATAL);
3126                 hf->len_size = (int)len_size;
3127         } else
3128                 memset(hf->bitlen, 0, len_size *  sizeof(hf->bitlen[0]));
3129         if (hf->tbl == NULL) {
3130                 hf->tbl = malloc(((size_t)1 << tbl_bits) * sizeof(hf->tbl[0]));
3131                 if (hf->tbl == NULL)
3132                         return (ARCHIVE_FATAL);
3133                 hf->tbl_bits = tbl_bits;
3134         }
3135         return (ARCHIVE_OK);
3136 }
3137
3138 static void
3139 lzx_huffman_free(struct huffman *hf)
3140 {
3141         free(hf->bitlen);
3142         free(hf->tbl);
3143 }
3144
3145 /*
3146  * Make a huffman coding table.
3147  */
3148 static int
3149 lzx_make_huffman_table(struct huffman *hf)
3150 {
3151         uint16_t *tbl;
3152         const unsigned char *bitlen;
3153         int bitptn[17], weight[17];
3154         int i, maxbits = 0, ptn, tbl_size, w;
3155         int len_avail;
3156
3157         /*
3158          * Initialize bit patterns.
3159          */
3160         ptn = 0;
3161         for (i = 1, w = 1 << 15; i <= 16; i++, w >>= 1) {
3162                 bitptn[i] = ptn;
3163                 weight[i] = w;
3164                 if (hf->freq[i]) {
3165                         ptn += hf->freq[i] * w;
3166                         maxbits = i;
3167                 }
3168         }
3169         if ((ptn & 0xffff) != 0 || maxbits > hf->tbl_bits)
3170                 return (0);/* Invalid */
3171
3172         hf->max_bits = maxbits;
3173
3174         /*
3175          * Cut out extra bits which we won't house in the table.
3176          * This preparation reduces the same calculation in the for-loop
3177          * making the table.
3178          */
3179         if (maxbits < 16) {
3180                 int ebits = 16 - maxbits;
3181                 for (i = 1; i <= maxbits; i++) {
3182                         bitptn[i] >>= ebits;
3183                         weight[i] >>= ebits;
3184                 }
3185         }
3186
3187         /*
3188          * Make the table.
3189          */
3190         tbl_size = 1 << hf->tbl_bits;
3191         tbl = hf->tbl;
3192         bitlen = hf->bitlen;
3193         len_avail = hf->len_size;
3194         hf->tree_used = 0;
3195         for (i = 0; i < len_avail; i++) {
3196                 uint16_t *p;
3197                 int len, cnt;
3198
3199                 if (bitlen[i] == 0)
3200                         continue;
3201                 /* Get a bit pattern */
3202                 len = bitlen[i];
3203                 if (len > tbl_size)
3204                         return (0);
3205                 ptn = bitptn[len];
3206                 cnt = weight[len];
3207                 /* Calculate next bit pattern */
3208                 if ((bitptn[len] = ptn + cnt) > tbl_size)
3209                         return (0);/* Invalid */
3210                 /* Update the table */
3211                 p = &(tbl[ptn]);
3212                 while (--cnt >= 0)
3213                         p[cnt] = (uint16_t)i;
3214         }
3215         return (1);
3216 }
3217
3218 static inline int
3219 lzx_decode_huffman(struct huffman *hf, unsigned rbits)
3220 {
3221         int c;
3222         c = hf->tbl[rbits];
3223         if (c < hf->len_size)
3224                 return (c);
3225         return (0);
3226 }