home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
DOS/V Power Report 1997 March
/
VPR9703A.ISO
/
OLS
/
Os2
/
LHA2P205
/
LHA2P205.LZH
/
lha2-2.05pre
/
source.lzh
/
src
/
maketree.c
< prev
next >
Wrap
C/C++ Source or Header
|
1995-10-15
|
3KB
|
179 lines
/*
* maketree.c --- make Huffman tree
* Copyright (C) 1988-1992. Haruyasu YOSHIZAKI
*
* $Log$
*/
#include <stdio.h>
#include <limits.h>
#include "typedef.h"
#include "slidehuf.h"
static short n, heapsize, heap[NC + 1];
static ushort *freq, *sort;
static uchar *len;
static ushort len_cnt[17];
void
make_code(short n, uchar len[], ushort code[])
{
ushort weight[17]; /* 0x10000ul >> bitlen */
ushort start[17]; /* start code */
ushort 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;
}
start[0] = weight[0] = 0;
for(i = 0; i < n; i++)
{
j = len[i];
code[i] = start[j];
start[j] += weight[j];
}
}
static void
count_len(short i) /* call with i = root */
{
static uchar 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(short root)
{
int i, k;
uint 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)
{
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(short i) /* priority queue; send i-th entry down heap */
{
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;
}
/* make tree, calculate len[], return root */
short
make_tree(short nparm, ushort freqparm[], uchar lenparm[], ushort 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 */
}