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