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 / maketree.c < prev    next >
C/C++ Source or Header  |  1995-10-15  |  3KB  |  179 lines
  1. /*
  2.  * maketree.c --- make Huffman tree
  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. static short n, heapsize, heap[NC + 1];
  16. static ushort *freq, *sort;
  17. static uchar *len;
  18. static ushort len_cnt[17];
  19.  
  20.  
  21. void
  22. make_code(short n, uchar len[], ushort code[])
  23. {
  24.   ushort weight[17];        /* 0x10000ul >> bitlen */
  25.   ushort start[17];        /* start code */
  26.   ushort j, k;
  27.   int i;
  28.  
  29.   j = 0;
  30.   k = 1 << (16 - 1);
  31.   for(i = 1; i <= 16; i++)
  32.     {
  33.       start[i] = j;
  34.       j += (weight[i] = k) * len_cnt[i];
  35.       k >>= 1;
  36.     }
  37.   start[0] = weight[0] = 0;
  38.   for(i = 0; i < n; i++)
  39.     {
  40.       j = len[i];
  41.       code[i] = start[j];
  42.       start[j] += weight[j];
  43.     }
  44. }
  45.  
  46.  
  47. static void
  48. count_len(short i)        /* call with i = root */
  49. {
  50.   static uchar depth = 0;
  51.  
  52.   if(i < n)
  53.     len_cnt[depth < 16 ? depth : 16]++;
  54.   else
  55.     {
  56.       depth++;
  57.       count_len(left [i]);
  58.       count_len(right[i]);
  59.       depth--;
  60.     }
  61. }
  62.  
  63.  
  64. static void
  65. make_len(short root)
  66. {
  67.   int i, k;
  68.   uint cum;
  69.  
  70.   for(i = 0; i <= 16; i++)
  71.     len_cnt[i] = 0;
  72.   count_len(root);
  73.   cum = 0;
  74.   for(i = 16; i > 0; i--)
  75.     cum += len_cnt[i] << (16 - i);
  76.  
  77. #if (UINT_MAX != 0xffff)
  78.   cum &= 0xffff;
  79. #endif
  80.   /* adjust len */
  81.   if(cum)
  82.     {
  83.       len_cnt[16] -= cum;    /* always len_cnt[16] > cum */
  84.       do
  85.     {
  86.       for(i = 15; i > 0; i--)
  87.         if(len_cnt[i])
  88.           {
  89.         len_cnt[i]--;
  90.         len_cnt[i + 1] += 2;
  91.         break;
  92.           }
  93.     }
  94.       while(--cum);
  95.     }
  96.  
  97.   /* make len */
  98.   for(i = 16; i > 0; i--)
  99.     {
  100.       k = len_cnt[i];
  101.       while(k > 0)
  102.     {
  103.       len[*sort++] = i;
  104.       k--;
  105.     }
  106.     }
  107. }
  108.  
  109.  
  110. static void
  111. downheap(short i)        /* priority queue; send i-th entry down heap */
  112. {
  113.   short j, k;
  114.  
  115.   k = heap[i];
  116.   while((j = 2 * i) <= heapsize)
  117.     {
  118.       if(j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  119.     j++;
  120.       if(freq[k] <= freq[heap[j]])
  121.     break;
  122.       heap[i] = heap[j];
  123.       i = j;
  124.     }
  125.   heap[i] = k;
  126. }
  127.  
  128.  
  129. /* make tree, calculate len[], return root */
  130. short
  131. make_tree(short nparm, ushort freqparm[], uchar lenparm[], ushort codeparm[])
  132. {
  133.   short i, j, k, avail;
  134.  
  135.   n = nparm;
  136.   freq = freqparm;
  137.   len = lenparm;
  138.   avail = n;
  139.   heapsize = 0;
  140.   heap[1] = 0;
  141.   for(i = 0; i < n; i++)
  142.     {
  143.       len[i] = 0;
  144.       if(freq[i])
  145.     heap[++heapsize] = i;
  146.     }
  147.   if(heapsize < 2)
  148.     {
  149.       codeparm[heap[1]] = 0;
  150.       return heap[1];
  151.     }
  152.   for(i = heapsize / 2; i >= 1; i--)
  153.     downheap(i);        /* make priority queue */
  154.   sort = codeparm;
  155.   do                /* while queue has at least two entries */
  156.     {
  157.       i = heap[1];        /* take out least-freq entry */
  158.       if(i < n)
  159.     *sort++ = i;
  160.       heap[1] = heap[heapsize--];
  161.       downheap(1);
  162.       j = heap[1];        /* next least-freq entry */
  163.       if(j < n)
  164.     *sort++ = j;
  165.       k = avail++;        /* generate new node */
  166.       freq[k] = freq[i] + freq[j];
  167.       heap[1] = k;
  168.       downheap(1);        /* put into queue */
  169.       left[k] = i;
  170.       right[k] = j;
  171.     }
  172.   while(heapsize > 1);
  173.   sort = codeparm;
  174.   make_len(k);
  175.   make_code(nparm, lenparm, codeparm);
  176.  
  177.   return k;            /* return root */
  178. }
  179.