Algorithm 版 (精华区)
发信人: lofe ()感激生活(), 信区: Algorithm
标 题: ar002--encode.c
发信站: 哈工大紫丁香 (Sun Sep 3 08:27:39 2000), 转信
/***********************************************************
encode.c -- sliding dictionary with percolating update
***********************************************************/
#include "ar.h"
#include <stdlib.h>
#include <string.h> /* memmove() */
#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;
#else
static ushort *level;
#endif
static void allocate_memory(void)
{
if (next != NULL) return;
text = malloc(DICSIZ * 2 + MAXMATCH);
level = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
childcount = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
#if PERCOLATE
position = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
#else
position = malloc(DICSIZ * sizeof(*position));
#endif
parent = malloc(DICSIZ * 2 * sizeof(*parent));
prev = malloc(DICSIZ * 2 * sizeof(*prev));
next = malloc((MAX_HASH_VAL + 1) * sizeof(*next));
if (next == NULL) error("Out of memory.");
}
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;
}
#define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
static node child(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(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(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;
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];
}
#if 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(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] & ~PERC_FLAG;
#else
t = position[r];
#endif
if (t >= pos) t -= DICSIZ;
#if 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(void)
{
int n;
remainder--;
if (++pos == DICSIZ * 2) {
memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH);
n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, infile);
remainder += n; pos = DICSIZ; putc('.', stderr);
}
delete_node(); insert_node();
}
void encode(void)
{
int lastmatchlen;
node lastmatchpos;
allocate_memory(); init_slide(); huf_encode_start();
remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, infile);
putc('.', stderr);
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)
output(text[pos - 1], 0);
else {
output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
(pos - lastmatchpos - 2) & (DICSIZ - 1));
while (--lastmatchlen > 0) get_next_match();
if (matchlen > remainder) matchlen = remainder;
}
}
huf_encode_end();
}
--
We Are the World!
infosite@263.net
※ 修改:．haojs 于 Sep 3 08:25:07 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: bbs.hit.edu.cn]
--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：211.497毫秒