blob: fb83383c2048e246b4de65cf0daf1fe90d3e9563 [file] [log] [blame]
Luc Verhaegen462b7762009-06-10 16:56:26 +02001/*
2 * This file is a severely cut down and cleaned up version of lha.
3 *
4 * All changes compared to lha-svn894 are:
5 *
6 * Copyright 2009 Luc Verhaegen <libv@skynet.be>
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2, or (at your option)
11 * any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; see the file COPYING. If not, write to
20 * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
21 */
22/*
23 * LHA has a terrible history... It dates back to 1988, has had many different
24 * authors and has been mostly Public Domain Software.
25 *
26 * Since 1999, Koji Arai <arai@users.sourceforge.jp> has been doing most of
27 * the work at http://sourceforge.jp/projects/lha/.
28 */
29
Luc Verhaegen2e424062009-06-16 08:02:13 +020030#define _GNU_SOURCE 1
31
Luc Verhaegen462b7762009-06-10 16:56:26 +020032#include <stdio.h>
Luc Verhaegen462b7762009-06-10 16:56:26 +020033#include <string.h>
34#include <stdlib.h>
Stefan Reinauer6ed57e52010-04-24 01:15:17 +020035#include "compat.h"
Luc Verhaegen1646a412009-06-16 08:22:14 +020036#include "lh5_extract.h"
Luc Verhaegen462b7762009-06-10 16:56:26 +020037
Luc Verhaegen462b7762009-06-10 16:56:26 +020038/*
39 *
40 * LHA header parsing.
41 *
42 */
Luc Verhaegen462b7762009-06-10 16:56:26 +020043static int
44calc_sum(unsigned char *p, int len)
45{
46 int sum = 0;
47
48 while (len--)
49 sum += *p++;
50
51 return sum & 0xff;
52}
53
Luc Verhaegen462b7762009-06-10 16:56:26 +020054/*
55 * level 1 header
56 *
57 *
58 * offset size field name
59 * -----------------------------------
60 * 0 1 header size [*1]
61 * 1 1 header sum
62 * -------------------------------------
63 * 2 5 method ID ^
64 * 7 4 skip size [*2] |
65 * 11 4 original size |
66 * 15 2 time |
67 * 17 2 date |
68 * 19 1 attribute (0x20 fixed) | [*1] header size (X+Y+25)
69 * 20 1 level (0x01 fixed) |
70 * 21 1 name length |
71 * 22 X filename |
72 * X+ 22 2 file crc (CRC-16) |
73 * X+ 24 1 OS ID |
74 * X +25 Y ??? |
75 * X+Y+25 2 next-header size v
76 * -------------------------------------------------
77 * X+Y+27 Z ext-header ^
78 * : |
79 * ----------------------------------- | [*2] skip size
80 * X+Y+Z+27 data |
81 * : v
82 * -------------------------------------------------
83 *
84 */
Luc Verhaegen1646a412009-06-16 08:22:14 +020085unsigned int
Luc Verhaegen2e424062009-06-16 08:02:13 +020086LH5HeaderParse(unsigned char *Buffer, int BufferSize,
87 unsigned int *original_size, unsigned int *packed_size,
88 char **name, unsigned short *crc)
Luc Verhaegen462b7762009-06-10 16:56:26 +020089{
Luc Verhaegen462b7762009-06-10 16:56:26 +020090 unsigned int offset;
91 unsigned char header_size, checksum, name_length;
Luc Verhaegen462b7762009-06-10 16:56:26 +020092
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +020093 if (BufferSize < 27) {
94 fprintf(stderr, "Error: Packed Buffer is too small to contain an lha "
95 "header.\n");
96 return 0;
Luc Verhaegen462b7762009-06-10 16:56:26 +020097 }
98
99 /* check attribute */
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200100 if (Buffer[19] != 0x20) {
Luc Verhaegen462b7762009-06-10 16:56:26 +0200101 fprintf(stderr, "Error: Invalid lha header attribute byte.\n");
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200102 return 0;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200103 }
104
105 /* check method */
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200106 if (memcmp(Buffer + 2, "-lh5-", 5) != 0) {
Luc Verhaegen462b7762009-06-10 16:56:26 +0200107 fprintf(stderr, "Error: Compression method is not LZHUFF5.\n");
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200108 return 0;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200109 }
110
111 /* check header level */
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200112 if (Buffer[20] != 1) {
113 fprintf(stderr, "Error: Header level %d is not supported\n", Buffer[20]);
114 return 0;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200115 }
116
117 /* read in the full header */
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200118 header_size = Buffer[0];
119 if (BufferSize < (header_size + 2)) {
120 fprintf(stderr, "Error: Packed Buffer is too small to contain the"
121 " full header.\n");
122 return 0;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200123 }
124
125 /* verify checksum */
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200126 checksum = Buffer[1];
127 if (calc_sum(Buffer + 2, header_size) != checksum) {
Luc Verhaegen462b7762009-06-10 16:56:26 +0200128 fprintf(stderr, "Error: Invalid lha header checksum.\n");
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200129 return 0;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200130 }
131
Peter Lemenkovfec24c92009-07-23 23:46:34 +0400132 *packed_size = le32toh(*(unsigned int *) (Buffer + 7));
133 *original_size = le32toh(*(unsigned int *) (Buffer + 11));
Luc Verhaegen462b7762009-06-10 16:56:26 +0200134
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200135 name_length = Buffer[21];
Luc Verhaegen2e424062009-06-16 08:02:13 +0200136 *name = strndup((char *) Buffer + 22, name_length);
Luc Verhaegen462b7762009-06-10 16:56:26 +0200137
Peter Lemenkovfec24c92009-07-23 23:46:34 +0400138 *crc = le16toh(*(unsigned short *) (Buffer + 22 + name_length));
Luc Verhaegen462b7762009-06-10 16:56:26 +0200139
140 offset = header_size + 2;
141 /* Skip extended headers */
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200142 while (1) {
Peter Lemenkovfec24c92009-07-23 23:46:34 +0400143 unsigned short extend_size = le16toh(*(unsigned short *) (Buffer + offset - 2));
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200144
145 if (!extend_size)
146 break;
147
Luc Verhaegen462b7762009-06-10 16:56:26 +0200148 *packed_size -= extend_size;
149 offset += extend_size;
150
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200151 if (BufferSize < offset) {
152 fprintf(stderr, "Error: Buffer to small to contain extended "
153 "header.\n");
154 return 0;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200155 }
Luc Verhaegen462b7762009-06-10 16:56:26 +0200156 }
157
158 return offset;
159}
160
161/*
Luc Verhaegen12c87162009-06-11 14:07:17 +0200162 * CRC Calculation.
Luc Verhaegen462b7762009-06-10 16:56:26 +0200163 */
Luc Verhaegen12c87162009-06-11 14:07:17 +0200164unsigned short
165CRC16Calculate(unsigned char *Buffer, int BufferSize)
Luc Verhaegen462b7762009-06-10 16:56:26 +0200166{
Luc Verhaegen12c87162009-06-11 14:07:17 +0200167#define CRCPOLY 0xA001 /* CRC-16 (x^16+x^15+x^2+1) */
168 unsigned short CRCTable[0x100];
169 unsigned short crc;
170 int i;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200171
Luc Verhaegen12c87162009-06-11 14:07:17 +0200172 /* First, initialise our CRCTable */
173 for (i = 0; i < 0x100; i++) {
174 unsigned short r = i;
175 unsigned int j;
176
177 for (j = 0; j < 8; j++) {
Luc Verhaegen462b7762009-06-10 16:56:26 +0200178 if (r & 1)
179 r = (r >> 1) ^ CRCPOLY;
180 else
181 r >>= 1;
Luc Verhaegen12c87162009-06-11 14:07:17 +0200182 }
183 CRCTable[i] = r;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200184 }
Luc Verhaegen462b7762009-06-10 16:56:26 +0200185
Luc Verhaegen12c87162009-06-11 14:07:17 +0200186 /* now go over the entire Buffer */
187 crc = 0;
188 for (i = 0; i < BufferSize; i++)
189 crc = CRCTable[(crc ^ Buffer[i]) & 0xFF] ^ (crc >> 8);
Luc Verhaegen462b7762009-06-10 16:56:26 +0200190
191 return crc;
192}
193
194/*
195 *
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200196 * Bit handling code.
Luc Verhaegen462b7762009-06-10 16:56:26 +0200197 *
198 */
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200199static unsigned char *CompressedBuffer;
200static int CompressedSize;
201static int CompressedOffset;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200202
203static unsigned short bitbuf;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200204static unsigned char subbitbuf, bitcount;
205
206static void
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200207BitBufInit(unsigned char *Buffer, int BufferSize)
208{
209 CompressedBuffer = Buffer;
210 CompressedOffset = 0;
211 CompressedSize = BufferSize;
212
213 bitbuf = 0;
214 subbitbuf = 0;
215 bitcount = 0;
216}
217
218static void
219fillbuf(unsigned char n) /* Shift bitbuf n bits left, read n bits */
Luc Verhaegen462b7762009-06-10 16:56:26 +0200220{
221 while (n > bitcount) {
222 n -= bitcount;
223 bitbuf = (bitbuf << bitcount) + (subbitbuf >> (8 - bitcount));
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200224
225
226 if (CompressedOffset < CompressedSize) {
227 subbitbuf = CompressedBuffer[CompressedOffset];
228 CompressedOffset++;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200229 } else
230 subbitbuf = 0;
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200231
Luc Verhaegen462b7762009-06-10 16:56:26 +0200232 bitcount = 8;
233 }
234 bitcount -= n;
235 bitbuf = (bitbuf << n) + (subbitbuf >> (8 - n));
236 subbitbuf <<= n;
237}
238
239static unsigned short
240getbits(unsigned char n)
241{
242 unsigned short x;
243
244 x = bitbuf >> (16 - n);
245 fillbuf(n);
246
247 return x;
248}
249
250static unsigned short
251peekbits(unsigned char n)
252{
253 unsigned short x;
254
255 x = bitbuf >> (16 - n);
256
257 return x;
258}
259
Luc Verhaegenc8aa2a72009-06-11 04:28:46 +0200260/*
261 *
262 * LHA extraction.
263 *
264 */
265#define MIN(a,b) ((a) <= (b) ? (a) : (b))
266
267#define LZHUFF5_DICBIT 13 /* 2^13 = 8KB sliding dictionary */
268#define MAXMATCH 256 /* formerly F (not more than 255 + 1) */
269#define THRESHOLD 3 /* choose optimal value */
270#define NP (LZHUFF5_DICBIT + 1)
271#define NT (16 + 3) /* USHORT + THRESHOLD */
272#define NC (255 + MAXMATCH + 2 - THRESHOLD)
273
274#define PBIT 4 /* smallest integer such that (1 << PBIT) > * NP */
275#define TBIT 5 /* smallest integer such that (1 << TBIT) > * NT */
276#define CBIT 9 /* smallest integer such that (1 << CBIT) > * NC */
277
278/* #if NT > NP #define NPT NT #else #define NPT NP #endif */
279#define NPT 0x80
280
281static unsigned short left[2 * NC - 1], right[2 * NC - 1];
282
283static unsigned short c_table[4096]; /* decode */
284static unsigned short pt_table[256]; /* decode */
285
286static unsigned char c_len[NC];
287static unsigned char pt_len[NPT];
288
Luc Verhaegen462b7762009-06-10 16:56:26 +0200289static void
290make_table(short nchar, unsigned char bitlen[], short tablebits, unsigned short table[])
291{
292 unsigned short count[17]; /* count of bitlen */
293 unsigned short weight[17]; /* 0x10000ul >> bitlen */
294 unsigned short start[17]; /* first code of bitlen */
295 unsigned short total;
296 unsigned int i, l;
297 int j, k, m, n, avail;
298 unsigned short *p;
299
300 avail = nchar;
301
302 /* initialize */
303 for (i = 1; i <= 16; i++) {
304 count[i] = 0;
305 weight[i] = 1 << (16 - i);
306 }
307
308 /* count */
309 for (i = 0; i < nchar; i++) {
310 if (bitlen[i] > 16) {
311 /* CVE-2006-4335 */
312 fprintf(stderr, "Error: Bad table (case a)");
313 exit(1);
314 }
315 else
316 count[bitlen[i]]++;
317 }
318
319 /* calculate first code */
320 total = 0;
321 for (i = 1; i <= 16; i++) {
322 start[i] = total;
323 total += weight[i] * count[i];
324 }
325 if ((total & 0xffff) != 0 || tablebits > 16) { /* 16 for weight below */
326 fprintf(stderr, "Error: make_table(): Bad table (case b)");
327 exit(1);
328 }
329
330 /* shift data for make table. */
331 m = 16 - tablebits;
332 for (i = 1; i <= tablebits; i++) {
333 start[i] >>= m;
334 weight[i] >>= m;
335 }
336
337 /* initialize */
338 j = start[tablebits + 1] >> m;
339 k = MIN(1 << tablebits, 4096);
340 if (j != 0)
341 for (i = j; i < k; i++)
342 table[i] = 0;
343
344 /* create table and tree */
345 for (j = 0; j < nchar; j++) {
346 k = bitlen[j];
347 if (k == 0)
348 continue;
349 l = start[k] + weight[k];
350 if (k <= tablebits) {
351 /* code in table */
352 l = MIN(l, 4096);
353 for (i = start[k]; i < l; i++)
354 table[i] = j;
355 }
356 else {
357 /* code not in table */
358 i = start[k];
359 if ((i >> m) > 4096) {
360 /* CVE-2006-4337 */
361 fprintf(stderr, "Error: Bad table (case c)");
362 exit(1);
363 }
364 p = &table[i >> m];
365 i <<= tablebits;
366 n = k - tablebits;
367 /* make tree (n length) */
368 while (--n >= 0) {
369 if (*p == 0) {
370 right[avail] = left[avail] = 0;
371 *p = avail++;
372 }
373 if (i & 0x8000)
374 p = &right[*p];
375 else
376 p = &left[*p];
377 i <<= 1;
378 }
379 *p = j;
380 }
381 start[k] = l;
382 }
383}
384
385static void
386read_pt_len(short nn, short nbit, short i_special)
387{
388 int i, c, n;
389
390 n = getbits(nbit);
391 if (n == 0) {
392 c = getbits(nbit);
393 for (i = 0; i < nn; i++)
394 pt_len[i] = 0;
395 for (i = 0; i < 256; i++)
396 pt_table[i] = c;
397 }
398 else {
399 i = 0;
400 while (i < MIN(n, NPT)) {
401 c = peekbits(3);
402 if (c != 7)
403 fillbuf(3);
404 else {
405 unsigned short mask = 1 << (16 - 4);
406 while (mask & bitbuf) {
407 mask >>= 1;
408 c++;
409 }
410 fillbuf(c - 3);
411 }
412
413 pt_len[i++] = c;
414 if (i == i_special) {
415 c = getbits(2);
416 while (--c >= 0 && i < NPT)
417 pt_len[i++] = 0;
418 }
419 }
420 while (i < nn)
421 pt_len[i++] = 0;
422 make_table(nn, pt_len, 8, pt_table);
423 }
424}
425
426static void
427read_c_len(void)
428{
429 short i, c, n;
430
431 n = getbits(CBIT);
432 if (n == 0) {
433 c = getbits(CBIT);
434 for (i = 0; i < NC; i++)
435 c_len[i] = 0;
436 for (i = 0; i < 4096; i++)
437 c_table[i] = c;
438 } else {
439 i = 0;
440 while (i < MIN(n,NC)) {
441 c = pt_table[peekbits(8)];
442 if (c >= NT) {
443 unsigned short mask = 1 << (16 - 9);
444 do {
445 if (bitbuf & mask)
446 c = right[c];
447 else
448 c = left[c];
449 mask >>= 1;
450 } while (c >= NT && (mask || c != left[c])); /* CVE-2006-4338 */
451 }
452 fillbuf(pt_len[c]);
453 if (c <= 2) {
454 if (c == 0)
455 c = 1;
456 else if (c == 1)
457 c = getbits(4) + 3;
458 else
459 c = getbits(CBIT) + 20;
460 while (--c >= 0)
461 c_len[i++] = 0;
462 }
463 else
464 c_len[i++] = c - 2;
465 }
466 while (i < NC)
467 c_len[i++] = 0;
468 make_table(NC, c_len, 12, c_table);
469 }
470}
471
472static unsigned short
473decode_c_st1(void)
474{
475 unsigned short j, mask;
476
477 j = c_table[peekbits(12)];
478 if (j < NC)
479 fillbuf(c_len[j]);
480 else {
481 fillbuf(12);
482 mask = 1 << (16 - 1);
483 do {
484 if (bitbuf & mask)
485 j = right[j];
486 else
487 j = left[j];
488 mask >>= 1;
489 } while (j >= NC && (mask || j != left[j])); /* CVE-2006-4338 */
490 fillbuf(c_len[j] - 12);
491 }
492 return j;
493}
494
495static unsigned short
496decode_p_st1(void)
497{
498 unsigned short j, mask;
499
500 j = pt_table[peekbits(8)];
501 if (j < NP)
502 fillbuf(pt_len[j]);
503 else {
504 fillbuf(8);
505 mask = 1 << (16 - 1);
506 do {
507 if (bitbuf & mask)
508 j = right[j];
509 else
510 j = left[j];
511 mask >>= 1;
512 } while (j >= NP && (mask || j != left[j])); /* CVE-2006-4338 */
513 fillbuf(pt_len[j] - 8);
514 }
515 if (j != 0)
516 j = (1 << (j - 1)) + getbits(j - 1);
517 return j;
518}
519
Luc Verhaegen1646a412009-06-16 08:22:14 +0200520void
Luc Verhaegen9af97842009-06-11 14:28:33 +0200521LH5Decode(unsigned char *PackedBuffer, int PackedBufferSize,
Luc Verhaegenb8941802009-06-15 20:31:11 +0200522 unsigned char *OutputBuffer, int OutputBufferSize)
Luc Verhaegen462b7762009-06-10 16:56:26 +0200523{
524 unsigned short blocksize = 0;
525 unsigned int i, c;
Luc Verhaegenb8941802009-06-15 20:31:11 +0200526 int n = 0;
Luc Verhaegen462b7762009-06-10 16:56:26 +0200527
Luc Verhaegen9af97842009-06-11 14:28:33 +0200528 BitBufInit(PackedBuffer, PackedBufferSize);
Luc Verhaegen462b7762009-06-10 16:56:26 +0200529 fillbuf(2 * 8);
530
Luc Verhaegenb8941802009-06-15 20:31:11 +0200531 while (n < OutputBufferSize) {
Luc Verhaegen462b7762009-06-10 16:56:26 +0200532 if (blocksize == 0) {
533 blocksize = getbits(16);
534 read_pt_len(NT, TBIT, 3);
535 read_c_len();
536 read_pt_len(NP, PBIT, -1);
537 }
538 blocksize--;
539
540 c = decode_c_st1();
541
Luc Verhaegenb8941802009-06-15 20:31:11 +0200542 if (c < 256)
543 OutputBuffer[n++] = c;
544 else {
545 int length = c - 256 + THRESHOLD;
546 int offset = 1 + decode_p_st1();
Luc Verhaegen462b7762009-06-10 16:56:26 +0200547
Luc Verhaegenb8941802009-06-15 20:31:11 +0200548 for (i = 0; i < length; i++) {
549 OutputBuffer[n] = OutputBuffer[n - offset];
550 n++;
551 }
Luc Verhaegen462b7762009-06-10 16:56:26 +0200552 }
553 }
Luc Verhaegen462b7762009-06-10 16:56:26 +0200554}