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
make_code(nchar,bitlen,code,leaf_num)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
count_leaf(node,nchar,leaf_num,depth)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
make_len(nchar,bitlen,sort,leaf_num)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
downheap(i,heap,heapsize,freq)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
make_tree(nchar,freq,bitlen,code)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 }
180