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
make_code(n,len,code)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
count_len(i)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
make_len(root)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
downheap(i)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
make_tree(nparm,freqparm,lenparm,codeparm)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: */
176