"SfR Fresh" - the SfR Freeware/Shareware Archive 
Member "lha-114i/src/maketree.c" of archive lha-114i.tar.gz:
As a special service "SfR Fresh" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting with prefixed line numbers.
Alternatively you can here view or download the uninterpreted source code file.
That can be also achieved for any archive member file by clicking within an archive contents listing on the first character of the file(path) respectively on the according byte size field.
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: */