-/***********************************************************\r
- maketree.c -- make Huffman tree\r
-***********************************************************/\r
-#include "ar.h"\r
-\r
-static int n, heapsize;\r
-static short heap[NC + 1];\r
-static ushort *freq, *sortptr, len_cnt[17];\r
-static uchar *len;\r
-\r
-static void count_len(int i) /* call with i = root */\r
-{\r
- static int depth = 0;\r
-\r
- if (i < n) len_cnt[(depth < 16) ? depth : 16]++;\r
- else {\r
- depth++;\r
- count_len(left [i]);\r
- count_len(right[i]);\r
- depth--;\r
- }\r
-}\r
-\r
-static void make_len(int root)\r
-{\r
- int i, k;\r
- uint cum;\r
-\r
- for (i = 0; i <= 16; i++) len_cnt[i] = 0;\r
- count_len(root);\r
- cum = 0;\r
- for (i = 16; i > 0; i--)\r
- cum += len_cnt[i] << (16 - i);\r
- while (cum != (1U << 16)) {\r
- fprintf(stderr, "17");\r
- len_cnt[16]--;\r
- for (i = 15; i > 0; i--) {\r
- if (len_cnt[i] != 0) {\r
- len_cnt[i]--; len_cnt[i+1] += 2; break;\r
- }\r
- }\r
- cum--;\r
- }\r
- for (i = 16; i > 0; i--) {\r
- k = len_cnt[i];\r
- while (--k >= 0) len[*sortptr++] = i;\r
- }\r
-}\r
-\r
-static void downheap(int i)\r
- /* priority queue; send i-th entry down heap */\r
-{\r
- int j, k;\r
-\r
- k = heap[i];\r
- while ((j = 2 * i) <= heapsize) {\r
- if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])\r
- j++;\r
- if (freq[k] <= freq[heap[j]]) break;\r
- heap[i] = heap[j]; i = j;\r
- }\r
- heap[i] = k;\r
-}\r
-\r
-static void make_code(int n, uchar len[], ushort code[])\r
-{\r
- int i;\r
- ushort start[18];\r
-\r
- start[1] = 0;\r
- for (i = 1; i <= 16; i++)\r
- start[i + 1] = (start[i] + len_cnt[i]) << 1;\r
- for (i = 0; i < n; i++) code[i] = start[len[i]]++;\r
-}\r
-\r
-int make_tree(int nparm, ushort freqparm[],\r
- uchar lenparm[], ushort codeparm[])\r
- /* make tree, calculate len[], return root */\r
-{\r
- int i, j, k, avail;\r
-\r
- n = nparm; freq = freqparm; len = lenparm;\r
- avail = n; heapsize = 0; heap[1] = 0;\r
- for (i = 0; i < n; i++) {\r
- len[i] = 0;\r
- if (freq[i]) heap[++heapsize] = i;\r
- }\r
- if (heapsize < 2) {\r
- codeparm[heap[1]] = 0; return heap[1];\r
- }\r
- for (i = heapsize / 2; i >= 1; i--)\r
- downheap(i); /* make priority queue */\r
- sortptr = codeparm;\r
- do { /* while queue has at least two entries */\r
- i = heap[1]; /* take out least-freq entry */\r
- if (i < n) *sortptr++ = i;\r
- heap[1] = heap[heapsize--];\r
- downheap(1);\r
- j = heap[1]; /* next least-freq entry */\r
- if (j < n) *sortptr++ = j;\r
- k = avail++; /* generate new node */\r
- freq[k] = freq[i] + freq[j];\r
- heap[1] = k; downheap(1); /* put into queue */\r
- left[k] = i; right[k] = j;\r
- } while (heapsize > 1);\r
- sortptr = codeparm;\r
- make_len(k);\r
- make_code(nparm, lenparm, codeparm);\r
- return k; /* return root */\r
-}\r
+/***********************************************************
+ maketree.c -- make Huffman tree
+***********************************************************/
+#include "ar.h"
+
+struct heap_t {
+ short buf[NC + 1]; /* buf[0] is not used */
+ int size;
+ unsigned short *freq; /* priority */
+};
+
+struct tree_t {
+ ushort left[2 * NC - 1];
+ ushort right[2 * NC - 1];
+ ushort len_cnt[17];
+};
+
+static void
+count_len(struct tree_t *t, int i, int n, int *depth)
+{ /* call with i = root */
+ if (i < n)
+ t->len_cnt[(*depth < 16) ? *depth : 16]++;
+ else {
+ ++*depth;
+ count_len(t, t->left[i], n, depth);
+ count_len(t, t->right[i], n, depth);
+ --*depth;
+ }
+}
+
+static void
+make_len(struct tree_t *t, int root, int n, uchar *len, ushort *sortptr)
+{
+ int i, k;
+ uint cum;
+ int depth = 0;
+
+ for (i = 0; i <= 16; i++)
+ t->len_cnt[i] = 0;
+ count_len(t, root, n, &depth);
+ cum = 0;
+ for (i = 16; i > 0; i--)
+ cum += t->len_cnt[i] << (16 - i);
+ while (cum != (1U << 16)) {
+ t->len_cnt[16]--;
+ for (i = 15; i > 0; i--) {
+ if (t->len_cnt[i] != 0) {
+ t->len_cnt[i]--;
+ t->len_cnt[i + 1] += 2;
+ break;
+ }
+ }
+ cum--;
+ }
+ for (i = 16; i > 0; i--) {
+ k = t->len_cnt[i];
+ while (--k >= 0)
+ len[*sortptr++] = i;
+ }
+}
+
+static void
+downheap(struct heap_t *heap, int i)
+ /* priority queue; send i-th entry down heap */
+{
+ int j, k;
+
+ k = heap->buf[i];
+ while ((j = 2 * i) <= heap->size) {
+ if (j < heap->size && heap->freq[heap->buf[j]] > heap->freq[heap->buf[j + 1]])
+ j++;
+ if (heap->freq[k] <= heap->freq[heap->buf[j]])
+ break;
+ heap->buf[i] = heap->buf[j];
+ i = j;
+ }
+ heap->buf[i] = k;
+}
+
+static void
+make_code(struct tree_t *t, int n, uchar len[], ushort code[])
+{
+ int i;
+ ushort start[18];
+
+ start[1] = 0;
+ for (i = 1; i <= 16; i++)
+ start[i + 1] = (start[i] + t->len_cnt[i]) << 1;
+ for (i = 0; i < n; i++)
+ code[i] = start[len[i]]++;
+}
+
+int
+make_tree(int nparm, ushort freqparm[], uchar lenparm[], ushort codeparm[])
+ /* make tree, calculate len[], return root */
+{
+ int i, j, k, avail;
+ struct heap_t heap;
+ struct tree_t t;
+ int n;
+ unsigned short *sortptr;
+
+ n = nparm;
+ heap.freq = freqparm;
+ avail = n;
+ heap.size = 0;
+ heap.buf[1] = 0;
+ for (i = 0; i < n; i++) {
+ lenparm[i] = 0;
+ if (heap.freq[i])
+ heap.buf[++heap.size] = i;
+ }
+ if (heap.size < 2) {
+ codeparm[heap.buf[1]] = 0;
+ return heap.buf[1];
+ }
+ for (i = heap.size / 2; i >= 1; i--)
+ downheap(&heap, i); /* make priority queue */
+ sortptr = codeparm;
+ do { /* while queue has at least two entries */
+ i = heap.buf[1]; /* take out least-freq entry */
+ if (i < n)
+ *sortptr++ = i;
+ heap.buf[1] = heap.buf[heap.size--];
+ downheap(&heap, 1);
+
+ j = heap.buf[1]; /* next least-freq entry */
+ if (j < n)
+ *sortptr++ = j;
+
+ k = avail++; /* generate new node */
+ heap.freq[k] = heap.freq[i] + heap.freq[j];
+ heap.buf[1] = k;
+ downheap(&heap, 1); /* put into queue */
+ t.left[k] = i;
+ t.right[k] = j;
+ } while (heap.size > 1);
+ make_len(&t, k, n, lenparm, codeparm);
+ make_code(&t, nparm, lenparm, codeparm);
+ return k; /* return root */
+}
OSDN Git Service
