lzd.c

#pragma prototyped

/*
 * lzd decoder snarfed from the public domain booz -- Rahul Dhesi 1991/07/07
 */

#include <codex.h>

#define MEM_BLOCK_SIZE	8192
#define OUT_BUF_SIZE	(MEM_BLOCK_SIZE/2)
#define IN_BUF_SIZE	(MEM_BLOCK_SIZE/2)

#define STACKSIZE	2000
#define INBUFSIZ	(IN_BUF_SIZE - SPARE)
#define OUTBUFSIZ	(OUT_BUF_SIZE - SPARE)
#define MEMERR		2
#define IOERR		1
#define MAXBITS		13
#define CLEAR		256         /* clear code */
#define Z_EOF		257         /* end of file marker */
#define FIRST_FREE	258         /* first free code */
#define MAXMAX		8192        /* max code + 1 */
#define SPARE		4

typedef struct Table_s
{
	unsigned int	next;
	char		z_ch;
} Table_t;

typedef struct State_s
{
	Codex_t*	codex;

	unsigned char	buf[SF_BUFSIZE];
	unsigned char*	ip;
	unsigned char*	ie;

	unsigned long	bitbuf;
	unsigned short	bitcount;
	unsigned short	bitmask;

	unsigned int	old_code;
	unsigned int	suf_code;
	unsigned int	max_code;
	unsigned int	free_code;
	unsigned int	in_code;
	unsigned int	fin_char;
	unsigned int	nbits;
	unsigned int	cpy;
	unsigned int	bad;
	unsigned int	eof;
	unsigned int	sp;
	unsigned int	stack[STACKSIZE + SPARE];

	Table_t		table[MAXMAX];

	char		spare[SPARE];
} State_t;

#define GETCHAR(p)	((p)->ip < (p)->ie ? (int)*(p)->ip++ : fill(p))

static int
fill(State_t* state)
{
	ssize_t	r;

	if (state->eof)
		return 0;
	if ((r = sfrd(state->codex->sp, state->buf, sizeof(state->buf), &state->codex->sfdisc)) <= 0)
	{
		state->eof = 1;
		return 0;
	}
	state->ie = (state->ip = state->buf) + r;
	return *state->ip++;
}

static int
getcode(State_t* state)
{
	unsigned short	x;

	while (state->nbits > state->bitcount)
	{
		state->bitbuf |= GETCHAR(state) << state->bitcount;
		state->bitcount += 8;
	}
	x = state->bitbuf & state->bitmask;
	state->bitbuf >>= state->nbits;
	state->bitcount -= state->nbits;
	return state->eof ? Z_EOF : x;
}

static void
push(State_t* state, int c)
{
	state->stack[state->sp++] = c;
	if (state->sp >= STACKSIZE)
		state->sp--;
}
   
#define pop(p)    ((p)->stack[--(p)->sp])

static void
clrcode(State_t* state)
{
	state->bitmask = (1 << (state->nbits = 9)) - 1;
	state->max_code = 512;
	state->free_code = FIRST_FREE;
}

static void
addcode(register State_t* state, int suf_code, int old_code)
{
	state->table[state->free_code].z_ch = suf_code;
	state->table[state->free_code].next = old_code;
	if (++state->free_code >= state->max_code && state->nbits < MAXBITS)
	{
		state->nbits++;
		state->bitmask <<= 1;
		state->bitmask |= 1;
		state->max_code = state->max_code << 1;
	}
}

static int
lzd_open(Codex_t* p, char* const args[], Codexnum_t flags)
{
	register State_t*		state;

	if (!(state = newof(0, State_t, 1, 0)))
	{
		if (p->disc->errorf)
			(*p->disc->errorf)(NiL, p->disc, 2, "out of space");
		return -1;
	}
	state->codex = p;
	p->data = state;
	return 0;
}

static int
lzd_init(Codex_t* p)
{
	register State_t*	state = (State_t*)p->data;

	state->bitcount = 0;
	state->bad = state->cpy = state->eof = 0;
	state->ip = state->ie = 0;
	state->sp = 0;
	clrcode(state);
	return 0;
}

static ssize_t
lzd_read(Sfio_t* sp, void* buf, size_t n, Sfdisc_t* disc)
{
	register State_t*	state = (State_t*)CODEX(disc)->data;
	register char*		s = (char*)buf;
	register char*		e = s + n;
	register int		c;

	if (state->eof)
		return state->bad;
	if (state->cpy)
	{
		state->cpy = 0;
		while (state->sp != 0)
		{
			*s++ = pop(state);
			if (s >= e)
			{
				state->cpy = 1;
				return s - (char*)buf;
			}
		}
	}
	while ((c = getcode(state)) != Z_EOF)
	{
		if (c == CLEAR)
		{
			clrcode(state);
			*s++ = state->fin_char = state->suf_code = state->old_code = c = getcode(state);
			if (s >= e)
				return s - (char*)buf;
		}
		else
		{
			state->in_code = c;
			if (c >= state->free_code)
			{
				c = state->old_code;
				push(state, state->fin_char);
			}
			while (c > 255)
			{
				push(state, state->table[c].z_ch);
				c = state->table[c].next;
			}
			state->suf_code = state->fin_char = c;
			addcode(state, state->suf_code, state->old_code);
			state->old_code = state->in_code;
			push(state, state->suf_code);
			while (state->sp != 0)
			{
				*s++ = pop(state);
				if (s >= e)
				{
					state->cpy = 1;
					return s - (char*)buf;
				}
			}
		}
	}
	state->eof = 1;
	return s - (char*)buf;
}

Codexmeth_t	codex_lzd =
{
	"lzd",
	"\bzoo\b(1) archive lzd compression.",
	"[+(version)?codex-lzd 1991-07-07]"
	"[+(author)?Rahul Dhesi]",
	CODEX_DECODE|CODEX_COMPRESS,
	0,
	0,
	lzd_open,
	0,
	lzd_init,
	0,
	lzd_read,
	0,
	0,
	0,
	0,
	0,
	0,
	CODEXNEXT(lzd)
};

CODEXLIB(lzd)