This is slide.c in view mode; [Download] [Up]
/* ------------------------------------------------------------------------ */
/* LHa for UNIX */
/* slice.c -- sliding dictionary with percolating update */
/* */
/* Modified Nobutaka Watazaki */
/* */
/* Ver. 1.14d Exchanging a search algorithm 1997.01.11 T.Okamoto */
/* ------------------------------------------------------------------------ */
#include "lha.h"
/* ------------------------------------------------------------------------ */
static unsigned long encoded_origsize;
/* ------------------------------------------------------------------------ */
static unsigned short *hash;
static unsigned short *prev;
static unsigned char *text;
unsigned char *too_flag;
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[] = {
/* 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;
#if 0
static node pos, matchpos, avail, *position, *parent, *prev;
static int remainder, matchlen;
static unsigned char *level, *childcount;
static unsigned long dicsiz; /* t.okamoto */
static unsigned short max_hash_val;
static unsigned short hash1, hash2;
#endif
#if 1
#define DICSIZ (1UL << 15)
#define TXTSIZ (DICSIZ * 2 + MAXMATCH)
#endif
#define HSHSIZ (1UL<<15)
#define LIMIT 0x100 /* chain 長の limit */
static unsigned int txtsiz;
static unsigned long dicsiz;
static unsigned int hval;
static int matchlen;
static unsigned int matchpos;
static unsigned int pos;
static unsigned int remainder;
/* ------------------------------------------------------------------------ */
int
encode_alloc(method)
int method;
{
if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */
encode_set = encode_define[0];
maxmatch = 60;
dicbit = 12; /* 12 Changed N.Watazaki */
} else { /* method LH4(12),LH5(13),LH6(15) */
encode_set = encode_define[1];
maxmatch = MAXMATCH;
if (method == LZHUFF6_METHOD_NUM)
dicbit = MAX_DICBIT; /* 15 bits */
else /* LH5 LH4 is not used */
dicbit = MAX_DICBIT - 2; /* 13 bits */
}
dicsiz = (1UL << dicbit);
txtsiz = dicsiz*2+maxmatch;
if (hash) return method;
if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
hash = (unsigned short*)malloc(HSHSIZ * 2);
prev = (unsigned short*)malloc(DICSIZ * 2);
text = (unsigned char*)malloc(TXTSIZ);
too_flag = (unsigned char*)malloc(HSHSIZ);
if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
exit(207);
return method;
}
/* ------------------------------------------------------------------------ */
/* ポインタの初期化 */
static void init_slide(void)
{
unsigned int i;
for (i = 0; i < HSHSIZ; i++) {
hash[i] = NIL;
too_flag[i] = 0;
}
}
/* 辞書を DICSIZ 分 前にずらす */
static void update()
{
unsigned int i, j;
unsigned int k;
long n;
#if 0
memmove(&text[0], &text[dicsiz], (unsigned)(txtsiz - dicsiz));
#else
{
int m;
i = 0; j = dicsiz; m = txtsiz-dicsiz;
while (m-- > 0) {
text[i++] = text[j++];
}
}
#endif
n = fread_crc(&text[(unsigned)(txtsiz - dicsiz)],
(unsigned)dicsiz, infile);
remainder += n;
encoded_origsize += n;
pos -= dicsiz;
for (i = 0; i < HSHSIZ; i++) {
j = hash[i];
hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
too_flag[i] = 0;
}
for (i = 0; i < dicsiz; i++) {
j = prev[i];
prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
}
}
/* 現在の文字列をチェーンに追加する */
static void insert(void)
{
prev[pos & (dicsiz - 1)] = hash[hval];
hash[hval] = pos;
}
/* 現在の文字列と最長一致する文字列を検索し、チェーンに追加する */
static void match_insert(void)
{
unsigned int scan_pos, scan_end, len;
unsigned char *a, *b;
unsigned int chain, off, h, max;
max = maxmatch; /* MAXMATCH; */
if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
matchpos = pos;
off = 0;
for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
}
if (off == maxmatch - THRESHOLD) off = 0;
for (;;) {
chain = 0;
scan_pos = hash[h];
/* scan_end = (pos > DICSIZ) ? pos + off - DICSIZ : off; */
scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
while (scan_pos > scan_end) {
chain++;
if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
{
a = text + scan_pos - off; b = text + pos;
for (len = 0; len < max && *a++ == *b++; len++);
}
if (len > matchlen) {
matchpos = scan_pos - off;
if ((matchlen = len) == max) {
break;
}
}
}
scan_pos = prev[scan_pos & (dicsiz - 1)];
}
if (chain >= LIMIT)
too_flag[h] = 1;
if (matchlen > off + 2 || off == 0)
break;
max = off + 2;
off = 0;
h = hval;
}
prev[pos & (dicsiz - 1)] = hash[hval];
hash[hval] = pos;
}
/* ポインタを進め、辞書を更新し、ハッシュ値を更新する */
static void get_next()
{
remainder--;
if (++pos >= txtsiz - maxmatch) {
update();
}
hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
}
void encode(interface)
struct interfacing *interface;
{
int lastmatchlen;
unsigned int lastmatchoffset;
infile = interface->infile;
outfile = interface->outfile;
origsize = interface->original;
compsize = count = 0L;
crc = unpackable = 0;
/* encode_alloc(); */ /* allocate_memory(); */
init_slide();
encode_set.encode_start();
memset(&text[dicsiz], ' ', dicsiz);
remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
encoded_origsize = remainder;
matchlen = THRESHOLD - 1;
pos = dicsiz;
if (matchlen > remainder) matchlen = remainder;
hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
insert();
while (remainder > 0 && ! unpackable) {
lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1;
--matchlen;
get_next(); match_insert();
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),
(lastmatchoffset) & (dicsiz-1) );
--lastmatchlen;
while (--lastmatchlen > 0) {
get_next(); insert();
count++;
}
get_next();
matchlen = THRESHOLD - 1;
match_insert();
if (matchlen > remainder) matchlen = remainder;
}
}
encode_set.encode_end();
interface->packed = compsize;
interface->original = encoded_origsize;
}
/* ------------------------------------------------------------------------ */
#if 0
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;
}
#endif
/* ------------------------------------------------------------------------ */
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.