"SfR Fresh" - the SfR Freeware/Shareware Archive 
Member "lha-114i/src/dhuf.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 /* 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: */