OSDN Git Service

merged changing from lha-1.14f to lha-1.14i.
[lha/lha.git] / src / dhuf.c
1 /* ------------------------------------------------------------------------ */
2 /* LHa for UNIX                                                                                                                         */
3 /*                              dhuf.c -- Dynamic Hufffman routine                                                      */
4 /*                                                                                                                                                      */
5 /*              Modified                        H.Yoshizaki                                                                     */
6 /*                                                                                                                                                      */
7 /*      Ver. 1.14       Source All chagned                              1995.01.14      N.Watazaki              */
8 /* ------------------------------------------------------------------------ */
9 #include "lha.h"
10
11 /* ------------------------------------------------------------------------ */
12 static short    child[TREESIZE], parent[TREESIZE], block[TREESIZE], edge[TREESIZE], stock[TREESIZE],
13                 s_node[TREESIZE / 2];   /* Changed N.Watazaki */
14 /*      node[..] -> s_node[..] */
15
16 static unsigned short freq[TREESIZE];
17
18 static unsigned short total_p;
19 static int      avail, n1;
20 static int      most_p, nn;
21 static unsigned long nextcount;
22 /* ------------------------------------------------------------------------ */
23 void
24 start_c_dyn( /* void */ )
25 {
26         int             i, j, f;
27
28         n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;
29         for (i = 0; i < TREESIZE_C; i++) {
30                 stock[i] = i;
31                 block[i] = 0;
32         }
33         for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--) {
34                 freq[j] = 1;
35                 child[j] = ~i;
36                 s_node[i] = j;
37                 block[j] = 1;
38         }
39         avail = 2;
40         edge[1] = n_max - 1;
41         i = n_max * 2 - 2;
42         while (j >= 0) {
43                 f = freq[j] = freq[i] + freq[i - 1];
44                 child[j] = i;
45                 parent[i] = parent[i - 1] = j;
46                 if (f == freq[j + 1]) {
47                         edge[block[j] = block[j + 1]] = j;
48                 }
49                 else {
50                         edge[block[j] = stock[avail++]] = j;
51                 }
52                 i -= 2;
53                 j--;
54         }
55 }
56
57 /* ------------------------------------------------------------------------ */
58 static void
59 start_p_dyn( /* void */ )
60 {
61         freq[ROOT_P] = 1;
62         child[ROOT_P] = ~(N_CHAR);
63         s_node[N_CHAR] = ROOT_P;
64         edge[block[ROOT_P] = stock[avail++]] = ROOT_P;
65         most_p = ROOT_P;
66         total_p = 0;
67         nn = 1 << dicbit;
68         nextcount = 64;
69 }
70
71 /* ------------------------------------------------------------------------ */
72 void
73 decode_start_dyn( /* void */ )
74 {
75         n_max = 286;
76         maxmatch = MAXMATCH;
77         init_getbits();
78         start_c_dyn();
79         start_p_dyn();
80 }
81
82 /* ------------------------------------------------------------------------ */
83 static void
84 reconst(start, end)
85         int             start;
86         int             end;
87 {
88         int             i, j, k, l, b;
89         unsigned int    f, g;
90
91         for (i = j = start; i < end; i++) {
92                 if ((k = child[i]) < 0) {
93                         freq[j] = (freq[i] + 1) / 2;
94                         child[j] = k;
95                         j++;
96                 }
97                 if (edge[b = block[i]] == i) {
98                         stock[--avail] = b;
99                 }
100         }
101         j--;
102         i = end - 1;
103         l = end - 2;
104         while (i >= start) {
105                 while (i >= l) {
106                         freq[i] = freq[j];
107                         child[i] = child[j];
108                         i--, j--;
109                 }
110                 f = freq[l] + freq[l + 1];
111                 for (k = start; f < freq[k]; k++);
112                 while (j >= k) {
113                         freq[i] = freq[j];
114                         child[i] = child[j];
115                         i--, j--;
116                 }
117                 freq[i] = f;
118                 child[i] = l + 1;
119                 i--;
120                 l -= 2;
121         }
122         f = 0;
123         for (i = start; i < end; i++) {
124                 if ((j = child[i]) < 0)
125                         s_node[~j] = i;
126                 else
127                         parent[j] = parent[j - 1] = i;
128                 if ((g = freq[i]) == f) {
129                         block[i] = b;
130                 }
131                 else {
132                         edge[b = block[i] = stock[avail++]] = i;
133                         f = g;
134                 }
135         }
136 }
137
138 /* ------------------------------------------------------------------------ */
139 static int
140 swap_inc(p)
141         int             p;
142 {
143         int             b, q, r, s;
144
145         b = block[p];
146         if ((q = edge[b]) != p) {       /* swap for leader */
147                 r = child[p];
148                 s = child[q];
149                 child[p] = s;
150                 child[q] = r;
151                 if (r >= 0)
152                         parent[r] = parent[r - 1] = q;
153                 else
154                         s_node[~r] = q;
155                 if (s >= 0)
156                         parent[s] = parent[s - 1] = p;
157                 else
158                         s_node[~s] = p;
159                 p = q;
160                 goto Adjust;
161         }
162         else if (b == block[p + 1]) {
163 Adjust:
164                 edge[b]++;
165                 if (++freq[p] == freq[p - 1]) {
166                         block[p] = block[p - 1];
167                 }
168                 else {
169                         edge[block[p] = stock[avail++]] = p;    /* create block */
170                 }
171         }
172         else if (++freq[p] == freq[p - 1]) {
173                 stock[--avail] = b;     /* delete block */
174                 block[p] = block[p - 1];
175         }
176         return parent[p];
177 }
178
179 /* ------------------------------------------------------------------------ */
180 static void
181 update_c(p)
182         int             p;
183 {
184         int             q;
185
186         if (freq[ROOT_C] == 0x8000) {
187                 reconst(0, n_max * 2 - 1);
188         }
189         freq[ROOT_C]++;
190         q = s_node[p];
191         do {
192                 q = swap_inc(q);
193         } while (q != ROOT_C);
194 }
195
196 /* ------------------------------------------------------------------------ */
197 static void
198 update_p(p)
199         int             p;
200 {
201         int             q;
202
203         if (total_p == 0x8000) {
204                 reconst(ROOT_P, most_p + 1);
205                 total_p = freq[ROOT_P];
206                 freq[ROOT_P] = 0xffff;
207         }
208         q = s_node[p + N_CHAR];
209         while (q != ROOT_P) {
210                 q = swap_inc(q);
211         }
212         total_p++;
213 }
214
215 /* ------------------------------------------------------------------------ */
216 static void
217 make_new_node(p)
218         int             p;
219 {
220         int             q, r;
221
222         r = most_p + 1;
223         q = r + 1;
224         s_node[~(child[r] = child[most_p])] = r;
225         child[q] = ~(p + N_CHAR);
226         child[most_p] = q;
227         freq[r] = freq[most_p];
228         freq[q] = 0;
229         block[r] = block[most_p];
230         if (most_p == ROOT_P) {
231                 freq[ROOT_P] = 0xffff;
232                 edge[block[ROOT_P]]++;
233         }
234         parent[r] = parent[q] = most_p;
235         edge[block[q] = stock[avail++]] = s_node[p + N_CHAR] = most_p = q;
236         update_p(p);
237 }
238
239 /* ------------------------------------------------------------------------ */
240 static void
241 encode_c_dyn(c)
242         unsigned int    c;
243 {
244         unsigned int    bits;
245         int             p, d, cnt;
246
247         d = c - n1;
248         if (d >= 0) {
249                 c = n1;
250         }
251         cnt = bits = 0;
252         p = s_node[c];
253         do {
254                 bits >>= 1;
255                 if (p & 1) {
256                         bits |= 0x8000;
257                 }
258                 if (++cnt == 16) {
259                         putcode(16, bits);
260                         cnt = bits = 0;
261                 }
262         } while ((p = parent[p]) != ROOT_C);
263         putcode(cnt, bits);
264         if (d >= 0)
265                 putbits(8, d);
266         update_c(c);
267 }
268
269 /* ------------------------------------------------------------------------ */
270 unsigned short
271 decode_c_dyn( /* void */ )
272 {
273         int             c;
274         short           buf, cnt;
275
276         c = child[ROOT_C];
277         buf = bitbuf;
278         cnt = 0;
279         do {
280                 c = child[c - (buf < 0)];
281                 buf <<= 1;
282                 if (++cnt == 16) {
283                         fillbuf(16);
284                         buf = bitbuf;
285                         cnt = 0;
286                 }
287         } while (c > 0);
288         fillbuf(cnt);
289         c = ~c;
290         update_c(c);
291         if (c == n1)
292                 c += getbits(8);
293         return c;
294 }
295
296 /* ------------------------------------------------------------------------ */
297 unsigned short
298 decode_p_dyn( /* void */ )
299 {
300         int             c;
301         short           buf, cnt;
302
303         while (count > nextcount) {
304                 make_new_node(nextcount / 64);
305                 if ((nextcount += 64) >= nn)
306                         nextcount = 0xffffffff;
307         }
308         c = child[ROOT_P];
309         buf = bitbuf;
310         cnt = 0;
311         while (c > 0) {
312                 c = child[c - (buf < 0)];
313                 buf <<= 1;
314                 if (++cnt == 16) {
315                         fillbuf(16);
316                         buf = bitbuf;
317                         cnt = 0;
318                 }
319         }
320         fillbuf(cnt);
321         c = (~c) - N_CHAR;
322         update_p(c);
323
324         return (c << 6) + getbits(6);
325 }
326
327 /* ------------------------------------------------------------------------ */
328 void
329 output_dyn(code, pos)
330         unsigned int    code;
331         unsigned int    pos;
332 {
333         encode_c_dyn(code);
334         if (code >= 0x100) {
335                 encode_p_st0(pos);
336         }
337 }
338
339 /* ------------------------------------------------------------------------ */
340 void
341 encode_end_dyn( /* void */ )
342 {
343         putcode(7, 0);
344 }
345
346 /* Local Variables: */
347 /* mode:c */
348 /* tab-width:4 */
349 /* End: */