home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
vol_300
/
379_01
/
zoo210s.zoo
/
encode.c
< prev
next >
Wrap
C/C++ Source or Header
|
1991-07-12
|
8KB
|
317 lines
/*$Source: /usr/home/dhesi/zoo/RCS/encode.c,v $*/
/*$Id: encode.c,v 1.41 91/07/09 01:39:47 dhesi Exp $*/
/*
Adapted from "ar" archiver written by Haruhiko Okumura.
*/
#include "options.h"
#include "zoo.h"
#include "ar.h"
#include "lzh.h"
extern void prterror();
extern char *out_buf_adr;
#include <assert.h>
#ifdef ANSI_HDRS
# include <stdlib.h>
# include <string.h>
#endif
#include "errors.i"
FILE *lzh_infile;
FILE *lzh_outfile;
/*
sliding dictionary with percolating update
*/
#define PERCOLATE 1
#define NIL 0
#define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)
typedef short node;
static uchar *text, *childcount;
static node pos, matchpos, avail,
*position, *parent, *prev, *next = NULL;
static int remainder, matchlen;
#if MAXMATCH <= (UCHAR_MAX + 1)
static uchar *level;
# define T_LEVEL uchar *
#else
static ushort *level;
# define T_LEVEL ushort *
#endif
static void allocate_memory()
{
if (next != NULL) return;
/* text = (uchar *) malloc(DICSIZ * 2 + MAXMATCH); */
text = (uchar *) out_buf_adr; /* reuse I/O buffer used elsewhere */
level = (T_LEVEL) malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
childcount = (uchar *)malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
#ifdef 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) prterror('f', no_memory);
}
static void init_slide()
{
node i;
for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
level[i] = 1;
#ifdef 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;
}
#define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
static node child(q, c)
node q;
uchar c;
/* q's child for character c (NIL if not found) */
{
node r;
r = next[HASH(q, c)];
parent[NIL] = q; /* sentinel */
while (parent[r] != q) r = next[r];
return r;
}
static void makechild(q, c, r)
node q;
uchar c;
node r;
/* Let r be q's child for character c. */
{
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]++;
}
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;
uchar 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];
}
#ifdef PERCOLATE
t = q;
while (position[t] < 0) {
position[t] = pos; t = parent[t];
}
if (t < DICSIZ) position[t] = pos | PERC_FLAG;
#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] & ~PERC_FLAG;
}
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()
{
#ifdef 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;
#ifdef PERCOLATE
t = position[r] & ~PERC_FLAG;
#else
t = position[r];
#endif
if (t >= pos) t -= DICSIZ;
#ifdef PERCOLATE
s = t; q = parent[r];
while ((u = position[q]) & PERC_FLAG) {
u &= ~PERC_FLAG; 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 | PERC_FLAG;
}
#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) {
#ifdef CHECK_BREAK
check_break();
#endif
(void) MOVE_LEFT((char *) &text[0], (char *) &text[DICSIZ], DICSIZ + MAXMATCH);
n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, lzh_infile);
remainder += n; pos = DICSIZ;
#ifdef SHOW_DOTS
(void) putc('.', stderr);
(void) fflush(stderr);
#endif
}
delete_node(); insert_node();
}
/* read from infile, compress, write to outfile */
void encode(infile, outfile)
FILE *infile;
FILE *outfile;
{
int lastmatchlen;
node lastmatchpos;
/* make input/output files visible to other functions */
lzh_infile = infile;
lzh_outfile = outfile;
allocate_memory(); init_slide(); huf_encode_start();
remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, lzh_infile);
#ifdef SHOW_DOTS
(void) putc('.', stderr);
(void) fflush(stderr);
#endif
matchlen = 0;
pos = DICSIZ; insert_node();
if (matchlen > remainder) matchlen = remainder;
while (remainder > 0 && ! unpackable) {
lastmatchlen = matchlen; lastmatchpos = matchpos;
get_next_match();
if (matchlen > remainder) matchlen = remainder;
if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
#if 0
d1log("%c", text[pos-1]);
#endif
output(text[pos - 1], 0);
} else {
#if 0
(void) putc('.', stderr); (void) fflush(stderr);
#endif
#if 0
{
int i;
d1log("\nlastmatchlen=%d, pos=%d, lastmatchpos=%d",
lastmatchlen, pos, lastmatchpos);
d1log("\n[%d: ", (int) lastmatchlen);
for (i = 0; i < lastmatchlen; i++)
d1log("%c", text[lastmatchpos + i]);
d1log("]\n");
}
#endif
output((uint) (lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD)),
(uint) ((pos - lastmatchpos - 2) & (DICSIZ - 1)));
while (--lastmatchlen > 0) get_next_match();
if (matchlen > remainder) matchlen = remainder;
}
}
huf_encode_end();
}
#ifdef NEED_MEMMOVE
/* like memmove, but for moving stuff LEFT (downwards in memory) only!! */
void move_left(dest, src, len)
char *dest;
char *src;
int len;
{
while (len-- > 0)
*dest++ = *src++;
}
#endif /* NEED_MEMMOVE */