Synchronet now requires the libarchive development package (e.g. libarchive-dev on Debian-based Linux distros, libarchive.org for more info) to build successfully.

lzh.c 20.1 KB
Newer Older
1 2 3 4
/* lzh.c */

/* Synchronet LZH compression library */

5
/* $Id: lzh.c,v 1.16 2020/04/17 14:08:11 deuce Exp $ */
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

/**************************************************************************** 
 * @format.tab-size 4		(Plain Text/Source Code File Header)			* 
 * @format.use-tabs true	(see http://www.synchro.net/ptsc_hdr.html)		*
 *																			*
 * Rob Swindell's conversion of 1988 LZH (LHarc) encoding functions			* 
 * Based on Japanese version 29-NOV-1988									* 
 * LZSS coded by Haruhiko Okumura											* 
 * Adaptive Huffman Coding coded by Haruyasu Yoshizaki						* 
 *																			*
 * Anonymous FTP access to the most recent released source is available at	*
 * ftp://vert.synchro.net, ftp://cvs.synchro.net and ftp://ftp.synchro.net	*
 *																			*
 * Anonymous CVS access to the development source and modification history	*
 * is available at cvs.synchro.net:/cvsroot/sbbs, example:					*
 * cvs -d :pserver:anonymous@cvs.synchro.net:/cvsroot/sbbs login			*
 *     (just hit return, no password is necessary)							*
 * cvs -d :pserver:anonymous@cvs.synchro.net:/cvsroot/sbbs checkout src		*
 *																			*
 * For Synchronet coding style and modification guidelines, see				*
 * http://www.synchro.net/source.html										*
 *																			*
 * You are encouraged to submit any modifications (preferably in Unix diff	*
 * format) via e-mail to mods@synchro.net									*
 *																			*
 * Note: If this box doesn't appear square, then you need to fix your tabs.	*
 ****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
38 39 40

/* FreeBSD's malloc.h is deprecated, it drops a warning and */
/* #includes <stdlib.h>, which is already here.             */
41 42
#if !defined(__unix__)
	#include <malloc.h>
43 44
#endif

45 46
#include "lzh.h"

deuce's avatar
deuce committed
47 48 49 50 51
#define REALLOC realloc
#define LMALLOC malloc
#define MALLOC malloc
#define LFREE free
#define FREE free
52 53 54 55 56 57 58 59 60 61



/* LZSS Parameters */

#define LZH_N			4096	/* Size of string buffer */
#define LZH_F			60		/* Size of look-ahead buffer */
#define LZH_THRESHOLD	2
#define LZH_NIL 		LZH_N	/* End of tree's node  */

62 63 64 65 66 67 68 69 70 71 72 73 74
/* Huffman coding parameters */

#define LZH_N_CHAR		(256 - LZH_THRESHOLD + LZH_F)
					/* character code (= 0..LZH_N_CHAR-1) */
#define LZH_T		(LZH_N_CHAR * 2 - 1)	/* Size of table */
#define LZH_R		(LZH_T - 1) 		/* root position */
#define MAX_FREQ	0x8000
					/* update when cumulative frequency */
					/* reaches to this value */

/* Converted from global variables to struct Apr-21-2003 */
typedef struct {

75 76
#ifdef LZH_DYNAMIC_BUF

77 78 79
	unsigned char*	text_buf;
	short int		match_position, match_length,
					*lson, *rson, *dad;
80

81
	unsigned short*	freq;	 /* cumulative freq table */
82

83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
	/*
	 * pointing parent nodes.
	 * area [LZH_T..(LZH_T + LZH_N_CHAR - 1)] are pointers for leaves
	 */
	short int*		prnt;

	/* pointing children nodes (son[], son[] + 1)*/
	short int*		son;

#else	/* STATIC */

	unsigned char	text_buf[LZH_N + LZH_F - 1];
	short int		match_position, match_length,
					lson[LZH_N + 1], rson[LZH_N + 257], dad[LZH_N + 1];

	unsigned short	freq[LZH_T + 1];   /* cumulative freq table */
	short int		prnt[LZH_T + LZH_N_CHAR];
	short int		son[LZH_T + 1];		  /* bug fixed by Digital Dynamics */
101 102 103

#endif

104
	unsigned short	getbuf;		/* Was just "unsigned" fixed 04/12/95 */
105
	uint8_t			getlen;
106
	unsigned		putbuf;
107
	uint8_t			putlen;
108

109 110 111 112 113
	unsigned short	code, len;

} lzh_t;

