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