home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / ARCHIVERS / lhasrc.lzh / dhuf.c < prev    next >
Text File  |  1992-05-13  |  7KB  |  325 lines
  1. /**************************************************************
  2.     title   dhuf.c
  3. ***************************************************************
  4.     Dynamic Huffman routine
  5.                                                 H.Yoshizaki
  6. **************************************************************/
  7. #include <stdio.h>
  8. #include "slidehuf.h"
  9.  
  10. #define N_CHAR      (256 + 60 - THRESHOLD + 1)
  11. #define TREESIZE_C  (N_CHAR * 2)
  12. #define TREESIZE_P  (128 * 2)
  13. #define TREESIZE    (TREESIZE_C + TREESIZE_P)
  14. #define ROOT_C      0
  15. #define ROOT_P      TREESIZE_C
  16.  
  17. unsigned int n_max;
  18.  
  19. static short child [TREESIZE],
  20.              parent[TREESIZE],
  21.              block [TREESIZE],
  22.              edge  [TREESIZE],
  23.              stock [TREESIZE],
  24.              node  [TREESIZE / 2];
  25.  
  26. static unsigned short freq[TREESIZE];
  27.  
  28. static unsigned short total_p;
  29. static int avail, n1;
  30. static int most_p, nn;
  31. static unsigned long nextcount;
  32.  
  33. void start_c_dyn()
  34. {
  35.     int i, j, f;
  36.  
  37.     n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;
  38.     for (i = 0; i < TREESIZE_C; i++) {
  39.         stock[i] = i;
  40.         block[i] = 0;
  41.     }
  42.     for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--) {
  43.         freq[j] = 1;
  44.         child[j] = ~i;
  45.         node[i] = j;
  46.         block[j] = 1;
  47.     }
  48.     avail = 2;
  49.     edge[1] = n_max - 1;
  50.     i = n_max * 2 - 2;
  51.     while (j >= 0) {
  52.         f = freq[j] = freq[i] + freq[i - 1];
  53.         child[j] = i;
  54.         parent[i] = parent[i - 1] = j;
  55.         if (f == freq[j + 1]) {
  56.             edge[block[j] = block[j + 1]] = j;
  57.         } 
  58.         else {
  59.             edge[block[j] = stock[avail++]] = j;
  60.         }
  61.         i -= 2;
  62.         j--;
  63.     }
  64. }
  65.  
  66. static void start_p_dyn()
  67. {
  68.     freq[ROOT_P] = 1;
  69.     child[ROOT_P] = ~(N_CHAR);
  70.     node[N_CHAR] = ROOT_P;
  71.     edge[block[ROOT_P] = stock[avail++]] = ROOT_P;
  72.     most_p = ROOT_P;
  73.     total_p = 0;
  74.     nn = 1 << dicbit;
  75.     nextcount = 64;
  76. }
  77.  
  78. void decode_start_dyn()
  79. {
  80.     n_max = 286;
  81.     maxmatch = MAXMATCH;
  82.     init_getbits();
  83.     start_c_dyn();
  84.     start_p_dyn();
  85. }
  86.  
  87. static void reconst( start , end )
  88. int start;
  89. int end;
  90. {
  91.     int i, j, k, l, b;
  92.     unsigned int f, g;
  93.  
  94.     for (i = j = start; i < end; i++) {
  95.         if ((k = child[i]) < 0) {
  96.             freq[j] = (freq[i] + 1) / 2;
  97.             child[j] = k;
  98.             j++;
  99.         }
  100.         if (edge[b = block[i]] == i) {
  101.             stock[--avail] = b;
  102.         }
  103.     }
  104.     j--;
  105.     i = end - 1;
  106.     l = end - 2;
  107.     while (i >= start) {
  108.         while (i >= l) {
  109.             freq[i] = freq[j]; 
  110.             child[i] = child[j];
  111.             i--, j--;
  112.         }
  113.         f = freq[l] + freq[l + 1];
  114.         for (k = start; f < freq[k]; k++);
  115.         while(j >= k) {
  116.             freq[i] = freq[j]; 
  117.             child[i] = child[j];
  118.             i--, j--;
  119.         }
  120.         freq[i] = f; 
  121.         child[i] = l + 1;
  122.         i--;
  123.         l -= 2;
  124.     }
  125.     f = 0;
  126.     for (i = start; i < end; i++) {
  127.         if ((j = child[i]) < 0) node[~j] = i;
  128.         else parent[j] = parent[j - 1] = i;
  129.         if ((g = freq[i]) == f) {
  130.             block[i] = b;
  131.         } 
  132.         else {
  133.             edge[b = block[i] = stock[avail++]] = i;
  134.             f = g;
  135.         }
  136.     }
  137. }
  138.  
  139. static int swap_inc(p)
  140. int p;
  141. {
  142.     int b, q, r, s;
  143.  
  144.     b = block[p];
  145.     if ((q = edge[b]) != p) {    /* swap for leader */
  146.         r = child[p]; 
  147.         s = child[q];
  148.         child[p] = s; 
  149.         child[q] = r;
  150.         if (r >= 0) parent[r] = parent[r - 1] = q;
  151.         else        node[~r] = q;
  152.         if (s >= 0)    parent[s] = parent[s - 1] = p;
  153.         else        node[~s] = p;
  154.         p = q;
  155.         goto Adjust;
  156.     } 
  157.     else if (b == block[p + 1]) {
  158. Adjust:
  159.         edge[b]++;
  160.         if (++freq[p] == freq[p - 1]) {
  161.             block[p] = block[p - 1];
  162.         } 
  163.         else {
  164.             edge[block[p] = stock[avail++]] = p;    /* create block */
  165.         }
  166.     } 
  167.     else if (++freq[p] == freq[p - 1]) {
  168.         stock[--avail] = b;        /* delete block */
  169.         block[p] = block[p - 1];
  170.     }
  171.     return parent[p];
  172. }
  173.  
  174. static void update_c(p)
  175. int p;
  176. {
  177.     int q;
  178.  
  179.     if (freq[ROOT_C] == 0x8000) {
  180.         reconst(0, n_max * 2 - 1);
  181.     }
  182.     freq[ROOT_C]++;
  183.     q = node[p];
  184.     do {
  185.         q = swap_inc(q);
  186.     } 
  187.     while (q != ROOT_C);
  188. }
  189.  
  190. static void update_p(p)
  191. int p;
  192. {
  193.     int q;
  194.  
  195.     if (total_p == 0x8000) {
  196.         reconst(ROOT_P, most_p + 1);
  197.         total_p = freq[ROOT_P];
  198.         freq[ROOT_P] = 0xffff;
  199.     }
  200.     q = node[p + N_CHAR];
  201.     while (q != ROOT_P) {
  202.         q = swap_inc(q);
  203.     }
  204.     total_p++;
  205. }
  206.  
  207. static void make_new_node(p)
  208. int p;
  209. {
  210.     int q, r;
  211.  
  212.     r = most_p + 1; 
  213.     q = r + 1;
  214.     node[~(child[r] = child[most_p])] = r;
  215.     child[q] = ~(p + N_CHAR);
  216.     child[most_p] = q;
  217.     freq[r] = freq[most_p];
  218.     freq[q] = 0;
  219.     block[r] = block[most_p];
  220.     if (most_p == ROOT_P) {
  221.         freq[ROOT_P] = 0xffff;
  222.         edge[block[ROOT_P]]++;
  223.     }
  224.     parent[r] = parent[q] = most_p;
  225.     edge[block[q] = stock[avail++]] = node[p + N_CHAR] = most_p = q;
  226.     update_p(p);
  227. }
  228.  
  229. static void encode_c_dyn(c)
  230. int c;
  231. {
  232.     unsigned int bits;
  233.     int p, d, cnt;
  234.  
  235.     d = c - n1;
  236.     if (d >= 0) {
  237.         c = n1;
  238.     }
  239.     cnt = bits = 0;  
  240.     p = node[c];
  241.     do {
  242.         bits >>= 1;
  243.         if (p & 1) {
  244.             bits |= 0x8000;
  245.         }
  246.         if (++cnt == 16) {
  247.             putcode(16, bits);
  248.             cnt = bits = 0;
  249.         }
  250.     } 
  251.     while ((p = parent[p]) != ROOT_C);
  252.     putcode(cnt, bits);
  253.     if (d >= 0) putbits(8, d);
  254.     update_c(c);
  255. }
  256.  
  257. unsigned short decode_c_dyn()
  258. {
  259.     int c;
  260.     short buf, cnt;
  261.  
  262.     c = child[ROOT_C];
  263.     buf = bitbuf;
  264.     cnt = 0;
  265.     do {
  266.         c = child[c - (buf < 0)];
  267.         buf <<= 1;
  268.         if (++cnt == 16) {
  269.             fillbuf(16);
  270.             buf = bitbuf; 
  271.             cnt = 0;
  272.         }
  273.     } 
  274.     while (c > 0);
  275.     fillbuf(cnt);
  276.     c = ~c;
  277.     update_c(c);
  278.     if (c == n1) c += getbits(8);
  279.     return c;
  280. }
  281.  
  282. unsigned short decode_p_dyn()
  283. {
  284.     int c;
  285.     short buf, cnt;
  286.  
  287.     while (count > nextcount) {
  288.         make_new_node(nextcount / 64);
  289.         if ((nextcount += 64) >= nn)
  290.             nextcount = 0xffffffff;
  291.     }
  292.     c = child[ROOT_P];
  293.     buf = bitbuf; 
  294.     cnt = 0;
  295.     while (c > 0) {
  296.         c = child[c - (buf < 0)];
  297.         buf <<= 1;
  298.         if (++cnt == 16) {
  299.             fillbuf(16);
  300.             buf = bitbuf; 
  301.             cnt = 0;
  302.         }
  303.     }
  304.     fillbuf(cnt);
  305.     c = (~c) - N_CHAR;
  306.     update_p(c);
  307.  
  308.     return (c << 6) + getbits(6);
  309. }
  310.  
  311. void output_dyn( code , pos )
  312. int code;
  313. unsigned int pos;
  314. {
  315.     encode_c_dyn(code);
  316.     if (code >= 0x100) {
  317.         encode_p_st0(pos);
  318.     }
  319. }
  320.  
  321. void encode_end_dyn()
  322. {
  323.     putcode(7, 0);
  324. }
  325.