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 /* ------------------------------------------------------------------------ */
74 decode_start_dyn( /* void */ )
84 /* ------------------------------------------------------------------------ */
93 for (i = j = start; i < end; i++) {
94 if ((k = child[i]) < 0) {
95 freq[j] = (freq[i] + 1) / 2;
99 if (edge[b = block[i]] == i) {
112 f = freq[l] + freq[l + 1];
113 for (k = start; f < freq[k]; k++);
125 for (i = start; i < end; i++) {
126 if ((j = child[i]) < 0)
129 parent[j] = parent[j - 1] = i;
130 if ((g = freq[i]) == f) {
134 edge[b = block[i] = stock[avail++]] = i;
140 /* ------------------------------------------------------------------------ */
148 if ((q = edge[b]) != p) { /* swap for leader */
154 parent[r] = parent[r - 1] = q;
158 parent[s] = parent[s - 1] = p;
164 else if (b == block[p + 1]) {
167 if (++freq[p] == freq[p - 1]) {
168 block[p] = block[p - 1];
171 edge[block[p] = stock[avail++]] = p; /* create block */
174 else if (++freq[p] == freq[p - 1]) {
175 stock[--avail] = b; /* delete block */
176 block[p] = block[p - 1];
181 /* ------------------------------------------------------------------------ */
188 if (freq[ROOT_C] == 0x8000) {
189 reconst(0, n_max * 2 - 1);
195 } while (q != ROOT_C);
198 /* ------------------------------------------------------------------------ */
205 if (total_p == 0x8000) {
206 reconst(ROOT_P, most_p + 1);
207 total_p = freq[ROOT_P];
208 freq[ROOT_P] = 0xffff;
210 q = s_node[p + N_CHAR];
211 while (q != ROOT_P) {
217 /* ------------------------------------------------------------------------ */
226 s_node[~(child[r] = child[most_p])] = r;
227 child[q] = ~(p + N_CHAR);
229 freq[r] = freq[most_p];
231 block[r] = block[most_p];
232 if (most_p == ROOT_P) {
233 freq[ROOT_P] = 0xffff;
234 edge[block[ROOT_P]]++;
236 parent[r] = parent[q] = most_p;
237 edge[block[q] = stock[avail++]] = s_node[p + N_CHAR] = most_p = q;
241 /* ------------------------------------------------------------------------ */
261 } while ((p = parent[p]) != ROOT_C);
263 putcode(cnt, bits >> 16);
265 putcode(16, bits >> 16);
266 putbits(cnt - 16, bits);
273 /* ------------------------------------------------------------------------ */
276 decode_c_dyn( /* void */ )
285 c = child[c - (buf < 0)];
301 /* ------------------------------------------------------------------------ */
304 decode_p_dyn( /* void */ )
309 while (count > nextcount) {
310 make_new_node(nextcount / 64);
311 if ((nextcount += 64) >= nn)
312 nextcount = 0xffffffff;
318 c = child[c - (buf < 0)];
330 return (c << 6) + getbits(6);
333 /* ------------------------------------------------------------------------ */
336 output_dyn(code, pos)
346 /* ------------------------------------------------------------------------ */
349 encode_end_dyn( /* void */ )