contrib/libarchive/libarchive/archive_read_support_format_lha.c

   1 /*-
   2  * Copyright (c) 2008-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
  41 #include "archive.h"
  42 #include "archive_entry.h"
  43 #include "archive_entry_locale.h"
  44 #include "archive_private.h"
  45 #include "archive_read_private.h"
  46 #include "archive_endian.h"
  47
  48
  49 #define MAXMATCH                256     /* Maximum match length. */
  50 #define MINMATCH                3       /* Minimum match length. */
  51 /*
  52  * Literal table format:
  53  * +0              +256                      +510
  54  * +---------------+-------------------------+
  55  * | literal code  |       match length      |
  56  * |   0 ... 255   |  MINMATCH ... MAXMATCH  |
  57  * +---------------+-------------------------+
  58  *  <---          LT_BITLEN_SIZE         --->
  59  */
  60 /* Literal table size. */
  61 #define LT_BITLEN_SIZE          (UCHAR_MAX + 1 + MAXMATCH - MINMATCH + 1)
  62 /* Position table size.
  63  * Note: this used for both position table and pre literal table.*/
  64 #define PT_BITLEN_SIZE          (3 + 16)
  65
  66 struct lzh_dec {
  67         /* Decoding status. */
  68         int                      state;
  69
  70         /*
  71          * Window to see last 8Ki(lh5),32Ki(lh6),64Ki(lh7) bytes of decoded
  72          * data.
  73          */
  74         int                      w_size;
  75         int                      w_mask;
  76         /* Window buffer, which is a loop buffer. */
  77         unsigned char           *w_buff;
  78         /* The insert position to the window. */
  79         int                      w_pos;
  80         /* The position where we can copy decoded code from the window. */
  81         int                      copy_pos;
  82         /* The length how many bytes we can copy decoded code from
  83          * the window. */
  84         int                      copy_len;
  85         /* The remaining bytes that we have not copied decoded data from
  86          * the window to an output buffer. */
  87         int                      w_remaining;
  88
  89         /*
  90          * Bit stream reader.
  91          */
  92         struct lzh_br {
  93 #define CACHE_TYPE              uint64_t
  94 #define CACHE_BITS              (8 * sizeof(CACHE_TYPE))
  95                 /* Cache buffer. */
  96                 CACHE_TYPE       cache_buffer;
  97                 /* Indicates how many bits avail in cache_buffer. */
  98                 int              cache_avail;
  99         } br;
 100
 101         /*
 102          * Huffman coding.
 103          */
 104         struct huffman {
 105                 int              len_size;
 106                 int              len_avail;
 107                 int              len_bits;
 108                 int              freq[17];
 109                 unsigned char   *bitlen;
 110
 111                 /*
 112                  * Use a index table. It's faster than searching a huffman
 113                  * coding tree, which is a binary tree. But a use of a large
 114                  * index table causes L1 cache read miss many times.
 115                  */
 116 #define HTBL_BITS       10
 117                 int              max_bits;
 118                 int              shift_bits;
 119                 int              tbl_bits;
 120                 int              tree_used;
 121                 int              tree_avail;
 122                 /* Direct access table. */
 123                 uint16_t        *tbl;
 124                 /* Binary tree table for extra bits over the direct access. */
 125                 struct htree_t {
 126                         uint16_t left;
 127                         uint16_t right;
 128                 }               *tree;
 129         }                        lt, pt;
 130
 131         int                      blocks_avail;
 132         int                      pos_pt_len_size;
 133         int                      pos_pt_len_bits;
 134         int                      literal_pt_len_size;
 135         int                      literal_pt_len_bits;
 136         int                      reading_position;
 137         int                      loop;
 138         int                      error;
 139 };
 140
 141 struct lzh_stream {
 142         const unsigned char     *next_in;
 143         int64_t                  avail_in;
 144         int64_t                  total_in;
 145         unsigned char           *next_out;
 146         int64_t                  avail_out;
 147         int64_t                  total_out;
 148         struct lzh_dec          *ds;
 149 };
 150
 151 struct lha {
 152         /* entry_bytes_remaining is the number of bytes we expect.          */
 153         int64_t                  entry_offset;
 154         int64_t                  entry_bytes_remaining;
 155         int64_t                  entry_unconsumed;
 156         uint16_t                 entry_crc_calculated;
 157
 158         size_t                   header_size;   /* header size              */
 159         unsigned char            level;         /* header level             */
 160         char                     method[3];     /* compress type            */
 161         int64_t                  compsize;      /* compressed data size     */
 162         int64_t                  origsize;      /* original file size       */
 163         int                      setflag;
 164 #define BIRTHTIME_IS_SET        1
 165 #define ATIME_IS_SET            2
 166 #define UNIX_MODE_IS_SET        4
 167 #define CRC_IS_SET              8
 168         time_t                   birthtime;
 169         long                     birthtime_tv_nsec;
 170         time_t                   mtime;
 171         long                     mtime_tv_nsec;
 172         time_t                   atime;
 173         long                     atime_tv_nsec;
 174         mode_t                   mode;
 175         int64_t                  uid;
 176         int64_t                  gid;
 177         struct archive_string    uname;
 178         struct archive_string    gname;
 179         uint16_t                 header_crc;
 180         uint16_t                 crc;
 181         struct archive_string_conv *sconv;
 182         struct archive_string_conv *opt_sconv;
 183
 184         struct archive_string    dirname;
 185         struct archive_string    filename;
 186         struct archive_wstring   ws;
 187
 188         unsigned char            dos_attr;
 189
 190         /* Flag to mark progress that an archive was read their first header.*/
 191         char                     found_first_header;
 192         /* Flag to mark that indicates an empty directory. */
 193         char                     directory;
 194
 195         /* Flags to mark progress of decompression. */
 196         char                     decompress_init;
 197         char                     end_of_entry;
 198         char                     end_of_entry_cleanup;
 199         char                     entry_is_compressed;
 200
 201         unsigned char           *uncompressed_buffer;
 202         size_t                   uncompressed_buffer_size;
 203
 204         char                     format_name[64];
 205
 206         struct lzh_stream        strm;
 207 };
 208
 209 /*
 210  * LHA header common member offset.
 211  */
 212 #define H_METHOD_OFFSET 2       /* Compress type. */
 213 #define H_ATTR_OFFSET   19      /* DOS attribute. */
 214 #define H_LEVEL_OFFSET  20      /* Header Level.  */
 215 #define H_SIZE          22      /* Minimum header size. */
 216
 217 static const uint16_t crc16tbl[256] = {
 218         0x0000,0xC0C1,0xC181,0x0140,0xC301,0x03C0,0x0280,0xC241,
 219         0xC601,0x06C0,0x0780,0xC741,0x0500,0xC5C1,0xC481,0x0440,
 220         0xCC01,0x0CC0,0x0D80,0xCD41,0x0F00,0xCFC1,0xCE81,0x0E40,
 221         0x0A00,0xCAC1,0xCB81,0x0B40,0xC901,0x09C0,0x0880,0xC841,
 222         0xD801,0x18C0,0x1980,0xD941,0x1B00,0xDBC1,0xDA81,0x1A40,
 223         0x1E00,0xDEC1,0xDF81,0x1F40,0xDD01,0x1DC0,0x1C80,0xDC41,
 224         0x1400,0xD4C1,0xD581,0x1540,0xD701,0x17C0,0x1680,0xD641,
 225         0xD201,0x12C0,0x1380,0xD341,0x1100,0xD1C1,0xD081,0x1040,
 226         0xF001,0x30C0,0x3180,0xF141,0x3300,0xF3C1,0xF281,0x3240,
 227         0x3600,0xF6C1,0xF781,0x3740,0xF501,0x35C0,0x3480,0xF441,
 228         0x3C00,0xFCC1,0xFD81,0x3D40,0xFF01,0x3FC0,0x3E80,0xFE41,
 229         0xFA01,0x3AC0,0x3B80,0xFB41,0x3900,0xF9C1,0xF881,0x3840,
 230         0x2800,0xE8C1,0xE981,0x2940,0xEB01,0x2BC0,0x2A80,0xEA41,
 231         0xEE01,0x2EC0,0x2F80,0xEF41,0x2D00,0xEDC1,0xEC81,0x2C40,
 232         0xE401,0x24C0,0x2580,0xE541,0x2700,0xE7C1,0xE681,0x2640,
 233         0x2200,0xE2C1,0xE381,0x2340,0xE101,0x21C0,0x2080,0xE041,
 234         0xA001,0x60C0,0x6180,0xA141,0x6300,0xA3C1,0xA281,0x6240,
 235         0x6600,0xA6C1,0xA781,0x6740,0xA501,0x65C0,0x6480,0xA441,
 236         0x6C00,0xACC1,0xAD81,0x6D40,0xAF01,0x6FC0,0x6E80,0xAE41,
 237         0xAA01,0x6AC0,0x6B80,0xAB41,0x6900,0xA9C1,0xA881,0x6840,
 238         0x7800,0xB8C1,0xB981,0x7940,0xBB01,0x7BC0,0x7A80,0xBA41,
 239         0xBE01,0x7EC0,0x7F80,0xBF41,0x7D00,0xBDC1,0xBC81,0x7C40,
 240         0xB401,0x74C0,0x7580,0xB541,0x7700,0xB7C1,0xB681,0x7640,
 241         0x7200,0xB2C1,0xB381,0x7340,0xB101,0x71C0,0x7080,0xB041,
 242         0x5000,0x90C1,0x9181,0x5140,0x9301,0x53C0,0x5280,0x9241,
 243         0x9601,0x56C0,0x5780,0x9741,0x5500,0x95C1,0x9481,0x5440,
 244         0x9C01,0x5CC0,0x5D80,0x9D41,0x5F00,0x9FC1,0x9E81,0x5E40,
 245         0x5A00,0x9AC1,0x9B81,0x5B40,0x9901,0x59C0,0x5880,0x9841,
 246         0x8801,0x48C0,0x4980,0x8941,0x4B00,0x8BC1,0x8A81,0x4A40,
 247         0x4E00,0x8EC1,0x8F81,0x4F40,0x8D01,0x4DC0,0x4C80,0x8C41,
 248         0x4400,0x84C1,0x8581,0x4540,0x8701,0x47C0,0x4680,0x8641,
 249         0x8201,0x42C0,0x4380,0x8341,0x4100,0x81C1,0x8081,0x4040
 250 };
 251
 252 static int      archive_read_format_lha_bid(struct archive_read *, int);
 253 static int      archive_read_format_lha_options(struct archive_read *,
 254                     const char *, const char *);
 255 static int      archive_read_format_lha_read_header(struct archive_read *,
 256                     struct archive_entry *);
 257 static int      archive_read_format_lha_read_data(struct archive_read *,
 258                     const void **, size_t *, int64_t *);
 259 static int      archive_read_format_lha_read_data_skip(struct archive_read *);
 260 static int      archive_read_format_lha_cleanup(struct archive_read *);
 261
 262 static void     lha_replace_path_separator(struct lha *,
 263                     struct archive_entry *);
 264 static int      lha_read_file_header_0(struct archive_read *, struct lha *);
 265 static int      lha_read_file_header_1(struct archive_read *, struct lha *);
 266 static int      lha_read_file_header_2(struct archive_read *, struct lha *);
 267 static int      lha_read_file_header_3(struct archive_read *, struct lha *);
 268 static int      lha_read_file_extended_header(struct archive_read *,
 269                     struct lha *, uint16_t *, int, size_t, size_t *);
 270 static size_t   lha_check_header_format(const void *);
 271 static int      lha_skip_sfx(struct archive_read *);
 272 static time_t   lha_dos_time(const unsigned char *);
 273 static time_t   lha_win_time(uint64_t, long *);
 274 static unsigned char    lha_calcsum(unsigned char, const void *,
 275                     int, size_t);
 276 static int      lha_parse_linkname(struct archive_string *,
 277                     struct archive_string *);
 278 static int      lha_read_data_none(struct archive_read *, const void **,
 279                     size_t *, int64_t *);
 280 static int      lha_read_data_lzh(struct archive_read *, const void **,
 281                     size_t *, int64_t *);
 282 static uint16_t lha_crc16(uint16_t, const void *, size_t);
 283 static int      lzh_decode_init(struct lzh_stream *, const char *);
 284 static void     lzh_decode_free(struct lzh_stream *);
 285 static int      lzh_decode(struct lzh_stream *, int);
 286 static int      lzh_br_fillup(struct lzh_stream *, struct lzh_br *);
 287 static int      lzh_huffman_init(struct huffman *, size_t, int);
 288 static void     lzh_huffman_free(struct huffman *);
 289 static int      lzh_read_pt_bitlen(struct lzh_stream *, int start, int end);
 290 static int      lzh_make_fake_table(struct huffman *, uint16_t);
 291 static int      lzh_make_huffman_table(struct huffman *);
 292 static inline int lzh_decode_huffman(struct huffman *, unsigned);
 293 static int      lzh_decode_huffman_tree(struct huffman *, unsigned, int);
 294
 295
 296 int
 297 archive_read_support_format_lha(struct archive *_a)
 298 {
 299         struct archive_read *a = (struct archive_read *)_a;
 300         struct lha *lha;
 301         int r;
 302
 303         archive_check_magic(_a, ARCHIVE_READ_MAGIC,
 304             ARCHIVE_STATE_NEW, "archive_read_support_format_lha");
 305
 306         lha = (struct lha *)calloc(1, sizeof(*lha));
 307         if (lha == NULL) {
 308                 archive_set_error(&a->archive, ENOMEM,
 309                     "Can't allocate lha data");
 310                 return (ARCHIVE_FATAL);
 311         }
 312         archive_string_init(&lha->ws);
 313
 314         r = __archive_read_register_format(a,
 315             lha,
 316             "lha",
 317             archive_read_format_lha_bid,
 318             archive_read_format_lha_options,
 319             archive_read_format_lha_read_header,
 320             archive_read_format_lha_read_data,
 321             archive_read_format_lha_read_data_skip,
 322             NULL,
 323             archive_read_format_lha_cleanup);
 324
 325         if (r != ARCHIVE_OK)
 326                 free(lha);
 327         return (ARCHIVE_OK);
 328 }
 329
 330 static size_t
 331 lha_check_header_format(const void *h)
 332 {
 333         const unsigned char *p = h;
 334         size_t next_skip_bytes;
 335
 336         switch (p[H_METHOD_OFFSET+3]) {
 337         /*
 338          * "-lh0-" ... "-lh7-" "-lhd-"
 339          * "-lzs-" "-lz5-"
 340          */
 341         case '0': case '1': case '2': case '3':
 342         case '4': case '5': case '6': case '7':
 343         case 'd':
 344         case 's':
 345                 next_skip_bytes = 4;
 346
 347                 /* b0 == 0 means the end of an LHa archive file.        */
 348                 if (p[0] == 0)
 349                         break;
 350                 if (p[H_METHOD_OFFSET] != '-' || p[H_METHOD_OFFSET+1] != 'l'
 351                     ||  p[H_METHOD_OFFSET+4] != '-')
 352                         break;
 353
 354                 if (p[H_METHOD_OFFSET+2] == 'h') {
 355                         /* "-lh?-" */
 356                         if (p[H_METHOD_OFFSET+3] == 's')
 357                                 break;
 358                         if (p[H_LEVEL_OFFSET] == 0)
 359                                 return (0);
 360                         if (p[H_LEVEL_OFFSET] <= 3 && p[H_ATTR_OFFSET] == 0x20)
 361                                 return (0);
 362                 }
 363                 if (p[H_METHOD_OFFSET+2] == 'z') {
 364                         /* LArc extensions: -lzs-,-lz4- and -lz5- */
 365                         if (p[H_LEVEL_OFFSET] != 0)
 366                                 break;
 367                         if (p[H_METHOD_OFFSET+3] == 's'
 368                             || p[H_METHOD_OFFSET+3] == '4'
 369                             || p[H_METHOD_OFFSET+3] == '5')
 370                                 return (0);
 371                 }
 372                 break;
 373         case 'h': next_skip_bytes = 1; break;
 374         case 'z': next_skip_bytes = 1; break;
 375         case 'l': next_skip_bytes = 2; break;
 376         case '-': next_skip_bytes = 3; break;
 377         default : next_skip_bytes = 4; break;
 378         }
 379
 380         return (next_skip_bytes);
 381 }
 382
 383 static int
 384 archive_read_format_lha_bid(struct archive_read *a, int best_bid)
 385 {
 386         const char *p;
 387         const void *buff;
 388         ssize_t bytes_avail, offset, window;
 389         size_t next;
 390
 391         /* If there's already a better bid than we can ever
 392            make, don't bother testing. */
 393         if (best_bid > 30)
 394                 return (-1);
 395
 396         if ((p = __archive_read_ahead(a, H_SIZE, NULL)) == NULL)
 397                 return (-1);
 398
 399         if (lha_check_header_format(p) == 0)
 400                 return (30);
 401
 402         if (p[0] == 'M' && p[1] == 'Z') {
 403                 /* PE file */
 404                 offset = 0;
 405                 window = 4096;
 406                 while (offset < (1024 * 20)) {
 407                         buff = __archive_read_ahead(a, offset + window,
 408                             &bytes_avail);
 409                         if (buff == NULL) {
 410                                 /* Remaining bytes are less than window. */
 411                                 window >>= 1;
 412                                 if (window < (H_SIZE + 3))
 413                                         return (0);
 414                                 continue;
 415                         }
 416                         p = (const char *)buff + offset;
 417                         while (p + H_SIZE < (const char *)buff + bytes_avail) {
 418                                 if ((next = lha_check_header_format(p)) == 0)
 419                                         return (30);
 420                                 p += next;
 421                         }
 422                         offset = p - (const char *)buff;
 423                 }
 424         }
 425         return (0);
 426 }
 427
 428 static int
 429 archive_read_format_lha_options(struct archive_read *a,
 430     const char *key, const char *val)
 431 {
 432         struct lha *lha;
 433         int ret = ARCHIVE_FAILED;
 434
 435         lha = (struct lha *)(a->format->data);
 436         if (strcmp(key, "hdrcharset")  == 0) {
 437                 if (val == NULL || val[0] == 0)
 438                         archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
 439                             "lha: hdrcharset option needs a character-set name");
 440                 else {
 441                         lha->opt_sconv =
 442                             archive_string_conversion_from_charset(
 443                                 &a->archive, val, 0);
 444                         if (lha->opt_sconv != NULL)
 445                                 ret = ARCHIVE_OK;
 446                         else
 447                                 ret = ARCHIVE_FATAL;
 448                 }
 449                 return (ret);
 450         }
 451
 452         /* Note: The "warn" return is just to inform the options
 453          * supervisor that we didn't handle it.  It will generate
 454          * a suitable error if no one used this option. */
 455         return (ARCHIVE_WARN);
 456 }
 457
 458 static int
 459 lha_skip_sfx(struct archive_read *a)
 460 {
 461         const void *h;
 462         const char *p, *q;
 463         size_t next, skip;
 464         ssize_t bytes, window;
 465
 466         window = 4096;
 467         for (;;) {
 468                 h = __archive_read_ahead(a, window, &bytes);
 469                 if (h == NULL) {
 470                         /* Remaining bytes are less than window. */
 471                         window >>= 1;
 472                         if (window < (H_SIZE + 3))
 473                                 goto fatal;
 474                         continue;
 475                 }
 476                 if (bytes < H_SIZE)
 477                         goto fatal;
 478                 p = h;
 479                 q = p + bytes;
 480
 481                 /*
 482                  * Scan ahead until we find something that looks
 483                  * like the lha header.
 484                  */
 485                 while (p + H_SIZE < q) {
 486                         if ((next = lha_check_header_format(p)) == 0) {
 487                                 skip = p - (const char *)h;
 488                                 __archive_read_consume(a, skip);
 489                                 return (ARCHIVE_OK);
 490                         }
 491                         p += next;
 492                 }
 493                 skip = p - (const char *)h;
 494                 __archive_read_consume(a, skip);
 495         }
 496 fatal:
 497         archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
 498             "Couldn't find out LHa header");
 499         return (ARCHIVE_FATAL);
 500 }
 501
 502 static int
 503 truncated_error(struct archive_read *a)
 504 {
 505         archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
 506             "Truncated LHa header");
 507         return (ARCHIVE_FATAL);
 508 }
 509
 510 static int
 511 archive_read_format_lha_read_header(struct archive_read *a,
 512     struct archive_entry *entry)
 513 {
 514         struct archive_string linkname;
 515         struct archive_string pathname;
 516         struct lha *lha;
 517         const unsigned char *p;
 518         const char *signature;
 519         int err;
 520
 521         a->archive.archive_format = ARCHIVE_FORMAT_LHA;
 522         if (a->archive.archive_format_name == NULL)
 523                 a->archive.archive_format_name = "lha";
 524
 525         lha = (struct lha *)(a->format->data);
 526         lha->decompress_init = 0;
 527         lha->end_of_entry = 0;
 528         lha->end_of_entry_cleanup = 0;
 529         lha->entry_unconsumed = 0;
 530
 531         if ((p = __archive_read_ahead(a, H_SIZE, NULL)) == NULL) {
 532                 /*
 533                  * LHa archiver added 0 to the tail of its archive file as
 534                  * the mark of the end of the archive.
 535                  */
 536                 signature = __archive_read_ahead(a, sizeof(signature[0]), NULL);
 537                 if (signature == NULL || signature[0] == 0)
 538                         return (ARCHIVE_EOF);
 539                 return (truncated_error(a));
 540         }
 541
 542         signature = (const char *)p;
 543         if (lha->found_first_header == 0 &&
 544             signature[0] == 'M' && signature[1] == 'Z') {
 545                 /* This is an executable?  Must be self-extracting...   */
 546                 err = lha_skip_sfx(a);
 547                 if (err < ARCHIVE_WARN)
 548                         return (err);
 549
 550                 if ((p = __archive_read_ahead(a, sizeof(*p), NULL)) == NULL)
 551                         return (truncated_error(a));
 552                 signature = (const char *)p;
 553         }
 554         /* signature[0] == 0 means the end of an LHa archive file. */
 555         if (signature[0] == 0)
 556                 return (ARCHIVE_EOF);
 557
 558         /*
 559          * Check the header format and method type.
 560          */
 561         if (lha_check_header_format(p) != 0) {
 562                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
 563                     "Bad LHa file");
 564                 return (ARCHIVE_FATAL);
 565         }
 566
 567         /* We've found the first header. */
 568         lha->found_first_header = 1;
 569         /* Set a default value and common data */
 570         lha->header_size = 0;
 571         lha->level = p[H_LEVEL_OFFSET];
 572         lha->method[0] = p[H_METHOD_OFFSET+1];
 573         lha->method[1] = p[H_METHOD_OFFSET+2];
 574         lha->method[2] = p[H_METHOD_OFFSET+3];
 575         if (memcmp(lha->method, "lhd", 3) == 0)
 576                 lha->directory = 1;
 577         else
 578                 lha->directory = 0;
 579         if (memcmp(lha->method, "lh0", 3) == 0 ||
 580             memcmp(lha->method, "lz4", 3) == 0)
 581                 lha->entry_is_compressed = 0;
 582         else
 583                 lha->entry_is_compressed = 1;
 584
 585         lha->compsize = 0;
 586         lha->origsize = 0;
 587         lha->setflag = 0;
 588         lha->birthtime = 0;
 589         lha->birthtime_tv_nsec = 0;
 590         lha->mtime = 0;
 591         lha->mtime_tv_nsec = 0;
 592         lha->atime = 0;
 593         lha->atime_tv_nsec = 0;
 594         lha->mode = (lha->directory)? 0777 : 0666;
 595         lha->uid = 0;
 596         lha->gid = 0;
 597         archive_string_empty(&lha->dirname);
 598         archive_string_empty(&lha->filename);
 599         lha->dos_attr = 0;
 600         if (lha->opt_sconv != NULL)
 601                 lha->sconv = lha->opt_sconv;
 602         else
 603                 lha->sconv = NULL;
 604
 605         switch (p[H_LEVEL_OFFSET]) {
 606         case 0:
 607                 err = lha_read_file_header_0(a, lha);
 608                 break;
 609         case 1:
 610                 err = lha_read_file_header_1(a, lha);
 611                 break;
 612         case 2:
 613                 err = lha_read_file_header_2(a, lha);
 614                 break;
 615         case 3:
 616                 err = lha_read_file_header_3(a, lha);
 617                 break;
 618         default:
 619                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
 620                     "Unsupported LHa header level %d", p[H_LEVEL_OFFSET]);
 621                 err = ARCHIVE_FATAL;
 622                 break;
 623         }
 624         if (err < ARCHIVE_WARN)
 625                 return (err);
 626
 627
 628         if (!lha->directory && archive_strlen(&lha->filename) == 0)
 629                 /* The filename has not been set */
 630                 return (truncated_error(a));
 631
 632         /*
 633          * Make a pathname from a dirname and a filename.
 634          */
 635         archive_string_concat(&lha->dirname, &lha->filename);
 636         archive_string_init(&pathname);
 637         archive_string_init(&linkname);
 638         archive_string_copy(&pathname, &lha->dirname);
 639
 640         if ((lha->mode & AE_IFMT) == AE_IFLNK) {
 641                 /*
 642                  * Extract the symlink-name if it's included in the pathname.
 643                  */
 644                 if (!lha_parse_linkname(&linkname, &pathname)) {
 645                         /* We couldn't get the symlink-name. */
 646                         archive_set_error(&a->archive,
 647                             ARCHIVE_ERRNO_FILE_FORMAT,
 648                             "Unknown symlink-name");
 649                         archive_string_free(&pathname);
 650                         archive_string_free(&linkname);
 651                         return (ARCHIVE_FAILED);
 652                 }
 653         } else {
 654                 /*
 655                  * Make sure a file-type is set.
 656                  * The mode has been overridden if it is in the extended data.
 657                  */
 658                 lha->mode = (lha->mode & ~AE_IFMT) |
 659                     ((lha->directory)? AE_IFDIR: AE_IFREG);
 660         }
 661         if ((lha->setflag & UNIX_MODE_IS_SET) == 0 &&
 662             (lha->dos_attr & 1) != 0)
 663                 lha->mode &= ~(0222);/* read only. */
 664
 665         /*
 666          * Set basic file parameters.
 667          */
 668         if (archive_entry_copy_pathname_l(entry, pathname.s,
 669             pathname.length, lha->sconv) != 0) {
 670                 if (errno == ENOMEM) {
 671                         archive_set_error(&a->archive, ENOMEM,
 672                             "Can't allocate memory for Pathname");
 673                         return (ARCHIVE_FATAL);
 674                 }
 675                 archive_set_error(&a->archive,
 676                     ARCHIVE_ERRNO_FILE_FORMAT,
 677                     "Pathname cannot be converted "
 678                     "from %s to current locale.",
 679                     archive_string_conversion_charset_name(lha->sconv));
 680                 err = ARCHIVE_WARN;
 681         }
 682         archive_string_free(&pathname);
 683         if (archive_strlen(&linkname) > 0) {
 684                 if (archive_entry_copy_symlink_l(entry, linkname.s,
 685                     linkname.length, lha->sconv) != 0) {
 686                         if (errno == ENOMEM) {
 687                                 archive_set_error(&a->archive, ENOMEM,
 688                                     "Can't allocate memory for Linkname");
 689                                 return (ARCHIVE_FATAL);
 690                         }
 691                         archive_set_error(&a->archive,
 692                             ARCHIVE_ERRNO_FILE_FORMAT,
 693                             "Linkname cannot be converted "
 694                             "from %s to current locale.",
 695                             archive_string_conversion_charset_name(lha->sconv));
 696                         err = ARCHIVE_WARN;
 697                 }
 698         } else
 699                 archive_entry_set_symlink(entry, NULL);
 700         archive_string_free(&linkname);
 701         /*
 702          * When a header level is 0, there is a possibility that
 703          * a pathname and a symlink has '\' character, a directory
 704          * separator in DOS/Windows. So we should convert it to '/'.
 705          */
 706         if (p[H_LEVEL_OFFSET] == 0)
 707                 lha_replace_path_separator(lha, entry);
 708
 709         archive_entry_set_mode(entry, lha->mode);
 710         archive_entry_set_uid(entry, lha->uid);
 711         archive_entry_set_gid(entry, lha->gid);
 712         if (archive_strlen(&lha->uname) > 0)
 713                 archive_entry_set_uname(entry, lha->uname.s);
 714         if (archive_strlen(&lha->gname) > 0)
 715                 archive_entry_set_gname(entry, lha->gname.s);
 716         if (lha->setflag & BIRTHTIME_IS_SET) {
 717                 archive_entry_set_birthtime(entry, lha->birthtime,
 718                     lha->birthtime_tv_nsec);
 719                 archive_entry_set_ctime(entry, lha->birthtime,
 720                     lha->birthtime_tv_nsec);
 721         } else {
 722                 archive_entry_unset_birthtime(entry);
 723                 archive_entry_unset_ctime(entry);
 724         }
 725         archive_entry_set_mtime(entry, lha->mtime, lha->mtime_tv_nsec);
 726         if (lha->setflag & ATIME_IS_SET)
 727                 archive_entry_set_atime(entry, lha->atime,
 728                     lha->atime_tv_nsec);
 729         else
 730                 archive_entry_unset_atime(entry);
 731         if (lha->directory || archive_entry_symlink(entry) != NULL)
 732                 archive_entry_unset_size(entry);
 733         else
 734                 archive_entry_set_size(entry, lha->origsize);
 735
 736         /*
 737          * Prepare variables used to read a file content.
 738          */
 739         lha->entry_bytes_remaining = lha->compsize;
 740         lha->entry_offset = 0;
 741         lha->entry_crc_calculated = 0;
 742
 743         /*
 744          * This file does not have a content.
 745          */
 746         if (lha->directory || lha->compsize == 0)
 747                 lha->end_of_entry = 1;
 748
 749         sprintf(lha->format_name, "lha -%c%c%c-",
 750             lha->method[0], lha->method[1], lha->method[2]);
 751         a->archive.archive_format_name = lha->format_name;
 752
 753         return (err);
 754 }
 755
 756 /*
 757  * Replace a DOS path separator '\' by a character '/'.
 758  * Some multi-byte character set have  a character '\' in its second byte.
 759  */
 760 static void
 761 lha_replace_path_separator(struct lha *lha, struct archive_entry *entry)
 762 {
 763         const wchar_t *wp;
 764         size_t i;
 765
 766         if ((wp = archive_entry_pathname_w(entry)) != NULL) {
 767                 archive_wstrcpy(&(lha->ws), wp);
 768                 for (i = 0; i < archive_strlen(&(lha->ws)); i++) {
 769                         if (lha->ws.s[i] == L'\\')
 770                                 lha->ws.s[i] = L'/';
 771                 }
 772                 archive_entry_copy_pathname_w(entry, lha->ws.s);
 773         }
 774
 775         if ((wp = archive_entry_symlink_w(entry)) != NULL) {
 776                 archive_wstrcpy(&(lha->ws), wp);
 777                 for (i = 0; i < archive_strlen(&(lha->ws)); i++) {
 778                         if (lha->ws.s[i] == L'\\')
 779                                 lha->ws.s[i] = L'/';
 780                 }
 781                 archive_entry_copy_symlink_w(entry, lha->ws.s);
 782         }
 783 }
 784
 785 /*
 786  * Header 0 format
 787  *
 788  * +0              +1         +2               +7                  +11
 789  * +---------------+----------+----------------+-------------------+
 790  * |header size(*1)|header sum|compression type|compressed size(*2)|
 791  * +---------------+----------+----------------+-------------------+
 792  *                             <---------------------(*1)----------*
 793  *
 794  * +11               +15       +17       +19            +20              +21
 795  * +-----------------+---------+---------+--------------+----------------+
 796  * |uncompressed size|time(DOS)|date(DOS)|attribute(DOS)|header level(=0)|
 797  * +-----------------+---------+---------+--------------+----------------+
 798  * *--------------------------------(*1)---------------------------------*
 799  *
 800  * +21             +22       +22+(*3)   +22+(*3)+2       +22+(*3)+2+(*4)
 801  * +---------------+---------+----------+----------------+------------------+
 802  * |name length(*3)|file name|file CRC16|extra header(*4)|  compressed data |
 803  * +---------------+---------+----------+----------------+------------------+
 804  *                  <--(*3)->                             <------(*2)------>
 805  * *----------------------(*1)-------------------------->
 806  *
 807  */
 808 #define H0_HEADER_SIZE_OFFSET   0
 809 #define H0_HEADER_SUM_OFFSET    1
 810 #define H0_COMP_SIZE_OFFSET     7
 811 #define H0_ORIG_SIZE_OFFSET     11
 812 #define H0_DOS_TIME_OFFSET      15
 813 #define H0_NAME_LEN_OFFSET      21
 814 #define H0_FILE_NAME_OFFSET     22
 815 #define H0_FIXED_SIZE           24
 816 static int
 817 lha_read_file_header_0(struct archive_read *a, struct lha *lha)
 818 {
 819         const unsigned char *p;
 820         int extdsize, namelen;
 821         unsigned char headersum, sum_calculated;
 822
 823         if ((p = __archive_read_ahead(a, H0_FIXED_SIZE, NULL)) == NULL)
 824                 return (truncated_error(a));
 825         lha->header_size = p[H0_HEADER_SIZE_OFFSET] + 2;
 826         headersum = p[H0_HEADER_SUM_OFFSET];
 827         lha->compsize = archive_le32dec(p + H0_COMP_SIZE_OFFSET);
 828         lha->origsize = archive_le32dec(p + H0_ORIG_SIZE_OFFSET);
 829         lha->mtime = lha_dos_time(p + H0_DOS_TIME_OFFSET);
 830         namelen = p[H0_NAME_LEN_OFFSET];
 831         extdsize = (int)lha->header_size - H0_FIXED_SIZE - namelen;
 832         if ((namelen > 221 || extdsize < 0) && extdsize != -2) {
 833                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
 834                     "Invalid LHa header");
 835                 return (ARCHIVE_FATAL);
 836         }
 837         if ((p = __archive_read_ahead(a, lha->header_size, NULL)) == NULL)
 838                 return (truncated_error(a));
 839
 840         archive_strncpy(&lha->filename, p + H0_FILE_NAME_OFFSET, namelen);
 841         /* When extdsize == -2, A CRC16 value is not present in the header. */
 842         if (extdsize >= 0) {
 843                 lha->crc = archive_le16dec(p + H0_FILE_NAME_OFFSET + namelen);
 844                 lha->setflag |= CRC_IS_SET;
 845         }
 846         sum_calculated = lha_calcsum(0, p, 2, lha->header_size - 2);
 847
 848         /* Read an extended header */
 849         if (extdsize > 0) {
 850                 /* This extended data is set by 'LHa for UNIX' only.
 851                  * Maybe fixed size.
 852                  */
 853                 p += H0_FILE_NAME_OFFSET + namelen + 2;
 854                 if (p[0] == 'U' && extdsize == 12) {
 855                         /* p[1] is a minor version. */
 856                         lha->mtime = archive_le32dec(&p[2]);
 857                         lha->mode = archive_le16dec(&p[6]);
 858                         lha->uid = archive_le16dec(&p[8]);
 859                         lha->gid = archive_le16dec(&p[10]);
 860                         lha->setflag |= UNIX_MODE_IS_SET;
 861                 }
 862         }
 863         __archive_read_consume(a, lha->header_size);
 864
 865         if (sum_calculated != headersum) {
 866                 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
 867                     "LHa header sum error");
 868                 return (ARCHIVE_FATAL);
 869         }
 870
 871         return (ARCHIVE_OK);
 872 }
 873
 874 /*
 875  * Header 1 format
 876  *
 877  * +0              +1         +2               +7            +11
 878  * +---------------+----------+----------------+-------------+
 879  * |header size(*1)|header sum|compression type|skip size(*2)|
 880  * +---------------+----------+----------------+-------------+
 881  *                             <---------------(*1)----------*
 882  *
 883  * +11               +15       +17       +19            +20              +21
 884  * +-----------------+---------+---------+--------------+----------------+
 885  * |uncompressed size|time(DOS)|date(DOS)|attribute(DOS)|header level(=1)|
 886  * +-----------------+---------+---------+--------------+----------------+
 887  * *-------------------------------(*1)----------------------------------*
 888  *
 889  * +21             +22       +22+(*3)   +22+(*3)+2  +22+(*3)+3  +22+(*3)+3+(*4)
 890  * +---------------+---------+----------+-----------+-----------+
 891  * |name length(*3)|file name|file CRC16|  creator  |padding(*4)|
 892  * +---------------+---------+----------+-----------+-----------+
 893  *                  <--(*3)->
 894  * *----------------------------(*1)----------------------------*
 895  *
 896  * +22+(*3)+3+(*4)  +22+(*3)+3+(*4)+2     +22+(*3)+3+(*4)+2+(*5)
 897  * +----------------+---------------------+------------------------+
 898  * |next header size| extended header(*5) |     compressed data    |
 899  * +----------------+---------------------+------------------------+
 900  * *------(*1)-----> <--------------------(*2)-------------------->
 901  */
 902 #define H1_HEADER_SIZE_OFFSET   0
 903 #define H1_HEADER_SUM_OFFSET    1
 904 #define H1_COMP_SIZE_OFFSET     7
 905 #define H1_ORIG_SIZE_OFFSET     11
 906 #define H1_DOS_TIME_OFFSET      15
 907 #define H1_NAME_LEN_OFFSET      21
 908 #define H1_FILE_NAME_OFFSET     22
 909 #define H1_FIXED_SIZE           27
 910 static int
 911 lha_read_file_header_1(struct archive_read *a, struct lha *lha)
 912 {
 913         const unsigned char *p;
 914         size_t extdsize;
 915         int i, err, err2;
 916         int namelen, padding;
 917         unsigned char headersum, sum_calculated;
 918
 919         err = ARCHIVE_OK;
 920
 921         if ((p = __archive_read_ahead(a, H1_FIXED_SIZE, NULL)) == NULL)
 922                 return (truncated_error(a));
 923
 924         lha->header_size = p[H1_HEADER_SIZE_OFFSET] + 2;
 925         headersum = p[H1_HEADER_SUM_OFFSET];
 926         /* Note: An extended header size is included in a compsize. */
 927         lha->compsize = archive_le32dec(p + H1_COMP_SIZE_OFFSET);
 928         lha->origsize = archive_le32dec(p + H1_ORIG_SIZE_OFFSET);
 929         lha->mtime = lha_dos_time(p + H1_DOS_TIME_OFFSET);
 930         namelen = p[H1_NAME_LEN_OFFSET];
 931         /* Calculate a padding size. The result will be normally 0 only(?) */
 932         padding = ((int)lha->header_size) - H1_FIXED_SIZE - namelen;
 933
 934         if (namelen > 230 || padding < 0)
 935                 goto invalid;
 936
 937         if ((p = __archive_read_ahead(a, lha->header_size, NULL)) == NULL)
 938                 return (truncated_error(a));
 939
 940         for (i = 0; i < namelen; i++) {
 941                 if (p[i + H1_FILE_NAME_OFFSET] == 0xff)
 942                         goto invalid;/* Invalid filename. */
 943         }
 944         archive_strncpy(&lha->filename, p + H1_FILE_NAME_OFFSET, namelen);
 945         lha->crc = archive_le16dec(p + H1_FILE_NAME_OFFSET + namelen);
 946         lha->setflag |= CRC_IS_SET;
 947
 948         sum_calculated = lha_calcsum(0, p, 2, lha->header_size - 2);
 949         /* Consume used bytes but not include `next header size' data
 950          * since it will be consumed in lha_read_file_extended_header(). */
 951         __archive_read_consume(a, lha->header_size - 2);
 952
 953         /* Read extended headers */
 954         err2 = lha_read_file_extended_header(a, lha, NULL, 2,
 955             (size_t)(lha->compsize + 2), &extdsize);
 956         if (err2 < ARCHIVE_WARN)
 957                 return (err2);
 958         if (err2 < err)
 959                 err = err2;
 960         /* Get a real compressed file size. */
 961         lha->compsize -= extdsize - 2;
 962
 963         if (sum_calculated != headersum) {
 964                 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
 965                     "LHa header sum error");
 966                 return (ARCHIVE_FATAL);
 967         }
 968         return (err);
 969 invalid:
 970         archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
 971             "Invalid LHa header");
 972         return (ARCHIVE_FATAL);
 973 }
 974
 975 /*
 976  * Header 2 format
 977  *
 978  * +0              +2               +7                  +11               +15
 979  * +---------------+----------------+-------------------+-----------------+
 980  * |header size(*1)|compression type|compressed size(*2)|uncompressed size|
 981  * +---------------+----------------+-------------------+-----------------+
 982  *  <--------------------------------(*1)---------------------------------*
 983  *
 984  * +15               +19          +20              +21        +23         +24
 985  * +-----------------+------------+----------------+----------+-----------+
 986  * |data/time(time_t)| 0x20 fixed |header level(=2)|file CRC16|  creator  |
 987  * +-----------------+------------+----------------+----------+-----------+
 988  * *---------------------------------(*1)---------------------------------*
 989  *
 990  * +24              +26                 +26+(*3)      +26+(*3)+(*4)
 991  * +----------------+-------------------+-------------+-------------------+
 992  * |next header size|extended header(*3)| padding(*4) |  compressed data  |
 993  * +----------------+-------------------+-------------+-------------------+
 994  * *--------------------------(*1)-------------------> <------(*2)------->
 995  *
 996  */
 997 #define H2_HEADER_SIZE_OFFSET   0
 998 #define H2_COMP_SIZE_OFFSET     7
 999 #define H2_ORIG_SIZE_OFFSET     11