static void lzh_init_tree(lzh_t* lzh)  /* Initializing tree */
114 115 116 117
{
	short int  i;

	for (i = LZH_N + 1; i <= LZH_N + 256; i++)
118
		lzh->rson[i] = LZH_NIL;			/* root */
119
	for (i = 0; i < LZH_N; i++)
120
		lzh->dad[i] = LZH_NIL;			/* node */
121 122 123 124 125 126
}

/******************************/
/* Inserting node to the tree */
/* Only used during encoding  */
/******************************/
127
static void lzh_insert_node(lzh_t* lzh, short int r)
128 129 130 131 132 133
{
	short int  i, p, cmp;
	unsigned char  *key;
	unsigned c;

	cmp = 1;
134
	key = lzh->text_buf+r;
135
	p = LZH_N + 1 + key[0];
136 137
	lzh->rson[r] = lzh->lson[r] = LZH_NIL;
	lzh->match_length = 0;
138 139
	for ( ; ; ) {
		if (cmp >= 0) {
140 141
			if (lzh->rson[p] != LZH_NIL)
				p = lzh->rson[p];
142
			else {
143 144
				lzh->rson[p] = r;
				lzh->dad[r] = p;
145 146 147
				return;
			}
		} else {
148 149
			if (lzh->lson[p] != LZH_NIL)
				p = lzh->lson[p];
150
			else {
151 152
				lzh->lson[p] = r;
				lzh->dad[r] = p;
153 154 155 156
				return;
			}
		}
		for (i = 1; i < LZH_F; i++)
157
			if ((cmp = key[i] - lzh->text_buf[p + i]) != 0)
158 159
				break;
		if (i > LZH_THRESHOLD) {
160 161 162
			if (i > lzh->match_length) {
				lzh->match_position = ((r - p) & (LZH_N - 1)) - 1;
				if ((lzh->match_length = i) >= LZH_F)
163 164
					break;
			}
165
			if (i == lzh->match_length) {
166
				if ((c = ((r - p) & (LZH_N - 1)) - 1) 
167 168
					< (unsigned)lzh->match_position) {
					lzh->match_position = c;
169 170 171 172
				}
			}
		}
	}
173 174 175 176 177 178 179
	lzh->dad[r] = lzh->dad[p];
	lzh->lson[r] = lzh->lson[p];
	lzh->rson[r] = lzh->rson[p];
	lzh->dad[lzh->lson[p]] = r;
	lzh->dad[lzh->rson[p]] = r;
	if (lzh->rson[lzh->dad[p]] == p)
		lzh->rson[lzh->dad[p]] = r;
180
	else
181 182
		lzh->lson[lzh->dad[p]] = r;
	lzh->dad[p] = LZH_NIL;  /* remove p */
183 184
}

185
static void lzh_delete_node(lzh_t* lzh, short int p)  /* Deleting node from the tree */
186 187 188
{
	short int  q;

189
	if (lzh->dad[p] == LZH_NIL)
190
		return;			/* unregistered */
191 192
	if (lzh->rson[p] == LZH_NIL)
		q = lzh->lson[p];
193
	else
194 195
	if (lzh->lson[p] == LZH_NIL)
		q = lzh->rson[p];
196
	else {
197 198
		q = lzh->lson[p];
		if (lzh->rson[q] != LZH_NIL) {
199
			do {
200 201 202 203 204 205
				q = lzh->rson[q];
			} while (lzh->rson[q] != LZH_NIL);
			lzh->rson[lzh->dad[q]] = lzh->lson[q];
			lzh->dad[lzh->lson[q]] = lzh->dad[q];
			lzh->lson[q] = lzh->lson[p];
			lzh->dad[lzh->lson[p]] = q;
206
		}
207 208
		lzh->rson[q] = lzh->rson[p];
		lzh->dad[lzh->rson[p]] = q;
209
	}
210 211 212
	lzh->dad[q] = lzh->dad[p];
	if (lzh->rson[lzh->dad[p]] == p)
		lzh->rson[lzh->dad[p]] = q;
213
	else
214 215
		lzh->lson[lzh->dad[p]] = q;
	lzh->dad[p] = LZH_NIL;
216 217 218 219 220 221 222
}

