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