1 /*$Source: /usr/home/dhesi/zoo/RCS/huf.c,v $*/
2 /*$Id: huf.c,v 1.9 91/07/09 01:39:55 dhesi Exp $*/
3 /***********************************************************
4 huf.c -- static Huffman
5
6 Adapted from "ar" archiver written by Haruhiko Okumura.
7 ***********************************************************/
8 #ifdef ANSI_HDRS
9 # include <stdlib.h>
10 #endif
11
12 #include "options.h"
13 #include "zoo.h"
14 #include "ar.h"
15 #include "lzh.h"
16 #include "errors.i"
17
18 extern void prterror();
19
20 #define NP (DICBIT + 1)
21 #define NT (CODE_BIT + 3)
22 #define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */
23 #define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */
24 #if NT > NP
25 # define NPT NT
26 #else
27 # define NPT NP
28 #endif
29
30 int decoded; /* for use in decode.c */
31
32 ushort left[2 * NC - 1], right[2 * NC - 1];
33 static uchar *buf, c_len[NC], pt_len[NPT];
34 static uint bufsiz = 0, blocksize;
35 static ushort c_freq[2 * NC - 1], c_table[4096], c_code[NC],
36 p_freq[2 * NP - 1], pt_table[256], pt_code[NPT],
37 t_freq[2 * NT - 1];
38
39 /***** encoding *****/
40
count_t_freq()41 static void count_t_freq()
42 {
43 int i, k, n, count;
44
45 for (i = 0; i < NT; i++) t_freq[i] = 0;
46 n = NC;
47 while (n > 0 && c_len[n - 1] == 0) n--;
48 i = 0;
49 while (i < n) {
50 k = c_len[i++];
51 if (k == 0) {
52 count = 1;
53 while (i < n && c_len[i] == 0) { i++; count++; }
54 if (count <= 2) t_freq[0] += count;
55 else if (count <= 18) t_freq[1]++;
56 else if (count == 19) { t_freq[0]++; t_freq[1]++; }
57 else t_freq[2]++;
58 } else t_freq[k + 2]++;
59 }
60 }
61
write_pt_len(n,nbit,i_special)62 static void write_pt_len(n, nbit, i_special)
63 int n;
64 int nbit;
65 int i_special;
66 {
67 int i, k;
68
69 while (n > 0 && pt_len[n - 1] == 0) n--;
70 putbits(nbit, (uint) n);
71 i = 0;
72 while (i < n) {
73 k = pt_len[i++];
74 if (k <= 6) putbits(3, (uint) k);
75 else putbits(k - 3, (uint) (((unsigned) 1 << (k - 3)) - 2));
76 if (i == i_special) {
77 while (i < 6 && pt_len[i] == 0) i++;
78 putbits(2, (uint) ((i - 3) & 3));
79 }
80 }
81 }
82
write_c_len()83 static void write_c_len()
84 {
85 int i, k, n, count;
86
87 n = NC;
88 while (n > 0 && c_len[n - 1] == 0) n--;
89 putbits(CBIT, (uint) n);
90 i = 0;
91 while (i < n) {
92 k = c_len[i++];
93 if (k == 0) {
94 count = 1;
95 while (i < n && c_len[i] == 0) { i++; count++; }
96 if (count <= 2) {
97 for (k = 0; k < count; k++)
98 putbits((int) pt_len[0], (uint) pt_code[0]);
99 } else if (count <= 18) {
100 putbits((int) pt_len[1], (uint) pt_code[1]);
101 putbits(4, (uint) (count - 3));
102 } else if (count == 19) {
103 putbits((int) pt_len[0], (uint) pt_code[0]);
104 putbits((int) pt_len[1], (uint) pt_code[1]);
105 putbits(4, 15);
106 } else {
107 putbits((int) pt_len[2], (uint) pt_code[2]);
108 putbits(CBIT, (uint) (count - 20));
109 }
110 } else putbits((int) pt_len[k + 2], (uint) pt_code[k + 2]);
111 }
112 }
113
encode_c(c)114 static void encode_c(c)
115 int c;
116 {
117 putbits((int) c_len[c], (uint) c_code[c]);
118 }
119
encode_p(p)120 static void encode_p(p)
121 uint p;
122 {
123 uint c, q;
124
125 c = 0; q = p; while (q) { q >>= 1; c++; }
126 putbits((int) pt_len[c], (uint) pt_code[c]);
127 if (c > 1) putbits((int) (c - 1), (uint) (p & ((unsigned) 0xFFFF >> (17 - c))));
128 }
129
send_block()130 static void send_block()
131 {
132 uint i, k, flags, root, pos, size;
133
134 root = make_tree(NC, c_freq, c_len, c_code);
135 size = c_freq[root];
136 #if 0
137 /*debug*/ (void) fprintf(stderr, "\nsize = %u\n", size);
138 #endif
139 putbits(16, size);
140 if (root >= NC) {
141 count_t_freq();
142 root = make_tree(NT, t_freq, pt_len, pt_code);
143 if (root >= NT) {
144 write_pt_len(NT, TBIT, 3);
145 } else {
146 putbits(TBIT, 0); putbits(TBIT, root);
147 }
148 write_c_len();
149 } else {
150 putbits(TBIT, 0); putbits(TBIT, 0);
151 putbits(CBIT, 0); putbits(CBIT, root);
152 }
153 root = make_tree(NP, p_freq, pt_len, pt_code);
154 if (root >= NP) {
155 write_pt_len(NP, PBIT, -1);
156 } else {
157 putbits(PBIT, 0); putbits(PBIT, root);
158 }
159 pos = 0;
160 for (i = 0; i < size; i++) {
161 if (i % CHAR_BIT == 0) flags = buf[pos++]; else flags <<= 1;
162 if (flags & ((unsigned) 1 << (CHAR_BIT - 1))) {
163 encode_c((int) (buf[pos++] + ((unsigned) 1 << CHAR_BIT)));
164 k = buf[pos++] << CHAR_BIT; k += buf[pos++];
165 encode_p(k);
166 } else encode_c((int) buf[pos++]);
167 if (unpackable) return;
168 }
169 for (i = 0; i < NC; i++) c_freq[i] = 0;
170 for (i = 0; i < NP; i++) p_freq[i] = 0;
171 }
172
173 static uint output_pos, output_mask;
174
output(c,p)175 void output(c, p)
176 uint c;
177 uint p;
178 {
179 static uint cpos;
180
181 if ((output_mask >>= 1) == 0) {
182 output_mask = (unsigned) 1 << (CHAR_BIT - 1);
183 if (output_pos >= bufsiz - 3 * CHAR_BIT) {
184 send_block();
185 if (unpackable) return;
186 output_pos = 0;
187 }
188 cpos = output_pos++; buf[cpos] = 0;
189 }
190 buf[output_pos++] = (uchar) c; c_freq[c]++;
191 if (c >= ((unsigned) 1 << CHAR_BIT)) {
192 buf[cpos] |= output_mask;
193 buf[output_pos++] = (uchar)(p >> CHAR_BIT);
194 buf[output_pos++] = (uchar) p;
195 c = 0; while (p) { p >>= 1; c++; }
196 p_freq[c]++;
197 }
198 }
199
huf_encode_start()200 void huf_encode_start()
201 {
202 int i;
203
204 if (bufsiz == 0) {
205 bufsiz = 16 * (unsigned) 1024;
206 while ((buf = (uchar *) malloc(bufsiz)) == NULL) {
207 bufsiz = (bufsiz / (unsigned) 10) * (unsigned) 9;
208 if (bufsiz < 4 * (unsigned) 1024)
209 prterror('f', no_memory);
210 }
211 }
212 buf[0] = 0;
213 for (i = 0; i < NC; i++) c_freq[i] = 0;
214 for (i = 0; i < NP; i++) p_freq[i] = 0;
215 output_pos = output_mask = 0;
216 init_putbits();
217 }
218
huf_encode_end()219 void huf_encode_end()
220 {
221 if (! unpackable) {
222 send_block();
223 putbits(CHAR_BIT - 1, 0); /* flush remaining bits */
224 putbits(16, 0); /* EOF marker */
225 }
226 }
227
228 /***** decoding *****/
229
read_pt_len(nn,nbit,i_special)230 static void read_pt_len(nn, nbit, i_special)
231 int nn;
232 int nbit;
233 int i_special;
234 {
235 int i, c, n;
236 uint mask;
237
238 n = getbits(nbit);
239 if (n == 0) {
240 c = getbits(nbit);
241 for (i = 0; i < nn; i++) pt_len[i] = 0;
242 for (i = 0; i < 256; i++) pt_table[i] = c;
243 } else {
244 i = 0;
245 while (i < n) {
246 c = bitbuf >> (BITBUFSIZ - 3);
247 if (c == 7) {
248 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
249 while (mask & bitbuf) { mask >>= 1; c++; }
250 }
251 fillbuf((c < 7) ? 3 : c - 3);
252 pt_len[i++] = c;
253 if (i == i_special) {
254 c = getbits(2);
255 while (--c >= 0) pt_len[i++] = 0;
256 }
257 }
258 while (i < nn) pt_len[i++] = 0;
259 make_table(nn, pt_len, 8, pt_table);
260 }
261 }
262
read_c_len()263 static void read_c_len()
264 {
265 int i, c, n;
266 uint mask;
267
268 n = getbits(CBIT);
269 if (n == 0) {
270 c = getbits(CBIT);
271 for (i = 0; i < NC; i++) c_len[i] = 0;
272 for (i = 0; i < 4096; i++) c_table[i] = c;
273 } else {
274 i = 0;
275 while (i < n) {
276 c = pt_table[bitbuf >> (BITBUFSIZ - 8)];
277 if (c >= NT) {
278 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
279 do {
280 if (bitbuf & mask) c = right[c];
281 else c = left [c];
282 mask >>= 1;
283 } while (c >= NT);
284 }
285 fillbuf((int) pt_len[c]);
286 if (c <= 2) {
287 if (c == 0) c = 1;
288 else if (c == 1) c = getbits(4) + 3;
289 else c = getbits(CBIT) + 20;
290 while (--c >= 0) c_len[i++] = 0;
291 } else c_len[i++] = c - 2;
292 }
293 while (i < NC) c_len[i++] = 0;
294 make_table(NC, c_len, 12, c_table);
295 }
296 }
297
decode_c()298 uint decode_c()
299 {
300 uint j, mask;
301
302 if (blocksize == 0) {
303 blocksize = getbits(16);
304 if (blocksize == 0) {
305 #if 0
306 (void) fprintf(stderr, "block size = 0, decoded\n"); /* debug */
307 #endif
308 decoded = 1;
309 return 0;
310 }
311 read_pt_len(NT, TBIT, 3);
312 read_c_len();
313 read_pt_len(NP, PBIT, -1);
314 }
315 blocksize--;
316 j = c_table[bitbuf >> (BITBUFSIZ - 12)];
317 if (j >= NC) {
318 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
319 do {
320 if (bitbuf & mask) j = right[j];
321 else j = left [j];
322 mask >>= 1;
323 } while (j >= NC);
324 }
325 fillbuf((int) c_len[j]);
326 return j;
327 }
328
decode_p()329 uint decode_p()
330 {
331 uint j, mask;
332
333 j = pt_table[bitbuf >> (BITBUFSIZ - 8)];
334 if (j >= NP) {
335 mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
336 do {
337 if (bitbuf & mask) j = right[j];
338 else j = left [j];
339 mask >>= 1;
340 } while (j >= NP);
341 }
342 fillbuf((int) pt_len[j]);
343 if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1));
344 return j;
345 }
346
huf_decode_start()347 void huf_decode_start()
348 {
349 init_getbits(); blocksize = 0;
350 }
351