maketree.c

   1 /***********************************************************
   2         maketree.c -- make Huffman tree
   3 ***********************************************************/
   4 #include "ar.h"
   5
   6 static int n, heapsize;
   7 static short heap[NC + 1];
   8 static ushort *freq, *sortptr, len_cnt[17];
   9 static uchar *len;
  10
  11 static void
  12 count_len(int i)
  13 {                               /* call with i = root */
  14     static int depth = 0;
  15
  16     if (i < n)
  17         len_cnt[(depth < 16) ? depth : 16]++;
  18     else {
  19         depth++;
  20         count_len(left[i]);
  21         count_len(right[i]);
  22         depth--;
  23     }
  24 }
  25
  26 static void
  27 make_len(int root)
  28 {
  29     int i, k;
  30     uint cum;
  31
  32     for (i = 0; i <= 16; i++)
  33         len_cnt[i] = 0;
  34     count_len(root);
  35     cum = 0;
  36     for (i = 16; i > 0; i--)
  37         cum += len_cnt[i] << (16 - i);
  38     while (cum != (1U << 16)) {
  39         fprintf(stderr, "17");
  40         len_cnt[16]--;
  41         for (i = 15; i > 0; i--) {
  42             if (len_cnt[i] != 0) {
  43                 len_cnt[i]--;
  44                 len_cnt[i + 1] += 2;
  45                 break;
  46             }
  47         }
  48         cum--;
  49     }
  50     for (i = 16; i > 0; i--) {
  51         k = len_cnt[i];
  52         while (--k >= 0)
  53             len[*sortptr++] = i;
  54     }
  55 }
  56
  57 static void
  58 downheap(int i)
  59         /* priority queue; send i-th entry down heap */
  60 {
  61     int j, k;
  62
  63     k = heap[i];
  64     while ((j = 2 * i) <= heapsize) {
  65         if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  66             j++;
  67         if (freq[k] <= freq[heap[j]])
  68             break;
  69         heap[i] = heap[j];
  70         i = j;
  71     }
  72     heap[i] = k;
  73 }
  74
  75 static void
  76 make_code(int n, uchar len[], ushort code[])
  77 {
  78     int i;
  79     ushort start[18];
  80
  81     start[1] = 0;
  82     for (i = 1; i <= 16; i++)
  83         start[i + 1] = (start[i] + len_cnt[i]) << 1;
  84     for (i = 0; i < n; i++)
  85         code[i] = start[len[i]]++;
  86 }
  87
  88 int
  89 make_tree(int nparm, ushort freqparm[], uchar lenparm[], ushort codeparm[])
  90         /* make tree, calculate len[], return root */
  91 {
  92     int i, j, k, avail;
  93
  94     n = nparm;
  95     freq = freqparm;
  96     len = lenparm;
  97     avail = n;
  98     heapsize = 0;
  99     heap[1] = 0;
 100     for (i = 0; i < n; i++) {
 101         len[i] = 0;
 102         if (freq[i])
 103             heap[++heapsize] = i;
 104     }
 105     if (heapsize < 2) {
 106         codeparm[heap[1]] = 0;
 107         return heap[1];
 108     }
 109     for (i = heapsize / 2; i >= 1; i--)
 110         downheap(i);            /* make priority queue */
 111     sortptr = codeparm;
 112     do {                        /* while queue has at least two entries */
 113         i = heap[1];            /* take out least-freq entry */
 114         if (i < n)
 115             *sortptr++ = i;
 116         heap[1] = heap[heapsize--];
 117         downheap(1);
 118         j = heap[1];            /* next least-freq entry */
 119         if (j < n)
 120             *sortptr++ = j;
 121         k = avail++;            /* generate new node */
 122         freq[k] = freq[i] + freq[j];
 123         heap[1] = k;
 124         downheap(1);            /* put into queue */
 125         left[k] = i;
 126         right[k] = j;
 127     } while (heapsize > 1);
 128     sortptr = codeparm;
 129     make_len(k);
 130     make_code(nparm, lenparm, codeparm);
 131     return k;                   /* return root */
 132 }