home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Amiga MA Magazine 1998 #3
/
amigamamagazinepolishissue1998.iso
/
ppc
/
lha_ppc
/
orig_src
/
slide.c
< prev
next >
Wrap
C/C++ Source or Header
|
1992-05-08
|
9KB
|
390 lines
/***********************************************************
slide.c -- sliding dictionary with percolating update
***********************************************************/
#include "lharc.h"
#include "slidehuf.h"
#include "intrface.h"
#define PERCOLATE 1
#define NIL 0
node *next = NULL;
int unpackable;
unsigned long origsize, compsize;
unsigned short dicbit;
unsigned short maxmatch;
unsigned long count;
unsigned short loc;
unsigned char *text;
int prev_char;
static unsigned long encoded_origsize;
static struct encode_option encode_define[2] = {
#if defined(__STDC__) || defined(AIX)
/* lh1 */
{(void(*)())output_dyn,
(void(*)())encode_start_fix,
(void(*)())encode_end_dyn},
/* lh4, 5 */
{(void(*)())output_st1,
(void(*)())encode_start_st1,
(void(*)())encode_end_st1}
#else
/* lh1 */
{(int(*)())output_dyn,
(int(*)())encode_start_fix,
(int(*)())encode_end_dyn},
/* lh4, 5 */
{(int(*)())output_st1,
(int(*)())encode_start_st1,
(int(*)())encode_end_st1}
#endif
};
static struct decode_option decode_define[7] = {
/* lh1 */
{decode_c_dyn, decode_p_st0, decode_start_fix},
/* lh2 */
{decode_c_dyn, decode_p_dyn, decode_start_dyn},
/* lh3 */
{decode_c_st0, decode_p_st0, decode_start_st0},
/* lh4 */
{decode_c_st1, decode_p_st1, decode_start_st1},
/* lh5 */
{decode_c_st1, decode_p_st1, decode_start_st1},
/* lzs */
{decode_c_lzs, decode_p_lzs, decode_start_lzs},
/* lz5 */
{decode_c_lz5, decode_p_lz5, decode_start_lz5}
};
static struct encode_option encode_set;
static struct decode_option decode_set;
static node pos, matchpos, avail,
*position, *parent, *prev;
static int remainder, matchlen;
static unsigned char *level, *childcount;
static unsigned short dicsiz;
static unsigned short max_hash_val;
static unsigned short hash1, hash2;
int encode_alloc(method)
int method;
{
if (method == 1) {
encode_set = encode_define[0];
maxmatch = 60;
dicbit = 12;
} else {
encode_set = encode_define[1];
maxmatch = MAXMATCH;
dicbit = 13;
}
while (1) {
dicsiz = 1 << dicbit;
max_hash_val = 3 * dicsiz + (dicsiz / 512 + 1) * UCHAR_MAX;
text = (unsigned char *)malloc(dicsiz * 2 + maxmatch);
level = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*level));
childcount = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*childcount));
#if PERCOLATE
position = (node *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*position));
#else
position = (node *)malloc(dicsiz * sizeof(*position));
#endif
parent = (node *)malloc(dicsiz * 2 * sizeof(*parent));
prev = (node *)malloc(dicsiz * 2 * sizeof(*prev));
next = (node *)malloc((max_hash_val + 1) * sizeof(*next));
if (next == NULL ||
method > 1 && alloc_buf() == NULL) {
if (next) free(next);
if (prev) free(prev);
if (parent) free(parent);
if (position) free(position);
if (childcount) free(childcount);
if (level) free(level);
if (text) free(text);
} else {
break;
}
if (--dicbit < 12 )
/* error(MEMOVRERR, NULL); */
exit( 207 );
}
if (method == 5)
method = dicbit - 8;
return method;
}
static void init_slide(void)
{
node i;
for (i = dicsiz; i <= dicsiz + UCHAR_MAX; i++) {
level[i] = 1;
#if PERCOLATE
position[i] = NIL; /* sentinel */
#endif
}
for (i = dicsiz; i < dicsiz * 2; i++) parent[i] = NIL;
avail = 1;
for (i = 1; i < dicsiz - 1; i++) next[i] = i + 1;
next[dicsiz - 1] = NIL;
for (i = dicsiz * 2; i <= max_hash_val; i++) next[i] = NIL;
hash1 = dicbit - 9;
hash2 = dicsiz * 2;
}
#define HASH(p, c) ((p) + ((c) << hash1) + hash2)
static /* inline */ node child(q, c)
/* q's child for character c (NIL if not found) */
node q;
unsigned char c;
{
node r;
r = next[HASH(q, c)];
parent[NIL] = q; /* sentinel */
while (parent[r] != q) r = next[r];
return r;
}
static /* inline */ void makechild(q, c, r)
/* Let r be q's child for character c. */
node q;
unsigned char c;
node r;
{
node h, t;
h = HASH(q, c);
t = next[h]; next[h] = r; next[r] = t;
prev[t] = r; prev[r] = h;
parent[r] = q; childcount[q]++;
}
static /*inline*/ void split(old)
node old;
{
node new, t;
new = avail; avail = next[new]; childcount[new] = 0;
t = prev[old]; prev[new] = t; next[t] = new;
t = next[old]; next[new] = t; prev[t] = new;
parent[new] = parent[old];
level[new] = matchlen;
position[new] = pos;
makechild(new, text[matchpos + matchlen], old);
makechild(new, text[pos + matchlen], pos);
}
static void insert_node(void)
{
node q, r, j, t;
unsigned char c, *t1, *t2;
if (matchlen >= 4) {
matchlen--;
r = (matchpos + 1) | dicsiz;
while ((q = parent[r]) == NIL) r = next[r];
while (level[q] >= matchlen) {
r = q; q = parent[q];
}
#if PERCOLATE
t = q;
while (position[t] < 0) {
position[t] = pos; t = parent[t];
}
if (t < dicsiz) position[t] = pos | SHRT_MIN;
#else
t = q;
while (t < dicsiz) {
position[t] = pos; t = parent[t];
}
#endif
} else {
q = text[pos] + dicsiz; c = text[pos + 1];
if ((r = child(q, c)) == NIL) {
makechild(q, c, pos); matchlen = 1;
return;
}
matchlen = 2;
}
for ( ; ; ) {
if (r >= dicsiz) {
j = maxmatch; matchpos = r;
} else {
j = level[r];
matchpos = position[r] & SHRT_MAX;
}
if (matchpos >= pos) matchpos -= dicsiz;
t1 = &text[pos + matchlen]; t2 = &text[matchpos + matchlen];
while (matchlen < j) {
if (*t1 != *t2) { split(r); return; }
matchlen++; t1++; t2++;
}
if (matchlen == maxmatch) break;
position[r] = pos;
q = r;
if ((r = child(q, *t1)) == NIL) {
makechild(q, *t1, pos); return;
}
matchlen++;
}
t = prev[r]; prev[pos] = t; next[t] = pos;
t = next[r]; next[pos] = t; prev[t] = pos;
parent[pos] = q; parent[r] = NIL;
next[r] = pos; /* special use of next[] */
}
static void delete_node(void)
{
#if PERCOLATE
node q, r, s, t, u;
#else
node r, s, t, u;
#endif
if (parent[pos] == NIL) return;
r = prev[pos]; s = next[pos];
next[r] = s; prev[s] = r;
r = parent[pos]; parent[pos] = NIL;
if (r >= dicsiz || --childcount[r] > 1) return;
#if PERCOLATE
t = position[r] & SHRT_MAX;
#else
t = position[r];
#endif
if (t >= pos) t -= dicsiz;
#if PERCOLATE
s = t; q = parent[r];
while ((u = position[q]) < 0) {
u &= SHRT_MAX; if (u >= pos) u -= dicsiz;
if (u > s) s = u;
position[q] = (s | dicsiz); q = parent[q];
}
if (q < dicsiz) {
if (u >= pos) u -= dicsiz;
if (u > s) s = u;
position[q] = (s | dicsiz) | SHRT_MIN;
}
#endif
s = child(r, text[t + level[r]]);
t = prev[s]; u = next[s];
next[t] = u; prev[u] = t;
t = prev[r]; next[t] = s; prev[s] = t;
t = next[r]; prev[t] = s; next[s] = t;
parent[s] = parent[r]; parent[r] = NIL;
next[r] = avail; avail = r;
}
/* static */void get_next_match(void)
{
int n;
remainder--;
if (++pos == dicsiz * 2) {
bcopy(&text[dicsiz], &text[0], dicsiz + maxmatch);
n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile);
encoded_origsize += n;
remainder += n; pos = dicsiz;
}
delete_node(); insert_node();
}
void encode(interface)
struct interfacing *interface;
{
int lastmatchlen, dicsiz1;
node lastmatchpos;
infile = interface -> infile;
outfile = interface -> outfile;
origsize = interface -> original;
compsize = count = 0L;
crc = unpackable = 0;
init_slide(); encode_set.encode_start();
dicsiz1 = dicsiz - 1;
pos = dicsiz + maxmatch;
memset(&text[pos], ' ', dicsiz);
remainder = fread_crc(&text[pos], dicsiz, infile);
encoded_origsize = remainder;
matchlen = 0;
insert_node();
while (remainder > 0 && ! unpackable) {
lastmatchlen = matchlen; lastmatchpos = matchpos;
get_next_match();
if (matchlen > remainder) matchlen = remainder;
if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
encode_set.output(text[pos - 1], 0);
count++;
} else {
encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
(pos - lastmatchpos - 2) & dicsiz1);
while (--lastmatchlen > 0) {
get_next_match();
count++;
}
if (matchlen > remainder) matchlen = remainder;
}
}
encode_set.encode_end();
interface -> packed = compsize;
interface -> original = encoded_origsize;
}
void decode(interface)
struct interfacing *interface;
{
int i, j, k, c, dicsiz1, offset;
infile = interface -> infile;
outfile = interface -> outfile;
dicbit = interface -> dicbit;
origsize = interface -> original;
compsize = interface -> packed;
decode_set = decode_define[interface -> method - 1];
crc = 0;
prev_char = -1;
dicsiz = 1 << dicbit;
text = (unsigned char *)malloc(dicsiz);
if (text == NULL)
/* error(MEMOVRERR, NULL); */
exit( errno );
memset(text, ' ', dicsiz);
decode_set.decode_start();
dicsiz1 = dicsiz - 1;
offset = (interface -> method == 6) ? 0x100 - 2 : 0x100 - 3;
count = 0; loc = 0;
while (count < origsize) {
c = decode_set.decode_c();
if (c <= UCHAR_MAX) {
text[loc++] = c;
if (loc == dicsiz) {
fwrite_crc(text, dicsiz, outfile);
loc = 0;
}
count++;
} else {
j = c - offset;
i = (loc - decode_set.decode_p() - 1) & dicsiz1;
count += j;
for (k = 0; k < j; k++) {
c = text[(i + k) & dicsiz1];
text[loc++] = c;
if (loc == dicsiz) {
fwrite_crc(text, dicsiz, outfile);
loc = 0;
}
}
}
}
if (loc != 0) {
fwrite_crc(text, loc, outfile);
}
free(text);
}