/*
 * Tables for encoding/decoding upper 6 bits of
 * sliding dictionary pointer
 */
/* encoder table */
223
static uint8_t lzh_p_len[64] = {
224 225 226 227 228 229 230 231 232 233
	0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
	0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
};

234
static uint8_t lzh_p_code[64] = {
235 236 237 238 239 240 241 242 243 244 245
	0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
	0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
	0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
	0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
	0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
	0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
	0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
	0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
};

/* decoder table */
246
static uint8_t lzh_d_code[256] = {
247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
	0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
	0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
	0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
	0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
	0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
	0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
	0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
	0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
	0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
	0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
	0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
	0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
	0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
	0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
	0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
	0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
	0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
	0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
	0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
	0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
	0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
};

281
static uint8_t lzh_d_len[256] = {
282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
	0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
	0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
	0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
	0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
	0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
	0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
	0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
	0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
};


deuce's avatar
deuce committed
317
static int lzh_getbit(lzh_t* lzh, uint8_t *inbuf, int32_t *incnt, long inlen)    /* get one bit */
318 319 320
{
	short int i;

321
	while (lzh->getlen <= 8) {
322 323 324 325
		if((*incnt)>=inlen)
			i=0;
		else
			i=inbuf[(*incnt)++];
326 327
		lzh->getbuf |= i << (8 - lzh->getlen);
		lzh->getlen += 8;
328
	}
329 330 331
	i = lzh->getbuf;
	lzh->getbuf <<= 1;
	lzh->getlen--;
332 333 334
	return (i < 0);
}

deuce's avatar
deuce committed
335
static short int lzh_getbyte(lzh_t* lzh, uint8_t *inbuf, int32_t *incnt, long inlen)   /* get a byte */
336 337 338
{
	unsigned short i;

339
	while (lzh->getlen <= 8) {
340 341 342 343
		if((*incnt)>=inlen)
			i=0;
		else
			i=inbuf[(*incnt)++];
344 345
		lzh->getbuf |= i << (8 - lzh->getlen);
		lzh->getlen += 8;
346
	}
347 348 349
	i = lzh->getbuf;
	lzh->getbuf <<= 8;
	lzh->getlen -= 8;
350 351 352 353 354
	return i >> 8;
}


/* output c bits */
deuce's avatar
deuce committed
355
static void lzh_putcode(lzh_t* lzh, short int l, unsigned short c, uint8_t *outbuf, int32_t *outlen)
356
{
357 358 359 360 361 362 363
	lzh->putbuf |= c >> lzh->putlen;
	if ((lzh->putlen += l) >= 8) {
		outbuf[(*outlen)++]=(lzh->putbuf >> 8);
		if ((lzh->putlen -= 8) >= 8) {
			outbuf[(*outlen)++]=lzh->putbuf;
			lzh->putlen -= 8;
			lzh->putbuf = c << (l - lzh->putlen);
364
		} else {
365
			lzh->putbuf <<= 8;
366 367 368 369 370 371 372
		}
	}
}


/* initialize freq tree */

373
static void lzh_start_huff(lzh_t* lzh)
374 375 376 377
{
	short int i, j;

	for (i = 0; i < LZH_N_CHAR; i++) {
378 379 380
		lzh->freq[i] = 1;
		lzh->son[i] = i + LZH_T;
		lzh->prnt[i + LZH_T] = i;
381 382 383
	}
	i = 0; j = LZH_N_CHAR;
	while (j <= LZH_R) {
384 385 386
		lzh->freq[j] = lzh->freq[i] + lzh->freq[i + 1];
		lzh->son[j] = i;
		lzh->prnt[i] = lzh->prnt[i + 1] = j;
387 388
		i += 2; j++;
	}
389 390
	lzh->freq[LZH_T] = 0xffff;
    lzh->prnt[LZH_R] = 0;
391 392 393 394 395
}


