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
start_c_dyn()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
start_p_dyn()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
decode_start_dyn()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
reconst(start,end)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
swap_inc(p)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
update_c(p)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
update_p(p)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
make_new_node(p)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
encode_c_dyn(c)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
decode_c_dyn()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
decode_p_dyn()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
output_dyn(code,pos)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
encode_end_dyn()341 encode_end_dyn( /* void */ )
342 {
343 putcode(7, 0);
344 }
345
346 /* Local Variables: */
347 /* mode:c */
348 /* tab-width:4 */
349 /* End: */
350