home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
rtsi.com
/
2014.01.www.rtsi.com.tar
/
www.rtsi.com
/
OS9
/
OSK
/
ARCHIVERS
/
lha208src.lzh
/
LHA
/
SRC
/
dhuf.c
< prev
next >
Wrap
Text File
|
1994-02-14
|
7KB
|
325 lines
/**************************************************************
title dhuf.c
***************************************************************
Dynamic Huffman routine
H.Yoshizaki
**************************************************************/
#include <stdio.h>
#include "slidehuf.h"
#define N_CHAR (256 + 60 - THRESHOLD + 1)
#define TREESIZE_C (N_CHAR * 2)
#define TREESIZE_P (128 * 2)
#define TREESIZE (TREESIZE_C + TREESIZE_P)
#define ROOT_C 0
#define ROOT_P TREESIZE_C
unsigned int n_max;
static short child [TREESIZE],
parent[TREESIZE],
block [TREESIZE],
edge [TREESIZE],
stock [TREESIZE],
node [TREESIZE / 2];
static unsigned short freq[TREESIZE];
static unsigned short total_p;
static int avail, n1;
static int most_p, nn;
static unsigned long nextcount;
void start_c_dyn()
{
int i, j, f;
n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;
for (i = 0; i < TREESIZE_C; i++) {
stock[i] = i;
block[i] = 0;
}
for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--) {
freq[j] = 1;
child[j] = ~i;
node[i] = j;
block[j] = 1;
}
avail = 2;
edge[1] = n_max - 1;
i = n_max * 2 - 2;
while (j >= 0) {
f = freq[j] = freq[i] + freq[i - 1];
child[j] = i;
parent[i] = parent[i - 1] = j;
if (f == freq[j + 1]) {
edge[block[j] = block[j + 1]] = j;
}
else {
edge[block[j] = stock[avail++]] = j;
}
i -= 2;
j--;
}
}
static void start_p_dyn()
{
freq[ROOT_P] = 1;
child[ROOT_P] = ~(N_CHAR);
node[N_CHAR] = ROOT_P;
edge[block[ROOT_P] = stock[avail++]] = ROOT_P;
most_p = ROOT_P;
total_p = 0;
nn = 1 << dicbit;
nextcount = 64;
}
void decode_start_dyn()
{
n_max = 286;
maxmatch = MAXMATCH;
init_getbits();
start_c_dyn();
start_p_dyn();
}
static void reconst( start , end )
int start;
int end;
{
int i, j, k, l, b;
unsigned int f, g;
for (i = j = start; i < end; i++) {
if ((k = child[i]) < 0) {
freq[j] = (freq[i] + 1) / 2;
child[j] = k;
j++;
}
if (edge[b = block[i]] == i) {
stock[--avail] = b;
}
}
j--;
i = end - 1;
l = end - 2;
while (i >= start) {
while (i >= l) {
freq[i] = freq[j];
child[i] = child[j];
i--, j--;
}
f = freq[l] + freq[l + 1];
for (k = start; f < freq[k]; k++);
while(j >= k) {
freq[i] = freq[j];
child[i] = child[j];
i--, j--;
}
freq[i] = f;
child[i] = l + 1;
i--;
l -= 2;
}
f = 0;
for (i = start; i < end; i++) {
if ((j = child[i]) < 0) node[~j] = i;
else parent[j] = parent[j - 1] = i;
if ((g = freq[i]) == f) {
block[i] = b;
}
else {
edge[b = block[i] = stock[avail++]] = i;
f = g;
}
}
}
static int swap_inc(p)
int p;
{
int b, q, r, s;
b = block[p];
if ((q = edge[b]) != p) { /* swap for leader */
r = child[p];
s = child[q];
child[p] = s;
child[q] = r;
if (r >= 0) parent[r] = parent[r - 1] = q;
else node[~r] = q;
if (s >= 0) parent[s] = parent[s - 1] = p;
else node[~s] = p;
p = q;
goto Adjust;
}
else if (b == block[p + 1]) {
Adjust:
edge[b]++;
if (++freq[p] == freq[p - 1]) {
block[p] = block[p - 1];
}
else {
edge[block[p] = stock[avail++]] = p; /* create block */
}
}
else if (++freq[p] == freq[p - 1]) {
stock[--avail] = b; /* delete block */
block[p] = block[p - 1];
}
return parent[p];
}
static void update_c(p)
int p;
{
int q;
if (freq[ROOT_C] == 0x8000) {
reconst(0, n_max * 2 - 1);
}
freq[ROOT_C]++;
q = node[p];
do {
q = swap_inc(q);
}
while (q != ROOT_C);
}
static void update_p(p)
int p;
{
int q;
if (total_p == 0x8000) {
reconst(ROOT_P, most_p + 1);
total_p = freq[ROOT_P];
freq[ROOT_P] = 0xffff;
}
q = node[p + N_CHAR];
while (q != ROOT_P) {
q = swap_inc(q);
}
total_p++;
}
static void make_new_node(p)
int p;
{
int q, r;
r = most_p + 1;
q = r + 1;
node[~(child[r] = child[most_p])] = r;
child[q] = ~(p + N_CHAR);
child[most_p] = q;
freq[r] = freq[most_p];
freq[q] = 0;
block[r] = block[most_p];
if (most_p == ROOT_P) {
freq[ROOT_P] = 0xffff;
edge[block[ROOT_P]]++;
}
parent[r] = parent[q] = most_p;
edge[block[q] = stock[avail++]] = node[p + N_CHAR] = most_p = q;
update_p(p);
}
static void encode_c_dyn(c)
int c;
{
unsigned int bits;
int p, d, cnt;
d = c - n1;
if (d >= 0) {
c = n1;
}
cnt = bits = 0;
p = node[c];
do {
bits >>= 1;
if (p & 1) {
bits |= 0x8000;
}
if (++cnt == 16) {
putcode(16, bits);
cnt = bits = 0;
}
}
while ((p = parent[p]) != ROOT_C);
putcode(cnt, bits);
if (d >= 0) putbits(8, d);
update_c(c);
}
unsigned short decode_c_dyn()
{
int c;
short buf, cnt;
c = child[ROOT_C];
buf = bitbuf;
cnt = 0;
do {
c = child[c - (buf < 0)];
buf <<= 1;
if (++cnt == 16) {
fillbuf(16);
buf = bitbuf;
cnt = 0;
}
}
while (c > 0);
fillbuf(cnt);
c = ~c;
update_c(c);
if (c == n1) c += getbits(8);
return c;
}
unsigned short decode_p_dyn()
{
int c;
short buf, cnt;
while (count > nextcount) {
make_new_node(nextcount / 64);
if ((nextcount += 64) >= nn)
nextcount = 0xffffffff;
}
c = child[ROOT_P];
buf = bitbuf;
cnt = 0;
while (c > 0) {
c = child[c - (buf < 0)];
buf <<= 1;
if (++cnt == 16) {
fillbuf(16);
buf = bitbuf;
cnt = 0;
}
}
fillbuf(cnt);
c = (~c) - N_CHAR;
update_p(c);
return (c << 6) + getbits(6);
}
void output_dyn( code , pos )
int code;
unsigned int pos;
{
encode_c_dyn(code);
if (code >= 0x100) {
encode_p_st0(pos);
}
}
void encode_end_dyn()
{
putcode(7, 0);
}