OSDN Git Service

* lharc.c (main): use xmalloc().
[lha/lha.git] / src / huf.c
1 /* ------------------------------------------------------------------------ */
2 /* LHa for UNIX                                                                                                                         */
3 /*                              huf.c -- new static Huffman                                                                     */
4 /*                                                                                                                                                      */
5 /*              Modified                        Nobutaka Watazaki                                                       */
6 /*                                                                                                                                                      */
7 /*      Ver. 1.14       Source All chagned                              1995.01.14      N.Watazaki              */
8 /*      Ver. 1.14i      Support LH7 & Bug Fixed                 2000.10. 6      t.okamoto               */
9 /* ------------------------------------------------------------------------ */
10 #include "lha.h"
11
12 #ifdef sony_news
13 #include <sys/param.h>
14 #endif
15
16 #if STDC_HEADERS
17 #include <stdlib.h>
18 #else
19 extern char *malloc ();
20 #endif
21
22 /* ------------------------------------------------------------------------ */
23 unsigned short  left[2 * NC - 1], right[2 * NC - 1];
24 unsigned char   c_len[NC], pt_len[NPT];
25 unsigned short  c_freq[2 * NC - 1], c_table[4096], c_code[NC], p_freq[2 * NP - 1],
26                 pt_table[256], pt_code[NPT], t_freq[2 * NT - 1];
27
28 static unsigned char *buf;
29 static unsigned int bufsiz;
30 static unsigned short blocksize;
31 static unsigned short output_pos, output_mask;
32 static                  int       pbit;
33 static                  int       np;
34 /* ------------------------------------------------------------------------ */
35 /*                                                              Encording                                                                       */
36 /* ------------------------------------------------------------------------ */
37 static void
38 count_t_freq(/*void*/)
39 {
40         short           i, k, n, count;
41
42         for (i = 0; i < NT; i++)
43                 t_freq[i] = 0;
44         n = NC;
45         while (n > 0 && c_len[n - 1] == 0)
46                 n--;
47         i = 0;
48         while (i < n) {
49                 k = c_len[i++];
50                 if (k == 0) {
51                         count = 1;
52                         while (i < n && c_len[i] == 0) {
53                                 i++;
54                                 count++;
55                         }
56                         if (count <= 2)
57                                 t_freq[0] += count;
58                         else if (count <= 18)
59                                 t_freq[1]++;
60                         else if (count == 19) {
61                                 t_freq[0]++;
62                                 t_freq[1]++;
63                         }
64                         else
65                                 t_freq[2]++;
66                 } else
67                         t_freq[k + 2]++;
68         }
69 }
70
71 /* ------------------------------------------------------------------------ */
72 static void
73 write_pt_len(n, nbit, i_special)
74         short           n;
75         short           nbit;
76         short           i_special;
77 {
78         short           i, k;
79
80         while (n > 0 && pt_len[n - 1] == 0)
81                 n--;
82         putbits(nbit, n);
83         i = 0;
84         while (i < n) {
85                 k = pt_len[i++];
86                 if (k <= 6)
87                         putbits(3, k);
88                 else
89                         putbits(k - 3, USHRT_MAX << 1);
90                 if (i == i_special) {
91                         while (i < 6 && pt_len[i] == 0)
92                                 i++;
93                         putbits(2, i - 3);
94                 }
95         }
96 }
97
98 /* ------------------------------------------------------------------------ */
99 static void
100 write_c_len(/*void*/)
101 {
102         short           i, k, n, count;
103
104         n = NC;
105         while (n > 0 && c_len[n - 1] == 0)
106                 n--;
107         putbits(CBIT, n);
108         i = 0;
109         while (i < n) {
110                 k = c_len[i++];
111                 if (k == 0) {
112                         count = 1;
113                         while (i < n && c_len[i] == 0) {
114                                 i++;
115                                 count++;
116                         }
117                         if (count <= 2) {
118                                 for (k = 0; k < count; k++)
119                                         putcode(pt_len[0], pt_code[0]);
120                         }
121                         else if (count <= 18) {
122                                 putcode(pt_len[1], pt_code[1]);
123                                 putbits(4, count - 3);
124                         }
125                         else if (count == 19) {
126                                 putcode(pt_len[0], pt_code[0]);
127                                 putcode(pt_len[1], pt_code[1]);
128                                 putbits(4, 15);
129                         }
130                         else {
131                                 putcode(pt_len[2], pt_code[2]);
132                                 putbits(CBIT, count - 20);
133                         }
134                 }
135                 else
136                         putcode(pt_len[k + 2], pt_code[k + 2]);
137         }
138 }
139
140 /* ------------------------------------------------------------------------ */
141 static void
142 encode_c(c)
143         short           c;
144 {
145         putcode(c_len[c], c_code[c]);
146 }
147
148 /* ------------------------------------------------------------------------ */
149 static void
150 encode_p(p)
151         unsigned short  p;
152 {
153         unsigned short  c, q;
154
155         c = 0;
156         q = p;
157         while (q) {
158                 q >>= 1;
159                 c++;
160         }
161         putcode(pt_len[c], pt_code[c]);
162         if (c > 1)
163                 putbits(c - 1, p);
164 }
165
166 /* ------------------------------------------------------------------------ */
167 static void
168 send_block( /* void */ )
169 {
170         unsigned char   flags;
171         unsigned short  i, k, root, pos, size;
172
173         root = make_tree(NC, c_freq, c_len, c_code);
174         size = c_freq[root];
175         putbits(16, size);
176         if (root >= NC) {
177                 count_t_freq();
178                 root = make_tree(NT, t_freq, pt_len, pt_code);
179                 if (root >= NT) {
180                         write_pt_len(NT, TBIT, 3);
181                 } else {
182                         putbits(TBIT, 0);
183                         putbits(TBIT, root);
184                 }
185                 write_c_len();
186         } else {
187                 putbits(TBIT, 0);
188                 putbits(TBIT, 0);
189                 putbits(CBIT, 0);
190                 putbits(CBIT, root);
191         }
192         root = make_tree(np, p_freq, pt_len, pt_code);
193         if (root >= np) {
194                 write_pt_len(np, pbit, -1);
195         }
196         else {
197                 putbits(pbit, 0);
198                 putbits(pbit, root);
199         }
200         pos = 0;
201         for (i = 0; i < size; i++) {
202                 if (i % CHAR_BIT == 0)
203                         flags = buf[pos++];
204                 else
205                         flags <<= 1;
206                 if (flags & (1 << (CHAR_BIT - 1))) {
207                         encode_c(buf[pos++] + (1 << CHAR_BIT));
208                         k = buf[pos++] << CHAR_BIT;
209                         k += buf[pos++];
210                         encode_p(k);
211                 } else
212                         encode_c(buf[pos++]);
213                 if (unpackable)
214                         return;
215         }
216         for (i = 0; i < NC; i++)
217                 c_freq[i] = 0;
218         for (i = 0; i < np; i++)
219                 p_freq[i] = 0;
220 }
221
222 /* ------------------------------------------------------------------------ */
223 void
224 output_st1(c, p)
225         unsigned short  c;
226         unsigned short  p;
227 {
228         static unsigned short cpos;
229
230         output_mask >>= 1;
231         if (output_mask == 0) {
232                 output_mask = 1 << (CHAR_BIT - 1);
233                 if (output_pos >= bufsiz - 3 * CHAR_BIT) {
234                         send_block();
235                         if (unpackable)
236                                 return;
237                         output_pos = 0;
238                 }
239                 cpos = output_pos++;
240                 buf[cpos] = 0;
241         }
242         buf[output_pos++] = (unsigned char) c;
243         c_freq[c]++;
244         if (c >= (1 << CHAR_BIT)) {
245                 buf[cpos] |= output_mask;
246                 buf[output_pos++] = (unsigned char) (p >> CHAR_BIT);
247                 buf[output_pos++] = (unsigned char) p;
248                 c = 0;
249                 while (p) {
250                         p >>= 1;
251                         c++;
252                 }
253                 p_freq[c]++;
254         }
255 }
256
257 /* ------------------------------------------------------------------------ */
258 unsigned char  *
259 alloc_buf( /* void */ )
260 {
261         bufsiz = 16 * 1024 *2;  /* 65408U; */ /* t.okamoto */
262         while ((buf = (unsigned char *) malloc(bufsiz)) == NULL) {
263                 bufsiz = (bufsiz / 10) * 9;
264                 if (bufsiz < 4 * 1024)
265                         break;
266         }
267         return buf;
268 }
269
270 /* ------------------------------------------------------------------------ */
271 void
272 encode_start_st1( /* void */ )
273 {
274         int             i;
275
276 #if 0
277         if (dicbit <= (MAX_DICBIT - 2)) {
278                 pbit = 4;       /* lh4,5 etc. */
279                 np = 14;
280         } else {
281                 pbit = 5;       /* lh6 */
282                 np = 16;
283         }
284 #endif
285
286         if (dicbit <= 13) {
287                 pbit = 4;       /* lh4,5 etc. */
288                 np = 14;
289         } else {
290                 pbit = 5;       /* lh6,7 */
291                 if (dicbit == 16)
292                         np = 17;
293                 else
294                         np = 16;
295         }
296
297         for (i = 0; i < NC; i++)
298                 c_freq[i] = 0;
299         for (i = 0; i < np; i++)
300                 p_freq[i] = 0;
301         output_pos = output_mask = 0;
302         init_putbits();
303         buf[0] = 0;
304 }
305
306 /* ------------------------------------------------------------------------ */
307 void
308 encode_end_st1( /* void */ )
309 {
310         if (!unpackable) {
311                 send_block();
312                 putbits(CHAR_BIT - 1, 0);       /* flush remaining bits */
313         }
314 }
315
316 /* ------------------------------------------------------------------------ */
317 /*                                                              decoding                                                                        */
318 /* ------------------------------------------------------------------------ */
319 static void
320 read_pt_len(nn, nbit, i_special)
321         short           nn;
322         short           nbit;
323         short           i_special;
324 {
325         int           i, c, n;
326
327         n = getbits(nbit);
328         if (n == 0) {
329                 c = getbits(nbit);
330                 for (i = 0; i < nn; i++)
331                         pt_len[i] = 0;
332                 for (i = 0; i < 256; i++)
333                         pt_table[i] = c;
334         }
335         else {
336                 i = 0;
337                 while (i < n) {
338                         c = bitbuf >> (16 - 3);
339                         if (c == 7) {
340                                 unsigned short  mask = 1 << (16 - 4);
341                                 while (mask & bitbuf) {
342                                         mask >>= 1;
343                                         c++;
344                                 }
345                         }
346                         fillbuf((c < 7) ? 3 : c - 3);
347                         pt_len[i++] = c;
348                         if (i == i_special) {
349                                 c = getbits(2);
350                                 while (--c >= 0)
351                                         pt_len[i++] = 0;
352                         }
353                 }
354                 while (i < nn)
355                         pt_len[i++] = 0;
356                 make_table(nn, pt_len, 8, pt_table);
357         }
358 }
359
360 /* ------------------------------------------------------------------------ */
361 static void
362 read_c_len( /* void */ )
363 {
364         short           i, c, n;
365
366         n = getbits(CBIT);
367         if (n == 0) {
368                 c = getbits(CBIT);
369                 for (i = 0; i < NC; i++)
370                         c_len[i] = 0;
371                 for (i = 0; i < 4096; i++)
372                         c_table[i] = c;
373         } else {
374                 i = 0;
375                 while (i < n) {
376                         c = pt_table[bitbuf >> (16 - 8)];
377                         if (c >= NT) {
378                                 unsigned short  mask = 1 << (16 - 9);
379                                 do {
380                                         if (bitbuf & mask)
381                                                 c = right[c];
382                                         else
383                                                 c = left[c];
384                                         mask >>= 1;
385                                 } while (c >= NT);
386                         }
387                         fillbuf(pt_len[c]);
388                         if (c <= 2) {
389                                 if (c == 0)
390                                         c = 1;
391                                 else if (c == 1)
392                                         c = getbits(4) + 3;
393                                 else
394                                         c = getbits(CBIT) + 20;
395                                 while (--c >= 0)
396                                         c_len[i++] = 0;
397                         }
398                         else
399                                 c_len[i++] = c - 2;
400                 }
401                 while (i < NC)
402                         c_len[i++] = 0;
403                 make_table(NC, c_len, 12, c_table);
404         }
405 }
406
407 /* ------------------------------------------------------------------------ */
408 unsigned short
409 decode_c_st1( /*void*/ )
410 {
411         unsigned short  j, mask;
412
413         if (blocksize == 0) {
414                 blocksize = getbits(16);
415                 read_pt_len(NT, TBIT, 3);
416                 read_c_len();
417                 read_pt_len(np, pbit, -1);
418         }
419         blocksize--;
420         j = c_table[bitbuf >> 4];
421         if (j < NC)
422                 fillbuf(c_len[j]);
423         else {
424                 fillbuf(12);
425                 mask = 1 << (16 - 1);
426                 do {
427                         if (bitbuf & mask)
428                                 j = right[j];
429                         else
430                                 j = left[j];
431                         mask >>= 1;
432                 } while (j >= NC);
433                 fillbuf(c_len[j] - 12);
434         }
435         return j;
436 }
437
438 /* ------------------------------------------------------------------------ */
439 unsigned short
440 decode_p_st1( /* void */ )
441 {
442         unsigned short  j, mask;
443
444         j = pt_table[bitbuf >> (16 - 8)];
445         if (j < np)
446                 fillbuf(pt_len[j]);
447         else {
448                 fillbuf(8);
449                 mask = 1 << (16 - 1);
450                 do {
451                         if (bitbuf & mask)
452                                 j = right[j];
453                         else
454                                 j = left[j];
455                         mask >>= 1;
456                 } while (j >= np);
457                 fillbuf(pt_len[j] - 8);
458         }
459         if (j != 0)
460                 j = (1 << (j - 1)) + getbits(j - 1);
461         return j;
462 }
463
464 /* ------------------------------------------------------------------------ */
465 void
466 decode_start_st1( /* void */ )
467 {
468         if (dicbit <= 13)  {
469                 np = 14;
470                 pbit = 4;
471         } else {
472                 if (dicbit == 16) {
473                         np = 17; /* for -lh7- */
474                 } else {
475                         np = 16;
476                 }
477                 pbit = 5;
478         }
479
480 #if 0
481         if (dicbit <= 13)  {            /* 13 ... Changed N.Watazaki */
482                 np = 14;
483                 pbit = 4;
484         } else {
485                 np = 16;
486                 pbit = 5;
487         }
488 #endif
489         init_getbits();
490         blocksize = 0;
491 }
492
493 /* Local Variables: */
494 /* mode:c */
495 /* tab-width:4 */
496 /* End: */