home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / ARCHIVERS / lhasrc.lzh / maketree.c < prev    next >
Text File  |  1992-05-13  |  4KB  |  152 lines
  1. /***********************************************************
  2.     maketree.c -- make Huffman tree
  3. ***********************************************************/
  4. #include "slidehuf.h"
  5.  
  6. static short n, heapsize, heap[NC + 1];
  7. static unsigned short *freq, *sort;
  8. static unsigned char *len;
  9. static unsigned short len_cnt[17];
  10.  
  11. void make_code(n, len, code)
  12. int n;
  13. unsigned char len[];
  14. unsigned short code[];
  15. {
  16.     unsigned short weight[17]; /* 0x10000ul >> bitlen */
  17.     unsigned short start[17];  /* start code */
  18.     unsigned short j, k;
  19.     int i;
  20.  
  21.     j = 0; 
  22.     k = 1 << (16 - 1);
  23.     for (i = 1; i <= 16; i++) {
  24.         start[i] = j;
  25.         j += (weight[i] = k) * len_cnt[i];
  26.         k >>= 1;
  27.     }
  28.     for (i = 0; i < n; i++) {
  29.         j = len[i];
  30.         code[i] = start[j];
  31.         start[j] += weight[j];
  32.     }
  33. }
  34.  
  35. static void count_len(i)  /* call with i = root */
  36. int i;
  37. {
  38.     static unsigned char depth = 0;
  39.  
  40.     if (i < n) len_cnt[depth < 16 ? depth : 16]++;
  41.     else {
  42.         depth++;
  43.         count_len(left [i]);
  44.         count_len(right[i]);
  45.         depth--;
  46.     }
  47. }
  48.  
  49. static void make_len(root)
  50. int root;
  51. {
  52.     int i, k;
  53.     unsigned int cum;
  54.  
  55.     for (i = 0; i <= 16; i++) len_cnt[i] = 0;
  56.     count_len(root);
  57.     cum = 0;
  58.     for (i = 16; i > 0; i--) {
  59.         cum += len_cnt[i] << (16 - i);
  60.     }
  61. #if defined(_MINIX) || (UINT_MAX != 0xffff)
  62.     cum &= 0xffff;
  63. #endif
  64.     /* adjust len */
  65.     if (cum) {
  66.         fprintf(stderr, "17");
  67.         len_cnt[16] -= cum;  /* always len_cnt[16] > cum */
  68.         do {
  69.             for (i = 15; i > 0; i--) {
  70.                 if (len_cnt[i]) {
  71.                     len_cnt[i]--; 
  72.                     len_cnt[i + 1] += 2; 
  73.                     break;
  74.                 }
  75.             }
  76.         } 
  77.         while (--cum);
  78.     }
  79.     /* make len */
  80.     for (i = 16; i > 0; i--) {
  81.         k = len_cnt[i];
  82.         while (k > 0) {
  83.             len[*sort++] = i;
  84.             k--;
  85.         }
  86.     }
  87. }
  88.  
  89. static void downheap(i)
  90. /* priority queue; send i-th entry down heap */
  91. int i;
  92. {
  93.     short j, k;
  94.  
  95.     k = heap[i];
  96.     while ((j = 2 * i) <= heapsize) {
  97.         if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  98.             j++;
  99.         if (freq[k] <= freq[heap[j]]) break;
  100.         heap[i] = heap[j];  
  101.         i = j;
  102.     }
  103.     heap[i] = k;
  104. }
  105.  
  106. short make_tree(nparm, freqparm, lenparm, codeparm)
  107. /* make tree, calculate len[], return root */
  108. int nparm;
  109. unsigned short freqparm[];
  110. unsigned char lenparm[];
  111. unsigned short codeparm[];
  112. {
  113.     short i, j, k, avail;
  114.  
  115.     n = nparm;  
  116.     freq = freqparm;  
  117.     len = lenparm;
  118.     avail = n;  
  119.     heapsize = 0;  
  120.     heap[1] = 0;
  121.     for (i = 0; i < n; i++) {
  122.         len[i] = 0;
  123.         if (freq[i]) heap[++heapsize] = i;
  124.     }
  125.     if (heapsize < 2) {
  126.         codeparm[heap[1]] = 0;
  127.         return heap[1];
  128.     }
  129.     for (i = heapsize / 2; i >= 1; i--)
  130.         downheap(i);  /* make priority queue */
  131.     sort = codeparm;
  132.     do {  /* while queue has at least two entries */
  133.         i = heap[1];  /* take out least-freq entry */
  134.         if (i < n) *sort++ = i;
  135.         heap[1] = heap[heapsize--];
  136.         downheap(1);
  137.         j = heap[1];  /* next least-freq entry */
  138.         if (j < n) *sort++ = j;
  139.         k = avail++;  /* generate new node */
  140.         freq[k] = freq[i] + freq[j];
  141.         heap[1] = k;  
  142.         downheap(1);  /* put into queue */
  143.         left[k] = i;  
  144.         right[k] = j;
  145.     } 
  146.     while (heapsize > 1);
  147.     sort = codeparm;
  148.     make_len(k);
  149.     make_code(nparm, lenparm, codeparm);
  150.     return k;  /* return root */
  151. }
  152.