home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / ARCHIVERS / lha208src.lzh / LHA / SRC / maketree.c < prev    next >
Text File  |  1994-02-14  |  4KB  |  155 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)
  62.     cum &= 0xffff;
  63. #else
  64.     if (UINT_MAX != 0xffff)
  65.         cum &= 0xffff;
  66. #endif
  67.     /* adjust len */
  68.     if (cum) {
  69.         fprintf(stderr, "17");
  70.         len_cnt[16] -= cum;  /* always len_cnt[16] > cum */
  71.         do {
  72.             for (i = 15; i > 0; i--) {
  73.                 if (len_cnt[i]) {
  74.                     len_cnt[i]--; 
  75.                     len_cnt[i + 1] += 2; 
  76.                     break;
  77.                 }
  78.             }
  79.         } 
  80.         while (--cum);
  81.     }
  82.     /* make len */
  83.     for (i = 16; i > 0; i--) {
  84.         k = len_cnt[i];
  85.         while (k > 0) {
  86.             len[*sort++] = i;
  87.             k--;
  88.         }
  89.     }
  90. }
  91.  
  92. static void downheap(i)
  93. /* priority queue; send i-th entry down heap */
  94. int i;
  95. {
  96.     short j, k;
  97.  
  98.     k = heap[i];
  99.     while ((j = 2 * i) <= heapsize) {
  100.         if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  101.             j++;
  102.         if (freq[k] <= freq[heap[j]]) break;
  103.         heap[i] = heap[j];  
  104.         i = j;
  105.     }
  106.     heap[i] = k;
  107. }
  108.  
  109. short make_tree(nparm, freqparm, lenparm, codeparm)
  110. /* make tree, calculate len[], return root */
  111. int nparm;
  112. unsigned short freqparm[];
  113. unsigned char lenparm[];
  114. unsigned short codeparm[];
  115. {
  116.     short i, j, k, avail;
  117.  
  118.     n = nparm;  
  119.     freq = freqparm;  
  120.     len = lenparm;
  121.     avail = n;  
  122.     heapsize = 0;  
  123.     heap[1] = 0;
  124.     for (i = 0; i < n; i++) {
  125.         len[i] = 0;
  126.         if (freq[i]) heap[++heapsize] = i;
  127.     }
  128.     if (heapsize < 2) {
  129.         codeparm[heap[1]] = 0;
  130.         return heap[1];
  131.     }
  132.     for (i = heapsize / 2; i >= 1; i--)
  133.         downheap(i);  /* make priority queue */
  134.     sort = codeparm;
  135.     do {  /* while queue has at least two entries */
  136.         i = heap[1];  /* take out least-freq entry */
  137.         if (i < n) *sort++ = i;
  138.         heap[1] = heap[heapsize--];
  139.         downheap(1);
  140.         j = heap[1];  /* next least-freq entry */
  141.         if (j < n) *sort++ = j;
  142.         k = avail++;  /* generate new node */
  143.         freq[k] = freq[i] + freq[j];
  144.         heap[1] = k;  
  145.         downheap(1);  /* put into queue */
  146.         left[k] = i;  
  147.         right[k] = j;
  148.     } 
  149.     while (heapsize > 1);
  150.     sort = codeparm;
  151.     make_len(k);
  152.     make_code(nparm, lenparm, codeparm);
  153.     return k;  /* return root */
  154. }
  155.