home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #3 / amigamamagazinepolishissue1998.iso / ppc / lha_ppc / src / maketree.c < prev    next >
C/C++ Source or Header  |  1997-12-04  |  3KB  |  137 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; k = 1 << (16 - 1);
  22.     for (i = 1; i <= 16; i++) {
  23.         start[i] = j;
  24.         j += (weight[i] = k) * len_cnt[i];
  25.         k >>= 1;
  26.     }
  27.     for (i = 0; i < n; i++) {
  28.         j = len[i];
  29.         code[i] = start[j];
  30.         start[j] += weight[j];
  31.     }
  32. }
  33.  
  34. static void count_len(int i)  /* call with i = root */
  35. {
  36.     static unsigned char depth = 0;
  37.  
  38.     if (i < n) len_cnt[depth < 16 ? depth : 16]++;
  39.     else {
  40.         depth++;
  41.         count_len(left [i]);
  42.         count_len(right[i]);
  43.         depth--;
  44.     }
  45. }
  46.  
  47. static void make_len(int root)
  48. {
  49.   int i, k;
  50.   unsigned int cum;
  51.  
  52.   for (i = 0; i <= 16; i++) len_cnt[i] = 0;
  53.   count_len(root);
  54.   cum = 0;
  55.   for (i = 16; i > 0; i--) {
  56.     cum += len_cnt[i] << (16 - i);
  57.   }
  58. #if (UINT_MAX != 0xffff)
  59.   cum &= 0xffff;
  60. #endif
  61. /* adjust len */
  62.     if (cum) {
  63.       fprintf(stderr, "17");
  64.       len_cnt[16] -= cum;        /* always len_cnt[16] > cum */
  65.       do {
  66.     for (i = 15; i > 0; i--) {
  67.       if (len_cnt[i]) {
  68.         len_cnt[i]--; len_cnt[i + 1] += 2; break;
  69.       }
  70.     }
  71.       } while (--cum);
  72.     }
  73. /* make len */
  74.   for (i = 16; i > 0; i--) {
  75.     k = len_cnt[i];
  76.     while (k > 0) {
  77.       len[*sort++] = i;
  78.       k--;
  79.     }
  80.   }
  81. }
  82.  
  83. static void downheap(int i)
  84.     /* priority queue; send i-th entry down heap */
  85. {
  86.   short j, k;
  87.  
  88.   k = heap[i];
  89.   while ((j = 2 * i) <= heapsize) {
  90.     if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  91.       j++;
  92.     if (freq[k] <= freq[heap[j]]) break;
  93.     heap[i] = heap[j];  i = j;
  94.   }
  95.   heap[i] = k;
  96. }
  97.  
  98. short make_tree(nparm, freqparm, lenparm, codeparm)
  99.     /* make tree, calculate len[], return root */
  100. int nparm;
  101. unsigned short freqparm[];
  102. unsigned char lenparm[];
  103. unsigned short codeparm[];
  104. {
  105.     short i, j, k, avail;
  106.  
  107.     n = nparm;  freq = freqparm;  len = lenparm;
  108.     avail = n;  heapsize = 0;  heap[1] = 0;
  109.     for (i = 0; i < n; i++) {
  110.         len[i] = 0;
  111.         if (freq[i]) heap[++heapsize] = i;
  112.     }
  113.     if (heapsize < 2) {
  114.         codeparm[heap[1]] = 0;
  115.         return heap[1];
  116.     }
  117.     for (i = heapsize / 2; i >= 1; i--)
  118.         downheap(i);  /* make priority queue */
  119.     sort = codeparm;
  120.     do {  /* while queue has at least two entries */
  121.         i = heap[1];  /* take out least-freq entry */
  122.         if (i < n) *sort++ = i;
  123.         heap[1] = heap[heapsize--];
  124.         downheap(1);
  125.         j = heap[1];  /* next least-freq entry */
  126.         if (j < n) *sort++ = j;
  127.         k = avail++;  /* generate new node */
  128.         freq[k] = freq[i] + freq[j];
  129.         heap[1] = k;  downheap(1);  /* put into queue */
  130.         left[k] = i;  right[k] = j;
  131.     } while (heapsize > 1);
  132.     sort = codeparm;
  133.     make_len(k);
  134.     make_code(nparm, lenparm, codeparm);
  135.     return k;  /* return root */
  136. }
  137.