1 /* $Id: LhA.c,v 1.16 2010/05/27 16:48:30 stoecker Exp $
2 LhA file archiver client
3
4 XAD library system for archive handling
5 Copyright (C) 1998 and later by Dirk Stoecker <soft@dstoecker.de>
6
7 This library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public
9 License as published by the Free Software Foundation; either
10 version 2.1 of the License, or (at your option) any later version.
11
12 This library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Lesser General Public License for more details.
16
17 You should have received a copy of the GNU Lesser General Public
18 License along with this library; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21
22 /*
23 Modified for xmp by Claudio Matsuoka, 20120812
24 */
25
26 #include "common.h"
27 #include "depacker.h"
28
29 #define LZHUFF0_METHOD 0x2D6C6830 /* -lh0- */
30 #define LZHUFF1_METHOD 0x2D6C6831 /* -lh1- */
31 #define LZHUFF2_METHOD 0x2D6C6832 /* -lh2- */
32 #define LZHUFF3_METHOD 0x2D6C6833 /* -lh3- */
33 #define LZHUFF4_METHOD 0x2D6C6834 /* -lh4- */
34 #define LZHUFF5_METHOD 0x2D6C6835 /* -lh5- */
35 #define LZHUFF6_METHOD 0x2D6C6836 /* -lh6- */
36 #define LZHUFF7_METHOD 0x2D6C6837 /* -lh7- */
37 #define LZHUFF8_METHOD 0x2D6C6838 /* -lh8- */
38 #define LARC_METHOD 0x2D6C7A73 /* -lzs- */
39 #define LARC5_METHOD 0x2D6C7A35 /* -lz5- */
40 #define LARC4_METHOD 0x2D6C7A34 /* -lz4- */
41 #define PMARC0_METHOD 0x2D706D30 /* -pm0- */
42 #define PMARC2_METHOD 0x2D706D32 /* -pm2- */
43
44 #undef UCHAR_MAX
45 #define UCHAR_MAX ((1<<(sizeof(uint8)*8))-1)
46 #define MAX_DICBIT 16
47 #undef CHAR_BIT
48 #define CHAR_BIT 8
49 #define USHRT_BIT 16 /* (CHAR_BIT * sizeof(ushort)) */
50 #define MAXMATCH 256 /* not more than UCHAR_MAX + 1 */
51 #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
52 #define THRESHOLD 3 /* choose optimal value */
53 #define NPT 0x80
54 #define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */
55 #define TBIT 5 /* smallest integer such that (1 << TBIT) > * NT */
56 #define NT (USHRT_BIT + 3)
57 #define N_CHAR (256 + 60 - THRESHOLD + 1)
58 #define TREESIZE_C (N_CHAR * 2)
59 #define TREESIZE_P (128 * 2)
60 #define TREESIZE (TREESIZE_C + TREESIZE_P)
61 #define ROOT_C 0
62 #define ROOT_P TREESIZE_C
63 #define N1 286 /* alphabet size */
64 #define EXTRABITS 8 /* >= log2(F-THRESHOLD+258-N1) */
65 #define BUFBITS 16 /* >= log2(MAXBUF) */
66 #define NP (MAX_DICBIT + 1)
67 #define LENFIELD 4 /* bit size of length field for tree output */
68 #define MAGIC0 18
69 #define MAGIC5 19
70
71 #ifdef ENABLE_PMARC
72 #define PMARC2_OFFSET (0x100 - 2)
73 struct PMARC2_Tree {
74 uint8 *leftarr;
75 uint8 *rightarr;
76 uint8 root;
77 };
78 #endif
79
80 struct LhADecrST {
81 int32 pbit;
82 int32 np;
83 int32 nn;
84 int32 n1;
85 int32 most_p;
86 int32 avail;
87 uint32 n_max;
88 uint16 maxmatch;
89 uint16 total_p;
90 uint16 blocksize;
91 uint16 c_table[4096];
92 uint16 pt_table[256];
93 uint16 left[2 * NC - 1];
94 uint16 right[2 * NC - 1];
95 uint16 freq[TREESIZE];
96 uint16 pt_code[NPT];
97 int16 child[TREESIZE];
98 int16 stock[TREESIZE];
99 int16 s_node[TREESIZE / 2];
100 int16 block[TREESIZE];
101 int16 parent[TREESIZE];
102 int16 edge[TREESIZE];
103 uint8 c_len[NC];
104 uint8 pt_len[NPT];
105 };
106
107 #ifdef ENABLE_PMARC
108 struct LhADecrPM {
109 struct PMARC2_Tree tree1;
110 struct PMARC2_Tree tree2;
111
112 uint16 lastupdate;
113 uint16 dicsiz1;
114 uint8 gettree1;
115 uint8 tree1left[32];
116 uint8 tree1right[32];
117 uint8 table1[32];
118
119 uint8 tree2left[8];
120 uint8 tree2right[8];
121 uint8 table2[8];
122
123 uint8 tree1bound;
124 uint8 mindepth;
125
126 /* Circular double-linked list. */
127 uint8 prev[0x100];
128 uint8 next[0x100];
129 uint8 parentarr[0x100];
130 uint8 lastbyte;
131 };
132 #endif
133
134 #ifdef ENABLE_LARC
135 struct LhADecrLZ {
136 int32 matchpos; /* LARC */
137 int32 flag; /* LARC */
138 int32 flagcnt; /* LARC */
139 };
140 #endif
141
142 struct LhADecrData {
143 int error;
144 FILE *in;
145 char *text;
146 uint16 DicBit;
147
148 uint16 bitbuf;
149 uint8 subbitbuf;
150 uint8 bitcount;
151 uint32 loc;
152 uint32 count;
153 uint32 nextcount;
154
155 union {
156 struct LhADecrST st;
157 #ifdef ENABLE_PMARC
158 struct LhADecrPM pm;
159 #endif
160 #ifdef ENABLE_LARC
161 struct LhADecrLZ lz;
162 #endif
163 } d;
164 };
165
166 /* Shift bitbuf n bits left, read n bits */
fillbuf(struct LhADecrData * dat,uint8 n)167 static inline void fillbuf(struct LhADecrData *dat, uint8 n)
168 {
169 #if 0
170 if(dat->error)
171 return;
172 #endif
173
174 while(n > dat->bitcount)
175 {
176 n -= dat->bitcount;
177 dat->bitbuf = (dat->bitbuf << dat->bitcount) + (dat->subbitbuf >> (CHAR_BIT - dat->bitcount));
178 dat->subbitbuf = fgetc(dat->in);
179
180 dat->bitcount = CHAR_BIT;
181 }
182 dat->bitcount -= n;
183 dat->bitbuf = (dat->bitbuf << n) + (dat->subbitbuf >> (CHAR_BIT - n));
184 dat->subbitbuf <<= n;
185 }
186
getbits(struct LhADecrData * dat,uint8 n)187 static inline uint16 getbits(struct LhADecrData *dat, uint8 n)
188 {
189 uint16 x;
190
191 x = dat->bitbuf >> (2 * CHAR_BIT - n);
192 fillbuf(dat, n);
193 return x;
194 }
195
196 //#define init_getbits(a) fillbuf((a), 2* CHAR_BIT)
197 /* this function can be replaced by a define! */
init_getbits(struct LhADecrData * dat)198 static void init_getbits(struct LhADecrData *dat)
199 {
200 dat->bitbuf = 0;
201 dat->subbitbuf = 0;
202 dat->bitcount = 0;
203 fillbuf(dat, 2 * CHAR_BIT);
204 }
205
206
207 /* ------------------------------------------------------------------------ */
208
make_table(struct LhADecrData * dat,int16 nchar,uint8 bitlen[],int16 tablebits,uint16 table[],int table_size)209 static int make_table(struct LhADecrData *dat, int16 nchar, uint8 bitlen[], int16 tablebits, uint16 table[], int table_size)
210 {
211 uint16 count[17]; /* count of bitlen */
212 uint16 weight[17]; /* 0x10000ul >> bitlen */
213 uint16 start[17]; /* first code of bitlen */
214 uint16 total;
215 uint32 i;
216 int32 j, k, l, m, n, avail;
217 uint16 *p;
218
219 #if 0
220 if(dat->error)
221 return;
222 #endif
223
224 avail = nchar;
225
226 memset(count, 0, 17*2);
227 for(i = 1; i <= 16; i++)
228 weight[i] = 1 << (16 - i);
229
230 /* count */
231 for(i = 0; i < nchar; i++)
232 {
233 if(bitlen[i] >= ARRAY_SIZE(count))
234 return -1;
235 count[bitlen[i]]++;
236 }
237
238 /* calculate first code */
239 total = 0;
240 for(i = 1; i <= 16; i++)
241 {
242 start[i] = total;
243 total += weight[i] * count[i];
244 }
245 if(total & 0xFFFF)
246 {
247 dat->error = 1;
248 return -1;
249 }
250
251 /* shift data for make table. */
252 m = 16 - tablebits;
253 for(i = 1; i <= tablebits; i++) {
254 start[i] >>= m;
255 weight[i] >>= m;
256 }
257
258 /* initialize */
259 j = start[tablebits + 1] >> m;
260 k = 1 << tablebits;
261 if(j != 0) {
262
263 /* Sanity check */
264 if (k > table_size) {
265 return -1;
266 }
267
268 for(i = j; i < k; i++)
269 table[i] = 0;
270 }
271
272 /* create table and tree */
273 for(j = 0; j < nchar; j++)
274 {
275 k = bitlen[j];
276
277 /* Sanity check */
278 if(k >= 17)
279 return -1;
280
281 if(k == 0)
282 continue;
283 l = start[k] + weight[k];
284
285 if(k <= tablebits)
286 {
287 /* Sanity check */
288 if (l > table_size) {
289 return -1;
290 }
291
292 /* code in table */
293 for(i = start[k]; i < l; i++)
294 table[i] = j;
295 }
296 else
297 {
298 #if 0
299 /* CID 156018 (#1 of 1): Logically dead code (DEADCODE)
300 * dead_error_line: Execution cannot reach this statement: return -1;
301 */
302 /* Sanity check */
303 if(k >= 17)
304 return -1;
305 #endif
306
307 /* code not in table */
308 i = start[k];
309 p = &table[i >> m];
310 i <<= tablebits;
311 n = k - tablebits;
312 /* make tree (n length) */
313 while(--n >= 0)
314 {
315 if(*p == 0)
316 {
317 dat->d.st.right[avail] = dat->d.st.left[avail] = 0;
318 *p = avail++;
319 }
320 if(i & 0x8000)
321 p = &dat->d.st.right[*p];
322 else
323 p = &dat->d.st.left[*p];
324 i <<= 1;
325 }
326 *p = j;
327 }
328 start[k] = l;
329 }
330
331 return 0;
332 }
333
334 /* ------------------------------------------------------------------------ */
335
read_pt_len(struct LhADecrData * dat,int16 nn,int16 nbit,int16 i_special)336 static int read_pt_len(struct LhADecrData *dat, int16 nn, int16 nbit, int16 i_special)
337 {
338 int16 i, c, n;
339
340 if(!(n = getbits(dat, nbit)))
341 {
342 c = getbits(dat, nbit);
343 for(i = 0; i < nn; i++)
344 dat->d.st.pt_len[i] = 0;
345 for(i = 0; i < 256; i++)
346 dat->d.st.pt_table[i] = c;
347 }
348 else
349 {
350 i = 0;
351 while(i < n)
352 {
353 c = dat->bitbuf >> (16 - 3);
354 if(c == 7)
355 {
356 uint16 mask;
357
358 mask = 1 << (16 - 4);
359 while(mask & dat->bitbuf)
360 {
361 mask >>= 1;
362 c++;
363 }
364 }
365 fillbuf(dat, (c < 7) ? 3 : c - 3);
366 dat->d.st.pt_len[i++] = c;
367 if(i == i_special)
368 {
369 c = getbits(dat, 2);
370 while(--c >= 0)
371 dat->d.st.pt_len[i++] = 0;
372 }
373 }
374 while(i < nn)
375 dat->d.st.pt_len[i++] = 0;
376 if (make_table(dat, nn, dat->d.st.pt_len, 8, dat->d.st.pt_table, 256) < 0)
377 return -1;
378 }
379
380 return 0;
381 }
382
read_c_len(struct LhADecrData * dat)383 static int read_c_len(struct LhADecrData *dat)
384 {
385 int16 i, c, n;
386
387 if(!(n = getbits(dat, CBIT)))
388 {
389 c = getbits(dat, CBIT);
390 for(i = 0; i < NC; i++)
391 dat->d.st.c_len[i] = 0;
392 for(i = 0; i < 4096; i++)
393 dat->d.st.c_table[i] = c;
394 }
395 else
396 {
397 i = 0;
398 while(i < n)
399 {
400 c = dat->d.st.pt_table[dat->bitbuf >> (16 - 8)];
401 if(c >= NT)
402 {
403 uint16 mask;
404
405 mask = 1 << (16 - 9);
406 do
407 {
408 if(dat->bitbuf & mask)
409 c = dat->d.st.right[c];
410 else
411 c = dat->d.st.left[c];
412 mask >>= 1;
413 } while(c >= NT);
414 }
415 fillbuf(dat, dat->d.st.pt_len[c]);
416 if(c <= 2)
417 {
418 if(!c)
419 c = 1;
420 else if(c == 1)
421 c = getbits(dat, 4) + 3;
422 else
423 c = getbits(dat, CBIT) + 20;
424
425 /* Sanity check */
426 if (i + c >= NC)
427 return -1;
428
429 while(--c >= 0)
430 dat->d.st.c_len[i++] = 0;
431 }
432 else
433 dat->d.st.c_len[i++] = c - 2;
434 }
435 while(i < NC)
436 dat->d.st.c_len[i++] = 0;
437 if (make_table(dat, NC, dat->d.st.c_len, 12, dat->d.st.c_table, 4096) < 0)
438 return -1;
439 }
440
441 return 0;
442 }
443
decode_c_st1(struct LhADecrData * dat)444 static int decode_c_st1(struct LhADecrData *dat)
445 {
446 uint16 j, mask;
447
448 if(!dat->d.st.blocksize)
449 {
450 dat->d.st.blocksize = getbits(dat, 16);
451 if (read_pt_len(dat, NT, TBIT, 3) < 0)
452 return -1;
453 if (read_c_len(dat) < 0)
454 return -1;
455 if (read_pt_len(dat, dat->d.st.np, dat->d.st.pbit, -1) < 0)
456 return -1;
457 }
458 dat->d.st.blocksize--;
459 j = dat->d.st.c_table[dat->bitbuf >> 4];
460 if(j < NC)
461 {
462 /* Sanity check - 0-length character encoding on the Huffman tree is
463 * invalid and can cause hangs here. */
464 if(dat->d.st.c_len[j] == 0)
465 return -1;
466 fillbuf(dat, dat->d.st.c_len[j]);
467 }
468 else
469 {
470 fillbuf(dat, 12);
471 mask = 1 << (16 - 1);
472 do
473 {
474 if(dat->bitbuf & mask)
475 j = dat->d.st.right[j];
476 else
477 j = dat->d.st.left[j];
478 mask >>= 1;
479 } while(j >= NC);
480 fillbuf(dat, dat->d.st.c_len[j] - 12);
481 }
482 return j;
483 }
484
decode_p_st1(struct LhADecrData * dat)485 static uint16 decode_p_st1(struct LhADecrData *dat)
486 {
487 uint16 j, mask;
488
489 j = dat->d.st.pt_table[dat->bitbuf >> (16 - 8)];
490 if(j < dat->d.st.np)
491 fillbuf(dat, dat->d.st.pt_len[j]);
492 else
493 {
494 fillbuf(dat, 8);
495 mask = 1 << (16 - 1);
496 do
497 {
498 if(dat->bitbuf & mask)
499 j = dat->d.st.right[j];
500 else
501 j = dat->d.st.left[j];
502 mask >>= 1;
503 } while(j >= dat->d.st.np);
504 fillbuf(dat, dat->d.st.pt_len[j] - 8);
505 }
506 if(j)
507 j = (1 << (j - 1)) + getbits(dat, j - 1);
508 return j;
509 }
510
decode_start_st1(struct LhADecrData * dat)511 static int decode_start_st1(struct LhADecrData *dat)
512 {
513 if(dat->DicBit <= 13)
514 {
515 dat->d.st.np = 14;
516 dat->d.st.pbit = 4;
517 }
518 else
519 {
520 if(dat->DicBit == 16)
521 dat->d.st.np = 17; /* for -lh7- */
522 else
523 dat->d.st.np = 16;
524 dat->d.st.pbit = 5;
525 }
526 init_getbits(dat);
527 // dat->d.st.blocksize = 0; /* done automatically */
528
529 return 0;
530 }
531
532 /* ------------------------------------------------------------------------ */
533
start_c_dyn(struct LhADecrData * dat)534 static void start_c_dyn(struct LhADecrData *dat)
535 {
536 int32 i, j, f;
537
538 dat->d.st.n1 = (dat->d.st.n_max >= 256 + dat->d.st.maxmatch - THRESHOLD + 1) ? 512 : dat->d.st.n_max - 1;
539 for(i = 0; i < TREESIZE_C; i++)
540 {
541 dat->d.st.stock[i] = i;
542 dat->d.st.block[i] = 0;
543 }
544 for(i = 0, j = dat->d.st.n_max * 2 - 2; i < (int32) dat->d.st.n_max; i++, j--)
545 {
546 dat->d.st.freq[j] = 1;
547 dat->d.st.child[j] = ~i;
548 dat->d.st.s_node[i] = j;
549 dat->d.st.block[j] = 1;
550 }
551 dat->d.st.avail = 2;
552 dat->d.st.edge[1] = dat->d.st.n_max - 1;
553 i = dat->d.st.n_max * 2 - 2;
554 while(j >= 0)
555 {
556 f = dat->d.st.freq[j] = dat->d.st.freq[i] + dat->d.st.freq[i - 1];
557 dat->d.st.child[j] = i;
558 dat->d.st.parent[i] = dat->d.st.parent[i - 1] = j;
559 if(f == dat->d.st.freq[j + 1])
560 {
561 dat->d.st.edge[dat->d.st.block[j] = dat->d.st.block[j + 1]] = j;
562 }
563 else
564 {
565 dat->d.st.edge[dat->d.st.block[j] = dat->d.st.stock[dat->d.st.avail++]] = j;
566 }
567 i -= 2;
568 j--;
569 }
570 }
571
572 #ifdef ENABLE_LH2
573
start_p_dyn(struct LhADecrData * dat)574 static void start_p_dyn(struct LhADecrData *dat)
575 {
576 dat->d.st.freq[ROOT_P] = 1;
577 dat->d.st.child[ROOT_P] = ~(N_CHAR);
578 dat->d.st.s_node[N_CHAR] = ROOT_P;
579 dat->d.st.edge[dat->d.st.block[ROOT_P] = dat->d.st.stock[dat->d.st.avail++]] = ROOT_P;
580 dat->d.st.most_p = ROOT_P;
581 dat->d.st.total_p = 0;
582 dat->d.st.nn = 1 << dat->DicBit;
583 dat->nextcount = 64;
584 }
585
decode_start_dyn(struct LhADecrData * dat)586 static void decode_start_dyn(struct LhADecrData *dat)
587 {
588 dat->d.st.n_max = 286;
589 dat->d.st.maxmatch = MAXMATCH;
590 init_getbits(dat);
591 start_c_dyn(dat);
592 start_p_dyn(dat);
593 }
594
595 #endif
596
reconst(struct LhADecrData * dat,int32 start,int32 end)597 static void reconst(struct LhADecrData *dat, int32 start, int32 end)
598 {
599 int32 i, j, k, l, b = 0;
600 uint32 f, g;
601
602 for(i = j = start; i < end; i++)
603 {
604 if((k = dat->d.st.child[i]) < 0)
605 {
606 dat->d.st.freq[j] = (dat->d.st.freq[i] + 1) / 2;
607 dat->d.st.child[j] = k;
608 j++;
609 }
610 if(dat->d.st.edge[b = dat->d.st.block[i]] == i)
611 {
612 dat->d.st.stock[--dat->d.st.avail] = b;
613 }
614 }
615 j--;
616 i = end - 1;
617 l = end - 2;
618 while(i >= start)
619 {
620 while(i >= l)
621 {
622 dat->d.st.freq[i] = dat->d.st.freq[j];
623 dat->d.st.child[i] = dat->d.st.child[j];
624 i--, j--;
625 }
626 f = dat->d.st.freq[l] + dat->d.st.freq[l + 1];
627 for(k = start; f < dat->d.st.freq[k]; k++)
628 ;
629 while(j >= k)
630 {
631 dat->d.st.freq[i] = dat->d.st.freq[j];
632 dat->d.st.child[i] = dat->d.st.child[j];
633 i--, j--;
634 }
635 dat->d.st.freq[i] = f;
636 dat->d.st.child[i] = l + 1;
637 i--;
638 l -= 2;
639 }
640 f = 0;
641 for(i = start; i < end; i++)
642 {
643 if((j = dat->d.st.child[i]) < 0)
644 dat->d.st.s_node[~j] = i;
645 else
646 dat->d.st.parent[j] = dat->d.st.parent[j - 1] = i;
647 if((g = dat->d.st.freq[i]) == f) {
648 dat->d.st.block[i] = b;
649 }
650 else
651 {
652 dat->d.st.edge[b = dat->d.st.block[i] = dat->d.st.stock[dat->d.st.avail++]] = i;
653 f = g;
654 }
655 }
656 }
657
swap_inc(struct LhADecrData * dat,int32 p)658 static int32 swap_inc(struct LhADecrData *dat, int32 p)
659 {
660 int32 b, q, r, s;
661
662 b = dat->d.st.block[p];
663 if((q = dat->d.st.edge[b]) != p)
664 { /* swap for leader */
665 r = dat->d.st.child[p];
666 s = dat->d.st.child[q];
667 dat->d.st.child[p] = s;
668 dat->d.st.child[q] = r;
669 if(r >= 0)
670 dat->d.st.parent[r] = dat->d.st.parent[r - 1] = q;
671 else
672 dat->d.st.s_node[~r] = q;
673 if(s >= 0)
674 dat->d.st.parent[s] = dat->d.st.parent[s - 1] = p;
675 else
676 dat->d.st.s_node[~s] = p;
677 p = q;
678 dat->d.st.edge[b]++;
679 if(++dat->d.st.freq[p] == dat->d.st.freq[p - 1])
680 {
681 dat->d.st.block[p] = dat->d.st.block[p - 1];
682 }
683 else
684 {
685 dat->d.st.edge[dat->d.st.block[p] = dat->d.st.stock[dat->d.st.avail++]] = p; /* create block */
686 }
687 }
688 else if(b == dat->d.st.block[p + 1])
689 {
690 dat->d.st.edge[b]++;
691 if(++dat->d.st.freq[p] == dat->d.st.freq[p - 1])
692 {
693 dat->d.st.block[p] = dat->d.st.block[p - 1];
694 }
695 else
696 {
697 dat->d.st.edge[dat->d.st.block[p] = dat->d.st.stock[dat->d.st.avail++]] = p; /* create block */
698 }
699 }
700 else if(++dat->d.st.freq[p] == dat->d.st.freq[p - 1])
701 {
702 dat->d.st.stock[--dat->d.st.avail] = b; /* delete block */
703 dat->d.st.block[p] = dat->d.st.block[p - 1];
704 }
705 return dat->d.st.parent[p];
706 }
707
708 #ifdef ENABLE_LH2
709
update_p(struct LhADecrData * dat,int32 p)710 static void update_p(struct LhADecrData *dat, int32 p)
711 {
712 int32 q;
713
714 if(dat->d.st.total_p == 0x8000)
715 {
716 reconst(dat, ROOT_P, dat->d.st.most_p + 1);
717 dat->d.st.total_p = dat->d.st.freq[ROOT_P];
718 dat->d.st.freq[ROOT_P] = 0xffff;
719 }
720 q = dat->d.st.s_node[p + N_CHAR];
721 while(q != ROOT_P)
722 {
723 q = swap_inc(dat, q);
724 }
725 dat->d.st.total_p++;
726 }
727
make_new_node(struct LhADecrData * dat,int32 p)728 static void make_new_node(struct LhADecrData *dat, int32 p)
729 {
730 int32 q, r;
731
732 r = dat->d.st.most_p + 1;
733 q = r + 1;
734 dat->d.st.s_node[~(dat->d.st.child[r] = dat->d.st.child[dat->d.st.most_p])] = r;
735 dat->d.st.child[q] = ~(p + N_CHAR);
736 dat->d.st.child[dat->d.st.most_p] = q;
737 dat->d.st.freq[r] = dat->d.st.freq[dat->d.st.most_p];
738 dat->d.st.freq[q] = 0;
739 dat->d.st.block[r] = dat->d.st.block[dat->d.st.most_p];
740 if(dat->d.st.most_p == ROOT_P)
741 {
742 dat->d.st.freq[ROOT_P] = 0xffff;
743 dat->d.st.edge[dat->d.st.block[ROOT_P]]++;
744 }
745 dat->d.st.parent[r] = dat->d.st.parent[q] = dat->d.st.most_p;
746 dat->d.st.edge[dat->d.st.block[q] = dat->d.st.stock[dat->d.st.avail++]] =
747 dat->d.st.s_node[p + N_CHAR] = dat->d.st.most_p = q;
748 update_p(dat, p);
749 }
750
751 #endif
752
update_c(struct LhADecrData * dat,int32 p)753 static void update_c(struct LhADecrData *dat, int32 p)
754 {
755 int32 q;
756
757 if(dat->d.st.freq[ROOT_C] == 0x8000)
758 {
759 reconst(dat, 0, (int32) dat->d.st.n_max * 2 - 1);
760 }
761 dat->d.st.freq[ROOT_C]++;
762 q = dat->d.st.s_node[p];
763 do
764 {
765 q = swap_inc(dat, q);
766 } while(q != ROOT_C);
767 }
768
decode_c_dyn(struct LhADecrData * dat)769 static int decode_c_dyn(struct LhADecrData *dat)
770 {
771 int32 c;
772 int16 buf, cnt;
773
774 c = dat->d.st.child[ROOT_C];
775 buf = dat->bitbuf;
776 cnt = 0;
777 do
778 {
779 c = dat->d.st.child[c - (buf < 0)];
780 buf <<= 1;
781 if(++cnt == 16)
782 {
783 fillbuf(dat, 16);
784 buf = dat->bitbuf;
785 cnt = 0;
786 }
787 } while(c > 0);
788 fillbuf(dat, cnt);
789 c = ~c;
790 update_c(dat, c);
791 if(c == dat->d.st.n1)
792 c += getbits(dat, 8);
793 return (uint16) c;
794 }
795
796 #ifdef ENABLE_LH2
797
decode_p_dyn(struct LhADecrData * dat)798 static uint16 decode_p_dyn(struct LhADecrData *dat)
799 {
800 int32 c;
801 int16 buf, cnt;
802
803 while(dat->count > dat->nextcount)
804 {
805 make_new_node(dat, (int32) dat->nextcount / 64);
806 if((dat->nextcount += 64) >= (uint32)dat->d.st.nn)
807 dat->nextcount = 0xffffffff;
808 }
809 c = dat->d.st.child[ROOT_P];
810 buf = dat->bitbuf;
811 cnt = 0;
812 while(c > 0)
813 {
814 c = dat->d.st.child[c - (buf < 0)];
815 buf <<= 1;
816 if(++cnt == 16)
817 {
818 fillbuf(dat, 16);
819 buf = dat->bitbuf;
820 cnt = 0;
821 }
822 }
823 fillbuf(dat, cnt);
824 c = (~c) - N_CHAR;
825 update_p(dat, c);
826
827 return (uint16) ((c << 6) + getbits(dat, 6));
828 }
829
830 #endif
831
832 /* ------------------------------------------------------------------------ */
833
834 static const int32 fixed[2][16] = {
835 {3, 0x01, 0x04, 0x0c, 0x18, 0x30, 0}, /* old compatible */
836 {2, 0x01, 0x01, 0x03, 0x06, 0x0D, 0x1F, 0x4E, 0} /* 8K buf */
837 };
838
ready_made(struct LhADecrData * dat,int32 method)839 static void ready_made(struct LhADecrData *dat, int32 method)
840 {
841 int32 i, j;
842 uint32 code, weight;
843 int32 *tbl;
844
845 tbl = (int32 *) fixed[method];
846 j = *tbl++;
847 weight = 1 << (16 - j);
848 code = 0;
849 for(i = 0; i < dat->d.st.np; i++)
850 {
851 while(*tbl == i)
852 {
853 j++;
854 tbl++;
855 weight >>= 1;
856 }
857 dat->d.st.pt_len[i] = j;
858 dat->d.st.pt_code[i] = code;
859 code += weight;
860 }
861 }
862
decode_start_fix(struct LhADecrData * dat)863 static int decode_start_fix(struct LhADecrData *dat)
864 {
865 dat->d.st.n_max = 314;
866 dat->d.st.maxmatch = 60;
867 init_getbits(dat);
868 dat->d.st.np = 1 << (12 - 6);
869 start_c_dyn(dat);
870 ready_made(dat, 0);
871 if (make_table(dat, dat->d.st.np, dat->d.st.pt_len, 8, dat->d.st.pt_table, 256) < 0)
872 return -1;
873
874 return 0;
875 }
876
decode_p_st0(struct LhADecrData * dat)877 static uint16 decode_p_st0(struct LhADecrData *dat)
878 {
879 int32 i, j;
880
881 j = dat->d.st.pt_table[dat->bitbuf >> 8];
882 if(j < dat->d.st.np)
883 {
884 fillbuf(dat, dat->d.st.pt_len[j]);
885 }
886 else
887 {
888 fillbuf(dat, 8);
889 i = dat->bitbuf;
890 do
891 {
892 if((int16) i < 0)
893 j = dat->d.st.right[j];
894 else
895 j = dat->d.st.left[j];
896 i <<= 1;
897 } while(j >= dat->d.st.np);
898 fillbuf(dat, dat->d.st.pt_len[j] - 8);
899 }
900 return (uint16)((j << 6) + getbits(dat, 6));
901 }
902
903 #ifdef ENABLE_LH3
904
decode_start_st0(struct LhADecrData * dat)905 static void decode_start_st0(struct LhADecrData *dat)
906 {
907 dat->d.st.n_max = 286;
908 dat->d.st.maxmatch = MAXMATCH;
909 init_getbits(dat);
910 dat->d.st.np = 1 << (MAX_DICBIT - 6);
911 }
912
read_tree_c(struct LhADecrData * dat)913 static int read_tree_c(struct LhADecrData *dat) /* read tree from file */
914 {
915 int32 i, c;
916
917 i = 0;
918 while(i < N1)
919 {
920 if(getbits(dat, 1))
921 dat->d.st.c_len[i] = getbits(dat, LENFIELD) + 1;
922 else
923 dat->d.st.c_len[i] = 0;
924 if(++i == 3 && dat->d.st.c_len[0] == 1 && dat->d.st.c_len[1] == 1 && dat->d.st.c_len[2] == 1)
925 {
926 c = getbits(dat, CBIT);
927 memset(dat->d.st.c_len, 0, N1);
928 for(i = 0; i < 4096; i++)
929 dat->d.st.c_table[i] = c;
930 return 0;
931 }
932 }
933 if (make_table(dat, N1, dat->d.st.c_len, 12, dat->d.st.c_table, 4096) < 0)
934 return -1;
935
936 return 0;
937 }
938
read_tree_p(struct LhADecrData * dat)939 static void read_tree_p(struct LhADecrData *dat) /* read tree from file */
940 {
941 int32 i, c;
942
943 i = 0;
944 while(i < NP)
945 {
946 dat->d.st.pt_len[i] = getbits(dat, LENFIELD);
947 if(++i == 3 && dat->d.st.pt_len[0] == 1 && dat->d.st.pt_len[1] == 1 && dat->d.st.pt_len[2] == 1)
948 {
949 c = getbits(dat, MAX_DICBIT - 6);
950 for(i = 0; i < NP; i++)
951 dat->d.st.c_len[i] = 0;
952 for(i = 0; i < 256; i++)
953 dat->d.st.c_table[i] = c;
954 return;
955 }
956 }
957 }
958
decode_c_st0(struct LhADecrData * dat)959 static int decode_c_st0(struct LhADecrData *dat)
960 {
961 int32 i, j;
962
963 if(!dat->d.st.blocksize) /* read block head */
964 {
965 dat->d.st.blocksize = getbits(dat, BUFBITS); /* read block blocksize */
966 if (read_tree_c(dat) < 0)
967 return -1;
968 if(getbits(dat, 1))
969 {
970 read_tree_p(dat);
971 }
972 else
973 {
974 ready_made(dat, 1);
975 }
976 if (make_table(dat, NP, dat->d.st.pt_len, 8, dat->d.st.pt_table, 256) < 0)
977 return -1;
978 }
979 dat->d.st.blocksize--;
980 j = dat->d.st.c_table[dat->bitbuf >> 4];
981 if(j < N1)
982 fillbuf(dat, dat->d.st.c_len[j]);
983 else
984 {
985 fillbuf(dat, 12);
986 i = dat->bitbuf;
987 do
988 {
989 if((int16) i < 0)
990 j = dat->d.st.right[j];
991 else
992 j = dat->d.st.left[j];
993 i <<= 1;
994 } while(j >= N1);
995 fillbuf(dat, dat->d.st.c_len[j] - 12);
996 }
997 if (j == N1 - 1)
998 j += getbits(dat, EXTRABITS);
999 return (uint16) j;
1000 }
1001
1002 #endif
1003
1004 /* ------------------------------------------------------------------------ */
1005
1006 #ifdef ENABLE_PMARC
1007
1008 static const int32 PMARC2_historyBits[8] = { 3, 3, 4, 5, 5, 5, 6, 6};
1009 static const int32 PMARC2_historyBase[8] = { 0, 8, 16, 32, 64, 96,128,192};
1010 static const int32 PMARC2_repeatBits[6] = { 3, 3, 5, 6, 7, 0};
1011 static const int32 PMARC2_repeatBase[6] = {17, 25, 33, 65,129,256};
1012
PMARC2_hist_update(struct LhADecrData * dat,uint8 data)1013 static void PMARC2_hist_update(struct LhADecrData *dat, uint8 data)
1014 {
1015 if(data != dat->d.pm.lastbyte)
1016 {
1017 uint8 oldNext, oldPrev, newNext;
1018
1019 /* detach from old position */
1020 oldNext = dat->d.pm.next[data];
1021 oldPrev = dat->d.pm.prev[data];
1022 dat->d.pm.prev[oldNext] = oldPrev;
1023 dat->d.pm.next[oldPrev] = oldNext;
1024
1025 /* attach to new next */
1026 newNext = dat->d.pm.next[dat->d.pm.lastbyte];
1027 dat->d.pm.prev[newNext] = data;
1028 dat->d.pm.next[data] = newNext;
1029
1030 /* attach to new prev */
1031 dat->d.pm.prev[data] = dat->d.pm.lastbyte;
1032 dat->d.pm.next[dat->d.pm.lastbyte] = data;
1033
1034 dat->d.pm.lastbyte = data;
1035 }
1036 }
1037
PMARC2_tree_get(struct LhADecrData * dat,struct PMARC2_Tree * t)1038 static int32 PMARC2_tree_get(struct LhADecrData *dat, struct PMARC2_Tree *t)
1039 {
1040 int32 i;
1041 i = t->root;
1042
1043 while (i < 0x80)
1044 {
1045 i = (getbits(dat, 1) == 0 ? t->leftarr[i] : t->rightarr[i] );
1046 }
1047 return i & 0x7F;
1048 }
1049
PMARC2_tree_rebuild(struct LhADecrData * dat,struct PMARC2_Tree * t,uint8 bound,uint8 mindepth,uint8 * table)1050 static void PMARC2_tree_rebuild(struct LhADecrData *dat, struct PMARC2_Tree *t,
1051 uint8 bound, uint8 mindepth, uint8 * table)
1052 {
1053 uint8 d;
1054 int32 i, curr, empty, n;
1055
1056 t->root = 0;
1057 memset(t->leftarr, 0, bound);
1058 memset(t->rightarr, 0, bound);
1059 memset(dat->d.pm.parentarr, 0, bound);
1060
1061 for(i = 0; i < dat->d.pm.mindepth - 1; i++)
1062 {
1063 t->leftarr[i] = i + 1;
1064 dat->d.pm.parentarr[i+1] = i;
1065 }
1066
1067 curr = dat->d.pm.mindepth - 1;
1068 empty = dat->d.pm.mindepth;
1069 for(d = dat->d.pm.mindepth; ; d++)
1070 {
1071 for(i = 0; i < bound; i++)
1072 {
1073 if(table[i] == d)
1074 {
1075 if(t->leftarr[curr] == 0)
1076 t->leftarr[curr] = i | 128;
1077 else
1078 {
1079 t->rightarr[curr] = i | 128;
1080 n = 0;
1081 while(t->rightarr[curr] != 0)
1082 {
1083 if(curr == 0) /* root? -> done */
1084 return;
1085 curr = dat->d.pm.parentarr[curr];
1086 n++;
1087 }
1088 t->rightarr[curr] = empty;
1089 for(;;)
1090 {
1091 dat->d.pm.parentarr[empty] = curr;
1092 curr = empty;
1093 empty++;
1094
1095 n--;
1096 if(n == 0)
1097 break;
1098 t->leftarr[curr] = empty;
1099 }
1100 }
1101 }
1102 }
1103 if(t->leftarr[curr] == 0)
1104 t->leftarr[curr] = empty;
1105 else
1106 t->rightarr[curr] = empty;
1107
1108 dat->d.pm.parentarr[empty] = curr;
1109 curr = empty;
1110 empty++;
1111 }
1112 }
1113
PMARC2_hist_lookup(struct LhADecrData * dat,int32 n)1114 static uint8 PMARC2_hist_lookup(struct LhADecrData *dat, int32 n)
1115 {
1116 uint8 i;
1117 uint8 *direction = dat->d.pm.prev;
1118
1119 if(n >= 0x80)
1120 {
1121 /* Speedup: If you have to process more than half the ring,
1122 it's faster to walk the other way around. */
1123 direction = dat->d.pm.next;
1124 n = 0x100 - n;
1125 }
1126 for(i = dat->d.pm.lastbyte; n != 0; n--)
1127 i = direction[i];
1128 return i;
1129 }
1130
PMARC2_maketree1(struct LhADecrData * dat)1131 static void PMARC2_maketree1(struct LhADecrData *dat)
1132 {
1133 int32 i, nbits, x;
1134
1135 dat->d.pm.tree1bound = getbits(dat, 5);
1136 dat->d.pm.mindepth = getbits(dat, 3);
1137
1138 if(dat->d.pm.mindepth == 0)
1139 dat->d.pm.tree1.root = 128 | (dat->d.pm.tree1bound - 1);
1140 else
1141 {
1142 memset(dat->d.pm.table1, 0, 32);
1143 nbits = getbits(dat, 3);
1144 for(i = 0; i < dat->d.pm.tree1bound; i++)
1145 {
1146 if((x = getbits(dat, nbits)))
1147 dat->d.pm.table1[i] = x - 1 + dat->d.pm.mindepth;
1148 }
1149 PMARC2_tree_rebuild(dat, &dat->d.pm.tree1, dat->d.pm.tree1bound,
1150 dat->d.pm.mindepth, dat->d.pm.table1);
1151 }
1152 }
1153
PMARC2_maketree2(struct LhADecrData * dat,int32 par_b)1154 static void PMARC2_maketree2(struct LhADecrData *dat, int32 par_b)
1155 /* in use: 5 <= par_b <= 8 */
1156 {
1157 int32 i, count, index;
1158
1159 if(dat->d.pm.tree1bound < 10)
1160 return;
1161 if(dat->d.pm.tree1bound == 29 && dat->d.pm.mindepth == 0)
1162 return;
1163
1164 for(i = 0; i < 8; i++)
1165 dat->d.pm.table2[i] = 0;
1166 for(i = 0; i < par_b; i++)
1167 dat->d.pm.table2[i] = getbits(dat, 3);
1168 index = 0;
1169 count = 0;
1170 for(i = 0; i < 8; i++)
1171 {
1172 if(dat->d.pm.table2[i] != 0)
1173 {
1174 index = i;
1175 count++;
1176 }
1177 }
1178
1179 if(count == 1)
1180 {
1181 dat->d.pm.tree2.root = 128 | index;
1182 }
1183 else if (count > 1)
1184 {
1185 dat->d.pm.mindepth = 1;
1186 PMARC2_tree_rebuild(dat, &dat->d.pm.tree2, 8, dat->d.pm.mindepth, dat->d.pm.table2);
1187 }
1188 /* Note: count == 0 is possible! */
1189 }
1190
decode_start_pm2(struct LhADecrData * dat)1191 static void decode_start_pm2(struct LhADecrData *dat)
1192 {
1193 int32 i;
1194
1195 dat->d.pm.tree1.leftarr = dat->d.pm.tree1left;
1196 dat->d.pm.tree1.rightarr = dat->d.pm.tree1right;
1197 /* dat->d.pm.tree1.root = 0; */
1198 dat->d.pm.tree2.leftarr = dat->d.pm.tree2left;
1199 dat->d.pm.tree2.rightarr = dat->d.pm.tree2right;
1200 /* dat->d.pm.tree2.root = 0; */
1201
1202 dat->d.pm.dicsiz1 = (1 << dat->DicBit) - 1;
1203 init_getbits(dat);
1204
1205 /* history init */
1206 for(i = 0; i < 0x100; i++)
1207 {
1208 dat->d.pm.prev[(0xFF + i) & 0xFF] = i;
1209 dat->d.pm.next[(0x01 + i) & 0xFF] = i;
1210 }
1211 dat->d.pm.prev[0x7F] = 0x00; dat->d.pm.next[0x00] = 0x7F;
1212 dat->d.pm.prev[0xDF] = 0x80; dat->d.pm.next[0x80] = 0xDF;
1213 dat->d.pm.prev[0x9F] = 0xE0; dat->d.pm.next[0xE0] = 0x9F;
1214 dat->d.pm.prev[0x1F] = 0xA0; dat->d.pm.next[0xA0] = 0x1F;
1215 dat->d.pm.prev[0xFF] = 0x20; dat->d.pm.next[0x20] = 0xFF;
1216 dat->d.pm.lastbyte = 0x20;
1217
1218 /* dat->nextcount = 0; */
1219 /* dat->d.pm.lastupdate = 0; */
1220 getbits(dat, 1); /* discard bit */
1221 }
1222
decode_c_pm2(struct LhADecrData * dat)1223 static uint16 decode_c_pm2(struct LhADecrData *dat)
1224 {
1225 /* various admin: */
1226 while(dat->d.pm.lastupdate != dat->loc)
1227 {
1228 PMARC2_hist_update(dat, dat->text[dat->d.pm.lastupdate]);
1229 dat->d.pm.lastupdate = (dat->d.pm.lastupdate + 1) & dat->d.pm.dicsiz1;
1230 }
1231 while(dat->count >= dat->nextcount)
1232 /* Actually it will never loop, because count doesn't grow that fast.
1233 However, this is the way does it.
1234 Probably other encoding methods can have repeats larger than 256 bytes.
1235 Note: puts this code in decode_p...
1236 */
1237 {
1238 if(dat->nextcount == 0x0000)
1239 {
1240 PMARC2_maketree1(dat);
1241 PMARC2_maketree2(dat, 5);
1242 dat->nextcount = 0x0400;
1243 }
1244 else if(dat->nextcount == 0x0400)
1245 {
1246 PMARC2_maketree2(dat, 6);
1247 dat->nextcount = 0x0800;
1248 }
1249 else if(dat->nextcount == 0x0800)
1250 {
1251 PMARC2_maketree2(dat, 7);
1252 dat->nextcount = 0x1000;
1253 }
1254 else if(dat->nextcount == 0x1000)
1255 {
1256 if(getbits(dat, 1) != 0)
1257 PMARC2_maketree1(dat);
1258 PMARC2_maketree2(dat, 8);
1259 dat->nextcount = 0x2000;
1260 }
1261 else
1262 { /* 0x2000, 0x3000, 0x4000, ... */
1263 if(getbits(dat, 1) != 0)
1264 {
1265 PMARC2_maketree1(dat);
1266 PMARC2_maketree2(dat, 8);
1267 }
1268 dat->nextcount += 0x1000;
1269 }
1270 }
1271 dat->d.pm.gettree1 = PMARC2_tree_get(dat, &dat->d.pm.tree1); /* value preserved for decode_p */
1272
1273 /* direct value (ret <= UCHAR_MAX) */
1274 if(dat->d.pm.gettree1 < 8)
1275 {
1276 return (uint16) (PMARC2_hist_lookup(dat, PMARC2_historyBase[dat->d.pm.gettree1]
1277 + getbits(dat, PMARC2_historyBits[dat->d.pm.gettree1])));
1278 }
1279
1280 /* repeats: (ret > UCHAR_MAX) */
1281 if(dat->d.pm.gettree1 < 23)
1282 {
1283 return (uint16) (PMARC2_OFFSET + 2 + (dat->d.pm.gettree1 - 8));
1284 }
1285
1286 return (uint16) (PMARC2_OFFSET + PMARC2_repeatBase[dat->d.pm.gettree1 - 23]
1287 + getbits(dat, PMARC2_repeatBits[dat->d.pm.gettree1 - 23]));
1288 }
1289
decode_p_pm2(struct LhADecrData * dat)1290 static uint16 decode_p_pm2(struct LhADecrData *dat)
1291 {
1292 /* gettree1 value preserved from decode_c */
1293 int32 nbits, delta, gettree2;
1294
1295 if(dat->d.pm.gettree1 == 8)
1296 { /* 2-byte repeat with offset 0..63 */
1297 nbits = 6; delta = 0;
1298 }
1299 else if(dat->d.pm.gettree1 < 28)
1300 { /* n-byte repeat with offset 0..8191 */
1301 if(!(gettree2 = PMARC2_tree_get(dat, &dat->d.pm.tree2)))
1302 {
1303 nbits = 6;
1304 delta = 0;
1305 }
1306 else
1307 { /* 1..7 */
1308 nbits = 5 + gettree2;
1309 delta = 1 << nbits;
1310 }
1311 }
1312 else
1313 { /* 256 bytes repeat with offset 0 */
1314 nbits = 0;
1315 delta = 0;
1316 }
1317 return (uint16) (delta + getbits(dat, nbits));
1318 }
1319
1320 #endif
1321
1322 /* ------------------------------------------------------------------------ */
1323
1324 #ifdef ENABLE_LARC
1325
decode_c_lzs(struct LhADecrData * dat)1326 static uint16 decode_c_lzs(struct LhADecrData *dat)
1327 {
1328 if(getbits(dat, 1))
1329 {
1330 return getbits(dat, 8);
1331 }
1332 else
1333 {
1334 dat->d.lz.matchpos = getbits(dat, 11);
1335 return (uint16) (getbits(dat, 4) + 0x100);
1336 }
1337 }
1338
decode_p_lzs(struct LhADecrData * dat)1339 static uint16 decode_p_lzs(struct LhADecrData *dat)
1340 {
1341 return (uint16) ((dat->loc - dat->d.lz.matchpos - MAGIC0) & 0x7ff);
1342 }
1343
decode_start_lzs(struct LhADecrData * dat)1344 static void decode_start_lzs(struct LhADecrData *dat)
1345 {
1346 init_getbits(dat);
1347 }
1348
decode_c_lz5(struct LhADecrData * dat)1349 static uint16 decode_c_lz5(struct LhADecrData *dat)
1350 {
1351 int32 c;
1352
1353 if(!dat->d.lz.flagcnt)
1354 {
1355 dat->d.lz.flagcnt = 8;
1356 dat->d.lz.flag = fgetc(dat->in);
1357 }
1358 dat->d.lz.flagcnt--;
1359 c = fgetc(dat->in);
1360 if((dat->d.lz.flag & 1) == 0)
1361 {
1362 dat->d.lz.matchpos = c;
1363 c = fgetc(dat->in);
1364 dat->d.lz.matchpos += (c & 0xf0) << 4;
1365 c &= 0x0f;
1366 c += 0x100;
1367 }
1368 dat->d.lz.flag >>= 1;
1369 return (uint16) c;
1370 }
1371
decode_p_lz5(struct LhADecrData * dat)1372 static uint16 decode_p_lz5(struct LhADecrData *dat)
1373 {
1374 return (uint16) ((dat->loc - dat->d.lz.matchpos - MAGIC5) & 0xfff);
1375 }
1376
decode_start_lz5(struct LhADecrData * dat)1377 static void decode_start_lz5(struct LhADecrData *dat)
1378 {
1379 int32 i;
1380 char *text;
1381
1382 text = dat->text;
1383
1384 dat->d.lz.flagcnt = 0;
1385
1386 for(i = 0; i < 256; i++)
1387 memset(text + i * 13 + 18, i, 13);
1388
1389 for(i = 0; i < 256; i++)
1390 text[256 * 13 + 18 + i] = i;
1391
1392 for(i = 0; i < 256; i++)
1393 text[256 * 13 + 256 + 18 + i] = 255 - i;
1394
1395 memset(text + 256 * 13 + 512 + 18, 0, 128);
1396 memset(text + 256 * 13 + 512 + 128 + 18, ' ', 128-18);
1397 }
1398
1399 #endif
1400
LhA_Decrunch(FILE * in,FILE * out,int size,uint32 Method)1401 static int32 LhA_Decrunch(FILE *in, FILE *out, int size, uint32 Method)
1402 {
1403 struct LhADecrData *dd;
1404 int32 err = 0;
1405
1406 if((dd = calloc(sizeof(struct LhADecrData), 1))) {
1407 int (*DecodeStart)(struct LhADecrData *);
1408 int (*DecodeC)(struct LhADecrData *);
1409 uint16 (*DecodeP)(struct LhADecrData *);
1410
1411 /* most often used stuff */
1412 dd->in = in;
1413 dd->DicBit = 13;
1414 DecodeStart = decode_start_st1;
1415 DecodeP = decode_p_st1;
1416 DecodeC = decode_c_st1;
1417
1418 switch(Method)
1419 {
1420 case LZHUFF1_METHOD:
1421 dd->DicBit = 12;
1422 DecodeStart = decode_start_fix;
1423 DecodeC = decode_c_dyn;
1424 DecodeP = decode_p_st0;
1425 break;
1426
1427 #ifdef ENABLE_LH2
1428 case LZHUFF2_METHOD:
1429 DecodeStart = decode_start_dyn;
1430 DecodeC = decode_c_dyn;
1431 DecodeP = decode_p_dyn;
1432 break;
1433 #endif
1434
1435 #ifdef ENABLE_LH3
1436 case LZHUFF3_METHOD:
1437 DecodeStart = decode_start_st0;
1438 DecodeP = decode_p_st0;
1439 DecodeC = decode_c_st0;
1440 break;
1441 #endif
1442
1443 #ifdef ENABLE_PMARC
1444 case PMARC2_METHOD:
1445 DecodeStart = decode_start_pm2;
1446 DecodeP = decode_p_pm2;
1447 DecodeC = decode_c_pm2;
1448 break;
1449 #endif
1450
1451 case LZHUFF4_METHOD:
1452 dd->DicBit = 12;
1453 // break;
1454 case LZHUFF5_METHOD:
1455 break;
1456 case LZHUFF6_METHOD:
1457 dd->DicBit = 15;
1458 break;
1459 case LZHUFF7_METHOD:
1460 dd->DicBit = 16;
1461 break;
1462 case LZHUFF8_METHOD:
1463 dd->DicBit = 17;
1464 break;
1465
1466 #ifdef ENABLE_LARC
1467 case LARC_METHOD:
1468 dd->DicBit = 11;
1469 DecodeStart = decode_start_lzs;
1470 DecodeC = decode_c_lzs;
1471 DecodeP = decode_p_lzs;
1472 break;
1473 case LARC5_METHOD:
1474 dd->DicBit = 12;
1475 DecodeStart = decode_start_lz5;
1476 DecodeC = decode_c_lz5;
1477 DecodeP = decode_p_lz5;
1478 break;
1479 #endif
1480
1481 default:
1482 err = 1; break;
1483 }
1484 if(!err)
1485 {
1486 char *text;
1487 int32 i, c, offset;
1488 uint32 dicsiz;
1489
1490 dicsiz = 1 << dd->DicBit;
1491
1492 #ifdef ENABLE_LARC
1493 offset = (Method == LARC_METHOD || Method == PMARC2_METHOD) ? 0x100 - 2 : 0x100 - 3;
1494 #else
1495 offset = 0x100 - 3;
1496 #endif
1497
1498 if((text = dd->text = calloc(dicsiz, 1)))
1499 {
1500 /* if(Method == LZHUFF1_METHOD || Method == LZHUFF2_METHOD || Method == LZHUFF3_METHOD ||
1501 Method == LZHUFF6_METHOD || Method == LARC_METHOD || Method == LARC5_METHOD)
1502 */
1503 memset(text, ' ', (size_t) dicsiz);
1504
1505 if (DecodeStart(dd) < 0) {
1506 goto error;
1507 }
1508
1509 --dicsiz; /* now used with AND */
1510 while(1)
1511 {
1512 if (dd->count >= size)
1513 break;
1514
1515 if(feof(dd->in))
1516 break;
1517
1518 c = DecodeC(dd);
1519 if (c < 0) {
1520 goto error;
1521 }
1522
1523 if(dd->error)
1524 break;
1525
1526 if(c <= UCHAR_MAX)
1527 {
1528 int res = fputc(c, out);
1529 if (res < 0) {
1530 goto error;
1531 }
1532 text[dd->loc++] = res;
1533 dd->loc &= dicsiz;
1534 dd->count++;
1535 }
1536 else
1537 {
1538 c -= offset;
1539 i = dd->loc - DecodeP(dd) - 1;
1540 dd->count += c;
1541 while(c--)
1542 {
1543 int res = fputc(text[i++ & dicsiz], out);
1544 if (res < 0) {
1545 goto error;
1546 }
1547 text[dd->loc++] = res;
1548 dd->loc &= dicsiz;
1549 }
1550 }
1551 }
1552 err = dd->error;
1553 free(text);
1554 }
1555 else
1556 err = -1;
1557 }
1558 free(dd);
1559 }
1560 else
1561 err = -1;
1562 return err;
1563
1564 error:
1565 free(dd->text);
1566 free(dd);
1567 return -1;
1568 }
1569
1570 /*
1571 * For xmp
1572 */
1573
1574 struct lha_data {
1575 int method;
1576 char name[256];
1577 int packed_size;
1578 int original_size;
1579 int crc;
1580 };
1581
1582 /*
1583 * level 0 header
1584 *
1585 *
1586 * offset size field name
1587 * ----------------------------------
1588 * 0 1 header size [*1]
1589 * 1 1 header sum
1590 * ---------------------------------------
1591 * 2 5 method ID ^
1592 * 7 4 packed size [*2] |
1593 * 11 4 original size |
1594 * 15 2 time |
1595 * 17 2 date |
1596 * 19 1 attribute | [*1] header size (X+Y+22)
1597 * 20 1 level (0x00 fixed) |
1598 * 21 1 name length |
1599 * 22 X pathname |
1600 * X +22 2 file crc (CRC-16) |
1601 * X +24 Y ext-header(old style) v
1602 * -------------------------------------------------
1603 * X+Y+24 data ^
1604 * : | [*2] packed size
1605 * : v
1606 * -------------------------------------------------
1607 *
1608 * ext-header(old style)
1609 * 0 1 ext-type ('U')
1610 * 1 1 minor version
1611 * 2 4 UNIX time
1612 * 6 2 mode
1613 * 8 2 uid
1614 * 10 2 gid
1615 *
1616 * attribute (MS-DOS)
1617 * bit1 read only
1618 * bit2 hidden
1619 * bit3 system
1620 * bit4 volume label
1621 * bit5 directory
1622 * bit6 archive bit (need to backup)
1623 *
1624 */
1625
1626 /*
1627 * level 1 header
1628 *
1629 *
1630 * offset size field name
1631 * -----------------------------------
1632 * 0 1 header size [*1]
1633 * 1 1 header sum
1634 * -------------------------------------
1635 * 2 5 method ID ^
1636 * 7 4 skip size [*2] |
1637 * 11 4 original size |
1638 * 15 2 time |
1639 * 17 2 date |
1640 * 19 1 attribute (0x20 fixed) | [*1] header size (X+Y+25)
1641 * 20 1 level (0x01 fixed) |
1642 * 21 1 name length |
1643 * 22 X filename |
1644 * X+ 22 2 file crc (CRC-16) |
1645 * X+ 24 1 OS ID |
1646 * X +25 Y ??? |
1647 * X+Y+25 2 next-header size v
1648 * -------------------------------------------------
1649 * X+Y+27 Z ext-header ^
1650 * : |
1651 * ----------------------------------- | [*2] skip size
1652 * X+Y+Z+27 data |
1653 * : v
1654 * -------------------------------------------------
1655 *
1656 */
1657
1658 /*
1659 * level 2 header
1660 *
1661 *
1662 * offset size field name
1663 * --------------------------------------------------
1664 * 0 2 total header size [*1] ^
1665 * ----------------------- |
1666 * 2 5 method ID |
1667 * 7 4 packed size [*2] |
1668 * 11 4 original size |
1669 * 15 4 time |
1670 * 19 1 RESERVED (0x20 fixed) | [*1] total header size
1671 * 20 1 level (0x02 fixed) | (X+26+(1))
1672 * 21 2 file crc (CRC-16) |
1673 * 23 1 OS ID |
1674 * 24 2 next-header size |
1675 * ----------------------------------- |
1676 * 26 X ext-header |
1677 * : |
1678 * ----------------------------------- |
1679 * X +26 (1) padding v
1680 * -------------------------------------------------
1681 * X +26+(1) data ^
1682 * : | [*2] packed size
1683 * : v
1684 * -------------------------------------------------
1685 *
1686 */
1687
1688 /*
1689 * level 3 header
1690 *
1691 *
1692 * offset size field name
1693 * --------------------------------------------------
1694 * 0 2 size field length (4 fixed) ^
1695 * 2 5 method ID |
1696 * 7 4 packed size [*2] |
1697 * 11 4 original size |
1698 * 15 4 time |
1699 * 19 1 RESERVED (0x20 fixed) | [*1] total header size
1700 * 20 1 level (0x03 fixed) | (X+32)
1701 * 21 2 file crc (CRC-16) |
1702 * 23 1 OS ID |
1703 * 24 4 total header size [*1] |
1704 * 28 4 next-header size |
1705 * ----------------------------------- |
1706 * 32 X ext-header |
1707 * : v
1708 * -------------------------------------------------
1709 * X +32 data ^
1710 * : | [*2] packed size
1711 * : v
1712 * -------------------------------------------------
1713 *
1714 */
1715
get_header(FILE * f,struct lha_data * data)1716 static int get_header(FILE *f, struct lha_data *data)
1717 {
1718 uint8 buf[21];
1719 int size, level, namelen;
1720 int error;
1721
1722 memset(data, 0, sizeof(struct lha_data));
1723 if (fread(buf, 1, 21, f) != 21)
1724 return -1;
1725 level = buf[20];
1726
1727 switch (level) {
1728 case 0:
1729 size = buf[0];
1730 data->method = readmem32b(buf + 2);
1731 data->packed_size = readmem32l(buf + 7);
1732 data->original_size = readmem32l(buf + 11);
1733 namelen = read8(f, &error);
1734 if (error != 0) {
1735 return -1;
1736 }
1737 if (fread(data->name, 1, namelen, f) != namelen) {
1738 return -1;
1739 }
1740 data->crc = read16l(f, &error);
1741 if (error != 0) {
1742 return -1;
1743 }
1744 if (fseek(f, size + 2 - 24 - namelen, SEEK_CUR) < 0) {
1745 return -1;
1746 }
1747 break;
1748 case 1:
1749 size = buf[0];
1750 data->method = readmem32b(buf + 2);
1751 data->packed_size = readmem32l(buf + 7);
1752 data->original_size = readmem32l(buf + 11);
1753 namelen = read8(f, &error);
1754 if (error != 0) {
1755 return -1;
1756 }
1757 if (fread(data->name, 1, namelen, f) != namelen) {
1758 return -1;
1759 }
1760 data->crc = read16l(f, &error);
1761 if (error != 0) {
1762 return -1;
1763 }
1764 if (fseek(f, size - (22 + namelen) - 2, SEEK_CUR) < 0) {
1765 return -1;
1766 }
1767 while ((size = read16l(f, &error)) != 0) {
1768 if (error != 0) {
1769 return -1;
1770 }
1771 if (fseek(f, size - 2, SEEK_CUR) < 0) {
1772 return -1;
1773 }
1774 data->packed_size -= size;
1775 }
1776 break;
1777 case 2:
1778 size = readmem16l(buf);
1779 /* fall through */
1780 case 3:
1781 data->method = readmem32b(buf + 2);
1782 data->packed_size = readmem32l(buf + 7);
1783 data->original_size = readmem32l(buf + 11);
1784 data->crc = read16l(f, &error);
1785 if (error != 0) {
1786 return -1;
1787 }
1788 read8(f, &error); /* skip OS id */
1789 if (error != 0) {
1790 return -1;
1791 }
1792 while ((size = read16l(f, &error)) != 0) {
1793 int type;
1794 int s = size - 3;
1795 if (error != 0) {
1796 return -1;
1797 }
1798 type = read8(f, &error);
1799 if (error != 0) {
1800 return -1;
1801 }
1802 if (type == 0x01) {
1803 /* Sanity check */
1804 if (s < 0 || s > 256) {
1805 return -1;
1806 }
1807 if (fread(data->name, 1, s, f) != s) {
1808 return -1;
1809 }
1810 } else {
1811 if (fseek(f, s, SEEK_CUR) < 0) {
1812 return -1;
1813 }
1814 }
1815 }
1816 break;
1817 default:
1818 return -1;
1819 }
1820
1821 return 0;
1822 }
1823
test_lha(unsigned char * b)1824 static int test_lha(unsigned char *b) {
1825 return b[2] == '-' && b[3] == 'l' && b[4] == 'h' && b[6] == '-' &&
1826 b[20] <= 3;
1827 }
1828
decrunch_lha(FILE * in,FILE * out)1829 static int decrunch_lha(FILE *in, FILE *out)
1830 {
1831 struct lha_data data;
1832
1833 while (1) {
1834 if (get_header(in, &data) < 0)
1835 break;
1836
1837 #if 0
1838 printf("method = %x\n", data.method);
1839 printf("name = %s\n", data.name);
1840 printf("packed size = %d\n", data.packed_size);
1841 printf("original size = %d\n", data.original_size);
1842 printf("position = %lx\n", ftell(in));
1843 #endif
1844
1845 if (libxmp_exclude_match(data.name)) {
1846 if (fseek(in, data.packed_size, SEEK_CUR) < 0) {
1847 return -1;
1848 }
1849 continue;
1850 }
1851 return LhA_Decrunch(in, out, data.original_size, data.method);
1852 }
1853
1854 return -1;
1855 }
1856
1857 struct depacker libxmp_depacker_lha = {
1858 test_lha,
1859 decrunch_lha
1860 };
1861