1 /* ------------------------------------------------------------------------ */
3 /* maketree.c -- make Huffman tree */
5 /* Modified Nobutaka Watazaki */
7 /* Ver. 1.14 Source All chagned 1995.01.14 N.Watazaki */
8 /* ------------------------------------------------------------------------ */
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 /* ------------------------------------------------------------------------ */
18 make_code(n, len, code)
21 unsigned short code[];
23 unsigned short weight[17]; /* 0x10000ul >> bitlen */
24 unsigned short start[17]; /* start code */
30 for (i = 1; i <= 16; i++) {
32 j += (weight[i] = k) * len_cnt[i];
35 for (i = 0; i < n; i++) {
38 start[j] += weight[j];
42 /* ------------------------------------------------------------------------ */
44 count_len(i) /* call with i = root */
47 static unsigned char depth = 0;
50 len_cnt[depth < 16 ? depth : 16]++;
59 /* ------------------------------------------------------------------------ */
67 for (i = 0; i <= 16; i++)
71 for (i = 16; i > 0; i--) {
72 cum += len_cnt[i] << (16 - i);
74 #if (UINT_MAX != 0xffff)
79 fprintf(stderr, "17");
80 len_cnt[16] -= cum; /* always len_cnt[16] > cum */
82 for (i = 15; i > 0; i--) {
92 for (i = 16; i > 0; i--) {
101 /* ------------------------------------------------------------------------ */
104 /* priority queue; send i-th entry down heap */
110 while ((j = 2 * i) <= heapsize) {
111 if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
113 if (freq[k] <= freq[heap[j]])
121 /* ------------------------------------------------------------------------ */
123 make_tree(nparm, freqparm, lenparm, codeparm)
124 /* make tree, calculate len[], return root */
126 unsigned short freqparm[];
127 unsigned char lenparm[];
128 unsigned short codeparm[];
130 short i, j, k, avail;
138 for (i = 0; i < n; i++) {
141 heap[++heapsize] = i;
144 codeparm[heap[1]] = 0;
147 for (i = heapsize / 2; i >= 1; i--)
148 downheap(i); /* make priority queue */
150 do { /* while queue has at least two entries */
151 i = heap[1]; /* take out least-freq entry */
154 heap[1] = heap[heapsize--];
156 j = heap[1]; /* next least-freq entry */
159 k = avail++; /* generate new node */
160 freq[k] = freq[i] + freq[j];
162 downheap(1); /* put into queue */
165 } while (heapsize > 1);
168 make_code(nparm, lenparm, codeparm);
169 return k; /* return root */
172 /* Local Variables: */