/************************************************************** title dhuf.c *************************************************************** Dynamic Huffman routine H.Yoshizaki **************************************************************/ #include #include "slidehuf.h" #define N_CHAR (256 + 60 - THRESHOLD + 1) #define TREESIZE_C (N_CHAR * 2) #define TREESIZE_P (128 * 2) #define TREESIZE (TREESIZE_C + TREESIZE_P) #define ROOT_C 0 #define ROOT_P TREESIZE_C unsigned int n_max; static short child [TREESIZE], parent[TREESIZE], block [TREESIZE], edge [TREESIZE], stock [TREESIZE], node [TREESIZE / 2]; static unsigned short freq[TREESIZE]; static unsigned short total_p; static int avail, n1; static int most_p, nn; static unsigned long nextcount; void start_c_dyn(void) { int i, j, f; n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1; for (i = 0; i < TREESIZE_C; i++) { stock[i] = i; block[i] = 0; } for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--) { freq[j] = 1; child[j] = ~i; node[i] = j; block[j] = 1; } avail = 2; edge[1] = n_max - 1; i = n_max * 2 - 2; while (j >= 0) { f = freq[j] = freq[i] + freq[i - 1]; child[j] = i; parent[i] = parent[i - 1] = j; if (f == freq[j + 1]) { edge[block[j] = block[j + 1]] = j; } else { edge[block[j] = stock[avail++]] = j; } i -= 2; j--; } } static void start_p_dyn(void) { freq[ROOT_P] = 1; child[ROOT_P] = ~(N_CHAR); node[N_CHAR] = ROOT_P; edge[block[ROOT_P] = stock[avail++]] = ROOT_P; most_p = ROOT_P; total_p = 0; nn = 1 << dicbit; nextcount = 64; } void decode_start_dyn(void) { n_max = 286; maxmatch = MAXMATCH; init_getbits(); start_c_dyn(); start_p_dyn(); } static void reconst( start , end ) int start; int end; { int i, j, k, l, b; unsigned int f, g; for (i = j = start; i < end; i++) { if ((k = child[i]) < 0) { freq[j] = (freq[i] + 1) / 2; child[j] = k; j++; } if (edge[b = block[i]] == i) { stock[--avail] = b; } } j--; i = end - 1; l = end - 2; while (i >= start) { while (i >= l) { freq[i] = freq[j]; child[i] = child[j]; i--, j--; } f = freq[l] + freq[l + 1]; for (k = start; f < freq[k]; k++); while(j >= k) { freq[i] = freq[j]; child[i] = child[j]; i--, j--; } freq[i] = f; child[i] = l + 1; i--; l -= 2; } f = 0; for (i = start; i < end; i++) { if ((j = child[i]) < 0) node[~j] = i; else parent[j] = parent[j - 1] = i; if ((g = freq[i]) == f) { block[i] = b; } else { edge[b = block[i] = stock[avail++]] = i; f = g; } } } static int swap_inc(p) int p; { int b, q, r, s; b = block[p]; if ((q = edge[b]) != p) { /* swap for leader */ r = child[p]; s = child[q]; child[p] = s; child[q] = r; if (r >= 0) parent[r] = parent[r - 1] = q; else node[~r] = q; if (s >= 0) parent[s] = parent[s - 1] = p; else node[~s] = p; p = q; goto Adjust; } else if (b == block[p + 1]) { Adjust: edge[b]++; if (++freq[p] == freq[p - 1]) { block[p] = block[p - 1]; } else { edge[block[p] = stock[avail++]] = p; /* create block */ } } else if (++freq[p] == freq[p - 1]) { stock[--avail] = b; /* delete block */ block[p] = block[p - 1]; } return parent[p]; } static void update_c(p) int p; { int q; if (freq[ROOT_C] == 0x8000) { reconst(0, n_max * 2 - 1); } freq[ROOT_C]++; q = node[p]; do { q = swap_inc(q); } while (q != ROOT_C); } static void update_p(p) int p; { int q; if (total_p == 0x8000) { reconst(ROOT_P, most_p + 1); total_p = freq[ROOT_P]; freq[ROOT_P] = 0xffff; } q = node[p + N_CHAR]; while (q != ROOT_P) { q = swap_inc(q); } total_p++; } static void make_new_node(p) int p; { int q, r; r = most_p + 1; q = r + 1; node[~(child[r] = child[most_p])] = r; child[q] = ~(p + N_CHAR); child[most_p] = q; freq[r] = freq[most_p]; freq[q] = 0; block[r] = block[most_p]; if (most_p == ROOT_P) { freq[ROOT_P] = 0xffff; edge[block[ROOT_P]]++; } parent[r] = parent[q] = most_p; edge[block[q] = stock[avail++]] = node[p + N_CHAR] = most_p = q; update_p(p); } static void encode_c_dyn(c) int c; { unsigned int bits; int p, d, cnt; d = c - n1; if (d >= 0) { c = n1; } cnt = bits = 0; p = node[c]; do { bits >>= 1; if (p & 1) { bits |= 0x8000; } if (++cnt == 16) { putcode(16, bits); cnt = bits = 0; } } while ((p = parent[p]) != ROOT_C); putcode(cnt, bits); if (d >= 0) putbits(8, d); update_c(c); } unsigned short decode_c_dyn(void) { int c; short buf, cnt; c = child[ROOT_C]; buf = bitbuf; cnt = 0; do { c = child[c - (buf < 0)]; buf <<= 1; if (++cnt == 16) { fillbuf(16); buf = bitbuf; cnt = 0; } } while (c > 0); fillbuf(cnt); c = ~c; update_c(c); if (c == n1) c += getbits(8); return c; } unsigned short decode_p_dyn(void) { int c; short buf, cnt; while (count > nextcount) { make_new_node(nextcount / 64); if ((nextcount += 64) >= nn) nextcount = 0xffffffff; } c = child[ROOT_P]; buf = bitbuf; cnt = 0; while (c > 0) { c = child[c - (buf < 0)]; buf <<= 1; if (++cnt == 16) { fillbuf(16); buf = bitbuf; cnt = 0; } } fillbuf(cnt); c = (~c) - N_CHAR; update_p(c); return (c << 6) + getbits(6); } void output_dyn( code , pos ) int code; unsigned int pos; { encode_c_dyn(code); if (code >= 0x100) { encode_p_st0(pos); } } void encode_end_dyn(void) { putcode(7, 0); }