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