This is maketree.c in view mode; [Download] [Up]
/* ------------------------------------------------------------------------ */
/* LHa for UNIX */
/* maketree.c -- make Huffman tree */
/* */
/* Modified Nobutaka Watazaki */
/* */
/* Ver. 1.14 Source All chagned 1995.01.14 N.Watazaki */
/* ------------------------------------------------------------------------ */
#include "lha.h"
/* ------------------------------------------------------------------------ */
static short n, heapsize, heap[NC + 1];
static unsigned short *freq, *sort;
static unsigned char *len;
static unsigned short len_cnt[17];
/* ------------------------------------------------------------------------ */
void
make_code(n, len, code)
int n;
unsigned char len[];
unsigned short code[];
{
unsigned short weight[17]; /* 0x10000ul >> bitlen */
unsigned short start[17]; /* start code */
unsigned short j, k;
int i;
j = 0;
k = 1 << (16 - 1);
for (i = 1; i <= 16; i++) {
start[i] = j;
j += (weight[i] = k) * len_cnt[i];
k >>= 1;
}
for (i = 0; i < n; i++) {
j = len[i];
code[i] = start[j];
start[j] += weight[j];
}
}
/* ------------------------------------------------------------------------ */
static void
count_len(i) /* call with i = root */
int i;
{
static unsigned char depth = 0;
if (i < n)
len_cnt[depth < 16 ? depth : 16]++;
else {
depth++;
count_len(left[i]);
count_len(right[i]);
depth--;
}
}
/* ------------------------------------------------------------------------ */
static void
make_len(root)
int root;
{
int i, k;
unsigned int cum;
for (i = 0; i <= 16; i++)
len_cnt[i] = 0;
count_len(root);
cum = 0;
for (i = 16; i > 0; i--) {
cum += len_cnt[i] << (16 - i);
}
#if (UINT_MAX != 0xffff)
cum &= 0xffff;
#endif
/* adjust len */
if (cum) {
fprintf(stderr, "17");
len_cnt[16] -= cum; /* always len_cnt[16] > cum */
do {
for (i = 15; i > 0; i--) {
if (len_cnt[i]) {
len_cnt[i]--;
len_cnt[i + 1] += 2;
break;
}
}
} while (--cum);
}
/* make len */
for (i = 16; i > 0; i--) {
k = len_cnt[i];
while (k > 0) {
len[*sort++] = i;
k--;
}
}
}
/* ------------------------------------------------------------------------ */
static void
downheap(i)
/* priority queue; send i-th entry down heap */
int i;
{
short j, k;
k = heap[i];
while ((j = 2 * i) <= heapsize) {
if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
j++;
if (freq[k] <= freq[heap[j]])
break;
heap[i] = heap[j];
i = j;
}
heap[i] = k;
}
/* ------------------------------------------------------------------------ */
short
make_tree(nparm, freqparm, lenparm, codeparm)
/* make tree, calculate len[], return root */
int nparm;
unsigned short freqparm[];
unsigned char lenparm[];
unsigned short codeparm[];
{
short i, j, k, avail;
n = nparm;
freq = freqparm;
len = lenparm;
avail = n;
heapsize = 0;
heap[1] = 0;
for (i = 0; i < n; i++) {
len[i] = 0;
if (freq[i])
heap[++heapsize] = i;
}
if (heapsize < 2) {
codeparm[heap[1]] = 0;
return heap[1];
}
for (i = heapsize / 2; i >= 1; i--)
downheap(i); /* make priority queue */
sort = codeparm;
do { /* while queue has at least two entries */
i = heap[1]; /* take out least-freq entry */
if (i < n)
*sort++ = i;
heap[1] = heap[heapsize--];
downheap(1);
j = heap[1]; /* next least-freq entry */
if (j < n)
*sort++ = j;
k = avail++; /* generate new node */
freq[k] = freq[i] + freq[j];
heap[1] = k;
downheap(1); /* put into queue */
left[k] = i;
right[k] = j;
} while (heapsize > 1);
sort = codeparm;
make_len(k);
make_code(nparm, lenparm, codeparm);
return k; /* return root */
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.