contrib/libarchive/libarchive/archive_read_support_format_cab.c

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