1 /* ------------------------------------------------------------------------ */
3 /* dhuf.c -- Dynamic Hufffman routine */
5 /* Modified H.Yoshizaki */
7 /* Ver. 1.14 Source All chagned 1995.01.14 N.Watazaki */
8 /* ------------------------------------------------------------------------ */
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[..] */
16 static unsigned short freq[TREESIZE];
18 static unsigned short total_p;
20 static int most_p, nn;
21 static unsigned long nextcount;
22 /* ------------------------------------------------------------------------ */
24 start_c_dyn( /* void */ )
28 n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;
29 for (i = 0; i < TREESIZE_C; i++) {
33 for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--) {
43 f = freq[j] = freq[i] + freq[i - 1];
45 parent[i] = parent[i - 1] = j;
46 if (f == freq[j + 1]) {
47 edge[block[j] = block[j + 1]] = j;
50 edge[block[j] = stock[avail++]] = j;
57 /* ------------------------------------------------------------------------ */
59 start_p_dyn( /* void */ )
62 child[ROOT_P] = ~(N_CHAR);
63 s_node[N_CHAR] = ROOT_P;
64 edge[block[ROOT_P] = stock[avail++]] = ROOT_P;
71 /* ------------------------------------------------------------------------ */
73 decode_start_dyn( /* void */ )
83 /* ------------------------------------------------------------------------ */
92 for (i = j = start; i < end; i++) {
93 if ((k = child[i]) < 0) {
94 freq[j] = (freq[i] + 1) / 2;
98 if (edge[b = block[i]] == i) {
111 f = freq[l] + freq[l + 1];
112 for (k = start; f < freq[k]; k++);
124 for (i = start; i < end; i++) {
125 if ((j = child[i]) < 0)
128 parent[j] = parent[j - 1] = i;
129 if ((g = freq[i]) == f) {
133 edge[b = block[i] = stock[avail++]] = i;
139 /* ------------------------------------------------------------------------ */
147 if ((q = edge[b]) != p) { /* swap for leader */
153 parent[r] = parent[r - 1] = q;
157 parent[s] = parent[s - 1] = p;
163 else if (b == block[p + 1]) {
166 if (++freq[p] == freq[p - 1]) {
167 block[p] = block[p - 1];
170 edge[block[p] = stock[avail++]] = p; /* create block */
173 else if (++freq[p] == freq[p - 1]) {
174 stock[--avail] = b; /* delete block */
175 block[p] = block[p - 1];
180 /* ------------------------------------------------------------------------ */
187 if (freq[ROOT_C] == 0x8000) {
188 reconst(0, n_max * 2 - 1);
194 } while (q != ROOT_C);
197 /* ------------------------------------------------------------------------ */
204 if (total_p == 0x8000) {
205 reconst(ROOT_P, most_p + 1);
206 total_p = freq[ROOT_P];
207 freq[ROOT_P] = 0xffff;
209 q = s_node[p + N_CHAR];
210 while (q != ROOT_P) {
216 /* ------------------------------------------------------------------------ */
225 s_node[~(child[r] = child[most_p])] = r;
226 child[q] = ~(p + N_CHAR);
228 freq[r] = freq[most_p];
230 block[r] = block[most_p];
231 if (most_p == ROOT_P) {
232 freq[ROOT_P] = 0xffff;
233 edge[block[ROOT_P]]++;
235 parent[r] = parent[q] = most_p;
236 edge[block[q] = stock[avail++]] = s_node[p + N_CHAR] = most_p = q;
240 /* ------------------------------------------------------------------------ */
260 } while ((p = parent[p]) != ROOT_C);
262 putcode(cnt, bits >> 16);
264 putcode(16, bits >> 16);
265 putbits(cnt - 16, bits);
272 /* ------------------------------------------------------------------------ */
274 decode_c_dyn( /* void */ )
283 c = child[c - (buf < 0)];
299 /* ------------------------------------------------------------------------ */
301 decode_p_dyn( /* void */ )
306 while (count > nextcount) {
307 make_new_node(nextcount / 64);
308 if ((nextcount += 64) >= nn)
309 nextcount = 0xffffffff;
315 c = child[c - (buf < 0)];
327 return (c << 6) + getbits(6);
330 /* ------------------------------------------------------------------------ */
332 output_dyn(code, pos)
342 /* ------------------------------------------------------------------------ */
344 encode_end_dyn( /* void */ )
349 /* Local Variables: */
353 /* vi: set tabstop=4: */