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
/
slide.c
< prev
next >
Wrap
Text File
|
1994-02-14
|
11KB
|
441 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 struct encode_option encode_define[2] = {
#ifdef __STDC__
/* 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()
{
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()
{
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()
{
#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()
{
int n;
remainder--;
if (++pos == dicsiz * 2) {
bcopy(&text[dicsiz], &text[0], dicsiz + maxmatch);
n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile);
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;
compsize = count = 0L;
mcrc = 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);
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 = 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];
mcrc = 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);
}