1 /* ------------------------------------------------------------------------ */
3 /* huf.c -- new static Huffman */
5 /* Modified Nobutaka Watazaki */
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 /* ------------------------------------------------------------------------ */
13 #include <sys/param.h>
19 extern char *malloc ();
22 /* ------------------------------------------------------------------------ */
23 unsigned short left[2 * NC - 1], right[2 * NC - 1];
25 unsigned short c_code[NC]; /* encode */
26 unsigned short pt_code[NPT]; /* encode */
28 unsigned short c_table[4096]; /* decode */
29 unsigned short pt_table[256]; /* decode */
31 unsigned short c_freq[2 * NC - 1]; /* encode */
32 unsigned short p_freq[2 * NP - 1]; /* encode */
33 unsigned short t_freq[2 * NT - 1]; /* encode */
35 unsigned char c_len[NC];
36 unsigned char pt_len[NPT];
38 static unsigned char *buf; /* encode */
39 static unsigned int bufsiz; /* encode */
40 static unsigned short blocksize; /* decode */
41 static unsigned short output_pos, output_mask; /* encode */
45 /* ------------------------------------------------------------------------ */
47 /* ------------------------------------------------------------------------ */
49 count_t_freq(/*void*/)
53 for (i = 0; i < NT; i++)
56 while (n > 0 && c_len[n - 1] == 0)
63 while (i < n && c_len[i] == 0) {
71 else if (count == 19) {
82 /* ------------------------------------------------------------------------ */
84 write_pt_len(n, nbit, i_special)
91 while (n > 0 && pt_len[n - 1] == 0)
100 /* k=7 -> 1110 k=8 -> 11110 k=9 -> 111110 ... */
101 putbits(k - 3, USHRT_MAX << 1);
102 if (i == i_special) {
103 while (i < 6 && pt_len[i] == 0)
110 /* ------------------------------------------------------------------------ */
112 write_c_len(/*void*/)
114 short i, k, n, count;
117 while (n > 0 && c_len[n - 1] == 0)
125 while (i < n && c_len[i] == 0) {
130 for (k = 0; k < count; k++)
131 putcode(pt_len[0], pt_code[0]);
133 else if (count <= 18) {
134 putcode(pt_len[1], pt_code[1]);
135 putbits(4, count - 3);
137 else if (count == 19) {
138 putcode(pt_len[0], pt_code[0]);
139 putcode(pt_len[1], pt_code[1]);
143 putcode(pt_len[2], pt_code[2]);
144 putbits(CBIT, count - 20);
148 putcode(pt_len[k + 2], pt_code[k + 2]);
152 /* ------------------------------------------------------------------------ */
157 putcode(c_len[c], c_code[c]);
160 /* ------------------------------------------------------------------------ */
173 putcode(pt_len[c], pt_code[c]);
178 /* ------------------------------------------------------------------------ */
180 send_block( /* void */ )
183 unsigned short i, k, root, pos, size;
185 root = make_tree(NC, c_freq, c_len, c_code);
190 root = make_tree(NT, t_freq, pt_len, pt_code);
192 write_pt_len(NT, TBIT, 3);
204 root = make_tree(np, p_freq, pt_len, pt_code);
206 write_pt_len(np, pbit, -1);
213 for (i = 0; i < size; i++) {
214 if (i % CHAR_BIT == 0)
218 if (flags & (1 << (CHAR_BIT - 1))) {
219 encode_c(buf[pos++] + (1 << CHAR_BIT));
220 k = buf[pos++] << CHAR_BIT;
224 encode_c(buf[pos++]);
228 for (i = 0; i < NC; i++)
230 for (i = 0; i < np; i++)
234 /* ------------------------------------------------------------------------ */
241 static unsigned short cpos;
244 if (output_mask == 0) {
245 output_mask = 1 << (CHAR_BIT - 1);
246 if (output_pos >= bufsiz - 3 * CHAR_BIT) {
255 buf[output_pos++] = (unsigned char) c;
257 if (c >= (1 << CHAR_BIT)) {
258 buf[cpos] |= output_mask;
259 buf[output_pos++] = (unsigned char) (p >> CHAR_BIT);
260 buf[output_pos++] = (unsigned char) p;
270 /* ------------------------------------------------------------------------ */
272 alloc_buf( /* void */ )
274 bufsiz = 16 * 1024 *2; /* 65408U; */ /* t.okamoto */
275 while ((buf = (unsigned char *) malloc(bufsiz)) == NULL) {
276 bufsiz = (bufsiz / 10) * 9;
277 if (bufsiz < 4 * 1024)
278 fatal_error("Not enough memory");
283 /* ------------------------------------------------------------------------ */
286 encode_start_st1( /* void */ )
292 case LZHUFF5_DICBIT: pbit = 4; np = LZHUFF5_DICBIT + 1; break;
293 case LZHUFF6_DICBIT: pbit = 5; np = LZHUFF6_DICBIT + 1; break;
294 case LZHUFF7_DICBIT: pbit = 5; np = LZHUFF7_DICBIT + 1; break;
296 fatal_error("Cannot use %d bytes dictionary", 1 << dicbit);
299 for (i = 0; i < NC; i++)
301 for (i = 0; i < np; i++)
303 output_pos = output_mask = 0;
309 /* ------------------------------------------------------------------------ */
312 encode_end_st1( /* void */ )
316 putbits(CHAR_BIT - 1, 0); /* flush remaining bits */
320 /* ------------------------------------------------------------------------ */
322 /* ------------------------------------------------------------------------ */
324 read_pt_len(nn, nbit, i_special)
334 for (i = 0; i < nn; i++)
336 for (i = 0; i < 256; i++)
346 unsigned short mask = 1 << (16 - 4);
347 while (mask & bitbuf) {
355 if (i == i_special) {
363 make_table(nn, pt_len, 8, pt_table);
367 /* ------------------------------------------------------------------------ */
369 read_c_len( /* void */ )
376 for (i = 0; i < NC; i++)
378 for (i = 0; i < 4096; i++)
383 c = pt_table[peekbits(8)];
385 unsigned short mask = 1 << (16 - 9);
401 c = getbits(CBIT) + 20;
410 make_table(NC, c_len, 12, c_table);
414 /* ------------------------------------------------------------------------ */
417 decode_c_st1( /*void*/ )
419 unsigned short j, mask;
421 if (blocksize == 0) {
422 blocksize = getbits(16);
423 read_pt_len(NT, TBIT, 3);
425 read_pt_len(np, pbit, -1);
428 j = c_table[peekbits(12)];
433 mask = 1 << (16 - 1);
441 fillbuf(c_len[j] - 12);
446 /* ------------------------------------------------------------------------ */
449 decode_p_st1( /* void */ )
451 unsigned short j, mask;
453 j = pt_table[peekbits(8)];
458 mask = 1 << (16 - 1);
466 fillbuf(pt_len[j] - 8);
469 j = (1 << (j - 1)) + getbits(j - 1);
473 /* ------------------------------------------------------------------------ */
476 decode_start_st1( /* void */ )
480 case LZHUFF5_DICBIT: pbit = 4; np = LZHUFF5_DICBIT + 1; break;
481 case LZHUFF6_DICBIT: pbit = 5; np = LZHUFF6_DICBIT + 1; break;
482 case LZHUFF7_DICBIT: pbit = 5; np = LZHUFF7_DICBIT + 1; break;
484 fatal_error("Cannot use %d bytes dictionary", 1 << dicbit);