![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to lzh.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Synchronet] / sbbs / smblib|
Return to lzh.c CVS log | Up to [Synchronet] / sbbs / smblib |
1.1 root 1: /* lzh.c */
2:
3: /* Synchronet LZH compression library */
4:
5: /* $Id: lzh.c,v 1.7 2003/04/22 01:19:17 rswindell Exp $ */
6:
7: /****************************************************************************
8: * @format.tab-size 4 (Plain Text/Source Code File Header) *
9: * @format.use-tabs true (see http://www.synchro.net/ptsc_hdr.html) *
10: * *
11: * Rob Swindell's conversion of 1988 LZH (LHarc) encoding functions *
12: * Based on Japanese version 29-NOV-1988 *
13: * LZSS coded by Haruhiko Okumura *
14: * Adaptive Huffman Coding coded by Haruyasu Yoshizaki *
15: * *
16: * Anonymous FTP access to the most recent released source is available at *
17: * ftp://vert.synchro.net, ftp://cvs.synchro.net and ftp://ftp.synchro.net *
18: * *
19: * Anonymous CVS access to the development source and modification history *
20: * is available at cvs.synchro.net:/cvsroot/sbbs, example: *
21: * cvs -d :pserver:[email protected]:/cvsroot/sbbs login *
22: * (just hit return, no password is necessary) *
23: * cvs -d :pserver:[email protected]:/cvsroot/sbbs checkout src *
24: * *
25: * For Synchronet coding style and modification guidelines, see *
26: * http://www.synchro.net/source.html *
27: * *
28: * You are encouraged to submit any modifications (preferably in Unix diff *
29: * format) via e-mail to [email protected] *
30: * *
31: * Note: If this box doesn't appear square, then you need to fix your tabs. *
32: ****************************************************************************/
33:
34: #include <stdio.h>
35: #include <stdlib.h>
36: #include <string.h>
37: #include <ctype.h>
38:
39: /* FreeBSD's malloc.h is deprecated, it drops a warning and */
40: /* #includes <stdlib.h>, which is already here. */
41: #if !defined(__unix__)
42: #include <malloc.h>
43: #endif
44:
45: #include "lzh.h"
46:
47: /****************************************************************************/
48: /* Memory allocation macros for various compilers and environments */
49: /* MALLOC is used for allocations of 64k or less */
50: /* FREE is used to free buffers allocated with MALLOC */
51: /* LMALLOC is used for allocations of possibly larger than 64k */
52: /* LFREE is used to free buffers allocated with LMALLOC */
53: /* REALLOC is used to re-size a previously MALLOCed or LMALLOCed buffer */
54: /****************************************************************************/
55: #if defined(__COMPACT__) || defined(__LARGE__) || defined(__HUGE__)
56: #if defined(__TURBOC__)
57: #define REALLOC(x,y) farrealloc(x,y)
58: #define LMALLOC(x) farmalloc(x)
59: #define MALLOC(x) farmalloc(x)
60: #define LFREE(x) farfree(x)
61: #define FREE(x) farfree(x)
62: #elif defined(__WATCOMC__)
63: #define REALLOC realloc
64: #define LMALLOC(x) halloc(x,1) /* far heap, but slow */
65: #define MALLOC malloc /* far heap, but 64k max */
66: #define LFREE hfree
67: #define FREE free
68: #else /* Other 16-bit Compiler */
69: #define REALLOC realloc
70: #define LMALLOC malloc
71: #define MALLOC malloc
72: #define LFREE free
73: #define FREE free
74: #endif
75: #else /* 32-bit Compiler or Small Memory Model */
76: #define REALLOC realloc
77: #define LMALLOC malloc
78: #define MALLOC malloc
79: #define LFREE free
80: #define FREE free
81: #endif
82:
83:
84:
85: /* LZSS Parameters */
86:
87: #define LZH_N 4096 /* Size of string buffer */
88: #define LZH_F 60 /* Size of look-ahead buffer */
89: #define LZH_THRESHOLD 2
90: #define LZH_NIL LZH_N /* End of tree's node */
91:
92: /* Huffman coding parameters */
93:
94: #define LZH_N_CHAR (256 - LZH_THRESHOLD + LZH_F)
95: /* character code (= 0..LZH_N_CHAR-1) */
96: #define LZH_T (LZH_N_CHAR * 2 - 1) /* Size of table */
97: #define LZH_R (LZH_T - 1) /* root position */
98: #define MAX_FREQ 0x8000
99: /* update when cumulative frequency */
100: /* reaches to this value */
101:
102: /* Converted from global variables to struct Apr-21-2003 */
103: typedef struct {
104:
105: #ifdef LZH_DYNAMIC_BUF
106:
107: unsigned char* text_buf;
108: short int match_position, match_length,
109: *lson, *rson, *dad;
110:
111: unsigned short* freq; /* cumulative freq table */
112:
113: /*
114: * pointing parent nodes.
115: * area [LZH_T..(LZH_T + LZH_N_CHAR - 1)] are pointers for leaves
116: */
117: short int* prnt;
118:
119: /* pointing children nodes (son[], son[] + 1)*/
120: short int* son;
121:
122: #else /* STATIC */
123:
124: unsigned char text_buf[LZH_N + LZH_F - 1];
125: short int match_position, match_length,
126: lson[LZH_N + 1], rson[LZH_N + 257], dad[LZH_N + 1];
127:
128: unsigned short freq[LZH_T + 1]; /* cumulative freq table */
129: short int prnt[LZH_T + LZH_N_CHAR];
130: short int son[LZH_T + 1]; /* bug fixed by Digital Dynamics */
131:
132: #endif
133:
134: unsigned short getbuf; /* Was just "unsigned" fixed 04/12/95 */
135: uchar getlen;
136: unsigned putbuf;
137: uchar putlen;
138:
139: unsigned short code, len;
140:
141: } lzh_t;
142:
143: static void lzh_init_tree(lzh_t* lzh) /* Initializing tree */
144: {
145: short int i;
146:
147: for (i = LZH_N + 1; i <= LZH_N + 256; i++)
148: lzh->rson[i] = LZH_NIL; /* root */
149: for (i = 0; i < LZH_N; i++)
150: lzh->dad[i] = LZH_NIL; /* node */
151: }
152:
153: /******************************/
154: /* Inserting node to the tree */
155: /* Only used during encoding */
156: /******************************/
157: static void lzh_insert_node(lzh_t* lzh, short int r)
158: {
159: short int i, p, cmp;
160: unsigned char *key;
161: unsigned c;
162:
163: cmp = 1;
164: key = lzh->text_buf+r;
165: p = LZH_N + 1 + key[0];
166: lzh->rson[r] = lzh->lson[r] = LZH_NIL;
167: lzh->match_length = 0;
168: for ( ; ; ) {
169: if (cmp >= 0) {
170: if (lzh->rson[p] != LZH_NIL)
171: p = lzh->rson[p];
172: else {
173: lzh->rson[p] = r;
174: lzh->dad[r] = p;
175: return;
176: }
177: } else {
178: if (lzh->lson[p] != LZH_NIL)
179: p = lzh->lson[p];
180: else {
181: lzh->lson[p] = r;
182: lzh->dad[r] = p;
183: return;
184: }
185: }
186: for (i = 1; i < LZH_F; i++)
187: if ((cmp = key[i] - lzh->text_buf[p + i]) != 0)
188: break;
189: if (i > LZH_THRESHOLD) {
190: if (i > lzh->match_length) {
191: lzh->match_position = ((r - p) & (LZH_N - 1)) - 1;
192: if ((lzh->match_length = i) >= LZH_F)
193: break;
194: }
195: if (i == lzh->match_length) {
196: if ((c = ((r - p) & (LZH_N - 1)) - 1)
197: < (unsigned)lzh->match_position) {
198: lzh->match_position = c;
199: }
200: }
201: }
202: }
203: lzh->dad[r] = lzh->dad[p];
204: lzh->lson[r] = lzh->lson[p];
205: lzh->rson[r] = lzh->rson[p];
206: lzh->dad[lzh->lson[p]] = r;
207: lzh->dad[lzh->rson[p]] = r;
208: if (lzh->rson[lzh->dad[p]] == p)
209: lzh->rson[lzh->dad[p]] = r;
210: else
211: lzh->lson[lzh->dad[p]] = r;
212: lzh->dad[p] = LZH_NIL; /* remove p */
213: }
214:
215: static void lzh_delete_node(lzh_t* lzh, short int p) /* Deleting node from the tree */
216: {
217: short int q;
218:
219: if (lzh->dad[p] == LZH_NIL)
220: return; /* unregistered */
221: if (lzh->rson[p] == LZH_NIL)
222: q = lzh->lson[p];
223: else
224: if (lzh->lson[p] == LZH_NIL)
225: q = lzh->rson[p];
226: else {
227: q = lzh->lson[p];
228: if (lzh->rson[q] != LZH_NIL) {
229: do {
230: q = lzh->rson[q];
231: } while (lzh->rson[q] != LZH_NIL);
232: lzh->rson[lzh->dad[q]] = lzh->lson[q];
233: lzh->dad[lzh->lson[q]] = lzh->dad[q];
234: lzh->lson[q] = lzh->lson[p];
235: lzh->dad[lzh->lson[p]] = q;
236: }
237: lzh->rson[q] = lzh->rson[p];
238: lzh->dad[lzh->rson[p]] = q;
239: }
240: lzh->dad[q] = lzh->dad[p];
241: if (lzh->rson[lzh->dad[p]] == p)
242: lzh->rson[lzh->dad[p]] = q;
243: else
244: lzh->lson[lzh->dad[p]] = q;
245: lzh->dad[p] = LZH_NIL;
246: }
247:
248: /*
249: * Tables for encoding/decoding upper 6 bits of
250: * sliding dictionary pointer
251: */
252: /* encoder table */
253: static uchar lzh_p_len[64] = {
254: 0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
255: 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
256: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
257: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
258: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
259: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
260: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
261: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
262: };
263:
264: static uchar lzh_p_code[64] = {
265: 0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
266: 0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
267: 0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
268: 0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
269: 0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
270: 0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
271: 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
272: 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
273: };
274:
275: /* decoder table */
276: static uchar lzh_d_code[256] = {
277: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
278: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
279: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
280: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
281: 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
282: 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
283: 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
284: 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
285: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
286: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
287: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
288: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
289: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
290: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
291: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
292: 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
293: 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
294: 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
295: 0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
296: 0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
297: 0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
298: 0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
299: 0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
300: 0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
301: 0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
302: 0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
303: 0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
304: 0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
305: 0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
306: 0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
307: 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
308: 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
309: };
310:
311: static uchar lzh_d_len[256] = {
312: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
313: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
314: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
315: 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
316: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
317: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
318: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
319: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
320: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
321: 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
322: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
323: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
324: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
325: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
326: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
327: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
328: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
329: 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
330: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
331: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
332: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
333: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
334: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
335: 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
336: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
337: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
338: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
339: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
340: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
341: 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
342: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
343: 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
344: };
345:
346:
347: static int lzh_getbit(lzh_t* lzh, uchar *inbuf, long *incnt, long inlen) /* get one bit */
348: {
349: short int i;
350:
351: while (lzh->getlen <= 8) {
352: if((*incnt)>=inlen)
353: i=0;
354: else
355: i=inbuf[(*incnt)++];
356: lzh->getbuf |= i << (8 - lzh->getlen);
357: lzh->getlen += 8;
358: }
359: i = lzh->getbuf;
360: lzh->getbuf <<= 1;
361: lzh->getlen--;
362: return (i < 0);
363: }
364:
365: static short int lzh_getbyte(lzh_t* lzh, uchar *inbuf, long *incnt, long inlen) /* get a byte */
366: {
367: unsigned short i;
368:
369: while (lzh->getlen <= 8) {
370: if((*incnt)>=inlen)
371: i=0;
372: else
373: i=inbuf[(*incnt)++];
374: lzh->getbuf |= i << (8 - lzh->getlen);
375: lzh->getlen += 8;
376: }
377: i = lzh->getbuf;
378: lzh->getbuf <<= 8;
379: lzh->getlen -= 8;
380: return i >> 8;
381: }
382:
383:
384: /* output c bits */
385: static void lzh_putcode(lzh_t* lzh, short int l, unsigned short c, uchar *outbuf, long *outlen)
386: {
387: lzh->putbuf |= c >> lzh->putlen;
388: if ((lzh->putlen += l) >= 8) {
389: outbuf[(*outlen)++]=(lzh->putbuf >> 8);
390: if ((lzh->putlen -= 8) >= 8) {
391: outbuf[(*outlen)++]=lzh->putbuf;
392: lzh->putlen -= 8;
393: lzh->putbuf = c << (l - lzh->putlen);
394: } else {
395: lzh->putbuf <<= 8;
396: }
397: }
398: }
399:
400:
401: /* initialize freq tree */
402:
403: static void lzh_start_huff(lzh_t* lzh)
404: {
405: short int i, j;
406:
407: for (i = 0; i < LZH_N_CHAR; i++) {
408: lzh->freq[i] = 1;
409: lzh->son[i] = i + LZH_T;
410: lzh->prnt[i + LZH_T] = i;
411: }
412: i = 0; j = LZH_N_CHAR;
413: while (j <= LZH_R) {
414: lzh->freq[j] = lzh->freq[i] + lzh->freq[i + 1];
415: lzh->son[j] = i;
416: lzh->prnt[i] = lzh->prnt[i + 1] = j;
417: i += 2; j++;
418: }
419: lzh->freq[LZH_T] = 0xffff;
420: lzh->prnt[LZH_R] = 0;
421: }
422:
423:
424: /* reconstruct freq tree */
425:
426: static void lzh_reconst(lzh_t* lzh)
427: {
428: short int i, j, k;
429: unsigned short f, l;
430:
431: /* halven cumulative freq for leaf nodes */
432: j = 0;
433: for (i = 0; i < LZH_T; i++) {
434: if (lzh->son[i] >= LZH_T) {
435: lzh->freq[j] = (lzh->freq[i] + 1) / 2;
436: lzh->son[j] = lzh->son[i];
437: j++;
438: }
439: }
440: /* make a tree : first, connect children nodes */
441: for (i = 0, j = LZH_N_CHAR; j < LZH_T; i += 2, j++) {
442: k = i + 1;
443: f = lzh->freq[j] = lzh->freq[i] + lzh->freq[k];
444: for (k = j - 1; f < lzh->freq[k]; k--);
445: k++;
446: l = (j - k) * 2;
447:
448: /* movmem() is Turbo-C dependent
449: rewritten to memmove() by Kenji */
450:
451: /* movmem(&lzh->freq[k], &lzh->freq[k + 1], l); */
452: (void)memmove(lzh->freq+k+1,lzh->freq+k, l);
453: lzh->freq[k] = f;
454: /* movmem(&lzh->son[k], &lzh->son[k + 1], l); */
455: (void)memmove(lzh->son+k+1,lzh->son+k, l);
456: lzh->son[k] = i;
457: }
458: /* connect parent nodes */
459: for (i = 0; i < LZH_T; i++) {
460: if ((k = lzh->son[i]) >= LZH_T) {
461: lzh->prnt[k] = i;
462: } else {
463: lzh->prnt[k] = lzh->prnt[k + 1] = i;
464: }
465: }
466: }
467:
468: /* update freq tree */
469:
470: static void lzh_update(lzh_t* lzh, short int c)
471: {
472: short int i, j, k, l;
473:
474: if (lzh->freq[LZH_R] == MAX_FREQ) {
475: lzh_reconst(lzh);
476: }
477: c = lzh->prnt[c + LZH_T];
478: do {
479: k = ++lzh->freq[c];
480:
481: /* swap nodes to keep the tree freq-ordered */
482: if (k > lzh->freq[l = c + 1]) {
483: while (k > lzh->freq[++l]);
484: l--;
485: lzh->freq[c] = lzh->freq[l];
486: lzh->freq[l] = k;
487:
488: i = lzh->son[c];
489: lzh->prnt[i] = l;
490: if (i < LZH_T) lzh->prnt[i + 1] = l;
491:
492: j = lzh->son[l];
493: lzh->son[l] = i;
494:
495: lzh->prnt[j] = c;
496: if (j < LZH_T) lzh->prnt[j + 1] = c;
497: lzh->son[c] = j;
498:
499: c = l;
500: }
501: } while ((c = lzh->prnt[c]) != 0); /* do it until reaching the root */
502: }
503:
504: static void lzh_encode_char(lzh_t* lzh, unsigned short c, uchar *outbuf, long *outlen)
505: {
506: unsigned short i;
507: short int j, k;
508:
509: i = 0;
510: j = 0;
511: k = lzh->prnt[c + LZH_T];
512:
513: /* search connections from leaf node to the root */
514: do {
515: i >>= 1;
516:
517: /*
518: if node's address is odd, output 1
519: else output 0
520: */
521: if (k & 1) i += 0x8000;
522:
523: j++;
524: } while ((k = lzh->prnt[k]) != LZH_R);
525: lzh_putcode(lzh, j, i, outbuf, outlen);
526: lzh->code = i;
527: lzh->len = j;
528: lzh_update(lzh,c);
529: }
530:
531: static void lzh_encode_position(lzh_t* lzh, unsigned short c, uchar *outbuf, long *outlen)
532: {
533: unsigned short i;
534:
535: /* output upper 6 bits with encoding */
536: i = c >> 6;
537: lzh_putcode(lzh, lzh_p_len[i], (unsigned short)(lzh_p_code[i] << 8), outbuf, outlen);
538:
539: /* output lower 6 bits directly */
540: lzh_putcode(lzh, 6, (unsigned short)((c & 0x3f) << 10), outbuf, outlen);
541: }
542:
543: static void lzh_encode_end(lzh_t* lzh, uchar *outbuf, long *outlen)
544: {
545: if (lzh->putlen) {
546: outbuf[(*outlen)++]=(lzh->putbuf >> 8);
547: }
548: }
549:
550: static short int lzh_decode_char(lzh_t* lzh, uchar *inbuf, long *incnt, long inlen)
551: {
552: unsigned short c;
553:
554: c = lzh->son[LZH_R];
555:
556: /*
557: * start searching tree from the root to leaves.
558: * choose node #(lzh.son[]) if input bit == 0
559: * else choose #(lzh.son[]+1) (input bit == 1)
560: */
561: while (c < LZH_T) {
562: c += lzh_getbit(lzh,inbuf,incnt,inlen);
563: c = lzh->son[c];
564: }
565: c -= LZH_T;
566: lzh_update(lzh,c);
567: return c;
568: }
569:
570: static short int lzh_decode_position(lzh_t* lzh, uchar *inbuf, long *incnt, long inlen)
571: {
572: unsigned short i, j, c;
573:
574: /* decode upper 6 bits from given table */
575: i = lzh_getbyte(lzh,inbuf,incnt,inlen);
576: c = (unsigned)lzh_d_code[i] << 6;
577: j = lzh_d_len[i];
578:
579: /* input lower 6 bits directly */
580: j -= 2;
581: while (j--) {
582: i = (i << 1) + lzh_getbit(lzh,inbuf,incnt,inlen);
583: }
584: return c | (i & 0x3f);
585: }
586:
587: /* Compression */
588:
589: /* Encoding/Compressing */
590: /* Returns length of outbuf */
591: long LZHCALL lzh_encode(uchar *inbuf, long inlen, uchar *outbuf)
592: {
593: short int i, c, len, r, s, last_match_length;
594: long incnt,outlen; /* textsize=0; */
595: lzh_t lzh;
596: memset(&lzh,0,sizeof(lzh));
597:
598: #ifdef LZH_DYNAMIC_BUF
599:
600: if((lzh.text_buf=(uchar *)MALLOC(LZH_N + LZH_F - 1))==NULL)
601: return(-1);
602: if((lzh.freq=(unsigned short*)MALLOC((LZH_T + 1)*sizeof(unsigned short)))==NULL) {
603: FREE(lzh.text_buf);
604: return(-1); }
605: if((lzh.prnt=(short *)MALLOC((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) {
606: FREE(lzh.text_buf);
607: FREE(lzh.freq);
608: return(-1); }
609: if((lzh.son=(short *)MALLOC((LZH_T + 1) * sizeof(short)))==NULL) {
610: FREE(lzh.text_buf);
611: FREE(lzh.prnt);
612: FREE(lzh.freq);
613: return(-1); }
614: if((lzh.lson=(short *)MALLOC((LZH_N + 1)*sizeof(short)))==NULL) {
615: FREE(lzh.text_buf);
616: FREE(lzh.prnt);
617: FREE(lzh.freq);
618: FREE(lzh.son);
619: return(-1); }
620: if((lzh.rson=(short *)MALLOC((LZH_N + 257)*sizeof(short)))==NULL) {
621: FREE(lzh.text_buf);
622: FREE(lzh.prnt);
623: FREE(lzh.freq);
624: FREE(lzh.son);
625: FREE(lzh.lson);
626: return(-1); }
627: if((lzh.dad=(short *)MALLOC((LZH_N + 1)*sizeof(short)))==NULL) {
628: FREE(lzh.text_buf);
629: FREE(lzh.prnt);
630: FREE(lzh.freq);
631: FREE(lzh.son);
632: FREE(lzh.lson);
633: FREE(lzh.rson);
634: return(-1); }
635: #endif
636:
637: incnt=0;
638: memcpy(outbuf,&inlen,sizeof(inlen));
639: outlen=sizeof(inlen);
640: if(!inlen) {
641: #ifdef LZH_DYNAMIC_BUF
642: FREE(lzh.text_buf);
643: FREE(lzh.prnt);
644: FREE(lzh.freq);
645: FREE(lzh.son);
646: FREE(lzh.lson);
647: FREE(lzh.rson);
648: FREE(lzh.dad);
649: #endif
650: return(outlen); }
651: lzh_start_huff(&lzh);
652: lzh_init_tree(&lzh);
653: s = 0;
654: r = LZH_N - LZH_F;
655: for (i = s; i < r; i++)
656: lzh.text_buf[i] = ' ';
657: for (len = 0; len < LZH_F && incnt<inlen; len++)
658: lzh.text_buf[r + len] = inbuf[incnt++];
659: /* textsize = len; */
660: for (i = 1; i <= LZH_F; i++)
661: lzh_insert_node(&lzh,(short)(r - i));
662: lzh_insert_node(&lzh,r);
663: do {
664: if (lzh.match_length > len)
665: lzh.match_length = len;
666: if (lzh.match_length <= LZH_THRESHOLD) {
667: lzh.match_length = 1;
668: lzh_encode_char(&lzh,lzh.text_buf[r],outbuf,&outlen);
669: } else {
670: lzh_encode_char(&lzh,(unsigned short)(255 - LZH_THRESHOLD + lzh.match_length)
671: ,outbuf,&outlen);
672: lzh_encode_position(&lzh,lzh.match_position
673: ,outbuf,&outlen);
674: }
675: last_match_length = lzh.match_length;
676: for (i = 0; i < last_match_length && incnt<inlen; i++) {
677: lzh_delete_node(&lzh,s);
678: c=inbuf[incnt++];
679: lzh.text_buf[s] = (uchar)c;
680: if (s < LZH_F - 1)
681: lzh.text_buf[s + LZH_N] = (uchar)c;
682: s = (s + 1) & (LZH_N - 1);
683: r = (r + 1) & (LZH_N - 1);
684: lzh_insert_node(&lzh,r);
685: }
686: /***
687: if ((textsize += i) > printcount) {
688: printf("%12ld\r", textsize);
689: printcount += 1024;
690: }
691: ***/
692: while (i++ < last_match_length) {
693: lzh_delete_node(&lzh,s);
694: s = (s + 1) & (LZH_N - 1);
695: r = (r + 1) & (LZH_N - 1);
696: if (--len) lzh_insert_node(&lzh,r);
697: }
698: } while (len > 0);
699: lzh_encode_end(&lzh,outbuf,&outlen);
700: /*
701: printf("input: %ld (%ld) bytes\n", inlen,textsize);
702: printf("output: %ld bytes\n", outlen);
703: printf("output/input: %.3f\n", (double)outlen / inlen);
704: */
705:
706: #ifdef LZH_DYNAMIC_BUF
707: FREE(lzh.text_buf);
708: FREE(lzh.prnt);
709: FREE(lzh.freq);
710: FREE(lzh.son);
711: FREE(lzh.lson);
712: FREE(lzh.rson);
713: FREE(lzh.dad);
714: #endif
715:
716: return(outlen);
717: }
718:
719: /* Decoding/Uncompressing */
720: /* Returns length of outbuf */
721: long LZHCALL lzh_decode(uchar *inbuf, long inlen, uchar *outbuf)
722: {
723: short int i, j, k, r, c;
724: unsigned long int count;
725: long incnt,textsize;
726: lzh_t lzh;
727:
728: memset(&lzh,0,sizeof(lzh));
729: #ifdef LZH_DYNAMIC_BUF
730:
731: if((lzh.text_buf=(uchar *)MALLOC((LZH_N + LZH_F - 1)*2))==NULL)
732: return(-1);
733: if((lzh.freq=(unsigned short *)MALLOC((LZH_T + 1)*sizeof(unsigned short)))
734: ==NULL) {
735: FREE(lzh.text_buf);
736: return(-1); }
737: if((lzh.prnt=(short *)MALLOC((LZH_T + LZH_N_CHAR)*sizeof(short)))==NULL) {
738: FREE(lzh.text_buf);
739: FREE(lzh.freq);
740: return(-1); }
741: if((lzh.son=(short *)MALLOC((LZH_T + 1) * sizeof(short)))==NULL) {
742: FREE(lzh.text_buf);
743: FREE(lzh.prnt);
744: FREE(lzh.freq);
745: return(-1); }
746:
747: #endif
748:
749: incnt=0;
750: memcpy(&textsize,inbuf,sizeof(textsize));
751: incnt+=sizeof(textsize);
752: if (textsize == 0) {
753: #ifdef LZH_DYNAMIC_BUF
754: FREE(lzh.text_buf);
755: FREE(lzh.prnt);
756: FREE(lzh.freq);
757: FREE(lzh.son);
758: #endif
759: return(textsize); }
760: lzh_start_huff(&lzh);
761: for (i = 0; i < LZH_N - LZH_F; i++)
762: *(lzh.text_buf+i) = ' ';
763: r = LZH_N - LZH_F;
764: for (count = 0; count < (unsigned long)textsize; ) {
765: c = lzh_decode_char(&lzh,inbuf,&incnt,inlen);
766: if (c < 256) {
767: outbuf[count]=(uchar)c;
768: #if 0
769: if(r>(LZH_N + LZH_F - 1) || r<0) {
770: printf("Overflow! (%d)\n",r);
771: getch();
772: exit(-1); }
773: #endif
774: *(lzh.text_buf+r) = (uchar)c;
775: r++;
776: r &= (LZH_N - 1);
777: count++;
778: } else {
779: i = (r - lzh_decode_position(&lzh,inbuf,&incnt,inlen) - 1)
780: & (LZH_N - 1);
781: j = c - 255 + LZH_THRESHOLD;
782: for (k = 0; k < j && count<(unsigned long)textsize; k++) {
783: c = lzh.text_buf[(i + k) & (LZH_N - 1)];
784: outbuf[count]=(uchar)c;
785: #if 0
786: if(r>(LZH_N + LZH_F - 1) || r<0) {
787: printf("Overflow! (%d)\n",r);
788: exit(-1); }
789: #endif
790: *(lzh.text_buf+r) = (uchar)c;
791: r++;
792: r &= (LZH_N - 1);
793: count++;
794: }
795: }
796: }
797: /***
798: printf("%12ld\n", count);
799: ***/
800:
801: #ifdef LZH_DYNAMIC_BUF
802: FREE(lzh.text_buf);
803: FREE(lzh.prnt);
804: FREE(lzh.freq);
805: FREE(lzh.son);
806: #endif
807:
808: return(count);
809: }
810:
811:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.