src/maketree.c

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