1 /*
2 TiMidity++ -- MIDI to WAVE converter and player
3 Copyright (C) 1999-2002 Masanao Izumo <mo@goice.co.jp>
4 Copyright (C) 1995 Tuukka Toivonen <tt@cgs.fi>
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20
21 #ifdef HAVE_CONFIG_H
22 #include "config.h"
23 #endif /* HAVE_CONFIG_H */
24 #include <stdio.h>
25 #include <stdlib.h>
26 #ifndef NO_STRING_H
27 #include <string.h>
28 #else
29 #include <strings.h>
30 #endif
31 #include "timidity.h"
32 #include "unlzh.h"
33
34 #ifndef UCHAR_MAX
35 #define UCHAR_MAX 255 /* max value for an unsigned char */
36 #endif
37 #ifndef CHAR_BIT
38 #define CHAR_BIT 8
39 #endif
40 #define MAX_DICBIT 15
41 #define MAXMATCH 256 /* formerly F (not more than UCHAR_MAX + 1) */
42 #define THRESHOLD 3 /* choose optimal value */
43
44 #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
45 /* alphabet = {0, 1, 2, ..., NC - 1} */
46 #define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */
47 #define USHRT_BIT 16 /* (CHAR_BIT * sizeof(ushort)) */
48 #define NP (MAX_DICBIT + 1)
49 #define NT (USHRT_BIT + 3)
50 #define PBIT 4 /* smallest integer such that (1 << PBIT) > NP */
51 #define TBIT 5 /* smallest integer such that (1 << TBIT) > NT */
52 #define NPT 0x80
53 #define N1 286 /* alphabet size */
54 #define N2 (2 * N1 - 1) /* # of nodes in Huffman tree */
55 #define EXTRABITS 8
56 /* >= log2(F-THRESHOLD+258-N1) */
57 #define BUFBITS 16 /* >= log2(MAXBUF) */
58 #define LENFIELD 4 /* bit size of length field for tree output */
59 #define SNP (8 * 1024 / 64)
60 #define SNP2 (SNP * 2 - 1)
61 #define N_CHAR (256 + 60 - THRESHOLD + 1)
62 #define TREESIZE_C (N_CHAR * 2)
63 #define TREESIZE_P (128 * 2)
64 #define TREESIZE (TREESIZE_C + TREESIZE_P)
65 #define ROOT_C 0
66 #define ROOT_P TREESIZE_C
67 #define MAGIC0 18
68 #define MAGIC5 19
69 #define INBUFSIZ BUFSIZ
70
71 #undef MIN
72 #define MIN(a,b) ((a) < (b) ? (a) : (b))
73
74 struct _UNLZHHandler
75 {
76 void *user_val;
77 long (* read_func)(char *buff, long buff_size, void *user_val);
78 int method;
79
80 unsigned char inbuf[INBUFSIZ];
81 int inbuf_size;
82 int inbuf_cnt;
83 int initflag;
84
85 int cpylen;
86 int cpypos;
87 unsigned long origsize;
88 unsigned long compsize;
89 void (* decode_s)(UNLZHHandler decoder);
90 unsigned short (* decode_c)(UNLZHHandler decoder);
91 unsigned short (* decode_p)(UNLZHHandler decoder);
92 int dicbit;
93 unsigned short maxmatch;
94 unsigned long count;
95 unsigned short loc;
96 unsigned char text[1L<<MAX_DICBIT];
97 unsigned short bitbuf;
98 unsigned char subbitbuf, bitcount;
99 unsigned short left[2 * NC - 1], right[2 * NC - 1];
100 unsigned char c_len[NC], pt_len[NPT];
101 unsigned short c_table[4096], pt_table[256];
102 unsigned short blocksize;
103 unsigned int n_max;
104 short child [TREESIZE],
105 parent[TREESIZE],
106 block [TREESIZE],
107 edge [TREESIZE],
108 stock [TREESIZE],
109 node [TREESIZE / 2];
110 unsigned short freq[TREESIZE];
111 unsigned short total_p;
112 int avail, n1;
113 int most_p, nn;
114 unsigned long nextcount;
115 unsigned int snp;
116 int flag, flagcnt, matchpos;
117 int offset;
118 unsigned int pbit;
119 };
120
121 static unsigned short decode_c_cpy(UNLZHHandler decoder);
122 static unsigned short decode_p_cpy(UNLZHHandler decoder);
123 static void decode_start_cpy(UNLZHHandler decoder);
124 static void read_pt_len(UNLZHHandler decoder,
125 short k, short nbit, short i_special);
126 static void read_c_len(UNLZHHandler decoder);
127 static unsigned short decode_c_st1(UNLZHHandler decoder);
128 static unsigned short decode_p_st1(UNLZHHandler decoder);
129 static void decode_start_st1(UNLZHHandler decoder);
130 static void start_c_dyn(UNLZHHandler decoder);
131 static void start_p_dyn(UNLZHHandler decoder);
132 static void decode_start_dyn(UNLZHHandler decoder);
133 static void reconst(UNLZHHandler decoder, int start, int end);
134 static int swap_inc(UNLZHHandler decoder, int p);
135 static void update_c(UNLZHHandler decoder, int p);
136 static void update_p(UNLZHHandler decoder, int p);
137 static void make_new_node(UNLZHHandler decoder, int p);
138 static unsigned short decode_c_dyn(UNLZHHandler decoder);
139 static unsigned short decode_p_dyn(UNLZHHandler decoder);
140 static void decode_start_st0(UNLZHHandler decoder);
141 static void ready_made(UNLZHHandler decoder, int method);
142 static void read_tree_c(UNLZHHandler decoder);
143 static void read_tree_p(UNLZHHandler decoder);
144 static void decode_start_fix(UNLZHHandler decoder);
145 static unsigned short decode_c_st0(UNLZHHandler decoder);
146 static unsigned short decode_p_st0(UNLZHHandler decoder);
147 static unsigned short decode_c_lzs(UNLZHHandler decoder);
148 static unsigned short decode_p_lzs(UNLZHHandler decoder);
149 static void decode_start_lzs(UNLZHHandler decoder);
150 static unsigned short decode_c_lz5(UNLZHHandler decoder);
151 static unsigned short decode_p_lz5(UNLZHHandler decoder);
152 static void decode_start_lz5(UNLZHHandler decoder);
153 static int make_table(UNLZHHandler decoder,
154 int nchar, unsigned char bitlen[],
155 int tablebits, unsigned short table[]);
156 static int fill_inbuf(UNLZHHandler decoder);
157 static void fillbuf(UNLZHHandler decoder, unsigned char n);
158 static unsigned short getbits(UNLZHHandler decoder, unsigned char n);
159 static void init_getbits(UNLZHHandler decoder);
160
161 #define NEXTBYTE (decoder->inbuf_cnt < decoder->inbuf_size ? (int)decoder->inbuf[decoder->inbuf_cnt++] : fill_inbuf(decoder))
162
163 static struct
164 {
165 char *id;
166 int dicbit;
167 void (*decode_s)(UNLZHHandler decoder);
168 unsigned short (*decode_c)(UNLZHHandler decoder);
169 unsigned short (*decode_p)(UNLZHHandler decoder);
170 } method_table[] =
171 {
172 /* No compression */
173 {"-lh0-", 0, decode_start_cpy, decode_c_cpy, decode_p_cpy},
174
175 /* 4k sliding dictionary(max 60 bytes)
176 + dynamic Huffman + fixed encoding of position */
177 {"-lh1-", 12, decode_start_fix, decode_c_dyn, decode_p_st0},
178
179 /* 8k sliding dictionary(max 256 bytes) + dynamic Huffman */
180 {"-lh2-", 13, decode_start_dyn, decode_c_dyn, decode_p_dyn},
181
182 /* 8k sliding dictionary(max 256 bytes) + static Huffman */
183 {"-lh3-", 13, decode_start_st0, decode_c_st0, decode_p_st0},
184
185 /* 4k sliding dictionary(max 256 bytes)
186 + static Huffman + improved encoding of position and trees */
187 {"-lh4-", 12, decode_start_st1, decode_c_st1, decode_p_st1},
188
189 /* 8k sliding dictionary(max 256 bytes)
190 + static Huffman + improved encoding of position and trees */
191 {"-lh5-", 13, decode_start_st1, decode_c_st1, decode_p_st1},
192
193 /* 2k sliding dictionary(max 17 bytes) */
194 {"-lzs-", 11, decode_start_lzs, decode_c_lzs, decode_p_lzs},
195
196 /* No compression */
197 {"-lz5-", 12, decode_start_lz5, decode_c_lz5, decode_p_lz5},
198
199 /* 4k sliding dictionary(max 17 bytes) */
200 {"-lz4-", 0, decode_start_cpy, decode_c_cpy, decode_p_cpy},
201
202 /* Directory */
203 {"-lhd-", 0, NULL, NULL, NULL},
204
205 /* 32k sliding dictionary + static Huffman */
206 {"-lh6-", 15, decode_start_st1, decode_c_st1, decode_p_st1},
207
208 #if 0 /* not supported */
209 /* 64k sliding dictionary + static Huffman */
210 {"-lh7-", 16, decode_start_st1, decode_c_st1, decode_p_st1},
211 #endif
212 {NULL, 0, NULL, NULL}
213 };
214
215 char *lzh_methods[] =
216 {
217 "-lh0-", "-lh1-", "-lh2-", "-lh3-", "-lh4-", "-lh5-",
218 "-lzs-", "-lz5-", "-lz4-", "-lhd-", "-lh6-", "-lh7-", NULL
219 };
220
221 /*ARGSUSED*/
default_read_func(char * buf,long size,void * v)222 static long default_read_func(char *buf, long size, void *v)
223 {
224 return (long)fread(buf, 1, size, stdin);
225 }
226
open_unlzh_handler(long (* read_func)(char *,long,void *),const char * method,long compsize,long origsize,void * user_val)227 UNLZHHandler open_unlzh_handler(long (* read_func)(char *, long, void *),
228 const char *method,
229 long compsize, long origsize, void *user_val)
230 {
231 UNLZHHandler decoder;
232 int i;
233
234 for(i = 0; method_table[i].id != NULL; i++)
235 if(!strcmp(method_table[i].id, method))
236 break;
237 if(method_table[i].id == NULL)
238 return NULL; /* Invalid method */
239
240 if((decoder = (UNLZHHandler)malloc(sizeof(struct _UNLZHHandler))) == NULL)
241 return NULL;
242 memset(decoder, 0, sizeof(struct _UNLZHHandler));
243
244 if(strcmp(method, "-lhd-") == 0)
245 origsize = 0;
246
247 decoder->method = i;
248 decoder->dicbit = method_table[i].dicbit;
249 decoder->decode_s = method_table[i].decode_s;
250 decoder->decode_c = method_table[i].decode_c;
251 decoder->decode_p = method_table[i].decode_p;
252 decoder->compsize = compsize;
253 decoder->origsize = origsize;
254 decoder->user_val = user_val;
255 decoder->cpylen = 0;
256 decoder->cpypos = 0;
257 decoder->offset = (decoder->method == 6) ? 0x100 - 2 : 0x100 - 3;
258 decoder->count = 0;
259 decoder->loc = 0;
260 decoder->initflag = 0;
261
262 if(read_func == NULL)
263 decoder->read_func = default_read_func;
264 else
265 decoder->read_func = read_func;
266
267 return decoder;
268 }
269
close_unlzh_handler(UNLZHHandler decoder)270 void close_unlzh_handler(UNLZHHandler decoder)
271 {
272 free(decoder);
273 }
274
unlzh(UNLZHHandler decoder,char * buff,long buff_size)275 long unlzh(UNLZHHandler decoder, char *buff, long buff_size)
276 {
277 long n;
278 unsigned short dicsiz1;
279 int offset;
280 int cpylen, cpypos, loc;
281 unsigned char *text;
282 unsigned long origsize;
283
284 if((origsize = decoder->origsize) == 0 || buff_size <= 0)
285 return 0;
286
287 if(!decoder->initflag)
288 {
289 decoder->initflag = 1;
290 decoder->decode_s(decoder);
291 }
292
293 dicsiz1 = (1 << decoder->dicbit) - 1;
294 n = 0;
295 text = decoder->text;
296
297 if(decoder->cpylen > 0)
298 {
299 cpylen = decoder->cpylen;
300 cpypos = decoder->cpypos;
301 loc = decoder->loc;
302 while(cpylen > 0 && n < buff_size)
303 {
304 buff[n++] = text[loc++] = text[cpypos++];
305 loc &= dicsiz1;
306 cpypos &= dicsiz1;
307 cpylen--;
308 }
309 decoder->cpylen = cpylen;
310 decoder->cpypos = cpypos;
311 decoder->loc = loc;
312 }
313
314 if(n == buff_size)
315 return buff_size;
316
317 offset = decoder->offset;
318 while(decoder->count < origsize && n < buff_size)
319 {
320 int c;
321
322 c = decoder->decode_c(decoder);
323 if(c <= UCHAR_MAX)
324 {
325 buff[n++] = decoder->text[decoder->loc++] = c;
326 decoder->loc &= dicsiz1;
327 decoder->count++;
328 }
329 else
330 {
331 int i, j, k, m;
332
333 j = c - offset;
334 i = (decoder->loc - decoder->decode_p(decoder) - 1) & dicsiz1;
335 decoder->count += j;
336 loc = decoder->loc;
337 m = buff_size - n;
338 if(m > j)
339 m = j;
340 for(k = 0; k < m; k++)
341 {
342 buff[n++] = text[loc++] = text[i++];
343 loc &= dicsiz1;
344 i &= dicsiz1;
345 }
346 decoder->loc = loc;
347 if(k < j)
348 {
349 decoder->cpylen = j - k;
350 decoder->cpypos = i;
351 break;
352 }
353 }
354 }
355
356 return n;
357 }
358
decode_c_cpy(UNLZHHandler decoder)359 static unsigned short decode_c_cpy(UNLZHHandler decoder)
360 {
361 int c;
362
363 if((c = NEXTBYTE) == EOF)
364 return 0;
365 return (unsigned short)c;
366 }
367
368 /*ARGSUSED*/
decode_p_cpy(UNLZHHandler decoder)369 static unsigned short decode_p_cpy(UNLZHHandler decoder)
370 {
371 return 0;
372 }
373
decode_start_cpy(UNLZHHandler decoder)374 static void decode_start_cpy(UNLZHHandler decoder)
375 {
376 init_getbits(decoder);
377 }
378
read_pt_len(UNLZHHandler decoder,short k,short nbit,short i_special)379 static void read_pt_len(UNLZHHandler decoder,
380 short k, short nbit, short i_special)
381 {
382 short i, c, n;
383
384 n = getbits(decoder, nbit);
385 if(n == 0)
386 {
387 c = getbits(decoder, nbit);
388 for(i = 0; i < k; i++)
389 decoder->pt_len[i] = 0;
390 for(i = 0; i < 256; i++)
391 decoder->pt_table[i] = c;
392 }
393 else
394 {
395 i = 0;
396 while(i < n)
397 {
398 c = decoder->bitbuf >> (16 - 3);
399 if (c == 7)
400 {
401 unsigned short mask = 1 << (16 - 4);
402 while(mask & decoder->bitbuf)
403 {
404 mask >>= 1;
405 c++;
406 }
407 }
408 fillbuf(decoder, (c < 7) ? 3 : c - 3);
409 decoder->pt_len[i++] = c;
410 if(i == i_special)
411 {
412 c = getbits(decoder, 2);
413 while(--c >= 0 && i < NPT)
414 decoder->pt_len[i++] = 0;
415 }
416 }
417 while(i < k)
418 decoder->pt_len[i++] = 0;
419 make_table(decoder, k, decoder->pt_len, 8, decoder->pt_table);
420 }
421 }
422
read_c_len(UNLZHHandler decoder)423 static void read_c_len(UNLZHHandler decoder)
424 {
425 short i, c, n;
426
427 n = getbits(decoder, CBIT);
428 if(n == 0)
429 {
430 c = getbits(decoder, CBIT);
431 for(i = 0; i < NC; i++)
432 decoder->c_len[i] = 0;
433 for(i = 0; i < 4096; i++)
434 decoder->c_table[i] = c;
435 }
436 else
437 {
438 i = 0;
439 n = MIN(n, NC);
440 while(i < n)
441 {
442 c = decoder->pt_table[decoder->bitbuf >> (16 - 8)];
443 if(c >= NT)
444 {
445 unsigned short mask = 1 << (16 - 9);
446 do
447 {
448 if(decoder->bitbuf & mask)
449 c = decoder->right[c];
450 else
451 c = decoder->left[c];
452 mask >>= 1;
453 } while(c >= NT && (mask || c != decoder->left[c]));
454 }
455 fillbuf(decoder, decoder->pt_len[c]);
456 if(c <= 2)
457 {
458 if(c == 0)
459 c = 1;
460 else if(c == 1)
461 c = getbits(decoder, 4) + 3;
462 else
463 c = getbits(decoder, CBIT) + 20;
464 while(--c >= 0)
465 decoder->c_len[i++] = 0;
466 }
467 else
468 decoder->c_len[i++] = c - 2;
469 }
470 while(i < NC)
471 decoder->c_len[i++] = 0;
472 make_table(decoder, NC, decoder->c_len, 12, decoder->c_table);
473 }
474 }
475
decode_c_st1(UNLZHHandler decoder)476 static unsigned short decode_c_st1(UNLZHHandler decoder)
477 {
478 unsigned short j, mask;
479
480 if(decoder->blocksize == 0)
481 {
482 decoder->blocksize = getbits(decoder, 16);
483 read_pt_len(decoder, NT, TBIT, 3);
484 read_c_len(decoder);
485 read_pt_len(decoder, decoder->snp, decoder->pbit, -1);
486 }
487 decoder->blocksize--;
488 j = decoder->c_table[decoder->bitbuf >> 4];
489 if(j < NC)
490 fillbuf(decoder, decoder->c_len[j]);
491 else
492 {
493 fillbuf(decoder, 12);
494 mask = 1 << (16 - 1);
495 do
496 {
497 if(decoder->bitbuf & mask)
498 j = decoder->right[j];
499 else
500 j = decoder->left[j];
501 mask >>= 1;
502 } while(j >= NC && (mask || j != decoder->left[j]));
503 fillbuf(decoder, decoder->c_len[j] - 12);
504 }
505 return j;
506 }
507
decode_p_st1(UNLZHHandler decoder)508 static unsigned short decode_p_st1(UNLZHHandler decoder)
509 {
510 unsigned short j, mask;
511 unsigned int np = decoder->snp;
512
513 j = decoder->pt_table[decoder->bitbuf >> (16 - 8)];
514 if(j < np)
515 fillbuf(decoder, decoder->pt_len[j]);
516 else
517 {
518 fillbuf(decoder, 8);
519 mask = 1 << (16 - 1);
520 do
521 {
522 if(decoder->bitbuf & mask)
523 j = decoder->right[j];
524 else
525 j = decoder->left[j];
526 mask >>= 1;
527 } while(j >= np && (mask || j != decoder->left[j]));
528 fillbuf(decoder, decoder->pt_len[j] - 8);
529 }
530 if(j != 0)
531 j = (1 << (j - 1)) + getbits(decoder, j - 1);
532 return j;
533 }
534
535
decode_start_st1(UNLZHHandler decoder)536 static void decode_start_st1(UNLZHHandler decoder)
537 {
538 if(decoder->dicbit <= (MAX_DICBIT - 2)) {
539 decoder->snp = 14;
540 decoder->pbit = 4;
541 } else {
542 decoder->snp = 16;
543 decoder->pbit = 5;
544 }
545
546 init_getbits(decoder);
547 decoder->blocksize = 0;
548 }
549
start_c_dyn(UNLZHHandler decoder)550 static void start_c_dyn(UNLZHHandler decoder)
551 {
552 int i, j, f;
553
554 decoder->n1 = (decoder->n_max >= 256 + decoder->maxmatch - THRESHOLD + 1)
555 ? 512 : decoder->n_max - 1;
556 for(i = 0; i < TREESIZE_C; i++)
557 {
558 decoder->stock[i] = i;
559 decoder->block[i] = 0;
560 }
561 for(i = 0, j = decoder->n_max * 2 - 2; i < decoder->n_max; i++, j--)
562 {
563 decoder->freq[j] = 1;
564 decoder->child[j] = ~i;
565 decoder->node[i] = j;
566 decoder->block[j] = 1;
567 }
568 decoder->avail = 2;
569 decoder->edge[1] = decoder->n_max - 1;
570 i = decoder->n_max * 2 - 2;
571 while(j >= 0)
572 {
573 f = decoder->freq[j] = decoder->freq[i] + decoder->freq[i - 1];
574 decoder->child[j] = i;
575 decoder->parent[i] = decoder->parent[i - 1] = j;
576 if(f == decoder->freq[j + 1])
577 {
578 decoder->edge[decoder->block[j] = decoder->block[j + 1]] = j;
579 }
580 else
581 {
582 decoder->edge[decoder->block[j] =
583 decoder->stock[decoder->avail++]] = j;
584 }
585 i -= 2;
586 j--;
587 }
588 }
589
start_p_dyn(UNLZHHandler decoder)590 static void start_p_dyn(UNLZHHandler decoder)
591 {
592 decoder->freq[ROOT_P] = 1;
593 decoder->child[ROOT_P] = ~(N_CHAR);
594 decoder->node[N_CHAR] = ROOT_P;
595 decoder->edge[decoder->block[ROOT_P] =
596 decoder->stock[decoder->avail++]] = ROOT_P;
597 decoder->most_p = ROOT_P;
598 decoder->total_p = 0;
599 decoder->nn = 1 << decoder->dicbit;
600 decoder->nextcount = 64;
601 }
602
decode_start_dyn(UNLZHHandler decoder)603 static void decode_start_dyn(UNLZHHandler decoder)
604 {
605 decoder->n_max = 286;
606 decoder->maxmatch = MAXMATCH;
607 init_getbits(decoder);
608 start_c_dyn(decoder);
609 start_p_dyn(decoder);
610 }
611
reconst(UNLZHHandler decoder,int start,int end)612 static void reconst(UNLZHHandler decoder, int start, int end)
613 {
614 int i, j, k, l, b;
615 unsigned int f, g;
616
617 b = 0;
618 for(i = j = start; i < end; i++)
619 {
620 if((k = decoder->child[i]) < 0)
621 {
622 decoder->freq[j] = (decoder->freq[i] + 1) / 2;
623 decoder->child[j] = k;
624 j++;
625 }
626 if(decoder->edge[b = decoder->block[i]] == i)
627 {
628 decoder->stock[--decoder->avail] = b;
629 }
630 }
631 j--;
632 i = end - 1;
633 l = end - 2;
634 while(i >= start)
635 {
636 while (i >= l)
637 {
638 decoder->freq[i] = decoder->freq[j];
639 decoder->child[i] = decoder->child[j];
640 i--;
641 j--;
642 }
643 f = decoder->freq[l] + decoder->freq[l + 1];
644 for(k = start; f < decoder->freq[k]; k++)
645 ;
646 while(j >= k)
647 {
648 decoder->freq[i] = decoder->freq[j];
649 decoder->child[i] = decoder->child[j];
650 i--;
651 j--;
652 }
653 decoder->freq[i] = f;
654 decoder->child[i] = l + 1;
655 i--;
656 l -= 2;
657 }
658 f = 0;
659 for(i = start; i < end; i++)
660 {
661 if((j = decoder->child[i]) < 0)
662 decoder->node[~j] = i;
663 else
664 decoder->parent[j] = decoder->parent[j - 1] = i;
665 if((g = decoder->freq[i]) == f)
666 {
667 decoder->block[i] = b;
668 }
669 else
670 {
671 decoder->edge[b = decoder->block[i]
672 = decoder->stock[decoder->avail++]] = i;
673 f = g;
674 }
675 }
676 }
677
swap_inc(UNLZHHandler decoder,int p)678 static int swap_inc(UNLZHHandler decoder, int p)
679 {
680 int b, q, r, s;
681
682 b = decoder->block[p];
683 if((q = decoder->edge[b]) != p)
684 { /* swap for leader */
685 r = decoder->child[p];
686 s = decoder->child[q];
687 decoder->child[p] = s;
688 decoder->child[q] = r;
689 if(r >= 0)
690 decoder->parent[r] = decoder->parent[r - 1] = q;
691 else
692 decoder->node[~r] = q;
693 if(s >= 0)
694 decoder->parent[s] = decoder->parent[s - 1] = p;
695 else
696 decoder->node[~s] = p;
697 p = q;
698 goto Adjust;
699 }
700 else if(b == decoder->block[p + 1])
701 {
702 Adjust:
703 decoder->edge[b]++;
704 if(++decoder->freq[p] == decoder->freq[p - 1])
705 {
706 decoder->block[p] = decoder->block[p - 1];
707 }
708 else
709 {
710 decoder->edge[decoder->block[p] =
711 decoder->stock[decoder->avail++]] = p; /* create block */
712 }
713 }
714 else if (++decoder->freq[p] == decoder->freq[p - 1])
715 {
716 decoder->stock[--decoder->avail] = b; /* delete block */
717 decoder->block[p] = decoder->block[p - 1];
718 }
719 return decoder->parent[p];
720 }
721
update_c(UNLZHHandler decoder,int p)722 static void update_c(UNLZHHandler decoder, int p)
723 {
724 int q;
725
726 if(decoder->freq[ROOT_C] == 0x8000)
727 {
728 reconst(decoder, 0, decoder->n_max * 2 - 1);
729 }
730 decoder->freq[ROOT_C]++;
731 q = decoder->node[p];
732 do
733 {
734 q = swap_inc(decoder, q);
735 } while(q != ROOT_C);
736 }
737
update_p(UNLZHHandler decoder,int p)738 static void update_p(UNLZHHandler decoder, int p)
739 {
740 int q;
741
742 if(decoder->total_p == 0x8000)
743 {
744 reconst(decoder, ROOT_P, decoder->most_p + 1);
745 decoder->total_p = decoder->freq[ROOT_P];
746 decoder->freq[ROOT_P] = 0xffff;
747 }
748 q = decoder->node[p + N_CHAR];
749 while(q != ROOT_P)
750 {
751 q = swap_inc(decoder, q);
752 }
753 decoder->total_p++;
754 }
755
make_new_node(UNLZHHandler decoder,int p)756 static void make_new_node(UNLZHHandler decoder, int p)
757 {
758 int q, r;
759
760 r = decoder->most_p + 1;
761 q = r + 1;
762 decoder->node[~(decoder->child[r] = decoder->child[decoder->most_p])] = r;
763 decoder->child[q] = ~(p + N_CHAR);
764 decoder->child[decoder->most_p] = q;
765 decoder->freq[r] = decoder->freq[decoder->most_p];
766 decoder->freq[q] = 0;
767 decoder->block[r] = decoder->block[decoder->most_p];
768 if(decoder->most_p == ROOT_P)
769 {
770 decoder->freq[ROOT_P] = 0xffff;
771 decoder->edge[decoder->block[ROOT_P]]++;
772 }
773 decoder->parent[r] = decoder->parent[q] = decoder->most_p;
774 decoder->edge[decoder->block[q] = decoder->stock[decoder->avail++]]
775 = decoder->node[p + N_CHAR] = decoder->most_p = q;
776 update_p(decoder, p);
777 }
778
decode_c_dyn(UNLZHHandler decoder)779 static unsigned short decode_c_dyn(UNLZHHandler decoder)
780 {
781 int c;
782 short buf, cnt;
783
784 c = decoder->child[ROOT_C];
785 buf = decoder->bitbuf;
786 cnt = 0;
787 do
788 {
789 c = decoder->child[c - (buf < 0)];
790 buf <<= 1;
791 if(++cnt == 16)
792 {
793 fillbuf(decoder, 16);
794 buf = decoder->bitbuf;
795 cnt = 0;
796 }
797 }while (c > 0);
798 fillbuf(decoder, cnt);
799 c = ~c;
800 update_c(decoder, c);
801 if(c == decoder->n1)
802 c += getbits(decoder, 8);
803 return c;
804 }
805
decode_p_dyn(UNLZHHandler decoder)806 static unsigned short decode_p_dyn(UNLZHHandler decoder)
807 {
808 int c;
809 short buf, cnt;
810
811 while(decoder->count > decoder->nextcount)
812 {
813 make_new_node(decoder, (int)(decoder->nextcount / 64));
814 if((decoder->nextcount += 64) >= decoder->nn)
815 decoder->nextcount = 0xffffffff;
816 }
817 c = decoder->child[ROOT_P];
818 buf = decoder->bitbuf;
819 cnt = 0;
820 while(c > 0)
821 {
822 c = decoder->child[c - (buf < 0)];
823 buf <<= 1;
824 if(++cnt == 16)
825 {
826 fillbuf(decoder, 16);
827 buf = decoder->bitbuf;
828 cnt = 0;
829 }
830 }
831 fillbuf(decoder, cnt);
832 c = (~c) - N_CHAR;
833 update_p(decoder, c);
834
835 return (c << 6) + getbits(decoder, 6);
836 }
837
decode_start_st0(UNLZHHandler decoder)838 static void decode_start_st0(UNLZHHandler decoder)
839 {
840 decoder->n_max = 286;
841 decoder->maxmatch = MAXMATCH;
842 init_getbits(decoder);
843 decoder->snp = 1 << (MAX_DICBIT - 6);
844 decoder->blocksize = 0;
845 }
846
847 static int fixed[2][16] = {
848 {3, 0x01, 0x04, 0x0c, 0x18, 0x30, 0}, /* old compatible */
849 {2, 0x01, 0x01, 0x03, 0x06, 0x0D, 0x1F, 0x4E, 0} /* 8K buf */
850 };
851
ready_made(UNLZHHandler decoder,int method)852 static void ready_made(UNLZHHandler decoder, int method)
853 {
854 int i, j;
855 unsigned int code, weight;
856 int *tbl;
857
858 tbl = fixed[method];
859 j = *tbl++;
860 weight = 1 << (16 - j);
861 code = 0;
862 for(i = 0; i < decoder->snp; i++)
863 {
864 while(*tbl == i)
865 {
866 j++;
867 tbl++;
868 weight >>= 1;
869 }
870 decoder->pt_len[i] = j;
871 code += weight;
872 }
873 }
874
read_tree_c(UNLZHHandler decoder)875 static void read_tree_c(UNLZHHandler decoder) /* read tree from file */
876 {
877 int i, c;
878
879 i = 0;
880 while(i < N1)
881 {
882 if(getbits(decoder, 1))
883 decoder->c_len[i] = getbits(decoder, LENFIELD) + 1;
884 else
885 decoder->c_len[i] = 0;
886 if(++i == 3 && decoder->c_len[0] == 1 &&
887 decoder->c_len[1] == 1 && decoder->c_len[2] == 1)
888 {
889 c = getbits(decoder, CBIT);
890 for(i = 0; i < N1; i++)
891 decoder->c_len[i] = 0;
892 for(i = 0; i < 4096; i++)
893 decoder->c_table[i] = c;
894 return;
895 }
896 }
897 make_table(decoder, N1, decoder->c_len, 12, decoder->c_table);
898 }
899
read_tree_p(UNLZHHandler decoder)900 static void read_tree_p(UNLZHHandler decoder) /* read tree from file */
901 {
902 int i, c;
903
904 i = 0;
905 while(i < SNP)
906 {
907 decoder->pt_len[i] = getbits(decoder, LENFIELD);
908 if(++i == 3 && decoder->pt_len[0] == 1 &&
909 decoder->pt_len[1] == 1 && decoder->pt_len[2] == 1)
910 {
911 c = getbits(decoder, MAX_DICBIT - 6);
912 for(i = 0; i < SNP; i++)
913 decoder->c_len[i] = 0;
914 for(i = 0; i < 256; i++)
915 decoder->c_table[i] = c;
916 return;
917 }
918 }
919 }
920
decode_start_fix(UNLZHHandler decoder)921 static void decode_start_fix(UNLZHHandler decoder)
922 {
923 decoder->n_max = 314;
924 decoder->maxmatch = 60;
925 init_getbits(decoder);
926 decoder->snp = 1 << (12 - 6);
927 start_c_dyn(decoder);
928 ready_made(decoder, 0);
929 make_table(decoder, decoder->snp, decoder->pt_len, 8, decoder->pt_table);
930 }
931
decode_c_st0(UNLZHHandler decoder)932 static unsigned short decode_c_st0(UNLZHHandler decoder)
933 {
934 int i, j;
935
936 if(decoder->blocksize == 0) /* read block head */
937 {
938 /* read block blocksize */
939 decoder->blocksize = getbits(decoder, BUFBITS);
940 read_tree_c(decoder);
941 if(getbits(decoder, 1))
942 {
943 read_tree_p(decoder);
944 }
945 else
946 {
947 ready_made(decoder, 1);
948 }
949 make_table(decoder, SNP, decoder->pt_len, 8, decoder->pt_table);
950 }
951 decoder->blocksize--;
952 j = decoder->c_table[decoder->bitbuf >> 4];
953 if(j < N1)
954 fillbuf(decoder, decoder->c_len[j]);
955 else
956 {
957 fillbuf(decoder, 12);
958 i = decoder->bitbuf;
959 do
960 {
961 if((short)i < 0)
962 j = decoder->right[j];
963 else
964 j = decoder->left [j];
965 i <<= 1;
966 } while(j >= N1);
967 fillbuf(decoder, decoder->c_len[j] - 12);
968 }
969 if(j == N1 - 1)
970 j += getbits(decoder, EXTRABITS);
971 return j;
972 }
973
decode_p_st0(UNLZHHandler decoder)974 static unsigned short decode_p_st0(UNLZHHandler decoder)
975 {
976 int i, j;
977
978 j = decoder->pt_table[decoder->bitbuf >> 8];
979 if(j < decoder->snp)
980 {
981 fillbuf(decoder, decoder->pt_len[j]);
982 }
983 else
984 {
985 fillbuf(decoder, 8);
986 i = decoder->bitbuf;
987 do
988 {
989 if((short)i < 0)
990 j = decoder->right[j];
991 else
992 j = decoder->left[j];
993 i <<= 1;
994 } while(j >= decoder->snp);
995 fillbuf(decoder, decoder->pt_len[j] - 8);
996 }
997 return (j << 6) + getbits(decoder, 6);
998 }
999
decode_c_lzs(UNLZHHandler decoder)1000 static unsigned short decode_c_lzs(UNLZHHandler decoder)
1001 {
1002 if(getbits(decoder, 1))
1003 return getbits(decoder, 8);
1004 decoder->matchpos = getbits(decoder, 11);
1005 return getbits(decoder, 4) + 0x100;
1006 }
1007
decode_p_lzs(UNLZHHandler decoder)1008 static unsigned short decode_p_lzs(UNLZHHandler decoder)
1009 {
1010 return (decoder->loc - decoder->matchpos - MAGIC0) & 0x7ff;
1011 }
1012
decode_start_lzs(UNLZHHandler decoder)1013 static void decode_start_lzs(UNLZHHandler decoder)
1014 {
1015 init_getbits(decoder);
1016 }
1017
decode_c_lz5(UNLZHHandler decoder)1018 static unsigned short decode_c_lz5(UNLZHHandler decoder)
1019 {
1020 int c;
1021
1022 if(decoder->flagcnt == 0)
1023 {
1024 decoder->flagcnt = 8;
1025 decoder->flag = NEXTBYTE;
1026 }
1027 decoder->flagcnt--;
1028 c = NEXTBYTE;
1029 if((decoder->flag & 1) == 0)
1030 {
1031 decoder->matchpos = c;
1032 c = NEXTBYTE;
1033 decoder->matchpos += (c & 0xf0) << 4;
1034 c &= 0x0f;
1035 c += 0x100;
1036 }
1037 decoder->flag >>= 1;
1038 return c;
1039 }
1040
decode_p_lz5(UNLZHHandler decoder)1041 static unsigned short decode_p_lz5(UNLZHHandler decoder)
1042 {
1043 return (decoder->loc - decoder->matchpos - MAGIC5) & 0xfff;
1044 }
1045
decode_start_lz5(UNLZHHandler decoder)1046 static void decode_start_lz5(UNLZHHandler decoder)
1047 {
1048 int i;
1049
1050 decoder->flagcnt = 0;
1051 for(i = 0; i < 256; i++)
1052 memset(&decoder->text[i * 13 + 18], i, 13);
1053 for(i = 0; i < 256; i++)
1054 decoder->text[256 * 13 + 18 + i] = i;
1055 for(i = 0; i < 256; i++)
1056 decoder->text[256 * 13 + 256 + 18 + i] = 255 - i;
1057 memset(&decoder->text[256 * 13 + 512 + 18], 0, 128);
1058 memset(&decoder->text[256 * 13 + 512 + 128 + 18], ' ', 128 - 18);
1059 }
1060
make_table(UNLZHHandler decoder,int nchar,unsigned char bitlen[],int tablebits,unsigned short table[])1061 static int make_table(UNLZHHandler decoder,
1062 int nchar, unsigned char bitlen[],
1063 int tablebits, unsigned short table[])
1064 {
1065 unsigned short cnttable[17]; /* count of bitlen */
1066 unsigned short weight[17]; /* 0x10000ul >> bitlen */
1067 unsigned short start[17]; /* first code of bitlen */
1068 unsigned short total;
1069 unsigned int i;
1070 int j, k, l, m, n, available, tablelimit;
1071 unsigned short *p;
1072
1073 tablelimit = 1 << tablebits;
1074 available = nchar;
1075
1076 /* initialize */
1077 for(i = 1; i <= 16; i++)
1078 {
1079 cnttable[i] = 0;
1080 weight[i] = 1 << (16 - i);
1081 }
1082
1083 /* cnttable */
1084 for(i = 0; i < nchar; i++)
1085 {
1086 if(bitlen[i] > 16)
1087 {
1088 fprintf(stderr, "Decode: Bad table (4)\n");
1089 return 1;
1090 }
1091 cnttable[bitlen[i]]++;
1092 }
1093
1094 /* calculate first code */
1095 total = 0;
1096 for(i = 1; i <= 16; i++)
1097 {
1098 start[i] = total;
1099 total += weight[i] * cnttable[i];
1100 }
1101 if((total & 0xffff) != 0)
1102 {
1103 fprintf(stderr, "Decode: Bad table (5)\n");
1104 /*exit(1);*/ /* for win32gui i/f 2002/8/17 */
1105 return 1;
1106 }
1107
1108 /* shift data for make table. */
1109 m = 16 - tablebits;
1110 for(i = 1; i <= tablebits; i++)
1111 {
1112 start[i] >>= m;
1113 weight[i] >>= m;
1114 }
1115
1116 /* initialize */
1117 j = start[tablebits + 1] >> m;
1118 if(j != 0)
1119 {
1120 k = 1 << tablebits;
1121 for(i = j; i < k; i++)
1122 table[i] = 0;
1123 }
1124
1125 /* create table and tree */
1126 for(j = 0; j < nchar; j++)
1127 {
1128 k = bitlen[j];
1129 if(k == 0)
1130 continue;
1131 l = start[k] + weight[k];
1132 if(k <= tablebits)
1133 {
1134 /* code in table */
1135 l = MIN(l, tablelimit);
1136 for(i = start[k]; i < l; i++)
1137 table[i] = j;
1138 }
1139 else
1140 {
1141 /* code not in table */
1142 i = start[k];
1143 if ((i >> m) >= tablelimit)
1144 {
1145 fprintf(stderr, "Decode: Bad table (6)\n");
1146 return 1;
1147 }
1148 p = &table[i >> m];
1149 i <<= tablebits;
1150 n = k - tablebits;
1151 /* make tree (n length) */
1152 while(--n >= 0)
1153 {
1154 if(*p == 0)
1155 {
1156 decoder->right[available] = decoder->left[available] = 0;
1157 *p = available++;
1158 }
1159 if(i & 0x8000)
1160 p = &decoder->right[*p];
1161 else
1162 p = &decoder->left[*p];
1163 i <<= 1;
1164 }
1165 *p = j;
1166 }
1167 start[k] = l;
1168 }
1169 return 0;
1170 }
1171
fill_inbuf(UNLZHHandler decoder)1172 static int fill_inbuf(UNLZHHandler decoder)
1173 {
1174 long n, i;
1175
1176 if(decoder->compsize == 0)
1177 return EOF;
1178 i = INBUFSIZ;
1179 if(i > decoder->compsize)
1180 i = (long)decoder->compsize;
1181 n = decoder->read_func((char *)decoder->inbuf, i, decoder->user_val);
1182 if(n <= 0)
1183 return EOF;
1184 decoder->inbuf_size = n;
1185 decoder->inbuf_cnt = 1;
1186 decoder->compsize -= n;
1187 return (int)decoder->inbuf[0];
1188 }
1189
1190 /* Shift bitbuf n bits left, read n bits */
fillbuf(UNLZHHandler decoder,unsigned char n)1191 static void fillbuf(UNLZHHandler decoder, unsigned char n)
1192 {
1193 unsigned char bitcount;
1194 unsigned short bitbuf;
1195
1196 bitcount = decoder->bitcount;
1197 bitbuf = decoder->bitbuf;
1198 while(n > bitcount)
1199 {
1200 n -= bitcount;
1201 bitbuf = (bitbuf << bitcount)
1202 + (decoder->subbitbuf >> (CHAR_BIT - bitcount));
1203 decoder->subbitbuf = (unsigned char)NEXTBYTE;
1204 bitcount = CHAR_BIT;
1205 }
1206 bitcount -= n;
1207 bitbuf = (bitbuf << n) + (decoder->subbitbuf >> (CHAR_BIT - n));
1208 decoder->subbitbuf <<= n;
1209 decoder->bitcount = bitcount;
1210 decoder->bitbuf = bitbuf;
1211 }
1212
getbits(UNLZHHandler decoder,unsigned char n)1213 static unsigned short getbits(UNLZHHandler decoder, unsigned char n)
1214 {
1215 unsigned short x;
1216
1217 x = decoder->bitbuf >> (2 * CHAR_BIT - n);
1218 fillbuf(decoder, n);
1219 return x;
1220 }
1221
init_getbits(UNLZHHandler decoder)1222 static void init_getbits(UNLZHHandler decoder)
1223 {
1224 decoder->bitbuf = 0;
1225 decoder->subbitbuf = 0;
1226 decoder->bitcount = 0;
1227 decoder->inbuf_cnt = 0;
1228 decoder->inbuf_size = 0;
1229 fillbuf(decoder, 2 * CHAR_BIT);
1230 }
1231