This is slide-old.c in view mode; [Download] [Up]
/* ------------------------------------------------------------------------ */
/* LHa for UNIX */
/* slice.c -- sliding dictionary with percolating update */
/* */
/* Modified Nobutaka Watazaki */
/* */
/* Ver. 1.14 Source All chagned 1995.01.14 N.Watazaki */
/* ------------------------------------------------------------------------ */
#include "lha.h"
/* ------------------------------------------------------------------------ */
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, 6 */
{(int (*) ()) output_st1,
(int (*) ()) encode_start_st1,
(int (*) ()) encode_end_st1}
#endif
};
static struct decode_option decode_define[] = {
/* 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},
/* lh6 */
{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 long /*short*/ dicsiz; /* t.okamoto */
static unsigned short max_hash_val;
static unsigned short hash1, hash2;
/* ------------------------------------------------------------------------ */
int
encode_alloc(method)
int method;
{
if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */
encode_set = encode_define[0];
maxmatch = 60;
dicbit = MAX_DICBIT - 3; /* 12 Changed N.Watazaki */
} else {
encode_set = encode_define[1];
maxmatch = MAXMATCH;
if (method == LZHUFF6_METHOD_NUM)
dicbit = MAX_DICBIT; /* 15 Changed N.Watazaki */
else
dicbit = MAX_DICBIT - 2; /* 13 Changed N.Watazaki */
}
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;
}
exit(207);
}
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 == 7) ? 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);
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.