1000 #define H2_TIME_OFFSET          15
1001 #define H2_CRC_OFFSET           21
1002 #define H2_FIXED_SIZE           24
1003 static int
1004 lha_read_file_header_2(struct archive_read *a, struct lha *lha)
1005 {
1006         const unsigned char *p;
1007         size_t extdsize;
1008         int err, padding;
1009         uint16_t header_crc;
1010
1011         if ((p = __archive_read_ahead(a, H2_FIXED_SIZE, NULL)) == NULL)
1012                 return (truncated_error(a));
1013
1014         lha->header_size =archive_le16dec(p + H2_HEADER_SIZE_OFFSET);
1015         lha->compsize = archive_le32dec(p + H2_COMP_SIZE_OFFSET);
1016         lha->origsize = archive_le32dec(p + H2_ORIG_SIZE_OFFSET);
1017         lha->mtime = archive_le32dec(p + H2_TIME_OFFSET);
1018         lha->crc = archive_le16dec(p + H2_CRC_OFFSET);
1019         lha->setflag |= CRC_IS_SET;
1020
1021         if (lha->header_size < H2_FIXED_SIZE) {
1022                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1023                     "Invalid LHa header size");
1024                 return (ARCHIVE_FATAL);
1025         }
1026
1027         header_crc = lha_crc16(0, p, H2_FIXED_SIZE);
1028         __archive_read_consume(a, H2_FIXED_SIZE);
1029
1030         /* Read extended headers */
1031         err = lha_read_file_extended_header(a, lha, &header_crc, 2,
1032                   lha->header_size - H2_FIXED_SIZE, &extdsize);
1033         if (err < ARCHIVE_WARN)
1034                 return (err);
1035
1036         /* Calculate a padding size. The result will be normally 0 or 1. */
1037         padding = (int)lha->header_size - (int)(H2_FIXED_SIZE + extdsize);
1038         if (padding > 0) {
1039                 if ((p = __archive_read_ahead(a, padding, NULL)) == NULL)
1040                         return (truncated_error(a));
1041                 header_crc = lha_crc16(header_crc, p, padding);
1042                 __archive_read_consume(a, padding);
1043         }
1044
1045         if (header_crc != lha->header_crc) {
1046                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1047                     "LHa header CRC error");
1048                 return (ARCHIVE_FATAL);
1049         }
1050         return (err);
1051 }
1052
1053 /*
1054  * Header 3 format
1055  *
1056  * +0           +2               +7                  +11               +15
1057  * +------------+----------------+-------------------+-----------------+
1058  * | 0x04 fixed |compression type|compressed size(*2)|uncompressed size|
1059  * +------------+----------------+-------------------+-----------------+
1060  *  <-------------------------------(*1)-------------------------------*
1061  *
1062  * +15               +19          +20              +21        +23         +24
1063  * +-----------------+------------+----------------+----------+-----------+
1064  * |date/time(time_t)| 0x20 fixed |header level(=3)|file CRC16|  creator  |
1065  * +-----------------+------------+----------------+----------+-----------+
1066  * *--------------------------------(*1)----------------------------------*
1067  *
1068  * +24             +28              +32                 +32+(*3)
1069  * +---------------+----------------+-------------------+-----------------+
1070  * |header size(*1)|next header size|extended header(*3)| compressed data |
1071  * +---------------+----------------+-------------------+-----------------+
1072  * *------------------------(*1)-----------------------> <------(*2)----->
1073  *
1074  */
1075 #define H3_FIELD_LEN_OFFSET     0
1076 #define H3_COMP_SIZE_OFFSET     7
1077 #define H3_ORIG_SIZE_OFFSET     11
1078 #define H3_TIME_OFFSET          15
1079 #define H3_CRC_OFFSET           21
1080 #define H3_HEADER_SIZE_OFFSET   24
1081 #define H3_FIXED_SIZE           28
1082 static int
1083 lha_read_file_header_3(struct archive_read *a, struct lha *lha)
1084 {
1085         const unsigned char *p;
1086         size_t extdsize;
1087         int err;
1088         uint16_t header_crc;
1089
1090         if ((p = __archive_read_ahead(a, H3_FIXED_SIZE, NULL)) == NULL)
1091                 return (truncated_error(a));
1092
1093         if (archive_le16dec(p + H3_FIELD_LEN_OFFSET) != 4)
1094                 goto invalid;
1095         lha->header_size =archive_le32dec(p + H3_HEADER_SIZE_OFFSET);
1096         lha->compsize = archive_le32dec(p + H3_COMP_SIZE_OFFSET);
1097         lha->origsize = archive_le32dec(p + H3_ORIG_SIZE_OFFSET);
1098         lha->mtime = archive_le32dec(p + H3_TIME_OFFSET);
1099         lha->crc = archive_le16dec(p + H3_CRC_OFFSET);
1100         lha->setflag |= CRC_IS_SET;
1101
1102         if (lha->header_size < H3_FIXED_SIZE + 4)
1103                 goto invalid;
1104         header_crc = lha_crc16(0, p, H3_FIXED_SIZE);
1105         __archive_read_consume(a, H3_FIXED_SIZE);
1106
1107         /* Read extended headers */
1108         err = lha_read_file_extended_header(a, lha, &header_crc, 4,
1109                   lha->header_size - H3_FIXED_SIZE, &extdsize);
1110         if (err < ARCHIVE_WARN)
1111                 return (err);
1112
1113         if (header_crc != lha->header_crc) {
1114                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1115                     "LHa header CRC error");
1116                 return (ARCHIVE_FATAL);
1117         }
1118         return (err);
1119 invalid:
1120         archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1121             "Invalid LHa header");
1122         return (ARCHIVE_FATAL);
1123 }
1124
1125 /*
1126  * Extended header format
1127  *
1128  * +0             +2        +3  -- used in header 1 and 2
1129  * +0             +4        +5  -- used in header 3
1130  * +--------------+---------+-------------------+--------------+--
1131  * |ex-header size|header id|        data       |ex-header size| .......
1132  * +--------------+---------+-------------------+--------------+--
1133  *  <-------------( ex-header size)------------> <-- next extended header --*
1134  *
1135  * If the ex-header size is zero, it is the make of the end of extended
1136  * headers.
1137  *
1138  */
1139 static int
1140 lha_read_file_extended_header(struct archive_read *a, struct lha *lha,
1141     uint16_t *crc, int sizefield_length, size_t limitsize, size_t *total_size)
1142 {
1143         const void *h;
1144         const unsigned char *extdheader;
1145         size_t  extdsize;
1146         size_t  datasize;
1147         unsigned int i;
1148         unsigned char extdtype;
1149
1150 #define EXT_HEADER_CRC          0x00            /* Header CRC and information*/
1151 #define EXT_FILENAME            0x01            /* Filename                 */
1152 #define EXT_DIRECTORY           0x02            /* Directory name           */
1153 #define EXT_DOS_ATTR            0x40            /* MS-DOS attribute         */
1154 #define EXT_TIMESTAMP           0x41            /* Windows time stamp       */
1155 #define EXT_FILESIZE            0x42            /* Large file size          */
1156 #define EXT_TIMEZONE            0x43            /* Time zone                */
1157 #define EXT_UTF16_FILENAME      0x44            /* UTF-16 filename          */
1158 #define EXT_UTF16_DIRECTORY     0x45            /* UTF-16 directory name    */
1159 #define EXT_CODEPAGE            0x46            /* Codepage                 */
1160 #define EXT_UNIX_MODE           0x50            /* File permission          */
1161 #define EXT_UNIX_GID_UID        0x51            /* gid,uid                  */
1162 #define EXT_UNIX_GNAME          0x52            /* Group name               */
1163 #define EXT_UNIX_UNAME          0x53            /* User name                */
1164 #define EXT_UNIX_MTIME          0x54            /* Modified time            */
1165 #define EXT_OS2_NEW_ATTR        0x7f            /* new attribute(OS/2 only) */
1166 #define EXT_NEW_ATTR            0xff            /* new attribute            */
1167
1168         *total_size = sizefield_length;
1169
1170         for (;;) {
1171                 /* Read an extended header size. */
1172                 if ((h =
1173                     __archive_read_ahead(a, sizefield_length, NULL)) == NULL)
1174                         return (truncated_error(a));
1175                 /* Check if the size is the zero indicates the end of the
1176                  * extended header. */
1177                 if (sizefield_length == sizeof(uint16_t))
1178                         extdsize = archive_le16dec(h);
1179                 else
1180                         extdsize = archive_le32dec(h);
1181                 if (extdsize == 0) {
1182                         /* End of extended header */
1183                         if (crc != NULL)
1184                                 *crc = lha_crc16(*crc, h, sizefield_length);
1185                         __archive_read_consume(a, sizefield_length);
1186                         return (ARCHIVE_OK);
1187                 }
1188
1189                 /* Sanity check to the extended header size. */
1190                 if (((uint64_t)*total_size + extdsize) >
1191                                     (uint64_t)limitsize ||
1192                     extdsize <= (size_t)sizefield_length)
1193                         goto invalid;
1194
1195                 /* Read the extended header. */
1196                 if ((h = __archive_read_ahead(a, extdsize, NULL)) == NULL)
1197                         return (truncated_error(a));
1198                 *total_size += extdsize;
1199
1200                 extdheader = (const unsigned char *)h;
1201                 /* Get the extended header type. */
1202                 extdtype = extdheader[sizefield_length];
1203                 /* Calculate an extended data size. */
1204                 datasize = extdsize - (1 + sizefield_length);
1205                 /* Skip an extended header size field and type field. */
1206                 extdheader += sizefield_length + 1;
1207
1208                 if (crc != NULL && extdtype != EXT_HEADER_CRC)
1209                         *crc = lha_crc16(*crc, h, extdsize);
1210                 switch (extdtype) {
1211                 case EXT_HEADER_CRC:
1212                         /* We only use a header CRC. Following data will not
1213                          * be used. */
1214                         if (datasize >= 2) {
1215                                 lha->header_crc = archive_le16dec(extdheader);
1216                                 if (crc != NULL) {
1217                                         static const char zeros[2] = {0, 0};
1218                                         *crc = lha_crc16(*crc, h,
1219                                             extdsize - datasize);
1220                                         /* CRC value itself as zero */
1221                                         *crc = lha_crc16(*crc, zeros, 2);
1222                                         *crc = lha_crc16(*crc,
1223                                             extdheader+2, datasize - 2);
1224                                 }
1225                         }
1226                         break;
1227                 case EXT_FILENAME:
1228                         if (datasize == 0) {
1229                                 /* maybe directory header */
1230                                 archive_string_empty(&lha->filename);
1231                                 break;
1232                         }
1233                         archive_strncpy(&lha->filename,
1234                             (const char *)extdheader, datasize);
1235                         break;
1236                 case EXT_DIRECTORY:
1237                         if (datasize == 0)
1238                                 /* no directory name data. exit this case. */
1239                                 break;
1240
1241                         archive_strncpy(&lha->dirname,
1242                             (const char *)extdheader, datasize);
1243                         /*
1244                          * Convert directory delimiter from 0xFF
1245                          * to '/' for local system.
1246                          */
1247                         for (i = 0; i < lha->dirname.length; i++) {
1248                                 if ((unsigned char)lha->dirname.s[i] == 0xFF)
1249                                         lha->dirname.s[i] = '/';
1250                         }
1251                         /* Is last character directory separator? */
1252                         if (lha->dirname.s[lha->dirname.length-1] != '/')
1253                                 /* invalid directory data */
1254                                 goto invalid;
1255                         break;
1256                 case EXT_DOS_ATTR:
1257                         if (datasize == 2)
1258                                 lha->dos_attr = (unsigned char)
1259                                     (archive_le16dec(extdheader) & 0xff);
1260                         break;
1261                 case EXT_TIMESTAMP:
1262                         if (datasize == (sizeof(uint64_t) * 3)) {
1263                                 lha->birthtime = lha_win_time(
1264                                     archive_le64dec(extdheader),
1265                                     &lha->birthtime_tv_nsec);
1266                                 extdheader += sizeof(uint64_t);
1267                                 lha->mtime = lha_win_time(
1268                                     archive_le64dec(extdheader),
1269                                     &lha->mtime_tv_nsec);
1270                                 extdheader += sizeof(uint64_t);
1271                                 lha->atime = lha_win_time(
1272                                     archive_le64dec(extdheader),
1273                                     &lha->atime_tv_nsec);
1274                                 lha->setflag |= BIRTHTIME_IS_SET |
1275                                     ATIME_IS_SET;
1276                         }
1277                         break;
1278                 case EXT_FILESIZE:
1279                         if (datasize == sizeof(uint64_t) * 2) {
1280                                 lha->compsize = archive_le64dec(extdheader);
1281                                 extdheader += sizeof(uint64_t);
1282                                 lha->origsize = archive_le64dec(extdheader);
1283                         }
1284                         break;
1285                 case EXT_CODEPAGE:
1286                         /* Get an archived filename charset from codepage.
1287                          * This overwrites the charset specified by
1288                          * hdrcharset option. */
1289                         if (datasize == sizeof(uint32_t)) {
1290                                 struct archive_string cp;
1291                                 const char *charset;
1292
1293                                 archive_string_init(&cp);
1294                                 switch (archive_le32dec(extdheader)) {
1295                                 case 65001: /* UTF-8 */
1296                                         charset = "UTF-8";
1297                                         break;
1298                                 default:
1299                                         archive_string_sprintf(&cp, "CP%d",
1300                                             (int)archive_le32dec(extdheader));
1301                                         charset = cp.s;
1302                                         break;
1303                                 }
1304                                 lha->sconv =
1305                                     archive_string_conversion_from_charset(
1306                                         &(a->archive), charset, 1);
1307                                 archive_string_free(&cp);
1308                                 if (lha->sconv == NULL)
1309                                         return (ARCHIVE_FATAL);
1310                         }
1311                         break;
1312                 case EXT_UNIX_MODE:
1313                         if (datasize == sizeof(uint16_t)) {
1314                                 lha->mode = archive_le16dec(extdheader);
1315                                 lha->setflag |= UNIX_MODE_IS_SET;
1316                         }
1317                         break;
1318                 case EXT_UNIX_GID_UID:
1319                         if (datasize == (sizeof(uint16_t) * 2)) {
1320                                 lha->gid = archive_le16dec(extdheader);
1321                                 lha->uid = archive_le16dec(extdheader+2);
1322                         }
1323                         break;
1324                 case EXT_UNIX_GNAME:
1325                         if (datasize > 0)
1326                                 archive_strncpy(&lha->gname,
1327                                     (const char *)extdheader, datasize);
1328                         break;
1329                 case EXT_UNIX_UNAME:
1330                         if (datasize > 0)
1331                                 archive_strncpy(&lha->uname,
1332                                     (const char *)extdheader, datasize);
1333                         break;
1334                 case EXT_UNIX_MTIME:
1335                         if (datasize == sizeof(uint32_t))
1336                                 lha->mtime = archive_le32dec(extdheader);
1337                         break;
1338                 case EXT_OS2_NEW_ATTR:
1339                         /* This extended header is OS/2 depend. */
1340                         if (datasize == 16) {
1341                                 lha->dos_attr = (unsigned char)
1342                                     (archive_le16dec(extdheader) & 0xff);
1343                                 lha->mode = archive_le16dec(extdheader+2);
1344                                 lha->gid = archive_le16dec(extdheader+4);
1345                                 lha->uid = archive_le16dec(extdheader+6);
1346                                 lha->birthtime = archive_le32dec(extdheader+8);
1347                                 lha->atime = archive_le32dec(extdheader+12);
1348                                 lha->setflag |= UNIX_MODE_IS_SET
1349                                     | BIRTHTIME_IS_SET | ATIME_IS_SET;
1350                         }
1351                         break;
1352                 case EXT_NEW_ATTR:
1353                         if (datasize == 20) {
1354                                 lha->mode = (mode_t)archive_le32dec(extdheader);
1355                                 lha->gid = archive_le32dec(extdheader+4);
1356                                 lha->uid = archive_le32dec(extdheader+8);
1357                                 lha->birthtime = archive_le32dec(extdheader+12);
1358                                 lha->atime = archive_le32dec(extdheader+16);
1359                                 lha->setflag |= UNIX_MODE_IS_SET
1360                                     | BIRTHTIME_IS_SET | ATIME_IS_SET;
1361                         }
1362                         break;
1363                 case EXT_TIMEZONE:              /* Not supported */
1364                 case EXT_UTF16_FILENAME:        /* Not supported */
1365                 case EXT_UTF16_DIRECTORY:       /* Not supported */
1366                 default:
1367                         break;
1368                 }
1369
1370                 __archive_read_consume(a, extdsize);
1371         }
1372 invalid:
1373         archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1374             "Invalid extended LHa header");
1375         return (ARCHIVE_FATAL);
1376 }
1377
1378 static int
1379 archive_read_format_lha_read_data(struct archive_read *a,
1380     const void **buff, size_t *size, int64_t *offset)
1381 {
1382         struct lha *lha = (struct lha *)(a->format->data);
1383         int r;
1384
1385         if (lha->entry_unconsumed) {
1386                 /* Consume as much as the decompressor actually used. */
1387                 __archive_read_consume(a, lha->entry_unconsumed);
1388                 lha->entry_unconsumed = 0;
1389         }
1390         if (lha->end_of_entry) {
1391                 if (!lha->end_of_entry_cleanup) {
1392                         if ((lha->setflag & CRC_IS_SET) &&
1393                             lha->crc != lha->entry_crc_calculated) {
1394                                 archive_set_error(&a->archive,
1395                                     ARCHIVE_ERRNO_MISC,
1396                                     "LHa data CRC error");
1397                                 return (ARCHIVE_WARN);
1398                         }
1399
1400                         /* End-of-entry cleanup done. */
1401                         lha->end_of_entry_cleanup = 1;
1402                 }
1403                 *offset = lha->entry_offset;
1404                 *size = 0;
1405                 *buff = NULL;
1406                 return (ARCHIVE_EOF);
1407         }
1408
1409         if (lha->entry_is_compressed)
1410                 r =  lha_read_data_lzh(a, buff, size, offset);
1411         else
1412                 /* No compression. */
1413                 r =  lha_read_data_none(a, buff, size, offset);
1414         return (r);
1415 }
1416
1417 /*
1418  * Read a file content in no compression.
1419  *
1420  * Returns ARCHIVE_OK if successful, ARCHIVE_FATAL otherwise, sets
1421  * lha->end_of_entry if it consumes all of the data.
1422  */
1423 static int
1424 lha_read_data_none(struct archive_read *a, const void **buff,
1425     size_t *size, int64_t *offset)
1426 {
1427         struct lha *lha = (struct lha *)(a->format->data);
1428         ssize_t bytes_avail;
1429
1430         if (lha->entry_bytes_remaining == 0) {
1431                 *buff = NULL;
1432                 *size = 0;
1433                 *offset = lha->entry_offset;
1434                 lha->end_of_entry = 1;
1435                 return (ARCHIVE_OK);
1436         }
1437         /*
1438          * Note: '1' here is a performance optimization.
1439          * Recall that the decompression layer returns a count of
1440          * available bytes; asking for more than that forces the
1441          * decompressor to combine reads by copying data.
1442          */
1443         *buff = __archive_read_ahead(a, 1, &bytes_avail);
1444         if (bytes_avail <= 0) {
1445                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1446                     "Truncated LHa file data");
1447                 return (ARCHIVE_FATAL);
1448         }
1449         if (bytes_avail > lha->entry_bytes_remaining)
1450                 bytes_avail = (ssize_t)lha->entry_bytes_remaining;
1451         lha->entry_crc_calculated =
1452             lha_crc16(lha->entry_crc_calculated, *buff, bytes_avail);
1453         *size = bytes_avail;
1454         *offset = lha->entry_offset;
1455         lha->entry_offset += bytes_avail;
1456         lha->entry_bytes_remaining -= bytes_avail;
1457         if (lha->entry_bytes_remaining == 0)
1458                 lha->end_of_entry = 1;
1459         lha->entry_unconsumed = bytes_avail;
1460         return (ARCHIVE_OK);
1461 }
1462
1463 /*
1464  * Read a file content in LZHUFF encoding.
1465  *
1466  * Returns ARCHIVE_OK if successful, returns ARCHIVE_WARN if compression is
1467  * unsupported, ARCHIVE_FATAL otherwise, sets lha->end_of_entry if it consumes
1468  * all of the data.
1469  */
1470 static int
1471 lha_read_data_lzh(struct archive_read *a, const void **buff,
1472     size_t *size, int64_t *offset)
1473 {
1474         struct lha *lha = (struct lha *)(a->format->data);
1475         ssize_t bytes_avail;
1476         int r;
1477
1478         /* If the buffer hasn't been allocated, allocate it now. */
1479         if (lha->uncompressed_buffer == NULL) {
1480                 lha->uncompressed_buffer_size = 64 * 1024;
1481                 lha->uncompressed_buffer
1482                     = (unsigned char *)malloc(lha->uncompressed_buffer_size);
1483                 if (lha->uncompressed_buffer == NULL) {
1484                         archive_set_error(&a->archive, ENOMEM,
1485                             "No memory for lzh decompression");
1486                         return (ARCHIVE_FATAL);
1487                 }
1488         }
1489
1490         /* If we haven't yet read any data, initialize the decompressor. */
1491         if (!lha->decompress_init) {
1492                 r = lzh_decode_init(&(lha->strm), lha->method);
1493                 switch (r) {
1494                 case ARCHIVE_OK:
1495                         break;
1496                 case ARCHIVE_FAILED:
1497                         /* Unsupported compression. */
1498                         *buff = NULL;
1499                         *size = 0;
1500                         *offset = 0;
1501                         archive_set_error(&a->archive,
1502                             ARCHIVE_ERRNO_FILE_FORMAT,
1503                             "Unsupported lzh compression method -%c%c%c-",
1504                             lha->method[0], lha->method[1], lha->method[2]);
1505                         /* We know compressed size; just skip it. */
1506                         archive_read_format_lha_read_data_skip(a);
1507                         return (ARCHIVE_WARN);
1508                 default:
1509                         archive_set_error(&a->archive, ENOMEM,
1510                             "Couldn't allocate memory "
1511                             "for lzh decompression");
1512                         return (ARCHIVE_FATAL);
1513                 }
1514                 /* We've initialized decompression for this stream. */
1515                 lha->decompress_init = 1;
1516                 lha->strm.avail_out = 0;
1517                 lha->strm.total_out = 0;
1518         }
1519
1520         /*
1521          * Note: '1' here is a performance optimization.
1522          * Recall that the decompression layer returns a count of
1523          * available bytes; asking for more than that forces the
1524          * decompressor to combine reads by copying data.
1525          */
1526         lha->strm.next_in = __archive_read_ahead(a, 1, &bytes_avail);
1527         if (bytes_avail <= 0) {
1528                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1529                     "Truncated LHa file body");
1530                 return (ARCHIVE_FATAL);
1531         }
1532         if (bytes_avail > lha->entry_bytes_remaining)
1533                 bytes_avail = (ssize_t)lha->entry_bytes_remaining;
1534
1535         lha->strm.avail_in = bytes_avail;
1536         lha->strm.total_in = 0;
1537         if (lha->strm.avail_out == 0) {
1538                 lha->strm.next_out = lha->uncompressed_buffer;
1539                 lha->strm.avail_out = lha->uncompressed_buffer_size;
1540         }
1541
1542         r = lzh_decode(&(lha->strm), bytes_avail == lha->entry_bytes_remaining);
1543         switch (r) {
1544         case ARCHIVE_OK:
1545                 break;
1546         case ARCHIVE_EOF:
1547                 lha->end_of_entry = 1;
1548                 break;
1549         default:
1550                 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
1551                     "Bad lzh data");
1552                 return (ARCHIVE_FAILED);
1553         }
1554         lha->entry_unconsumed = lha->strm.total_in;
1555         lha->entry_bytes_remaining -= lha->strm.total_in;
1556
1557         if (lha->strm.avail_out == 0 || lha->end_of_entry) {
1558                 *offset = lha->entry_offset;
1559                 *size = lha->strm.next_out - lha->uncompressed_buffer;
1560                 *buff = lha->uncompressed_buffer;
1561                 lha->entry_crc_calculated =
1562                     lha_crc16(lha->entry_crc_calculated, *buff, *size);
1563                 lha->entry_offset += *size;
1564         } else {
1565                 *offset = lha->entry_offset;
1566                 *size = 0;
1567                 *buff = NULL;
1568         }
1569         return (ARCHIVE_OK);
1570 }
1571
1572 /*
1573  * Skip a file content.
1574  */
1575 static int
1576 archive_read_format_lha_read_data_skip(struct archive_read *a)
1577 {
1578         struct lha *lha;
1579         int64_t bytes_skipped;
1580
1581         lha = (struct lha *)(a->format->data);
1582
1583         if (lha->entry_unconsumed) {
1584                 /* Consume as much as the decompressor actually used. */
1585                 __archive_read_consume(a, lha->entry_unconsumed);
1586                 lha->entry_unconsumed = 0;
1587         }
1588
1589         /* if we've already read to end of data, we're done. */
1590         if (lha->end_of_entry_cleanup)
1591                 return (ARCHIVE_OK);
1592
1593         /*
1594          * If the length is at the beginning, we can skip the
1595          * compressed data much more quickly.
1596          */
1597         bytes_skipped = __archive_read_consume(a, lha->entry_bytes_remaining);
1598         if (bytes_skipped < 0)
1599                 return (ARCHIVE_FATAL);
1600
1601         /* This entry is finished and done. */
1602         lha->end_of_entry_cleanup = lha->end_of_entry = 1;
1603         return (ARCHIVE_OK);
1604 }
1605
1606 static int
1607 archive_read_format_lha_cleanup(struct archive_read *a)
1608 {
1609         struct lha *lha = (struct lha *)(a->format->data);
1610
1611         lzh_decode_free(&(lha->strm));
1612         free(lha->uncompressed_buffer);
1613         archive_string_free(&(lha->dirname));
1614         archive_string_free(&(lha->filename));
1615         archive_string_free(&(lha->uname));
1616         archive_string_free(&(lha->gname));
1617         archive_wstring_free(&(lha->ws));
1618         free(lha);
1619         (a->format->data) = NULL;
1620         return (ARCHIVE_OK);
1621 }
1622
1623 /*
1624  * 'LHa for UNIX' utility has archived a symbolic-link name after
1625  * a pathname with '|' character.
1626  * This function extracts the symbolic-link name from the pathname.
1627  *
1628  * example.
1629  *   1. a symbolic-name is 'aaa/bb/cc'
1630  *   2. a filename is 'xxx/bbb'
1631  *  then a archived pathname is 'xxx/bbb|aaa/bb/cc'
1632  */
1633 static int
1634 lha_parse_linkname(struct archive_string *linkname,
1635     struct archive_string *pathname)
1636 {
1637         char *  linkptr;
1638         size_t  symlen;
1639
1640         linkptr = strchr(pathname->s, '|');
1641         if (linkptr != NULL) {
1642                 symlen = strlen(linkptr + 1);
1643                 archive_strncpy(linkname, linkptr+1, symlen);
1644
1645                 *linkptr = 0;
1646                 pathname->length = strlen(pathname->s);
1647
1648                 return (1);
1649         }
1650         return (0);
1651 }
1652
1653 /* Convert an MSDOS-style date/time into Unix-style time. */
1654 static time_t
1655 lha_dos_time(const unsigned char *p)
1656 {
1657         int msTime, msDate;
1658         struct tm ts;
1659
1660         msTime = archive_le16dec(p);
1661         msDate = archive_le16dec(p+2);
1662
1663         memset(&ts, 0, sizeof(ts));
1664         ts.tm_year = ((msDate >> 9) & 0x7f) + 80;   /* Years since 1900. */
1665         ts.tm_mon = ((msDate >> 5) & 0x0f) - 1;     /* Month number.     */
1666         ts.tm_mday = msDate & 0x1f;                 /* Day of month.     */
1667         ts.tm_hour = (msTime >> 11) & 0x1f;
1668         ts.tm_min = (msTime >> 5) & 0x3f;
1669         ts.tm_sec = (msTime << 1) & 0x3e;
1670         ts.tm_isdst = -1;
1671         return (mktime(&ts));
1672 }
1673
1674 /* Convert an MS-Windows-style date/time into Unix-style time. */
1675 static time_t
1676 lha_win_time(uint64_t wintime, long *ns)
1677 {
1678 #define EPOC_TIME ARCHIVE_LITERAL_ULL(116444736000000000)
1679
1680         if (wintime >= EPOC_TIME) {
1681                 wintime -= EPOC_TIME;   /* 1970-01-01 00:00:00 (UTC) */
1682                 if (ns != NULL)
1683                         *ns = (long)(wintime % 10000000) * 100;
1684                 return (wintime / 10000000);
1685         } else {
1686                 if (ns != NULL)
1687                         *ns = 0;
1688                 return (0);
1689         }
1690 }
1691
1692 static unsigned char
1693 lha_calcsum(unsigned char sum, const void *pp, int offset, size_t size)
1694 {
1695         unsigned char const *p = (unsigned char const *)pp;
1696
1697         p += offset;
1698         for (;size > 0; --size)
1699                 sum += *p++;
1700         return (sum);
1701 }
1702
1703 #define CRC16(crc, v)   do {    \
1704         (crc) = crc16tbl[((crc) ^ v) & 0xFF] ^ ((crc) >> 8);    \
1705 } while (0)
1706
1707 static uint16_t
1708 lha_crc16(uint16_t crc, const void *pp, size_t len)
1709 {
1710         const unsigned char *buff = (const unsigned char *)pp;
1711
1712         while (len >= 8) {
1713                 CRC16(crc, *buff++); CRC16(crc, *buff++);
1714                 CRC16(crc, *buff++); CRC16(crc, *buff++);
1715                 CRC16(crc, *buff++); CRC16(crc, *buff++);
1716                 CRC16(crc, *buff++); CRC16(crc, *buff++);
1717                 len -= 8;
1718         }
1719         switch (len) {
1720         case 7:
1721                 CRC16(crc, *buff++);
1722                 /* FALL THROUGH */
1723         case 6:
1724                 CRC16(crc, *buff++);
1725                 /* FALL THROUGH */
1726         case 5:
1727                 CRC16(crc, *buff++);
1728                 /* FALL THROUGH */
1729         case 4:
1730                 CRC16(crc, *buff++);
1731                 /* FALL THROUGH */
1732         case 3:
1733                 CRC16(crc, *buff++);
1734                 /* FALL THROUGH */
1735         case 2:
1736                 CRC16(crc, *buff++);
1737                 /* FALL THROUGH */
1738         case 1:
1739                 CRC16(crc, *buff);
1740                 /* FALL THROUGH */
1741         case 0:
1742                 break;
1743         }
1744         return (crc);
1745 }
1746
1747
1748 /*
1749  * Initialize LZHUF decoder.
1750  *
1751  * Returns ARCHIVE_OK if initialization was successful.
1752  * Returns ARCHIVE_FAILED if method is unsupported.
1753  * Returns ARCHIVE_FATAL if initialization failed; memory allocation
1754  * error occurred.
1755  */
1756 static int
1757 lzh_decode_init(struct lzh_stream *strm, const char *method)
1758 {
1759         struct lzh_dec *ds;
1760         int w_bits, w_size;
1761
1762         if (strm->ds == NULL) {
1763                 strm->ds = calloc(1, sizeof(*strm->ds));
1764                 if (strm->ds == NULL)
1765                         return (ARCHIVE_FATAL);
1766         }
1767         ds = strm->ds;
1768         ds->error = ARCHIVE_FAILED;
1769         if (method == NULL || method[0] != 'l' || method[1] != 'h')
1770                 return (ARCHIVE_FAILED);
1771         switch (method[2]) {
1772         case '5':
1773                 w_bits = 13;/* 8KiB for window */
1774                 break;
1775         case '6':
1776                 w_bits = 15;/* 32KiB for window */
1777                 break;
1778         case '7':
1779                 w_bits = 16;/* 64KiB for window */
1780                 break;
1781         default:
1782                 return (ARCHIVE_FAILED);/* Not supported. */
1783         }
1784         ds->error = ARCHIVE_FATAL;
1785         w_size = ds->w_size;
1786         ds->w_size = 1U << w_bits;
1787         ds->w_mask = ds->w_size -1;
1788         if (ds->w_buff == NULL || w_size != ds->w_size) {
1789                 free(ds->w_buff);
1790                 ds->w_buff = malloc(ds->w_size);
1791                 if (ds->w_buff == NULL)
1792                         return (ARCHIVE_FATAL);
1793         }
1794         memset(ds->w_buff, 0x20, ds->w_size);
1795         ds->w_pos = 0;
1796         ds->w_remaining = 0;
1797         ds->state = 0;
1798         ds->pos_pt_len_size = w_bits + 1;
1799         ds->pos_pt_len_bits = (w_bits == 15 || w_bits == 16)? 5: 4;
1800         ds->literal_pt_len_size = PT_BITLEN_SIZE;
1801         ds->literal_pt_len_bits = 5;
1802         ds->br.cache_buffer = 0;
1803         ds->br.cache_avail = 0;
1804
1805         if (lzh_huffman_init(&(ds->lt), LT_BITLEN_SIZE, 16)
1806             != ARCHIVE_OK)
1807                 return (ARCHIVE_FATAL);
1808         ds->lt.len_bits = 9;
1809         if (lzh_huffman_init(&(ds->pt), PT_BITLEN_SIZE, 16)
1810             != ARCHIVE_OK)
1811                 return (ARCHIVE_FATAL);
1812         ds->error = 0;
1813
1814         return (ARCHIVE_OK);
1815 }
1816
1817 /*
1818  * Release LZHUF decoder.
1819  */
1820 static void
1821 lzh_decode_free(struct lzh_stream *strm)
1822 {
1823
1824         if (strm->ds == NULL)
1825                 return;
1826         free(strm->ds->w_buff);
1827         lzh_huffman_free(&(strm->ds->lt));
1828         lzh_huffman_free(&(strm->ds->pt));
1829         free(strm->ds);
1830         strm->ds = NULL;
1831 }
1832
1833 /*
1834  * Bit stream reader.
1835  */
1836 /* Check that the cache buffer has enough bits. */
1837 #define lzh_br_has(br, n)       ((br)->cache_avail >= n)
1838 /* Get compressed data by bit. */
1839 #define lzh_br_bits(br, n)                              \
1840         (((uint16_t)((br)->cache_buffer >>              \
1841                 ((br)->cache_avail - (n)))) & cache_masks[n])
1842 #define lzh_br_bits_forced(br, n)                       \
1843         (((uint16_t)((br)->cache_buffer <<              \
1844                 ((n) - (br)->cache_avail))) & cache_masks[n])
1845 /* Read ahead to make sure the cache buffer has enough compressed data we
1846  * will use.
1847  *  True  : completed, there is enough data in the cache buffer.
1848  *  False : we met that strm->next_in is empty, we have to get following
1849  *          bytes. */
1850 #define lzh_br_read_ahead_0(strm, br, n)        \
1851         (lzh_br_has(br, (n)) || lzh_br_fillup(strm, br))
1852 /*  True  : the cache buffer has some bits as much as we need.
1853  *  False : there are no enough bits in the cache buffer to be used,
1854  *          we have to get following bytes if we could. */
1855 #define lzh_br_read_ahead(strm, br, n)  \
1856         (lzh_br_read_ahead_0((strm), (br), (n)) || lzh_br_has((br), (n)))
1857
1858 /* Notify how many bits we consumed. */
1859 #define lzh_br_consume(br, n)   ((br)->cache_avail -= (n))
1860 #define lzh_br_unconsume(br, n) ((br)->cache_avail += (n))
1861
1862 static const uint16_t cache_masks[] = {
1863         0x0000, 0x0001, 0x0003, 0x0007,
1864         0x000F, 0x001F, 0x003F, 0x007F,
1865         0x00FF, 0x01FF, 0x03FF, 0x07FF,
1866         0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF,
1867         0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF
1868 };
1869
1870 /*
1871  * Shift away used bits in the cache data and fill it up with following bits.
1872  * Call this when cache buffer does not have enough bits you need.
1873  *
1874  * Returns 1 if the cache buffer is full.
1875  * Returns 0 if the cache buffer is not full; input buffer is empty.
1876  */
1877 static int
1878 lzh_br_fillup(struct lzh_stream *strm, struct lzh_br *br)
1879 {
1880         int n = CACHE_BITS - br->cache_avail;
1881
1882         for (;;) {
1883                 switch (n >> 3) {
1884                 case 8:
1885                         if (strm->avail_in >= 8) {
1886                                 br->cache_buffer =
1887                                     ((uint64_t)strm->next_in[0]) << 56 |
1888                                     ((uint64_t)strm->next_in[1]) << 48 |
1889                                     ((uint64_t)strm->next_in[2]) << 40 |
1890                                     ((uint64_t)strm->next_in[3]) << 32 |
1891                                     ((uint32_t)strm->next_in[4]) << 24 |
1892                                     ((uint32_t)strm->next_in[5]) << 16 |
1893                                     ((uint32_t)strm->next_in[6]) << 8 |
1894                                      (uint32_t)strm->next_in[7];
1895                                 strm->next_in += 8;
1896                                 strm->avail_in -= 8;
1897                                 br->cache_avail += 8 * 8;
1898                                 return (1);
1899                         }
1900                         break;
1901                 case 7:
1902                         if (strm->avail_in >= 7) {
1903                                 br->cache_buffer =
1904                                    (br->cache_buffer << 56) |
1905                                     ((uint64_t)strm->next_in[0]) << 48 |
1906                                     ((uint64_t)strm->next_in[1]) << 40 |
1907                                     ((uint64_t)strm->next_in[2]) << 32 |
1908                                     ((uint32_t)strm->next_in[3]) << 24 |
1909                                     ((uint32_t)strm->next_in[4]) << 16 |
1910                                     ((uint32_t)strm->next_in[5]) << 8 |
1911                                      (uint32_t)strm->next_in[6];
1912                                 strm->next_in += 7;
1913                                 strm->avail_in -= 7;
1914                                 br->cache_avail += 7 * 8;
1915                                 return (1);
1916                         }
1917                         break;
1918                 case 6:
1919                         if (strm->avail_in >= 6) {
1920                                 br->cache_buffer =
1921                                    (br->cache_buffer << 48) |
1922                                     ((uint64_t)strm->next_in[0]) << 40 |
1923                                     ((uint64_t)strm->next_in[1]) << 32 |
1924                                     ((uint32_t)strm->next_in[2]) << 24 |
1925                                     ((uint32_t)strm->next_in[3]) << 16 |
1926                                     ((uint32_t)strm->next_in[4]) << 8 |
1927                                      (uint32_t)strm->next_in[5];
1928                                 strm->next_in += 6;
1929                                 strm->avail_in -= 6;
1930                                 br->cache_avail += 6 * 8;
1931                                 return (1);
1932                         }
1933                         break;
1934                 case 0:
1935                         /* We have enough compressed data in
1936                          * the cache buffer.*/
1937                         return (1);
1938                 default:
1939                         break;
1940                 }
1941                 if (strm->avail_in == 0) {
1942                         /* There is not enough compressed data to fill up the
1943                          * cache buffer. */
1944                         return (0);
1945                 }
1946                 br->cache_buffer =
1947                    (br->cache_buffer << 8) | *strm->next_in++;
1948                 strm->avail_in--;
1949                 br->cache_avail += 8;
1950                 n -= 8;
1951         }
1952 }
1953
1954 /*
1955  * Decode LZHUF.
1956  *
1957  * 1. Returns ARCHIVE_OK if output buffer or input buffer are empty.
1958  *    Please set available buffer and call this function again.
1959  * 2. Returns ARCHIVE_EOF if decompression has been completed.
1960  * 3. Returns ARCHIVE_FAILED if an error occurred; compressed data
1961  *    is broken or you do not set 'last' flag properly.
1962  * 4. 'last' flag is very important, you must set 1 to the flag if there
1963  *    is no input data. The lha compressed data format does not provide how
1964  *    to know the compressed data is really finished.
1965  *    Note: lha command utility check if the total size of output bytes is
1966  *    reached the uncompressed size recorded in its header. it does not mind
1967  *    that the decoding process is properly finished.
1968  *    GNU ZIP can decompress another compressed file made by SCO LZH compress.
1969  *    it handles EOF as null to fill read buffer with zero until the decoding
1970  *    process meet 2 bytes of zeros at reading a size of a next chunk, so the
1971  *    zeros are treated as the mark of the end of the data although the zeros
1972  *    is dummy, not the file data.
1973  */
1974 static int      lzh_read_blocks(struct lzh_stream *, int);
1975 static int      lzh_decode_blocks(struct lzh_stream *, int);
1976 #define ST_RD_BLOCK             0
1977 #define ST_RD_PT_1              1
1978 #define ST_RD_PT_2              2
1979 #define ST_RD_PT_3              3
1980 #define ST_RD_PT_4              4
1981 #define ST_RD_LITERAL_1         5
1982 #define ST_RD_LITERAL_2         6
1983 #define ST_RD_LITERAL_3         7
1984 #define ST_RD_POS_DATA_1        8
1985 #define ST_GET_LITERAL          9
1986 #define ST_GET_POS_1            10
1987 #define ST_GET_POS_2            11
1988 #define ST_COPY_DATA            12
1989
1990 static int
1991 lzh_decode(struct lzh_stream *strm, int last)
1992 {
1993         struct lzh_dec *ds = strm->ds;
1994         int64_t avail_in;
1995         int r;
1996
1997         if (ds->error)
1998                 return (ds->error);
1999
2000         avail_in = strm->avail_in;
2001         do {
2002                 if (ds->state < ST_GET_LITERAL)
2003                         r = lzh_read_blocks(strm, last);
2004                 else
2005                         r = lzh_decode_blocks(strm, last);
2006         } while (r == 100);
2007         strm->total_in += avail_in - strm->avail_in;
2008         return (r);
2009 }
2010
2011 static int
2012 lzh_copy_from_window(struct lzh_stream *strm, struct lzh_dec *ds)
2013 {
2014         size_t copy_bytes;
2015
2016         if (ds->w_remaining == 0 && ds->w_pos > 0) {
2017                 if (ds->w_pos - ds->copy_pos <= strm->avail_out)
2018                         copy_bytes = ds->w_pos - ds->copy_pos;
2019                 else
2020                         copy_bytes = (size_t)strm->avail_out;
2021                 memcpy(strm->next_out,
2022                     ds->w_buff + ds->copy_pos, copy_bytes);
2023                 ds->copy_pos += (int)copy_bytes;
2024         } else {
2025                 if (ds->w_remaining <= strm->avail_out)
2026                         copy_bytes = ds->w_remaining;
2027                 else
2028                         copy_bytes = (size_t)strm->avail_out;
2029                 memcpy(strm->next_out,
2030                     ds->w_buff + ds->w_size - ds->w_remaining, copy_bytes);
2031                 ds->w_remaining -= (int)copy_bytes;
2032         }
2033         strm->next_out += copy_bytes;
2034         strm->avail_out -= copy_bytes;
2035         strm->total_out += copy_bytes;
2036         if (strm->avail_out == 0)
2037                 return (0);
2038         else
2039                 return (1);
2040 }
2041
2042 static int
2043 lzh_read_blocks(struct lzh_stream *strm, int last)
2044 {
2045         struct lzh_dec *ds = strm->ds;
2046         struct lzh_br *br = &(ds->br);
2047         int c = 0, i;
2048         unsigned rbits;
2049
2050         for (;;) {
2051                 switch (ds->state) {
2052                 case ST_RD_BLOCK:
2053                         /*
2054                          * Read a block number indicates how many blocks
2055                          * we will handle. The block is composed of a
2056                          * literal and a match, sometimes a literal only
2057                          * in particular, there are no reference data at
2058                          * the beginning of the decompression.
2059                          */
2060                         if (!lzh_br_read_ahead_0(strm, br, 16)) {
2061                                 if (!last)
2062                                         /* We need following data. */
2063                                         return (ARCHIVE_OK);
2064                                 if (lzh_br_has(br, 8)) {
2065                                         /*
2066                                          * It seems there are extra bits.
2067                                          *  1. Compressed data is broken.
2068                                          *  2. `last' flag does not properly
2069                                          *     set.
2070                                          */
2071                                         goto failed;
2072                                 }
2073                                 if (ds->w_pos > 0) {
2074                                         if (!lzh_copy_from_window(strm, ds))
2075                                                 return (ARCHIVE_OK);
2076                                 }
2077                                 /* End of compressed data; we have completely
2078                                  * handled all compressed data. */
2079                                 return (ARCHIVE_EOF);
2080                         }
2081                         ds->blocks_avail = lzh_br_bits(br, 16);
2082                         if (ds->blocks_avail == 0)
2083                                 goto failed;
2084                         lzh_br_consume(br, 16);
2085                         /*
2086                          * Read a literal table compressed in huffman
2087                          * coding.
2088                          */
2089                         ds->pt.len_size = ds->literal_pt_len_size;
2090                         ds->pt.len_bits = ds->literal_pt_len_bits;
2091                         ds->reading_position = 0;
2092                         /* FALL THROUGH */
2093                 case ST_RD_PT_1:
2094                         /* Note: ST_RD_PT_1, ST_RD_PT_2 and ST_RD_PT_4 are
2095                          * used in reading both a literal table and a
2096                          * position table. */
2097                         if (!lzh_br_read_ahead(strm, br, ds->pt.len_bits)) {
2098                                 if (last)
2099                                         goto failed;/* Truncated data. */
2100                                 ds->state = ST_RD_PT_1;
2101                                 return (ARCHIVE_OK);
2102                         }
2103                         ds->pt.len_avail = lzh_br_bits(br, ds->pt.len_bits);
2104                         lzh_br_consume(br, ds->pt.len_bits);
2105                         /* FALL THROUGH */
2106                 case ST_RD_PT_2:
2107                         if (ds->pt.len_avail == 0) {
2108                                 /* There is no bitlen. */
2109                                 if (!lzh_br_read_ahead(strm, br,
2110                                     ds->pt.len_bits)) {
2111                                         if (last)
2112                                                 goto failed;/* Truncated data.*/
2113                                         ds->state = ST_RD_PT_2;
2114                                         return (ARCHIVE_OK);
2115                                 }
2116                                 if (!lzh_make_fake_table(&(ds->pt),
2117                                     lzh_br_bits(br, ds->pt.len_bits)))
2118                                         goto failed;/* Invalid data. */
2119                                 lzh_br_consume(br, ds->pt.len_bits);
2120                                 if (ds->reading_position)
2121                                         ds->state = ST_GET_LITERAL;
2122                                 else
2123                                         ds->state = ST_RD_LITERAL_1;
2124                                 break;
2125                         } else if (ds->pt.len_avail > ds->pt.len_size)
2126                                 goto failed;/* Invalid data. */
2127                         ds->loop = 0;
2128                         memset(ds->pt.freq, 0, sizeof(ds->pt.freq));
2129                         if (ds->pt.len_avail < 3 ||
2130                             ds->pt.len_size == ds->pos_pt_len_size) {
2131                                 ds->state = ST_RD_PT_4;
2132                                 break;
2133                         }
2134                         /* FALL THROUGH */
2135                 case ST_RD_PT_3:
2136                         ds->loop = lzh_read_pt_bitlen(strm, ds->loop, 3);
2137                         if (ds->loop < 3) {
2138                                 if (ds->loop < 0 || last)
2139                                         goto failed;/* Invalid data. */
2140                                 /* Not completed, get following data. */
2141                                 ds->state = ST_RD_PT_3;
2142                                 return (ARCHIVE_OK);
2143                         }
2144                         /* There are some null in bitlen of the literal. */
2145                         if (!lzh_br_read_ahead(strm, br, 2)) {
2146                                 if (last)
2147                                         goto failed;/* Truncated data. */
2148                                 ds->state = ST_RD_PT_3;
2149                                 return (ARCHIVE_OK);
2150                         }
2151                         c = lzh_br_bits(br, 2);
2152                         lzh_br_consume(br, 2);
2153                         if (c > ds->pt.len_avail - 3)
2154                                 goto failed;/* Invalid data. */
2155                         for (i = 3; c-- > 0 ;)
2156                                 ds->pt.bitlen[i++] = 0;
2157                         ds->loop = i;
2158                         /* FALL THROUGH */
2159                 case ST_RD_PT_4:
2160                         ds->loop = lzh_read_pt_bitlen(strm, ds->loop,
2161                             ds->pt.len_avail);
2162                         if (ds->loop < ds->pt.len_avail) {
2163                                 if (ds->loop < 0 || last)
2164                                         goto failed;/* Invalid data. */
2165                                 /* Not completed, get following data. */
2166                                 ds->state = ST_RD_PT_4;
2167                                 return (ARCHIVE_OK);
2168                         }
2169                         if (!lzh_make_huffman_table(&(ds->pt)))
2170                                 goto failed;/* Invalid data */
2171                         if (ds->reading_position) {
2172                                 ds->state = ST_GET_LITERAL;
2173                                 break;
2174                         }
2175                         /* FALL THROUGH */
2176                 case ST_RD_LITERAL_1:
2177                         if (!lzh_br_read_ahead(strm, br, ds->lt.len_bits)) {
2178                                 if (last)
2179                                         goto failed;/* Truncated data. */
2180                                 ds->state = ST_RD_LITERAL_1;
2181                                 return (ARCHIVE_OK);
2182                         }
2183                         ds->lt.len_avail = lzh_br_bits(br, ds->lt.len_bits);
2184                         lzh_br_consume(br, ds->lt.len_bits);
2185                         /* FALL THROUGH */
2186                 case ST_RD_LITERAL_2:
2187                         if (ds->lt.len_avail == 0) {
2188                                 /* There is no bitlen. */
2189                                 if (!lzh_br_read_ahead(strm, br,
2190                                     ds->lt.len_bits)) {
2191                                         if (last)
2192                                                 goto failed;/* Truncated data.*/
2193                                         ds->state = ST_RD_LITERAL_2;
2194                                         return (ARCHIVE_OK);
2195                                 }
2196                                 if (!lzh_make_fake_table(&(ds->lt),
2197                                     lzh_br_bits(br, ds->lt.len_bits)))
2198                                         goto failed;/* Invalid data */
2199                                 lzh_br_consume(br, ds->lt.len_bits);
2200                                 ds->state = ST_RD_POS_DATA_1;
2201                                 break;
2202                         } else if (ds->lt.len_avail > ds->lt.len_size)
2203                                 goto failed;/* Invalid data */
2204                         ds->loop = 0;
2205                         memset(ds->lt.freq, 0, sizeof(ds->lt.freq));
2206                         /* FALL THROUGH */
2207                 case ST_RD_LITERAL_3:
2208                         i = ds->loop;
2209                         while (i < ds->lt.len_avail) {
2210                                 if (!lzh_br_read_ahead(strm, br,
2211                                     ds->pt.max_bits)) {
2212                                         if (last)
2213                                                 goto failed;/* Truncated data.*/
2214                                         ds->loop = i;
2215                                         ds->state = ST_RD_LITERAL_3;
2216                                         return (ARCHIVE_OK);
2217                                 }
2218                                 rbits = lzh_br_bits(br, ds->pt.max_bits);
2219                                 c = lzh_decode_huffman(&(ds->pt), rbits);
2220                                 if (c > 2) {
2221                                         /* Note: 'c' will never be more than
2222                                          * eighteen since it's limited by
2223                                          * PT_BITLEN_SIZE, which is being set
2224                                          * to ds->pt.len_size through
2225                                          * ds->literal_pt_len_size. */
2226                                         lzh_br_consume(br, ds->pt.bitlen[c]);
2227                                         c -= 2;
2228                                         ds->lt.freq[c]++;
2229                                         ds->lt.bitlen[i++] = c;
2230                                 } else if (c == 0) {
2231                                         lzh_br_consume(br, ds->pt.bitlen[c]);
2232                                         ds->lt.bitlen[i++] = 0;
2233                                 } else {
2234                                         /* c == 1 or c == 2 */
2235                                         int n = (c == 1)?4:9;
2236                                         if (!lzh_br_read_ahead(strm, br,
2237                                              ds->pt.bitlen[c] + n)) {
2238                                                 if (last) /* Truncated data. */
2239                                                         goto failed;
2240                                                 ds->loop = i;
2241                                                 ds->state = ST_RD_LITERAL_3;
2242                                                 return (ARCHIVE_OK);
2243                                         }
2244                                         lzh_br_consume(br, ds->pt.bitlen[c]);
2245                                         c = lzh_br_bits(br, n);
2246                                         lzh_br_consume(br, n);
2247                                         c += (n == 4)?3:20;
2248                                         if (i + c > ds->lt.len_avail)
2249                                                 goto failed;/* Invalid data */
2250                                         memset(&(ds->lt.bitlen[i]), 0, c);
2251                                         i += c;
2252                                 }
2253                         }
2254                         if (i > ds->lt.len_avail ||
2255                             !lzh_make_huffman_table(&(ds->lt)))
2256                                 goto failed;/* Invalid data */
2257                         /* FALL THROUGH */
2258                 case ST_RD_POS_DATA_1:
2259                         /*
2260                          * Read a position table compressed in huffman
2261                          * coding.
2262                          */
2263                         ds->pt.len_size = ds->pos_pt_len_size;
2264                         ds->pt.len_bits = ds->pos_pt_len_bits;
2265                         ds->reading_position = 1;
2266                         ds->state = ST_RD_PT_1;
2267                         break;
2268                 case ST_GET_LITERAL:
2269                         return (100);
2270                 }
2271         }
2272 failed:
2273         return (ds->error = ARCHIVE_FAILED);
2274 }
2275
2276 static int
2277 lzh_decode_blocks(struct lzh_stream *strm, int last)
2278 {
2279         struct lzh_dec *ds = strm->ds;
2280         struct lzh_br bre = ds->br;
2281         struct huffman *lt = &(ds->lt);
2282         struct huffman *pt = &(ds->pt);
2283         unsigned char *w_buff = ds->w_buff;
2284         unsigned char *lt_bitlen = lt->bitlen;
2285         unsigned char *pt_bitlen = pt->bitlen;
2286         int blocks_avail = ds->blocks_avail, c = 0;
2287         int copy_len = ds->copy_len, copy_pos = ds->copy_pos;
2288         int w_pos = ds->w_pos, w_mask = ds->w_mask, w_size = ds->w_size;
2289         int lt_max_bits = lt->max_bits, pt_max_bits = pt->max_bits;
2290         int state = ds->state;
2291
2292         if (ds->w_remaining > 0) {
2293                 if (!lzh_copy_from_window(strm, ds))
2294                         goto next_data;
2295         }
2296         for (;;) {
2297                 switch (state) {
2298                 case ST_GET_LITERAL:
2299                         for (;;) {
2300                                 if (blocks_avail == 0) {
2301                                         /* We have decoded all blocks.
2302                                          * Let's handle next blocks. */
2303                                         ds->state = ST_RD_BLOCK;
2304                                         ds->br = bre;
2305                                         ds->blocks_avail = 0;
2306                                         ds->w_pos = w_pos;
2307                                         ds->copy_pos = 0;
2308                                         return (100);
2309                                 }
2310
2311                                 /* lzh_br_read_ahead() always try to fill the
2312                                  * cache buffer up. In specific situation we
2313                                  * are close to the end of the data, the cache
2314                                  * buffer will not be full and thus we have to
2315                                  * determine if the cache buffer has some bits
2316                                  * as much as we need after lzh_br_read_ahead()
2317                                  * failed. */
2318                                 if (!lzh_br_read_ahead(strm, &bre,
2319                                     lt_max_bits)) {
2320                                         if (!last)
2321                                                 goto next_data;
2322                                         /* Remaining bits are less than
2323                                          * maximum bits(lt.max_bits) but maybe
2324                                          * it still remains as much as we need,
2325                                          * so we should try to use it with
2326                                          * dummy bits. */
2327                                         c = lzh_decode_huffman(lt,
2328                                               lzh_br_bits_forced(&bre,
2329                                                 lt_max_bits));
2330                                         lzh_br_consume(&bre, lt_bitlen[c]);
2331                                         if (!lzh_br_has(&bre, 0))
2332                                                 goto failed;/* Over read. */
2333                                 } else {
2334                                         c = lzh_decode_huffman(lt,
2335                                               lzh_br_bits(&bre, lt_max_bits));
2336                                         lzh_br_consume(&bre, lt_bitlen[c]);
2337                                 }
2338                                 blocks_avail--;
2339                                 if (c > UCHAR_MAX)
2340                                         /* Current block is a match data. */
2341                                         break;
2342                                 /*
2343                                  * 'c' is exactly a literal code.
2344                                  */
2345                                 /* Save a decoded code to reference it
2346                                  * afterward. */
2347                                 w_buff[w_pos] = c;
2348                                 if (++w_pos >= w_size) {
2349                                         w_pos = 0;
2350                                         ds->w_remaining = w_size;
2351                                         if (!lzh_copy_from_window(strm, ds))
2352                                                 goto next_data;
2353                                 }
2354                         }
2355                         /* 'c' is the length of a match pattern we have
2356                          * already extracted, which has be stored in
2357                          * window(ds->w_buff). */
2358                         copy_len = c - (UCHAR_MAX + 1) + MINMATCH;
2359                         /* FALL THROUGH */
2360                 case ST_GET_POS_1:
2361                         /*
2362                          * Get a reference position.
2363                          */
2364                         if (!lzh_br_read_ahead(strm, &bre, pt_max_bits)) {
2365                                 if (!last) {
2366                                         state = ST_GET_POS_1;
2367                                         ds->copy_len = copy_len;
2368                                         goto next_data;
2369                                 }
2370                                 copy_pos = lzh_decode_huffman(pt,
2371                                     lzh_br_bits_forced(&bre, pt_max_bits));
2372                                 lzh_br_consume(&bre, pt_bitlen[copy_pos]);
2373                                 if (!lzh_br_has(&bre, 0))
2374                                         goto failed;/* Over read. */
2375                         } else {
2376                                 copy_pos = lzh_decode_huffman(pt,
2377                                     lzh_br_bits(&bre, pt_max_bits));
2378                                 lzh_br_consume(&bre, pt_bitlen[copy_pos]);
2379                         }
2380                         /* FALL THROUGH */
2381                 case ST_GET_POS_2:
2382                         if (copy_pos > 1) {
2383                                 /* We need an additional adjustment number to
2384                                  * the position. */
2385                                 int p = copy_pos - 1;
2386                                 if (!lzh_br_read_ahead(strm, &bre, p)) {
2387                                         if (last)
2388                                                 goto failed;/* Truncated data.*/
2389                                         state = ST_GET_POS_2;
2390                                         ds->copy_len = copy_len;
2391                                         ds->copy_pos = copy_pos;
2392                                         goto next_data;
2393                                 }
2394                                 copy_pos = (1 << p) + lzh_br_bits(&bre, p);
2395                                 lzh_br_consume(&bre, p);
2396                         }
2397                         /* The position is actually a distance from the last
2398                          * code we had extracted and thus we have to convert
2399                          * it to a position of the window. */
2400                         copy_pos = (w_pos - copy_pos - 1) & w_mask;
2401                         /* FALL THROUGH */
2402                 case ST_COPY_DATA:
2403                         /*
2404                          * Copy `copy_len' bytes as extracted data from
2405                          * the window into the output buffer.
2406                          */
2407                         for (;;) {
2408                                 int l;
2409
2410                                 l = copy_len;
2411                                 if (copy_pos > w_pos) {
2412                                         if (l > w_size - copy_pos)
2413                                                 l = w_size - copy_pos;
2414                                 } else {
2415                                         if (l > w_size - w_pos)
2416                                                 l = w_size - w_pos;
2417                                 }
2418                                 if ((copy_pos + l < w_pos)
2419                                     || (w_pos + l < copy_pos)) {
2420                                         /* No overlap. */
2421                                         memcpy(w_buff + w_pos,
2422                                             w_buff + copy_pos, l);
2423                                 } else {
2424                                         const unsigned char *s;
2425                                         unsigned char *d;
2426                                         int li;
2427
2428                                         d = w_buff + w_pos;
2429                                         s = w_buff + copy_pos;
2430                                         for (li = 0; li < l; li++)
2431                                                 d[li] = s[li];
2432                                 }
2433                                 w_pos = (w_pos + l) & w_mask;
2434                                 if (w_pos == 0) {
2435                                         ds->w_remaining = w_size;
2436                                         if (!lzh_copy_from_window(strm, ds)) {
2437                                                 if (copy_len <= l)
2438                                                         state = ST_GET_LITERAL;
2439                                                 else {
2440                                                         state = ST_COPY_DATA;
2441                                                         ds->copy_len =
2442                                                             copy_len - l;
2443                                                         ds->copy_pos =
2444                                                             (copy_pos + l)
2445                                                             & w_mask;
2446                                                 }
2447                                                 goto next_data;
2448                                         }
2449                                 }
2450                                 if (copy_len <= l)
2451                                         /* A copy of current pattern ended. */
2452                                         break;
2453                                 copy_len -= l;
2454                                 copy_pos = (copy_pos + l) & w_mask;
2455                         }
2456                         state = ST_GET_LITERAL;
2457                         break;
2458                 }
2459         }
2460 failed:
2461         return (ds->error = ARCHIVE_FAILED);
2462 next_data:
2463         ds->br = bre;
2464         ds->blocks_avail = blocks_avail;
2465         ds->state = state;
2466         ds->w_pos = w_pos;
2467         return (ARCHIVE_OK);
2468 }
2469
2470 static int
2471 lzh_huffman_init(struct huffman *hf, size_t len_size, int tbl_bits)
2472 {
2473         int bits;
2474
2475         if (hf->bitlen == NULL) {
2476                 hf->bitlen = malloc(len_size * sizeof(hf->bitlen[0]));
2477                 if (hf->bitlen == NULL)
2478                         return (ARCHIVE_FATAL);
2479         }
2480         if (hf->tbl == NULL) {
2481                 if (tbl_bits < HTBL_BITS)
2482                         bits = tbl_bits;
2483                 else
2484                         bits = HTBL_BITS;
2485                 hf->tbl = malloc(((size_t)1 << bits) * sizeof(hf->tbl[0]));
2486                 if (hf->tbl == NULL)
2487                         return (ARCHIVE_FATAL);
2488         }
2489         if (hf->tree == NULL && tbl_bits > HTBL_BITS) {
2490                 hf->tree_avail = 1 << (tbl_bits - HTBL_BITS + 4);
2491                 hf->tree = malloc(hf->tree_avail * sizeof(hf->tree[0]));
2492                 if (hf->tree == NULL)
2493                         return (ARCHIVE_FATAL);
2494         }
2495         hf->len_size = (int)len_size;
2496         hf->tbl_bits = tbl_bits;
2497         return (ARCHIVE_OK);
2498 }
2499
2500 static void
2501 lzh_huffman_free(struct huffman *hf)
2502 {
2503         free(hf->bitlen);
2504         free(hf->tbl);
2505         free(hf->tree);
2506 }
2507
2508 static int
2509 lzh_read_pt_bitlen(struct lzh_stream *strm, int start, int end)
2510 {
2511         struct lzh_dec *ds = strm->ds;
2512         struct lzh_br * br = &(ds->br);
2513         int c, i;
2514
2515         for (i = start; i < end;) {
2516                 /*
2517                  *  bit pattern     the number we need
2518                  *     000           ->  0
2519                  *     001           ->  1
2520                  *     010           ->  2
2521                  *     ...
2522                  *     110           ->  6
2523                  *     1110          ->  7
2524                  *     11110         ->  8
2525                  *     ...
2526                  *     1111111111110 ->  16
2527                  */
2528                 if (!lzh_br_read_ahead(strm, br, 3))
2529                         return (i);
2530                 if ((c = lzh_br_bits(br, 3)) == 7) {
2531                         int d;
2532                         if (!lzh_br_read_ahead(strm, br, 13))
2533                                 return (i);
2534                         d = lzh_br_bits(br, 13);
2535                         while (d & 0x200) {
2536                                 c++;
2537                                 d <<= 1;
2538                         }
2539                         if (c > 16)
2540                                 return (-1);/* Invalid data. */
2541                         lzh_br_consume(br, c - 3);
2542                 } else
2543                         lzh_br_consume(br, 3);
2544                 ds->pt.bitlen[i++] = c;
2545                 ds->pt.freq[c]++;
2546         }
2547         return (i);
2548 }
2549
2550 static int
2551 lzh_make_fake_table(struct huffman *hf, uint16_t c)
2552 {
2553         if (c >= hf->len_size)
2554                 return (0);
2555         hf->tbl[0] = c;
2556         hf->max_bits = 0;
2557         hf->shift_bits = 0;
2558         hf->bitlen[hf->tbl[0]] = 0;
2559         return (1);
2560 }
2561
2562 /*
2563  * Make a huffman coding table.
2564  */
2565 static int
2566 lzh_make_huffman_table(struct huffman *hf)
2567 {
2568         uint16_t *tbl;
2569         const unsigned char *bitlen;
2570         int bitptn[17], weight[17];
2571         int i, maxbits = 0, ptn, tbl_size, w;
2572         int diffbits, len_avail;
2573
2574         /*
2575          * Initialize bit patterns.
2576          */
2577         ptn = 0;
2578         for (i = 1, w = 1 << 15; i <= 16; i++, w >>= 1) {
2579                 bitptn[i] = ptn;
2580                 weight[i] = w;
2581                 if (hf->freq[i]) {
2582                         ptn += hf->freq[i] * w;
2583                         maxbits = i;
2584                 }
2585         }
2586         if (ptn != 0x10000 || maxbits > hf->tbl_bits)
2587                 return (0);/* Invalid */
2588
2589         hf->max_bits = maxbits;
2590
2591         /*
2592          * Cut out extra bits which we won't house in the table.
2593          * This preparation reduces the same calculation in the for-loop
2594          * making the table.
2595          */
2596         if (maxbits < 16) {
2597                 int ebits = 16 - maxbits;
2598                 for (i = 1; i <= maxbits; i++) {
2599                         bitptn[i] >>= ebits;
2600                         weight[i] >>= ebits;
2601                 }
2602         }
2603         if (maxbits > HTBL_BITS) {
2604                 int htbl_max;
2605                 uint16_t *p;
2606
2607                 diffbits = maxbits - HTBL_BITS;
2608                 for (i = 1; i <= HTBL_BITS; i++) {
2609                         bitptn[i] >>= diffbits;
2610                         weight[i] >>= diffbits;
2611                 }
2612                 htbl_max = bitptn[HTBL_BITS] +
2613                     weight[HTBL_BITS] * hf->freq[HTBL_BITS];
2614                 p = &(hf->tbl[htbl_max]);
2615                 while (p < &hf->tbl[1U<<HTBL_BITS])
2616                         *p++ = 0;
2617         } else
2618                 diffbits = 0;
2619         hf->shift_bits = diffbits;
2620
2621         /*
2622          * Make the table.
2623          */
2624         tbl_size = 1 << HTBL_BITS;
2625         tbl = hf->tbl;
2626         bitlen = hf->bitlen;
2627         len_avail = hf->len_avail;
2628         hf->tree_used = 0;
2629         for (i = 0; i < len_avail; i++) {
2630                 uint16_t *p;
2631                 int len, cnt;
2632                 uint16_t bit;
2633                 int extlen;
2634                 struct htree_t *ht;
2635
2636                 if (bitlen[i] == 0)
2637                         continue;
2638                 /* Get a bit pattern */
2639                 len = bitlen[i];
2640                 ptn = bitptn[len];
2641                 cnt = weight[len];
2642                 if (len <= HTBL_BITS) {
2643                         /* Calculate next bit pattern */
2644                         if ((bitptn[len] = ptn + cnt) > tbl_size)
2645                                 return (0);/* Invalid */
2646                         /* Update the table */
2647                         p = &(tbl[ptn]);
2648                         while (--cnt >= 0)
2649                                 p[cnt] = (uint16_t)i;
2650                         continue;
2651                 }
2652
2653                 /*
2654                  * A bit length is too big to be housed to a direct table,
2655                  * so we use a tree model for its extra bits.
2656                  */
2657                 bitptn[len] = ptn + cnt;
2658                 bit = 1U << (diffbits -1);
2659                 extlen = len - HTBL_BITS;
2660
2661                 p = &(tbl[ptn >> diffbits]);
2662                 if (*p == 0) {
2663                         *p = len_avail + hf->tree_used;
2664                         ht = &(hf->tree[hf->tree_used++]);
2665                         if (hf->tree_used > hf->tree_avail)
2666                                 return (0);/* Invalid */
2667                         ht->left = 0;
2668                         ht->right = 0;
2669                 } else {
2670                         if (*p < len_avail ||
2671                             *p >= (len_avail + hf->tree_used))
2672                                 return (0);/* Invalid */
2673                         ht = &(hf->tree[*p - len_avail]);
2674                 }
2675                 while (--extlen > 0) {
2676                         if (ptn & bit) {
2677                                 if (ht->left < len_avail) {
2678                                         ht->left = len_avail + hf->tree_used;
2679                                         ht = &(hf->tree[hf->tree_used++]);
2680                                         if (hf->tree_used > hf->tree_avail)
2681                                                 return (0);/* Invalid */
2682                                         ht->left = 0;
2683                                         ht->right = 0;
2684                                 } else {
2685                                         ht = &(hf->tree[ht->left - len_avail]);
2686                                 }
2687                         } else {
2688                                 if (ht->right < len_avail) {
2689                                         ht->right = len_avail + hf->tree_used;
2690                                         ht = &(hf->tree[hf->tree_used++]);
2691                                         if (hf->tree_used > hf->tree_avail)
2692                                                 return (0);/* Invalid */
2693                                         ht->left = 0;
2694                                         ht->right = 0;
2695                                 } else {
2696                                         ht = &(hf->tree[ht->right - len_avail]);
2697                                 }
2698                         }
2699                         bit >>= 1;
2700                 }
2701                 if (ptn & bit) {
2702                         if (ht->left != 0)
2703                                 return (0);/* Invalid */
2704                         ht->left = (uint16_t)i;
2705                 } else {
2706                         if (ht->right != 0)
2707                                 return (0);/* Invalid */
2708                         ht->right = (uint16_t)i;
2709                 }
2710         }
2711         return (1);
2712 }
2713
2714 static int
2715 lzh_decode_huffman_tree(struct huffman *hf, unsigned rbits, int c)
2716 {
2717         struct htree_t *ht;
2718         int extlen;
2719
2720         ht = hf->tree;
2721         extlen = hf->shift_bits;
2722         while (c >= hf->len_avail) {
2723                 c -= hf->len_avail;
2724                 if (extlen-- <= 0 || c >= hf->tree_used)
2725                         return (0);
2726                 if (rbits & (1U << extlen))
2727                         c = ht[c].left;
2728                 else
2729                         c = ht[c].right;
2730         }
2731         return (c);
2732 }
2733
2734 static inline int
2735 lzh_decode_huffman(struct huffman *hf, unsigned rbits)
2736 {
2737         int c;
2738         /*
2739          * At first search an index table for a bit pattern.
2740          * If it fails, search a huffman tree for.
2741          */
2742         c = hf->tbl[rbits >> hf->shift_bits];
2743         if (c < hf->len_avail)
2744                 return (c);
2745         /* This bit pattern needs to be found out at a huffman tree. */
2746         return (lzh_decode_huffman_tree(hf, rbits, c));
2747 }
2748