/* reconstruct freq tree */

396
static void lzh_reconst(lzh_t* lzh)
397 398 399 400 401 402 403
{
	short int i, j, k;
	unsigned short f, l;

	/* halven cumulative freq for leaf nodes */
	j = 0;
	for (i = 0; i < LZH_T; i++) {
404 405 406
		if (lzh->son[i] >= LZH_T) {
			lzh->freq[j] = (lzh->freq[i] + 1) / 2;
			lzh->son[j] = lzh->son[i];
407 408 409 410 411 412
			j++;
		}
	}
	/* make a tree : first, connect children nodes */
	for (i = 0, j = LZH_N_CHAR; j < LZH_T; i += 2, j++) {
		k = i + 1;
413 414
		f = lzh->freq[j] = lzh->freq[i] + lzh->freq[k];
		for (k = j - 1; f < lzh->freq[k]; k--);
415 416 417 418 419 420
		k++;
		l = (j - k) * 2;
		
		/* movmem() is Turbo-C dependent
		   rewritten to memmove() by Kenji */
		
421 422 423 424 425 426
		/* movmem(&lzh->freq[k], &lzh->freq[k + 1], l); */
		(void)memmove(lzh->freq+k+1,lzh->freq+k, l);
		lzh->freq[k] = f;
		/* movmem(&lzh->son[k], &lzh->son[k + 1], l); */
		(void)memmove(lzh->son+k+1,lzh->son+k, l);
		lzh->son[k] = i;
427 428 429
	}
	/* connect parent nodes */
	for (i = 0; i < LZH_T; i++) {
430 431
		if ((k = lzh->son[i]) >= LZH_T) {
			lzh->prnt[k] = i;
432
		} else {
433
			lzh->prnt[k] = lzh->prnt[k + 1] = i;
434 435 436 437 438 439
		}
	}
}

/* update freq tree */

440
static void lzh_update(lzh_t* lzh, short int c)
441 442 443
{
	short int i, j, k, l;

444 445
	if (lzh->freq[LZH_R] == MAX_FREQ) {
		lzh_reconst(lzh);
446
	}
447
	c = lzh->prnt[c + LZH_T];
448
	do {
449
		k = ++lzh->freq[c];
450 451

		/* swap nodes to keep the tree freq-ordered */
452
		if (((unsigned)k) > ((unsigned)lzh->freq[l = c + 1])) {
453
			while (l < (sizeof(lzh->freq) / sizeof(lzh->freq[0]) - 1) && k > lzh->freq[++l]);
454
			l--;
455 456
			lzh->freq[c] = lzh->freq[l];
			lzh->freq[l] = k;
457

458 459 460
			i = lzh->son[c];
			lzh->prnt[i] = l;
			if (i < LZH_T) lzh->prnt[i + 1] = l;
461

462 463
			j = lzh->son[l];
			lzh->son[l] = i;
464

465 466 467
			lzh->prnt[j] = c;
			if (j < LZH_T) lzh->prnt[j + 1] = c;
			lzh->son[c] = j;
468 469 470

			c = l;
		}
471
	} while (((c = lzh->prnt[c]) != 0) && c < ((sizeof(lzh->son)/sizeof(lzh->son[0]))-1));	/* do it until reaching the root */
472 473
}

deuce's avatar
deuce committed
474
static void lzh_encode_char(lzh_t* lzh, unsigned short c, uint8_t *outbuf, int32_t *outlen)
475 476 477 478 479 480
{
	unsigned short i;
	short int j, k;

	i = 0;
	j = 0;
481
	k = lzh->prnt[c + LZH_T];
482 483 484 485 486 487 488 489 490 491 492 493

	/* search connections from leaf node to the root */
	do {
		i >>= 1;

		/*
		if node's address is odd, output 1
		else output 0
		*/
		if (k & 1) i += 0x8000;

		j++;
494 495 496 497 498
	} while ((k = lzh->prnt[k]) != LZH_R);
	lzh_putcode(lzh, j, i, outbuf, outlen);
	lzh->code = i;
	lzh->len = j;
	lzh_update(lzh,c);
499 500
}

