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