encode.cpp

Award bios编辑器

//
// Award BIOS Editor - encode.cpp
// [ sliding dictionary with percolating update ]
//
// $Id: encode.cpp,v 1.3 2004/04/11 07:17:16 bpoint Exp $
//
//----------------------------------------------------------------------------
//
// Award BIOS Editor's LZH Engine was adapted from "ar" archiver written by 
// Haruhiko Okumura.
// 

#include "lzhEngine.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 ushort 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 = (uchar *)malloc(DICSIZ * 2 + MAXMATCH);
	level      = (uchar *)malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
	childcount = (uchar *)malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
	#if PERCOLATE
	  position = (short *)malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
	#else
	  position = (short *)malloc(DICSIZ * sizeof(*position));
	#endif
	parent     = (short *)malloc(DICSIZ * 2 * sizeof(*parent));
	prev       = (short *)malloc(DICSIZ * 2 * sizeof(*prev));
	next       = (short *)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 newnode, t;

	newnode = avail;  avail = next[newnode];  childcount[newnode] = 0;
	t = prev[old];  prev[newnode] = t;  next[t] = newnode;
	t = next[old];  next[newnode] = t;  prev[t] = newnode;
	parent[newnode] = parent[old];
	level[newnode] = (uchar)matchlen;
	position[newnode] = pos;
	makechild(newnode, text[matchpos + matchlen], old);
	makechild(newnode, 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 = memread_crc(&text[DICSIZ + MAXMATCH], DICSIZ);
		remainder += n;  pos = DICSIZ;  //putc('.', stderr);
	}
	delete_node();  insert_node();
}

void encode(void)
{
	ushort lastmatchlen;
	node lastmatchpos;

	allocate_memory();  init_slide();  huf_encode_start();
	remainder = memread_crc(&text[DICSIZ], DICSIZ + MAXMATCH);
//	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();
}