contrib/libarchive/libarchive/archive_read_support_format_cab.c

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