deuce's avatar
deuce committed
501
static void lzh_encode_position(lzh_t* lzh, unsigned short c, uint8_t *outbuf, int32_t *outlen)
502 503 504 505 506
{
	unsigned short i;

	/* output upper 6 bits with encoding */
	i = c >> 6;
507
	lzh_putcode(lzh, lzh_p_len[i], (unsigned short)(lzh_p_code[i] << 8), outbuf, outlen);
508 509

	/* output lower 6 bits directly */
510
	lzh_putcode(lzh, 6, (unsigned short)((c & 0x3f) << 10), outbuf, outlen);
511 512
}

deuce's avatar
deuce committed
513
static void lzh_encode_end(lzh_t* lzh, uint8_t *outbuf, int32_t *outlen)
514
{
515 516
	if (lzh->putlen) {
		outbuf[(*outlen)++]=(lzh->putbuf >> 8);
517 518 519
	}
}

deuce's avatar
deuce committed
520
static short int lzh_decode_char(lzh_t* lzh, uint8_t *inbuf, int32_t *incnt, long inlen)
521 522 523
{
	unsigned short c;

524
	c = lzh->son[LZH_R];
525 526 527

	/*
	 * start searching tree from the root to leaves.
528 529
	 * choose node #(lzh.son[]) if input bit == 0
	 * else choose #(lzh.son[]+1) (input bit == 1)
530 531
	 */
	while (c < LZH_T) {
532 533
		c += lzh_getbit(lzh,inbuf,incnt,inlen);
		c = lzh->son[c];
534 535
	}
	c -= LZH_T;
536
	lzh_update(lzh,c);
537 538 539
	return c;
}

deuce's avatar
deuce committed
540
static short int lzh_decode_position(lzh_t* lzh, uint8_t *inbuf, int32_t *incnt, long inlen)
541 542 543 544
{
	unsigned short i, j, c;

	/* decode upper 6 bits from given table */
545
	i = lzh_getbyte(lzh,inbuf,incnt,inlen);
546 547 548 549 550 551
	c = (unsigned)lzh_d_code[i] << 6;
	j = lzh_d_len[i];

	/* input lower 6 bits directly */
	j -= 2;
	while (j--) {
552
		i = (i << 1) + lzh_getbit(lzh,inbuf,incnt,inlen);
553
	}
rswindell's avatar
rswindell committed
554
	return c | (i & 0x3f);
555 556 557 558 559 560
}

/* Compression */

