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 }
 171
 172 /* Local Variables: */
 173 /* mode:c */
 174 /* tab-width:4 */
 175 /* End: */