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