/* Encoding/Compressing */
/* Returns length of outbuf */
561
int32_t lzh_encode(uint8_t *inbuf, int32_t inlen, uint8_t *outbuf)
562 563
{
	short int  i, c, len, r, s, last_match_length;
564
	int32_t incnt,outlen; /* textsize=0; */
565 566
	lzh_t lzh;
	memset(&lzh,0,sizeof(lzh));
567 568 569

#ifdef LZH_DYNAMIC_BUF

570
	if((lzh.text_buf=(uint8_t *)malloc(LZH_N + LZH_F - 1))==NULL)
571
		return(-1);
deuce's avatar
deuce committed
572 573
	if((lzh.freq=(unsigned short*)malloc((LZH_T + 1)*sizeof(unsigned short)))==NULL) {
		free(lzh.text_buf);
574
		return(-1); }
deuce's avatar
deuce committed
575 576 577
	if((lzh.prnt=(short *)malloc((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) {
		free(lzh.text_buf);
		free(lzh.freq);
578
		return(-1); }
deuce's avatar
deuce committed
579 580 581 582
	if((lzh.son=(short *)malloc((LZH_T + 1) * sizeof(short)))==NULL) {
		free(lzh.text_buf);
		free(lzh.prnt);
		free(lzh.freq);
583
		return(-1); }
deuce's avatar
deuce committed
584 585 586 587 588
	if((lzh.lson=(short *)malloc((LZH_N + 1)*sizeof(short)))==NULL) {
		free(lzh.text_buf);
		free(lzh.prnt);
		free(lzh.freq);
		free(lzh.son);
589
		return(-1); }
deuce's avatar
deuce committed
590 591 592 593 594 595
	if((lzh.rson=(short *)malloc((LZH_N + 257)*sizeof(short)))==NULL) {
		free(lzh.text_buf);
		free(lzh.prnt);
		free(lzh.freq);
		free(lzh.son);
		free(lzh.lson);
596
		return(-1); }
deuce's avatar
deuce committed
597 598 599 600 601 602 603
	if((lzh.dad=(short *)malloc((LZH_N + 1)*sizeof(short)))==NULL) {
		free(lzh.text_buf);
		free(lzh.prnt);
		free(lzh.freq);
		free(lzh.son);
        free(lzh.lson);
		free(lzh.rson);
604 605 606 607 608 609 610 611
		return(-1); }
#endif

	incnt=0;
	memcpy(outbuf,&inlen,sizeof(inlen));
	outlen=sizeof(inlen);
	if(!inlen) {
#ifdef LZH_DYNAMIC_BUF
deuce's avatar
deuce committed
612 613 614 615 616 617 618
		free(lzh.text_buf);
		free(lzh.prnt);
		free(lzh.freq);
		free(lzh.son);
        free(lzh.lson);
        free(lzh.rson);
		free(lzh.dad);
619 620
#endif
		return(outlen); }
621 622
	lzh_start_huff(&lzh);
	lzh_init_tree(&lzh);
623 624 625
	s = 0;
	r = LZH_N - LZH_F;
	for (i = s; i < r; i++)
626
		lzh.text_buf[i] = ' ';
627
	for (len = 0; len < LZH_F && incnt<inlen; len++)
628
		lzh.text_buf[r + len] = inbuf[incnt++];
629 630
	/* textsize = len; */
	for (i = 1; i <= LZH_F; i++)
631 632
		lzh_insert_node(&lzh,(short)(r - i));
	lzh_insert_node(&lzh,r);
633
	do {
634 635 636 637 638
		if (lzh.match_length > len)
			lzh.match_length = len;
		if (lzh.match_length <= LZH_THRESHOLD) {
			lzh.match_length = 1;
			lzh_encode_char(&lzh,lzh.text_buf[r],outbuf,&outlen);
639
		} else {
640
			lzh_encode_char(&lzh,(unsigned short)(255 - LZH_THRESHOLD + lzh.match_length)
641
				,outbuf,&outlen);
642
			lzh_encode_position(&lzh,lzh.match_position
643 644
				,outbuf,&outlen);
		}
645
		last_match_length = lzh.match_length;
646
		for (i = 0; i < last_match_length && incnt<inlen; i++) {
647
			lzh_delete_node(&lzh,s);
648
			c=inbuf[incnt++];
649
			lzh.text_buf[s] = (uint8_t)c;
650
			if (s < LZH_F - 1)
651
				lzh.text_buf[s + LZH_N] = (uint8_t)c;
652 653
			s = (s + 1) & (LZH_N - 1);
			r = (r + 1) & (LZH_N - 1);
654
			lzh_insert_node(&lzh,r);
655 656 657 658 659 660 661 662
		}
/***
		if ((textsize += i) > printcount) {
			printf("%12ld\r", textsize);
			printcount += 1024;
		}
***/
		while (i++ < last_match_length) {
663
			lzh_delete_node(&lzh,s);
664 665
			s = (s + 1) & (LZH_N - 1);
			r = (r + 1) & (LZH_N - 1);
666
			if (--len) lzh_insert_node(&lzh,r);
667 668
		}
	} while (len > 0);
669
	lzh_encode_end(&lzh,outbuf,&outlen);
670 671 672 673 674 675 676
/*
	printf("input: %ld (%ld) bytes\n", inlen,textsize);
	printf("output: %ld bytes\n", outlen);
	printf("output/input: %.3f\n", (double)outlen / inlen);
*/

#ifdef LZH_DYNAMIC_BUF
deuce's avatar
deuce committed
677 678 679 680 681 682 683
	free(lzh.text_buf);
	free(lzh.prnt);
	free(lzh.freq);
	free(lzh.son);
	free(lzh.lson);
	free(lzh.rson);
	free(lzh.dad);
684 685 686 687 688 689 690
#endif

	return(outlen);
}

/* Decoding/Uncompressing */
/* Returns length of outbuf */
691
int32_t lzh_decode(uint8_t *inbuf, int32_t inlen, uint8_t *outbuf)
692 693
{
	short int  i, j, k, r, c;
694 695
	uint32_t	count;
	int32_t		incnt,textsize;
696
	lzh_t lzh;
697

698
	memset(&lzh,0,sizeof(lzh));
699 700
#ifdef LZH_DYNAMIC_BUF

701
	if((lzh.text_buf=(uint8_t *)malloc((LZH_N + LZH_F - 1)*2))==NULL)
702
		return(-1);
deuce's avatar
deuce committed
703
	if((lzh.freq=(unsigned short *)malloc((LZH_T + 1)*sizeof(unsigned short)))
704
		==NULL) {
deuce's avatar
deuce committed
705
		free(lzh.text_buf);
706
		return(-1); }
deuce's avatar
deuce committed
707 708 709
	if((lzh.prnt=(short *)malloc((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) {
		free(lzh.text_buf);
		free(lzh.freq);
710
		return(-1); }
deuce's avatar
deuce committed
711 712 713 714
	if((lzh.son=(short *)malloc((LZH_T + 1) * sizeof(short)))==NULL) {
		free(lzh.text_buf);
		free(lzh.prnt);
		free(lzh.freq);
715 716 717 718 719 720 721 722 723
		return(-1); }

#endif

	incnt=0;
	memcpy(&textsize,inbuf,sizeof(textsize));
	incnt+=sizeof(textsize);
	if (textsize == 0) {
#ifdef LZH_DYNAMIC_BUF
deuce's avatar
deuce committed
724 725 726 727
		free(lzh.text_buf);
		free(lzh.prnt);
		free(lzh.freq);
		free(lzh.son);
728 729
#endif
		return(textsize); }
730
	lzh_start_huff(&lzh);
731
	for (i = 0; i < LZH_N - LZH_F; i++)
732
		*(lzh.text_buf+i) = ' ';
733
	r = LZH_N - LZH_F;
734
    for (count = 0; count < (unsigned long)textsize; ) {
735
		c = lzh_decode_char(&lzh,inbuf,&incnt,inlen);
736
		if (c < 256) {
737
			outbuf[count]=(uint8_t)c;
738 739 740 741 742 743
#if 0
			if(r>(LZH_N + LZH_F - 1) || r<0) {
				printf("Overflow! (%d)\n",r);
				getch();
				exit(-1); }
#endif
744
			*(lzh.text_buf+r) = (uint8_t)c;
745 746 747 748
			r++;
			r &= (LZH_N - 1);
			count++;
		} else {
749
			i = (r - lzh_decode_position(&lzh,inbuf,&incnt,inlen) - 1)
750 751
				& (LZH_N - 1);
			j = c - 255 + LZH_THRESHOLD;
752
			for (k = 0; k < j && count<(unsigned long)textsize; k++) {
753
				c = lzh.text_buf[(i + k) & (LZH_N - 1)];
754
				outbuf[count]=(uint8_t)c;
755 756 757 758 759
#if 0
				if(r>(LZH_N + LZH_F - 1) || r<0) {
					printf("Overflow! (%d)\n",r);
					exit(-1); }
#endif
760
				*(lzh.text_buf+r) = (uint8_t)c;
761 762 763 764 765 766 767 768 769 770 771
				r++;
				r &= (LZH_N - 1);
				count++;
			}
		}
	}
/***
	printf("%12ld\n", count);
***/

#ifdef LZH_DYNAMIC_BUF
deuce's avatar
deuce committed
772 773 774 775
	free(lzh.text_buf);
	free(lzh.prnt);
	free(lzh.freq);
	free(lzh.son);
776 777 778 779 780 781
#endif

return(count);
}