1 /*-
2 * Copyright (c) 2008-2014 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_time_private.h"
47 #include "archive_endian.h"
48
49
50 #define MAXMATCH 256 /* Maximum match length. */
51 #define MINMATCH 3 /* Minimum match length. */
52 /*
53 * Literal table format:
54 * +0 +256 +510
55 * +---------------+-------------------------+
56 * | literal code | match length |
57 * | 0 ... 255 | MINMATCH ... MAXMATCH |
58 * +---------------+-------------------------+
59 * <--- LT_BITLEN_SIZE --->
60 */
61 /* Literal table size. */
62 #define LT_BITLEN_SIZE (UCHAR_MAX + 1 + MAXMATCH - MINMATCH + 1)
63 /* Position table size.
64 * Note: this used for both position table and pre literal table.*/
65 #define PT_BITLEN_SIZE (3 + 16)
66
67 struct lzh_dec {
68 /* Decoding status. */
69 int state;
70
71 /*
72 * Window to see last 8Ki(lh5),32Ki(lh6),64Ki(lh7) bytes of decoded
73 * data.
74 */
75 int w_size;
76 int w_mask;
77 /* Window buffer, which is a loop buffer. */
78 unsigned char *w_buff;
79 /* The insert position to the window. */
80 int w_pos;
81 /* The position where we can copy decoded code from the window. */
82 int copy_pos;
83 /* The length how many bytes we can copy decoded code from
84 * the window. */
85 int copy_len;
86
87 /*
88 * Bit stream reader.
89 */
90 struct lzh_br {
91 #define CACHE_TYPE uint64_t
92 #define CACHE_BITS (8 * sizeof(CACHE_TYPE))
93 /* Cache buffer. */
94 CACHE_TYPE cache_buffer;
95 /* Indicates how many bits avail in cache_buffer. */
96 int cache_avail;
97 } br;
98
99 /*
100 * Huffman coding.
101 */
102 struct huffman {
103 int len_size;
104 int len_avail;
105 int len_bits;
106 int freq[17];
107 unsigned char *bitlen;
108
109 /*
110 * Use an index table. It's faster than searching a huffman
111 * coding tree, which is a binary tree. But usage of a large
112 * index table causes L1 cache read miss many times.
113 */
114 #define HTBL_BITS 10
115 int max_bits;
116 int shift_bits;
117 int tbl_bits;
118 int tree_used;
119 int tree_avail;
120 /* Direct access table. */
121 uint16_t *tbl;
122 /* Binary tree table for extra bits over the direct access. */
123 struct htree_t {
124 uint16_t left;
125 uint16_t right;
126 } *tree;
127 } lt, pt;
128
129 int blocks_avail;
130 int pos_pt_len_size;
131 int pos_pt_len_bits;
132 int literal_pt_len_size;
133 int literal_pt_len_bits;
134 int reading_position;
135 int loop;
136 int error;
137 };
138
139 struct lzh_stream {
140 const unsigned char *next_in;
141 int avail_in;
142 int64_t total_in;
143 const unsigned char *ref_ptr;
144 int avail_out;
145 struct lzh_dec *ds;
146 };
147
148 struct lha {
149 /* entry_bytes_remaining is the number of bytes we expect. */
150 int64_t entry_offset;
151 int64_t entry_bytes_remaining;
152 int64_t entry_unconsumed;
153 uint16_t entry_crc_calculated;
154
155 size_t header_size; /* header size */
156 unsigned char level; /* header level */
157 char method[3]; /* compress type */
158 int64_t compsize; /* compressed data size */
159 int64_t origsize; /* original file size */
160 int setflag;
161 #define BIRTHTIME_IS_SET 1
162 #define ATIME_IS_SET 2
163 #define UNIX_MODE_IS_SET 4
164 #define CRC_IS_SET 8
165 int64_t birthtime;
166 uint32_t birthtime_tv_nsec;
167 int64_t mtime;
168 uint32_t mtime_tv_nsec;
169 int64_t atime;
170 uint32_t atime_tv_nsec;
171 mode_t mode;
172 int64_t uid;
173 int64_t gid;
174 struct archive_string uname;
175 struct archive_string gname;
176 uint16_t header_crc;
177 uint16_t crc;
178 /* dirname and filename could be in different codepages */
179 struct archive_string_conv *sconv_dir;
180 struct archive_string_conv *sconv_fname;
181 struct archive_string_conv *opt_sconv;
182
183 struct archive_string dirname;
184 struct archive_string filename;
185 struct archive_wstring ws;
186
187 unsigned char dos_attr;
188
189 /* Flag to mark progress that an archive was read their first header.*/
190 char found_first_header;
191 /* Flag to mark that indicates an empty directory. */
192 char directory;
193
194 /* Flags to mark progress of decompression. */
195 char decompress_init;
196 char end_of_entry;
197 char end_of_entry_cleanup;
198 char entry_is_compressed;
199
200 char format_name[64];
201
202 struct lzh_stream strm;
203 };
204
205 /*
206 * LHA header common member offset.
207 */
208 #define H_METHOD_OFFSET 2 /* Compress type. */
209 #define H_ATTR_OFFSET 19 /* DOS attribute. */
210 #define H_LEVEL_OFFSET 20 /* Header Level. */
211 #define H_SIZE 22 /* Minimum header size. */
212
213 static int archive_read_format_lha_bid(struct archive_read *, int);
214 static int archive_read_format_lha_options(struct archive_read *,
215 const char *, const char *);
216 static int archive_read_format_lha_read_header(struct archive_read *,
217 struct archive_entry *);
218 static int archive_read_format_lha_read_data(struct archive_read *,
219 const void **, size_t *, int64_t *);
220 static int archive_read_format_lha_read_data_skip(struct archive_read *);
221 static int archive_read_format_lha_cleanup(struct archive_read *);
222
223 static void lha_replace_path_separator(struct lha *,
224 struct archive_entry *);
225 static int lha_read_file_header_0(struct archive_read *, struct lha *);
226 static int lha_read_file_header_1(struct archive_read *, struct lha *);
227 static int lha_read_file_header_2(struct archive_read *, struct lha *);
228 static int lha_read_file_header_3(struct archive_read *, struct lha *);
229 static int lha_read_file_extended_header(struct archive_read *,
230 struct lha *, uint16_t *, int, uint64_t, size_t *);
231 static size_t lha_check_header_format(const void *);
232 static int lha_skip_sfx(struct archive_read *);
233 static unsigned char lha_calcsum(unsigned char, const void *,
234 int, size_t);
235 static int lha_parse_linkname(struct archive_wstring *,
236 struct archive_wstring *);
237 static int lha_read_data_none(struct archive_read *, const void **,
238 size_t *, int64_t *);
239 static int lha_read_data_lzh(struct archive_read *, const void **,
240 size_t *, int64_t *);
241 static uint16_t lha_crc16(uint16_t, const void *, size_t);
242 static int lzh_decode_init(struct lzh_stream *, const char *);
243 static void lzh_decode_free(struct lzh_stream *);
244 static int lzh_decode(struct lzh_stream *, int);
245 static int lzh_br_fillup(struct lzh_stream *, struct lzh_br *);
246 static int lzh_huffman_init(struct huffman *, size_t, int);
247 static void lzh_huffman_free(struct huffman *);
248 static int lzh_read_pt_bitlen(struct lzh_stream *, int start, int end);
249 static int lzh_make_fake_table(struct huffman *, uint16_t);
250 static int lzh_make_huffman_table(struct huffman *);
251 static inline int lzh_decode_huffman(struct huffman *, unsigned);
252 static int lzh_decode_huffman_tree(struct huffman *, unsigned, int);
253
254
255 int
archive_read_support_format_lha(struct archive * _a)256 archive_read_support_format_lha(struct archive *_a)
257 {
258 struct archive_read *a = (struct archive_read *)_a;
259 struct lha *lha;
260 int r;
261
262 archive_check_magic(_a, ARCHIVE_READ_MAGIC,
263 ARCHIVE_STATE_NEW, "archive_read_support_format_lha");
264
265 lha = calloc(1, sizeof(*lha));
266 if (lha == NULL) {
267 archive_set_error(&a->archive, ENOMEM,
268 "Can't allocate lha data");
269 return (ARCHIVE_FATAL);
270 }
271 archive_string_init(&lha->ws);
272
273 r = __archive_read_register_format(a,
274 lha,
275 "lha",
276 archive_read_format_lha_bid,
277 archive_read_format_lha_options,
278 archive_read_format_lha_read_header,
279 archive_read_format_lha_read_data,
280 archive_read_format_lha_read_data_skip,
281 NULL,
282 archive_read_format_lha_cleanup,
283 NULL,
284 NULL);
285
286 if (r != ARCHIVE_OK)
287 free(lha);
288 return (ARCHIVE_OK);
289 }
290
291 static size_t
lha_check_header_format(const void * h)292 lha_check_header_format(const void *h)
293 {
294 const unsigned char *p = h;
295 size_t next_skip_bytes;
296
297 switch (p[H_METHOD_OFFSET+3]) {
298 /*
299 * "-lh0-" ... "-lh7-" "-lhd-"
300 * "-lzs-" "-lz5-"
301 */
302 case '0': case '1': case '2': case '3':
303 case '4': case '5': case '6': case '7':
304 case 'd':
305 case 's':
306 next_skip_bytes = 4;
307
308 /* b0 == 0 means the end of an LHa archive file. */
309 if (p[0] == 0)
310 break;
311 if (p[H_METHOD_OFFSET] != '-' || p[H_METHOD_OFFSET+1] != 'l'
312 || p[H_METHOD_OFFSET+4] != '-')
313 break;
314
315 if (p[H_METHOD_OFFSET+2] == 'h') {
316 /* "-lh?-" */
317 if (p[H_METHOD_OFFSET+3] == 's')
318 break;
319 if (p[H_LEVEL_OFFSET] == 0)
320 return (0);
321 if (p[H_LEVEL_OFFSET] <= 3 && p[H_ATTR_OFFSET] == 0x20)
322 return (0);
323 }
324 if (p[H_METHOD_OFFSET+2] == 'z') {
325 /* LArc extensions: -lzs-,-lz4- and -lz5- */
326 if (p[H_LEVEL_OFFSET] != 0)
327 break;
328 if (p[H_METHOD_OFFSET+3] == 's'
329 || p[H_METHOD_OFFSET+3] == '4'
330 || p[H_METHOD_OFFSET+3] == '5')
331 return (0);
332 }
333 break;
334 case 'h': next_skip_bytes = 1; break;
335 case 'z': next_skip_bytes = 1; break;
336 case 'l': next_skip_bytes = 2; break;
337 case '-': next_skip_bytes = 3; break;
338 default : next_skip_bytes = 4; break;
339 }
340
341 return (next_skip_bytes);
342 }
343
344 static int
archive_read_format_lha_bid(struct archive_read * a,int best_bid)345 archive_read_format_lha_bid(struct archive_read *a, int best_bid)
346 {
347 const char *p;
348 const void *buff;
349 ssize_t bytes_avail, offset, window;
350 size_t next;
351
352 /* If there's already a better bid than we can ever
353 make, don't bother testing. */
354 if (best_bid > 30)
355 return (-1);
356
357 if ((p = __archive_read_ahead(a, H_SIZE, NULL)) == NULL)
358 return (-1);
359
360 if (lha_check_header_format(p) == 0)
361 return (30);
362
363 if (p[0] == 'M' && p[1] == 'Z') {
364 /* PE file */
365 offset = 0;
366 window = 4096;
367 while (offset < (1024 * 20)) {
368 buff = __archive_read_ahead(a, offset + window,
369 &bytes_avail);
370 if (buff == NULL) {
371 /* Remaining bytes are less than window. */
372 window >>= 1;
373 if (window < (H_SIZE + 3))
374 return (0);
375 continue;
376 }
377 p = (const char *)buff + offset;
378 while (p + H_SIZE < (const char *)buff + bytes_avail) {
379 if ((next = lha_check_header_format(p)) == 0)
380 return (30);
381 p += next;
382 }
383 offset = p - (const char *)buff;
384 }
385 }
386 return (0);
387 }
388
389 static int
archive_read_format_lha_options(struct archive_read * a,const char * key,const char * val)390 archive_read_format_lha_options(struct archive_read *a,
391 const char *key, const char *val)
392 {
393 struct lha *lha = a->format->data;
394 int ret = ARCHIVE_FAILED;
395
396 if (strcmp(key, "hdrcharset") == 0) {
397 if (val == NULL || val[0] == 0)
398 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
399 "lha: hdrcharset option needs a character-set name");
400 else {
401 lha->opt_sconv =
402 archive_string_conversion_from_charset(
403 &a->archive, val, 0);
404 if (lha->opt_sconv != NULL)
405 ret = ARCHIVE_OK;
406 else
407 ret = ARCHIVE_FATAL;
408 }
409 return (ret);
410 }
411
412 /* Note: The "warn" return is just to inform the options
413 * supervisor that we didn't handle it. It will generate
414 * a suitable error if no one used this option. */
415 return (ARCHIVE_WARN);
416 }
417
418 static int
lha_skip_sfx(struct archive_read * a)419 lha_skip_sfx(struct archive_read *a)
420 {
421 const void *h;
422 const char *p, *q;
423 size_t next, skip;
424 ssize_t bytes, window;
425
426 window = 4096;
427 for (;;) {
428 h = __archive_read_ahead(a, window, &bytes);
429 if (h == NULL) {
430 /* Remaining bytes are less than window. */
431 window >>= 1;
432 if (window < (H_SIZE + 3))
433 goto fatal;
434 continue;
435 }
436 if (bytes < H_SIZE)
437 goto fatal;
438 p = h;
439 q = p + bytes;
440
441 /*
442 * Scan ahead until we find something that looks
443 * like the lha header.
444 */
445 while (p + H_SIZE < q) {
446 if ((next = lha_check_header_format(p)) == 0) {
447 skip = p - (const char *)h;
448 __archive_read_consume(a, skip);
449 return (ARCHIVE_OK);
450 }
451 p += next;
452 }
453 skip = p - (const char *)h;
454 __archive_read_consume(a, skip);
455 }
456 fatal:
457 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
458 "Couldn't find out LHa header");
459 return (ARCHIVE_FATAL);
460 }
461
462 static int
truncated_error(struct archive_read * a)463 truncated_error(struct archive_read *a)
464 {
465 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
466 "Truncated LHa header");
467 return (ARCHIVE_FATAL);
468 }
469
470 static int
archive_read_format_lha_read_header(struct archive_read * a,struct archive_entry * entry)471 archive_read_format_lha_read_header(struct archive_read *a,
472 struct archive_entry *entry)
473 {
474 struct lha *lha = a->format->data;
475 struct archive_wstring linkname;
476 struct archive_wstring pathname;
477 const unsigned char *p;
478 const char *signature;
479 int err;
480 struct archive_mstring conv_buffer;
481 const wchar_t *conv_buffer_p;
482
483 a->archive.archive_format = ARCHIVE_FORMAT_LHA;
484 if (a->archive.archive_format_name == NULL)
485 a->archive.archive_format_name = "lha";
486
487 lha->decompress_init = 0;
488 lha->end_of_entry = 0;
489 lha->end_of_entry_cleanup = 0;
490 lha->entry_unconsumed = 0;
491
492 if ((p = __archive_read_ahead(a, H_SIZE, NULL)) == NULL) {
493 /*
494 * LHa archiver added 0 to the tail of its archive file as
495 * the mark of the end of the archive.
496 */
497 signature = __archive_read_ahead(a, sizeof(signature[0]), NULL);
498 if (signature == NULL || signature[0] == 0)
499 return (ARCHIVE_EOF);
500 return (truncated_error(a));
501 }
502
503 signature = (const char *)p;
504 if (lha->found_first_header == 0 &&
505 signature[0] == 'M' && signature[1] == 'Z') {
506 /* This is an executable? Must be self-extracting... */
507 err = lha_skip_sfx(a);
508 if (err < ARCHIVE_WARN)
509 return (err);
510
511 if ((p = __archive_read_ahead(a, sizeof(*p), NULL)) == NULL)
512 return (truncated_error(a));
513 signature = (const char *)p;
514 }
515 /* signature[0] == 0 means the end of an LHa archive file. */
516 if (signature[0] == 0)
517 return (ARCHIVE_EOF);
518
519 /*
520 * Check the header format and method type.
521 */
522 if (lha_check_header_format(p) != 0) {
523 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
524 "Bad LHa file");
525 return (ARCHIVE_FATAL);
526 }
527
528 /* We've found the first header. */
529 lha->found_first_header = 1;
530 /* Set a default value and common data */
531 lha->header_size = 0;
532 lha->level = p[H_LEVEL_OFFSET];
533 lha->method[0] = p[H_METHOD_OFFSET+1];
534 lha->method[1] = p[H_METHOD_OFFSET+2];
535 lha->method[2] = p[H_METHOD_OFFSET+3];
536 if (memcmp(lha->method, "lhd", 3) == 0)
537 lha->directory = 1;
538 else
539 lha->directory = 0;
540 if (memcmp(lha->method, "lh0", 3) == 0 ||
541 memcmp(lha->method, "lz4", 3) == 0)
542 lha->entry_is_compressed = 0;
543 else
544 lha->entry_is_compressed = 1;
545
546 lha->compsize = 0;
547 lha->origsize = 0;
548 lha->setflag = 0;
549 lha->birthtime = 0;
550 lha->birthtime_tv_nsec = 0;
551 lha->mtime = 0;
552 lha->mtime_tv_nsec = 0;
553 lha->atime = 0;
554 lha->atime_tv_nsec = 0;
555 lha->mode = (lha->directory)? 0777 : 0666;
556 lha->uid = 0;
557 lha->gid = 0;
558 archive_string_empty(&lha->dirname);
559 archive_string_empty(&lha->filename);
560 lha->dos_attr = 0;
561 if (lha->opt_sconv != NULL) {
562 lha->sconv_dir = lha->opt_sconv;
563 lha->sconv_fname = lha->opt_sconv;
564 } else {
565 lha->sconv_dir = NULL;
566 lha->sconv_fname = NULL;
567 }
568
569 switch (p[H_LEVEL_OFFSET]) {
570 case 0:
571 err = lha_read_file_header_0(a, lha);
572 break;
573 case 1:
574 err = lha_read_file_header_1(a, lha);
575 break;
576 case 2:
577 err = lha_read_file_header_2(a, lha);
578 break;
579 case 3:
580 err = lha_read_file_header_3(a, lha);
581 break;
582 default:
583 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
584 "Unsupported LHa header level %d", p[H_LEVEL_OFFSET]);
585 err = ARCHIVE_FATAL;
586 break;
587 }
588 if (err < ARCHIVE_WARN)
589 return (err);
590
591
592 if (!lha->directory && archive_strlen(&lha->filename) == 0)
593 /* The filename has not been set */
594 return (truncated_error(a));
595
596 /*
597 * Make a pathname from a dirname and a filename, after converting to Unicode.
598 * This is because codepages might differ between dirname and filename.
599 */
600 archive_string_init(&pathname);
601 archive_string_init(&linkname);
602 archive_string_init(&conv_buffer.aes_mbs);
603 archive_string_init(&conv_buffer.aes_mbs_in_locale);
604 archive_string_init(&conv_buffer.aes_utf8);
605 archive_string_init(&conv_buffer.aes_wcs);
606 if (0 != archive_mstring_copy_mbs_len_l(&conv_buffer, lha->dirname.s, lha->dirname.length, lha->sconv_dir)) {
607 archive_set_error(&a->archive,
608 ARCHIVE_ERRNO_FILE_FORMAT,
609 "Pathname cannot be converted "
610 "from %s to Unicode",
611 archive_string_conversion_charset_name(lha->sconv_dir));
612 err = ARCHIVE_FATAL;
613 } else if (0 != archive_mstring_get_wcs(&a->archive, &conv_buffer, &conv_buffer_p))
614 err = ARCHIVE_FATAL;
615 if (err == ARCHIVE_FATAL) {
616 archive_mstring_clean(&conv_buffer);
617 archive_wstring_free(&pathname);
618 archive_wstring_free(&linkname);
619 return (err);
620 }
621 archive_wstring_copy(&pathname, &conv_buffer.aes_wcs);
622
623 archive_string_empty(&conv_buffer.aes_mbs);
624 archive_string_empty(&conv_buffer.aes_mbs_in_locale);
625 archive_string_empty(&conv_buffer.aes_utf8);
626 archive_wstring_empty(&conv_buffer.aes_wcs);
627 if (0 != archive_mstring_copy_mbs_len_l(&conv_buffer, lha->filename.s, lha->filename.length, lha->sconv_fname)) {
628 archive_set_error(&a->archive,
629 ARCHIVE_ERRNO_FILE_FORMAT,
630 "Pathname cannot be converted "
631 "from %s to Unicode",
632 archive_string_conversion_charset_name(lha->sconv_fname));
633 err = ARCHIVE_FATAL;
634 }
635 else if (0 != archive_mstring_get_wcs(&a->archive, &conv_buffer, &conv_buffer_p))
636 err = ARCHIVE_FATAL;
637 if (err == ARCHIVE_FATAL) {
638 archive_mstring_clean(&conv_buffer);
639 archive_wstring_free(&pathname);
640 archive_wstring_free(&linkname);
641 return (err);
642 }
643 archive_wstring_concat(&pathname, &conv_buffer.aes_wcs);
644 archive_mstring_clean(&conv_buffer);
645
646 if ((lha->mode & AE_IFMT) == AE_IFLNK) {
647 /*
648 * Extract the symlink-name if it's included in the pathname.
649 */
650 if (!lha_parse_linkname(&linkname, &pathname)) {
651 /* We couldn't get the symlink-name. */
652 archive_set_error(&a->archive,
653 ARCHIVE_ERRNO_FILE_FORMAT,
654 "Unknown symlink-name");
655 archive_wstring_free(&pathname);
656 archive_wstring_free(&linkname);
657 return (ARCHIVE_FAILED);
658 }
659 } else {
660 /*
661 * Make sure a file-type is set.
662 * The mode has been overridden if it is in the extended data.
663 */
664 lha->mode = (lha->mode & ~AE_IFMT) |
665 ((lha->directory)? AE_IFDIR: AE_IFREG);
666 }
667 if ((lha->setflag & UNIX_MODE_IS_SET) == 0 &&
668 (lha->dos_attr & 1) != 0)
669 lha->mode &= ~(0222);/* read only. */
670
671 /*
672 * Set basic file parameters.
673 */
674 archive_entry_copy_pathname_w(entry, pathname.s);
675 archive_wstring_free(&pathname);
676 if (archive_strlen(&linkname) > 0) {
677 archive_entry_copy_symlink_w(entry, linkname.s);
678 } else
679 archive_entry_set_symlink(entry, NULL);
680 archive_wstring_free(&linkname);
681 /*
682 * When a header level is 0, there is a possibility that
683 * a pathname and a symlink has '\' character, a directory
684 * separator in DOS/Windows. So we should convert it to '/'.
685 */
686 if (lha->level == 0)
687 lha_replace_path_separator(lha, entry);
688
689 archive_entry_set_mode(entry, lha->mode);
690 archive_entry_set_uid(entry, lha->uid);
691 archive_entry_set_gid(entry, lha->gid);
692 if (archive_strlen(&lha->uname) > 0)
693 archive_entry_set_uname(entry, lha->uname.s);
694 if (archive_strlen(&lha->gname) > 0)
695 archive_entry_set_gname(entry, lha->gname.s);
696 if (lha->setflag & BIRTHTIME_IS_SET) {
697 archive_entry_set_birthtime(entry, lha->birthtime,
698 lha->birthtime_tv_nsec);
699 archive_entry_set_ctime(entry, lha->birthtime,
700 lha->birthtime_tv_nsec);
701 } else {
702 archive_entry_unset_birthtime(entry);
703 archive_entry_unset_ctime(entry);
704 }
705 archive_entry_set_mtime(entry, lha->mtime, lha->mtime_tv_nsec);
706 if (lha->setflag & ATIME_IS_SET)
707 archive_entry_set_atime(entry, lha->atime,
708 lha->atime_tv_nsec);
709 else
710 archive_entry_unset_atime(entry);
711 if (lha->directory || archive_entry_symlink(entry) != NULL)
712 archive_entry_unset_size(entry);
713 else
714 archive_entry_set_size(entry, lha->origsize);
715
716 /*
717 * Prepare variables used to read a file content.
718 */
719 lha->entry_bytes_remaining = lha->compsize;
720 if (lha->entry_bytes_remaining < 0) {
721 archive_set_error(&a->archive,
722 ARCHIVE_ERRNO_FILE_FORMAT,
723 "Invalid LHa entry size");
724 return (ARCHIVE_FATAL);
725 }
726 lha->entry_offset = 0;
727 lha->entry_crc_calculated = 0;
728
729 /*
730 * This file does not have a content.
731 */
732 if (lha->directory || lha->compsize == 0)
733 lha->end_of_entry = 1;
734
735 snprintf(lha->format_name, sizeof(lha->format_name), "lha -%c%c%c-",
736 lha->method[0], lha->method[1], lha->method[2]);
737 a->archive.archive_format_name = lha->format_name;
738
739 return (err);
740 }
741
742 /*
743 * Replace a DOS path separator '\' by a character '/'.
744 * Some multi-byte character set have a character '\' in its second byte.
745 */
746 static void
lha_replace_path_separator(struct lha * lha,struct archive_entry * entry)747 lha_replace_path_separator(struct lha *lha, struct archive_entry *entry)
748 {
749 const wchar_t *wp;
750 size_t i;
751
752 if ((wp = archive_entry_pathname_w(entry)) != NULL) {
753 archive_wstrcpy(&(lha->ws), wp);
754 for (i = 0; i < archive_strlen(&(lha->ws)); i++) {
755 if (lha->ws.s[i] == L'\\')
756 lha->ws.s[i] = L'/';
757 }
758 archive_entry_copy_pathname_w(entry, lha->ws.s);
759 }
760
761 if ((wp = archive_entry_symlink_w(entry)) != NULL) {
762 archive_wstrcpy(&(lha->ws), wp);
763 for (i = 0; i < archive_strlen(&(lha->ws)); i++) {
764 if (lha->ws.s[i] == L'\\')
765 lha->ws.s[i] = L'/';
766 }
767 archive_entry_copy_symlink_w(entry, lha->ws.s);
768 }
769 }
770
771 /*
772 * Header 0 format
773 *
774 * +0 +1 +2 +7 +11
775 * +---------------+----------+----------------+-------------------+
776 * |header size(*1)|header sum|compression type|compressed size(*2)|
777 * +---------------+----------+----------------+-------------------+
778 * <---------------------(*1)----------*
779 *
780 * +11 +15 +17 +19 +20 +21
781 * +-----------------+---------+---------+--------------+----------------+
782 * |uncompressed size|time(DOS)|date(DOS)|attribute(DOS)|header level(=0)|
783 * +-----------------+---------+---------+--------------+----------------+
784 * *--------------------------------(*1)---------------------------------*
785 *
786 * +21 +22 +22+(*3) +22+(*3)+2 +22+(*3)+2+(*4)
787 * +---------------+---------+----------+----------------+------------------+
788 * |name length(*3)|file name|file CRC16|extra header(*4)| compressed data |
789 * +---------------+---------+----------+----------------+------------------+
790 * <--(*3)-> <------(*2)------>
791 * *----------------------(*1)-------------------------->
792 *
793 */
794 #define H0_HEADER_SIZE_OFFSET 0
795 #define H0_HEADER_SUM_OFFSET 1
796 #define H0_COMP_SIZE_OFFSET 7
797 #define H0_ORIG_SIZE_OFFSET 11
798 #define H0_DOS_TIME_OFFSET 15
799 #define H0_NAME_LEN_OFFSET 21
800 #define H0_FILE_NAME_OFFSET 22
801 #define H0_FIXED_SIZE 24
802 static int
lha_read_file_header_0(struct archive_read * a,struct lha * lha)803 lha_read_file_header_0(struct archive_read *a, struct lha *lha)
804 {
805 const unsigned char *p;
806 int extdsize, namelen;
807 unsigned char headersum, sum_calculated;
808
809 if ((p = __archive_read_ahead(a, H0_FIXED_SIZE, NULL)) == NULL)
810 return (truncated_error(a));
811 lha->header_size = p[H0_HEADER_SIZE_OFFSET] + 2;
812 headersum = p[H0_HEADER_SUM_OFFSET];
813 lha->compsize = archive_le32dec(p + H0_COMP_SIZE_OFFSET);
814 lha->origsize = archive_le32dec(p + H0_ORIG_SIZE_OFFSET);
815 lha->mtime = dos_to_unix(archive_le32dec(p + H0_DOS_TIME_OFFSET));
816 namelen = p[H0_NAME_LEN_OFFSET];
817 extdsize = (int)lha->header_size - H0_FIXED_SIZE - namelen;
818 if ((namelen > 221 || extdsize < 0) && extdsize != -2) {
819 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
820 "Invalid LHa header");
821 return (ARCHIVE_FATAL);
822 }
823 if ((p = __archive_read_ahead(a, lha->header_size, NULL)) == NULL)
824 return (truncated_error(a));
825
826 archive_strncpy(&lha->filename, p + H0_FILE_NAME_OFFSET, namelen);
827 /* When extdsize == -2, A CRC16 value is not present in the header. */
828 if (extdsize >= 0) {
829 lha->crc = archive_le16dec(p + H0_FILE_NAME_OFFSET + namelen);
830 lha->setflag |= CRC_IS_SET;
831 }
832 sum_calculated = lha_calcsum(0, p, 2, lha->header_size - 2);
833
834 /* Read an extended header */
835 if (extdsize > 0) {
836 /* This extended data is set by 'LHa for UNIX' only.
837 * Maybe fixed size.
838 */
839 p += H0_FILE_NAME_OFFSET + namelen + 2;
840 if (p[0] == 'U' && extdsize == 12) {
841 /* p[1] is a minor version. */
842 lha->mtime = archive_le32dec(&p[2]);
843 lha->mode = archive_le16dec(&p[6]);
844 lha->uid = archive_le16dec(&p[8]);
845 lha->gid = archive_le16dec(&p[10]);
846 lha->setflag |= UNIX_MODE_IS_SET;
847 }
848 }
849 __archive_read_consume(a, lha->header_size);
850
851 if (sum_calculated != headersum) {
852 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
853 "LHa header sum error");
854 return (ARCHIVE_FATAL);
855 }
856
857 return (ARCHIVE_OK);
858 }
859
860 /*
861 * Header 1 format
862 *
863 * +0 +1 +2 +7 +11
864 * +---------------+----------+----------------+-------------+
865 * |header size(*1)|header sum|compression type|skip size(*2)|
866 * +---------------+----------+----------------+-------------+
867 * <---------------(*1)----------*
868 *
869 * +11 +15 +17 +19 +20 +21
870 * +-----------------+---------+---------+--------------+----------------+
871 * |uncompressed size|time(DOS)|date(DOS)|attribute(DOS)|header level(=1)|
872 * +-----------------+---------+---------+--------------+----------------+
873 * *-------------------------------(*1)----------------------------------*
874 *
875 * +21 +22 +22+(*3) +22+(*3)+2 +22+(*3)+3 +22+(*3)+3+(*4)
876 * +---------------+---------+----------+-----------+-----------+
877 * |name length(*3)|file name|file CRC16| creator |padding(*4)|
878 * +---------------+---------+----------+-----------+-----------+
879 * <--(*3)->
880 * *----------------------------(*1)----------------------------*
881 *
882 * +22+(*3)+3+(*4) +22+(*3)+3+(*4)+2 +22+(*3)+3+(*4)+2+(*5)
883 * +----------------+---------------------+------------------------+
884 * |next header size| extended header(*5) | compressed data |
885 * +----------------+---------------------+------------------------+
886 * *------(*1)-----> <--------------------(*2)-------------------->
887 */
888 #define H1_HEADER_SIZE_OFFSET 0
889 #define H1_HEADER_SUM_OFFSET 1
890 #define H1_COMP_SIZE_OFFSET 7
891 #define H1_ORIG_SIZE_OFFSET 11
892 #define H1_DOS_TIME_OFFSET 15
893 #define H1_NAME_LEN_OFFSET 21
894 #define H1_FILE_NAME_OFFSET 22
895 #define H1_FIXED_SIZE 27
896 static int
lha_read_file_header_1(struct archive_read * a,struct lha * lha)897 lha_read_file_header_1(struct archive_read *a, struct lha *lha)
898 {
899 const unsigned char *p;
900 size_t extdsize;
901 int err, err2;
902 int namelen, padding;
903 unsigned char headersum, sum_calculated;
904
905 err = ARCHIVE_OK;
906
907 if ((p = __archive_read_ahead(a, H1_FIXED_SIZE, NULL)) == NULL)
908 return (truncated_error(a));
909
910 lha->header_size = p[H1_HEADER_SIZE_OFFSET] + 2;
911 headersum = p[H1_HEADER_SUM_OFFSET];
912 /* Note: An extended header size is included in a compsize. */
913 lha->compsize = archive_le32dec(p + H1_COMP_SIZE_OFFSET);
914 lha->origsize = archive_le32dec(p + H1_ORIG_SIZE_OFFSET);
915 lha->mtime = dos_to_unix(archive_le32dec(p + H1_DOS_TIME_OFFSET));
916 namelen = p[H1_NAME_LEN_OFFSET];
917 /* Calculate a padding size. The result will be normally 0 only(?) */
918 padding = ((int)lha->header_size) - H1_FIXED_SIZE - namelen;
919
920 if (namelen > 230 || padding < 0)
921 goto invalid;
922
923 if ((p = __archive_read_ahead(a, lha->header_size, NULL)) == NULL)
924 return (truncated_error(a));
925
926 if (memchr(p + H1_FILE_NAME_OFFSET, 0xff,
927 (size_t)namelen) != NULL)
928 goto invalid; /* Invalid filename. */
929 archive_strncpy(&lha->filename, p + H1_FILE_NAME_OFFSET, namelen);
930 lha->crc = archive_le16dec(p + H1_FILE_NAME_OFFSET + namelen);
931 lha->setflag |= CRC_IS_SET;
932
933 sum_calculated = lha_calcsum(0, p, 2, lha->header_size - 2);
934 /* Consume used bytes but not include `next header size' data
935 * since it will be consumed in lha_read_file_extended_header(). */
936 __archive_read_consume(a, lha->header_size - 2);
937
938 /* Read extended headers */
939 err2 = lha_read_file_extended_header(a, lha, NULL, 2,
940 (uint64_t)(lha->compsize + 2), &extdsize);
941 if (err2 < ARCHIVE_WARN)
942 return (err2);
943 if (err2 < err)
944 err = err2;
945 /* Get a real compressed file size. */
946 lha->compsize -= extdsize - 2;
947
948 if (lha->compsize < 0)
949 goto invalid; /* Invalid compressed file size */
950
951 if (sum_calculated != headersum) {
952 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
953 "LHa header sum error");
954 return (ARCHIVE_FATAL);
955 }
956 return (err);
957 invalid:
958 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
959 "Invalid LHa header");
960 return (ARCHIVE_FATAL);
961 }
962
963 /*
964 * Header 2 format
965 *
966 * +0 +2 +7 +11 +15
967 * +---------------+----------------+-------------------+-----------------+
968 * |header size(*1)|compression type|compressed size(*2)|uncompressed size|
969 * +---------------+----------------+-------------------+-----------------+
970 * <--------------------------------(*1)---------------------------------*
971 *
972 * +15 +19 +20 +21 +23 +24
973 * +-----------------+------------+----------------+----------+-----------+
974 * |data/time(time_t)| 0x20 fixed |header level(=2)|file CRC16| creator |
975 * +-----------------+------------+----------------+----------+-----------+
976 * *---------------------------------(*1)---------------------------------*
977 *
978 * +24 +26 +26+(*3) +26+(*3)+(*4)
979 * +----------------+-------------------+-------------+-------------------+
980 * |next header size|extended header(*3)| padding(*4) | compressed data |
981 * +----------------+-------------------+-------------+-------------------+
982 * *--------------------------(*1)-------------------> <------(*2)------->
983 *
984 */
985 #define H2_HEADER_SIZE_OFFSET 0
986 #define H2_COMP_SIZE_OFFSET 7
987 #define H2_ORIG_SIZE_OFFSET 11
988 #define H2_TIME_OFFSET 15
989 #define H2_CRC_OFFSET 21
990 #define H2_FIXED_SIZE 24
991 static int
lha_read_file_header_2(struct archive_read * a,struct lha * lha)992 lha_read_file_header_2(struct archive_read *a, struct lha *lha)
993 {
994 const unsigned char *p;
995 size_t extdsize;
996 int err, padding;
997 uint16_t header_crc;
998
999 if ((p = __archive_read_ahead(a, H2_FIXED_SIZE, NULL)) == NULL)
1000 return (truncated_error(a));
1001
1002 lha->header_size =archive_le16dec(p + H2_HEADER_SIZE_OFFSET);
1003 lha->compsize = archive_le32dec(p + H2_COMP_SIZE_OFFSET);
1004 lha->origsize = archive_le32dec(p + H2_ORIG_SIZE_OFFSET);
1005 lha->mtime = archive_le32dec(p + H2_TIME_OFFSET);
1006 lha->crc = archive_le16dec(p + H2_CRC_OFFSET);
1007 lha->setflag |= CRC_IS_SET;
1008
1009 if (lha->header_size < H2_FIXED_SIZE) {
1010 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1011 "Invalid LHa header size");
1012 return (ARCHIVE_FATAL);
1013 }
1014
1015 header_crc = lha_crc16(0, p, H2_FIXED_SIZE);
1016 __archive_read_consume(a, H2_FIXED_SIZE);
1017
1018 /* Read extended headers */
1019 err = lha_read_file_extended_header(a, lha, &header_crc, 2,
1020 lha->header_size - H2_FIXED_SIZE, &extdsize);
1021 if (err < ARCHIVE_WARN)
1022 return (err);
1023
1024 /* Calculate a padding size. The result will be normally 0 or 1. */
1025 padding = (int)lha->header_size - (int)(H2_FIXED_SIZE + extdsize);
1026 if (padding > 0) {
1027 if ((p = __archive_read_ahead(a, padding, NULL)) == NULL)
1028 return (truncated_error(a));
1029 header_crc = lha_crc16(header_crc, p, padding);
1030 __archive_read_consume(a, padding);
1031 }
1032
1033 if (header_crc != lha->header_crc) {
1034 #ifndef DONT_FAIL_ON_CRC_ERROR
1035 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1036 "LHa header CRC error");
1037 return (ARCHIVE_FATAL);
1038 #endif
1039 }
1040 return (err);
1041 }
1042
1043 /*
1044 * Header 3 format
1045 *
1046 * +0 +2 +7 +11 +15
1047 * +------------+----------------+-------------------+-----------------+
1048 * | 0x04 fixed |compression type|compressed size(*2)|uncompressed size|
1049 * +------------+----------------+-------------------+-----------------+
1050 * <-------------------------------(*1)-------------------------------*
1051 *
1052 * +15 +19 +20 +21 +23 +24
1053 * +-----------------+------------+----------------+----------+-----------+
1054 * |date/time(time_t)| 0x20 fixed |header level(=3)|file CRC16| creator |
1055 * +-----------------+------------+----------------+----------+-----------+
1056 * *--------------------------------(*1)----------------------------------*
1057 *
1058 * +24 +28 +32 +32+(*3)
1059 * +---------------+----------------+-------------------+-----------------+
1060 * |header size(*1)|next header size|extended header(*3)| compressed data |
1061 * +---------------+----------------+-------------------+-----------------+
1062 * *------------------------(*1)-----------------------> <------(*2)----->
1063 *
1064 */
1065 #define H3_FIELD_LEN_OFFSET 0
1066 #define H3_COMP_SIZE_OFFSET 7
1067 #define H3_ORIG_SIZE_OFFSET 11
1068 #define H3_TIME_OFFSET 15
1069 #define H3_CRC_OFFSET 21
1070 #define H3_HEADER_SIZE_OFFSET 24
1071 #define H3_FIXED_SIZE 28
1072 static int
lha_read_file_header_3(struct archive_read * a,struct lha * lha)1073 lha_read_file_header_3(struct archive_read *a, struct lha *lha)
1074 {
1075 const unsigned char *p;
1076 size_t extdsize;
1077 int err;
1078 uint16_t header_crc;
1079
1080 if ((p = __archive_read_ahead(a, H3_FIXED_SIZE, NULL)) == NULL)
1081 return (truncated_error(a));
1082
1083 if (archive_le16dec(p + H3_FIELD_LEN_OFFSET) != 4)
1084 goto invalid;
1085 lha->header_size = archive_le32dec(p + H3_HEADER_SIZE_OFFSET);
1086 lha->compsize = archive_le32dec(p + H3_COMP_SIZE_OFFSET);
1087 lha->origsize = archive_le32dec(p + H3_ORIG_SIZE_OFFSET);
1088 lha->mtime = archive_le32dec(p + H3_TIME_OFFSET);
1089 lha->crc = archive_le16dec(p + H3_CRC_OFFSET);
1090 lha->setflag |= CRC_IS_SET;
1091
1092 if (lha->header_size < H3_FIXED_SIZE + 4)
1093 goto invalid;
1094 header_crc = lha_crc16(0, p, H3_FIXED_SIZE);
1095 __archive_read_consume(a, H3_FIXED_SIZE);
1096
1097 /* Reject ridiculously large header */
1098 if (lha->header_size > 65536) {
1099 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1100 "LHa header size too large");
1101 return (ARCHIVE_FATAL);
1102 }
1103
1104 /* Read extended headers */
1105 err = lha_read_file_extended_header(a, lha, &header_crc, 4,
1106 lha->header_size - H3_FIXED_SIZE, &extdsize);
1107 if (err < ARCHIVE_WARN)
1108 return (err);
1109
1110 if (header_crc != lha->header_crc) {
1111 #ifndef DONT_FAIL_ON_CRC_ERROR
1112 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1113 "LHa header CRC error");
1114 return (ARCHIVE_FATAL);
1115 #endif
1116 }
1117 return (err);
1118 invalid:
1119 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1120 "Invalid LHa header");
1121 return (ARCHIVE_FATAL);
1122 }
1123
1124 /*
1125 * Extended header format
1126 *
1127 * +0 +2 +3 -- used in header 1 and 2
1128 * +0 +4 +5 -- used in header 3
1129 * +--------------+---------+-------------------+--------------+--
1130 * |ex-header size|header id| data |ex-header size| .......
1131 * +--------------+---------+-------------------+--------------+--
1132 * <-------------( ex-header size)------------> <-- next extended header --*
1133 *
1134 * If the ex-header size is zero, it is the make of the end of extended
1135 * headers.
1136 *
1137 */
1138 static int
lha_read_file_extended_header(struct archive_read * a,struct lha * lha,uint16_t * crc,int sizefield_length,uint64_t limitsize,size_t * total_size)1139 lha_read_file_extended_header(struct archive_read *a, struct lha *lha,
1140 uint16_t *crc, int sizefield_length, uint64_t limitsize, size_t *total_size)
1141 {
1142 const void *h;
1143 const unsigned char *extdheader;
1144 size_t extdsize;
1145 size_t datasize;
1146 unsigned int i;
1147 unsigned char extdtype;
1148
1149 #define EXT_HEADER_CRC 0x00 /* Header CRC and information*/
1150 #define EXT_FILENAME 0x01 /* Filename */
1151 #define EXT_DIRECTORY 0x02 /* Directory name */
1152 #define EXT_DOS_ATTR 0x40 /* MS-DOS attribute */
1153 #define EXT_TIMESTAMP 0x41 /* Windows time stamp */
1154 #define EXT_FILESIZE 0x42 /* Large file size */
1155 #define EXT_TIMEZONE 0x43 /* Time zone */
1156 #define EXT_UTF16_FILENAME 0x44 /* UTF-16 filename */
1157 #define EXT_UTF16_DIRECTORY 0x45 /* UTF-16 directory name */
1158 #define EXT_CODEPAGE 0x46 /* Codepage */
1159 #define EXT_UNIX_MODE 0x50 /* File permission */
1160 #define EXT_UNIX_GID_UID 0x51 /* gid,uid */
1161 #define EXT_UNIX_GNAME 0x52 /* Group name */
1162 #define EXT_UNIX_UNAME 0x53 /* User name */
1163 #define EXT_UNIX_MTIME 0x54 /* Modified time */
1164 #define EXT_OS2_NEW_ATTR 0x7f /* new attribute(OS/2 only) */
1165 #define EXT_NEW_ATTR 0xff /* new attribute */
1166
1167 *total_size = sizefield_length;
1168
1169 for (;;) {
1170 /* Read an extended header size. */
1171 if ((h =
1172 __archive_read_ahead(a, sizefield_length, NULL)) == NULL)
1173 return (truncated_error(a));
1174 /* Check if the size is the zero indicates the end of the
1175 * extended header. */
1176 if (sizefield_length == sizeof(uint16_t))
1177 extdsize = archive_le16dec(h);
1178 else
1179 extdsize = archive_le32dec(h);
1180 if (extdsize == 0) {
1181 /* End of extended header */
1182 if (crc != NULL)
1183 *crc = lha_crc16(*crc, h, sizefield_length);
1184 __archive_read_consume(a, sizefield_length);
1185 return (ARCHIVE_OK);
1186 }
1187
1188 /* Sanity check to the extended header size. */
1189 if (((uint64_t)*total_size + extdsize) > limitsize ||
1190 extdsize <= (size_t)sizefield_length)
1191 goto invalid;
1192
1193 /* Read the extended header. */
1194 if ((h = __archive_read_ahead(a, extdsize, NULL)) == NULL)
1195 return (truncated_error(a));
1196 *total_size += extdsize;
1197
1198 extdheader = (const unsigned char *)h;
1199 /* Get the extended header type. */
1200 extdtype = extdheader[sizefield_length];
1201 /* Calculate an extended data size. */
1202 datasize = extdsize - (1 + sizefield_length);
1203 /* Skip an extended header size field and type field. */
1204 extdheader += sizefield_length + 1;
1205
1206 if (crc != NULL && extdtype != EXT_HEADER_CRC)
1207 *crc = lha_crc16(*crc, h, extdsize);
1208 switch (extdtype) {
1209 case EXT_HEADER_CRC:
1210 /* We only use a header CRC. Following data will not
1211 * be used. */
1212 if (datasize >= 2) {
1213 lha->header_crc = archive_le16dec(extdheader);
1214 if (crc != NULL) {
1215 static const char zeros[2] = {0, 0};
1216 *crc = lha_crc16(*crc, h,
1217 extdsize - datasize);
1218 /* CRC value itself as zero */
1219 *crc = lha_crc16(*crc, zeros, 2);
1220 *crc = lha_crc16(*crc,
1221 extdheader+2, datasize - 2);
1222 }
1223 }
1224 break;
1225 case EXT_FILENAME:
1226 if (datasize == 0) {
1227 /* maybe directory header */
1228 archive_string_empty(&lha->filename);
1229 break;
1230 }
1231 if (extdheader[0] == '\0')
1232 goto invalid;
1233 archive_strncpy(&lha->filename,
1234 (const char *)extdheader, datasize);
1235 break;
1236 case EXT_UTF16_FILENAME:
1237 if (datasize == 0) {
1238 /* maybe directory header */
1239 archive_string_empty(&lha->filename);
1240 break;
1241 } else if (datasize & 1) {
1242 /* UTF-16 characters take always 2 or 4 bytes */
1243 goto invalid;
1244 }
1245 if (extdheader[0] == '\0')
1246 goto invalid;
1247 archive_string_empty(&lha->filename);
1248 archive_array_append(&lha->filename,
1249 (const char *)extdheader, datasize);
1250 /* Setup a string conversion for a filename. */
1251 lha->sconv_fname =
1252 archive_string_conversion_from_charset(&a->archive,
1253 "UTF-16LE", 1);
1254 if (lha->sconv_fname == NULL)
1255 return (ARCHIVE_FATAL);
1256 break;
1257 case EXT_DIRECTORY:
1258 if (datasize == 0 || extdheader[0] == '\0')
1259 /* no directory name data. exit this case. */
1260 goto invalid;
1261
1262 archive_strncpy(&lha->dirname,
1263 (const char *)extdheader, datasize);
1264 /*
1265 * Convert directory delimiter from 0xFF
1266 * to '/' for local system.
1267 */
1268 for (i = 0; i < lha->dirname.length; i++) {
1269 if ((unsigned char)lha->dirname.s[i] == 0xFF)
1270 lha->dirname.s[i] = '/';
1271 }
1272 /* Is last character directory separator? */
1273 if (lha->dirname.s[lha->dirname.length-1] != '/')
1274 /* invalid directory data */
1275 goto invalid;
1276 break;
1277 case EXT_UTF16_DIRECTORY:
1278 /* UTF-16 characters take always 2 or 4 bytes */
1279 if (datasize == 0 || (datasize & 1) ||
1280 extdheader[0] == '\0') {
1281 /* no directory name data. exit this case. */
1282 goto invalid;
1283 }
1284
1285 archive_string_empty(&lha->dirname);
1286 archive_array_append(&lha->dirname,
1287 (const char *)extdheader, datasize);
1288 lha->sconv_dir =
1289 archive_string_conversion_from_charset(&a->archive,
1290 "UTF-16LE", 1);
1291 if (lha->sconv_dir == NULL)
1292 return (ARCHIVE_FATAL);
1293 else {
1294 /*
1295 * Convert directory delimiter from 0xFFFF
1296 * to '/' for local system.
1297 */
1298 uint16_t dirSep;
1299 uint16_t d = 1;
1300 if (archive_be16dec(&d) == 1)
1301 dirSep = 0x2F00;
1302 else
1303 dirSep = 0x002F;
1304
1305 /* UTF-16LE character */
1306 uint16_t *utf16name =
1307 (uint16_t *)lha->dirname.s;
1308 for (i = 0; i < lha->dirname.length / 2; i++) {
1309 if (utf16name[i] == 0xFFFF) {
1310 utf16name[i] = dirSep;
1311 }
1312 }
1313 /* Is last character directory separator? */
1314 if (utf16name[lha->dirname.length / 2 - 1] !=
1315 dirSep) {
1316 /* invalid directory data */
1317 goto invalid;
1318 }
1319 }
1320 break;
1321 case EXT_DOS_ATTR:
1322 if (datasize == 2)
1323 lha->dos_attr = (unsigned char)
1324 (archive_le16dec(extdheader) & 0xff);
1325 break;
1326 case EXT_TIMESTAMP:
1327 if (datasize == (sizeof(uint64_t) * 3)) {
1328 ntfs_to_unix(archive_le64dec(extdheader),
1329 &lha->birthtime,
1330 &lha->birthtime_tv_nsec);
1331 extdheader += sizeof(uint64_t);
1332 ntfs_to_unix(archive_le64dec(extdheader),
1333 &lha->mtime,
1334 &lha->mtime_tv_nsec);
1335 extdheader += sizeof(uint64_t);
1336 ntfs_to_unix(archive_le64dec(extdheader),
1337 &lha->atime,
1338 &lha->atime_tv_nsec);
1339 lha->setflag |= BIRTHTIME_IS_SET |
1340 ATIME_IS_SET;
1341 }
1342 break;
1343 case EXT_FILESIZE:
1344 if (datasize == sizeof(uint64_t) * 2) {
1345 lha->compsize = archive_le64dec(extdheader);
1346 extdheader += sizeof(uint64_t);
1347 lha->origsize = archive_le64dec(extdheader);
1348 if (lha->compsize < 0 || lha->origsize < 0)
1349 goto invalid;
1350 }
1351 break;
1352 case EXT_CODEPAGE:
1353 /* Get an archived filename charset from codepage.
1354 * This overwrites the charset specified by
1355 * hdrcharset option. */
1356 if (datasize == sizeof(uint32_t)) {
1357 struct archive_string cp;
1358 const char *charset;
1359
1360 archive_string_init(&cp);
1361 switch (archive_le32dec(extdheader)) {
1362 case 65001: /* UTF-8 */
1363 charset = "UTF-8";
1364 break;
1365 default:
1366 archive_string_sprintf(&cp, "CP%d",
1367 (int)archive_le32dec(extdheader));
1368 charset = cp.s;
1369 break;
1370 }
1371 lha->sconv_dir =
1372 archive_string_conversion_from_charset(
1373 &(a->archive), charset, 1);
1374 lha->sconv_fname =
1375 archive_string_conversion_from_charset(
1376 &(a->archive), charset, 1);
1377 archive_string_free(&cp);
1378 if (lha->sconv_dir == NULL)
1379 return (ARCHIVE_FATAL);
1380 if (lha->sconv_fname == NULL)
1381 return (ARCHIVE_FATAL);
1382 }
1383 break;
1384 case EXT_UNIX_MODE:
1385 if (datasize == sizeof(uint16_t)) {
1386 lha->mode = archive_le16dec(extdheader);
1387 lha->setflag |= UNIX_MODE_IS_SET;
1388 }
1389 break;
1390 case EXT_UNIX_GID_UID:
1391 if (datasize == (sizeof(uint16_t) * 2)) {
1392 lha->gid = archive_le16dec(extdheader);
1393 lha->uid = archive_le16dec(extdheader+2);
1394 }
1395 break;
1396 case EXT_UNIX_GNAME:
1397 if (datasize > 0)
1398 archive_strncpy(&lha->gname,
1399 (const char *)extdheader, datasize);
1400 break;
1401 case EXT_UNIX_UNAME:
1402 if (datasize > 0)
1403 archive_strncpy(&lha->uname,
1404 (const char *)extdheader, datasize);
1405 break;
1406 case EXT_UNIX_MTIME:
1407 if (datasize == sizeof(uint32_t))
1408 lha->mtime = archive_le32dec(extdheader);
1409 break;
1410 case EXT_OS2_NEW_ATTR:
1411 /* This extended header is OS/2 depend. */
1412 if (datasize == 16) {
1413 lha->dos_attr = (unsigned char)
1414 (archive_le16dec(extdheader) & 0xff);
1415 lha->mode = archive_le16dec(extdheader+2);
1416 lha->gid = archive_le16dec(extdheader+4);
1417 lha->uid = archive_le16dec(extdheader+6);
1418 lha->birthtime = archive_le32dec(extdheader+8);
1419 lha->atime = archive_le32dec(extdheader+12);
1420 lha->setflag |= UNIX_MODE_IS_SET
1421 | BIRTHTIME_IS_SET | ATIME_IS_SET;
1422 }
1423 break;
1424 case EXT_NEW_ATTR:
1425 if (datasize == 20) {
1426 lha->mode = (mode_t)archive_le32dec(extdheader);
1427 lha->gid = archive_le32dec(extdheader+4);
1428 lha->uid = archive_le32dec(extdheader+8);
1429 lha->birthtime = archive_le32dec(extdheader+12);
1430 lha->atime = archive_le32dec(extdheader+16);
1431 lha->setflag |= UNIX_MODE_IS_SET
1432 | BIRTHTIME_IS_SET | ATIME_IS_SET;
1433 }
1434 break;
1435 case EXT_TIMEZONE: /* Not supported */
1436 break;
1437 default:
1438 break;
1439 }
1440
1441 __archive_read_consume(a, extdsize);
1442 }
1443 invalid:
1444 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1445 "Invalid extended LHa header");
1446 return (ARCHIVE_FATAL);
1447 }
1448
1449 static int
lha_end_of_entry(struct archive_read * a)1450 lha_end_of_entry(struct archive_read *a)
1451 {
1452 struct lha *lha = a->format->data;
1453 int r = ARCHIVE_EOF;
1454
1455 if (!lha->end_of_entry_cleanup) {
1456 if ((lha->setflag & CRC_IS_SET) &&
1457 lha->crc != lha->entry_crc_calculated) {
1458 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
1459 "LHa data CRC error");
1460 r = ARCHIVE_WARN;
1461 }
1462
1463 /* End-of-entry cleanup done. */
1464 lha->end_of_entry_cleanup = 1;
1465 }
1466 return (r);
1467 }
1468
1469 static int
archive_read_format_lha_read_data(struct archive_read * a,const void ** buff,size_t * size,int64_t * offset)1470 archive_read_format_lha_read_data(struct archive_read *a,
1471 const void **buff, size_t *size, int64_t *offset)
1472 {
1473 struct lha *lha = a->format->data;
1474 int r;
1475
1476 if (lha->entry_unconsumed) {
1477 /* Consume as much as the decompressor actually used. */
1478 __archive_read_consume(a, lha->entry_unconsumed);
1479 lha->entry_unconsumed = 0;
1480 }
1481 if (lha->end_of_entry) {
1482 *offset = lha->entry_offset;
1483 *size = 0;
1484 *buff = NULL;
1485 return (lha_end_of_entry(a));
1486 }
1487
1488 if (lha->entry_is_compressed)
1489 r = lha_read_data_lzh(a, buff, size, offset);
1490 else
1491 /* No compression. */
1492 r = lha_read_data_none(a, buff, size, offset);
1493 return (r);
1494 }
1495
1496 /*
1497 * Read a file content in no compression.
1498 *
1499 * Returns ARCHIVE_OK if successful, ARCHIVE_FATAL otherwise, sets
1500 * lha->end_of_entry if it consumes all of the data.
1501 */
1502 static int
lha_read_data_none(struct archive_read * a,const void ** buff,size_t * size,int64_t * offset)1503 lha_read_data_none(struct archive_read *a, const void **buff,
1504 size_t *size, int64_t *offset)
1505 {
1506 struct lha *lha = a->format->data;
1507 ssize_t bytes_avail;
1508
1509 if (lha->entry_bytes_remaining == 0) {
1510 *buff = NULL;
1511 *size = 0;
1512 *offset = lha->entry_offset;
1513 lha->end_of_entry = 1;
1514 return (ARCHIVE_OK);
1515 }
1516 /*
1517 * Note: '1' here is a performance optimization.
1518 * Recall that the decompression layer returns a count of
1519 * available bytes; asking for more than that forces the
1520 * decompressor to combine reads by copying data.
1521 */
1522 *buff = __archive_read_ahead(a, 1, &bytes_avail);
1523 if (bytes_avail <= 0) {
1524 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1525 "Truncated LHa file data");
1526 return (ARCHIVE_FATAL);
1527 }
1528 if (bytes_avail > lha->entry_bytes_remaining)
1529 bytes_avail = (ssize_t)lha->entry_bytes_remaining;
1530 lha->entry_crc_calculated =
1531 lha_crc16(lha->entry_crc_calculated, *buff, bytes_avail);
1532 *size = bytes_avail;
1533 *offset = lha->entry_offset;
1534 lha->entry_offset += bytes_avail;
1535 lha->entry_bytes_remaining -= bytes_avail;
1536 if (lha->entry_bytes_remaining == 0)
1537 lha->end_of_entry = 1;
1538 lha->entry_unconsumed = bytes_avail;
1539 return (ARCHIVE_OK);
1540 }
1541
1542 /*
1543 * Read a file content in LZHUFF encoding.
1544 *
1545 * Returns ARCHIVE_OK if successful, returns ARCHIVE_WARN if compression is
1546 * unsupported, ARCHIVE_FATAL otherwise, sets lha->end_of_entry if it consumes
1547 * all of the data.
1548 */
1549 static int
lha_read_data_lzh(struct archive_read * a,const void ** buff,size_t * size,int64_t * offset)1550 lha_read_data_lzh(struct archive_read *a, const void **buff,
1551 size_t *size, int64_t *offset)
1552 {
1553 struct lha *lha = a->format->data;
1554 ssize_t bytes_avail;
1555 int r;
1556
1557 /* If we haven't yet read any data, initialize the decompressor. */
1558 if (!lha->decompress_init) {
1559 r = lzh_decode_init(&(lha->strm), lha->method);
1560 switch (r) {
1561 case ARCHIVE_OK:
1562 break;
1563 case ARCHIVE_FAILED:
1564 /* Unsupported compression. */
1565 *buff = NULL;
1566 *size = 0;
1567 *offset = 0;
1568 archive_set_error(&a->archive,
1569 ARCHIVE_ERRNO_FILE_FORMAT,
1570 "Unsupported lzh compression method -%c%c%c-",
1571 lha->method[0], lha->method[1], lha->method[2]);
1572 /* We know compressed size; just skip it. */
1573 archive_read_format_lha_read_data_skip(a);
1574 return (ARCHIVE_WARN);
1575 default:
1576 archive_set_error(&a->archive, ENOMEM,
1577 "Couldn't allocate memory "
1578 "for lzh decompression");
1579 return (ARCHIVE_FATAL);
1580 }
1581 /* We've initialized decompression for this stream. */
1582 lha->decompress_init = 1;
1583 lha->strm.avail_out = 0;
1584 }
1585
1586 /*
1587 * Note: '1' here is a performance optimization.
1588 * Recall that the decompression layer returns a count of
1589 * available bytes; asking for more than that forces the
1590 * decompressor to combine reads by copying data.
1591 */
1592 lha->strm.next_in = __archive_read_ahead(a, 1, &bytes_avail);
1593 if (bytes_avail <= 0) {
1594 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
1595 "Truncated LHa file body");
1596 return (ARCHIVE_FATAL);
1597 }
1598 if (bytes_avail > lha->entry_bytes_remaining)
1599 bytes_avail = (ssize_t)lha->entry_bytes_remaining;
1600
1601 lha->strm.avail_in = (int)bytes_avail;
1602 lha->strm.total_in = 0;
1603 lha->strm.avail_out = 0;
1604
1605 r = lzh_decode(&(lha->strm), bytes_avail == lha->entry_bytes_remaining);
1606 switch (r) {
1607 case ARCHIVE_OK:
1608 break;
1609 case ARCHIVE_EOF:
1610 lha->end_of_entry = 1;
1611 break;
1612 default:
1613 archive_set_error(&a->archive, ARCHIVE_ERRNO_MISC,
1614 "Bad lzh data");
1615 return (ARCHIVE_FAILED);
1616 }
1617 lha->entry_unconsumed = lha->strm.total_in;
1618 lha->entry_bytes_remaining -= lha->strm.total_in;
1619
1620 if (lha->strm.avail_out) {
1621 *offset = lha->entry_offset;
1622 *size = lha->strm.avail_out;
1623 *buff = lha->strm.ref_ptr;
1624 lha->entry_crc_calculated =
1625 lha_crc16(lha->entry_crc_calculated, *buff, *size);
1626 lha->entry_offset += *size;
1627 } else {
1628 *offset = lha->entry_offset;
1629 *size = 0;
1630 *buff = NULL;
1631 if (lha->end_of_entry)
1632 return (lha_end_of_entry(a));
1633 }
1634 return (ARCHIVE_OK);
1635 }
1636
1637 /*
1638 * Skip a file content.
1639 */
1640 static int
archive_read_format_lha_read_data_skip(struct archive_read * a)1641 archive_read_format_lha_read_data_skip(struct archive_read *a)
1642 {
1643 struct lha *lha = a->format->data;
1644 int64_t bytes_skipped;
1645
1646 if (lha->entry_unconsumed) {
1647 /* Consume as much as the decompressor actually used. */
1648 __archive_read_consume(a, lha->entry_unconsumed);
1649 lha->entry_unconsumed = 0;
1650 }
1651
1652 /* if we've already read to end of data, we're done. */
1653 if (lha->end_of_entry_cleanup)
1654 return (ARCHIVE_OK);
1655
1656 /*
1657 * If the length is at the beginning, we can skip the
1658 * compressed data much more quickly.
1659 */
1660 bytes_skipped = __archive_read_consume(a, lha->entry_bytes_remaining);
1661 if (bytes_skipped < 0)
1662 return (ARCHIVE_FATAL);
1663
1664 /* This entry is finished and done. */
1665 lha->end_of_entry_cleanup = lha->end_of_entry = 1;
1666 return (ARCHIVE_OK);
1667 }
1668
1669 static int
archive_read_format_lha_cleanup(struct archive_read * a)1670 archive_read_format_lha_cleanup(struct archive_read *a)
1671 {
1672 struct lha *lha = a->format->data;
1673
1674 lzh_decode_free(&(lha->strm));
1675 archive_string_free(&(lha->dirname));
1676 archive_string_free(&(lha->filename));
1677 archive_string_free(&(lha->uname));
1678 archive_string_free(&(lha->gname));
1679 archive_wstring_free(&(lha->ws));
1680 free(lha);
1681 a->format->data = NULL;
1682 return (ARCHIVE_OK);
1683 }
1684
1685 /*
1686 * 'LHa for UNIX' utility has archived a symbolic-link name after
1687 * a pathname with '|' character.
1688 * This function extracts the symbolic-link name from the pathname.
1689 *
1690 * example.
1691 * 1. a symbolic-name is 'aaa/bb/cc'
1692 * 2. a filename is 'xxx/bbb'
1693 * then an archived pathname is 'xxx/bbb|aaa/bb/cc'
1694 */
1695 static int
lha_parse_linkname(struct archive_wstring * linkname,struct archive_wstring * pathname)1696 lha_parse_linkname(struct archive_wstring *linkname,
1697 struct archive_wstring *pathname)
1698 {
1699 wchar_t * linkptr;
1700 size_t symlen;
1701
1702 linkptr = wcschr(pathname->s, L'|');
1703 if (linkptr != NULL) {
1704 symlen = wcslen(linkptr + 1);
1705 archive_wstrncpy(linkname, linkptr+1, symlen);
1706
1707 *linkptr = 0;
1708 pathname->length = wcslen(pathname->s);
1709
1710 return (1);
1711 }
1712 return (0);
1713 }
1714
1715 static unsigned char
lha_calcsum(unsigned char sum,const void * pp,int offset,size_t size)1716 lha_calcsum(unsigned char sum, const void *pp, int offset, size_t size)
1717 {
1718 unsigned char const *p = (unsigned char const *)pp;
1719
1720 p += offset;
1721 for (;size > 0; --size)
1722 sum += *p++;
1723 return (sum);
1724 }
1725
1726 static const uint16_t crc16tbl[2][256] = {
1727 {
1728 0x0000, 0xc0c1, 0xc181, 0x0140, 0xc301, 0x03c0, 0x0280,
1729 0xc241, 0xc601, 0x06c0, 0x0780, 0xc741, 0x0500, 0xc5c1,
1730 0xc481, 0x0440, 0xcc01, 0x0cc0, 0x0d80, 0xcd41, 0x0f00,
1731 0xcfc1, 0xce81, 0x0e40, 0x0a00, 0xcac1, 0xcb81, 0x0b40,
1732 0xc901, 0x09c0, 0x0880, 0xc841, 0xd801, 0x18c0, 0x1980,
1733 0xd941, 0x1b00, 0xdbc1, 0xda81, 0x1a40, 0x1e00, 0xdec1,
1734 0xdf81, 0x1f40, 0xdd01, 0x1dc0, 0x1c80, 0xdc41, 0x1400,
1735 0xd4c1, 0xd581, 0x1540, 0xd701, 0x17c0, 0x1680, 0xd641,
1736 0xd201, 0x12c0, 0x1380, 0xd341, 0x1100, 0xd1c1, 0xd081,
1737 0x1040, 0xf001, 0x30c0, 0x3180, 0xf141, 0x3300, 0xf3c1,
1738 0xf281, 0x3240, 0x3600, 0xf6c1, 0xf781, 0x3740, 0xf501,
1739 0x35c0, 0x3480, 0xf441, 0x3c00, 0xfcc1, 0xfd81, 0x3d40,
1740 0xff01, 0x3fc0, 0x3e80, 0xfe41, 0xfa01, 0x3ac0, 0x3b80,
1741 0xfb41, 0x3900, 0xf9c1, 0xf881, 0x3840, 0x2800, 0xe8c1,
1742 0xe981, 0x2940, 0xeb01, 0x2bc0, 0x2a80, 0xea41, 0xee01,
1743 0x2ec0, 0x2f80, 0xef41, 0x2d00, 0xedc1, 0xec81, 0x2c40,
1744 0xe401, 0x24c0, 0x2580, 0xe541, 0x2700, 0xe7c1, 0xe681,
1745 0x2640, 0x2200, 0xe2c1, 0xe381, 0x2340, 0xe101, 0x21c0,
1746 0x2080, 0xe041, 0xa001, 0x60c0, 0x6180, 0xa141, 0x6300,
1747 0xa3c1, 0xa281, 0x6240, 0x6600, 0xa6c1, 0xa781, 0x6740,
1748 0xa501, 0x65c0, 0x6480, 0xa441, 0x6c00, 0xacc1, 0xad81,
1749 0x6d40, 0xaf01, 0x6fc0, 0x6e80, 0xae41, 0xaa01, 0x6ac0,
1750 0x6b80, 0xab41, 0x6900, 0xa9c1, 0xa881, 0x6840, 0x7800,
1751 0xb8c1, 0xb981, 0x7940, 0xbb01, 0x7bc0, 0x7a80, 0xba41,
1752 0xbe01, 0x7ec0, 0x7f80, 0xbf41, 0x7d00, 0xbdc1, 0xbc81,
1753 0x7c40, 0xb401, 0x74c0, 0x7580, 0xb541, 0x7700, 0xb7c1,
1754 0xb681, 0x7640, 0x7200, 0xb2c1, 0xb381, 0x7340, 0xb101,
1755 0x71c0, 0x7080, 0xb041, 0x5000, 0x90c1, 0x9181, 0x5140,
1756 0x9301, 0x53c0, 0x5280, 0x9241, 0x9601, 0x56c0, 0x5780,
1757 0x9741, 0x5500, 0x95c1, 0x9481, 0x5440, 0x9c01, 0x5cc0,
1758 0x5d80, 0x9d41, 0x5f00, 0x9fc1, 0x9e81, 0x5e40, 0x5a00,
1759 0x9ac1, 0x9b81, 0x5b40, 0x9901, 0x59c0, 0x5880, 0x9841,
1760 0x8801, 0x48c0, 0x4980, 0x8941, 0x4b00, 0x8bc1, 0x8a81,
1761 0x4a40, 0x4e00, 0x8ec1, 0x8f81, 0x4f40, 0x8d01, 0x4dc0,
1762 0x4c80, 0x8c41, 0x4400, 0x84c1, 0x8581, 0x4540, 0x8701,
1763 0x47c0, 0x4680, 0x8641, 0x8201, 0x42c0, 0x4380, 0x8341,
1764 0x4100, 0x81c1, 0x8081, 0x4040
1765 },
1766 {
1767 0x0000, 0x9001, 0x6001, 0xf000, 0xc002, 0x5003, 0xa003,
1768 0x3002, 0xc007, 0x5006, 0xa006, 0x3007, 0x0005, 0x9004,
1769 0x6004, 0xf005, 0xc00d, 0x500c, 0xa00c, 0x300d, 0x000f,
1770 0x900e, 0x600e, 0xf00f, 0x000a, 0x900b, 0x600b, 0xf00a,
1771 0xc008, 0x5009, 0xa009, 0x3008, 0xc019, 0x5018, 0xa018,
1772 0x3019, 0x001b, 0x901a, 0x601a, 0xf01b, 0x001e, 0x901f,
1773 0x601f, 0xf01e, 0xc01c, 0x501d, 0xa01d, 0x301c, 0x0014,
1774 0x9015, 0x6015, 0xf014, 0xc016, 0x5017, 0xa017, 0x3016,
1775 0xc013, 0x5012, 0xa012, 0x3013, 0x0011, 0x9010, 0x6010,
1776 0xf011, 0xc031, 0x5030, 0xa030, 0x3031, 0x0033, 0x9032,
1777 0x6032, 0xf033, 0x0036, 0x9037, 0x6037, 0xf036, 0xc034,
1778 0x5035, 0xa035, 0x3034, 0x003c, 0x903d, 0x603d, 0xf03c,
1779 0xc03e, 0x503f, 0xa03f, 0x303e, 0xc03b, 0x503a, 0xa03a,
1780 0x303b, 0x0039, 0x9038, 0x6038, 0xf039, 0x0028, 0x9029,
1781 0x6029, 0xf028, 0xc02a, 0x502b, 0xa02b, 0x302a, 0xc02f,
1782 0x502e, 0xa02e, 0x302f, 0x002d, 0x902c, 0x602c, 0xf02d,
1783 0xc025, 0x5024, 0xa024, 0x3025, 0x0027, 0x9026, 0x6026,
1784 0xf027, 0x0022, 0x9023, 0x6023, 0xf022, 0xc020, 0x5021,
1785 0xa021, 0x3020, 0xc061, 0x5060, 0xa060, 0x3061, 0x0063,
1786 0x9062, 0x6062, 0xf063, 0x0066, 0x9067, 0x6067, 0xf066,
1787 0xc064, 0x5065, 0xa065, 0x3064, 0x006c, 0x906d, 0x606d,
1788 0xf06c, 0xc06e, 0x506f, 0xa06f, 0x306e, 0xc06b, 0x506a,
1789 0xa06a, 0x306b, 0x0069, 0x9068, 0x6068, 0xf069, 0x0078,
1790 0x9079, 0x6079, 0xf078, 0xc07a, 0x507b, 0xa07b, 0x307a,
1791 0xc07f, 0x507e, 0xa07e, 0x307f, 0x007d, 0x907c, 0x607c,
1792 0xf07d, 0xc075, 0x5074, 0xa074, 0x3075, 0x0077, 0x9076,
1793 0x6076, 0xf077, 0x0072, 0x9073, 0x6073, 0xf072, 0xc070,
1794 0x5071, 0xa071, 0x3070, 0x0050, 0x9051, 0x6051, 0xf050,
1795 0xc052, 0x5053, 0xa053, 0x3052, 0xc057, 0x5056, 0xa056,
1796 0x3057, 0x0055, 0x9054, 0x6054, 0xf055, 0xc05d, 0x505c,
1797 0xa05c, 0x305d, 0x005f, 0x905e, 0x605e, 0xf05f, 0x005a,
1798 0x905b, 0x605b, 0xf05a, 0xc058, 0x5059, 0xa059, 0x3058,
1799 0xc049, 0x5048, 0xa048, 0x3049, 0x004b, 0x904a, 0x604a,
1800 0xf04b, 0x004e, 0x904f, 0x604f, 0xf04e, 0xc04c, 0x504d,
1801 0xa04d, 0x304c, 0x0044, 0x9045, 0x6045, 0xf044, 0xc046,
1802 0x5047, 0xa047, 0x3046, 0xc043, 0x5042, 0xa042, 0x3043,
1803 0x0041, 0x9040, 0x6040, 0xf041
1804 }
1805 };
1806
1807 static uint16_t
lha_crc16(uint16_t crc,const void * pp,size_t len)1808 lha_crc16(uint16_t crc, const void *pp, size_t len)
1809 {
1810 const unsigned char *p = (const unsigned char *)pp;
1811 const uint16_t *buff;
1812 const union {
1813 uint32_t i;
1814 char c[4];
1815 } u = { 0x01020304 };
1816
1817 if (len == 0)
1818 return crc;
1819
1820 /* Process unaligned address. */
1821 if (((uintptr_t)p) & (uintptr_t)0x1) {
1822 crc = (crc >> 8) ^ crc16tbl[0][(crc ^ *p++) & 0xff];
1823 len--;
1824 }
1825 buff = (const uint16_t *)p;
1826 /*
1827 * Modern C compiler such as GCC does not unroll automatically yet
1828 * without unrolling pragma, and Clang is so. So we should
1829 * unroll this loop for its performance.
1830 */
1831 for (;len >= 8; len -= 8) {
1832 /* This if statement expects compiler optimization will
1833 * remove the statement which will not be executed. */
1834 #undef bswap16
1835 #ifndef __has_builtin
1836 #define __has_builtin(x) 0
1837 #endif
1838 #if defined(_MSC_VER) && _MSC_VER >= 1400 /* Visual Studio */
1839 # define bswap16(x) _byteswap_ushort(x)
1840 #elif defined(__GNUC__) && ((__GNUC__ == 4 && __GNUC_MINOR__ >= 8) || __GNUC__ > 4)
1841 /* GCC 4.8 and later has __builtin_bswap16() */
1842 # define bswap16(x) __builtin_bswap16(x)
1843 #elif defined(__clang__) && __has_builtin(__builtin_bswap16)
1844 /* Newer clang versions have __builtin_bswap16() */
1845 # define bswap16(x) __builtin_bswap16(x)
1846 #else
1847 # define bswap16(x) ((((x) >> 8) & 0xff) | ((x) << 8))
1848 #endif
1849 #define CRC16W do { \
1850 if(u.c[0] == 1) { /* Big endian */ \
1851 crc ^= bswap16(*buff); buff++; \
1852 } else \
1853 crc ^= *buff++; \
1854 crc = crc16tbl[1][crc & 0xff] ^ crc16tbl[0][crc >> 8];\
1855 } while (0)
1856 CRC16W;
1857 CRC16W;
1858 CRC16W;
1859 CRC16W;
1860 #undef CRC16W
1861 #undef bswap16
1862 }
1863
1864 p = (const unsigned char *)buff;
1865 for (;len; len--) {
1866 crc = (crc >> 8) ^ crc16tbl[0][(crc ^ *p++) & 0xff];
1867 }
1868 return crc;
1869 }
1870
1871 /*
1872 * Initialize LZHUF decoder.
1873 *
1874 * Returns ARCHIVE_OK if initialization was successful.
1875 * Returns ARCHIVE_FAILED if method is unsupported.
1876 * Returns ARCHIVE_FATAL if initialization failed; memory allocation
1877 * error occurred.
1878 */
1879 static int
lzh_decode_init(struct lzh_stream * strm,const char * method)1880 lzh_decode_init(struct lzh_stream *strm, const char *method)
1881 {
1882 struct lzh_dec *ds;
1883 int w_bits, w_size;
1884
1885 if (strm->ds == NULL) {
1886 strm->ds = calloc(1, sizeof(*strm->ds));
1887 if (strm->ds == NULL)
1888 return (ARCHIVE_FATAL);
1889 }
1890 ds = strm->ds;
1891 ds->error = ARCHIVE_FAILED;
1892 if (method == NULL || method[0] != 'l' || method[1] != 'h')
1893 return (ARCHIVE_FAILED);
1894 switch (method[2]) {
1895 case '5':
1896 w_bits = 13;/* 8KiB for window */
1897 break;
1898 case '6':
1899 w_bits = 15;/* 32KiB for window */
1900 break;
1901 case '7':
1902 w_bits = 16;/* 64KiB for window */
1903 break;
1904 default:
1905 return (ARCHIVE_FAILED);/* Not supported. */
1906 }
1907 ds->error = ARCHIVE_FATAL;
1908 /* Expand a window size up to 128 KiB for decompressing process
1909 * performance whatever its original window size is. */
1910 ds->w_size = 1U << 17;
1911 ds->w_mask = ds->w_size -1;
1912 if (ds->w_buff == NULL) {
1913 ds->w_buff = malloc(ds->w_size);
1914 if (ds->w_buff == NULL)
1915 return (ARCHIVE_FATAL);
1916 }
1917 w_size = 1U << w_bits;
1918 memset(ds->w_buff + ds->w_size - w_size, 0x20, w_size);
1919 ds->w_pos = 0;
1920 ds->state = 0;
1921 ds->pos_pt_len_size = w_bits + 1;
1922 ds->pos_pt_len_bits = (w_bits == 15 || w_bits == 16)? 5: 4;
1923 ds->literal_pt_len_size = PT_BITLEN_SIZE;
1924 ds->literal_pt_len_bits = 5;
1925 ds->br.cache_buffer = 0;
1926 ds->br.cache_avail = 0;
1927
1928 if (lzh_huffman_init(&(ds->lt), LT_BITLEN_SIZE, 16)
1929 != ARCHIVE_OK)
1930 return (ARCHIVE_FATAL);
1931 ds->lt.len_bits = 9;
1932 if (lzh_huffman_init(&(ds->pt), PT_BITLEN_SIZE, 16)
1933 != ARCHIVE_OK)
1934 return (ARCHIVE_FATAL);
1935 ds->error = 0;
1936
1937 return (ARCHIVE_OK);
1938 }
1939
1940 /*
1941 * Release LZHUF decoder.
1942 */
1943 static void
lzh_decode_free(struct lzh_stream * strm)1944 lzh_decode_free(struct lzh_stream *strm)
1945 {
1946
1947 if (strm->ds == NULL)
1948 return;
1949 free(strm->ds->w_buff);
1950 lzh_huffman_free(&(strm->ds->lt));
1951 lzh_huffman_free(&(strm->ds->pt));
1952 free(strm->ds);
1953 strm->ds = NULL;
1954 }
1955
1956 /*
1957 * Bit stream reader.
1958 */
1959 /* Check that the cache buffer has enough bits. */
1960 #define lzh_br_has(br, n) ((br)->cache_avail >= n)
1961 /* Get compressed data by bit. */
1962 #define lzh_br_bits(br, n) \
1963 (((uint16_t)((br)->cache_buffer >> \
1964 ((br)->cache_avail - (n)))) & cache_masks[n])
1965 #define lzh_br_bits_forced(br, n) \
1966 (((uint16_t)((br)->cache_buffer << \
1967 ((n) - (br)->cache_avail))) & cache_masks[n])
1968 /* Read ahead to make sure the cache buffer has enough compressed data we
1969 * will use.
1970 * True : completed, there is enough data in the cache buffer.
1971 * False : we met that strm->next_in is empty, we have to get following
1972 * bytes. */
1973 #define lzh_br_read_ahead_0(strm, br, n) \
1974 (lzh_br_has(br, (n)) || lzh_br_fillup(strm, br))
1975 /* True : the cache buffer has some bits as much as we need.
1976 * False : there are no enough bits in the cache buffer to be used,
1977 * we have to get following bytes if we could. */
1978 #define lzh_br_read_ahead(strm, br, n) \
1979 (lzh_br_read_ahead_0((strm), (br), (n)) || lzh_br_has((br), (n)))
1980
1981 /* Notify how many bits we consumed. */
1982 #define lzh_br_consume(br, n) ((br)->cache_avail -= (n))
1983 #define lzh_br_unconsume(br, n) ((br)->cache_avail += (n))
1984
1985 static const uint16_t cache_masks[] = {
1986 0x0000, 0x0001, 0x0003, 0x0007,
1987 0x000F, 0x001F, 0x003F, 0x007F,
1988 0x00FF, 0x01FF, 0x03FF, 0x07FF,
1989 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF,
1990 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF
1991 };
1992
1993 /*
1994 * Shift away used bits in the cache data and fill it up with following bits.
1995 * Call this when cache buffer does not have enough bits you need.
1996 *
1997 * Returns 1 if the cache buffer is full.
1998 * Returns 0 if the cache buffer is not full; input buffer is empty.
1999 */
2000 static int
lzh_br_fillup(struct lzh_stream * strm,struct lzh_br * br)2001 lzh_br_fillup(struct lzh_stream *strm, struct lzh_br *br)
2002 {
2003 int n = CACHE_BITS - br->cache_avail;
2004
2005 for (;;) {
2006 const int x = n >> 3;
2007 if (strm->avail_in >= x) {
2008 switch (x) {
2009 case 8:
2010 br->cache_buffer =
2011 ((uint64_t)strm->next_in[0]) << 56 |
2012 ((uint64_t)strm->next_in[1]) << 48 |
2013 ((uint64_t)strm->next_in[2]) << 40 |
2014 ((uint64_t)strm->next_in[3]) << 32 |
2015 ((uint32_t)strm->next_in[4]) << 24 |
2016 ((uint32_t)strm->next_in[5]) << 16 |
2017 ((uint32_t)strm->next_in[6]) << 8 |
2018 (uint32_t)strm->next_in[7];
2019 strm->next_in += 8;
2020 strm->avail_in -= 8;
2021 br->cache_avail += 8 * 8;
2022 return (1);
2023 case 7:
2024 br->cache_buffer =
2025 (br->cache_buffer << 56) |
2026 ((uint64_t)strm->next_in[0]) << 48 |
2027 ((uint64_t)strm->next_in[1]) << 40 |
2028 ((uint64_t)strm->next_in[2]) << 32 |
2029 ((uint64_t)strm->next_in[3]) << 24 |
2030 ((uint64_t)strm->next_in[4]) << 16 |
2031 ((uint64_t)strm->next_in[5]) << 8 |
2032 (uint64_t)strm->next_in[6];
2033 strm->next_in += 7;
2034 strm->avail_in -= 7;
2035 br->cache_avail += 7 * 8;
2036 return (1);
2037 case 6:
2038 br->cache_buffer =
2039 (br->cache_buffer << 48) |
2040 ((uint64_t)strm->next_in[0]) << 40 |
2041 ((uint64_t)strm->next_in[1]) << 32 |
2042 ((uint64_t)strm->next_in[2]) << 24 |
2043 ((uint64_t)strm->next_in[3]) << 16 |
2044 ((uint64_t)strm->next_in[4]) << 8 |
2045 (uint64_t)strm->next_in[5];
2046 strm->next_in += 6;
2047 strm->avail_in -= 6;
2048 br->cache_avail += 6 * 8;
2049 return (1);
2050 case 0:
2051 /* We have enough compressed data in
2052 * the cache buffer.*/
2053 return (1);
2054 default:
2055 break;
2056 }
2057 }
2058 if (strm->avail_in == 0) {
2059 /* There is not enough compressed data to fill up the
2060 * cache buffer. */
2061 return (0);
2062 }
2063 br->cache_buffer =
2064 (br->cache_buffer << 8) | *strm->next_in++;
2065 strm->avail_in--;
2066 br->cache_avail += 8;
2067 n -= 8;
2068 }
2069 }
2070
2071 /*
2072 * Decode LZHUF.
2073 *
2074 * 1. Returns ARCHIVE_OK if output buffer or input buffer are empty.
2075 * Please set available buffer and call this function again.
2076 * 2. Returns ARCHIVE_EOF if decompression has been completed.
2077 * 3. Returns ARCHIVE_FAILED if an error occurred; compressed data
2078 * is broken or you do not set 'last' flag properly.
2079 * 4. 'last' flag is very important, you must set 1 to the flag if there
2080 * is no input data. The lha compressed data format does not provide how
2081 * to know the compressed data is really finished.
2082 * Note: lha command utility check if the total size of output bytes is
2083 * reached the uncompressed size recorded in its header. it does not mind
2084 * that the decoding process is properly finished.
2085 * GNU ZIP can decompress another compressed file made by SCO LZH compress.
2086 * it handles EOF as null to fill read buffer with zero until the decoding
2087 * process meet 2 bytes of zeros at reading a size of a next chunk, so the
2088 * zeros are treated as the mark of the end of the data although the zeros
2089 * is dummy, not the file data.
2090 */
2091 static int lzh_read_blocks(struct lzh_stream *, int);
2092 static int lzh_decode_blocks(struct lzh_stream *, int);
2093 #define ST_RD_BLOCK 0
2094 #define ST_RD_PT_1 1
2095 #define ST_RD_PT_2 2
2096 #define ST_RD_PT_3 3
2097 #define ST_RD_PT_4 4
2098 #define ST_RD_LITERAL_1 5
2099 #define ST_RD_LITERAL_2 6
2100 #define ST_RD_LITERAL_3 7
2101 #define ST_RD_POS_DATA_1 8
2102 #define ST_GET_LITERAL 9
2103 #define ST_GET_POS_1 10
2104 #define ST_GET_POS_2 11
2105 #define ST_COPY_DATA 12
2106
2107 static int
lzh_decode(struct lzh_stream * strm,int last)2108 lzh_decode(struct lzh_stream *strm, int last)
2109 {
2110 struct lzh_dec *ds = strm->ds;
2111 int avail_in;
2112 int r;
2113
2114 if (ds->error)
2115 return (ds->error);
2116
2117 avail_in = strm->avail_in;
2118 do {
2119 if (ds->state < ST_GET_LITERAL)
2120 r = lzh_read_blocks(strm, last);
2121 else
2122 r = lzh_decode_blocks(strm, last);
2123 } while (r == 100);
2124 strm->total_in += avail_in - strm->avail_in;
2125 return (r);
2126 }
2127
2128 static void
lzh_emit_window(struct lzh_stream * strm,size_t s)2129 lzh_emit_window(struct lzh_stream *strm, size_t s)
2130 {
2131 strm->ref_ptr = strm->ds->w_buff;
2132 strm->avail_out = (int)s;
2133 }
2134
2135 static int
lzh_read_blocks(struct lzh_stream * strm,int last)2136 lzh_read_blocks(struct lzh_stream *strm, int last)
2137 {
2138 struct lzh_dec *ds = strm->ds;
2139 struct lzh_br *br = &(ds->br);
2140 int c = 0, i;
2141 unsigned rbits;
2142
2143 for (;;) {
2144 switch (ds->state) {
2145 case ST_RD_BLOCK:
2146 /*
2147 * Read a block number indicates how many blocks
2148 * we will handle. The block is composed of a
2149 * literal and a match, sometimes a literal only
2150 * in particular, there are no reference data at
2151 * the beginning of the decompression.
2152 */
2153 if (!lzh_br_read_ahead_0(strm, br, 16)) {
2154 if (!last)
2155 /* We need following data. */
2156 return (ARCHIVE_OK);
2157 if (lzh_br_has(br, 8)) {
2158 /*
2159 * It seems there are extra bits.
2160 * 1. Compressed data is broken.
2161 * 2. `last' flag does not properly
2162 * set.
2163 */
2164 goto failed;
2165 }
2166 if (ds->w_pos > 0) {
2167 lzh_emit_window(strm, ds->w_pos);
2168 ds->w_pos = 0;
2169 return (ARCHIVE_OK);
2170 }
2171 /* End of compressed data; we have completely
2172 * handled all compressed data. */
2173 return (ARCHIVE_EOF);
2174 }
2175 ds->blocks_avail = lzh_br_bits(br, 16);
2176 if (ds->blocks_avail == 0)
2177 goto failed;
2178 lzh_br_consume(br, 16);
2179 /*
2180 * Read a literal table compressed in huffman
2181 * coding.
2182 */
2183 ds->pt.len_size = ds->literal_pt_len_size;
2184 ds->pt.len_bits = ds->literal_pt_len_bits;
2185 ds->reading_position = 0;
2186 /* FALL THROUGH */
2187 case ST_RD_PT_1:
2188 /* Note: ST_RD_PT_1, ST_RD_PT_2 and ST_RD_PT_4 are
2189 * used in reading both a literal table and a
2190 * position table. */
2191 if (!lzh_br_read_ahead(strm, br, ds->pt.len_bits)) {
2192 if (last)
2193 goto failed;/* Truncated data. */
2194 ds->state = ST_RD_PT_1;
2195 return (ARCHIVE_OK);
2196 }
2197 ds->pt.len_avail = lzh_br_bits(br, ds->pt.len_bits);
2198 lzh_br_consume(br, ds->pt.len_bits);
2199 /* FALL THROUGH */
2200 case ST_RD_PT_2:
2201 if (ds->pt.len_avail == 0) {
2202 /* There is no bitlen. */
2203 if (!lzh_br_read_ahead(strm, br,
2204 ds->pt.len_bits)) {
2205 if (last)
2206 goto failed;/* Truncated data.*/
2207 ds->state = ST_RD_PT_2;
2208 return (ARCHIVE_OK);
2209 }
2210 if (!lzh_make_fake_table(&(ds->pt),
2211 lzh_br_bits(br, ds->pt.len_bits)))
2212 goto failed;/* Invalid data. */
2213 lzh_br_consume(br, ds->pt.len_bits);
2214 if (ds->reading_position)
2215 ds->state = ST_GET_LITERAL;
2216 else
2217 ds->state = ST_RD_LITERAL_1;
2218 break;
2219 } else if (ds->pt.len_avail > ds->pt.len_size)
2220 goto failed;/* Invalid data. */
2221 ds->loop = 0;
2222 memset(ds->pt.freq, 0, sizeof(ds->pt.freq));
2223 if (ds->pt.len_avail < 3 ||
2224 ds->pt.len_size == ds->pos_pt_len_size) {
2225 ds->state = ST_RD_PT_4;
2226 break;
2227 }
2228 /* FALL THROUGH */
2229 case ST_RD_PT_3:
2230 ds->loop = lzh_read_pt_bitlen(strm, ds->loop, 3);
2231 if (ds->loop < 3) {
2232 if (ds->loop < 0 || last)
2233 goto failed;/* Invalid data. */
2234 /* Not completed, get following data. */
2235 ds->state = ST_RD_PT_3;
2236 return (ARCHIVE_OK);
2237 }
2238 /* There are some null in bitlen of the literal. */
2239 if (!lzh_br_read_ahead(strm, br, 2)) {
2240 if (last)
2241 goto failed;/* Truncated data. */
2242 ds->state = ST_RD_PT_3;
2243 return (ARCHIVE_OK);
2244 }
2245 c = lzh_br_bits(br, 2);
2246 lzh_br_consume(br, 2);
2247 if (c > ds->pt.len_avail - 3)
2248 goto failed;/* Invalid data. */
2249 for (i = 3; c-- > 0 ;)
2250 ds->pt.bitlen[i++] = 0;
2251 ds->loop = i;
2252 /* FALL THROUGH */
2253 case ST_RD_PT_4:
2254 ds->loop = lzh_read_pt_bitlen(strm, ds->loop,
2255 ds->pt.len_avail);
2256 if (ds->loop < ds->pt.len_avail) {
2257 if (ds->loop < 0 || last)
2258 goto failed;/* Invalid data. */
2259 /* Not completed, get following data. */
2260 ds->state = ST_RD_PT_4;
2261 return (ARCHIVE_OK);
2262 }
2263 if (!lzh_make_huffman_table(&(ds->pt)))
2264 goto failed;/* Invalid data */
2265 if (ds->reading_position) {
2266 ds->state = ST_GET_LITERAL;
2267 break;
2268 }
2269 /* FALL THROUGH */
2270 case ST_RD_LITERAL_1:
2271 if (!lzh_br_read_ahead(strm, br, ds->lt.len_bits)) {
2272 if (last)
2273 goto failed;/* Truncated data. */
2274 ds->state = ST_RD_LITERAL_1;
2275 return (ARCHIVE_OK);
2276 }
2277 ds->lt.len_avail = lzh_br_bits(br, ds->lt.len_bits);
2278 lzh_br_consume(br, ds->lt.len_bits);
2279 /* FALL THROUGH */
2280 case ST_RD_LITERAL_2:
2281 if (ds->lt.len_avail == 0) {
2282 /* There is no bitlen. */
2283 if (!lzh_br_read_ahead(strm, br,
2284 ds->lt.len_bits)) {
2285 if (last)
2286 goto failed;/* Truncated data.*/
2287 ds->state = ST_RD_LITERAL_2;
2288 return (ARCHIVE_OK);
2289 }
2290 if (!lzh_make_fake_table(&(ds->lt),
2291 lzh_br_bits(br, ds->lt.len_bits)))
2292 goto failed;/* Invalid data */
2293 lzh_br_consume(br, ds->lt.len_bits);
2294 ds->state = ST_RD_POS_DATA_1;
2295 break;
2296 } else if (ds->lt.len_avail > ds->lt.len_size)
2297 goto failed;/* Invalid data */
2298 ds->loop = 0;
2299 memset(ds->lt.freq, 0, sizeof(ds->lt.freq));
2300 /* FALL THROUGH */
2301 case ST_RD_LITERAL_3:
2302 i = ds->loop;
2303 while (i < ds->lt.len_avail) {
2304 if (!lzh_br_read_ahead(strm, br,
2305 ds->pt.max_bits)) {
2306 if (last)
2307 goto failed;/* Truncated data.*/
2308 ds->loop = i;
2309 ds->state = ST_RD_LITERAL_3;
2310 return (ARCHIVE_OK);
2311 }
2312 rbits = lzh_br_bits(br, ds->pt.max_bits);
2313 c = lzh_decode_huffman(&(ds->pt), rbits);
2314 if (c > 2) {
2315 /* Note: 'c' will never be more than
2316 * eighteen since it's limited by
2317 * PT_BITLEN_SIZE, which is being set
2318 * to ds->pt.len_size through
2319 * ds->literal_pt_len_size. */
2320 lzh_br_consume(br, ds->pt.bitlen[c]);
2321 c -= 2;
2322 ds->lt.freq[c]++;
2323 ds->lt.bitlen[i++] = c;
2324 } else if (c == 0) {
2325 lzh_br_consume(br, ds->pt.bitlen[c]);
2326 ds->lt.bitlen[i++] = 0;
2327 } else {
2328 /* c == 1 or c == 2 */
2329 int n = (c == 1)?4:9;
2330 if (!lzh_br_read_ahead(strm, br,
2331 ds->pt.bitlen[c] + n)) {
2332 if (last) /* Truncated data. */
2333 goto failed;
2334 ds->loop = i;
2335 ds->state = ST_RD_LITERAL_3;
2336 return (ARCHIVE_OK);
2337 }
2338 lzh_br_consume(br, ds->pt.bitlen[c]);
2339 c = lzh_br_bits(br, n);
2340 lzh_br_consume(br, n);
2341 c += (n == 4)?3:20;
2342 if (i + c > ds->lt.len_avail)
2343 goto failed;/* Invalid data */
2344 memset(&(ds->lt.bitlen[i]), 0, c);
2345 i += c;
2346 }
2347 }
2348 if (i > ds->lt.len_avail ||
2349 !lzh_make_huffman_table(&(ds->lt)))
2350 goto failed;/* Invalid data */
2351 /* FALL THROUGH */
2352 case ST_RD_POS_DATA_1:
2353 /*
2354 * Read a position table compressed in huffman
2355 * coding.
2356 */
2357 ds->pt.len_size = ds->pos_pt_len_size;
2358 ds->pt.len_bits = ds->pos_pt_len_bits;
2359 ds->reading_position = 1;
2360 ds->state = ST_RD_PT_1;
2361 break;
2362 case ST_GET_LITERAL:
2363 return (100);
2364 }
2365 }
2366 failed:
2367 return (ds->error = ARCHIVE_FAILED);
2368 }
2369
2370 static int
lzh_decode_blocks(struct lzh_stream * strm,int last)2371 lzh_decode_blocks(struct lzh_stream *strm, int last)
2372 {
2373 struct lzh_dec *ds = strm->ds;
2374 struct lzh_br bre = ds->br;
2375 struct huffman *lt = &(ds->lt);
2376 struct huffman *pt = &(ds->pt);
2377 unsigned char *w_buff = ds->w_buff;
2378 unsigned char *lt_bitlen = lt->bitlen;
2379 unsigned char *pt_bitlen = pt->bitlen;
2380 int blocks_avail = ds->blocks_avail, c = 0;
2381 int copy_len = ds->copy_len, copy_pos = ds->copy_pos;
2382 int w_pos = ds->w_pos, w_mask = ds->w_mask, w_size = ds->w_size;
2383 int lt_max_bits = lt->max_bits, pt_max_bits = pt->max_bits;
2384 int state = ds->state;
2385
2386 for (;;) {
2387 switch (state) {
2388 case ST_GET_LITERAL:
2389 for (;;) {
2390 if (blocks_avail == 0) {
2391 /* We have decoded all blocks.
2392 * Let's handle next blocks. */
2393 ds->state = ST_RD_BLOCK;
2394 ds->br = bre;
2395 ds->blocks_avail = 0;
2396 ds->w_pos = w_pos;
2397 ds->copy_pos = 0;
2398 return (100);
2399 }
2400
2401 /* lzh_br_read_ahead() always tries to fill the
2402 * cache buffer up. In specific situation we
2403 * are close to the end of the data, the cache
2404 * buffer will not be full and thus we have to
2405 * determine if the cache buffer has some bits
2406 * as much as we need after lzh_br_read_ahead()
2407 * failed. */
2408 if (!lzh_br_read_ahead(strm, &bre,
2409 lt_max_bits)) {
2410 if (!last)
2411 goto next_data;
2412 /* Remaining bits are less than
2413 * maximum bits(lt.max_bits) but maybe
2414 * it still remains as much as we need,
2415 * so we should try to use it with
2416 * dummy bits. */
2417 c = lzh_decode_huffman(lt,
2418 lzh_br_bits_forced(&bre,
2419 lt_max_bits));
2420 lzh_br_consume(&bre, lt_bitlen[c]);
2421 if (!lzh_br_has(&bre, 0))
2422 goto failed;/* Over read. */
2423 } else {
2424 c = lzh_decode_huffman(lt,
2425 lzh_br_bits(&bre, lt_max_bits));
2426 lzh_br_consume(&bre, lt_bitlen[c]);
2427 }
2428 blocks_avail--;
2429 if ((unsigned int)c > UCHAR_MAX)
2430 /* Current block is a match data. */
2431 break;
2432 /*
2433 * 'c' is exactly a literal code.
2434 */
2435 /* Save a decoded code to reference it
2436 * afterward. */
2437 w_buff[w_pos] = c;
2438 if (++w_pos >= w_size) {
2439 w_pos = 0;
2440 lzh_emit_window(strm, w_size);
2441 goto next_data;
2442 }
2443 }
2444 /* 'c' is the length of a match pattern we have
2445 * already extracted, which has be stored in
2446 * window(ds->w_buff). */
2447 copy_len = c - (UCHAR_MAX + 1) + MINMATCH;
2448 /* FALL THROUGH */
2449 case ST_GET_POS_1:
2450 /*
2451 * Get a reference position.
2452 */
2453 if (!lzh_br_read_ahead(strm, &bre, pt_max_bits)) {
2454 if (!last) {
2455 state = ST_GET_POS_1;
2456 ds->copy_len = copy_len;
2457 goto next_data;
2458 }
2459 copy_pos = lzh_decode_huffman(pt,
2460 lzh_br_bits_forced(&bre, pt_max_bits));
2461 lzh_br_consume(&bre, pt_bitlen[copy_pos]);
2462 if (!lzh_br_has(&bre, 0))
2463 goto failed;/* Over read. */
2464 } else {
2465 copy_pos = lzh_decode_huffman(pt,
2466 lzh_br_bits(&bre, pt_max_bits));
2467 lzh_br_consume(&bre, pt_bitlen[copy_pos]);
2468 }
2469 /* FALL THROUGH */
2470 case ST_GET_POS_2:
2471 if (copy_pos > 1) {
2472 /* We need an additional adjustment number to
2473 * the position. */
2474 int p = copy_pos - 1;
2475 if (!lzh_br_read_ahead(strm, &bre, p)) {
2476 if (last)
2477 goto failed;/* Truncated data.*/
2478 state = ST_GET_POS_2;
2479 ds->copy_len = copy_len;
2480 ds->copy_pos = copy_pos;
2481 goto next_data;
2482 }
2483 copy_pos = (1 << p) + lzh_br_bits(&bre, p);
2484 lzh_br_consume(&bre, p);
2485 }
2486 /* The position is actually a distance from the last
2487 * code we had extracted and thus we have to convert
2488 * it to a position of the window. */
2489 copy_pos = (w_pos - copy_pos - 1) & w_mask;
2490 /* FALL THROUGH */
2491 case ST_COPY_DATA:
2492 /*
2493 * Copy `copy_len' bytes as extracted data from
2494 * the window into the output buffer.
2495 */
2496 for (;;) {
2497 int l;
2498
2499 l = copy_len;
2500 if (copy_pos > w_pos) {
2501 if (l > w_size - copy_pos)
2502 l = w_size - copy_pos;
2503 } else {
2504 if (l > w_size - w_pos)
2505 l = w_size - w_pos;
2506 }
2507 if ((copy_pos + l < w_pos)
2508 || (w_pos + l < copy_pos)) {
2509 /* No overlap. */
2510 memcpy(w_buff + w_pos,
2511 w_buff + copy_pos, l);
2512 } else {
2513 const unsigned char *s;
2514 unsigned char *d;
2515 int li;
2516
2517 d = w_buff + w_pos;
2518 s = w_buff + copy_pos;
2519 for (li = 0; li < l-1;) {
2520 d[li] = s[li];li++;
2521 d[li] = s[li];li++;
2522 }
2523 if (li < l)
2524 d[li] = s[li];
2525 }
2526 w_pos += l;
2527 if (w_pos == w_size) {
2528 w_pos = 0;
2529 lzh_emit_window(strm, w_size);
2530 if (copy_len <= l)
2531 state = ST_GET_LITERAL;
2532 else {
2533 state = ST_COPY_DATA;
2534 ds->copy_len = copy_len - l;
2535 ds->copy_pos =
2536 (copy_pos + l) & w_mask;
2537 }
2538 goto next_data;
2539 }
2540 if (copy_len <= l)
2541 /* A copy of current pattern ended. */
2542 break;
2543 copy_len -= l;
2544 copy_pos = (copy_pos + l) & w_mask;
2545 }
2546 state = ST_GET_LITERAL;
2547 break;
2548 }
2549 }
2550 failed:
2551 return (ds->error = ARCHIVE_FAILED);
2552 next_data:
2553 ds->br = bre;
2554 ds->blocks_avail = blocks_avail;
2555 ds->state = state;
2556 ds->w_pos = w_pos;
2557 return (ARCHIVE_OK);
2558 }
2559
2560 static int
lzh_huffman_init(struct huffman * hf,size_t len_size,int tbl_bits)2561 lzh_huffman_init(struct huffman *hf, size_t len_size, int tbl_bits)
2562 {
2563 int bits;
2564
2565 if (hf->bitlen == NULL) {
2566 hf->bitlen = malloc(len_size * sizeof(hf->bitlen[0]));
2567 if (hf->bitlen == NULL)
2568 return (ARCHIVE_FATAL);
2569 }
2570 if (hf->tbl == NULL) {
2571 if (tbl_bits < HTBL_BITS)
2572 bits = tbl_bits;
2573 else
2574 bits = HTBL_BITS;
2575 hf->tbl = malloc(((size_t)1 << bits) * sizeof(hf->tbl[0]));
2576 if (hf->tbl == NULL)
2577 return (ARCHIVE_FATAL);
2578 }
2579 if (hf->tree == NULL && tbl_bits > HTBL_BITS) {
2580 hf->tree_avail = 1 << (tbl_bits - HTBL_BITS + 4);
2581 hf->tree = malloc(hf->tree_avail * sizeof(hf->tree[0]));
2582 if (hf->tree == NULL)
2583 return (ARCHIVE_FATAL);
2584 }
2585 hf->len_size = (int)len_size;
2586 hf->tbl_bits = tbl_bits;
2587 return (ARCHIVE_OK);
2588 }
2589
2590 static void
lzh_huffman_free(struct huffman * hf)2591 lzh_huffman_free(struct huffman *hf)
2592 {
2593 free(hf->bitlen);
2594 free(hf->tbl);
2595 free(hf->tree);
2596 }
2597
2598 static const char bitlen_tbl[0x400] = {
2599 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2600 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2601 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2602 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2603 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2604 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2605 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2606 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2607 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2608 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2609 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2610 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2611 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2612 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2613 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2614 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2615 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2616 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2617 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2618 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2619 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2620 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2621 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2622 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2623 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2624 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2625 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2626 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2627 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2628 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2629 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2630 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2631 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2632 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2633 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2634 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2635 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2636 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2637 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2638 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2639 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2640 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2641 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2642 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2643 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2644 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2645 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2646 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2647 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
2648 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
2649 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
2650 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
2651 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
2652 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
2653 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
2654 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
2655 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2656 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2657 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2658 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2659 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2660 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2661 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
2662 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 16, 0
2663 };
2664 static int
lzh_read_pt_bitlen(struct lzh_stream * strm,int start,int end)2665 lzh_read_pt_bitlen(struct lzh_stream *strm, int start, int end)
2666 {
2667 struct lzh_dec *ds = strm->ds;
2668 struct lzh_br *br = &(ds->br);
2669 int c, i;
2670
2671 for (i = start; i < end; ) {
2672 /*
2673 * bit pattern the number we need
2674 * 000 -> 0
2675 * 001 -> 1
2676 * 010 -> 2
2677 * ...
2678 * 110 -> 6
2679 * 1110 -> 7
2680 * 11110 -> 8
2681 * ...
2682 * 1111111111110 -> 16
2683 */
2684 if (!lzh_br_read_ahead(strm, br, 3))
2685 return (i);
2686 if ((c = lzh_br_bits(br, 3)) == 7) {
2687 if (!lzh_br_read_ahead(strm, br, 13))
2688 return (i);
2689 c = bitlen_tbl[lzh_br_bits(br, 13) & 0x3FF];
2690 if (c)
2691 lzh_br_consume(br, c - 3);
2692 else
2693 return (-1);/* Invalid data. */
2694 } else
2695 lzh_br_consume(br, 3);
2696 ds->pt.bitlen[i++] = c;
2697 ds->pt.freq[c]++;
2698 }
2699 return (i);
2700 }
2701
2702 static int
lzh_make_fake_table(struct huffman * hf,uint16_t c)2703 lzh_make_fake_table(struct huffman *hf, uint16_t c)
2704 {
2705 if (c >= hf->len_size)
2706 return (0);
2707 hf->tbl[0] = c;
2708 hf->max_bits = 0;
2709 hf->shift_bits = 0;
2710 hf->bitlen[hf->tbl[0]] = 0;
2711 return (1);
2712 }
2713
2714 /*
2715 * Make a huffman coding table.
2716 */
2717 static int
lzh_make_huffman_table(struct huffman * hf)2718 lzh_make_huffman_table(struct huffman *hf)
2719 {
2720 uint16_t *tbl;
2721 const unsigned char *bitlen;
2722 int bitptn[17], weight[17];
2723 int i, maxbits = 0, ptn, tbl_size, w;
2724 int diffbits, len_avail;
2725
2726 /*
2727 * Initialize bit patterns.
2728 */
2729 ptn = 0;
2730 for (i = 1, w = 1 << 15; i <= 16; i++, w >>= 1) {
2731 bitptn[i] = ptn;
2732 weight[i] = w;
2733 if (hf->freq[i]) {
2734 ptn += hf->freq[i] * w;
2735 maxbits = i;
2736 }
2737 }
2738 if (ptn != 0x10000 || maxbits > hf->tbl_bits)
2739 return (0);/* Invalid */
2740
2741 hf->max_bits = maxbits;
2742
2743 /*
2744 * Cut out extra bits which we won't house in the table.
2745 * This preparation reduces the same calculation in the for-loop
2746 * making the table.
2747 */
2748 if (maxbits < 16) {
2749 int ebits = 16 - maxbits;
2750 for (i = 1; i <= maxbits; i++) {
2751 bitptn[i] >>= ebits;
2752 weight[i] >>= ebits;
2753 }
2754 }
2755 if (maxbits > HTBL_BITS) {
2756 unsigned htbl_max;
2757 uint16_t *p;
2758
2759 diffbits = maxbits - HTBL_BITS;
2760 for (i = 1; i <= HTBL_BITS; i++) {
2761 bitptn[i] >>= diffbits;
2762 weight[i] >>= diffbits;
2763 }
2764 htbl_max = bitptn[HTBL_BITS] +
2765 weight[HTBL_BITS] * hf->freq[HTBL_BITS];
2766 p = &(hf->tbl[htbl_max]);
2767 while (p < &hf->tbl[1U<<HTBL_BITS])
2768 *p++ = 0;
2769 } else
2770 diffbits = 0;
2771 hf->shift_bits = diffbits;
2772
2773 /*
2774 * Make the table.
2775 */
2776 tbl_size = 1 << HTBL_BITS;
2777 tbl = hf->tbl;
2778 bitlen = hf->bitlen;
2779 len_avail = hf->len_avail;
2780 hf->tree_used = 0;
2781 for (i = 0; i < len_avail; i++) {
2782 uint16_t *p;
2783 int len, cnt;
2784 uint16_t bit;
2785 int extlen;
2786 struct htree_t *ht;
2787
2788 if (bitlen[i] == 0)
2789 continue;
2790 /* Get a bit pattern */
2791 len = bitlen[i];
2792 ptn = bitptn[len];
2793 cnt = weight[len];
2794 if (len <= HTBL_BITS) {
2795 /* Calculate next bit pattern */
2796 if ((bitptn[len] = ptn + cnt) > tbl_size)
2797 return (0);/* Invalid */
2798 /* Update the table */
2799 p = &(tbl[ptn]);
2800 if (cnt > 7) {
2801 uint16_t *pc;
2802
2803 cnt -= 8;
2804 pc = &p[cnt];
2805 pc[0] = (uint16_t)i;
2806 pc[1] = (uint16_t)i;
2807 pc[2] = (uint16_t)i;
2808 pc[3] = (uint16_t)i;
2809 pc[4] = (uint16_t)i;
2810 pc[5] = (uint16_t)i;
2811 pc[6] = (uint16_t)i;
2812 pc[7] = (uint16_t)i;
2813 if (cnt > 7) {
2814 cnt -= 8;
2815 memcpy(&p[cnt], pc,
2816 8 * sizeof(uint16_t));
2817 pc = &p[cnt];
2818 while (cnt > 15) {
2819 cnt -= 16;
2820 memcpy(&p[cnt], pc,
2821 16 * sizeof(uint16_t));
2822 }
2823 }
2824 if (cnt)
2825 memcpy(p, pc, cnt * sizeof(uint16_t));
2826 } else {
2827 while (cnt > 1) {
2828 p[--cnt] = (uint16_t)i;
2829 p[--cnt] = (uint16_t)i;
2830 }
2831 if (cnt)
2832 p[--cnt] = (uint16_t)i;
2833 }
2834 continue;
2835 }
2836
2837 /*
2838 * A bit length is too big to be housed to a direct table,
2839 * so we use a tree model for its extra bits.
2840 */
2841 bitptn[len] = ptn + cnt;
2842 bit = 1U << (diffbits -1);
2843 extlen = len - HTBL_BITS;
2844
2845 p = &(tbl[ptn >> diffbits]);
2846 if (*p == 0) {
2847 *p = len_avail + hf->tree_used;
2848 ht = &(hf->tree[hf->tree_used++]);
2849 if (hf->tree_used > hf->tree_avail)
2850 return (0);/* Invalid */
2851 ht->left = 0;
2852 ht->right = 0;
2853 } else {
2854 if (*p < len_avail ||
2855 *p >= (len_avail + hf->tree_used))
2856 return (0);/* Invalid */
2857 ht = &(hf->tree[*p - len_avail]);
2858 }
2859 while (--extlen > 0) {
2860 if (ptn & bit) {
2861 if (ht->left < len_avail) {
2862 ht->left = len_avail + hf->tree_used;
2863 ht = &(hf->tree[hf->tree_used++]);
2864 if (hf->tree_used > hf->tree_avail)
2865 return (0);/* Invalid */
2866 ht->left = 0;
2867 ht->right = 0;
2868 } else {
2869 ht = &(hf->tree[ht->left - len_avail]);
2870 }
2871 } else {
2872 if (ht->right < len_avail) {
2873 ht->right = len_avail + hf->tree_used;
2874 ht = &(hf->tree[hf->tree_used++]);
2875 if (hf->tree_used > hf->tree_avail)
2876 return (0);/* Invalid */
2877 ht->left = 0;
2878 ht->right = 0;
2879 } else {
2880 ht = &(hf->tree[ht->right - len_avail]);
2881 }
2882 }
2883 bit >>= 1;
2884 }
2885 if (ptn & bit) {
2886 if (ht->left != 0)
2887 return (0);/* Invalid */
2888 ht->left = (uint16_t)i;
2889 } else {
2890 if (ht->right != 0)
2891 return (0);/* Invalid */
2892 ht->right = (uint16_t)i;
2893 }
2894 }
2895 return (1);
2896 }
2897
2898 static int
lzh_decode_huffman_tree(struct huffman * hf,unsigned rbits,int c)2899 lzh_decode_huffman_tree(struct huffman *hf, unsigned rbits, int c)
2900 {
2901 struct htree_t *ht;
2902 int extlen;
2903
2904 ht = hf->tree;
2905 extlen = hf->shift_bits;
2906 while (c >= hf->len_avail) {
2907 c -= hf->len_avail;
2908 if (extlen-- <= 0 || c >= hf->tree_used)
2909 return (0);
2910 if (rbits & (1U << extlen))
2911 c = ht[c].left;
2912 else
2913 c = ht[c].right;
2914 }
2915 return (c);
2916 }
2917
2918 static inline int
lzh_decode_huffman(struct huffman * hf,unsigned rbits)2919 lzh_decode_huffman(struct huffman *hf, unsigned rbits)
2920 {
2921 int c;
2922 /*
2923 * At first search an index table for a bit pattern.
2924 * If it fails, search a huffman tree for.
2925 */
2926 c = hf->tbl[rbits >> hf->shift_bits];
2927 if (c < hf->len_avail || hf->len_avail == 0)
2928 return (c);
2929 /* This bit pattern needs to be found out at a huffman tree. */
2930 return (lzh_decode_huffman_tree(hf, rbits, c));
2931 }
2932