Revision | 98706404653b523090ebe92bf776ad90ddf8d68d (tree) |
---|---|
Time | 2008-06-23 14:45:55 |
Author | Koji Arai <jca02266@gmai...> |
Commiter | Koji Arai |
huf.c was refined.
@@ -6,6 +6,22 @@ | ||
6 | 6 | #include <limits.h> |
7 | 7 | #include <sys/types.h> |
8 | 8 | |
9 | +#define MAXDICBIT 16 /* 12(-lh4-) or 13(-lh5-) */ | |
10 | +#define MAXDICSIZ (1U << MAXDICBIT) | |
11 | +#define MATCHBIT 8 /* bits for MAXMATCH - THRESHOLD */ | |
12 | +#define MAXMATCH 256 /* formerly F (not more than UCHAR_MAX + 1) */ | |
13 | +#define THRESHOLD 3 /* choose optimal value */ | |
14 | + | |
15 | +#define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD) | |
16 | + /* alphabet = {0, 1, 2, ..., NC - 1} */ | |
17 | +#define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */ | |
18 | +#define CODE_BIT 16 /* codeword length */ | |
19 | + | |
20 | +#define NP (MAXDICBIT + 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 | + | |
9 | 25 | typedef unsigned char uchar; /* 8 bits or more */ |
10 | 26 | typedef unsigned int uint; /* 16 bits or more */ |
11 | 27 | typedef unsigned short ushort; /* 16 bits or more */ |
@@ -21,6 +37,11 @@ struct lzh_istream { | ||
21 | 37 | |
22 | 38 | /* huf.c */ |
23 | 39 | unsigned int blocksize; |
40 | + | |
41 | + unsigned char c_len[NC]; | |
42 | + unsigned short c_table[4096]; | |
43 | + unsigned char p_len[NP]; | |
44 | + unsigned short p_table[256]; | |
24 | 45 | }; |
25 | 46 | |
26 | 47 | struct lzh_ostream { |
@@ -41,6 +62,9 @@ struct lzh_ostream { | ||
41 | 62 | /* huf.c:output() */ |
42 | 63 | unsigned int output_pos, output_mask; |
43 | 64 | unsigned int cpos; |
65 | + | |
66 | + unsigned short c_freq[2 * NC - 1]; | |
67 | + unsigned short p_freq[2 * NP - 1]; | |
44 | 68 | }; |
45 | 69 | |
46 | 70 | struct lzh_header { |
@@ -101,21 +125,9 @@ extern struct lha_opts opts; | ||
101 | 125 | |
102 | 126 | #define BITBUFSIZ (CHAR_BIT * sizeof(unsigned short)) /* size of bitbuf */ |
103 | 127 | |
104 | -/* encode.c and decode.c */ | |
105 | - | |
106 | -#define MAXDICBIT 16 /* 12(-lh4-) or 13(-lh5-) */ | |
107 | -#define MAXDICSIZ (1U << MAXDICBIT) | |
108 | -#define MATCHBIT 8 /* bits for MAXMATCH - THRESHOLD */ | |
109 | -#define MAXMATCH 256 /* formerly F (not more than UCHAR_MAX + 1) */ | |
110 | -#define THRESHOLD 3 /* choose optimal value */ | |
111 | - | |
112 | 128 | /* huf.c */ |
113 | 129 | |
114 | -#define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD) | |
115 | - /* alphabet = {0, 1, 2, ..., NC - 1} */ | |
116 | -#define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */ | |
117 | -#define CODE_BIT 16 /* codeword length */ | |
118 | - | |
130 | +/* decoding */ | |
119 | 131 | struct huf_t { |
120 | 132 | ushort left[2 * NC - 1], right[2 * NC - 1]; |
121 | 133 | }; |
@@ -10,7 +10,6 @@ extract(struct lzh_istream *rp, int to_file, struct lzh_header *h) | ||
10 | 10 | { |
11 | 11 | FILE *outfile = NULL; |
12 | 12 | unsigned int crc; |
13 | - struct huf_t huf; | |
14 | 13 | |
15 | 14 | if (to_file) { |
16 | 15 | if (memcmp(h->method, "-lhd-", sizeof(h->method)) == 0) { |
@@ -58,6 +57,7 @@ extract(struct lzh_istream *rp, int to_file, struct lzh_header *h) | ||
58 | 57 | unsigned int slide_off = 0; |
59 | 58 | int slide_len = 0; |
60 | 59 | unsigned long remainder = h->origsize; |
60 | + struct huf_t huf; | |
61 | 61 | |
62 | 62 | crc = INIT_CRC; |
63 | 63 | if (opts.method->dicbit != 0) |
@@ -4,38 +4,9 @@ | ||
4 | 4 | #include <stdlib.h> |
5 | 5 | #include "ar.h" |
6 | 6 | |
7 | -#define NP (MAXDICBIT + 1) | |
8 | -#define NT (CODE_BIT + 3) | |
9 | -#define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */ | |
10 | -#define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */ | |
11 | -#if NT > NP | |
12 | -#define NPT NT | |
13 | -#else | |
14 | -#define NPT NP | |
15 | -#endif | |
16 | - | |
17 | 7 | static int np; |
18 | 8 | static int pbit; |
19 | 9 | |
20 | -/* encoding/decoding */ | |
21 | -static uchar c_len[NC], pt_len[NPT]; | |
22 | - | |
23 | -/* encoding */ | |
24 | -static ushort c_freq[2 * NC - 1], c_code[NC]; | |
25 | -static ushort p_freq[2 * NP - 1], pt_code[NPT]; | |
26 | -static ushort t_freq[2 * NT - 1]; | |
27 | - | |
28 | -/* | |
29 | - size frequency bitlength Huffman coding | |
30 | - ----------------------------------------------------------- | |
31 | - NC c_freq c_len c_code | |
32 | - NT t_freq pt_len pt_code | |
33 | - np p_freq pt_len pt_code | |
34 | - */ | |
35 | - | |
36 | -/* decoding */ | |
37 | -static ushort c_table[4096], pt_table[256]; | |
38 | - | |
39 | 10 | static void |
40 | 11 | init_parameter(struct lha_method *m) |
41 | 12 | { |
@@ -46,7 +17,7 @@ init_parameter(struct lha_method *m) | ||
46 | 17 | /***** encoding *****/ |
47 | 18 | |
48 | 19 | static void |
49 | -count_t_freq(void) | |
20 | +count_t_freq(struct lzh_ostream *wp, uchar *c_len, ushort *t_freq) | |
50 | 21 | { |
51 | 22 | int i, k, n, count; |
52 | 23 |
@@ -81,7 +52,8 @@ count_t_freq(void) | ||
81 | 52 | } |
82 | 53 | |
83 | 54 | static void |
84 | -write_pt_len(struct lzh_ostream *wp, int n, int nbit, int i_special) | |
55 | +write_pt_len(struct lzh_ostream *wp, int n, int nbit, int i_special, | |
56 | + uchar *pt_len) | |
85 | 57 | { |
86 | 58 | int i, k; |
87 | 59 |
@@ -104,7 +76,7 @@ write_pt_len(struct lzh_ostream *wp, int n, int nbit, int i_special) | ||
104 | 76 | } |
105 | 77 | |
106 | 78 | static void |
107 | -write_c_len(struct lzh_ostream *wp) | |
79 | +write_c_len(struct lzh_ostream *wp, uchar *c_len, uchar *t_len, ushort *t_code) | |
108 | 80 | { |
109 | 81 | int i, k, n, count; |
110 | 82 |
@@ -123,35 +95,35 @@ write_c_len(struct lzh_ostream *wp) | ||
123 | 95 | } |
124 | 96 | if (count <= 2) { |
125 | 97 | for (k = 0; k < count; k++) |
126 | - putbits(wp, pt_len[0], pt_code[0]); | |
98 | + putbits(wp, t_len[0], t_code[0]); | |
127 | 99 | } |
128 | 100 | else if (count <= 18) { |
129 | - putbits(wp, pt_len[1], pt_code[1]); | |
101 | + putbits(wp, t_len[1], t_code[1]); | |
130 | 102 | putbits(wp, 4, count - 3); |
131 | 103 | } |
132 | 104 | else if (count == 19) { |
133 | - putbits(wp, pt_len[0], pt_code[0]); | |
134 | - putbits(wp, pt_len[1], pt_code[1]); | |
105 | + putbits(wp, t_len[0], t_code[0]); | |
106 | + putbits(wp, t_len[1], t_code[1]); | |
135 | 107 | putbits(wp, 4, 15); |
136 | 108 | } |
137 | 109 | else { |
138 | - putbits(wp, pt_len[2], pt_code[2]); | |
110 | + putbits(wp, t_len[2], t_code[2]); | |
139 | 111 | putbits(wp, CBIT, count - 20); |
140 | 112 | } |
141 | 113 | } |
142 | 114 | else |
143 | - putbits(wp, pt_len[k + 2], pt_code[k + 2]); | |
115 | + putbits(wp, t_len[k + 2], t_code[k + 2]); | |
144 | 116 | } |
145 | 117 | } |
146 | 118 | |
147 | 119 | static void |
148 | -encode_c(struct lzh_ostream *wp, int c) | |
120 | +encode_c(struct lzh_ostream *wp, int c, uchar *c_len, ushort *c_code) | |
149 | 121 | { |
150 | 122 | putbits(wp, c_len[c], c_code[c]); |
151 | 123 | } |
152 | 124 | |
153 | 125 | static void |
154 | -encode_p(struct lzh_ostream *wp, uint p) | |
126 | +encode_p(struct lzh_ostream *wp, uint p, uchar *p_len, ushort *p_code) | |
155 | 127 | { |
156 | 128 | uint c, q; |
157 | 129 |
@@ -161,12 +133,18 @@ encode_p(struct lzh_ostream *wp, uint p) | ||
161 | 133 | q >>= 1; |
162 | 134 | c++; |
163 | 135 | } |
164 | - putbits(wp, pt_len[c], pt_code[c]); | |
136 | + putbits(wp, p_len[c], p_code[c]); | |
165 | 137 | if (c > 1) |
166 | 138 | putbits(wp, c - 1, p & (0xFFFFU >> (17 - c))); |
167 | 139 | } |
168 | 140 | |
169 | 141 | /* |
142 | + size frequency bitlength Huffman coding | |
143 | + ----------------------------------------------------------- | |
144 | + NC c_freq c_len c_code | |
145 | + NT t_freq t_len t_code | |
146 | + np p_freq p_len p_code | |
147 | + | |
170 | 148 | output format for a block. |
171 | 149 | |
172 | 150 | +-----------+ |
@@ -175,7 +153,7 @@ encode_p(struct lzh_ostream *wp, uint p) | ||
175 | 153 | 16bit |
176 | 154 | |
177 | 155 | +-----+--------------------+ |
178 | - | len | pt_len | Huffman tree for c_len[] | |
156 | + | len | t_len | Huffman tree for c_len[] | |
179 | 157 | +-----+--------------------+ |
180 | 158 | 5bit ?? bit |
181 | 159 | TBIT |
@@ -187,7 +165,7 @@ encode_p(struct lzh_ostream *wp, uint p) | ||
187 | 165 | CBIT |
188 | 166 | |
189 | 167 | +---------+--------------------+ |
190 | - | len | pt_len | Huffman tree for offset | |
168 | + | len | p_len | Huffman tree for offset | |
191 | 169 | +---------+--------------------+ |
192 | 170 | pbit ?? bit |
193 | 171 | (pbit=4bit(lh4,5) or 5bit(lh6,7)) |
@@ -232,23 +210,34 @@ send_block(struct lzh_ostream *wp) | ||
232 | 210 | { |
233 | 211 | uint i, k, flags, root, pos, size; |
234 | 212 | |
213 | + uchar c_len[NC]; | |
214 | + ushort c_code[NC]; | |
215 | + | |
216 | + uchar t_len[NT]; | |
217 | + ushort t_code[NT]; | |
218 | + | |
219 | + uchar p_len[NP]; | |
220 | + ushort p_code[NP]; | |
221 | + | |
235 | 222 | /* make Huffman tree for characters and length */ |
236 | - root = make_tree(NC, c_freq, c_len, c_code); | |
237 | - size = c_freq[root]; | |
223 | + root = make_tree(NC, wp->c_freq, c_len, c_code); | |
224 | + size = wp->c_freq[root]; | |
238 | 225 | putbits(wp, 16, size); |
239 | 226 | if (root >= NC) { |
227 | + ushort t_freq[2 * NT - 1]; | |
228 | + | |
240 | 229 | /* make Huffman tree for c_len */ |
241 | - count_t_freq(); | |
242 | - root = make_tree(NT, t_freq, pt_len, pt_code); | |
230 | + count_t_freq(wp, c_len, t_freq); | |
231 | + root = make_tree(NT, t_freq, t_len, t_code); | |
243 | 232 | if (root >= NT) { |
244 | - write_pt_len(wp, NT, TBIT, 3); | |
233 | + write_pt_len(wp, NT, TBIT, 3, t_len); | |
245 | 234 | } |
246 | 235 | else { |
247 | 236 | /* only one kind */ |
248 | 237 | putbits(wp, TBIT, 0); |
249 | 238 | putbits(wp, TBIT, root); |
250 | 239 | } |
251 | - write_c_len(wp); | |
240 | + write_c_len(wp, c_len, t_len, t_code); | |
252 | 241 | } |
253 | 242 | else { |
254 | 243 | /* only one kind */ |
@@ -259,9 +248,9 @@ send_block(struct lzh_ostream *wp) | ||
259 | 248 | } |
260 | 249 | |
261 | 250 | /* make Huffman tree for offset */ |
262 | - root = make_tree(np, p_freq, pt_len, pt_code); | |
251 | + root = make_tree(np, wp->p_freq, p_len, p_code); | |
263 | 252 | if (root >= np) { |
264 | - write_pt_len(wp, np, pbit, -1); | |
253 | + write_pt_len(wp, np, pbit, -1, p_len); | |
265 | 254 | } |
266 | 255 | else { |
267 | 256 | putbits(wp, pbit, 0); |
@@ -277,15 +266,15 @@ send_block(struct lzh_ostream *wp) | ||
277 | 266 | flags <<= 1; |
278 | 267 | if (flags & (1U << (CHAR_BIT - 1))) { |
279 | 268 | /* write length */ |
280 | - encode_c(wp, wp->buf[pos++] + (1U << CHAR_BIT)); | |
269 | + encode_c(wp, wp->buf[pos++] + (1U << CHAR_BIT), c_len, c_code); | |
281 | 270 | /* write offset */ |
282 | 271 | k = wp->buf[pos++] << CHAR_BIT; |
283 | 272 | k += wp->buf[pos++]; |
284 | - encode_p(wp, k); | |
273 | + encode_p(wp, k, p_len, p_code); | |
285 | 274 | } |
286 | 275 | else { |
287 | 276 | /* write character */ |
288 | - encode_c(wp, wp->buf[pos++]); | |
277 | + encode_c(wp, wp->buf[pos++], c_len, c_code); | |
289 | 278 | } |
290 | 279 | if (wp->unpackable) |
291 | 280 | return; |
@@ -293,9 +282,9 @@ send_block(struct lzh_ostream *wp) | ||
293 | 282 | |
294 | 283 | /* clear frequency table */ |
295 | 284 | for (i = 0; i < NC; i++) |
296 | - c_freq[i] = 0; | |
285 | + wp->c_freq[i] = 0; | |
297 | 286 | for (i = 0; i < np; i++) |
298 | - p_freq[i] = 0; | |
287 | + wp->p_freq[i] = 0; | |
299 | 288 | } |
300 | 289 | |
301 | 290 | /* |
@@ -330,7 +319,7 @@ output(struct lzh_ostream *wp, uint c, uint p) | ||
330 | 319 | wp->buf[wp->cpos] = 0; |
331 | 320 | } |
332 | 321 | wp->buf[wp->output_pos++] = (uchar) c; |
333 | - c_freq[c]++; | |
322 | + wp->c_freq[c]++; | |
334 | 323 | |
335 | 324 | if (c >= (1U << CHAR_BIT)) { |
336 | 325 | /* c is length, p is offset */ |
@@ -345,7 +334,7 @@ output(struct lzh_ostream *wp, uint c, uint p) | ||
345 | 334 | p >>= 1; |
346 | 335 | n++; |
347 | 336 | } |
348 | - p_freq[n]++; | |
337 | + wp->p_freq[n]++; | |
349 | 338 | } |
350 | 339 | } |
351 | 340 | } |
@@ -368,9 +357,9 @@ huf_encode_start(struct lzh_ostream *wp, struct lha_method *m) | ||
368 | 357 | } |
369 | 358 | wp->buf[0] = 0; |
370 | 359 | for (i = 0; i < NC; i++) |
371 | - c_freq[i] = 0; | |
360 | + wp->c_freq[i] = 0; | |
372 | 361 | for (i = 0; i < np; i++) |
373 | - p_freq[i] = 0; | |
362 | + wp->p_freq[i] = 0; | |
374 | 363 | |
375 | 364 | init_putbits(wp); |
376 | 365 | } |
@@ -392,7 +381,8 @@ huf_encode_end(struct lzh_ostream *wp) | ||
392 | 381 | /***** decoding *****/ |
393 | 382 | |
394 | 383 | static void |
395 | -read_pt_len(struct huf_t *huf, struct lzh_istream *rp, int nn, int nbit, int i_special) | |
384 | +read_pt_len(struct huf_t *huf, struct lzh_istream *rp, int nn, int nbit, | |
385 | + int i_special, uchar *pt_len, ushort *pt_table) | |
396 | 386 | { |
397 | 387 | int i, c, n; |
398 | 388 | uint mask; |
@@ -431,7 +421,7 @@ read_pt_len(struct huf_t *huf, struct lzh_istream *rp, int nn, int nbit, int i_s | ||
431 | 421 | } |
432 | 422 | |
433 | 423 | static void |
434 | -read_c_len(struct huf_t *huf, struct lzh_istream *rp) | |
424 | +read_c_len(struct huf_t *huf, struct lzh_istream *rp, uchar *t_len, ushort *t_table) | |
435 | 425 | { |
436 | 426 | int i, c, n; |
437 | 427 | uint mask; |
@@ -440,14 +430,14 @@ read_c_len(struct huf_t *huf, struct lzh_istream *rp) | ||
440 | 430 | if (n == 0) { |
441 | 431 | c = getbits(rp, CBIT); |
442 | 432 | for (i = 0; i < NC; i++) |
443 | - c_len[i] = 0; | |
433 | + rp->c_len[i] = 0; | |
444 | 434 | for (i = 0; i < 4096; i++) |
445 | - c_table[i] = c; | |
435 | + rp->c_table[i] = c; | |
446 | 436 | } |
447 | 437 | else { |
448 | 438 | i = 0; |
449 | 439 | while (i < n) { |
450 | - c = pt_table[rp->bitbuf >> (BITBUFSIZ - 8)]; | |
440 | + c = t_table[rp->bitbuf >> (BITBUFSIZ - 8)]; | |
451 | 441 | if (c >= NT) { |
452 | 442 | mask = 1U << (BITBUFSIZ - 1 - 8); |
453 | 443 | do { |
@@ -458,7 +448,7 @@ read_c_len(struct huf_t *huf, struct lzh_istream *rp) | ||
458 | 448 | mask >>= 1; |
459 | 449 | } while (c >= NT); |
460 | 450 | } |
461 | - fillbuf(rp, pt_len[c]); | |
451 | + fillbuf(rp, t_len[c]); | |
462 | 452 | if (c <= 2) { |
463 | 453 | if (c == 0) |
464 | 454 | c = 1; |
@@ -467,14 +457,14 @@ read_c_len(struct huf_t *huf, struct lzh_istream *rp) | ||
467 | 457 | else |
468 | 458 | c = getbits(rp, CBIT) + 20; |
469 | 459 | while (--c >= 0) |
470 | - c_len[i++] = 0; | |
460 | + rp->c_len[i++] = 0; | |
471 | 461 | } |
472 | 462 | else |
473 | - c_len[i++] = c - 2; | |
463 | + rp->c_len[i++] = c - 2; | |
474 | 464 | } |
475 | 465 | while (i < NC) |
476 | - c_len[i++] = 0; | |
477 | - make_table(huf, NC, c_len, 12, c_table); | |
466 | + rp->c_len[i++] = 0; | |
467 | + make_table(huf, NC, rp->c_len, 12, rp->c_table); | |
478 | 468 | } |
479 | 469 | } |
480 | 470 |
@@ -484,13 +474,16 @@ decode_c(struct huf_t *huf, struct lzh_istream *rp) | ||
484 | 474 | uint j, mask; |
485 | 475 | |
486 | 476 | if (rp->blocksize == 0) { |
477 | + uchar t_len[NT]; | |
478 | + unsigned short t_table[256]; | |
479 | + | |
487 | 480 | rp->blocksize = getbits(rp, 16); |
488 | - read_pt_len(huf, rp, NT, TBIT, 3); | |
489 | - read_c_len(huf, rp); | |
490 | - read_pt_len(huf, rp, np, pbit, -1); | |
481 | + read_pt_len(huf, rp, NT, TBIT, 3, t_len, t_table); | |
482 | + read_c_len(huf, rp, t_len, t_table); | |
483 | + read_pt_len(huf, rp, np, pbit, -1, rp->p_len, rp->p_table); | |
491 | 484 | } |
492 | 485 | rp->blocksize--; |
493 | - j = c_table[rp->bitbuf >> (BITBUFSIZ - 12)]; | |
486 | + j = rp->c_table[rp->bitbuf >> (BITBUFSIZ - 12)]; | |
494 | 487 | if (j >= NC) { |
495 | 488 | mask = 1U << (BITBUFSIZ - 1 - 12); |
496 | 489 | do { |
@@ -501,7 +494,7 @@ decode_c(struct huf_t *huf, struct lzh_istream *rp) | ||
501 | 494 | mask >>= 1; |
502 | 495 | } while (j >= NC); |
503 | 496 | } |
504 | - fillbuf(rp, c_len[j]); | |
497 | + fillbuf(rp, rp->c_len[j]); | |
505 | 498 | return j; |
506 | 499 | } |
507 | 500 |
@@ -510,7 +503,7 @@ decode_p(struct huf_t *huf, struct lzh_istream *rp) | ||
510 | 503 | { |
511 | 504 | uint j, mask; |
512 | 505 | |
513 | - j = pt_table[rp->bitbuf >> (BITBUFSIZ - 8)]; | |
506 | + j = rp->p_table[rp->bitbuf >> (BITBUFSIZ - 8)]; | |
514 | 507 | if (j >= np) { |
515 | 508 | mask = 1U << (BITBUFSIZ - 1 - 8); |
516 | 509 | do { |
@@ -521,7 +514,7 @@ decode_p(struct huf_t *huf, struct lzh_istream *rp) | ||
521 | 514 | mask >>= 1; |
522 | 515 | } while (j >= np); |
523 | 516 | } |
524 | - fillbuf(rp, pt_len[j]); | |
517 | + fillbuf(rp, rp->p_len[j]); | |
525 | 518 | if (j != 0) |
526 | 519 | j = (1U << (j - 1)) + getbits(rp, j - 1); |
527 | 520 | return j; |